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

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

摘要

基于注意的图像裁剪是为了保留图像中最重要的区域。
这种方法的一个常见任务是寻找集中注意力最大化的最小矩形。
我们证明，在适当的公式下，可以使用低计算复杂度的高效算法来完成这一任务。
在一个实际有用的场景中，裁剪矩形的长宽比是给定的，这个问题可以用与图像像素数线性的计算复杂度来解决。
我们还研究了多矩形裁剪的可能性，以及一种促进全自动图像裁剪的新模型.

1.介绍

之前的研究人员已经提出了许多上下文感知的图像裁剪/大小调整方法，
这些方法大致可以分为两类: ①以注意为基础的方法和②以美学为导向的方法

1.1相关工作

基于注意的方法的基本思想是试图在裁剪或调整大小后保留图像中视觉上重要的区域。
以美学为导向的方法旨在最大限度地提高裁剪图像的视觉吸引力。
视觉美学虽然有一定的共性，但也会受到文化、个人经历、受教育程度甚至心理状态[4]等主观因素的影响。
因此，目前大多数以美学为导向的图像裁剪方法都是基于照片质量评价研究[11][3][22]，使用图像的某些客观方面，如低水平图像特征和经验的照片合成规则。

1.2 动机

在大多数现有的基于注意力的图像裁剪方法中，生成注意力图后的一个常见任务是寻找一个最优的裁剪矩形。这次论文最主要的就是关注这一点。
通常，这种最佳矩形搜索过程的目的是在最小化裁剪面积和最大化其中的总像素注意值之间达成一个折衷。
考虑到大量可能的候选矩形，暴力搜索可能会非常缓慢。
在这项工作中，我们提出了几个最优矩形搜索问题的实用公式和设计低计算复杂度的算法来解决它们。

2.问题的公式

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

• 首先，最小化矩形的面积，以裁剪掉视觉上不重要的图像区域。
• 其次，最大化矩形内的注意值之和，尽可能保留视觉上重要的图像区域。

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

假设 $G$ 是一个从一幅图像 $I$ 中提取得到的非负值注意力图（attention map），在G中更高的视觉注意值对应图像 $I$ 中的更高视觉重要性的像素。 在没有失去普遍性的情况下,我们制定最优裁剪矩形搜索问题,问题1（Problem 1）, 其中 $\tau$ 是需要保留的全部注意力的最小百分比和 $\ddot R$ 是是满足此要求的最小矩形。

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)，则称为有效的矩形。

图像像素的注意值可以看作是对其视觉重要性的度量。可以合理地认为，每个像素都可能包含一定数量的视觉信息。因此，在这项研究中，我们简单地假设注意力价值是非负的。这与大多数现有的计算注意力图[9][10][25][8]的工作是一致的。

让 $|| \ddot R(\tau) ||$表示 $\ddot R(\tau)$的矩形区域面积。对于任意一个图像G， $|| \ddot R(\tau) ||$ 都是关于 $\tau$ 的递增函数，即：
$\forall \tau_1\geq\tau_2, || \ddot R(\tau_1) ||\geq || \ddot R(\tau_2) ||...............................(2)$
为了避免歧义，我们设置整张注意图的矩形区域面积为1，所以数值 $||\ddot R||$代表 $\ddot R$ 在 $G$ 中占的面积的百分比。

需要强调的是，当给定一个最小百分比 $\tau$ ， $\ddot R(\tau)$也可能不是唯一的。
这在实践中是可以接受的，因为它只会导致不同的裁剪结果，但面积大小和视觉重要性是相同的。
需要注意的是， $|| \ddot R(\tau) ||$ 不是关于 $\tau$ 的单调递增函数。因为有可能当 $\tau_1\neq \tau_2$时， $|| \ddot R(\tau_1) ||= || \ddot R(\tau_2) ||$ 。这通常发生在 $\tau_1和\tau_2$之间的差异非常小的时候。

乍一看，问题1类似于著名的最大子矩阵问题，即寻找一个矩阵，它的子矩阵 $\ddot S$的元素和是最大的[2][21]。尽管这两个问题表面上相似，但本质上是不同的。

图像裁剪的另一个实际考虑是与图像重定向的应用有关。如今，纵横比在不同的显示设备如台式PC、移动电话或可穿戴设备上变化很大。为了达到最佳的显示效率，一个很有前景的选择是让被裁剪的图像与目标显示具有相同的纵横比，这就导致了问题2的定义。

Problem 2(固定长宽比矩形搜索)给定一个百分比率 $\tau$, 在 $G$ 中找到一个面积尽可能小的矩形 $\ddot R(\tau, r)$，具有固定的宽高比 r > 0，以满足公式（1）

在以前的研究中很少提到的一个问题是，有时从包含多个视觉上重要区域的图像中只选择一个裁剪矩形可能不合适，这些区域在空间上分散。图3显示了一个典型的示例，其中将 $\tau$ 设置为0.75。通过选择两个矩形而不是一个矩形，使整个矩形面积缩小了一半，在视觉上更加合理。基于这样的理解，我们定义了问题3，可以看作是问题2的推广。

Problem 3(多个矩形搜索)给定一个百分比率 $\tau$, 在 $G$ 中找出不超过N个的不相交的矩形 $\ddot R_1, \ddot R_2,...,\ddot R_N$, 全部具有固定的宽高比 r > 0，表示这些矩形的并集为 $\ddot R(\tau, r, N) = \ddot R_1 \cup \ddot R_2 \cup ...\cup \ddot R_N$，以满足公式（1）的情况下最小化总的面积 $||\ddot R||$

问题3通过允许更多的裁剪矩形，增加了搜索过程的自由度，通过减少需要保留的总面积大小，提高了图像裁剪的有效性。然而，很明显，这样的泛化将增加问题的复杂性的组合。因此，在本文中我们只讨论N = 2的情况。需要注意的是，对于某些图像，使用多个裁剪矩形可能不是很有利。换句话说，在解决问题3时，可能会发现一些矩形是空的。

3.算法与分析

假设注意图（attention map ）G有m行n列，并且 $m\leq n$。
为了解决上面提到的空间离散化问题，我们使用下面的近似值来计算纵横比。给定一个纵横比 $r$，假设一个候选矩形的高度为 $h$,那么它的宽度计算为：
$w = \left \lceil h \times r \right \rceil...............................................(3)$

对于给定一个注意图 $G$, 我们采用类似矩阵的符号: $G(i,j)$代表第 $i$ 行 ( $i\in[1,m]$) 和第 $j$ 列 ( $j\in[1,n]$)的注意数值；

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

定义关于 $G$ 的积分图 $G^+$ :
$G^+(i,j) = \sum_{k=1}^i\sum_{l=1}^jG(k,l)$
为了简化描述，我们还定义了一个基于列的积分图 $G_c^+$,以按列地存储G的累加和：
$G_c^+ = \sum_{k=1}^iG(k,j)$
下图展示了两张积分图的例子：

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

3.1 Problem 1

解决问题1的一种蛮力算法是穷举检查G中每一个可能的矩形，从而找到满足(1)的最小矩形。
更具体地说，如图5(a)所示，对于G中的每个点(i, j)，算法检查所有矩形R的左上角(i, j)。

利用公式（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的矩形都不再被考虑。一个典型的例子是图5(a)中包含R的大虚线矩形。更激进的做法是，所有左上角是 $(i_1,j_1)$和右下角是 $(i_2,j > j_2)$的矩形都可以安全地忽略。

假设我们正在检查所有的候选矩形，它们的上边界在第 $i_1$ 行，下边界在第 $i_2$ 行，如图6(a)所示。当阴影矩形有效时，我们实际上正在寻找两个彼此尽可能接近的列索引 $j_1和j_2$ 。将第 $i_1$ 行按列累积到第 $i_2$ 行，可以将这个二维问题转化为图6(a)底部所示的一维问题。

给定一个非负输入数组，我们要找出其中元素和大于或等于给定阈值的最短子数组（shortest subarray）。在我们的例子中，阈值是 $\tau\sum G$，并且输入数组是 $\sum_{i=i_1}^{i_2}G(i,:)$。这个输入数组可以通过公式(5)利用复杂度为 $O(n)$的逐列积分图计算：
$\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都会增加1。注意到st和ed在退出时都不会超过n，因此循环体最多执行 $2n$ 次。因此，整体计算复杂度为 $O(n)$。

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

它的基本思想是循环所有可能的 $(i_1,i_2)$，同时找到相应的最短子数组。
第5,6行这两个操作最消耗时间，复杂度都是O(n)。通过对所有可能的 $(i_1,i_2)$进行循环，它们将被执行 $m^2/2$ 次，导致总体计算复杂度为 $O(m^2n)$。或者更准确地说， $O(m^2n+mn)$考虑两个积分图的额外计算。

3.2 Problem 2

由于剪切矩形的长宽比的限制，问题2本质上比问题1简单。从图5(b)中所示的蛮力算法可以看出这一点。

如前所述，给定长宽比为r的矩形的高度h，其宽度将由(3)唯一决定。因此在图5(b)中，左上角可能的矩形 $(i_1,j_1)$ 的数量变得更小了。它实际上是由不同高度值的数量决定的，基本上是 $O(m)$。通过对所有可能的 $(i_1,i_2)$进行循环，蛮力算法的总体计算复杂度为 $O(m^2n)$。

改进算法的思路如图6(b)所示。在长宽比固定的情况下，所有 $i_1和i_2$ 为边界的候选矩形有同样的尺寸w0×h0,其中 $w_0 = i_2-i_1+1$.
显然，有O(n)个不同的这样的矩形。我们只需要在这些矩形中找出注意值总和最大的那个。与上一节的思路类似，这个问题也可以转化为一个一维搜索问题，即寻找一个和最大的定长子数组。具体地说，在我们的例子中，这个最大值应该大于或等于给定的阈值 $\tau\sum G$。这是一个简单的问题，可以很容易地用复杂度 $O(n)$解决，如算法3（Algorithm 3）所示。

在调用算法3时，只需对所有可能的 $(i_1, i_2)$进行循环就可以解决problem 2。不幸的是，这种方法是没有意义的，因为它会导致 $O(m^2n)$ 的计算复杂度，这与暴力搜索是相同的。

在图6(b)中，候选矩形的面积大小完全由 $i_1到i_2$ 的距离决定。因此，对于一个给定的 $i_1$ 的值，如果为某个 $i_2$ 找到了一个有效的矩形，那么 $i_2$ 下面的任何位置，例如 $i_2'$ 在图6(b)中，将不再需要考虑，因为明显增加了矩形面积大小。基于此理解，提出了算法4(Algorithm 4）。

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

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

让我们定义一个bool函数 $v(i_1,i_2)$ 来表示一个被第 $i_1$ 行和第 $i_2$ 行包围的有效矩形是否存在。显然，由于G的非负性，该函数满足公式(6):
$v(i,j) = 0 \Rightarrow \forall i^*,j^* \in[i,j] ,v(i^*,j^*)=0.....................(6)$
假设在执行的某个阶段，我们有 $v(i_1,i_2) = 1$，如图7(a)所示。根据算法， $i_1$ 将被移动到第很前面的位置，使得 $v(i_1',i_2)=0$, 如图7(b)所示。注意，这也意味着 $v(i_1'-1,i_2) = 1$。最后 $i_2$被移动到很靠前的位置，使得 $v(i_1',i_2')=1$,意味着 $v(i_1',i_2'-1)=0$

为了确保完整性，我们应该检查当 $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$的自动选择

根据我们的定义， $\tau$ 是被保留的注意力的百分比。通常情况下，可根据经验或用户要求来选择这个值。由于所提出的算法复杂度较低，我们甚至可以允许用户实时改变这个值。然而，研究自动选择的可能性仍然是有趣的。考虑到在问题1中， $对于\forall \tau[0,1]，\ddot R(\tau)总是存在，$使分析具有简洁性，我们只针对问题1研究这一问题。

考虑到图像裁剪的性质， $\tau$ 的选择在很大程度上依赖于 $||\ddot R(\tau)||$函数的数学性质。很明显地， $||\ddot R(\tau)||$函数是一个复杂的函数，在不同的注意图中有着不同的表现。理想情况下，对于一个所有像素都同等重要的统一注意力地图，我们有 $||\ddot R(\tau)|| = \tau$。对于正价值注意力地图，有 $||\ddot R(0)|| = 0$和 $||\ddot R(1)|| = 1$。

在现实生活中的图像中，具有高度注意力值的像素通常是空间集中的，这就导致了一个现象，如图9第三行所示，通常对于小的 $\tau$ ， $||\ddot R(\tau)||$值增长缓慢，对于大的 $\tau$， $||\ddot R(\tau)||$值增长迅速。对于不同的图像，函数曲线可能会有显著差异。然而，通过在图9第四行所示的对数坐标中绘制它们，可以观察到 $log(||\ddot R(\tau)||)$和 $log(\tau)$之间的强线性相关。

为了进一步验证这一观察结果，我们计算了1000张随机选择的Microsoft COCO 图片中的的 $log(||\ddot R(\tau)||)$和 $log(\tau)$之间的Pearson相关系数，相关系数的均值和标准差分别为0.995和0.004，说明该对数线性假设具有较强的统计有效性。

因此，我们提出了一个简单的幂函数模型：
$||\ddot R(\tau)|| = \tau^{\gamma},(\gamma\geq 1)$
其中 $\gamma$ 实际上可以用来测量意向图的浓度。更大的 $\gamma$ 通常表示较高的视觉注意力集中程度，如图9(b)所示。对于给定的图像，可以通过线性拟合 $log(||\ddot R(\tau)||)$和 $log(\tau)$之间的关系，来估计 $\gamma$ 的大小。

在实际应用中，我们选取了 $\tau$的10个抽样点进行拟合。在此基础上，可以很容易地确定不同的目标，以选择最优的 $\tau$。举例来说，我们在(7)中提出一个简单的目标函数，其基本原理是在注意力保持和区域裁剪之间达到平衡。公式（7）：
$\tau^* = {argmax}_{\tau} \tau(1-||\ddot R(\tau)||) = argmax_{\tau}(\tau-\tau^{1+\gamma})..........(7)$
解析求解(7)可得：
$\tau^* = (1+\gamma)^{-1/\gamma}$
关于argmax的解释（百度）：

解析求解公式（7）的过程（其实就是求取得极大值时的自变量）
问题：
$f(\tau) = \tau -\tau^{1+\gamma},求\tau取什么值时，f(\tau)取得最大值$
解：
$f'(\tau) = 1-(1+\gamma)\tau^{\gamma}$

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

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

当 $\tau<(1+\gamma)^{-1/\gamma}时，f'(\tau)>0,f(\tau)随着\tau的增大而增大，$
当 $\tau\geq(1+\gamma)^{-1/\gamma}时，f'(\tau)\leq0,f(\tau)随着\tau的增大而减小，$

故，当 $\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]中选择的。图10和图11为问题1中定义的最小面积裁剪结果。图10说明了 $\tau$的影响。可以看出，剪切矩形的大小和位置都随着 $\tau$的变化 而变化。图11演示了自动选择 $\tau$ 的有效性。

图12显示了高宽比变化时问题2的可视化结果。相当令人惊讶的是，裁剪矩形与不同的长宽比看起来都是合理的。图13是多个矩形的裁剪结果。[10]中提出的注意模型故意强调图像中心附近的视觉重要性，导致图13中红色矩形显示的结果不理想。

我们还在1000张随机选择的图像上，比较了算法2和算法4与相应的暴力穷举算法的平均运行时间。实验在3.6GHz CPU, 16GB内存的桌面PC上进行，使用Matlab实现。在图14中，加速度比与 $\tau$ 对应。所有注意图均[8]中的方法生成，并且 $m = 188,n = 250$ 。算法2中计算所有 $\tau$值所需的平均运行时间为137.8ms，算法4中为4.2ms。

5.结论

我们研究了基于注意力的图像裁剪中最优矩形搜索的计算复杂度。根据不同的应用需求和图像特性，提出了三个问题公式，并设计了计算复杂度较低的算法。我们还提出了一种基于注意力保持和区域裁剪关系的全自动图像裁剪方法。实验结果证明了我们的方案的有效性和效率。

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

• 视觉满意与裁剪价值的选择之间的关系;
• 融合不同注意力图的可能性。
• 将这一研究扩展到以美学为导向的图像裁剪方法也是很有趣的。

该项目由清华大学自主科研计划(20131089382)、北京市高等教育青年精英教师项目(YETP0104)、国家自然科学基金(61101152)资助。