刘高源 裴焕斗
【摘要】本文基于Seam Carving图像缩放技术与显著图技术相结合，提出了一种改进Seam Carving的算法。较好的解决了Seam Carving算法对于图像中占比较大物体缩放效果不佳的问题。
【关键词】Seam Carving;显著图;图像缩放
1.引言
图像缩放技术的主要目的都是希望可以完整的保留住图像中的重要特征，为了达到在影像尺寸调整而又能维持前景物件的不畸变有众多的学者进行研究。
传统图像缩放方法非常直观，使用插值的办法对放大或缩小的图像增加或减少像素，通过其临近的像素估算出新的像素点的值。常用的插值算法有最邻近插值法、双线性插值法以及双三次插值法。但是此类方法对图像内容会产生较大的失真，没有考虑图像的梯度信息。
在2007年学者Avidan及Shamir提出了以保留图像内容为目标的图像缩放算法，其不同于以往的插值算法，其核心思路主要是通过区分图像中关键的区域和不易被观察的区域，利用缝补的办法任意调整图像的尺寸。
2.Seam Carving算法介绍
seam carving技术的关键在于缝隙，其垂直缝隙定义为：
公式中的x是一个映射函数，其范围为[1，...，m]。其要表达的意义是这条垂直缝隙是一条由上而下且宽度为1个像素，并且是在8邻近范围内的连续路径。同样水平缝隙的定义为：
其与垂直缝隙差别在于其宽度是从左至右的。
图1 垂直缝隙与水平缝隙示意图
对于缝隙的剪裁方面我们可以给定一个能量函数e，定义其能量成本：
接着就是要找到最佳的缝隙进行剪裁具体步骤如下：
第一步：从第二行开始往下累加所有可能的缝隙路径的最小或者最大能量（按图像是需要缩小还是放大来选择）直至最后一行。当完成第一步以后其最后一行的最小或者最大能量值即为最佳缝隙的起点。
第二步：从起点开始往回找出最佳缝隙其位置的8个邻近点的上方三个位置，其中最小或最大的能量值即是最佳缝隙，一直找到第一行就可以判定最佳缝隙的位置。
当对最佳垂直缝隙与最佳水平缝隙进行剪裁缩小时，其垂直缝隙右边所有像素往左移动一个像素，类似的其水平缝隙下面的所有像素向上移动一个像素，来补偿被剪裁的部分。
所以整张图像只有缝隙部分被删除，而其他部分与之前一样，不会像传统的插值法那样其像素值会被更改。
同理当对最佳垂直缝隙与最佳水平缝隙进行剪裁放大时，则为上述的反向运算，在其缝隙旁插入一个像素，此像素的值是将左右或者上下两边的值做平均而得来。
如此重复的进行剪裁运算即可相应的对图片进行任意尺寸的放大和缩小。使用该技术相对于传统的插值法无论在运算复杂度与图像质量上都能获得理想的平衡。
3.Seam Carving技术的不足
Avidan及Shamir提出的算法是完全自动的，但并非适用于所有的图像上，如果对人脸图像做缩小是采用了Viola and Jones所提出的AdaBoost人脸识别算法，将人脸先保护起来，则这种情况下缩放时不会影响到人脸，而并非所有的图像都会有前置的处理算法对图像进行保护，尤其是当单个物体占整张图像比例较大或者物体穿越整个图像时，缩放就会出现断裂形变现象，因而就必须使用人工的方法选出要保护的部分。
4.Seam Carving技术的改进
从前面可知Avidan及Shamir提出的Seam Cavring算法并非适用于所有图像上，这里我们提出一个改进的方法。利用显著图（saliency map）可以在一张图像中找到重点关注部分的特性，并且在进行seam carving的前提下，尽量保持重要内容的完整性。所以我们想要在缩放之前先利用saliency map做前置处理，限制seam carving的最大限度，再用传统的图像插值法来达到缩放的目的。
整个算法得流程分为五个步骤：
步骤一：找到最佳缝隙（max seam）。即找到能量最大的缝隙，因为我们希望要保留的部分为图像中重要的部分，也就是比较显著的地方。我们用以下数学表达式分别表示垂直及水平的energy map（M、Mh）。
Mh（ij）=e（i，j）+max（M（i-1，j-1），M（i-1，j）， M（i-1，j+1））
Mv（ij）=e（i，j）+max（M（i-1，j-1），M（i，j-1）， M（i+1，j-1））
图像中最后一行的最大值即为我们要找的最佳缝隙的起点。从起点开始往回找出最佳缝隙，也就是向上找其位置的八相邻位上方的三个位置，其最大的即是最佳缝隙的路径，一直找到第一行即可找出能量最大的垂直缝隙Lv，同理水平缝隙也是用相同方法来找到最佳水平缝隙Lh。
步骤二：利用saliency map来产生一个bitmap M'.这个bitmap中值为1所代表的图像即是代表图像中有重要内容的地方;相反的，值为0所代表的是可以删除的部分。其做法是使用Otsu算法算出bitmap的门槛阀值
步骤三：借由步骤二的结果我们可以得到一个门槛阀值T，这个门槛值所代表的就是能够缩小的极限，這个门槛值同样有垂直水平两个方向，其求法如下：
步骤四：当我们求得门槛值后就使用我们seam carving算法缩小至其限制值。
步骤五：使用双三次插值法及seam carving算法缩放至目标大小。
使用改进seam carving算法后图像缩放效果如下：
图2
5.结论
由图像缩放结果可以看出本文提出的改进Seam Carving算法在缝隙的选取上保留了在人类视觉上被重点关注的部分，因此可以有效改善图像缩放效果，减少图像断裂形变的情况发生。这说明改进算法的确可以改善原始算法的不足之处，但是本算法在保持图像不失真的情况下仍存在缩放比例有限等限制因素，这是在未来我们需要进一步研究的方向。
参考文献
[1]Viola，p.，and Jones，M.“Rapid object detection using a boosted cascade of simple features，”In Coference on Computer Vision and Pattern Recognition （CVPR），2001，pp.511-518.
[2]Avidan，S.，Shamir，A.，“Seam Carving for Content-Aware Image Resizing”，ACM Transactions on Graphics（TOG），vol.26，no.3，2007.
[3]Setlur，V.，Takagi，S.，Rasker，R.，Gleicher，M.，and GOOCH，B.，“Automatic Image Retargeting，”ACM International Conference Proceeding Series;vol.154，2005，pp.59-68.
[4]I.Andreadis and A.Amanatiadis，“Digital Image Scaling，”Instrumentation and Measurement Technology Conference，2005.Proceedings of the IEEE，vol.3，16-19pp.2028-2032，May 2005.
[5]M.M.L，S.D.G and S.R，“An image resizing algorithm for binary maps，”Digital Object Identifier pp.126-132，2004.
[6]J.Allebach and P.W.Wong，“Edge-directed interpol-ation，”International Conference on Image Processing， vol.3，16-19 pp.707-710，Sept 1996.
作者簡介：
刘高源，男，湖南长沙人，硕士研究生，现就读于中北大学信息与通信工程学院电子信息技术及仪器专业。
裴焕斗，男，山西代县人，副教授，现供职于中北大学信息与通信工程学院。
