基于Seam Carving技術(shù)的圖像縮放改進(jìn)算法研究

劉高源 裴煥斗

【摘要】本文基于Seam Carving圖像縮放技術(shù)與顯著圖技術(shù)相結(jié)合，提出了一種改進(jìn)Seam Carving的算法。較好的解決了Seam Carving算法對(duì)于圖像中占比較大物體縮放效果不佳的問(wèn)題。

【關(guān)鍵詞】Seam Carving;顯著圖;圖像縮放

1.引言

圖像縮放技術(shù)的主要目的都是希望可以完整的保留住圖像中的重要特征，為了達(dá)到在影像尺寸調(diào)整而又能維持前景物件的不畸變有眾多的學(xué)者進(jìn)行研究。

傳統(tǒng)圖像縮放方法非常直觀，使用插值的辦法對(duì)放大或縮小的圖像增加或減少像素，通過(guò)其臨近的像素估算出新的像素點(diǎn)的值。常用的插值算法有最鄰近插值法、雙線性插值法以及雙三次插值法。但是此類(lèi)方法對(duì)圖像內(nèi)容會(huì)產(chǎn)生較大的失真，沒(méi)有考慮圖像的梯度信息。

在2007年學(xué)者Avidan及Shamir提出了以保留圖像內(nèi)容為目標(biāo)的圖像縮放算法，其不同于以往的插值算法，其核心思路主要是通過(guò)區(qū)分圖像中關(guān)鍵的區(qū)域和不易被觀察的區(qū)域，利用縫補(bǔ)的辦法任意調(diào)整圖像的尺寸。

2.Seam Carving算法介紹

seam carving技術(shù)的關(guān)鍵在于縫隙，其垂直縫隙定義為：

公式中的x是一個(gè)映射函數(shù)，其范圍為[1，...，m]。其要表達(dá)的意義是這條垂直縫隙是一條由上而下且寬度為1個(gè)像素，并且是在8鄰近范圍內(nèi)的連續(xù)路徑。同樣水平縫隙的定義為：

其與垂直縫隙差別在于其寬度是從左至右的。

圖1 垂直縫隙與水平縫隙示意圖

對(duì)于縫隙的剪裁方面我們可以給定一個(gè)能量函數(shù)e，定義其能量成本：

接著就是要找到最佳的縫隙進(jìn)行剪裁具體步驟如下：

第一步：從第二行開(kāi)始往下累加所有可能的縫隙路徑的最小或者最大能量（按圖像是需要縮小還是放大來(lái)選擇）直至最后一行。當(dāng)完成第一步以后其最后一行的最小或者最大能量值即為最佳縫隙的起點(diǎn)。

第二步：從起點(diǎn)開(kāi)始往回找出最佳縫隙其位置的8個(gè)鄰近點(diǎn)的上方三個(gè)位置，其中最小或最大的能量值即是最佳縫隙，一直找到第一行就可以判定最佳縫隙的位置。

當(dāng)對(duì)最佳垂直縫隙與最佳水平縫隙進(jìn)行剪裁縮小時(shí)，其垂直縫隙右邊所有像素往左移動(dòng)一個(gè)像素，類(lèi)似的其水平縫隙下面的所有像素向上移動(dòng)一個(gè)像素，來(lái)補(bǔ)償被剪裁的部分。

所以整張圖像只有縫隙部分被刪除，而其他部分與之前一樣，不會(huì)像傳統(tǒng)的插值法那樣其像素值會(huì)被更改。

同理當(dāng)對(duì)最佳垂直縫隙與最佳水平縫隙進(jìn)行剪裁放大時(shí)，則為上述的反向運(yùn)算，在其縫隙旁插入一個(gè)像素，此像素的值是將左右或者上下兩邊的值做平均而得來(lái)。

如此重復(fù)的進(jìn)行剪裁運(yùn)算即可相應(yīng)的對(duì)圖片進(jìn)行任意尺寸的放大和縮小。使用該技術(shù)相對(duì)于傳統(tǒng)的插值法無(wú)論在運(yùn)算復(fù)雜度與圖像質(zhì)量上都能獲得理想的平衡。

3.Seam Carving技術(shù)的不足

Avidan及Shamir提出的算法是完全自動(dòng)的，但并非適用于所有的圖像上，如果對(duì)人臉圖像做縮小是采用了Viola and Jones所提出的AdaBoost人臉識(shí)別算法，將人臉先保護(hù)起來(lái)，則這種情況下縮放時(shí)不會(huì)影響到人臉，而并非所有的圖像都會(huì)有前置的處理算法對(duì)圖像進(jìn)行保護(hù)，尤其是當(dāng)單個(gè)物體占整張圖像比例較大或者物體穿越整個(gè)圖像時(shí)，縮放就會(huì)出現(xiàn)斷裂形變現(xiàn)象，因而就必須使用人工的方法選出要保護(hù)的部分。

4.Seam Carving技術(shù)的改進(jìn)

從前面可知Avidan及Shamir提出的Seam Cavring算法并非適用于所有圖像上，這里我們提出一個(gè)改進(jìn)的方法。利用顯著圖（saliency map）可以在一張圖像中找到重點(diǎn)關(guān)注部分的特性，并且在進(jìn)行seam carving的前提下，盡量保持重要內(nèi)容的完整性。所以我們想要在縮放之前先利用saliency map做前置處理，限制seam carving的最大限度，再用傳統(tǒng)的圖像插值法來(lái)達(dá)到縮放的目的。

整個(gè)算法得流程分為五個(gè)步驟：

步驟一：找到最佳縫隙（max seam）。即找到能量最大的縫隙，因?yàn)槲覀兿ＭＡ舻牟糠譃閳D像中重要的部分，也就是比較顯著的地方。我們用以下數(shù)學(xué)表達(dá)式分別表示垂直及水平的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））

圖像中最后一行的最大值即為我們要找的最佳縫隙的起點(diǎn)。從起點(diǎn)開(kāi)始往回找出最佳縫隙，也就是向上找其位置的八相鄰位上方的三個(gè)位置，其最大的即是最佳縫隙的路徑，一直找到第一行即可找出能量最大的垂直縫隙Lv，同理水平縫隙也是用相同方法來(lái)找到最佳水平縫隙Lh。

步驟二：利用saliency map來(lái)產(chǎn)生一個(gè)bitmap M'.這個(gè)bitmap中值為1所代表的圖像即是代表圖像中有重要內(nèi)容的地方;相反的，值為0所代表的是可以刪除的部分。其做法是使用Otsu算法算出bitmap的門(mén)檻閥值

步驟三：借由步驟二的結(jié)果我們可以得到一個(gè)門(mén)檻閥值T，這個(gè)門(mén)檻值所代表的就是能夠縮小的極限，這個(gè)門(mén)檻值同樣有垂直水平兩個(gè)方向，其求法如下：

步驟四：當(dāng)我們求得門(mén)檻值后就使用我們seam carving算法縮小至其限制值。

步驟五：使用雙三次插值法及seam carving算法縮放至目標(biāo)大小。

使用改進(jìn)seam carving算法后圖像縮放效果如下：

圖2

5.結(jié)論

由圖像縮放結(jié)果可以看出本文提出的改進(jìn)Seam Carving算法在縫隙的選取上保留了在人類(lèi)視覺(jué)上被重點(diǎn)關(guān)注的部分，因此可以有效改善圖像縮放效果，減少圖像斷裂形變的情況發(fā)生。這說(shuō)明改進(jìn)算法的確可以改善原始算法的不足之處，但是本算法在保持圖像不失真的情況下仍存在縮放比例有限等限制因素，這是在未來(lái)我們需要進(jìn)一步研究的方向。

參考文獻(xiàn)

[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.

作者簡(jiǎn)介：

劉高源，男，湖南長(zhǎng)沙人，碩士研究生，現(xiàn)就讀于中北大學(xué)信息與通信工程學(xué)院電子信息技術(shù)及儀器專(zhuān)業(yè)。

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