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

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

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

②(山東師范大學(xué)智能信息計(jì)算與安全實(shí)驗(yàn)室 濟(jì)南 250358)

③(濟(jì)南技師學(xué)院 濟(jì)南 250031)

④(香港理工大學(xué)設(shè)計(jì)學(xué)院 香港 999077)

1 引言

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

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

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

2 相關(guān)工作

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

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

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

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

3 最小位移可視差檢測(cè)算法

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

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

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

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

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

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

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

其 中，λ為正則項(xiàng)權(quán)重。

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

當(dāng)位移可視差u計(jì)算最準(zhǔn)確時(shí)，式(4)能夠取得最小值。因此，計(jì)算u的過(guò)程可以看作對(duì)式(4)的最小化尋優(yōu)過(guò)程，最終目標(biāo)函數(shù)可以表示為式(5)：

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

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

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

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

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

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

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

4 連續(xù)Seam Carving模型

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

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

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

5 實(shí)驗(yàn)結(jié)果分析

5.1 實(shí)驗(yàn)設(shè)置

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

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

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

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

5.2 定性實(shí)驗(yàn)對(duì)比和分析

在第1組實(shí)驗(yàn)中，我們針對(duì)其他Seam Carving改進(jìn)算法進(jìn)行對(duì)比實(shí)驗(yàn)。針對(duì)高分辨率圖像和運(yùn)動(dòng)圖像進(jìn)行大比例縮放實(shí)驗(yàn)(縮放比例超過(guò)60%)，見(jiàn)圖3。

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

圖3 SC改進(jìn)算法定量對(duì)比實(shí)驗(yàn)

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

圖4 像素級(jí)扭曲度對(duì)比

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

5.3 定量實(shí)驗(yàn)對(duì)比和分析

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

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

圖5 圖像縮放算法定量對(duì)比實(shí)驗(yàn)

表2 圖像縮放定量對(duì)比

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

6 結(jié)束語(yǔ)

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

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