基于Seam Carving的雙向接縫裁剪圖像重定向

陳加玲， 葉少珍, 2

(1. 福州大學(xué)數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院， 福建 福州 350108； 2. 福州大學(xué)智能制造仿真研究院， 福建 福州 350108)

0 引言

隨著經(jīng)濟(jì)與科學(xué)技術(shù)的發(fā)展， 數(shù)字電子設(shè)備普及千家萬戶， 同一尺寸圖像在不同屏幕比例的數(shù)字電子設(shè)備上普遍存在顯示差異， 于是如何處理圖像與屏幕尺寸不適配問題成為新的研究熱點(diǎn). 針對(duì)這個(gè)問題， 傳統(tǒng)圖像縮放技術(shù)一般有三種方法， 均勻縮放、 居中裁剪和黑邊填充. 均勻縮放是通過幾何變換方式對(duì)圖像像素進(jìn)行映射填充， 會(huì)對(duì)圖像的水平及豎直方向上造成擠壓或拉伸形變； 居中裁剪是按顯示屏寬高比盡可能大的范圍裁剪圖像中間區(qū)域， 雖然圖像整體沒有發(fā)生扭曲， 但是圖像信息部分丟失了； 黑邊填充是對(duì)圖像進(jìn)行等比縮放加上邊緣黑色填充， 雖沒有整體扭曲和內(nèi)容丟失， 但屏幕周圍填充的黑邊， 沒有充分利用屏幕空間特性. 這些傳統(tǒng)技術(shù)都采用統(tǒng)一處理方式， 無差別地處理所有結(jié)構(gòu)和內(nèi)容相差異的圖像， 往往達(dá)不到用戶滿意的結(jié)果.

1 現(xiàn)有圖像重定向方法比較

與傳統(tǒng)方法不同， 內(nèi)容感知的重定向方法通過自動(dòng)識(shí)別不同內(nèi)容區(qū)域的重要程度， 并保持高重要性的主體區(qū)域不變或均勻縮放， 同時(shí)允許重要性低且分布均勻的背景區(qū)域盡可能調(diào)整和適當(dāng)變形. 當(dāng)前內(nèi)容感知的圖像重定向方法主要有以下幾種： 智能裁剪方法[1-3]、 形變方法[4]、 多操作符方法[5]和Seam Carving方法[6-8]. 智能裁剪方法一般分為基于注意力的和美學(xué)導(dǎo)向， 二者統(tǒng)一目標(biāo)都是基于上下文感知的圖像進(jìn)行裁剪， 但又有區(qū)別. 基于注意力的方法側(cè)重于在裁剪或者調(diào)整大小過程中保留視覺重要區(qū)域， 如自動(dòng)保留注意力百分比方法[3]尋找到注意力和裁剪區(qū)域之間的平衡點(diǎn)； 后者側(cè)重于在眾多任意裁剪的子圖中通過圖像質(zhì)量評(píng)估遴選最具視覺吸引力的候選子圖， 如使用貝葉斯網(wǎng)絡(luò)作為質(zhì)量選擇標(biāo)準(zhǔn)， 以流形嵌入算法核心指導(dǎo)圖像裁剪[2]， 和選擇寬高比下最大尺寸且最大顯著性得分的子圖的內(nèi)容保留裁剪(content-persistent thumbnail cropping)方法[1]. 基于形變的方法一般使用一個(gè)三角形或四邊形網(wǎng)格對(duì)圖像進(jìn)行分區(qū)， 通過調(diào)整翹曲圖頂點(diǎn)坐標(biāo)來實(shí)現(xiàn)重定圖像. 如使用貝爾特拉米表示(Beltrami representation)作為翹曲圖[4]維持形變過程的幾何形狀, 然后利用雙射翹曲將翹曲圖映射到重定向目標(biāo). 多操作符方法重定向效果往往比單一操作更好， 如結(jié)合縫刻、 裁剪、 形變和縮放四種重定向算子， 使用尺度不變特征變換(SIFT)流和結(jié)構(gòu)相似度(SSIM)進(jìn)行原始圖像和重定向圖像的對(duì)應(yīng)密集和相似度估計(jì)， 利用視覺顯著性加權(quán)相似度估計(jì)結(jié)果確定迭代算子[5]. Seam Carving(下稱“SC”)圖像調(diào)整技術(shù)或稱接縫雕刻[6]， 其算法比前面提到的方法都簡單且具有不錯(cuò)的重定向性能. 這類方法一般通過原圖啟發(fā)式得到代表像素重要程度的能量圖， 根據(jù)能量圖進(jìn)行反復(fù)裁剪水平或者豎直方向能量最小細(xì)縫. 但由于能量圖僅檢測到圖像的邊緣信息， 裁剪的細(xì)縫不可避免穿過重要主體對(duì)象. 近年來不斷有其他研究者提出改進(jìn)， 如使用原始的梯度圖融合GBVS模型(graph-based visual saliency, GBVS)產(chǎn)生的顯著度圖[7]， 通過線性加權(quán)和相乘兩種方式得到兩種不同功能的能量圖； 更有利用融合了顯著性和HVS邊緣映射[8]， 將平面圖像重定向擴(kuò)展到立體圖像重定向也取得不錯(cuò)的效果.

綜上所述， 關(guān)于SC算法， 如何得到包含邊緣和保護(hù)主體的重定向成為一個(gè)共同關(guān)注的問題， 本研究提出對(duì)應(yīng)于上述研究問題的雙向接縫剪裁的重定向方法. 首先， 使用融合梯度和顯著圖提出一種新型能量圖； 其次， 提出了SC裁剪策略的改進(jìn)方法； 最后， 進(jìn)行多組多方法對(duì)比實(shí)驗(yàn)并采用SIFT Flow指標(biāo)對(duì)其質(zhì)量進(jìn)行分析和評(píng)價(jià).

2 圖像重定向改進(jìn)算法

SC是一種非均勻的圖像大小調(diào)整方法， 也是一種內(nèi)容感知的圖像重定向方法. 根據(jù)能量圖檢測出原圖中不重要區(qū)域， 然后在某一維度貪心的刪除或插入能量最小的細(xì)縫. 算法定義能量圖為表示像素重要程度的梯度圖， 定義裁剪縫為圖像中的一條縱向或橫向連續(xù)路徑， 自頂向下的路徑每一行只經(jīng)過一個(gè)像素點(diǎn)， 從左到右的路徑每一列只經(jīng)過一個(gè)像素點(diǎn). 以搜索最小能量縱向裁剪縫為例， 從第一行開始， 向左下、 正下、 右下方尋找路徑并累計(jì)能量. 這樣利用動(dòng)態(tài)規(guī)劃搜索出能量圖的最小代價(jià)路徑稱為“細(xì)縫”.

而后注意到細(xì)縫移除時(shí)會(huì)伴隨新的能量插入， 即當(dāng)前像素及其左上、 正上和右上像素分別作為細(xì)縫像素移除后， 周邊像素由不相鄰變?yōu)橄噜彛?則新相鄰像素之間的差值作為額外的移除代價(jià)， 如下式所示：

(1)

于是進(jìn)一步提出向前能量法則的改進(jìn)， 改進(jìn)了能量函數(shù)為能量值e(i,j)、 能量累計(jì)值C(i,j)、 移除代價(jià)公式(1)三方面總和的最小值， 表示為以下公式：

(2)

圖1 算法框架流程圖

雖然SC在重定向方面具有不錯(cuò)的效果， 但仍存在兩方面問題： 1) 使用梯度能量圖僅僅檢測到圖像的邊緣信息， 容易造成圖像中顯著物體形狀結(jié)構(gòu)被破壞和重要內(nèi)容缺失的現(xiàn)象. 2) 圖像縮放比率較大且分布均勻的信息在裁剪方向上消耗完時(shí)， 裁剪的細(xì)縫不僅會(huì)穿過感興趣區(qū)域(region of interest, ROI)使圖像發(fā)生扭曲， 而且ROI區(qū)域與全局之間的布局關(guān)系受到破壞.

本研究以SC算法為研究對(duì)象， 針對(duì)以上兩個(gè)問題， 首先提出了融合邊緣梯度和內(nèi)容顯著性的能量圖， 其次基于能量圖又提出了雙向裁剪方法重定向方法. 框架流程如圖1所示， 首先使用原圖自適應(yīng)生成梯度圖和顯著圖， 二者線性融合得到能量圖； 然后， 使用動(dòng)態(tài)規(guī)劃方法對(duì)能量圖進(jìn)行水平和豎直兩個(gè)方向上搜索最小能量細(xì)縫， 根據(jù)原圖和目標(biāo)圖之間的尺寸關(guān)系， 交替插入/刪除豎直/水平細(xì)縫； 最后， 得到微調(diào)的圖像， 以之取代原圖， 反復(fù)迭代前面操作達(dá)到目標(biāo)尺寸.

2.1 構(gòu)造新的能量圖

近年視覺性、 顯著性逐漸受到許多國內(nèi)外研究者的關(guān)注， 通常圖像在沒有給出其他注意力信息的情況下， 人類視覺水平的顯著性作為重要圖的依據(jù)具有重要意義. SC的梯度圖認(rèn)為圖像邊緣部分是相對(duì)比較重要的， 但對(duì)于一些多紋理為背景的圖像中， 這種方法常常會(huì)喪失前景主體的重要保留. 本研究方法認(rèn)可傳統(tǒng)方法邊緣檢測的必要性， 但同時(shí)額外融合了表征重要對(duì)象邊界和主體的顯著圖， 希望通過產(chǎn)生新能量圖對(duì)SC算法效果起到較好的提升.

文獻(xiàn)[9]提出的全分辨率頻率調(diào)制算法(稱FT法)， 能夠高效簡潔地檢測顯著性對(duì)象清晰邊界. 文獻(xiàn)[10]提出的快速光柵掃描顯著性檢測算法(稱MB法), 這是一種近似最小障礙距離變換的算法， 對(duì)圖像像素波動(dòng)具有很好的魯棒性， 且能夠捕獲圖像邊界關(guān)聯(lián)線索從而保留重要內(nèi)容. 通過線性融合FT顯著圖、 MB顯著圖及梯度圖并歸一化進(jìn)而構(gòu)造出一種新型能量圖.

梯度法定義為表示圖像像素的能量值為x方向和y方向上的梯度絕對(duì)值的和， 即下式中e(i,j)對(duì)應(yīng)的是圖像中(i,j)位置像素的能量值. 圖像對(duì)應(yīng)的高能量像素點(diǎn)， 說明該像素點(diǎn)是需要保留的高能量像素值， 對(duì)圖像重要性越大， 反之低能量像素值， 保留的意義較弱， 對(duì)圖像重要性越小.

(3)

FT顯著性檢測是在顏色空間(lab color space, LAB)下， 利用顏色特征的中央-周邊算子來得到顯著圖， 此算法簡單、 高效而且可以生成全分辨率高質(zhì)量的顯著圖. 首先， 將輸入圖像I經(jīng)過高斯濾波得到Ihc， 并將圖像由RGB顏色空間轉(zhuǎn)換為LAB顏色空間， 取其三通道均值為Iave(lm, am, bm)； 然后， 利用均值Iave(lm, am, bm)對(duì)圖Ihc每個(gè)像素計(jì)算歐式距離得到S(x,y)(見下式)； 最后， 對(duì)S進(jìn)行最大值歸一化， 即得FT顯著圖.

S(x,y)=|Iave-Ihc(x,y)|

(4)

MB顯著性檢測以最小障礙距離路徑代價(jià)計(jì)算像素顏色距離， 然后利用快速光柵掃描的迭代方式獲得顯著圖. 首先， 采用Minimum Barrier Distance(MBD)作為路徑代價(jià)函數(shù)， 選取圖像的邊界像素作為背景種子； 然后， 通過FastMBD計(jì)算圖像每個(gè)顏色通道的各個(gè)像素和背景種子像素的MBD距離圖； 最后， 所有通道累加， 再進(jìn)行最大值歸一化， 即得MB顯著圖.

如圖2所示， 使用256階灰度圖作為能量圖. 256階灰度圖最亮為255， 最暗為0， 將最亮與最暗之間的亮度變化劃分為256份. 像素灰階是0～255中任意數(shù)值， 表示對(duì)應(yīng)像素的重要性， 像素能量越高， 像素灰階數(shù)值越大， 對(duì)應(yīng)能量圖越亮. 使用圖2(a)梯度法檢測出了表征邊緣重要度的梯度圖Sgrad， 圖2(b)中FT算法檢測出了表示重要對(duì)象邊界的顯著圖Sft， 圖2(c)中MB算法檢測出了表示重要對(duì)象內(nèi)容的顯著圖Smb， 對(duì)這三種重要性圖使用下式進(jìn)行線性融合, 然后歸一化得到一種新的能量圖Senery(見圖2(d)). 通過實(shí)驗(yàn)表明， 線性融合的參數(shù)α,β,θ分別控制在0.9～1.1， 0～0.3， 0～0.2之間生成的能量圖重定向效果性能較好. 本研究第三部分實(shí)驗(yàn)采用的參數(shù)為α=1,β=0.25,θ=0.16.

Senery=αSgrad+βSft+θSmb

(5)

(a) 梯度圖

2.2 融合顯著性的雙接縫裁剪

本研究提出結(jié)合了裁剪和擴(kuò)增的雙向接縫裁剪方法， 根據(jù)圖像重定向的目標(biāo)比例采取適當(dāng)?shù)牟呗詫?duì)水平和豎直兩個(gè)方向進(jìn)行裁剪和插入像素. 具體做法： 使用上面介紹新型能量圖， 根據(jù)能量圖動(dòng)態(tài)規(guī)劃搜索水平和垂直兩個(gè)方向的最小能量細(xì)縫， 對(duì)于寬高比縮小的一邊使用細(xì)縫裁剪， 對(duì)于寬高比擴(kuò)張的一邊使用進(jìn)行細(xì)縫插入， 目的是使得圖像重定向取得較好效果的同時(shí)盡可能保留重要內(nèi)容的布局.

2.2.1結(jié)合鄰近相似的像素?cái)U(kuò)增法

圖3 結(jié)合鄰近相似的像素?cái)U(kuò)增法

重定向方法涉及到圖像擴(kuò)增插入細(xì)縫， 除了找出插入位置還要選取合適的插入像素值， 然后再移動(dòng)像素， 基于以上因素提出了結(jié)合鄰近相似的像素?cái)U(kuò)增法. 以插入豎直細(xì)縫為例(見圖3)， 圖左側(cè)是能量圖使用動(dòng)態(tài)規(guī)劃查找最小路徑細(xì)縫后， 進(jìn)行圖像邊緣相似填充； 圖中間是細(xì)縫像素a0為中心的3×3的區(qū)域， 選擇周邊8個(gè)像素與之最相似的像素作為擴(kuò)增像素值a8(見下式)； 圖右側(cè)是擴(kuò)增像素pi(a8=pi)在細(xì)縫像素p2(a0=p2)右側(cè)進(jìn)行插入， 其余像素依次向右移動(dòng)一個(gè)像素單位.

(6)

另外, 對(duì)于圖像的非重要邊緣, 如大面積的天空、 草地、 海洋， 這類同質(zhì)性紋理具有一般重復(fù)性, 本文提出使用對(duì)稱仿制對(duì)同質(zhì)背景進(jìn)行像素?cái)U(kuò)增, 以避免過度細(xì)縫剪裁的問題及大幅實(shí)失真的現(xiàn)象. 即取原圖四周N行/列像素作為仿制原子, 增加的N列行像素與仿制原子互為對(duì)稱.

2.2.2改進(jìn)算法的設(shè)計(jì)與整合

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

實(shí)驗(yàn)使用MIT RetargetMe數(shù)據(jù)集， 采用五種方法與本研究方法進(jìn)行實(shí)驗(yàn)對(duì)比： 人工剪裁(CR)、 均勻縮放(SCL)、 Multi Operator(MULTIOP)[11]、 Scale and Stretch(SNS)[12]、 Seam Carving(SC)[6]. 同時(shí)， 設(shè)定了4∶3、 2∶1、 3∶4、 1∶2四種不同寬度的縮放比例實(shí)驗(yàn)， 通過分別進(jìn)行這四種比例的五種方法圖像重定向的對(duì)比實(shí)驗(yàn)來驗(yàn)證本研究提出方法有效性.

3.1 定量分析

為了對(duì)重定向方法的性能進(jìn)行客觀的檢測， 采用SIFT Flow[13]作為本研究提出的重定向方法效果的衡量指標(biāo). SIFT Flow質(zhì)量評(píng)價(jià)標(biāo)準(zhǔn)能有效地衡量重定向圖像較原始圖像的形狀信息的變化， 在兩幅圖中進(jìn)行稠密的特征采樣， 找到所有像素點(diǎn)相似處的位移差； 位移差越大， 兩個(gè)圖像重要物體之間的形變距離越大, 重定向圖像中的顯著物體較原圖扭曲失真越嚴(yán)重. 隨機(jī)選取幾組對(duì)比實(shí)驗(yàn)進(jìn)行SIFT Flow質(zhì)量測評(píng)， 從表1的質(zhì)量評(píng)價(jià)數(shù)據(jù)來看， 相對(duì)于其他的重定向方法， 本研究方法較其他方法在客觀指標(biāo)上均取得最小值， 也就是圖像重定向前后形狀信息變化和扭曲失真程度都比其他方法小.

表1 SIFT Flow評(píng)價(jià)指標(biāo)下其他重定向方法與本研究方法的對(duì)比

3.2 定性分析

(a) Original (b) CR (c) SCL (d) MULTIOP (e) SNS (f) SC (g) Ours

(a) Original (b) CR (c) SCL (d) MULTIOP (e) SNS (f) SC (g) Ours

前面兩組都是對(duì)于圖像寬度縮小的情況， 后面兩組是圖像寬度擴(kuò)增. 如圖6所示， 第三組是重定向目標(biāo)寬為原來的4/3倍(圖6(a))， 第四組是重定向目標(biāo)為原來的2倍(圖6(b)). 觀察第三、 四組圖像的威尼斯小船和天婦羅碗碟， 對(duì)比其他重定向方法的結(jié)果及結(jié)合前面幾組對(duì)比實(shí)驗(yàn)， 可以得出本研究方法都較好地維持原本形狀及主體對(duì)象在圖像中的布局.

(a) Original (b) CR (c) SCL (d) MULTIOP (e) SNS (f) SC (g) Ours

3.3 與原算法復(fù)雜度對(duì)比分析

4 結(jié)語

本研究提出一種雙向接縫裁剪的圖像重定向改進(jìn)方法， 結(jié)合梯度圖和顯著圖構(gòu)造了一種新型能量圖， 基于提出的新能量圖， 又對(duì)傳統(tǒng)的方法單向過度裁剪造成的問題提出了雙向裁剪接縫的改進(jìn). 在當(dāng)前廣泛使用于重定向領(lǐng)域的公開數(shù)據(jù)集MIT RetargetMe中， 進(jìn)行了多組多種方法對(duì)比實(shí)驗(yàn)， 實(shí)驗(yàn)結(jié)果表明該方法相對(duì)具有優(yōu)越性. 所提的改進(jìn)方法適應(yīng)于不同比例尺寸圖像重定向， 符合人眼視覺中心原則， 在突出重要對(duì)象主體和保護(hù)重要邊緣信息的同時(shí)， 調(diào)整了重要內(nèi)容在圖像整體中的布局.