基于Seam Carving技術的圖像縮放改進算法研究

劉高源 裴煥斗

【摘要】本文基于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.

作者簡介：

劉高源，男，湖南長沙人，碩士研究生，現就讀于中北大學信息與通信工程學院電子信息技術及儀器專業。

裴煥斗，男，山西代縣人，副教授，現供職于中北大學信息與通信工程學院。