基于主體區域保持的圖像縮放算法

鄒盼盼， 陸　平， 朱恒亮， 董振江，賈　霞， 林　曉,4， 馬利莊

(1. 上海交通大學電子信息與電氣工程學院數字媒體與數據重建實驗室，上海 200240；2. 東南大學信息科學與工程學院，江蘇 南京 210000；3. 中興通訊股份有限公司云計算及IT研究院，江蘇 南京210000) 4. 洛陽師范學院信息技術學院，河南 洛陽 471022)

基于主體區域保持的圖像縮放算法

鄒盼盼1， 陸平2,3， 朱恒亮1， 董振江3，賈霞3， 林曉1,4， 馬利莊1

(1. 上海交通大學電子信息與電氣工程學院數字媒體與數據重建實驗室，上海 200240；2. 東南大學信息科學與工程學院，江蘇 南京 210000；3. 中興通訊股份有限公司云計算及IT研究院，江蘇 南京210000) 4. 洛陽師范學院信息技術學院，河南 洛陽 471022)

基于插值運算的縮放算法和經典的縫裁剪算法是兩種常用的圖像縮放算法，傳統的縮放算法在縮放比例不一致的情況下其效果不佳，而縫裁剪算法在主體區域較大或者圖像背景較為復雜時對圖像的主體區域會造成一定破壞。針對以上問題，提出了一種基于主體區域保持的圖像縮放算法，使用高斯差分對圖像進行角點檢測，利用角點產生凸包，根據凸包對圖像進行主體區域檢測，計算能量圖并對位于主體區域像素點的能量給予相應的權重，根據權重的不同對主體區域進行不同程度的保護。實驗結果表明，該算法能更好地保持圖像主體區域。

縫裁剪；主體區域；角點檢測；圖像縮放；凸包

目前，隨著電子產品更新換代的速度越來越快，特別是智能手機等移動設備的出現，加速了信息的傳遞。在信息傳遞中，圖像信息尤為重要，為此就需要在不同的顯示設備上顯示圖像。由于不同的顯示設備有不同的長寬比，因此如果要在不同的顯示設備上顯示同一幅圖像，就需要對圖像進行相應的縮放處理。為此，研究人員從不同的方面提出了不同的方法[1-2]。

傳統的圖像縮放算法是基于差值核函數的縮放算法，其通過對圖像使用最近鄰插值、雙線性插值或雙三次插值等技術來改變圖像大小[3-4]，該算法對于長寬比相同的圖像縮放時效果很好，但是如果目標圖像與原圖像的長寬比不一致，則會使圖像中的主體區域產生拉伸或壓扁，從而導致圖像產生畸變，影響圖像的視覺效果。對比圖1(a)和圖1(b)可看出，傳統的縮放算法影響了圖像的視覺效果。

由于傳統的縮放算法不能很好保持圖像主體區域的視覺效果，為了解決此問題，研究者們提出了許多方法，其中比較有影響力的是 Avidan和Shamir[5]在2007的SiggGraph會議上提出的縫裁剪(seam carving)算法。如圖1(c)所示，縫裁剪算法相對于傳統的縮放算法可以更好地保持圖像的主體區域，但是這種方法在圖像中的主體區域比較大或主體區域的顏色與環境的顏色對比不明顯時，會產生讓人不滿意的效果。圖2中縫裁剪算法裁剪了方框中小男孩的腳，圖3縫裁剪算法對方框中船體和桅桿進行了裁剪。從圖2和圖3可看出縫裁剪算法影響了圖像主體區域的視覺效果。

因為縫裁剪算法可以比較好地保持圖像的主體區域，所以其適用范圍很廣，又因為縫裁剪算法存在一些不足，研究者們提出了不同改進的算法。Yan等[6]提出了基于區域匹配的縫裁剪算法并將該算法用于視頻縮放；Yue等[7]改進了縫裁剪算法，使得縫裁剪算法可以用于立體圖像的縮放；Frankovich和 Wong[8]提出了通過集成能量梯度函數來改進縫裁剪算法。

Dong等[9]提出了一種將縫裁剪算法和傳統的縮放算法結合起來對圖像進行縮放的方法，該算法可以有效地利用縫裁剪算法和傳統縮放算法的優點。Luo等[10]提出了將直接和間接的縫裁剪算法結合起來的自動圖像縮放算法，使得圖像在縮放過程中可以自動地選擇使用縮放方法，在不需要人為干預的情況下達到理想的縮放效果。

基于上述內容的分析，本文提出了一種新的基于主體區域保持的圖像縮放算法，該算法可以在圖像的主體區域比較大或主體區域與背景顏色對比不明顯的情況下得到較好的效果。

圖1　傳統縮放算法和縫裁剪算法的比較

圖2　線裁剪算法的縮放效果1

圖3　線裁剪算法的縮放效果2

1　相關工作

1.1縫裁剪算法

縫裁剪算法通過插入或者刪除縫對圖像進行縮放，其核心是每次找到一條能量最小的垂直縫，通過刪除該縫使圖像縮小一個像素，或者通過添加一條縫使圖像放大一個像素。如果要在水平方向進行縮放，則在水平方向上找一條能量最小的縫，然后對該縫進行相應的操作；如果要在垂直方向進行縮放，則在垂直方向上找到一條能量最小的縫，然后對該縫進行相應的操作。

因為在縫裁剪算法中需要保護圖像中視覺重要信息，而重要區域中像素的顏色值變化比較大，所以Avidan和Shamir[5]將像素能量定義為：

通過x和y方向梯度值的絕對值之和表示該點的能量。圖像I的垂直裁剪縫的定義為：

其中，x是一個映射x:[1,…, n]→[1,…,m]，即一條垂直的裁剪縫是一條從上到下能量最小的像素組成的8連通路徑。類似的，圖像I的水平裁剪縫定義為：

對于給定的能量函數e，定義一條裁剪縫代價為：

要找一條代價最小的裁剪縫，定義s*為代價最小的裁剪縫，則：

對圖像I用動態規劃算法求解代價最小的一條裁剪縫。以垂直裁剪縫為例，求解步驟如下：

(1) 利用式(1)計算每個(i, j)點處的能量，得到梯度矩陣MG。

(2) 從 MG第二行的第一個像素點開始從左到右，從上到下計算圖像中每點的能量值，直到計算出所有點的能量值。圖像中(i, j)處的像素點的能量表示為M(i, j)，則：其中，e(i, j)是式(1)得到像素點(i, j)的梯度值，遍歷完整幅圖像之后得到圖像的能量矩陣ME。

(3) 根據得到的能量矩陣ME，在最后一行找到能量值最小的像素點，然后從該像素點向上回溯并記錄回溯經過的每個像素點，直到回溯到第一行。其記錄下來的像素點組成的一條縫就是代價最小的一條裁剪縫s*。

(4) 如果要將圖像縮小，則刪除s*即可；如果要放大圖像，則復制s*得到，然后將插入s*旁邊即可。

1.2角點檢測與高斯差分

角點作為表征圖像局部特征的一個重要因素，其集中體現了圖像的很多重要形狀信息。角點不僅具有旋轉不變性，而且也幾乎不受光照條件的影響。在圖像的數據信息沒有被破壞的情況下，角點是圖像最小化處理的數據量。由于角點具有以上的性質，所以角點檢測具有很強的實用性，近年來也得到了越來越多的研究者重視。

關于如何定義角點目前還沒有達成共識，但是研究者一般認為：角點是圖像當中梯度變化最大的點。為了檢測圖像的角點，研究者們提出了許多方法。Song等[11]認為圖像中的噪聲嚴重的影響了角點檢測的性能且噪聲很難消除，針對這個問題提出了一種基于噪聲差異級別的角點檢測方法，該算法可以根據圖像的信噪比自適應的設定閾值以過濾假的角點；Ramakrishnan等[12]認為廣泛使用的ShiTomasi和Harris角點檢測方法需要手動的設定參數閾值，為此提出了一種基于迭代剪枝的策略改進了ShiTomasi和Harris的角點檢測算法；何中翔等[13]改進了一種基于Harris角點檢測算法的亞像素級角點檢測算法。而本文采用的角點檢測算法是基于高斯差分(difference of Gaussian, DOG)的。

對于二維圖像I(x,y)，其尺度空間L( x, y,σ)，由該圖像與高斯核G( x, y,σ)卷積得到：

其中，高斯核中的方差σ是尺度因子，決定著圖像被平滑的程度，連續改變σ就能構造圖像的高斯金字塔。DOG空間D( x, y,σ) 是高斯金字塔中相鄰尺度空間函數之差，即：其中，k表示相鄰尺度空間的尺度比例系數。不同的k值可以得到不同的DOG空間，所有的DOG空間就構成了DOG金字塔，然后檢測金字塔中間層(最高層和最底層除外)中每個像素點，如果一個像素點比相鄰的像素點的值都大或者都小，那么該點就是一個局部極值點，則將該點作為候選特征點，也就是角點。本文算法綜合考慮了算法的效果和時間復雜性，決定取3個不同的k值，這樣可以取得較好的效果和較快的速度。

2　圖像主體區域檢測

常用的圖像主體區域檢測算法主要是基于圖像的顯著性，一般認為圖像的顯著性圖顯示的區域即為圖像的主體區域[14]，但目前常用的求顯著性的算法計算量都比較大。另外一種求圖像主體區域的算法是基于角點檢測和凸包算法，由于圖像的角點很少，所以該算法處理速度很快。

角點可以表現圖像的局部特征，并且具有旋轉不變性，幾乎不受環境光照的影響，而且角點的數量一般比較少，處理速度相對較快，所以可通過角點構成的區域來表示圖像的主體區域。

由于圖像中角點比較少，所以本文決定采用Graham掃描算法[15]來求角點的凸包。Graham掃描算法首先需找到最小y軸坐標點，然后按照其他點和該點的連線與x軸的夾角角度值排序，通過判斷相鄰頂點的空間位置關系，從而得到逆時針排序的凸包頂點，其時間復雜度為n log2(n)，n表示頂點的數量。由于原始的Graham掃描算法在點集比較密集時效率會受到影響，吳文周等[16]對原始的Graham掃描算法進行了改進。具體的改進算法過程請參考文獻[16]。

3　本文算法

3.1算法目的

本文提出了一種新的基于主體區域保持的圖像縮放算法，具有比較快的速度，且比縫裁剪算法和傳統的縮放算法能夠更好地保持圖像的主體區域。在圖像中的主體區域較大或主體區域與背景的對比度不明顯的情況下，也可以取得較好的效果。

3.2算法的步驟

本文算法使用DOG對圖像進行角點檢測，對角點使用凸包算法找出圖像中的主體區域，再利用式(1)計算出圖像的能量圖，對能量圖中位于主體區域的點進行加權處理，得到新的能量圖，然后在新的能量圖上使用縫裁剪算法對圖像進行縮放。

算法主要分以下5步：

(1) 求出圖像的 DOG圖。在等式(9)中選擇 3個不同的尺度比例系數，如圖4所示，本文中選用的k值分別為0.750、0.857和0.875，得到3張不同的DOG圖。

(2) 根據步驟(1)中得到的3張DOG圖，找出中間的DOG圖中每一個像素是否為極值點。判斷像素點是否為極值點的方法：如圖 5(a)、(b)和(c)分別表示DOG空間的第1、2和3層，其中圖5(b)為中間層。要判斷其中間的(i, j)是否為極值點，則將中間點與其他的 26個黑色的點比較，如果中間點的值是這27個點中最大的或最小的，則(i, j)為極值點，由這些極值點組成的圖為原圖的角點圖。圖6(b)為圖6(a)的角點圖。

(3) 使用Graham掃描算法求角點圖的凸包，得到的凸包區域即為圖像的主體區域。圖6(c)所示即為由圖6(b)的角點求得的凸包圖。

(4) 利用式(10)求圖像的初始梯度值圖Einit，再對位于凸包內的像素點賦予權重，得到新的權重梯度值圖Enew，本文算法的梯度值圖Eours為初始梯度值圖Einit和新的權重梯度圖Enew的疊加。計算公式如下：

其中，式(10)中e(i,j)是根據式(1)得到的(i,j)處的梯度值，Einit(i, j)表示(i,j)處初始的梯度值；式(11) 中 w表示權重系數，I表示圖像，H表示凸包；式(12)中Eours(i, j)表示本文算法得到的梯度值圖。不同的權重將會對主體區域進行不同程度的保護。例如圖7(b)中為初始梯度值圖Einit，圖7(c)為新的權重梯度圖Eours。根據圖像的不同選擇最適合的權重，對主體區域不足和過度保護都會對縮放后的圖像造成不良影響。

(5) 在本文算法得到的梯度值圖Eours上使用動態規劃算法得到新的能量圖Mours，在Mours上使用縫裁剪算法對圖像進行縮放。

圖4　3種不同比例系數的高斯差分圖

圖5　判斷極值點示意圖

圖6　本文算法得到的角點圖、凸包圖

圖7　本文算法的初始梯度值和加權后的梯度值

4　實驗結果

本文實驗硬件平臺為一臺2.40 GHz, 4 GB內存的計算機，軟件平臺為MATLAB R2013a。本文將從主體區域的保持程度、本文算法與常用縮放算法的對比和本文算法的特點3個方面進行實驗。

4.1主體區域保持

由于本文算法對圖像的主體區域進行了加權保護，通過對位于主體區域和非主體區域的像素點給予不同的權重可實現不同程度的保護。相對于縫裁剪算法，本文算法在裁剪過程中可以更好地保持圖像的主體區域。

圖7(b)是本文算法得到的初始能量圖，圖7(c)是本文算法得到加權后的權重能量圖，圖7將式(11)中的權重值w設為5。通過對比2種算法得到的能量圖，可以看到因本文算法對圖像的主體區域進行了加權，所以得到的能量圖更加突出圖像的主體區域，可以更好地保持圖像的主體區域。

縫裁剪算法將圖像壓縮到一定程度的時候，由于背景區域被反復裁剪從而形成了折橫，導致背景區域的能量變大，使得裁剪縫可能穿過圖像的主體區域，從而損壞了圖像的主體區域。圖8(a)、(c)中采用的縫裁剪算法得到的裁剪縫均通過圖像的主體區域，采用本文算法得到圖8(b)、(d)的裁剪縫則避開了圖像的主體區域。由此可看出本文算法可以更好地保持圖像的主體區域。

4.2常用的縮放算法的比較

從圖 9的實驗結果看出本文算法可以更好地保持圖像的主體區域，而且在盡可能的保證主體區域內容完整性的情況下，取得了比較好的視覺效果。由于傳統的縮放算法在非等比例縮放的情況下會對圖像中的內容進行壓扁或者拉伸，所以影響縮放后圖像的視覺效果。縫裁剪算法可以保持圖像的主體區域，但是在某些情況下，特別是主體區域較大或者主體區域與背景對比度不明顯時，容易對主體區域造成破壞。比如圖9中海豚的尾巴、車窗的頂部、船上的桅桿和汽車左邊緣都被裁剪了，可見縫裁剪算法均沒有取得比較理想的效果，而本文算法則相對較好保持圖像的主體區域，取得了比較好的效果。

圖8　縫裁剪算法與本文算法在保持圖像主體區域的比較

圖9　傳統的縮放算法、縫裁剪算法和本文算法的比較

4.3本文算法的特點

由于在圖像縮放過程中每行或每列需要裁剪掉的像素數量是一定的，因此如果對圖像的主體區域進行了加權保護，就會對背景區域過多裁剪。從一方面來說這可以更好地保持圖像的主體區域；從另一方面來說本文算法相對于縫裁剪算法對背景區域的裁剪更多。如圖9中的第二排圖片所示，由于本文方法對車所在的區域進行了加權保護，所以車保存的比較完整，但是圖片右上角的公路卻比縫裁剪算法變形嚴重。因此對于主體區域的保護程度的取舍很重要，式(11)中不同的w值，會對主體區域進行不同程度的加權，從而對主體區域進行不同程度的保護。w值越大對主體區域的保護越強，更傾向于裁剪背景區域；反之，w值越小對主體區域的保護越小。

5　結論與展望

本文提出了一種新的基于主體區域保持的圖像縮放算法，通過對圖像使用DOG進行角點檢測，然后利用角點通過Graham算法求凸包，凸包所在的區域即為圖像的主體區域；在計算圖像能量圖時先計算初始的能量圖，再對位于凸包內的像素點的能量加權得到新的加權能量圖，然后將初始能量圖和加權能量圖疊加得到新的能量圖，最后在新的能量圖上采用縫裁剪算法對圖像進行縮放。實驗結果表明，本文對圖像的主體區域進行了加權保護，可以更好地保持圖像的主體區域。

本文算法也存在一定的局限性，如果圖像中存在多個主體，根據角點檢測得到的凸包必然會包含所有的主體區域，在某些情況下會將大量的非主體區域包含進來，從而保護了圖像中的非主體區域，這將破壞圖像縮放后的幾何結構。如果圖像的主體背景較復雜，則本文算法也會遇到與顯著性算法相同的問題：無法準確有效地檢測出圖像的主體區域，從而無法為主體區域提供準確有效地保護，進而導致縮放效果不佳。

本文算法在給主體區域和非主體區域所使用的權重是手動指定的，根據圖片縮放要求的不同需要指定不同的權重來達到最好的縮放效果。這顯然不能滿足處理批量圖片的要求，為了處理批量圖片需要根據圖片的不同自適應的指定權重，如何自適應指定權重是今后研究的重點。

[1] 施美玲, 徐丹, 內容感知圖像縮放技術綜述[J]. 中國圖象圖形學報, 2012, 17(2): 157-168.

[2] 施美玲, 徐丹, 錢志明. 基于成對比較的內容感知圖像縮放效果主觀評估[J]. 計算機輔助設計與圖形學學報, 2013, 25(10): 1503-1513.

[3] 楊云峰, 蘇志勛, 胡金燕. 一種保持邊緣特征的圖像插值方法[J]. 中國圖象圖形學報, 2005, 10(10): 1248-1251.

[4] van Ouwerkerk J D. Image super-resolution survey [J]. Image and Vision Computing, 2006, 24(10): 1039-1052.

[5] Avidan S, Shamir A. Seam carving for content-aware image resizing [J]. ACM Transactions on Graphics, 2007, 26(3): 10: 1-9.

[6] Yan B, Sun Kairan, Liu L. Match-area-based seam carving for video retargeting [J]. IEEE Transactions on Circuits and Systems for Video Technology, 2013, 23(2): 302-310.

[7] Yue B, Hou C P, Zhou Y. Improved seam carving for stereo image resizing [J]. EURASIP Journal on Wireless Communications and Networking, 2013, 2013(1): 1-6.

[8] Frankovich M, Wong A. Enhanced seam carving via integration of energy gradient functionals [J]. IEEE Signal Processing Letters, 2011, 18(6): 375-378.

[9] Dong W M, Zhou N, Paul J C, et al. Optimized image resizing using seam carving and scaling [J]. ACM Transactions on Graphics, 2009, 8(5): 125: 1-10.

[10] Luo S Q, Zhang J P, Zhang Q, et al. Multi-operator image retargeting with automatic integration of direct and indirect seam carving [J]. Image and Vision Computing, 2012, 30(9): 655-667.

[11] Song Y, Shen Y P, Li S X, et al. Corner detection in images under different noise levels [C]//Pattern Recognition (ICPR), 2014 22nd International Conference on. Stockholm, New York: IEEE Press, 2014: 906-911.

[12] Ramakrishnan N, Wu M Q, Lam S K, et al. Automated thresholding for low-complexity corner detection [C]// Adaptive Hardware and Systems (AHS). New York: IEEE Press, 2014: 97-103.

[13] 何中翔, 王明富, 楊世洪, 等. 遙感圖像客觀質量評價方法研究[J]. 圖學學報, 2011, 32(6): 47-52.

[14] Fang Y M, Chen Z Z, Lin W S, et al. Saliency detection in the compressed domain for adaptive image retargeting [J]. IEEE Transactions on Image Processing (TIP), 2012, 21(9): 3888-3901.

[15] Graham R L. An efficient algorithm for determine the convex hull of a finite planar set [J]. Information Processing Letters, 1972, 1(4): 132-133.

[16] 吳文周, 李利番, 王結臣. 平面點集凸包Graham算法的改進[J]. 測繪科學, 2010, 35(6): 123-125.

An Novel Image Resizing Method Based on Im portant Area Maintain

Zou Panpan1,Lu Ping2,3,Zhu Hengliang1,Dong Zhenjiang3,Jia Xia3,Lin Xiao1,4,Ma Lizhuang1

(1. School of Electronic Information and Electrical Engineering, Shanghai Jiao Tong University, Shanghai 200240, China; 2. School of Information Science and Engineering, Southeast University, Nanjing Jiangsu 210000, China; 3. Cloud Computing and IT Institute of ZTE Corporation, Nanjing Jiangsu 210000, China; 4. Academy of Information Technology, Luoyang Normal University, Luoyang Henan 471022, China)

Scaling and seam carving are commonly used algorithm in image resizing, but scaling is not suitable for the case that the resize ratio is not uniformity, seam carving will also has a bad effect on important area in some cases. In this paper we proposed a novel algorithm which is based on important region maintain. Firstly, we make a corner detection based on difference of Gaussian, then Graham-scan algorithm is applied to do an important region detection, after that we will add different weights between important region and unimportant region. The experimental result shows our method is better than other image resizing algorithms in maintaining the important area.

seam carving; important area; corner detection; image resizing; convex hull

TP 391.41

10.11996/JG.j.2095-302X.2016020230

A

2095-302X(2016)02-0230-07

2015-09-24；定稿日期：2015-10-01

國家自然科學基金項目(U1304616, 61133009, 61502220)；國家“973”重點基礎研究發展規劃項目(2011CB302200)

鄒盼盼(1989–)，男，湖北黃岡人，碩士研究生。主要研究方向為圖像視頻處理。E-mail：zou_pp@163.com

馬利莊(1963–)，男，浙江余姚人，教授，博士，博士生導師。主要研究方向為計算機圖形學、數字媒體等。E-mail：ma-lz@cs.sjtu.edu.cn