邹盼盼， 陆　平， 朱恒亮， 董振江，贾　霞， 林　晓,4， 马利庄

(1. 上海交通大学电子信息与电气工程学院数字媒体与数据重建实验室，上海 200240；2. 东南大学信息科学与工程学院，江苏 南京 210000；3. 中兴通讯股份有限公司云计算及IT研究院，江苏 南京210000) 4. 洛阳师范学院信息技术学院，河南 洛阳 471022)

基于主体区域保持的图像缩放算法

邹盼盼1， 陆平2,3， 朱恒亮1， 董振江3，贾霞3， 林晓1,4， 马利庄1

(1. 上海交通大学电子信息与电气工程学院数字媒体与数据重建实验室，上海 200240；2. 东南大学信息科学与工程学院，江苏 南京 210000；3. 中兴通讯股份有限公司云计算及IT研究院，江苏 南京210000) 4. 洛阳师范学院信息技术学院，河南 洛阳 471022)

基于插值运算的缩放算法和经典的缝裁剪算法是两种常用的图像缩放算法，传统的缩放算法在缩放比例不一致的情况下其效果不佳，而缝裁剪算法在主体区域较大或者图像背景较为复杂时对图像的主体区域会造成一定破坏。针对以上问题，提出了一种基于主体区域保持的图像缩放算法，使用高斯差分对图像进行角点检测，利用角点产生凸包，根据凸包对图像进行主体区域检测，计算能量图并对位于主体区域像素点的能量给予相应的权重，根据权重的不同对主体区域进行不同程度的保护。实验结果表明，该算法能更好地保持图像主体区域。

缝裁剪；主体区域；角点检测；图像缩放；凸包

目前，随着电子产品更新换代的速度越来越快，特别是智能手机等移动设备的出现，加速了信息的传递。在信息传递中，图像信息尤为重要，为此就需要在不同的显示设备上显示图像。由于不同的显示设备有不同的长宽比，因此如果要在不同的显示设备上显示同一幅图像，就需要对图像进行相应的缩放处理。为此，研究人员从不同的方面提出了不同的方法[1-2]。

传统的图像缩放算法是基于差值核函数的缩放算法，其通过对图像使用最近邻插值、双线性插值或双三次插值等技术来改变图像大小[3-4]，该算法对于长宽比相同的图像缩放时效果很好，但是如果目标图像与原图像的长宽比不一致，则会使图像中的主体区域产生拉伸或压扁，从而导致图像产生畸变，影响图像的视觉效果。对比图1(a)和图1(b)可看出，传统的缩放算法影响了图像的视觉效果。

由于传统的缩放算法不能很好保持图像主体区域的视觉效果，为了解决此问题，研究者们提出了许多方法，其中比较有影响力的是 Avidan和Shamir[5]在2007的SiggGraph会议上提出的缝裁剪(seam carving)算法。如图1(c)所示，缝裁剪算法相对于传统的缩放算法可以更好地保持图像的主体区域，但是这种方法在图像中的主体区域比较大或主体区域的颜色与环境的颜色对比不明显时，会产生让人不满意的效果。图2中缝裁剪算法裁剪了方框中小男孩的脚，图3缝裁剪算法对方框中船体和桅杆进行了裁剪。从图2和图3可看出缝裁剪算法影响了图像主体区域的视觉效果。

因为缝裁剪算法可以比较好地保持图像的主体区域，所以其适用范围很广，又因为缝裁剪算法存在一些不足，研究者们提出了不同改进的算法。Yan等[6]提出了基于区域匹配的缝裁剪算法并将该算法用于视频缩放；Yue等[7]改进了缝裁剪算法，使得缝裁剪算法可以用于立体图像的缩放；Frankovich和 Wong[8]提出了通过集成能量梯度函数来改进缝裁剪算法。

Dong等[9]提出了一种将缝裁剪算法和传统的缩放算法结合起来对图像进行缩放的方法，该算法可以有效地利用缝裁剪算法和传统缩放算法的优点。Luo等[10]提出了将直接和间接的缝裁剪算法结合起来的自动图像缩放算法，使得图像在缩放过程中可以自动地选择使用缩放方法，在不需要人为干预的情况下达到理想的缩放效果。

基于上述内容的分析，本文提出了一种新的基于主体区域保持的图像缩放算法，该算法可以在图像的主体区域比较大或主体区域与背景颜色对比不明显的情况下得到较好的效果。

图1　传统缩放算法和缝裁剪算法的比较

图2　线裁剪算法的缩放效果1

图3　线裁剪算法的缩放效果2

1　相关工作

1.1缝裁剪算法

缝裁剪算法通过插入或者删除缝对图像进行缩放，其核心是每次找到一条能量最小的垂直缝，通过删除该缝使图像缩小一个像素，或者通过添加一条缝使图像放大一个像素。如果要在水平方向进行缩放，则在水平方向上找一条能量最小的缝，然后对该缝进行相应的操作；如果要在垂直方向进行缩放，则在垂直方向上找到一条能量最小的缝，然后对该缝进行相应的操作。

因为在缝裁剪算法中需要保护图像中视觉重要信息，而重要区域中像素的颜色值变化比较大，所以Avidan和Shamir[5]将像素能量定义为：

通过x和y方向梯度值的绝对值之和表示该点的能量。图像I的垂直裁剪缝的定义为：

其中，x是一个映射x:[1,…, n]→[1,…,m]，即一条垂直的裁剪缝是一条从上到下能量最小的像素组成的8连通路径。类似的，图像I的水平裁剪缝定义为：

对于给定的能量函数e，定义一条裁剪缝代价为：

要找一条代价最小的裁剪缝，定义s*为代价最小的裁剪缝，则：

对图像I用动态规划算法求解代价最小的一条裁剪缝。以垂直裁剪缝为例，求解步骤如下：

(1) 利用式(1)计算每个(i, j)点处的能量，得到梯度矩阵MG。

(2) 从 MG第二行的第一个像素点开始从左到右，从上到下计算图像中每点的能量值，直到计算出所有点的能量值。图像中(i, j)处的像素点的能量表示为M(i, j)，则：其中，e(i, j)是式(1)得到像素点(i, j)的梯度值，遍历完整幅图像之后得到图像的能量矩阵ME。

(3) 根据得到的能量矩阵ME，在最后一行找到能量值最小的像素点，然后从该像素点向上回溯并记录回溯经过的每个像素点，直到回溯到第一行。其记录下来的像素点组成的一条缝就是代价最小的一条裁剪缝s*。

(4) 如果要将图像缩小，则删除s*即可；如果要放大图像，则复制s*得到，然后将插入s*旁边即可。

1.2角点检测与高斯差分

角点作为表征图像局部特征的一个重要因素，其集中体现了图像的很多重要形状信息。角点不仅具有旋转不变性，而且也几乎不受光照条件的影响。在图像的数据信息没有被破坏的情况下，角点是图像最小化处理的数据量。由于角点具有以上的性质，所以角点检测具有很强的实用性，近年来也得到了越来越多的研究者重视。

关于如何定义角点目前还没有达成共识，但是研究者一般认为：角点是图像当中梯度变化最大的点。为了检测图像的角点，研究者们提出了许多方法。Song等[11]认为图像中的噪声严重的影响了角点检测的性能且噪声很难消除，针对这个问题提出了一种基于噪声差异级别的角点检测方法，该算法可以根据图像的信噪比自适应的设定阈值以过滤假的角点；Ramakrishnan等[12]认为广泛使用的ShiTomasi和Harris角点检测方法需要手动的设定参数阈值，为此提出了一种基于迭代剪枝的策略改进了ShiTomasi和Harris的角点检测算法；何中翔等[13]改进了一种基于Harris角点检测算法的亚像素级角点检测算法。而本文采用的角点检测算法是基于高斯差分(difference of Gaussian, DOG)的。

对于二维图像I(x,y)，其尺度空间L( x, y,σ)，由该图像与高斯核G( x, y,σ)卷积得到：

其中，高斯核中的方差σ是尺度因子，决定着图像被平滑的程度，连续改变σ就能构造图像的高斯金字塔。DOG空间D( x, y,σ) 是高斯金字塔中相邻尺度空间函数之差，即：其中，k表示相邻尺度空间的尺度比例系数。不同的k值可以得到不同的DOG空间，所有的DOG空间就构成了DOG金字塔，然后检测金字塔中间层(最高层和最底层除外)中每个像素点，如果一个像素点比相邻的像素点的值都大或者都小，那么该点就是一个局部极值点，则将该点作为候选特征点，也就是角点。本文算法综合考虑了算法的效果和时间复杂性，决定取3个不同的k值，这样可以取得较好的效果和较快的速度。

2　图像主体区域检测

常用的图像主体区域检测算法主要是基于图像的显著性，一般认为图像的显著性图显示的区域即为图像的主体区域[14]，但目前常用的求显著性的算法计算量都比较大。另外一种求图像主体区域的算法是基于角点检测和凸包算法，由于图像的角点很少，所以该算法处理速度很快。

角点可以表现图像的局部特征，并且具有旋转不变性，几乎不受环境光照的影响，而且角点的数量一般比较少，处理速度相对较快，所以可通过角点构成的区域来表示图像的主体区域。

由于图像中角点比较少，所以本文决定采用Graham扫描算法[15]来求角点的凸包。Graham扫描算法首先需找到最小y轴坐标点，然后按照其他点和该点的连线与x轴的夹角角度值排序，通过判断相邻顶点的空间位置关系，从而得到逆时针排序的凸包顶点，其时间复杂度为n log2(n)，n表示顶点的数量。由于原始的Graham扫描算法在点集比较密集时效率会受到影响，吴文周等[16]对原始的Graham扫描算法进行了改进。具体的改进算法过程请参考文献[16]。

3　本文算法

3.1算法目的

本文提出了一种新的基于主体区域保持的图像缩放算法，具有比较快的速度，且比缝裁剪算法和传统的缩放算法能够更好地保持图像的主体区域。在图像中的主体区域较大或主体区域与背景的对比度不明显的情况下，也可以取得较好的效果。

3.2算法的步骤

本文算法使用DOG对图像进行角点检测，对角点使用凸包算法找出图像中的主体区域，再利用式(1)计算出图像的能量图，对能量图中位于主体区域的点进行加权处理，得到新的能量图，然后在新的能量图上使用缝裁剪算法对图像进行缩放。

算法主要分以下5步：

(1) 求出图像的 DOG图。在等式(9)中选择 3个不同的尺度比例系数，如图4所示，本文中选用的k值分别为0.750、0.857和0.875，得到3张不同的DOG图。

(2) 根据步骤(1)中得到的3张DOG图，找出中间的DOG图中每一个像素是否为极值点。判断像素点是否为极值点的方法：如图 5(a)、(b)和(c)分别表示DOG空间的第1、2和3层，其中图5(b)为中间层。要判断其中间的(i, j)是否为极值点，则将中间点与其他的 26个黑色的点比较，如果中间点的值是这27个点中最大的或最小的，则(i, j)为极值点，由这些极值点组成的图为原图的角点图。图6(b)为图6(a)的角点图。

(3) 使用Graham扫描算法求角点图的凸包，得到的凸包区域即为图像的主体区域。图6(c)所示即为由图6(b)的角点求得的凸包图。

(4) 利用式(10)求图像的初始梯度值图Einit，再对位于凸包内的像素点赋予权重，得到新的权重梯度值图Enew，本文算法的梯度值图Eours为初始梯度值图Einit和新的权重梯度图Enew的叠加。计算公式如下：

其中，式(10)中e(i,j)是根据式(1)得到的(i,j)处的梯度值，Einit(i, j)表示(i,j)处初始的梯度值；式(11) 中 w表示权重系数，I表示图像，H表示凸包；式(12)中Eours(i, j)表示本文算法得到的梯度值图。不同的权重将会对主体区域进行不同程度的保护。例如图7(b)中为初始梯度值图Einit，图7(c)为新的权重梯度图Eours。根据图像的不同选择最适合的权重，对主体区域不足和过度保护都会对缩放后的图像造成不良影响。

(5) 在本文算法得到的梯度值图Eours上使用动态规划算法得到新的能量图Mours，在Mours上使用缝裁剪算法对图像进行缩放。

图4　3种不同比例系数的高斯差分图

图5　判断极值点示意图

图6　本文算法得到的角点图、凸包图

图7　本文算法的初始梯度值和加权后的梯度值

4　实验结果

本文实验硬件平台为一台2.40 GHz, 4 GB内存的计算机，软件平台为MATLAB R2013a。本文将从主体区域的保持程度、本文算法与常用缩放算法的对比和本文算法的特点3个方面进行实验。

4.1主体区域保持

由于本文算法对图像的主体区域进行了加权保护，通过对位于主体区域和非主体区域的像素点给予不同的权重可实现不同程度的保护。相对于缝裁剪算法，本文算法在裁剪过程中可以更好地保持图像的主体区域。

图7(b)是本文算法得到的初始能量图，图7(c)是本文算法得到加权后的权重能量图，图7将式(11)中的权重值w设为5。通过对比2种算法得到的能量图，可以看到因本文算法对图像的主体区域进行了加权，所以得到的能量图更加突出图像的主体区域，可以更好地保持图像的主体区域。

缝裁剪算法将图像压缩到一定程度的时候，由于背景区域被反复裁剪从而形成了折横，导致背景区域的能量变大，使得裁剪缝可能穿过图像的主体区域，从而损坏了图像的主体区域。图8(a)、(c)中采用的缝裁剪算法得到的裁剪缝均通过图像的主体区域，采用本文算法得到图8(b)、(d)的裁剪缝则避开了图像的主体区域。由此可看出本文算法可以更好地保持图像的主体区域。

4.2常用的缩放算法的比较

从图 9的实验结果看出本文算法可以更好地保持图像的主体区域，而且在尽可能的保证主体区域内容完整性的情况下，取得了比较好的视觉效果。由于传统的缩放算法在非等比例缩放的情况下会对图像中的内容进行压扁或者拉伸，所以影响缩放后图像的视觉效果。缝裁剪算法可以保持图像的主体区域，但是在某些情况下，特别是主体区域较大或者主体区域与背景对比度不明显时，容易对主体区域造成破坏。比如图9中海豚的尾巴、车窗的顶部、船上的桅杆和汽车左边缘都被裁剪了，可见缝裁剪算法均没有取得比较理想的效果，而本文算法则相对较好保持图像的主体区域，取得了比较好的效果。

图8　缝裁剪算法与本文算法在保持图像主体区域的比较

图9　传统的缩放算法、缝裁剪算法和本文算法的比较

4.3本文算法的特点

由于在图像缩放过程中每行或每列需要裁剪掉的像素数量是一定的，因此如果对图像的主体区域进行了加权保护，就会对背景区域过多裁剪。从一方面来说这可以更好地保持图像的主体区域；从另一方面来说本文算法相对于缝裁剪算法对背景区域的裁剪更多。如图9中的第二排图片所示，由于本文方法对车所在的区域进行了加权保护，所以车保存的比较完整，但是图片右上角的公路却比缝裁剪算法变形严重。因此对于主体区域的保护程度的取舍很重要，式(11)中不同的w值，会对主体区域进行不同程度的加权，从而对主体区域进行不同程度的保护。w值越大对主体区域的保护越强，更倾向于裁剪背景区域；反之，w值越小对主体区域的保护越小。

5　结论与展望

本文提出了一种新的基于主体区域保持的图像缩放算法，通过对图像使用DOG进行角点检测，然后利用角点通过Graham算法求凸包，凸包所在的区域即为图像的主体区域；在计算图像能量图时先计算初始的能量图，再对位于凸包内的像素点的能量加权得到新的加权能量图，然后将初始能量图和加权能量图叠加得到新的能量图，最后在新的能量图上采用缝裁剪算法对图像进行缩放。实验结果表明，本文对图像的主体区域进行了加权保护，可以更好地保持图像的主体区域。

本文算法也存在一定的局限性，如果图像中存在多个主体，根据角点检测得到的凸包必然会包含所有的主体区域，在某些情况下会将大量的非主体区域包含进来，从而保护了图像中的非主体区域，这将破坏图像缩放后的几何结构。如果图像的主体背景较复杂，则本文算法也会遇到与显著性算法相同的问题：无法准确有效地检测出图像的主体区域，从而无法为主体区域提供准确有效地保护，进而导致缩放效果不佳。

本文算法在给主体区域和非主体区域所使用的权重是手动指定的，根据图片缩放要求的不同需要指定不同的权重来达到最好的缩放效果。这显然不能满足处理批量图片的要求，为了处理批量图片需要根据图片的不同自适应的指定权重，如何自适应指定权重是今后研究的重点。

[1] 施美玲, 徐丹, 内容感知图像缩放技术综述[J]. 中国图象图形学报, 2012, 17(2): 157-168.

[2] 施美玲, 徐丹, 钱志明. 基于成对比较的内容感知图像缩放效果主观评估[J]. 计算机辅助设计与图形学学报, 2013, 25(10): 1503-1513.

[3] 杨云峰, 苏志勋, 胡金燕. 一种保持边缘特征的图像插值方法[J]. 中国图象图形学报, 2005, 10(10): 1248-1251.

[4] van Ouwerkerk J D. Image super-resolution survey [J]. Image and Vision Computing, 2006, 24(10): 1039-1052.

[5] Avidan S, Shamir A. Seam carving for content-aware image resizing [J]. ACM Transactions on Graphics, 2007, 26(3): 10: 1-9.

[6] Yan B, Sun Kairan, Liu L. Match-area-based seam carving for video retargeting [J]. IEEE Transactions on Circuits and Systems for Video Technology, 2013, 23(2): 302-310.

[7] Yue B, Hou C P, Zhou Y. Improved seam carving for stereo image resizing [J]. EURASIP Journal on Wireless Communications and Networking, 2013, 2013(1): 1-6.

[8] Frankovich M, Wong A. Enhanced seam carving via integration of energy gradient functionals [J]. IEEE Signal Processing Letters, 2011, 18(6): 375-378.

[9] Dong W M, Zhou N, Paul J C, et al. Optimized image resizing using seam carving and scaling [J]. ACM Transactions on Graphics, 2009, 8(5): 125: 1-10.

[10] Luo S Q, Zhang J P, Zhang Q, et al. Multi-operator image retargeting with automatic integration of direct and indirect seam carving [J]. Image and Vision Computing, 2012, 30(9): 655-667.

[11] Song Y, Shen Y P, Li S X, et al. Corner detection in images under different noise levels [C]//Pattern Recognition (ICPR), 2014 22nd International Conference on. Stockholm, New York: IEEE Press, 2014: 906-911.

[12] Ramakrishnan N, Wu M Q, Lam S K, et al. Automated thresholding for low-complexity corner detection [C]// Adaptive Hardware and Systems (AHS). New York: IEEE Press, 2014: 97-103.

[13] 何中翔, 王明富, 杨世洪, 等. 遥感图像客观质量评价方法研究[J]. 图学学报, 2011, 32(6): 47-52.

[14] Fang Y M, Chen Z Z, Lin W S, et al. Saliency detection in the compressed domain for adaptive image retargeting [J]. IEEE Transactions on Image Processing (TIP), 2012, 21(9): 3888-3901.

[15] Graham R L. An efficient algorithm for determine the convex hull of a finite planar set [J]. Information Processing Letters, 1972, 1(4): 132-133.

[16] 吴文周, 李利番, 王结臣. 平面点集凸包Graham算法的改进[J]. 测绘科学, 2010, 35(6): 123-125.

An Novel Image Resizing Method Based on Im portant Area Maintain

Zou Panpan1,Lu Ping2,3,Zhu Hengliang1,Dong Zhenjiang3,Jia Xia3,Lin Xiao1,4,Ma Lizhuang1

(1. School of Electronic Information and Electrical Engineering, Shanghai Jiao Tong University, Shanghai 200240, China; 2. School of Information Science and Engineering, Southeast University, Nanjing Jiangsu 210000, China; 3. Cloud Computing and IT Institute of ZTE Corporation, Nanjing Jiangsu 210000, China; 4. Academy of Information Technology, Luoyang Normal University, Luoyang Henan 471022, China)

Scaling and seam carving are commonly used algorithm in image resizing, but scaling is not suitable for the case that the resize ratio is not uniformity, seam carving will also has a bad effect on important area in some cases. In this paper we proposed a novel algorithm which is based on important region maintain. Firstly, we make a corner detection based on difference of Gaussian, then Graham-scan algorithm is applied to do an important region detection, after that we will add different weights between important region and unimportant region. The experimental result shows our method is better than other image resizing algorithms in maintaining the important area.

seam carving; important area; corner detection; image resizing; convex hull

TP 391.41

10.11996/JG.j.2095-302X.2016020230

A

2095-302X(2016)02-0230-07

2015-09-24；定稿日期：2015-10-01

国家自然科学基金项目(U1304616, 61133009, 61502220)；国家“973”重点基础研究发展规划项目(2011CB302200)

邹盼盼(1989–)，男，湖北黄冈人，硕士研究生。主要研究方向为图像视频处理。E-mail：zou_pp@163.com

马利庄(1963–)，男，浙江余姚人，教授，博士，博士生导师。主要研究方向为计算机图形学、数字媒体等。E-mail：ma-lz@cs.sjtu.edu.cn