朱 運(yùn)，沈一帆，姜 昊

（復(fù)旦大學(xué) 計(jì)算機(jī)科學(xué)技術(shù)學(xué)院，上海200433）

0 引 言

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

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

1 相關(guān)研究

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

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

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

2 算法流程

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

2.1 重要度圖

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

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

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

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

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

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

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

2.2 劃 分

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

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

圖1 圖像woman的重要度圖

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

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

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

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

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

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

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

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

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

圖2 劃分效果

2.3 縮 放

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

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

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

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

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

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

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

3 實(shí)驗(yàn)和結(jié)果

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

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

圖3 縮放效果

4 結(jié)束語

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

［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）.［王會(huì)千，楊高波，張兆揚(yáng)，等.結(jié)合顯著度圖和自適應(yīng)能量線的快速圖像縮放［J］.計(jì)算機(jī)應(yīng)用研究，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）.［王會(huì)千，楊高波，張兆揚(yáng)，等.基于重要度擴(kuò)散和自適應(yīng)采樣的圖像／視頻縮放技術(shù)［J］.通信學(xué)報(bào)，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.