基于最小位移可視差的連續(xù)Seam Carving算法在圖像縮放中的研究

崔 嘉 宋 磊 陸宏菊 唐明晰 戚 萌*

①(山東師范大學信息科學與工程學院 濟南 250358)

②(山東師范大學智能信息計算與安全實驗室 濟南 250358)

③(濟南技師學院 濟南 250031)

④(香港理工大學設計學院 香港 999077)

1 引言

隨著眾多數(shù)字媒體設備的出現(xiàn)，同一張照片在不同顯示設備上智能縮放，即圖像縮放技術(image retargeting)已經(jīng)得到了廣泛的關注。圖像縮放的主要目標是保證圖像重要信息的同時改變圖像的尺寸和分辨率，該方法已經(jīng)在眾多領域[1-4]得到了推廣和應用。內(nèi)容敏感縮放(context-aware method)作為非均勻縮放技術被廣泛研究，其中包括Seam Carving[5]及其改進算法。

根據(jù)實現(xiàn)原理，內(nèi)容敏感縮放模型可以分為兩大類：(1)連續(xù)縮放模型，將圖像映射為3維空間內(nèi)的概率分布，根據(jù)顯著性等因素修改映射程度達到圖像縮放的目的，如warping算法[6,7]；(2)離散縮放模型，迭代尋找最小能量線(Seam)，通過增加或刪除Seam實現(xiàn)圖像縮放，如改進的Seam Carving(SC)算法[8,9]。本文主要關注離散縮放模型采用基于SC的內(nèi)容敏感縮放算法。為了保證圖像的重要區(qū)域不丟失，Zhou等人[10]提出的WSM模型(Wall-Seam Model)結合顯著性特征和圖像邊緣信息，采用雙向縮放保持圖像重要信息的同時達到最小縮放扭曲。立體顯著性[11]結合顯著信息、景深信息和梯度能量信息，可以更加準確地估算每一個像素的重要性。文獻[12,13]通過計算顯著能量在物體邊界的加速度不僅能夠保持重要區(qū)域的結構信息，還能夠對非顯著區(qū)域的結構信息進行保護。然而，在上述方法中，縮放扭曲現(xiàn)象始終普遍存在，尤其是在物體邊緣區(qū)域，這將會嚴重影響縮放圖片的質量。主要原因有兩方面：第一，在迭代式縮放過程中扭曲信息是遞增出現(xiàn)的，等到出現(xiàn)嚴重的視覺缺陷時，扭曲現(xiàn)象已經(jīng)過n(n ＞2)代疊加了；第二，S e a m Carving算法的離散式縮放模式導致無法將縮放信息傳遞給下一代，無法在后續(xù)迭代中有效避免嚴重扭曲疊加現(xiàn)象。

為解決上述問題，本文提出新的SC連續(xù)模型，在每一次迭代后，Seam的移除 (增加)會導致輕微的像素位移。相鄰像素間不同方向的位移累積會導致多次迭代后的潛在扭曲。本文提出最小位移可視差(Just Noticeable Distortion, JND)檢測算法計算每次迭代中的像素位移。通過本文提出的能量權重(Energy Weight, Ew)，將JND信息傳遞到下一次迭代中，從而有效避免扭曲現(xiàn)象。Ew和JND的提出，使得改進SC算法從離散縮放模型變成連續(xù)縮放模型。通過與最新縮放算法在公共圖像縮放數(shù)據(jù)集RetargetMe[14]進行對比實驗，驗證了本文方法的有效性和先進性。

2 相關工作

SC算法采用8連通相鄰最小能量線的方式，從上至下或從左至右對圖像進行縮放。由于其算法的普適性和有效性吸引了大量研究人員的關注，基于改進SC的算法陸續(xù)出現(xiàn)。根據(jù)近年來的研究成果，改進算法大致可以分為3個方向。

第一，研究人員致力于圖像顯著性特征的改進，常用的顯著性特征模型包括GBVS(Graph-Based Visual Saliency)模型[15]、Itti模型[16]和HSaliency模型[17]等。結合深度信息的立體顯著性特征[11]、邊緣特征[12,13]、陰影特征[8]和Global Scalar梯度特征[18]等不同特征可以輔助顯著性特征，增強縮放后的重要信息保持。雖然多特征融合有助于更全面地捕捉圖像信息，對于盡可能多地保持圖像重要信息具有積極作用，但是這些特征中缺少對于圖像內(nèi)容和語義方面的指導，往往會導致縮放效果無法兼顧圖像內(nèi)容的語義完整性(邊界扭曲)。

第二，多方法融合算法解決針對單一縮放模型的局限性。Fang等人[19]和Wei等人[20]分別在2017年和2018年提出融合Crop, SC, Warping,Scale和Stretch算法的圖像縮放模型，能夠獲得普遍優(yōu)于單一方法的效果。但是，針對不同類型圖像如何調整和確定各方法間的平衡參數(shù)，以及昂貴的時間代價都對該方向算法的改進提出了挑戰(zhàn)。

第三，還有研究學者采用其他的技術輔助SC算法，例如遺傳算法[10]，Block Artifact Grid[21]和共形映射[22]等。輔助方法都能夠針對某類圖像獲得較好的縮放效果，但是仍不能解決縮放扭曲的問題。本文研究在現(xiàn)有的3個改進方向的基礎上提出了新的思路，即通過JND算法的提出將SC的離散縮放模型改進為連續(xù)模型，能夠將每次迭代的縮放扭曲信息累加傳遞下去，從而改進縮放效果且抑制圖像邊緣扭曲現(xiàn)象。

3 最小位移可視差檢測算法

本文的主要研究目標是改進SC模型的圖像縮放質量，減少縮放后的邊緣扭曲現(xiàn)象。盡管現(xiàn)在已經(jīng)存在很多改進算法且縮放質量逐步提高，經(jīng)過反復試驗發(fā)現(xiàn)對于大比例縮放和圖像內(nèi)容復雜的情況扭曲現(xiàn)象仍普遍存在。本文通過分析發(fā)現(xiàn)，該問題出現(xiàn)的主要原因在于SC算法的離散式迭代和最小能量函數(shù)法。最小能量函數(shù)法僅計算當前狀態(tài)下的能量線(Seam)，離散式迭代導致前一次迭代信息無法傳遞到后續(xù)的縮放過程中。換句話說，如果第i次迭代出現(xiàn)了微小的扭曲，在離散式SC運行機制下扭曲位置無法在第i+1次迭代過程中得到保護。這將會導致接下來的k次迭代后，會出現(xiàn)扭曲放大進而影響縮放的美觀性。因此本文提出假設：如果在每一次迭代過程中的最小扭曲可視差JND能夠進行檢測，并將其傳遞至隨后的迭代過程中，則能有效降低扭曲出現(xiàn)的概率，提高縮放結果的質量。本文連續(xù)模型如圖1所示，其中圖(a)為離散SC模型，圖(b)為本文提出的連續(xù)SC模型，通過結合JND信息和能量權重Ew·(SC+Ew)，圖像縮放能量能夠以累加的方式傳遞到后續(xù)的迭代過程中，有效抑制扭曲現(xiàn)象的出現(xiàn)。

3.1 位移可視差函數(shù)

方向相反的微小像素移動會產(chǎn)生微小的圖像扭曲。經(jīng)實驗表明2個像素以內(nèi)的位移不會產(chǎn)生可視化扭曲。在光流估計研究領域，相鄰兩幀的像素移動可以通過最小化位移差進行計算[23]。受此啟發(fā)，本文定義最小位移可視差JND為像素位移向量，u=(u,v)T，其中u表示水平位移，v表示垂直位移。JND信息可以通過計算相鄰兩次迭代Seam Carving結果的能量相似性進行表達。本文希望在保持圖像重要信息的前提下，相鄰兩次迭代Seam Carving結果具有最高的相似性。也就是說，目標函數(shù)可以表示為Seam Carving的能量差最小化問題，如式(1)所示。

其中，α表示權重，I1為Seam Carving之前的圖像，I2為Seam Carving之后的圖像，x為圖像中的像素，? 為梯度計算。式(1)的第1項為顏色不變約束，第2項為梯度約束。如果u計算準確，則ED(u)將趨向于0。根據(jù)參考文獻[23]，一個好的模型應該傾向于含有更多信息的約束，而不是所有約束。我們定義一個二分權重映射 θ (γ):Z2→{0,1}，在優(yōu)化過程中通過遍歷決定采用哪一項約束。新的能量函數(shù)可以表示為

當 θ(γ)=0 時，梯度約束起作用；當θ(γ)=1時，顏色不變約束起作用。

在Seam Carving過程中，物體邊界對于縮放后的效果起重要的影響。因此，我們定義邊界保持正則項對位移能量進行約束，如式(3)。

其中， x ∈Z2，并且| |?(u)(x)||為 TV正則項，ω(x)為簡單結構適應映射[23]。因此，最終的可視化能量函數(shù)可以定義為式(4)

其 中，λ為正則項權重。

3.2 近似最小化尋優(yōu)

當位移可視差u計算最準確時，式(4)能夠取得最小值。因此，計算u的過程可以看作對式(4)的最小化尋優(yōu)過程，最終目標函數(shù)可以表示為式(5)：

最小化過程中需要同時對兩個變量u和θ進行計算，一般采用迭代優(yōu)化策略。在本文問題中，θ是二分映射，因此我們可以用平均場近似算法[24](Mean Field approximation, MF)化簡優(yōu)化。通過特定狀態(tài)替換θ減少一個變量簡化尋優(yōu)過程。特定狀態(tài)的當前系統(tǒng)概率分布可以表示為式(6)：

其中，β表示溫度反轉的閾值，Z表示狀態(tài)劃分函數(shù)。Z可以表示為式(7)：

沿鞍點方向所有的θ狀態(tài)代入式(7)可近似得到

圖1 傳統(tǒng)SC模型與本文模型對比圖

其 中， ΨI(u,x)=I2(x+u)-I1(x) 和Ψ?I(u,x)=?I2(x+u)-?I1(x)。因此對式(5)的最小化可以近似為對式(8)的最小化。在式(8)中只有一個變量,將會降低優(yōu)化難度。本文提出有效位移可視差函數(shù)可以表示為

將式(9)代入式(5)，最終最小化目標函數(shù)可以表示為

通過對單變量u進行尋優(yōu)，可以計算出每一次Seam Carving迭代后的最小位移可視差作為JND信息。

4 連續(xù)Seam Carving模型

最小位移可視差檢測算法可以獲得每次迭代后縮放的JND信息。在此基礎上，為了解決傳統(tǒng)離散模型對于縮放信息無法傳遞的問題，本文提出采用能量權重Ew表示累加縮放信息。JND中基于8連通域的相鄰像素移動方向相反表明該處大概率會出現(xiàn)扭曲現(xiàn)象。將該位置信息通過權重增加的方式記錄在Ew中，并在后續(xù)的最小能量線查找過程中進行適當?shù)谋Ｗo可以降低扭曲現(xiàn)象出現(xiàn)的概率。本文算法處理流程如圖2所示。每一次迭代過程中，首先對目標圖像提取特征，然后通過SC算法，結合上一次迭代的Ew尋找最小能量線進行縮放；然后將縮放前和縮放后的圖像計算JND信息，將扭曲像素位置在Ew中進行疊加傳遞到下一次迭代過程中，從而將離散的SC模型變?yōu)檫B續(xù)模型。

引入JND信息和Ew后的Seam Carving縮放過程可以表示為式(11)-式(13)：

連續(xù)Seam Carving圖像縮放算法如表1所示。

5 實驗結果分析

5.1 實驗設置

圖2 連續(xù)SC縮放模型處理流程

表1 連續(xù)Seam Carving圖像縮放算法

本文實驗環(huán)境為i7-6700 3.4 GHz, 16 GB DDR內(nèi)存，GTX1070顯卡，顯存8 GB, MATLAB R2015b。本文使用3個特征：顯著性特征Hsaliency[17]，景深特征JNB[25]和結構保持性邊界信息[13]。實現(xiàn)過程中的相關參數(shù)為：式(9)中的λ=0.5, β=5。

本文主要實驗數(shù)據(jù)來自圖像縮放公共數(shù)據(jù)集RegargetMe。為了驗證算法的有效性共設計并實現(xiàn)3組實驗：第1組實驗與當前Seam Carving改進算法進行對比，包括SC[5], WSM[10], SC+SA+DE[11]和本文算法，驗證本文方法針對SC模型改進的有效性；第2組實驗與當前最新其他方法進行比較，驗證本文算法在圖像縮放方面的先進性，包括Crop, SC, Warping[6], SNS[26]，本文方法離散模型和本文方法連續(xù)模型；第3組為定量對比，分別采用當前主流圖像縮放質量評估算法Sift-flow[27],ARS[28,29]和Vssm[30]進行定量對比。

5.2 定性實驗對比和分析

在第1組實驗中，我們針對其他Seam Carving改進算法進行對比實驗。針對高分辨率圖像和運動圖像進行大比例縮放實驗(縮放比例超過60%)，見圖3。

在圖3中，兒童草地圖為高清圖像，SC算法和SA+DE+SC算法都造成了小孩身體的縮小或頭部扭曲，WSM算法刪除了遠處的彩帶，本文算法在前景和背景保持方面都表現(xiàn)良好。在賽車圖中，SC算法導致賽車嚴重縮小，WSM算法造成賽道扭曲，SA+DE+SC算法和本文算法表現(xiàn)良好。在滑板圖中，SC算法和SA+DE+SC算法都對人物及其影子產(chǎn)生了嚴重的扭曲，WSM算法對于背景街道有所扭曲，本文算法對于運動圖像，無論前景還是背景都保持最為完整。通過第1組實驗可以證明本文方法對于扭曲現(xiàn)象具有明顯的減少效果。為了更好地體現(xiàn)JND算法在抑制扭曲方面的效果，我們在圖3所示的縮放過程中，計算前500次迭代過程中的像素級平均扭曲度(JND errors)，將其歸一化至[0, 1]區(qū)間內(nèi)，如圖4所示。圖像扭曲度在縮放開始階段都比較小，隨著縮放迭代數(shù)的增加，扭曲度都在不同程度的遞增(0-150代)。其中，SC算法由于只考慮到圖像梯度能量，扭曲產(chǎn)生得最快；WSM算法增加了邊緣信息的檢測，扭曲度的增加比SC算法略緩。SA+DE+SC算法通過景深能量值和顯著性能量值的約束，扭曲度的增加相較于SC算法和WSM算法更加緩慢。與此3種算法不同的是，本文算法能夠及時地檢測扭曲度并且通過Ew傳遞到下一代，因此本文算法的扭曲度雖然在初期也隨著迭代逐步遞增，但到達一定程度后(0.45)扭曲度遞增程度逐漸降低，并能保持在相對較低的范圍內(nèi)。由此可以證明本文提出的連續(xù)SC模型能夠對扭曲進行抑制，有效地避免了大規(guī)模的扭曲現(xiàn)象。

圖3 SC改進算法定量對比實驗

第2組實驗中，本文與當前主流的各種算法進行了對比，包括傳統(tǒng)縮放方法Crop，經(jīng)典離散縮放方法SC, SNS(Scale-and-Stretch)，經(jīng)典連續(xù)縮放方法Warping, JND+離散SC和JND+連續(xù)SC。實驗數(shù)據(jù)全部來自RegargetMe，選取其中4類圖像：人物、建筑、自然風光和動植物進行多次實驗，如圖5。

圖4 像素級扭曲度對比

在圖5中，從左到右依次為：(a)原圖，(b)Crop算法，(c)標準Seam Carving算法，(d)SNS算法，(e)Warping算法，(f)JND+離散SC模型，(g)JND+連續(xù)SC模型。其中，Crop算法能夠最完美地保持圖像中的重要區(qū)域(包括細節(jié)與尺寸)，但是會造成圖像兩側數(shù)據(jù)的大量丟失；SC算法在人臉、建筑都產(chǎn)生了扭曲；SNS算法雖然扭曲比較少，但是圖像中的重要信息尺寸縮減得最嚴重，例如蝴蝶；Warping算法在自然風景和動植物圖像中都產(chǎn)生了重要信息沒有完整保存的問題。JND+離散SC算法中，人物的臉部明顯扭曲，建筑圖像的尺寸縮減較大。相比較前面的算法，JND+連續(xù)SC算法在4類圖像方面都取得了非常好的縮放效果，在重要信息保持、抑制扭曲現(xiàn)象方面綜合來看明顯優(yōu)于前面的算法。

5.3 定量實驗對比和分析

當前，對于圖像縮放算法主流的評價方法還是基于用戶的視覺判斷。近年來陸續(xù)出現(xiàn)針對縮放質量評估的算法，本文選用其中的3個：Sift-flow,ARS, Vssm。其中，Sift-flow算法能夠計算原始圖像與縮放圖像之間的稠密相關性，用來衡量圖像縮放后內(nèi)容的保持程度，結果越高越好。ARS算法為近年來提出的，通過計算局部block的變化有效地評價縮放后的圖像扭曲程度，結果越高越好。Vssm算法通過雙向patch比較評估顯著性區(qū)域的不相似程度，結果越低越好。

本文在上述4個圖像類別中，每類圖像選取5幅，其中人物圖像和建筑圖像采用50%的縮放比，自然景觀圖像和動植物圖像采用60%的縮放比率。通過計算縮放前后圖像在3個評價算法的平均得分進行對比，具體如表2所示，DISJND表示JND+離散SC模型，CONJND表示JND+連續(xù)SC模型。

圖5 圖像縮放算法定量對比實驗

表2 圖像縮放定量對比

表2中數(shù)據(jù)顯示了本文方法在4個圖像類別中的圖像縮放優(yōu)越性。對于Sift-flow算法評價越高意味著縮放后的圖像與原圖像聯(lián)系越大。通過對比發(fā)現(xiàn)，本文算法提出的JND+連續(xù)SC模型在該指標評價高達0.79。對于ARS算法，Crop方法獲得最高的評價指標，這是因為Crop能夠原樣保存圖像縮放前的重要區(qū)域，不會產(chǎn)生扭曲。但是會造成圖像背景信息的大量丟失。除了Crop算法，本文算法在扭曲約束方面表現(xiàn)最好。對于Vssm算法，同樣是Crop方法獲得最高的評價指標，這是因為基于剪裁的方法，圖像重要區(qū)域與原圖基本相同，因此不相似性最低。除去Crop算法，本文算法仍舊獲得最佳評價。通過定量對比實驗得出的結論基本與5.2節(jié)的定性對比實驗結果一致。

6 結束語

本文提出最小位移可視差檢測算法，能夠在SC每次迭代過程中計算會造成扭曲的JND信息，通過本文提出的能量權值逐代累加傳遞下去，有效地將離散的SC模型變?yōu)檫B續(xù)模型，從而降低了傳統(tǒng)SC過程中出現(xiàn)的扭曲現(xiàn)象。通過實驗證明，基于JND的SC連續(xù)模型對于當前圖像縮放算法在性能上帶來較大的提高。

但由于加大了每次迭代的計算量，本文方法存在耗時嚴重的問題。采用GPU并行算法或其他加速算法減少時間復雜度將是未來需要解決的問題之一。另外，為了進一步提高圖像縮放質量，改進的SC模型與其他算法的結合將會是未來的潛在研究方向。