一種基于條分割及縮放的圖像重定算法

華 順 剛， 蘇 鐵 明， 李 新 豐， 歐 宗 瑛

(大連理工大學(xué) 機(jī)械工程學(xué)院，遼寧 大連 116024)

0 引 言

顯示設(shè)備的多樣性和數(shù)字網(wǎng)絡(luò)的發(fā)展，要求圖像和視頻能夠在各種顯示設(shè)備上，以不同的分辨率或縱橫比顯示，同時能夠完整地保留重要的信息和顯著內(nèi)容.由于缺少對顯著特征分布和圖像內(nèi)容的關(guān)注，傳統(tǒng)的圖像重定方法不能滿足各種類型的顯示設(shè)備的要求，比如標(biāo)準(zhǔn)Scaling和Cropping算法.其中Scaling算法有時會過分縮放圖像，使重要部分產(chǎn)生變形；而Cropping算法則強調(diào)圖像的主要部分，舍棄圖像的邊緣內(nèi)容，可能會丟掉圖像的某些重要信息.

近年來，很多學(xué)者致力于圖像縮放的研究，提出了多種圖像重定算法.其中，基于內(nèi)容感知的算法是一種關(guān)注圖像顯著信息和全局視覺效果的有效方法.該類算法通過使用圖像的顯著圖來實現(xiàn)圖像的縮放，將不重要的內(nèi)容移除，保留重要的信息和目標(biāo)，以實現(xiàn)理想的縮放效果.到目前為止，人們側(cè)重于圖像的不同特征和方面包括圖像的結(jié)構(gòu)、特征、顯著區(qū)域、重要信息及不重要信息等[1－7]，提出了多種基于內(nèi)容感知的圖像縮放算法.

Seam Carving算法[8]是一種經(jīng)典的優(yōu)秀圖像縮放方法，通過移除和復(fù)制不重要區(qū)域的低能量接縫，有效地調(diào)整圖像的大小.一個接縫是該圖中自頂向下或從左到右的能量較低的八連通像素接縫.然而，如果圖像被大幅度收縮，或不太重要的區(qū)域被基本去除，以及興趣目標(biāo)占滿整幅圖像時，重要目標(biāo)及內(nèi)容將產(chǎn)生扭曲變形，局部和全局結(jié)構(gòu)可能被破壞.Rubinstein等[9]改進(jìn)了Seam Carving算法以增強縮放效果并將其拓展到視頻縮放領(lǐng)域.

Kim等[10]基于頻域分析提出了一種自適應(yīng)的圖像和視頻縮放算法.通過優(yōu)化計算將圖像劃分為若干圖像條，根據(jù)圖像頻域信息計算各圖像條的縮減量并擴(kuò)展至視頻縮放領(lǐng)域，但是該方法有時會使圖像中的某些條過度壓縮而使整幅圖像產(chǎn)生扭曲變形.Liang等[5]提出了一種分片的圖像縮放算法，通過強調(diào)圖像的重要區(qū)域來保護(hù)圖像的全局效果.該方法結(jié)合圖像邊緣和顯著度測量建立顯著圖，將原始圖像分割成重要或不重要的圖像塊.該方法的不足在于:如果一個物體被分割到不同的小塊，其邊緣可能會產(chǎn)生錯切效果.

Hua等[3]通過對原始圖像和縮放圖像間相似度(距離)測量的研究，提出了一個基于SIFT特征的圖像縮放算法.由于這類算法需要迭代計算原始圖像和重定圖像的相似度[11－12]，非常耗時.

實驗表明，僅由某種單一的算法很難對所有類型圖像都獲得滿意的重定效果.Rubinstein等[6]提 出 了 一 種 將 Scaling、Cropping 和 Seam Carving算法進(jìn)行組合優(yōu)選的算法，但其尋找某一階段最優(yōu)算子的計算量很大.為提高計算效率，本文研究一種快速的基于內(nèi)容感知的圖像重定算法，通過結(jié)合Scaling和Cropping算法實現(xiàn)快速計算，以獲得高質(zhì)量的圖像目標(biāo)重定效果，并通過對RetargetMe圖像基準(zhǔn)庫[13]的重定實驗，表明本文算法的有效性.

1 圖像分割

一幅圖像由于包含了各種信息或目標(biāo)，若圖像內(nèi)的同一個物體或目標(biāo)能以協(xié)調(diào)一致的比例來縮放，則可以保持其整體視覺效果.將圖像分割成若干區(qū)域時，若某一個物體被劃分到不同的區(qū)域，那么不同部分將以不同的比例被縮放，可能使物體產(chǎn)生扭曲或變形.

對于水平方向尺寸縮放情況，本文首先計算每個像素列的能量和，再盡量將具有相似重要性的像素列分割到同一圖像條內(nèi).在圖像重定過程中，根據(jù)所獲得的顯著圖來縮放各圖像條.本文縮放策略是:圖像條的縮減量與它的重要程度成反比，即能量值越大的圖像條，重要程度越高，縮減比例越?。贿M(jìn)而，將處于邊緣的、縮減比例超過某一閾值的圖像條刪除，以保證某些內(nèi)容不會被過度縮放而造成圖像的扭曲和失真.

1.1 圖像能量圖

圖像中，重要目標(biāo)及顯著區(qū)域因像素的顏色、梯度、亮度等特征較為突出，會存在較高的能量.通過計算基于特征的圖像能量，可以構(gòu)建一幅圖像的能量圖，從而感知圖像重要信息的位置和程度.基于能量圖通過優(yōu)化迭代，可將圖像劃分成若干不同能量的圖像條.

有多種計算能量圖的方法，如梯度法、Harris－corners角點檢測、人臉檢測、圖像熵函數(shù)及梯度直方圖等算法[8].其中較經(jīng)典的計算方法是梯度法.其2范數(shù)形式為

另外，Achanta等[14]定義的能量圖注重檢測圖像中視覺效果明顯的區(qū)域，該方法將圖像色彩從RGB模型轉(zhuǎn)換為Lab模型，利用色彩和亮度，通過一種調(diào)頻方法計算圖像的顯著區(qū)域.文獻(xiàn)[10]結(jié)合重要性圖和由Itti等[15]提出并改進(jìn)的顯著圖方法，用于圖像和視頻的縮放.Avidan等的研究工作表明，圖像的梯度信息可以很好地用于圖像重定工作中[8]，因此，本文使用式(1)來建立圖像的能量圖.圖1為兩幅由圖像的梯度信息建立的能量圖實例.

圖1 原始圖像及其梯度圖Fig.1 Original images and their gradient maps

1.2 圖像條分割

基于能量圖可以將圖像分割成若干圖像條.這里只描述單一方向上的圖像縮放情況，將輸入圖像I的寬、高從n×m調(diào)整到n′×m，這樣b＝n－n′表示水平方向上的縮減量.首先根據(jù)式(1)計算每一像素的能量，并由式(2)累積各列像素的能量值進(jìn)而生成能量圖.圖2所示為圖1(a)(n×m＝500×333)中圖像所對應(yīng)的列累積梯度能量圖.

首先將原始圖像沿寬度方向均勻分割成N等份，即可得到N個圖像條.根據(jù)列累積能量圖由下式進(jìn)行迭代計算，得到各圖像條的最優(yōu)寬度值:

式中:li表示圖像條的左側(cè)水平坐標(biāo)，這里l1＝1，lN＋1＝n；ci－1和ci分別是對應(yīng)于第(i－1)和第i個圖像條的平均能量值，由計算得到；α為取值[0，1]的權(quán)重參數(shù).

式(3)表明，對于每一圖像條，最小化該條中的各列與其平均能量的差，同時最大化鄰近圖像條的平均能量差，以獲得優(yōu)化的坐標(biāo)li，使某一圖像條內(nèi)各列盡可能具有相似的重要程度.α則表示最小類內(nèi)、最大類間差值的分配權(quán)重.迭代過程中，使li－1和li＋1固定，通過從li－1到li＋1－1遍歷取值，重復(fù)計算li直至得到優(yōu)化值.如此，具有相似重要性的像素列被聚集到同一圖像條中，即較高(或較低)能量的像素列被盡可能劃分到一起.

圖2 列累積能量圖Fig.2 Column accumulated energy map

對于圖像條數(shù)目N的選擇，可以設(shè)置一個適當(dāng)?shù)闹?，如果取值偏小，圖像的能量特征難以充分顯現(xiàn)；反之，則會增加計算時間.大量實驗表明，N的取值大小對圖像的重定效果不會產(chǎn)生非常明顯的影響.因此本文中N取為10.

首先將圖像劃分成N個圖像條，得到各圖像條的寬度為n／N.由式(3)計算第(i－1)個圖像條的寬度wi－1＝li－li－1.表1列出了圖1(a)對應(yīng)的圖像條寬度和縮減量數(shù)據(jù).通過優(yōu)化迭代，各圖像條的計算寬度wi見表中第2列數(shù)據(jù).其中第2和第8圖像條分別具有最小寬度6和最大寬度97.第3列為平均能量值ci，第1圖像條具有最低平均能量值14.73，說明該圖像條最不重要.第4列和第5列是各圖像條的縮減量，將在下一節(jié)加以描述.

表1 分割圖1(a)生成的圖像條寬度及其縮減量Tab.1 Strip width and reduced amount associated with Fig.1(a)

2 圖像條的縮減量計算

圖像分割后即可進(jìn)行各圖像條的縮減量計算.一個高能量的圖像條，很可能包含重要的信息和目標(biāo)，應(yīng)盡可能少地縮減其寬度以保持圖像條內(nèi)的重要信息；反之，應(yīng)將低能量的圖像條盡可能大地縮放以實現(xiàn)圖像重定的需要.基于上述策略，定義如下公式計算圖像條的縮減量:

式中:b表示一幅圖像的全部縮減量；b′i為第i圖像條的縮減量，應(yīng)正比于圖像條寬wi，反比于其平均能量ci；對于原始圖像(圖1(a))在水平方向縮減一半的情況，由式(4)計算得到的各圖像條的縮減量見表1第4列.可見圖像條1原分割寬度為95，因平均能量最低，計算縮減量為66，有最大的縮放比例0.695(66／95)；圖像條6有最大的平均能量32.88，其縮放比例最小，為0.317(19／60).

通過縮減各圖像條的寬度，可以得到縮放的目標(biāo)圖像.如圖3所示，房屋(圖3(a))和汽車(圖3(c))均是圖像中的重要物體.由于包含房屋和汽車的圖像條具有高能量，其縮減量較小；而包含背景等不重要區(qū)域的圖像條的縮減量則較大.然而，從圖3(d)中可以看到，圖像左側(cè)邊緣部分被過分地壓縮，使這部分圖像內(nèi)容產(chǎn)生了錯切變形.鑒于此，下面將引入裁剪來避免此類由于區(qū)域過度縮減而使圖像產(chǎn)生扭曲和失真的情況.

圖3 水平方向的圖像縮放Fig.3 Resizing image in horizontal direction

如果邊緣圖像條的縮減量較大，說明其中所包含的內(nèi)容不太重要.通過設(shè)置某個閾值θ，判斷其縮減比是否超過該閾值，若超過則直接裁剪掉該圖像條，以突出重要區(qū)域并獲得好的圖像縮放效果.

裁剪判別規(guī)則:如果邊緣圖像條的縮減比超過了某一閾值，則進(jìn)行裁剪，并繼續(xù)判斷其相鄰圖像條.如果相鄰圖像條的縮減比也超過該閾值，則也進(jìn)行裁剪.本文中圖像每側(cè)至多刪除兩個圖像條以保護(hù)圖像總體信息和整體視覺效果.

閾值θ的選擇是一個較重要的環(huán)節(jié)，設(shè)置過小，邊緣圖像條被刪除的可能性就大，設(shè)置過大則不重要的區(qū)域難以被合理地刪除.本文對RetargetMe圖像基準(zhǔn)庫中的圖像進(jìn)行了實驗，θ設(shè)為0.65時，可適用于大部分圖像的情況.若一圖像條被壓縮超過65%，表明只有不到35%的尺寸會被保留，將整條的內(nèi)容用不到35%的空間顯示，圖像條中將會引入瑕疵，產(chǎn)生扭曲；而壓縮比大也說明該圖像條的能量較低，屬非重要區(qū)域.因此，將該條裁剪掉既可以避免扭曲產(chǎn)生，又可使得其他重要度高的圖像條盡量少壓縮，圖像重要目標(biāo)將得以保持.

圖4為不同閾值設(shè)置時圖像縮減一半的實例.將θ設(shè)為0.50時，圖像的邊緣會被過多裁剪；設(shè)為0.75時，因閾值較大，某些非重要區(qū)域，以及雖產(chǎn)生了扭曲但并未超過該閾值的區(qū)域沒被去除，兩種情況均會影響縮放效果.而設(shè)為0.65時，圖像中的重要信息和視覺效果都能被有效地保持.

圖4 不同閾值的縮放效果Fig.4 Resized results with different thresholds

根據(jù)裁剪規(guī)則，若去除了邊緣圖像條，則需根據(jù)式(4)重新計算剩余圖像條的縮減量.表1第5列為圖1(a)所示圖像的最終圖像條縮減量，其中圖像條1縮減了95列，也即該條被裁剪去掉.

3 算法描述

基于上述分析，本文提出一種快速有效的圖像縮放算法，通過結(jié)合標(biāo)準(zhǔn)縮放和裁剪來獲得高質(zhì)量的重定效果.單一方向進(jìn)行圖像縮放的算法步驟如下:

(1)由式(1)計算輸入圖像的能量；

(2)將圖像分割成N等份，根據(jù)像素列的能量迭代計算得到各圖像條的最優(yōu)寬度；

(3)計算各圖像條的縮減量b′i并判斷兩側(cè)圖像條的縮減比例b′i／wi，若大于閾值θ，則裁剪；進(jìn)一步判斷相鄰圖像條的縮減比例，同理判斷是否應(yīng)被裁剪，重新計算剩余圖像條的縮減量；

(4)根據(jù)最終縮減量，縮放圖像條實現(xiàn)圖像重定.

本文算法能夠應(yīng)用于水平方向和垂直方向的圖像縮小或放大.對于縱橫兩方向的縮放，有兩種方案:(1)先實現(xiàn)一個方向的縮放，再執(zhí)行另一個方向的縮放；(2)按照兩方向中較小的縮放比例先進(jìn)行全圖標(biāo)準(zhǔn)縮放，然后在另一個方向上按所提出算法實施圖像重定.

4 實驗及分析

本文實驗在主頻2.66GHz、內(nèi)存2GB的雙核臺式機(jī)上進(jìn)行.圖5所示為一幅500×341圖像其寬度縮減一半的重定實例.蝴蝶是圖像中的重要目標(biāo)，Scaling算法過分地縮小整幅圖像，而Cropping算法會裁剪掉一些內(nèi)容信息，如左邊的花就被裁掉了；Streaming Video[16]算法會使圖像的重要內(nèi)容向下整體偏移.與 Multi－operator算法[6]相似，本文所提出算法有效地保留了重要信息并得到了滿意的視覺效果.如圖6所示是幾種不同算法的縮放實例.實驗表明本文算法對大部分RetargetMe圖像基準(zhǔn)庫的圖像縮放可以獲得滿意的結(jié)果.

圖5 不同算法的結(jié)果比較Fig.5 Comparison of results by various methods

圖6 幾種算法的縮放實例Fig.6 Some examples by several methods

Multi－operator是一種優(yōu)秀的圖像重定算法，通過結(jié)合Seam Carving、Scaling和Cropping算法實現(xiàn)圖像重定，經(jīng)反復(fù)迭代得到3種算法的優(yōu)化組合.多算子方法雖可獲得較好效果，但迭代過程使該類方法耗時較多.一般地，2種算子組合的方法需2～10min，3～4種算子則需10～20 min才能完成縮放[6，17].例如在主頻2.53GHz、內(nèi)存2GB的雙核PC機(jī)上，縮減500×333圖像至一半尺寸時，Multi－operator耗時120～1 200 s，文獻(xiàn)[17]方法(Seam Carving＋Scaling)耗時40～180s，通過結(jié)合圖像能量和主色描述符定義成本函數(shù)加速也需10～40s[18].

本文通過分割、計算圖像條的縮減量，來判別使用Scaling縮放或Cropping裁剪圖像條實現(xiàn)圖像的重定，該方法更為快速有效.對大多數(shù)RetargetMe中的圖像來說，在水平方向縮小一半的平均耗時為0.2～0.3s，例如圖6中蝴蝶、泰姬陵、自行車、船各圖像的重定運行時間分別為0.276、0.279、0.268、0.635s.因此本文算法可以有效地適用于便攜式設(shè)備如手機(jī)等的需求.

算法中使用了標(biāo)準(zhǔn)Scaling，使圖像縮放較為平滑，可以保持圖像的全局視覺效果；同時結(jié)合Cropping裁剪不重要的邊緣及背景區(qū)域，使得重要目標(biāo)更為清晰突出.

為客觀評價圖像重定的效果，文中使用Liu等在文獻(xiàn)[19]中提到的算法來計算原始圖像和重定圖像的相似性(取值范圍[0，1]).該方法使用一種自頂向下的方法，從局部到全局的視點來組織圖像特征，設(shè)計一種尺度空間匹配算法便于提取圖像的全局幾何結(jié)構(gòu).將本文算法結(jié)果與其他幾種先進(jìn)的算法進(jìn)行了相似性評價比較，包括Multioperator、 Seam Carving、 Non－h(huán)omogeneous Warping[20]、Scale－and－stretch[4]、Streaming Video[16]和 Scaling等.考慮到 Cropping不會引起任何扭曲變形，在此不將其納入比較之列.使用RetargetMe圖像基準(zhǔn)庫中的66幅圖像，計算原始圖像和重定圖像的相似度.表2所示是計算得到的相似度平均值及平方和.結(jié)果表明本文算法在幾種算法中具有較好的效果和排序，這與主觀評價結(jié)果一致.

表2 幾種算法重定結(jié)果的相似度評價比較Tab.2 Similarity assessment for various methods

5 結(jié) 語

基于圖像的條分割及縮放，本文提出了一種快速有效的圖像重定算法.通過建立圖像能量圖，將圖像分割成一定寬度的圖像條，根據(jù)平均能量進(jìn)行縮放以保持重要目標(biāo)和興趣區(qū)域，同時對于縮放比例較大的邊緣圖像條進(jìn)行裁剪以保持圖像的整體視覺效果.大量實例表明，該算法能夠得到滿意的重定結(jié)果，與其他幾種先進(jìn)的算法相比，本文算法的主、客觀評價都具有較好的結(jié)果.另外，因具有快速、保真等特點，該算法可應(yīng)用于便攜式設(shè)備.

[1]Barnes C，Shechtman E，F(xiàn)inkelstein A，etal.Patchmatch: A randomized correspondence algorithm for structural image editing [J].ACM Transactions on Graphics，2009，28(3):Article number 24.

[2]Achanta R，Susstrunk S.Saliency detection for content－aware image resizing [C]／／ICIP 2009.Piscataway:IEEE Computer Society，2009:1005－1008.

[3]HUA Shun－gang，CHEN Guo－peng，WEI Honglei，etal.Similarity measure for image resizing using SIFT feature[J].EURASIP Journal on Image and Video Processing，2012，2012:Article number 6.

[4]Wang Y S，Tai C L，Sorkine O，etal.Optimized scale－and－stretch for image resizing [J]. ACM Transactions on Graphics，2008，27(5):Article number 118.

[5]LIANG Yun，SU Zhuo，LUO Xiao－nan.Patchwise scaling method for content－aware image resizing[J].Signal Processing，2012，92(5):1243－1257.

[6]Rubinstein M，Shamir A，Avidan S.Multi－operator media retargeting [J]. ACM Transactions onGraphics，2009，28(3):Article number 23.

[7]Panozzo D，Weber O，Sorkine O.Robust image retargeting via axis－aligned deformation [J].Computer Graphics Forum，2012，31(2):229－236.

[8]Avidan S，Shamir A.Seam Carving for contentaware image resizing [J].ACM Transactions on Graphics，2007，26(3):Article number 10.

[9]Rubinstein M，Shamir A，Avidan S.Improved Seam Carving for video retargeting [J].ACM Transactions on Graphics，2008，27(3):Article number 16.

[10]Kim J S，Jeong S G，Joo Y，etal.Content－aware image and video resizing based on frequency domain analysis [J].IEEE Transactions on Consumer Electronics，2011，57(2):615－622.

[11]HUA Shun－gang，LI Xiao－xiao，ZHONG Qing.Similarity criterion for image resizing [J].EURASIP Journal on Advances in Signal Processing，2011，2011:Article number 27.

[12]Simakov D， Caspi Y， Shechtman E，etal.Summarizing visual data using bidirectional similarity[C]／／CVPR 2008.Piscataway:IEEE Computer Society，2008.

[13]Rubinstein M，Gutierrez D，Sorkine O，etal.RetargetMe— A benchmark for image retargeting.[2010－01－01].http:／／people.csail.mit.edu／mrub／retargetme.

[14]Achanta R， Hemami S， Estrada F，etal.Frequency－tuned salient region detection [C]／／CVPR 2009.Piscataway:IEEE Computer Society，2009:1597－1604.

[15]Itti L，Koch C，Niebur E.A model of saliencybased visual attention for rapid scene analysis[J].IEEE Transactions on Pattern Analysis and Machine Intelligence，1998，20(11):1254－1259.

[16]Kr henbühl P，Lang M，Hornung A，etal.A system for retargeting of Streaming Video [J].ACM Transactions on Graphics，2009，28(5):Article number 126.

[17]DONG Wei－ming，ZHOU Ning，Paul J，etal.Optimized image resizing using Seam Carving and Scaling[J].ACM Transactions on Graphics，2009，28(5):Article number 125.

[18]DONG Wei－ming，BAO Guan－bo，ZHANG Xiaopeng，etal.Fast multi－operator image resizing and evaluation [J].Journal of Computer Science and Technology，2012，27(1):121－134.

[19]LIU Yong－jin，LUO Xi，XUAN Yu－ming，etal.Image retargeting quality assessment[J].Computer Graphics Forum，2011，30(2):583－592.

[20]Wolf L， Guttmann M， Cohen－Or D. Nonhomogeneous content－driven video－retargeting [C]／／ ICCV 2007. Piscataway:IEEE Computer Society，2007.