一种基于视觉显著图的线裁剪算法

彭国琴，施美玲，杨磊，徐丹

(云南大学信息学院，昆明 650091)

1 引言

随着信息技术的不断发展，显示设备的多样性和多功能性对数字媒体提出了新的要求，如设计者必须考虑不同的显示设备，为网页内容设计不同的预选方案和布局格式。电子产品也更加人性化、多元化，如电视、电脑、手机和PDA等，虽然显示设备在变化，但在软件显示格式和信息载体方面仍以传统为主，把这样的信息(主要是指图像)在不同纵横比的显示设备上显示，会引起图像的形变、失真或丢失。

为了不失真地显示图像，就需对待显示的图像进行处理，如对图像适当地缩放，比较常见的是标准图像缩放，但是这种方法没有考虑图像内容，在进行非等纵横比缩放时，由于纵向和横向的大小改变不一样，会导致图像缩放后发生形变，尤其是用户关注的图像视觉主体，即用户感兴趣的区域，如图1(b)中的房子明显的被压扁了，这是不为用户所接受的。

综上所述，图像的标准缩放无法很好地满足用户的需求，用户需要一种能适应不同显示媒介，保持图像主体任意纵横比的缩放算法，针对这一问题，本文提出了基于视觉显著图的线裁剪算法。实验表明，在基于图像内容的图像缩放中，本文提出的算法能够更好地保持视觉主体，尤其是在对图像进行非等纵横比缩放时，具有更好的抗形变能力。

2 相关工作

图像缩放是很多图像处理应用中的一个标准工具，它对图像中的每个像素都公平地处理，把图像缩放到目标大小。近年来，人们更加关注基于图像内容的保持图像主要特征(视觉主体)完整性的缩放，提出了很多保持图像主体的缩放算法，大致可以分为三种:剪切、非均匀缩放和线裁剪。

Chen［1］、Liu［2］、Setlur［4］、Suh［7］和 Santella［8］等人使用剪切的方法来实现把大的图像定位到小的显示设备上的问题，并保持图像中的视觉关注区域。这些算法都会导致信息的丢失，影响用户对完整信息的掌握，另外，如果图像的视觉主体出现在靠近边缘的位置，那么剪切是不能满足用户需求，于是人们提出了非均匀缩放和线裁剪的方法。

非均匀缩放的主要思想是保持图像的视觉主体，让形变发生在那些不感兴趣的区域，允许视觉主体的均匀变化，其它区域非均匀的变化，让非感兴趣区域吸收更多的变形量。Liu 和 Gleicher［3］、Gal［5］、Wolf［10］和 Wang［9］等人利用图像中不同像素点有不同的视觉关注度值来对图像进行非均匀的缩放。

线裁剪算法试图在图像缩放中尽量做到图像的总能量改变最小，只影响图像中能量值小的像素点，保留图像中能量值大的像素点，通过移除或插入能量值较小的像素点来改变图像的大小。Avidan和Shamir［11］提出了保持图像内容的线裁剪算法，把梯度图作为能量图，通过动态规划方法找到图像的优化裁剪线，移除(插入)裁剪线来缩小(放大)图像。Rubinstein等人［12］引入了前向能量标准来查找优化裁剪线，并应用到视频处理上，取得了更好的结果。

Avidan和Rubinstein使用像素点的梯度值作为该像素的能量值，梯度计算反映的是图像的边缘信息，当图像的视觉主体包含有大量的低能量信息时，如视觉主体的纹理不是很丰富，裁剪线就会穿过视觉主体，通过移除或插入这样的裁剪线来改变图像的大小时，必然会引起视觉主体的断裂和形变。这是用户不想看到的结果，为了实现保持视觉主体的图像缩放，本文提出了使用视觉模型来自动检测图像的视觉主体，构建图像的视觉显著图。有时视觉模型会把某些单一的对象认为是显著的，如天空、海水等区域，但是这些区域不一定要被保持，允许它们发生形变，因此我们使用梯度和显著值相结合的方法来度量每个像素点的能量值，认为那些结构化且视觉显著的区域需要保持，其他的区域可以发生形变。

本文使用Itti等人［6］提出的基于视觉显著性的自下而上方法来构建的，该视觉计算模型从图像的颜色、强度和方向三个属性来度量每个像素点的视觉重要程度。实验表明，本文提出的方法获得了比已有的线裁剪算法更好的效果，更好地实现保持主体的图像缩放，如图1(d)。

本文算法的工作流程如图2所示，将在第3部分详细讲述。本文共分为5部分:第1部分是引言，第2部分是相关工作，第3部分是本文算法的实现过程，第4部分是实验结果，第5部分是结论。

图2 本文工作流程

3 算法描述

线裁剪算法使用动态规划法在图像能量图上找到优化的裁剪线，通过对裁剪线的移除或插入来改变图像任意方向的大小。裁剪线是图像中能量和最小的像素点的集合，是这些像素点的八连通路径。本文使用梯度图和显著图相乘作为图像的能量图，梯度表示了对象边界的存在，显著图反映图像的视觉主体即重要特征、感兴趣区域。在该能量图上通过动态规划来找到优化的裁剪线，能很好地避免穿过图像视觉主体，更好地实现保持图像主体的缩放，取得了更好的缩放效果。

3.1 能量图计算

构建图像能量图是本文工作的基础，一个像素点能量值的大小决定了它的视觉重要程度，值越大越重要，视觉关注程度越大，值越小越不被关注，能量值小的点在缩放中可能组成裁剪线而被删除或复制来插入。本文使用梯度值和显著值相乘的结果作为像素点的能量值，构成图像的能量图。

3.1.1 梯度能量图计算

设图像I，大小为n×m，梯度能量函数是对图像中的每一个像素点分别对x方向和y方向求导，e(I)梯度函数为:

3.1.2 显著图计算

本文使用Itti等人提出了自下而上的视觉关注模型，该模型在相关研究的基础上，从生物学的角度，通过“特征融合理论”来解析人类的视觉搜索策略。该模型分别从颜色、强度和方向三个属性出发，如图3所示，分别在不同的尺度上产生高斯金字塔，通过对高斯金字塔进行“中心－周围”差分(Center－surround difference)和归一化。获取各个特征的多幅特征图(Feature map)，对特征图进行跨尺度融合及归一化后，得到图像的显著图S(i，j)。其中强度特征图6幅，颜色特征图12幅，方向特征图24幅。详细实现过程请参照文献［6］。

图3 显著图计算模型

3.1.3 能量图

记能量图为，则为:

3.2 裁剪线的选取

图像I的垂直裁剪线定义为:

其中x是一个映射，x:［1，…，n］→［1，…，m］，即从上到下每一行包含一个像素点，同样定义了映射y，y:［1，…，m］→［1，…，n］，所以一条水平裁剪线是:

使用动态规划算法来寻找优化的裁剪线s*，以垂直裁剪线为例，第一步就是从图像的第二行开始遍历整个图像，为每一点(i，j)计算累积最小能量M(i，j):

然后从M的最后一行开始，回溯找到组成累积最小能量值的像素点，优化裁剪线就是由这些像素点组成的。以上只考虑了裁剪移除(插入)的能量和最小，没有考虑到由于裁剪线的移除(插入)而引入的能量。当移除像素点之后，原来不相邻的像素点会成为邻居，它们之间组成了新的邻接关系，如图4所示，为了更好地实现保持主体的缩放引入了前向能量标准。

图4 三种不同方向的线裁剪

以垂直裁剪线为例，裁剪线中相邻像素点的选取有三种情况:左上方、正上方和右上方，如图4所示。三种情形分别引入的能量为:

在前向能量标准中，新的累积最小能量图M为:

根据前向能量标准，我们在新的累积最小能量图上回溯找到优化的裁剪线s*，实现对图像宽度的改变，同理可以定义水平的累积最小能量图，找到优化的水平裁剪线来改变图像的高度。如图5，显示了图像的水平裁剪线和垂直裁剪线。

减少图像的大小是通过找到优化裁剪线，移除这些裁剪线来实现，移除该裁剪线后，裁剪线右边(下面)的像素点向左(上)移动来填补被移除的像素点的位置。对图像的放大，则通过在裁剪线后面插入像素点实现，插入的像素点的值为裁剪线左右(上下)像素点值的平均。

4 实验分析和对比

图6显示了本文提出的线裁剪算法与前向能量标准线裁剪算法的对比。对图6(a)分别使用前向能量标准算法和本文提出的算法进行相同比例的缩放得到图6(b)和6(c)，从图6中我们可以明显的看到，在一定程度上对保持主体的图像缩放取得了更好的效果。如图6(b)和图6(c)分别是Avidan线裁剪算法和本文算法对原图像进行等宽度缩放的结果，从图中可以明显的看到我们的算法更好的保持了鹅的形状，而在图6(b)可以明显的看到鹅的体型发生了严重的形变。通过实验，证明本文提出的算法更好地保持了图像视觉主体，尤其是对图像进行非等纵横比的缩放时。能够更好地实现保持主体的缩放，主要是由于本文算法中使用了显著图来检测图像的视觉主体，使得这些区域的能量值大，裁剪线无法穿过这些区域，从而实现对这些区域的保持。

5 总结

本文实现了基于图像显著图的线裁剪算法，取得了比已有的线裁剪算法更好的结果，但由于该算法很大程度上依赖于图像的能量图，即图像显著图和梯度图，因此利用不同的梯度计算方法和图像显著图计算方法，产生的效果是不一样的，为了得到更好的缩放效果，今后工作的重点是改进能量图的计算算法，尤其是显著图的计算算法。同时把保持主体的任意图像缩放技术应用到视频处理上也是今后工作的重点。

致谢在此，我们向对本文的工作给予支持和建议的同行，尤其是云南大学视觉媒体实验室(VMC)的同学和老师表示感谢。

［1］ Chen L，Xie X，Fan X.A Visual Attention Model for Adapting Image on Small Diaplays［J］.Multimedia Systems ，2003，353 －364.

［2］ Liu H，Xie X，Ma W，Zhang H.Automatic Browsing of Large Pictures on Mobile Devices［R］.Proceedings of the eleventh ACM international conference on Multimedia，148－155.

［3］ Liu F ，Gleicher M.Video Retargeting:Automating Pan and Scan［C］.In Mulimedia 2006:Proceedings of the 14th annual ACM international conference on Multimedia，ACM，2006，241 －250.

［4］ Setlur V，Takagi S，Raskar R.Automatic Image Retargeting［C］.In The Mobile and Ubiquitous Multimedia(MUM)，ACM press，2005.

［5］ Gal R.，Sorkine O，Cohen －Or D.Feature－ A-ware texturing［C］.In Eurographics Symposium on Rendering.

［6］ Agarwala A，Dontcheva M，Agrawala M.Interactive Digital Photomontage［J］.ACM Trans.Graphs，2004(23)，294 －302.

［7］ Jia J，Sun J，Tang C － K，Shun H － Y.Drag －and － Drop pasting［R］.In Proceedings of SIGGRAPH.

［8］ Viola P，Jones M.Rapid Object Detection Using a Boosted Cascade of Simple Features［R］.Conference on Computer Vision and Pattern Recognition，2001(1):511 －518.

［9］ Itti L Koch C，Neibur E.A Model of Saliencybased Visual Attention for Rapid Scene Analysis［J］.IEEE Trans Pattern Analysis and Machine Intelligence，1998，20(11):1254 －1259.

［10］ Suh B，Ling H，Benjamin B Bederson.Automatic Thumbnail Cropping and Its Effectivenes［C］.In UIST’03:Proceedings of the 16th annual ACM symposium on User interface software and technology，ACM Press，New York，NY，USA，95 －104.

［11］ Santella A，Agrawala M，DeCarlo.Gaze －Based Interaction for Semi－Automatic Photo Cropping［C］.In ACM Human Factors in Computing Systems(CHI)，2006，771 －780.

［12］ Wang Y S Tai C L，Sorkine O，Lee T Y.Optimized Scale－and－Stretch for image Resizing［C］.ACM Trans.Graph.2008.

［13］ Wolf L，Guttmann M，Cohen－Or D.Nonhomogeneous content－driven Video－retargeting［R］.In Proceedings of the Eleventh IEEE International Conference on Computer Vision，2007，1 －6.

［14］ Avidan S，Shamir A.Seam Carving for Content－ aware Image Resizing［J］.ACM Transactions on Graphics，2007，26(3).

［15］ Rubinstein M，Shamir A，Avidan S.Improved Seam Carving for Video Retargeting［J］.ACM Transactions on Graphics，2008，27(3).

［16］ Perez P，Gangnet M，Blake A.Poisson Image Editing［J］.ACM Trans.Graph.2003，22(3):313－318.

［17］ DeCarlo D，Santella A.Stylization and Abstraction of Photographs［J］.ACM Trans.Graph.2002，21(3):769 －776.