基于內(nèi)容劃分和傅里葉分析的圖像縮放算法

朱 運，沈一帆，姜 昊

（復旦大學 計算機科學技術學院，上海200433）

0 引 言

保持圖像重要內(nèi)容和視覺連貫性是圖像縮放算法的兩個重要要求。傳統(tǒng)的圖像縮放方法包括比例變化（scaling）和裁剪（cropping），但是它們各有各的缺點。非等比例的縮放會造成圖像中的物體變形失真，而裁剪雖然可以避免變形失真，但是它需要用戶交互信息，并且會丟失圖像中次重要的信息。這兩種算法都難以滿足人們對圖像縮放的要求。因此人們提出了基于內(nèi)容的圖像縮放技術，其主要步驟為：①檢測原圖像中的顯著性區(qū)域；②根據(jù)顯著性區(qū)域選擇合適的縮放算子。主要的縮放算法一般可以分為兩類：一類是以Seam Carving算法為代表的離散型縮放算子，該類方法利用貪心算法逐步刪除或復制圖像中不重要的seam，直至達到指定的縮放尺寸；另一類是以變形技術（Image Warping）為代表的連續(xù)型縮放算子，該類方法將圖像視為連續(xù)的區(qū)域，將縮放過程視為原圖像區(qū)域通過幾何形變直至指定形狀的過程。前者算法簡潔，計算效率較高，但容易產(chǎn)生人工痕跡，出現(xiàn)視覺瑕疵；后者計算開銷較大，且容易產(chǎn)生局部比例失調(diào)的現(xiàn)象。因此，尋找高效且廣泛適用的基于內(nèi)容的圖像縮放算法依然是計算機圖像處理方向的研究熱點。

本文在此提出了一種結(jié)合基于內(nèi)容自適應劃分和傅里葉分析的圖像縮放算法，它綜合考慮了圖像的視覺顯著性、語義信息和結(jié)構(gòu)信息，將圖像劃分為多個子圖，并根據(jù)其視覺重要度自適應性地采樣，較好地保護了圖像中的重要內(nèi)容和全局框架，有效地避免了視覺失真，實驗證明了該算法的有效性。

1 相關研究

Shamir和Sorkin在文獻［1］總結(jié)了圖像縮放算法的三條原則：①縮放后的圖像必須保持原圖像中的重要內(nèi)容；②縮放后的圖像必須保持原圖像中的結(jié)構(gòu)信息；③縮放后的圖像必須避免視覺失真。但這三條原則卻往往存在矛盾，例如對于指定的縮小尺寸，保護重要區(qū)域則意味著刪除更多的非重要區(qū)域像素，而這往往會造成視覺失真，因此現(xiàn)有的圖像縮放算法只能盡量地滿足該三條原則并取得某種平衡。

文獻［2］提出了開創(chuàng)性的Seam Carving算法，該算法每次刪除和復制圖像中能量最小的seam直至到達指定大小，它可以有效地保護圖像中的重要內(nèi)容，但是對于包含復雜場景和顯著結(jié)構(gòu)的圖像，其縮放處理效果則不盡如人意。文獻［3］對其做了改進，利用k－means對圖像進行劃分，加速了Seam Carving中求最小能量seam的動態(tài)規(guī)劃過程。文獻［4］提出了最早的非均勻變形（warping）算法，該算法對原圖像中重要區(qū)域等比縮放，而非重要部分則根據(jù)縮放尺寸進行調(diào)整，因此往往造成非重要區(qū)域變形失真。文獻［5］則將圖像劃分為多個網(wǎng)格，對不同的網(wǎng)格應用不同的變形操作，并定義視覺損失能量函數(shù)以衡量變形操作所造成的失真程度，將形變過程轉(zhuǎn)換為求解帶有限制條件的函數(shù)優(yōu)化問題，但該算法計算開銷非常大，且存在局部比例失調(diào)的現(xiàn)象。文獻［6］將圖像縮放看成采樣過程，根據(jù)對圖像重要度的擴散和平滑確定采樣因子。文獻［7］利用頻域分析對圖像進行縮放，但它只考慮了圖像的結(jié)構(gòu)信息，而容易造成圖像內(nèi)容區(qū)域變形。文獻［8］利用濾波的思想，將原圖像中像素位移量視作其顯著度的積分，其縮放效果依賴于其顯著度圖檢測效果。

根據(jù)圖像縮放算法的三條原則，本文提出了基于內(nèi)容劃分和傅里葉分析的圖像縮放算法。首先計算了輸入圖像的重要度圖，該重要度圖包含了視覺顯著度信息，圖像語義信息和全局結(jié)構(gòu)信息。然后根據(jù)重要度圖將圖像轉(zhuǎn)換為一維離散信號，并且通過對該信號的分析將原圖像自適應地劃分為多個子圖。接著利用傅里葉變換和頻域分析確定每個子圖縮放的比例。最后根據(jù)其縮放比例對每個子圖進行下采樣，最終獲得指定尺寸的縮放圖像。

2 算法流程

不失一般性，本文假設只對圖像進行水平方向上的縮放（因為垂直方向上的縮放可以通過相同算法類推獲得）。因此圖像縮放過程可以表示為：對于分辨率為m×n的原圖像I以及分辨率為m′×n′的目標圖像I′（其中m＝m′，n′＜n），希望找到這樣一個映射函數(shù)f：I→I′，使得：①目標圖像I′盡可能地保全原圖像I中的重要內(nèi)容；②目標圖像I′盡可能地保全原圖像I中的重要結(jié)構(gòu)；③目標圖像I′盡可能地避免視覺失真。

2.1 重要度圖

為了保護圖像中的重要內(nèi)容和結(jié)構(gòu)信息，本節(jié)定義了重要度圖來衡量原圖像中每個區(qū)域?qū)τ谟^察者的重要程度。重要度圖是和原圖像大小相等的二維矩陣，其中每一項的值反映了原圖像中對應像素點處的重要程度，取值為［0，1］。根據(jù)人類視覺的特征，通常認為圖像中的視覺顯著區(qū)域，語義信息區(qū)域和結(jié)構(gòu)信息區(qū)域是重要區(qū)域，因此本節(jié)對這3種類型區(qū)域分別進行了檢測，并最后合并計算出原圖像的重要度圖。

根據(jù)人類視覺模型，利用顏色，亮度和方向等底層視覺特征在不同尺度上的對比程度來檢測圖像的顯著度，可以較好地提取圖像中人眼敏感的視覺顯著區(qū)域，其結(jié)果記做Si。

為了識別圖像中的內(nèi)容信息，文獻［9］提出了基于上下文的顯著度（context－aware saliency）檢測算法，通過計算每個圖像塊（patch）和與其最相似的K個圖像塊在顏色域和空間域上的距離來檢測圖像的顯著度，并根據(jù)Gestalt法則（即人類視覺焦點總是接近的）對其進行了修正，它可以有效地提取體現(xiàn)圖像語義和內(nèi)容信息的區(qū)域。因此，本文應用該算法計算原圖像中的語義信息區(qū)域，其結(jié)果記做Sc。

梯度表示圖像中的邊緣信息，可以用來衡量原圖像中的結(jié)構(gòu)信息區(qū)域。本文使用Sobel算子計算其梯度圖，其表達式為

綜上，輸入圖像的重要度圖S可以表示為

式中：α，β、γ——比例系數(shù)，在本文實驗中α＝0.6，β＝0.6，γ＝0.2。

圖1是圖像woman的重要度圖。其中圖1（a）是輸入圖像，圖1（b）是視覺顯著度圖，圖1（c）是應用文獻［9］算法得到的語義顯著度圖，圖1（d）是梯度圖，即結(jié)構(gòu)顯著度圖，圖1（e）是最終的重要度圖。可以看到該重要度圖能夠較好地體現(xiàn)原圖像中的視覺顯著性信息，語義信息以及整體結(jié)構(gòu)信息，圖中較亮的部分反映了人眼對圖像woman最為關注的區(qū)域。

2.2 劃 分

由于對同一個物體或區(qū)域應用不同的縮放比例會導致視覺變形失真，為了避免該情況，需要對相同的物體或區(qū)域盡量應用相同的縮放比例。因此，根據(jù)第2.1節(jié)計算得到的重要度圖對輸入圖像進行劃分，將相同的物體和重要區(qū)域盡可能地劃分到同一個子圖中，使得可以對子圖應用相同的縮放算子。自適應內(nèi)容劃分算法的步驟如下：

首先，將輸入圖像的重要度圖S通過式（3）轉(zhuǎn)換為長度為n的一維離散信號C

圖1 圖像woman的重要度圖

式中：c（x）——橫坐標為x的所有像素點在垂直方向上的重要度的平均值。該信號反映了輸入圖像在水平方向上的重要度分布。

然后，使用雙邊濾波器對C進行濾波。雙邊濾波器可以保護一維信號震蕩強烈的區(qū)域，而對信號中震蕩不那么劇烈的區(qū)域進行平滑，因此可以較好地在保護不同重要區(qū)域邊界的同時降低重要區(qū)域內(nèi)部像素的重要度差異，提高劃分的準確度。

接著，應用動態(tài)規(guī)劃方法對C進行自適應劃分，其具體步驟如下。

（1）初始化對C的劃分。首先將C平均地劃分為K個子信號，每個子信號的長度為m／K，在本文實驗中K取10。此處用向量B來描述一個劃分，其中B＝（b1，b2，...，bK＋1），bk和bk＋1分別為第k個子信號左邊界和右邊界的坐標。對于初始劃分B，bk＝kn／K，且b0＝1，bK＋1＝n。

（2）根據(jù)式（4）動態(tài)地更新每一個bk

式中：sk－1、sk——分割點bk左邊和右邊的子信號內(nèi)部重要度的平均值。式（5）的前兩項表示分割點bk左右兩邊的子信號內(nèi)部重要度差異，而第三項表示這兩個子信號之間的重要度差異。而式（4）表示在固定bk－1和bk＋1的情況下，尋找一個最優(yōu)的bk使得兩邊的子信號內(nèi)部重要度差異盡可能地小，而不同子信號之間的重要度差異盡可能地大（即尋找使得能量函數(shù)J最小的bk），其中參數(shù)α是用來確保子信號最小寬度，本文實驗中α取5。

（3）合并相似子信號。由于初始定義的子信號個數(shù)K可能遠遠大于圖像中重要區(qū)域的數(shù)量，可能導致將某個重要區(qū)域劃分到不同的子圖中，因此需要在根據(jù)圖像的內(nèi)容自適應地調(diào)整圖像劃分的數(shù)量。當劃分向量B中的所有項更新完畢時，先檢測其是否收斂：如果收斂，則轉(zhuǎn)向步驟4）；否則，逐步檢測相鄰的兩個子信號之間平均顯著度的差異｜sk－sk－1｜，如果該差異小一定的閾值時，則將兩個子信號合并，然后轉(zhuǎn)到步驟（2），在本文實驗中，該閾值取。

（4）根據(jù)對一維信號C的劃分對輸入圖像I進行劃分。

圖2是圖像woman的劃分效果圖。其中圖2（a）是輸入圖像，圖2（b）是未使用合并的劃分效果圖，圖2（c）是使用合并的劃分效果圖。可以看到在未使用合并的劃分中，圖像中的重要區(qū)域（人的頭和腿）被劃分到了不同的子圖中；而在使用合并的劃分中，圖中的女人被較好地劃分到了一個子圖中，且其劃分結(jié)果符合該輸入圖像的整體結(jié)構(gòu)。

圖2 劃分效果

2.3 縮 放

對于被劃分為多個子圖的輸入圖像，需要根據(jù)每個子圖的重要度信息決定其縮放因子，使得非重要區(qū)域縮放的像素更多一些，而重要區(qū)域盡可能保持不變。假設lk是第k個子圖的寬度，而rk表示該子圖需要刪除的列個數(shù)，因此每個子圖的采樣率為。

每個子圖中的重要度分布情況可以用一維的離散信號Ck來描述，其定義類似式（3），而刪除子圖中列的過程可以視為對該信號進行下采樣的過程。而下采樣過程中，該信號損失的是其高頻部分，即圖像中的細節(jié)信息，因而導致該信號或圖像失真，因此需要最小化其能量損失。在本文中使用指數(shù)函數(shù)來模擬該一維離散信號，其中sk的定義見式（6）。對該信號進行傅里葉變換，其高頻部分損失的能量為

而所有子圖經(jīng)過下采樣造成的高頻部分能量損失可以表示為

我們用式（8）中能量作為衡量是視覺連貫性損失的能量函數(shù)（visual distortion energy function）。因此，需求出使得該能量函數(shù)值最小的rk，且rk需要滿足限制條件

該問題等價于帶有限制條件的能量優(yōu)化問題，可以使用拉格朗日乘數(shù)法，即對函數(shù)

對rk求導，使其偏導數(shù)等于0，得到的結(jié)果為

最后根據(jù)rk對所有子圖進行均勻下采樣，從而得到最終的縮放結(jié)果。

3 實驗和結(jié)果

為了測試本文算法的性能，本文在CPU為Pentium（R）4 2.00GHz和內(nèi)存為3G的PC上進行了仿真實驗，編程語言采用的是matlab r2011a，而作為對比的算法是Seam Carving和文獻［4］中的算法。在將分辨率為700×1024的輸入圖像縮小至分辨率為700×512的目標圖像的過程中，Seam Carving算法平均耗時24s，文獻［4］中的算法平均耗時13s，而本文中的算法平均耗時0.7s，可以看出該算法的計算效率優(yōu)于Seam Carving和文獻［4］中的縮放效率。這主要是因為該算法計算完輸入圖像的重要度圖后，所有的頻域分析和縮放操作都是投影到一維向量空間進行操作的，大大地減少了計算開銷。

同時為了測試本文的性能，將本算法應用于文獻［10］中提出的圖像縮放標準數(shù)據(jù)庫，并與Seam Carving算法，裁剪算法和文獻［4］中算法的縮放效果進行比較。圖3是應用不同縮放算法所得的縮放效果圖。其中圖3（a）是輸入圖像，圖3（b）是應用了Seam Carving算法的結(jié)果，圖3（c）是應用了裁剪算法的結(jié)果，圖3（d）是應用了文獻［5］中縮放算法的結(jié)果，圖3（e）是本文算法的結(jié)果，以上算法的縮放比例均為50%。從實驗結(jié)果中可以看到：Seam Carving算法逐次刪除圖像中的不重要seam，但在圖像中可供刪除的不重要seam數(shù)量不足以讓原圖像縮放至指定尺寸的情況時，依然按照貪心算法刪除重要區(qū)域的seam而不考慮這些重要區(qū)域的全局信息，無法保護其視覺連貫性，例如圖3（a）中小孩的臉，在縮放過程中產(chǎn)生了嚴重的視覺變形；裁剪算法選取最優(yōu)的裁剪窗口，雖然不會產(chǎn)生變形，但無法傳遞原圖像的整體信息，不可避免地會造成圖像信息丟失，例如圖3（b）中小孩和雪人各被裁剪掉了一部分；文獻［5］中通過非均勻的變形算法獲得縮放圖像，雖然可以保全原圖像的整體結(jié)構(gòu)信息和重要區(qū)域，但由于對非重要區(qū)域的形變是只加有縮放尺寸的限制而無其它約束條件，因而容易造成不同區(qū)域間物體的縮放比例不協(xié)調(diào)，例如圖3（d）中小孩的臉和身體就比例失調(diào)了。而本文中的算法充分考慮輸入圖像的視覺顯著性信息、內(nèi)容語義信息和全局結(jié)構(gòu)信息，因而可以較好地保護輸入圖像中的重要區(qū)域和結(jié)構(gòu)信息，且根據(jù)其重要度信息進行劃分采樣，使得同一重要區(qū)域應用同樣的采樣率和采樣方法，從而保持目標圖像的視覺連貫性，在效果圖3（e）中，圖像中的重要區(qū)域（小孩和雪人）的比例基本保持協(xié)調(diào)，原圖像的整體架構(gòu)也得到了保護，其產(chǎn)生的視覺失真遠小于其它幾種算法。

圖3 縮放效果

4 結(jié)束語

本文提出了一種基于內(nèi)容劃分和傅里葉分析的圖像縮放算法。首先根據(jù)縮放算法3個原則，建立了結(jié)合了視覺顯著信息，語義信息，結(jié)構(gòu)信息的重要度圖。接著根據(jù)該重要度圖，對輸入圖像進行動態(tài)地劃分，使得不同的重要區(qū)域被劃分到不同的子圖中。最后，根據(jù)傅里葉變換和頻域分析確定每個子圖的采樣率并對之進行下采樣，從而得到最終的目標圖像。與同類的seam carving，裁剪等算法相比，該算法的計算效率較高，并且較好地在保護原圖像的重要區(qū)域和結(jié)構(gòu)的同時，避免了視覺上的變形和失真現(xiàn)象。在引入幀差異信息的情況下，該算法可以拓展到視頻縮放處理領域。

［1］Shamir A，Sorkine O.Visual media retargeting［C］／／SIGGRAPH ASIA.Yokohama，Japan：ACM，2009.

［2］Avian S，Shamir A.Seam carving for content－aware image resizing［J］.ACM Transactions on Graphics，2007，26（3）：267－276.

［3］WANG Huiqian，YANG Gaobo，ZHANG Zhaoyang，et al.Fast image resizing by combining with saliency map and adaptive seam［J］.Application Research of Computers，2010，27（9）：3594－3597（in Chinese）.［王會千，楊高波，張兆揚，等.結(jié)合顯著度圖和自適應能量線的快速圖像縮放［J］.計算機應用研究，2010，27（9）：3594－3597.］

［4］Wolf L，Guttmann M，Cohen－or D.Non－h(huán)omogeneous content－driven video－retargeting［C］／／Proceedings of the 11th IEEE International Conference on Computer Vision.Rio de Janeiro，Brazil：IEEE Computer Society，2007.

［5］ Wang Yu－Shuen，Tai Chiew－Lan，Sorkine O，et al.Optimized scale－and－stretch for image resizing［J］.ACM Transactions on Graphics，2008，27（5）：1－8.

［6］WANG Huiqian，YANG Gaobo，ZHANG Zhaoyang，et al.Image and video resizing algorithm based on importance diffusion and adaptive scaling［J］.Journal on Communications，2011，32（8）：166－170（in Chinese）.［王會千，楊高波，張兆揚，等.基于重要度擴散和自適應采樣的圖像／視頻縮放技術［J］.通信學報，2011，32（8）：166－170.］

［7］Kim Jun－Seong，Kim Jin－Hwan，Kim Chang－Su.Adaptive image and video retargeting technique based on fourier analysis［C］／／Proceedings of the 22th IEEE Confe－rence on Computer Vision and Pattern Recognition.Florida，USA：IEEE Computer Society，2009.

［8］Ding Yuanyuan，Xiao Jing，Yu Jingyi.Important filtering for image retageting［C］／／Proceedings of the 24th IEEE Conference on Computer Vision and Pattern Recognition.Colorado Springs，USA：IEEE Computer Society，2009.

［9］Stas Goferman，Lihi Zelnik－Manor，Ayellet Tal.Context－aware saliency detection［C］／／Proceedings of the 23th IEEE Conference on Computer Vision and Pattern Recognition.San Francisco，USA：IEEE Computer Society，2010.

［10］Rubinstein M，Gutierrez D，Sorkine O，et al.A comparative study of image retargeting［J］.ACM Transactions on Graphics，2010，29（6）：1－9.