显著性应用--论文笔记--Automatic Image Cropping : A Computational Complexity Study

论文信息：
作者：Jiansheng Chen Gaocheng Bai Shaoheng Liang Zhengqin Li（清华大学）
期刊：CVPR
任务：图片裁剪
年份：2016年
全文：PDF
主要内容：提出一种低复杂度的算法，能够在图片裁剪任务中，满足最大化重要信息和最小化裁剪面积的要求

论文笔记--Automatic Image Cropping : A Computational Complexity Study

• 摘要

• 1.介绍

• • 1.1相关工作
  • 1.2 动机

• 2.问题的公式

• 3.算法与分析

• • 3.1 Problem 1
  • 3.2 Problem 2
  • 3.3 Problem 3
  • 3.4 \tau的自动选择

• 4.实验

• 5.结论

摘要

基于注意力机制的图像裁剪旨在保留图像中最关键的部分。该方法的主要目标是通过最小化矩形面积来实现注意力分布的最大化。我们证明，在适当的情况下（即当特定条件满足时），可以通过低计算复杂度的高效算法实现这一目标。在一个实际应用中，默认设定裁剪矩形的比例时，默认情况下所需计算资源与像素数量呈线性关系。此外，在探索多目标矩形裁剪的同时,我们还提出了一个能够实现全自动图像处理的新模型.

1.介绍

在过往的研究中,学者们已开发出多种基于内容感知的图像缩放/尺寸修改方法.这些方法主要可分为两大类:其一是关注注意力机制的方法,其二是侧重于视觉美观性的方案.

1.1相关工作

主要通过关注注意力机制来实现对图像尺寸缩减过程中具有视觉价值部分的突出显示。以美学为导向的方法主要目标是最大化地提升压缩后图像的画面吸引力。尽管存在一些共同特点但由于多种外部条件的影响视觉美学的表现形式会呈现出显著的多样性包括但不限于文化背景个人经历受教育程度以及心理状态等因素都会对其表现产生重要影响。因此当前广泛采用的照片压缩算法多建立在对图片质量评估体系的研究基础之上并依据图片的一些基本属性如低层次特征以及经验导出的原则来进行处理。

1.2 动机

在现有的基于注意力机制的图像裁剪技术中，生成注意力图后的一个典型任务就是确定一个最优裁剪边界。本文的核心研究重点就围绕这一问题展开。一般情况下，在优化图像裁剪时所追求的主要目标是实现最小区域覆盖与保留较高像素注意值之间的权衡关系。然而，在处理高分辨率图像时由于候选区域数量庞大，在这种情况下采用暴力搜索可能会导致计算效率低下。为了提高算法效率，在这项研究中我们提出了若干针对最优矩形搜索问题的设计方案，并着重开发了低计算复杂度的优化策略以解决这些问题。

2.问题的公式

如上所述，在给定的注意力图上搜索最佳裁剪矩形的目标是双重的。

• 首先，缩减矩形面积以去除无关紧要的部分。
  • 其次，增强矩形内注意力值的总和以尽量保留重要部分。

这两个目标是对偶的，问题可以用任何一种方式来定义。

我们假设 G \in \mathbb{R}^{m \times n} 是从图像 I \in \mathbb{R}^{h \times w} 中提取出的一个非负注意力图（attention map）。该注意力图 G 中较高的数值对应于图像 I 中具有高重要性的像素。在不丧失一般性的情况下,我们设定最优裁剪矩形搜索问题为问题1 (Problem 1)。其中 \tau \in [0, 1] 表示需要保留的所有注意力中的最小百分比；而 \ddot R = (x_1, y_1, x_2, y_2) 则是满足这一要求所选用的最小矩形区域。

Problem 1(最小矩形搜索) 设定一个百分比阈值 \tau ，确定在图 G 中面积最小的矩形 \ddot R(\tau) ，使其满足方程（1）

\sum_{p\in \ddot R(\tau)}G(p) \geq\tau\sum_pG(p), \tau \in [0,1]..............................(1)
为了避免歧义，我们记 \sum_{p\in \ddot R}G(p) 为 \sum_{\ddot R}G, 记 \sum_pG(p) 为 \sum G.
同样，一个矩形如果满足(1)，则称为有效的矩形。

在数字图像处理领域, 每个像素都可以被视作其视觉重要性的一种评估指标. 从理论上讲, 在数字图像中每个像素通常承载着一定程度的画面细节信息. 因此, 在本研究中我们假定注意力价值均为非负数值, 并进一步探讨其在图像处理中的应用效果. 此外, 这一假定与现有文献中广泛采用的关注力机制模型具有高度一致性, 并且这些文献均未提及过此类特殊限制条件.

定义符号|| \ddot R(\tau) ||为\ddot R(\tau)所对应的矩形区域面积。对于任何一张图像G来说，在τ的变化过程中其对应的矩形区域面积都会呈现递增的趋势；具体而言，

\forall \tau_1 \geqslant \tau_2, || \ddot R(\tau_1) || \geqslant || \ddot R(\tau_2) ||

为了消除歧义，在整个注意力图中设定所有可能矩形区域的最大值为其总面积单位值，
即：

\max_{R} ||R|| = 1

这样一来，
数值 ||\dot{\Gamma}R|| 就能够反映 \dot{\Gamma}R
在原始图像空间中的占据比例。

特别值得注意的是，在设定一个最低比例\tau时，\ddot R(\tau)可能会存在多个不同的结果。然而，在实践中这是可以被接受的，因为这只会导致几种不同的裁剪方案，并且这些方案所覆盖区域的面积及其视觉影响力保持一致。值得注意的是，在这种情况下,|| \ddot R(\tau) || 的变化并不遵循严格的单调递增特性, 因此可能存在两个不同的比例\tau_1和\tau_2, 虽然它们不相等, 但其范数可能相等, 这种现象通常出现在两者之间的差异非常微小时有发生

初步看来，在解决实际问题时会遇到的问题1与著名的最大子矩阵问题具有高度相似性。具体来说，在这种情况下我们需要找到一个矩阵，并确定其子矩阵\ddot S的元素之和达到最大值[2][21]。值得注意的是尽管这两个问题在表面上表现得极其相似但它们的本质却存在显著差异

另一个实际考量涉及图像重定向应用的相关性。当前阶段,不同显示设备（如台式PC、移动电话及可穿戴设备）上的纵横比差异显著,这一特点给图像处理带来了挑战。为实现最佳视觉效果,一个具有潜力的选择是在保证目标展示区域的比例一致下进行裁剪,这种做法直接关联到问题2的具体定义

问题2（基于固定长宽比的矩形搜索）_设定一个百分比τ，在图G中寻找具有最小面积的该类矩形\ddot R(\tau, r)，其中r>0为预先设定的比例因子，并符合公式（1）的要求。

在以往的研究中对该问题的关注相对较少, 但有时在处理涉及多个视觉上重要的图像时, 单独选取一个剪切框并不合适, 因为这些关键区域往往呈分散分布状态。如图3所示, 当\tau被设定为0.75时, 这种现象尤为明显。相比之下, 采用两个矩形而非单个矩形能够有效减少整体面积的一半, 这样处理后的整体面积减半后更为合理, 在视觉效果上也更为理想。基于这一认识基础之上, 我们提出了一个新的问题（problem 3）作为对原有问题（problem 2）的一种扩展

Problem 3 (Multiple Rectangle Search) 设给定一个百分比τ，在图G中确定不超过N个互不相交且具有固定宽高比r>0的所有可能集合{R₁,R₂,…,R_N}。其并集定义为\ddot{R}(\tau,r,N)=\bigcup_{i=1}^N\dot{R}_i；为了使总覆盖面积|\!|\,\ddot{R}\!|\!|最小化的同时满足条件（1）。

在问题3中引入了更多裁剪矩形从而增强了搜索空间的多样性，并降低了必须保留的总面积提升了处理效率和效果。然而这种扩展方式可能导致问题复杂度上升，在mentioned context中我们仅探讨N=2的情形。需要注意的是a caveat is that for some images, employing multiple rectangles may not yield optimal results.in addressing problem 3, we might encounter empty or unnecessary rectangles.

3.算法与分析

为了便于解决空间离散化问题，在本研究中考虑注意力图G具有m行n列的结构，并满足m\leq n。针对上述空间离散化问题，我们采用了以下近似方法来计算纵、横比率。具体而言，在给定一个纵、横比率r的情况下，在假定某个候选矩形高度h的前提下，则其宽度可通过下式进行估算：

w = \left \lceil h \times r \right \rceil...............................................(3)

在给定情况下, 我们为了方便起见, 采用了类似于矩阵符号的方式: 其中G(i,j)表示图中节点对之间存在的注意力权重, 其中i取值于区间[1,m], j取值于区间[1,n].

为了避免歧义，当i\leq0或j\leq0时，令G(i,j)=0。

我们定义了基于 G 的积分图表示为 G^+ ：对于任意节点对 (i,j) ，其值等于从节点 (1,1) 到节点 (i,j) 所有路径权重之和。为了简化描述方式时，则引入了列积分数值表 C_j = \sum_{k=1}^{n}\sum_{l=1}^{j} G(k,l) 。进一步简化表达方式时，则引入了列积分数值表 C_j = \sum_{k=1}^{n}\sum_{l=1}^{j} G(k,l) 。

可以用累加求和并行计算得到G^+和G_c^+，总计算复杂度为O(mn)

3.1 Problem 1

为解决问题1而采用的一种暴力法则是系统性地遍历图G中的所有可能矩形，并从中筛选出满足条件(1)的那个最小面积的矩形。更详细地说，在图5(a)中所示位置上，该算法针对图G中的每一个点(i, j)，考察所有以该点为左上角界的矩形R。

基于公式（4）中的积分图技术，在R区域内可以准确地计算注意力值的累加：
\sum_RG = G^+(i_2,j_2)-G^+(i_2,j_1-1)-G^+(i_1-1,j_2)+G^+(i_1-1,j_1-1).......(4)

对于每一个位于左上方的顶点，在其周围存在数量为 O(mn) 的矩形区域需要进行检查。为了系统性地遍历这些角落位置会导致计算复杂度上升为 O(m^2n^2) 的水平

仔细观察图5(a)，可以看出，在蛮力算法中包含了大量冗余运算。举个例子来说,一旦确定R是一个有效的矩形,即满足条件（1）,那么所有面积超过R的区域都被排除在外。进一步优化的方法包括只考虑那些以(i_1,j_1)为左上角且右下角为(i_2,j > j_2)的区域。

假设我们正在考察所有候选矩形，则它们的上边界位于第i_{\text{upper}}}行、下边界位于第i_{\text{lower}}}行（如图6(a)所示）。当阴影区域有效时，在这种情况下，则表示我们在寻找两个尽可能接近的列索引j_{\text{left}}}和j_{\text{right}}}之间所对应的值范围。通过将第i_{\text{upper}}}行按列累加至第i_{\text{lower}}}行，则可将这一二维搜索空间转换为一维的问题（如图6(a)底部所示）。

我们关注一个非负输入向量，并希望找到其元素和大于或等于设定阈值的最小长度连续子向量（ shortest subvector ）。在示例中所述的情形下，该阈值被设定为\tau\sum G；而该输入向量则由公式(5)给出：

\sum_{i=i_1}^{i_2} G(i,:) = G_c^+(i_2,:)-G_c^+(i_1-1,:)\..........................(5)

此外，在这种情况下我们可以使用算法1（ Algorithm 1 ）来高效地解决这个问题；其中st和ed分别表示当前处理的最短子向量起始点与结束点。

该算法的主要思路在于确定一个合适的候选子数组，在后续步骤中会逐步缩减其长度，并使得以st为起点的所有子数组都不会被再次考虑，从而有效避免了重复计算。

特别地，当找不到满足条件的子数组或T\leq0时，j_1= j_2=0。

每次循环迭代时，在st或ed变量中会递增。观察到，在程序退出前这两个变量的值均不会超越给定的n值。由此可推断，在最坏情况下每次循环体内会执行两次运算。由此可知该算法的时间复杂度上界为O(n)

结合算法1和图6(a)所示的思想，提出算法2（Algorithm 2 ）来解决问题1。

它基于遍历所有可能的 (i_1,i_2) 组合的方法，并找到对应的最短子数组来实现算法的基本思路。
其中涉及的主要步骤包括计算两个方向上的积分图以及利用这些积分图来确定最佳匹配窗口。
在实际应用中发现该算法的时间复杂度约为 O(NM^3) ，其中 N 是图像的高度 M 是宽度 该算法通过逐层缩减搜索范围并结合多级特征检测能够有效提升检测速度同时保证较高的检测精度

3.2 Problem 2

受剪切矩形长宽比限制的影响，使得问题2本质上比问题1更为简单。从中提取出蛮力算法的表现可看出这一点。

基于前面所述，在一个长宽比为r且高度为h的矩形中, 宽度将严格确定地由公式(3)给出. 由此可知, 在图5(b)中, 位于左上方的所有可能矩形(i_1,j_1) 的数目减少到一定程度. 具体来说, 它的数量取决于不同高度值的数量, 大约为O(m). 遍历所有可能的(i_1,i_2)组合时, 蛰物算法的整体计算复杂度达到O(m^2n).

改进算法的思路如图6(b)所示。
在保持长宽比恒定的前提下，在所有由i₁和i₂界定的候选矩形中存在相同尺寸w₀×h₀（其中w₀ = i₂ - i₁ + 1）。

改进算法的思路如图6(b)所示。
在保持长宽比恒定的前提下，在所有由i₁和i₂界定的候选矩形中存在相同尺寸w₀×h₀（其中w₀ = i₂ - i₁ + 1）。

显然，在这些矩形中共有O(n)个不同的情况。为了获得最佳效果，我们需要在这些矩形中寻找总和最大的那个。与上一节的思想相似，在此问题中也存在着将其转化为一个一维搜索问题的可能性。具体而言，在我们的例子中，这个最大值应至少达到给定阈值τ∑G。这一问题相对简单，并可通过复杂度为O(n)的方法轻松解决。如算法3（Algorithm 3）所示。

当运行算法3时，在遍历所有可能的(i_1, i_2)的情况下就能完美地解决问题2。
遗憾的是这种方法并无实质价值……因为它的计算复杂度达到了O(m^2n)……这与暴力搜索效率相当。

如图所示，在图6(b)中, 候选区域的面积大小完全取决于i_1至i_2的距离。当固定一个特定的i_1值时, 若发现某一个i_2存在有效的候选区域, 则无需再考虑下方区域中的任何位置, 因为这些位置将导致候选区域的面积会显著增大. 基于此认识, 提出了算法4(Algorithm 4）。

两个指针 i_1和i_2 分别指向候选矩形的上边界和下边界。

我们使用图7来帮助证明算法4的正确性。

我们引入一个布尔函数 v(i,j) 来标识由第 i 行和第 j 行所界定的有效矩形是否存在。基于 G 的非负性质质可知该函数满足方程 (6)，即：

v(i,j)=0 \Rightarrow \forall i^*,j^* \in [i,j], v(i^*,j^*)=0 \quad (6)

假设在算法运行某一阶段时观察到存在某个区间使得 v[i,j]=\text{true} 如图 7(a) 所示。依据算法逻辑将左边界左移至当前最左侧位置使得新区间 v[i',j] 不再包含有效矩形 如图 7(b) 所示。这表明左侧边界的左侧相邻区间仍然存在有效矩形标识。接着再将右边界左移一位从而恢复了有效性。

为了确保完整性，我们应该检查当i_2^*\in[i_2,i_2')并且i_1^*\in[1,i_2^*]时所有的情况。

• 如果i_1^*\in[1,i_1'-2], 所有以i_1^*和i_2^*为边界的矩形框都可以被安全地忽略，因为它肯定大于已经被认为是有效的边界为i_1'-1和i_2 的矩形。因为，i_2^*-i_1^*\geq i_2-(i_1'-2)> i_2-(i_1'-1).
• 当i_1^* = i_1'-1,则i_2^* = i_2的情况已经被考虑到了，而其他的情况i_2^* > i_2由于明显增加的矩形面积大小同样可以忽略。
• 如果i_1^*\in[i_1',i_2^*]: 由于i_1^*,i_2^*\in[i_1',i_2'-1],并且v(i_1',i_2'-1)=0,根据公式6，我们有v(i_1^*,i_2^*) = 0。通过整个算法的执行，上述推理是有效的。

算法4的计算复杂度较低，在每次循环中变量i_1或i_2都会被递增1。由于退出条件要求i_1和i_2都不超出范围m，在这种情况下循环体最多只会运行2m次。因此总的计算复杂度为O(mn)。考虑到集合G中共有m×n个元素，并且每个元素都需要进行一次基本操作才能完成任务，则这一过程实际上构成了该问题的基本下限。

3.3 Problem 3

略

3.4 \tau的自动选择

按照我们所定义的，在τ的意义上指的是被保留下来的注意力占比。一般而言，在实际应用中我们可以依据经验和用户的设定来确定这一参数值。值得注意的是由于我们提出的方法计算负担不重因此我们甚至可以让用户实现对τ值的实时调整这一功能这使得系统操作更加灵活然而探索自动生成τ值的可能性仍然具有一定的理论价值因为对于所有属于区间[0,1]范围内的τ值函数\ddot R(\tau)始终存在这使得整个分析过程得以简化基于此本研究仅聚焦于问题1来进行深入探讨

鉴于图像裁剪的特性，在选择τ值时主要取决于||Ẅ(R(τ))||这一数学函数的具体属性。值得注意的是，在不同注意力图中这一范数表现出显著差异性。当处理一个所有像素同等重要的单一注意力掩码时，则有||Ẅ(R(τ))|| = τ本身。对于正价值注意力掩码而言，在τ=0时该范数值为零，在τ=1时则等于一。

在现实场景中的图像中

为了进一步验证上述观察结果，在1,000张随机选取的Microsoft COCO图片中计算了log(||\ddot R(τ)||)与log(τ)之间的Pearson相关系数，并发现其均值及标准差分别为0.995及± 0.表明该对数线性假设具有很强的统计学有效性

此乃我们所提出的简便幂函数模型：
||\ddot{R}(\tau)|| = \tau^{\gamma}, (\gamma \geq 1)
其中变量\gamma实际上被用于测定意向图的浓度程度。当\gamma值越大时，则通常反映较高水平的视觉注意力集中度（如图9(b)所示）。对于任意选定的图像样本，则可通过计算\log(||\ddot{R}(\tau)||)与\log(\tau)之间的线性回归关系来确定参数\gamma的具体数值。

关于argmax的解释（百度）

该过程旨在详细阐述求解公式的步骤（实际上等价于寻找使函数达到极值的关键变量）。请详细说明如何确定\tau使得f(\tau)达到最大值？具体而言，请推导出函数的最大值点对应的\tau取值为多少。

令f'(\tau) = 0,可得：

\tau = (1+\gamma)^{-1/\gamma}

若变量\tau满足\tau < (1+\gamma)^{-1/\gamma}时，则该函数f在其定义域内表现出增长趋势；
反之，在\tau \geq (1+\gamma)^{-1/\gamma}的情况下，则该函数f表现出递减特性。

故，当\tau = (1+\gamma)^{-1/\gamma}时，f(\tau)取得最大值。

4.实验

本研究的主要目标是通过提升矩形裁剪搜索算法的速度来实现图像处理任务中的高效运算。然而值得强调的是，在视觉感知任务中，注意力图的质量对结果表现具有决定性影响。在以下展示的所有视觉结果中，我们采用了两种不同的方法生成注意力地图，并通过对比实验验证了其有效性。其中黄、红区域分别基于文献[8]和[10]所生成的关注图进行计算。

[8]:S. Goferman, L. Zelinik-Manor, and A. Tal. Context-aware saliency detection. IEEE Trans. PAMI, 34(10):1915–1926, 2012. 2, 8
[10]:T. Judd, K. Ehinger, F. Durand, and A. Torralba. Learning to predict where humans look. In ICCV, 2009. 2, 8

我们实验中使用的所有图像均来自Microsoft COCO数据库[12]这一来源。其中图十与图十一分别对应问题一设定的最小面积裁剪方案，在不同参数设置下呈现出明显的差异性特征。通过图十可以看出τ参数对结果的影响情况及其变化趋势，在不同τ值下所得切割区域的位置及尺寸均有所变化可见，在不同τ值下所得切割区域的位置及尺寸均有所变化通过图十一可以看出自动调节τ值的有效性这一结论进一步得到了印证

如图12所示，在问题2中对高宽比的变化进行了可视化展示。这一发现非常令人意外的是，在不同长宽比下选择的裁剪矩形似乎都具有合理性。图13是多个矩形的裁剪结果。参考文献[10]中所提出的注意力机制特意突出了图像中心区域的高度视觉重要性这一特点，在图13所示的裁剪结果中这种现象表现得尤为明显。

我们在随机选取的1000张图像上进行了多个对比分析，并对所提出的方法与传统暴力穷举方法的时间效率进行了详细比较。实验环境设置于一台配备3.6GHz CPU和16GB内存的台式电脑上，并通过Matlab平台完成。如图所示，在图中展示的结果表明，在不同τ值下的加速效果具有显著差异性。所有标注信息均来自文献[8]中的方法构建，并且m=188,n=250。通过该测试集上的实验分析可知，在计算所有τ值的过程中所花费的时间平均为137.8ms（±标准差），而针对τ=...的情况则仅消耗约4.2ms时间。

5.结论

本研究聚焦于基于注意力机制下的图象裁员优化問題中最佳矩形搜索策略所需的时间複雜度評估。在不同應用場景及其特徵屬性分析基礎上，在本部分提出了若干個關鍵問題模型，并构建了低時間複雜度優化算法。此外, 本研究開拓了一種新型自動化的全場景圖象修剪方式，在关注 preserved重要区域的基础上实现了高效修剪过程。实验测试表明所提出的方案在有效性能方面表现优异

在今后的研究中还存在一些问题。例如，

• 视觉满意度与其裁剪价值间的对比关系;
  • 不同注意力图的融合可能性探讨。
  • 将此研究延展至基于美学导向的图像裁剪方法同样具有重要意义。

该项目得到了清华大学自主科研项目的资金支持（20131089382）以及北京市高等教育青年精英教师项目的 Partial Support（YETP0104）和国家自然科学基金面上项目的资助（61101152）。