基于梯度矢量方向性分析的线裁剪算法

聂栋栋 马勤勇 马利庄

①(燕山大学理学院 秦皇岛 066004)

②(燕山大学信息科学与工程学院 秦皇岛 066004)

③(上海交通大学计算机科学与工程系 上海 200240)

1 引言

图像缩放是图像处理领域的一个基本问题，它通过改变图像的分辨率适应不同的显示设备，满足各类应用需求。基于内容感知的图像适应算法成为近年来图像缩放领域的一个新的研究热点[1−4]，尤其是其中的线裁剪算法得到了众多研究者的广泛关注。该算法定义单像素宽的连续的近似水平或垂直的曲线为像素线路，然后根据图像像素的重要性，提取对人视觉影响最小的像素线路，最后通过复制或删除图像中像素线路，调整图像尺寸。算法最初由文献[5]提出，文献[6]将其扩展到了3维时空域中对视频图像进行处理。文献[7]通过线性算法在图像相邻的行或列间建立完全匹配关系，加快了算法的处理速度。文献[8]利用用户提供的相对深度地图，在线裁剪过程中实现对象的相互遮挡。文献[9]通过利用双向相似函数[10]在主颜色描述[11]及欧拉距离等基础上定义图像距离函数，并将图像线裁剪与图像缩放算法相结合。还有不少学者通过将显著性地图、人脸检测等[12,13]引入像素能量图的计算，改进算法处理效果。

本文提出了一种基于梯度矢量方向性分析的线裁剪算法，它通过对局部区域的图像梯度矢量场进行低通滤波，能更好地利用这类存在大量视觉冗余的随机纹理区域，进而更好地保护图像的边缘轮廓结构等真正视觉关注的重点区域。此外，本文还提出了新的像素能量计算方法，它在提取行、列像素线路时，对像素的梯度矢量的x,y方向的梯度分量分别赋予不同的权值。实验结果显示，文中算法算法的处理结果在整体视觉效果上更好，能够更好地保护视觉敏感的边缘轮廓结构。通过对算法处理后的目标图像和原图像的完整性距离和一致性距离进行分析，结果也显示与其它几种算法相比较，本文算法处理后的目标图像内所保留的图像信息最为完整，而且新引入的畸变也最小。

2 线裁剪算法

传统线裁剪算法根据图像梯度区分图像像素对人类视觉感知的重要性，以此提取像素线路并进行删除、插入处理。

一般而言，假设源图像大小为M×N，目标图像大小为M′×N，则线裁剪算法就需要提取条行像素线路。每条行像素线路的定义如下：

提取像素线路则根据像素线路上像素的能量和，优先选择能量较小的，即

提取到行像素线路后，若目标图像尺寸比原始图像小，则删除该像素线路就可以使图像尺寸缩小一行。如此循环处理次即可获得行数为M′的目标图像。若目标图像尺寸比原始图像大，为了避免同时选中一条像素线路，则先记录次提取的像素线路，再将这些像素线路拷贝后插入到图像相应位置就可以使图像尺寸达到目标。

当需要缩小图像宽度时，需要提取的就是列像素线路，其处理过程与行像素线路的类似，本文就不再赘述。

3 基于梯度矢量方向性分析的线裁剪算法

大量实验显示，以上线裁剪算法处理后的图像容易产生如下问题：首先是由于所提取的像素线路过度集中在某个图像区域，造成目标图像信息缺失，使图像整体的视觉效果处理前后差异过大；其次是部分图像边缘结构处容易产生视觉敏感的畸变。

鉴于以上问题，本文提出新的线裁剪算法。它利用线裁剪算法中被忽略的梯度矢量的方向性，即利用梯度矢量方向在不同图像区域的不同表现，以及不同梯度矢量方向在行列像素线路提取时产生的视觉影响也不同这两个特点，改善图像的处理效果。

研究发现，当线裁剪算法所提取的像素线路过度集中在某个图像区域时，并不完全是因为只有该区域存在大量视觉冗余信息，更可能是因为其它视觉冗余区域存在有较杂乱的纹理细节，使得算法误认为这些区域也是视觉关注的重点。注意到这类纹理区的梯度大小虽然会相对较大，但梯度方向却非常杂乱。因此本文算法提出对图像的梯度矢量场进行低通滤波，以消除这些纹理区域对像素重要性计算的影响。具体公式如下：

其中G为滤波后的梯度矢量场，∇Iy, ∇Ix和Gx,Gy分别表示低通滤波前后x,y方向的梯度值；*表示2维卷积运算；F为低通滤波器，考虑到算法复杂性，本文采用简单的2维均值滤波器，其大小取经验值为5×5。

需要说明的是本文通过Sobel算子计算图像梯度。因此，对于灰度图像：

其中H为Soble算子，∇Ix表示Soble算子提取的灰度图(亮度图)上的x方向梯度值；

而且对于彩色图像，考虑到彩色图像转换成灰度图像后必然会损失部分信息，本文直接在RGB彩色图像上提取像素梯度信息。对于彩色图像：

其中Ir,Ig,Ib分别表示彩色图像的红、绿、蓝3分量；表示Soble算子提取的相应分量上x方向的梯度值。

需要注意的是，本文采用Matlab中的x,y坐标方向，即x坐标表示垂直(行)方向与y坐标方向表示水平(列)方向。

与的计算类似，就不再重复说明了。

本文算法对图像整体视觉效果的保护，如图1所示。可以看出，由于梯度矢量的低通滤波削弱了近处大片纹理区的视觉重要性，使像素线路的提取更为合理，本文算法的整体视觉效果与原图更相似。

研究还发现，线裁剪算法所提取的像素线路在穿过不同梯度方向的边缘后，对视觉效果造成的影响明显不同。比如，当行像素线路在穿过水平走向的边缘后，会造成该边缘的左右两段发生显著错位，这是人类视觉感知非常敏感的图像畸变。而在行像素线路在穿过垂直走向的边缘后，虽然会改变该边缘的高度，但这种变化很难被视觉感知。同样，在列像素线路提取时也存在类似的情况。

这就说明，像素的重要性不仅取决于该像素梯度矢量的大小，同时与其梯度矢量的方向也有关。因此，本文对式(3)定义的像素能量函数进行修改，使算法在提取行列像素线路时，分别采用不同的像素能量计算公式：

其中ex,ey分别对应于提取行、列像素线路时的像素能量；w1,w2为经验权值，一般取w1=w2= 0 .8。

在新的像素能量计算基础上，算法根据式(2)提取累积能量最小的像素线路，再通过删除或复制像素线路改变原图像的尺寸，生成合适的目标图像。

4 实验结果及分析

本文算法实验是在PC机上的Matlab环境下进行的，并着重与文献[5]，文献[6]和文献[12]的算法进行了对比。为了表述的方便，本文分别以ASC, RSC,SSC表示这3种算法。

图2，图3显示了本文算法与ASC, RSC, SSC算法的比较。从中可以看出，本文算法的处理结果视觉效果要明显好于其它3种算法。如图2中白鹤伸开的翅膀以及图3中蘑菇的伞盖部分其它3种算法处理后都产生了明显的畸变，而本文算法的处理则保留了与原图相似的轮廓结构。

图4显示了本文算法对其它图像的处理结果。从中可以看出本文算法可以更好地利用图中的草地、树林等视觉相对冗余的信息，进而更好地保护图像中视觉更重要的区域，如图4(a)中的小房及树，4(b)中的溪流，4(c)中的椰子树。

为了客观地衡量算法处理后的目标图像与原始图像间的视觉相似性距离，实验采用了图像的完整性距离和一致性距离这两个指标。分别用于分析原图像中信息在处理后的目标图像中是否被完整保留以及目标图像中的信息是否和原图像一致(产生畸变的程度)。具体定义如下：

图1 本文算法与文献中算法对图像整体视觉效果保护的比较

图2 本文算法对白鹤图的处理结果((a)为原始图像，(b), (c), (d), (e)分别表示ASC, RSC, SSC以及本文算法对原图宽度缩小后的处理结果，(f), (g), (h), (i)分别表示ASC, RSC, SSC以及本文算法对原图高度缩小后的处理结果)

图3 本文算法对黄蘑菇图的处理结果((a)为原始图像，(b), (c), (d), (e)分别表示ASC, RSC, SSC以及本文算法对原图宽度缩小后的处理结果，(f), (g), (h), (i)分别表示ASC, RSC, SSC以及本文算法对原图高度缩小后的处理结果)

图4 本文算法对其它图像处理结果(第1行为原始图像，第2, 3, 4, 5行分别表示ASC, RSC, SSC以及本文算法的处理结果)

其中S,T分别表示原图像和目标图像；表示完整性距离，表示一致性距离；P,Q分别表示原图像和目标图像中的图像块；D(P,Q)表示多分辨率分析下两图像块的欧拉距离的最小值；Ns,NT表示原图像和目标图像的图像块数目。图5给出了实验中当所删除的像素线路占原图比例的逐渐增加后，本文算法，ASC, RSC, SSC算法的处理结果与原图像的相似性距离变化的曲线。从中可以看出，随着所删除的像素线路占原图比例越来越大，4种算法的完整性距离和一致性距离都逐渐增大，但相比其它3种算法，本文算法在增长趋势上明显较缓。这也说明需要提取较多的像素线路时，本文算法处理后的图像与原图像的完整性距离、一致性距离比其它3种算法都要小，即本文算法生成的目标图像对原图像的信息保存最为完整，新引入的图像畸变最小。

图5 ASC, RSC, SSC以及本文算法处理结果的相似性距离随像素线路占原图比例变化的曲线

5 结束语

本文重点考虑了之前线裁剪算法中被忽略的梯度矢量的方向性，提出了一种基于梯度矢量方向性分析的线裁剪算法。实验通过主、客观两方面的分析，显示相比其它几种算法，本文算法处理后的目标图像与原始图像整体视觉效果更加接近，图像边缘轮廓等细节保护的也较好。

[1] Kim Jun-Seong, Jeong Seong-Gyun, Joo Younghun,et al..Content-aware image and video resizing based on frequency domain analysis [J].IEEE Transactions on Consumer Electronics, 2011, 57(2): 615-622.

[2] Wang Shu-fan and Lai Shang-hong. Compressibility-aware media retargeting with structure preserving[J].IEEE Transactions on Image Processing, 2011, 20(3): 855-865.

[3] 施美玲, 徐丹. 主体大小能控的内容感知图像缩放[J]. 计算机辅助设计与图形学学报, 2011, 23(5): 915-922.Shi Mei-ling and Xu Dan. A prominent object size adjustable method for content-aware image resizing[J].Journal of Computer-Aided Design&Computer Graphics, 2011, 23(5):915-922.

[4] 雷励星. 基于混合能量的内容敏感图像缩放新方法[J]. 计算机学报, 2010, 33(10): 2016-2021.Lei Li-xing. Content-aware image resizing based on hybrid energy[J].Chinese Journal of Computers, 2010, 33(10):2016-2021.

[5] Avidan S and Shamir A. Seam carving for content-aware imageresizing [J].ACM Transaction on Graphics, 2007, 26(3):Article No.10.

[6] Rubinstein M, Shamir A, and Avidan S. Improved seam carving for video retargeting [J].ACM Transaction on Graphics, 2008, 27(3): Article No.16.

[7] Huang Hua, Fu Tian-Nan, Rosin P L,et al.. Real-time content-aware image resizing[J].Science in China Series F:Information Sciences, 2009, 52(2): 172-182.

[8] Mansfield A, Gehler P, Gool L,et al.. Scene carving: scene consistent image retargeting[C]. Proceedings of the 11th European Conference on Computer Vision: Part I. Heidelberg:Springer, 2010: 143-156.

[9] Dong Weiming, Zhou Ning, Paul J C,et al.. Optimized image resizing using seam carving and scaling[J].ACM Transactions on Graphics, 2009, 28(5): Article No.125.

[10] Simakov D, Caspi Y, Shechtman E,et al.. Summarizing visual data using bidirectional similarity[C]. Proceedings of IEEE Conference on Computer Vision and Pattern Recognition, Los Alamitos: IEEE Computer Society Press,2008: 1-8.

[11] Min Rui and Cheng H D. Effective image retrieval using dominant color descriptor and fuzzy support vector machine[J].Pattern Recognition, 2009, 42(1): 147-157.

[12] Achanta R and Susstrunk S. Saliency detection for content-aware image resizing[C]. Proc of IEEE ICIP’09,Piscataway, NJ, IEEE, 2009: 1005-1008.

[13] Chen Jianhui, Miao Lanfang, and Liu Xinguo. Balanced energy for content-aware image resizing [C]. Proc of 3rd IEEE International Conference on Ubi-media Computing,Piscataway, NJ, IEEE, 2010: 24-29.