一种改进的Seam Carving图像放大算法

陈小娥

(福建船政交通职业学院信息工程系，福建福州350007)

一种改进的Seam Carving图像放大算法

陈小娥

(福建船政交通职业学院信息工程系，福建福州350007)

针对基于Seam Caring的放大算法可能误判图像重要区域而造成线路错误提取的问题,提出一种增加人工干预来保护图像重要区域的方法，该方法可以有效减少裁剪线路经过视觉关注重要区域，从而避免重要对象发生扭曲变形。实验结果表明，改进的算法能得到更优的放大效果。

计算机图像处理；Seam Carving；图像放大；人工干预；自适应算法

随着科技进步，出现了各式各样的多媒体显示设备，如笔记本电脑、高清电视、移动电话和平板电脑等，它们具有不同的分辨率和纵横显示比例。如何在这些显示设备上自适应地显示给定分辨率的图像，即图像的自适应缩放问题，就成为人们关注的图像处理问题之一。

1 研究背景及现状

图像缩放算法的本质是图像分辨率的改变。早期的缩放算法通常采用简单插值算法、统一缩放算法和直接裁剪算法等。但是，由于显示设备纵横比例和原始图像尺寸不同，统一缩放算法和简单插值算法容易使图像的重要对象经过缩放后产生较大的扭曲变形，而裁剪技术则有裁剪掉图像中重要内容的风险，使缩放后的图像丢失重要信息。同时，传统的图像线性插值放大算法，如最近邻插值等对提高图像的分辨率能力有限，会出现边缘细节模糊等问题。尽管Kim等[1]提出了一种基于偏微分方程的曲率插值算法，该算法能够减少先前一般放大方法的锯齿波效应和边缘模糊等缺点，但仍无法很好地解决原始图像和显示设备纵横比不一样的情况下的放大问题。

Avidan等[2]提出一种基于Seam Carving的算法,该算法用图像像素点的能量值来表示图像中对象的重要程度，根据动态规划寻找累积能量值最小的像素带，通过不断删除或增加这些能量最小像素带来实现图像缩放。近年来该算法已成为研究基于内容感知的图像缩放的主流算法，很多学者对其进行了研究[3-7]。如文献[4]通过重新定义显著能量、优化查找方法以及结合双线性插值限制抽取像素带数目等方法来避免图像的重要内容产生扭曲和过度抽取；文献[5]结合可计算美学和内容感知图像缩放，设计一种新的图像缩放算法，既保留了图像的重要内容，同时也具有一定美感。其中，对于基于内容感知的图像放大算法，其难点在于，一方面是如果像素带插入的位置不当易导致图像出现“裂痕”,另一方面是可能误判图像重要区域而造成线路错误提取。如文献[8]针对插入像素带可能出现共用点的情况，提出了计算共用率等策略解决“裂痕”问题；文献[9]为解决误判问题，提出一种基于显著性区域求解图像能量函数的SDRS方法，但该方法较依赖于图像显著性检测的准确度。本文在Seam Carving算法的基础上，针对算法中可能误判图像重要区域而造成错误提取非视觉关注区域线路的问题，提出一种改进思路，即通过增加人工干预来修改图像中重要区域的像素能量值来达到保护该区域的目的，从而使放大后的图像重要对象不产生变形，由此得到更优的放大效果。

2 Seam Carving算法思想

Seam Carving算法的主要思路是在图像缩放过程中每次按一定的规律删除或者插入图像中的一条像素带。删除或插入的像素带应该是图像中相对不重要的部分，由此才能保持图像原有的特征。因此，需要提出一种标准来衡量像素带的重要性,Avidan等提出用能量函数来定义像素点的重要性,本文用图像梯度的一阶范数作为能量函数，具体公式如下:

设原始图像I的大小为n×m,其中n为列数,m为行数，则增加或删除的垂直像素带Cv可以表示为

其中x(i)是映射:x:[1,…,m]→[1,…,n]。类似地,水平像素带Ch可以表示为

其中,y(j)是映射:y:[1,…,n]→[1,…,m]。

如果记像素带C的能量值为E(C),则垂直像素带的能量最小值可以表示为

其中e(I(ci))为像素点Ci处的能量。

累积能量值最小的像素带采用动态规划算法求得。对于某像素点(i,j),其累积能量值记为M(i,j),则有

M(i,j)=e(i,j)+min(M(i-1,j-1),M(i,j-1),M(i+1,j-1))

具体方法是从图像的第二行到最后一行进行遍历，然后按照上述公式计算每个点的累积能量值。最后一行累积能量值最小的像素点的位置就是所求像素带的终点位置。最后，从该最小值点进行回溯，即可以找到能量值最小的像素带。

3 Seam Carving算法的改进

本文主要针对基于Seam Carving算法(简称“SC算法”)的图像放大算法进行改进。SC算法中，图像放大的方法是挑选能量值最小的像素带并插入。SC算法主要通过能量函数来定义像素点的重要性,对于某些图片的放大效果并不理想，可能会出现重要对象或者区域错误判断的情况。

为了得到更符合人类视觉机制的放大效果，本文提出改进的Seam Carving算法，通过人工干预选择视觉关注重点区域。具体方法是，用户通过鼠标选择视觉关注区域，并将该区域像素点的能量值人为地设置为最大值。由于SC算法提取的是能量值最低的像素带，因此人工选择的主体区域就避免了被提取和处理，从而避免了主体对象扭曲变形，达到保护图像重要信息的目的。

改进算法的具体思路如图1所示。图中每个方格代表一个像素，方格中左上角的数字代表该像素点本身的能量值，右下角的数字代表到当前像素点的累积能量值。图1(a)为源图像的像素点能量值示意图；图1(b)显示了经人工干预后的像素点能量值，即人工选取三个像素点(第2行第3、4、5列)作为重要区域的像素点，其能量值在原有像素值的基础上加上一个设定的最大值，图中最大值设置为500。图1(c)和图1(d)分别显示了原SC算法和本文提出的改进算法的动态规划求解过程，箭头方向表示像素点能量值累积的方向，其中圆角箭头所指向的方向表示累积得到最小能量值的方向，最后一行即为求得的最终累积能量值。图1(e)和图1(f)分别为原SC算法和本文算法通过动态规划求得累积能量最小值后，再经过回溯得出的最小能量值像素带，图中用灰色底纹粗线条代表求得的路线。由此可见，本文的改进算法避免了提取的线路经过图像中的重要区域。

(a)源图像像素点能量值

(b)人工选取重要区域

(c)原SC算法动态规划过程

(d)改进算法动态规划过程

(e)原SC算法选取的路线

(f)改进算法选取的路线

计算出累积能量值最小的像素带后，根据放大的尺寸，一次性选取好位置插入该像素带。插入的像素带各点的颜色值设置可以有多种方法，如可以直接复制该像素带的颜色值，也可以是该像素带的左右相邻(垂直方向)或者上下相邻(水平方向)的像素点颜色值的平均值。

4 算法实现及实验分析

本文实现了增加人工干预的Seam Carving改进放大算法，并进行实验测试。如图2所示，其中图2(a)为原始图像，图像尺寸为300像素×200像素；图2(c)为SC算法放大后的效果图，图像尺寸为350像素×200像素，即水平加宽50像素，由图可以看出图片右下角人物发生了变形，因为人物身体内部区域所在的像素梯度一阶范数能量值在此图中刚好比较小，如图2(b)所示。图2(d)是人工干预选择的区域，用画笔画出图像中视觉关注区域，图像中人物部分由画笔颜色覆盖。图2(e)图是用改进的人工干预算法放大的效果图，可以看出明显保护了图片中视觉重要区域不被破坏。实验结果表明，改进后的算法能得到更好的图片放大效果。

(a)原始图像

(b)梯度一阶范数能量值

(c)原SC放大算法

(d)人工选择区域

(e)本文算法

5 结语

本文实现了基于Seam Carving的图像放大算法并对其进行了改进，增加了人工干预，避免了原算法可能误判视觉重要区域而造成错误线路的提取，从而得到较为符合人类视觉关注机制的放大效果。与传统的放大算法以及原SC算法相比，改进的算法均取得了更好的效果。在今后的工作中，可进一步改进能量函数的计算方法，设计可自主计算避免错判区域的放大方法，解决人工干预的应用受到限制的问题，进一步扩大算法应用范围。

[1]KIM H,CHA Y,KIM S.Curvature interpolation method for image zooming[J].IEEE transactions on image processing,2011,20(7):1895-1903.

[2]AVIDAN S,SHAMIR A.Seam carving for content-aware image resizing[C]//ACM Transactions on Graphics (TOG).ACM,2007,26(3):10.

[3]张梓卷,康宝生.基于网格线平移的图像显示适配算法[J].计算机应用,2015,35(2):481-485.

[4]王金庭,杨敏,吴巍.一种改进的 Seam Carving 图像缩放算法[J].红外技术,2014,36(12):986-991.

[5]朱鹭伟,陈昭炯.结合美学原则的内容感知图像缩放算法[J].计算机工程与应用,2017(4):189-194.

[6]赵伟伟,张俊华,王逍,等.改进能量函数的 Seam carving 图像缩放方法[J].云南大学学报:自然科学版,2014,36(2):181-186.

[7]CHOI J,KIM C.Sparse Seam-Carving for structure preserving image retargeting[J].Journal of Signal Processing Systems 2016,85(2):275-283.

[8]陈小娥,陈昭炯.基于 Seam Carving 的图像放大算法研究与改进[J].计算机系统应用,2016 (6):254-259.

[9]王玺,夏清国,窦召虎,等.Seam Carving 和显著性分析的图像缩放方法研究[J].计算机工程与应用,2011,47(30):168-171.

责任编辑：杨子立

AnImprovedofImageMagnifyingAlgorithmBasedonSeamCarving

CHENXiaoe

(Department of Information Engineering,Fujian Chuanzheng Communications College，Fuzhou 35007)

In view of the problem that the amplification algorithm of seam carving may misjudge important areas of images and result in wrong extraction routes,an algorithm is proposed to protect the important areas with manual intervention.The improved method can reduce the probability of paths going through the important areas of images to avoid distorting important objects.The experimental results show the improved algorithm can achieve a better magnifying effect.

computer image processing;seam carving;image magnification;manual intervention;adaptive algorithm

10.3969/j.issn.1671- 0436.2017.03.008

2017- 05-17

福建省教育厅中青年教师教育科研项目(JAT160704)

陈小娥(1984— )，女，硕士，讲师。

TP391

：A

：1671- 0436(2017)03- 0038- 03