一種基于視覺顯著圖的線裁剪算法

彭國琴，施美玲，楊磊，徐丹

(云南大學信息學院，昆明 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.