一种基于条分割及缩放的图像重定算法

华 顺 刚， 苏 铁 明， 李 新 丰， 欧 宗 瑛

(大连理工大学 机械工程学院，辽宁 大连 116024)

0 引 言

显示设备的多样性和数字网络的发展，要求图像和视频能够在各种显示设备上，以不同的分辨率或纵横比显示，同时能够完整地保留重要的信息和显著内容.由于缺少对显著特征分布和图像内容的关注，传统的图像重定方法不能满足各种类型的显示设备的要求，比如标准Scaling和Cropping算法.其中Scaling算法有时会过分缩放图像，使重要部分产生变形；而Cropping算法则强调图像的主要部分，舍弃图像的边缘内容，可能会丢掉图像的某些重要信息.

近年来，很多学者致力于图像缩放的研究，提出了多种图像重定算法.其中，基于内容感知的算法是一种关注图像显著信息和全局视觉效果的有效方法.该类算法通过使用图像的显著图来实现图像的缩放，将不重要的内容移除，保留重要的信息和目标，以实现理想的缩放效果.到目前为止，人们侧重于图像的不同特征和方面包括图像的结构、特征、显著区域、重要信息及不重要信息等[1－7]，提出了多种基于内容感知的图像缩放算法.

Seam Carving算法[8]是一种经典的优秀图像缩放方法，通过移除和复制不重要区域的低能量接缝，有效地调整图像的大小.一个接缝是该图中自顶向下或从左到右的能量较低的八连通像素接缝.然而，如果图像被大幅度收缩，或不太重要的区域被基本去除，以及兴趣目标占满整幅图像时，重要目标及内容将产生扭曲变形，局部和全局结构可能被破坏.Rubinstein等[9]改进了Seam Carving算法以增强缩放效果并将其拓展到视频缩放领域.

Kim等[10]基于频域分析提出了一种自适应的图像和视频缩放算法.通过优化计算将图像划分为若干图像条，根据图像频域信息计算各图像条的缩减量并扩展至视频缩放领域，但是该方法有时会使图像中的某些条过度压缩而使整幅图像产生扭曲变形.Liang等[5]提出了一种分片的图像缩放算法，通过强调图像的重要区域来保护图像的全局效果.该方法结合图像边缘和显著度测量建立显著图，将原始图像分割成重要或不重要的图像块.该方法的不足在于:如果一个物体被分割到不同的小块，其边缘可能会产生错切效果.

Hua等[3]通过对原始图像和缩放图像间相似度(距离)测量的研究，提出了一个基于SIFT特征的图像缩放算法.由于这类算法需要迭代计算原始图像和重定图像的相似度[11－12]，非常耗时.

实验表明，仅由某种单一的算法很难对所有类型图像都获得满意的重定效果.Rubinstein等[6]提 出 了 一 种 将 Scaling、Cropping 和 Seam Carving算法进行组合优选的算法，但其寻找某一阶段最优算子的计算量很大.为提高计算效率，本文研究一种快速的基于内容感知的图像重定算法，通过结合Scaling和Cropping算法实现快速计算，以获得高质量的图像目标重定效果，并通过对RetargetMe图像基准库[13]的重定实验，表明本文算法的有效性.

1 图像分割

一幅图像由于包含了各种信息或目标，若图像内的同一个物体或目标能以协调一致的比例来缩放，则可以保持其整体视觉效果.将图像分割成若干区域时，若某一个物体被划分到不同的区域，那么不同部分将以不同的比例被缩放，可能使物体产生扭曲或变形.

对于水平方向尺寸缩放情况，本文首先计算每个像素列的能量和，再尽量将具有相似重要性的像素列分割到同一图像条内.在图像重定过程中，根据所获得的显著图来缩放各图像条.本文缩放策略是:图像条的缩减量与它的重要程度成反比，即能量值越大的图像条，重要程度越高，缩减比例越小；进而，将处于边缘的、缩减比例超过某一阈值的图像条删除，以保证某些内容不会被过度缩放而造成图像的扭曲和失真.

1.1 图像能量图

图像中，重要目标及显著区域因像素的颜色、梯度、亮度等特征较为突出，会存在较高的能量.通过计算基于特征的图像能量，可以构建一幅图像的能量图，从而感知图像重要信息的位置和程度.基于能量图通过优化迭代，可将图像划分成若干不同能量的图像条.

有多种计算能量图的方法，如梯度法、Harris－corners角点检测、人脸检测、图像熵函数及梯度直方图等算法[8].其中较经典的计算方法是梯度法.其2范数形式为

另外，Achanta等[14]定义的能量图注重检测图像中视觉效果明显的区域，该方法将图像色彩从RGB模型转换为Lab模型，利用色彩和亮度，通过一种调频方法计算图像的显著区域.文献[10]结合重要性图和由Itti等[15]提出并改进的显著图方法，用于图像和视频的缩放.Avidan等的研究工作表明，图像的梯度信息可以很好地用于图像重定工作中[8]，因此，本文使用式(1)来建立图像的能量图.图1为两幅由图像的梯度信息建立的能量图实例.

图1 原始图像及其梯度图Fig.1 Original images and their gradient maps

1.2 图像条分割

基于能量图可以将图像分割成若干图像条.这里只描述单一方向上的图像缩放情况，将输入图像I的宽、高从n×m调整到n′×m，这样b＝n－n′表示水平方向上的缩减量.首先根据式(1)计算每一像素的能量，并由式(2)累积各列像素的能量值进而生成能量图.图2所示为图1(a)(n×m＝500×333)中图像所对应的列累积梯度能量图.

首先将原始图像沿宽度方向均匀分割成N等份，即可得到N个图像条.根据列累积能量图由下式进行迭代计算，得到各图像条的最优宽度值:

式中:li表示图像条的左侧水平坐标，这里l1＝1，lN＋1＝n；ci－1和ci分别是对应于第(i－1)和第i个图像条的平均能量值，由计算得到；α为取值[0，1]的权重参数.

式(3)表明，对于每一图像条，最小化该条中的各列与其平均能量的差，同时最大化邻近图像条的平均能量差，以获得优化的坐标li，使某一图像条内各列尽可能具有相似的重要程度.α则表示最小类内、最大类间差值的分配权重.迭代过程中，使li－1和li＋1固定，通过从li－1到li＋1－1遍历取值，重复计算li直至得到优化值.如此，具有相似重要性的像素列被聚集到同一图像条中，即较高(或较低)能量的像素列被尽可能划分到一起.

图2 列累积能量图Fig.2 Column accumulated energy map

对于图像条数目N的选择，可以设置一个适当的值，如果取值偏小，图像的能量特征难以充分显现；反之，则会增加计算时间.大量实验表明，N的取值大小对图像的重定效果不会产生非常明显的影响.因此本文中N取为10.

首先将图像划分成N个图像条，得到各图像条的宽度为n／N.由式(3)计算第(i－1)个图像条的宽度wi－1＝li－li－1.表1列出了图1(a)对应的图像条宽度和缩减量数据.通过优化迭代，各图像条的计算宽度wi见表中第2列数据.其中第2和第8图像条分别具有最小宽度6和最大宽度97.第3列为平均能量值ci，第1图像条具有最低平均能量值14.73，说明该图像条最不重要.第4列和第5列是各图像条的缩减量，将在下一节加以描述.

表1 分割图1(a)生成的图像条宽度及其缩减量Tab.1 Strip width and reduced amount associated with Fig.1(a)

2 图像条的缩减量计算

图像分割后即可进行各图像条的缩减量计算.一个高能量的图像条，很可能包含重要的信息和目标，应尽可能少地缩减其宽度以保持图像条内的重要信息；反之，应将低能量的图像条尽可能大地缩放以实现图像重定的需要.基于上述策略，定义如下公式计算图像条的缩减量:

式中:b表示一幅图像的全部缩减量；b′i为第i图像条的缩减量，应正比于图像条宽wi，反比于其平均能量ci；对于原始图像(图1(a))在水平方向缩减一半的情况，由式(4)计算得到的各图像条的缩减量见表1第4列.可见图像条1原分割宽度为95，因平均能量最低，计算缩减量为66，有最大的缩放比例0.695(66／95)；图像条6有最大的平均能量32.88，其缩放比例最小，为0.317(19／60).

通过缩减各图像条的宽度，可以得到缩放的目标图像.如图3所示，房屋(图3(a))和汽车(图3(c))均是图像中的重要物体.由于包含房屋和汽车的图像条具有高能量，其缩减量较小；而包含背景等不重要区域的图像条的缩减量则较大.然而，从图3(d)中可以看到，图像左侧边缘部分被过分地压缩，使这部分图像内容产生了错切变形.鉴于此，下面将引入裁剪来避免此类由于区域过度缩减而使图像产生扭曲和失真的情况.

图3 水平方向的图像缩放Fig.3 Resizing image in horizontal direction

如果边缘图像条的缩减量较大，说明其中所包含的内容不太重要.通过设置某个阈值θ，判断其缩减比是否超过该阈值，若超过则直接裁剪掉该图像条，以突出重要区域并获得好的图像缩放效果.

裁剪判别规则:如果边缘图像条的缩减比超过了某一阈值，则进行裁剪，并继续判断其相邻图像条.如果相邻图像条的缩减比也超过该阈值，则也进行裁剪.本文中图像每侧至多删除两个图像条以保护图像总体信息和整体视觉效果.

阈值θ的选择是一个较重要的环节，设置过小，边缘图像条被删除的可能性就大，设置过大则不重要的区域难以被合理地删除.本文对RetargetMe图像基准库中的图像进行了实验，θ设为0.65时，可适用于大部分图像的情况.若一图像条被压缩超过65%，表明只有不到35%的尺寸会被保留，将整条的内容用不到35%的空间显示，图像条中将会引入瑕疵，产生扭曲；而压缩比大也说明该图像条的能量较低，属非重要区域.因此，将该条裁剪掉既可以避免扭曲产生，又可使得其他重要度高的图像条尽量少压缩，图像重要目标将得以保持.

图4为不同阈值设置时图像缩减一半的实例.将θ设为0.50时，图像的边缘会被过多裁剪；设为0.75时，因阈值较大，某些非重要区域，以及虽产生了扭曲但并未超过该阈值的区域没被去除，两种情况均会影响缩放效果.而设为0.65时，图像中的重要信息和视觉效果都能被有效地保持.

图4 不同阈值的缩放效果Fig.4 Resized results with different thresholds

根据裁剪规则，若去除了边缘图像条，则需根据式(4)重新计算剩余图像条的缩减量.表1第5列为图1(a)所示图像的最终图像条缩减量，其中图像条1缩减了95列，也即该条被裁剪去掉.

3 算法描述

基于上述分析，本文提出一种快速有效的图像缩放算法，通过结合标准缩放和裁剪来获得高质量的重定效果.单一方向进行图像缩放的算法步骤如下:

(1)由式(1)计算输入图像的能量；

(2)将图像分割成N等份，根据像素列的能量迭代计算得到各图像条的最优宽度；

(3)计算各图像条的缩减量b′i并判断两侧图像条的缩减比例b′i／wi，若大于阈值θ，则裁剪；进一步判断相邻图像条的缩减比例，同理判断是否应被裁剪，重新计算剩余图像条的缩减量；

(4)根据最终缩减量，缩放图像条实现图像重定.

本文算法能够应用于水平方向和垂直方向的图像缩小或放大.对于纵横两方向的缩放，有两种方案:(1)先实现一个方向的缩放，再执行另一个方向的缩放；(2)按照两方向中较小的缩放比例先进行全图标准缩放，然后在另一个方向上按所提出算法实施图像重定.

4 实验及分析

本文实验在主频2.66GHz、内存2GB的双核台式机上进行.图5所示为一幅500×341图像其宽度缩减一半的重定实例.蝴蝶是图像中的重要目标，Scaling算法过分地缩小整幅图像，而Cropping算法会裁剪掉一些内容信息，如左边的花就被裁掉了；Streaming Video[16]算法会使图像的重要内容向下整体偏移.与 Multi－operator算法[6]相似，本文所提出算法有效地保留了重要信息并得到了满意的视觉效果.如图6所示是几种不同算法的缩放实例.实验表明本文算法对大部分RetargetMe图像基准库的图像缩放可以获得满意的结果.

图5 不同算法的结果比较Fig.5 Comparison of results by various methods

图6 几种算法的缩放实例Fig.6 Some examples by several methods

Multi－operator是一种优秀的图像重定算法，通过结合Seam Carving、Scaling和Cropping算法实现图像重定，经反复迭代得到3种算法的优化组合.多算子方法虽可获得较好效果，但迭代过程使该类方法耗时较多.一般地，2种算子组合的方法需2～10min，3～4种算子则需10～20 min才能完成缩放[6，17].例如在主频2.53GHz、内存2GB的双核PC机上，缩减500×333图像至一半尺寸时，Multi－operator耗时120～1 200 s，文献[17]方法(Seam Carving＋Scaling)耗时40～180s，通过结合图像能量和主色描述符定义成本函数加速也需10～40s[18].

本文通过分割、计算图像条的缩减量，来判别使用Scaling缩放或Cropping裁剪图像条实现图像的重定，该方法更为快速有效.对大多数RetargetMe中的图像来说，在水平方向缩小一半的平均耗时为0.2～0.3s，例如图6中蝴蝶、泰姬陵、自行车、船各图像的重定运行时间分别为0.276、0.279、0.268、0.635s.因此本文算法可以有效地适用于便携式设备如手机等的需求.

算法中使用了标准Scaling，使图像缩放较为平滑，可以保持图像的全局视觉效果；同时结合Cropping裁剪不重要的边缘及背景区域，使得重要目标更为清晰突出.

为客观评价图像重定的效果，文中使用Liu等在文献[19]中提到的算法来计算原始图像和重定图像的相似性(取值范围[0，1]).该方法使用一种自顶向下的方法，从局部到全局的视点来组织图像特征，设计一种尺度空间匹配算法便于提取图像的全局几何结构.将本文算法结果与其他几种先进的算法进行了相似性评价比较，包括Multioperator、 Seam Carving、 Non－homogeneous Warping[20]、Scale－and－stretch[4]、Streaming Video[16]和 Scaling等.考虑到 Cropping不会引起任何扭曲变形，在此不将其纳入比较之列.使用RetargetMe图像基准库中的66幅图像，计算原始图像和重定图像的相似度.表2所示是计算得到的相似度平均值及平方和.结果表明本文算法在几种算法中具有较好的效果和排序，这与主观评价结果一致.

表2 几种算法重定结果的相似度评价比较Tab.2 Similarity assessment for various methods

5 结 语

基于图像的条分割及缩放，本文提出了一种快速有效的图像重定算法.通过建立图像能量图，将图像分割成一定宽度的图像条，根据平均能量进行缩放以保持重要目标和兴趣区域，同时对于缩放比例较大的边缘图像条进行裁剪以保持图像的整体视觉效果.大量实例表明，该算法能够得到满意的重定结果，与其他几种先进的算法相比，本文算法的主、客观评价都具有较好的结果.另外，因具有快速、保真等特点，该算法可应用于便携式设备.

[1]Barnes C，Shechtman E，Finkelstein A，etal.Patchmatch: A randomized correspondence algorithm for structural image editing [J].ACM Transactions on Graphics，2009，28(3):Article number 24.

[2]Achanta R，Susstrunk S.Saliency detection for content－aware image resizing [C]／／ICIP 2009.Piscataway:IEEE Computer Society，2009:1005－1008.

[3]HUA Shun－gang，CHEN Guo－peng，WEI Honglei，etal.Similarity measure for image resizing using SIFT feature[J].EURASIP Journal on Image and Video Processing，2012，2012:Article number 6.

[4]Wang Y S，Tai C L，Sorkine O，etal.Optimized scale－and－stretch for image resizing [J]. ACM Transactions on Graphics，2008，27(5):Article number 118.

[5]LIANG Yun，SU Zhuo，LUO Xiao－nan.Patchwise scaling method for content－aware image resizing[J].Signal Processing，2012，92(5):1243－1257.

[6]Rubinstein M，Shamir A，Avidan S.Multi－operator media retargeting [J]. ACM Transactions onGraphics，2009，28(3):Article number 23.

[7]Panozzo D，Weber O，Sorkine O.Robust image retargeting via axis－aligned deformation [J].Computer Graphics Forum，2012，31(2):229－236.

[8]Avidan S，Shamir A.Seam Carving for contentaware image resizing [J].ACM Transactions on Graphics，2007，26(3):Article number 10.

[9]Rubinstein M，Shamir A，Avidan S.Improved Seam Carving for video retargeting [J].ACM Transactions on Graphics，2008，27(3):Article number 16.

[10]Kim J S，Jeong S G，Joo Y，etal.Content－aware image and video resizing based on frequency domain analysis [J].IEEE Transactions on Consumer Electronics，2011，57(2):615－622.

[11]HUA Shun－gang，LI Xiao－xiao，ZHONG Qing.Similarity criterion for image resizing [J].EURASIP Journal on Advances in Signal Processing，2011，2011:Article number 27.

[12]Simakov D， Caspi Y， Shechtman E，etal.Summarizing visual data using bidirectional similarity[C]／／CVPR 2008.Piscataway:IEEE Computer Society，2008.

[13]Rubinstein M，Gutierrez D，Sorkine O，etal.RetargetMe— A benchmark for image retargeting.[2010－01－01].http:／／people.csail.mit.edu／mrub／retargetme.

[14]Achanta R， Hemami S， Estrada F，etal.Frequency－tuned salient region detection [C]／／CVPR 2009.Piscataway:IEEE Computer Society，2009:1597－1604.

[15]Itti L，Koch C，Niebur E.A model of saliencybased visual attention for rapid scene analysis[J].IEEE Transactions on Pattern Analysis and Machine Intelligence，1998，20(11):1254－1259.

[16]Kr henbühl P，Lang M，Hornung A，etal.A system for retargeting of Streaming Video [J].ACM Transactions on Graphics，2009，28(5):Article number 126.

[17]DONG Wei－ming，ZHOU Ning，Paul J，etal.Optimized image resizing using Seam Carving and Scaling[J].ACM Transactions on Graphics，2009，28(5):Article number 125.

[18]DONG Wei－ming，BAO Guan－bo，ZHANG Xiaopeng，etal.Fast multi－operator image resizing and evaluation [J].Journal of Computer Science and Technology，2012，27(1):121－134.

[19]LIU Yong－jin，LUO Xi，XUAN Yu－ming，etal.Image retargeting quality assessment[J].Computer Graphics Forum，2011，30(2):583－592.

[20]Wolf L， Guttmann M， Cohen－Or D. Nonhomogeneous content－driven video－retargeting [C]／／ ICCV 2007. Piscataway:IEEE Computer Society，2007.