鄒盼盼, 陸 平, 朱恒亮, 董振江,賈 霞, 林 曉,4, 馬利莊
(1. 上海交通大學(xué)電子信息與電氣工程學(xué)院數(shù)字媒體與數(shù)據(jù)重建實驗室,上海 200240;2. 東南大學(xué)信息科學(xué)與工程學(xué)院,江蘇 南京 210000;3. 中興通訊股份有限公司云計算及IT研究院,江蘇 南京210000) 4. 洛陽師范學(xué)院信息技術(shù)學(xué)院,河南 洛陽 471022)
基于主體區(qū)域保持的圖像縮放算法
鄒盼盼1, 陸平2,3, 朱恒亮1, 董振江3,賈霞3, 林曉1,4, 馬利莊1
(1. 上海交通大學(xué)電子信息與電氣工程學(xué)院數(shù)字媒體與數(shù)據(jù)重建實驗室,上海 200240;2. 東南大學(xué)信息科學(xué)與工程學(xué)院,江蘇 南京 210000;3. 中興通訊股份有限公司云計算及IT研究院,江蘇 南京210000) 4. 洛陽師范學(xué)院信息技術(shù)學(xué)院,河南 洛陽 471022)
基于插值運算的縮放算法和經(jīng)典的縫裁剪算法是兩種常用的圖像縮放算法,傳統(tǒng)的縮放算法在縮放比例不一致的情況下其效果不佳,而縫裁剪算法在主體區(qū)域較大或者圖像背景較為復(fù)雜時對圖像的主體區(qū)域會造成一定破壞。針對以上問題,提出了一種基于主體區(qū)域保持的圖像縮放算法,使用高斯差分對圖像進行角點檢測,利用角點產(chǎn)生凸包,根據(jù)凸包對圖像進行主體區(qū)域檢測,計算能量圖并對位于主體區(qū)域像素點的能量給予相應(yīng)的權(quán)重,根據(jù)權(quán)重的不同對主體區(qū)域進行不同程度的保護。實驗結(jié)果表明,該算法能更好地保持圖像主體區(qū)域。
縫裁剪;主體區(qū)域;角點檢測;圖像縮放;凸包
目前,隨著電子產(chǎn)品更新?lián)Q代的速度越來越快,特別是智能手機等移動設(shè)備的出現(xiàn),加速了信息的傳遞。在信息傳遞中,圖像信息尤為重要,為此就需要在不同的顯示設(shè)備上顯示圖像。由于不同的顯示設(shè)備有不同的長寬比,因此如果要在不同的顯示設(shè)備上顯示同一幅圖像,就需要對圖像進行相應(yīng)的縮放處理。為此,研究人員從不同的方面提出了不同的方法[1-2]。
傳統(tǒng)的圖像縮放算法是基于差值核函數(shù)的縮放算法,其通過對圖像使用最近鄰插值、雙線性插值或雙三次插值等技術(shù)來改變圖像大小[3-4],該算法對于長寬比相同的圖像縮放時效果很好,但是如果目標(biāo)圖像與原圖像的長寬比不一致,則會使圖像中的主體區(qū)域產(chǎn)生拉伸或壓扁,從而導(dǎo)致圖像產(chǎn)生畸變,影響圖像的視覺效果。對比圖1(a)和圖1(b)可看出,傳統(tǒng)的縮放算法影響了圖像的視覺效果。
由于傳統(tǒng)的縮放算法不能很好保持圖像主體區(qū)域的視覺效果,為了解決此問題,研究者們提出了許多方法,其中比較有影響力的是 Avidan和Shamir[5]在2007的SiggGraph會議上提出的縫裁剪(seam carving)算法。如圖1(c)所示,縫裁剪算法相對于傳統(tǒng)的縮放算法可以更好地保持圖像的主體區(qū)域,但是這種方法在圖像中的主體區(qū)域比較大或主體區(qū)域的顏色與環(huán)境的顏色對比不明顯時,會產(chǎn)生讓人不滿意的效果。圖2中縫裁剪算法裁剪了方框中小男孩的腳,圖3縫裁剪算法對方框中船體和桅桿進行了裁剪。從圖2和圖3可看出縫裁剪算法影響了圖像主體區(qū)域的視覺效果。
因為縫裁剪算法可以比較好地保持圖像的主體區(qū)域,所以其適用范圍很廣,又因為縫裁剪算法存在一些不足,研究者們提出了不同改進的算法。Yan等[6]提出了基于區(qū)域匹配的縫裁剪算法并將該算法用于視頻縮放;Yue等[7]改進了縫裁剪算法,使得縫裁剪算法可以用于立體圖像的縮放;Frankovich和 Wong[8]提出了通過集成能量梯度函數(shù)來改進縫裁剪算法。
Dong等[9]提出了一種將縫裁剪算法和傳統(tǒng)的縮放算法結(jié)合起來對圖像進行縮放的方法,該算法可以有效地利用縫裁剪算法和傳統(tǒng)縮放算法的優(yōu)點。Luo等[10]提出了將直接和間接的縫裁剪算法結(jié)合起來的自動圖像縮放算法,使得圖像在縮放過程中可以自動地選擇使用縮放方法,在不需要人為干預(yù)的情況下達(dá)到理想的縮放效果。
基于上述內(nèi)容的分析,本文提出了一種新的基于主體區(qū)域保持的圖像縮放算法,該算法可以在圖像的主體區(qū)域比較大或主體區(qū)域與背景顏色對比不明顯的情況下得到較好的效果。
圖1 傳統(tǒng)縮放算法和縫裁剪算法的比較
圖2 線裁剪算法的縮放效果1
圖3 線裁剪算法的縮放效果2
1.1縫裁剪算法
縫裁剪算法通過插入或者刪除縫對圖像進行縮放,其核心是每次找到一條能量最小的垂直縫,通過刪除該縫使圖像縮小一個像素,或者通過添加一條縫使圖像放大一個像素。如果要在水平方向進行縮放,則在水平方向上找一條能量最小的縫,然后對該縫進行相應(yīng)的操作;如果要在垂直方向進行縮放,則在垂直方向上找到一條能量最小的縫,然后對該縫進行相應(yīng)的操作。
因為在縫裁剪算法中需要保護圖像中視覺重要信息,而重要區(qū)域中像素的顏色值變化比較大,所以Avidan和Shamir[5]將像素能量定義為:
通過x和y方向梯度值的絕對值之和表示該點的能量。圖像I的垂直裁剪縫的定義為:
其中,x是一個映射x:[1,…, n]→[1,…,m],即一條垂直的裁剪縫是一條從上到下能量最小的像素組成的8連通路徑。類似的,圖像I的水平裁剪縫定義為:
對于給定的能量函數(shù)e,定義一條裁剪縫代價為:
要找一條代價最小的裁剪縫,定義s*為代價最小的裁剪縫,則:
對圖像I用動態(tài)規(guī)劃算法求解代價最小的一條裁剪縫。以垂直裁剪縫為例,求解步驟如下:
(1) 利用式(1)計算每個(i, j)點處的能量,得到梯度矩陣MG。
(2) 從 MG第二行的第一個像素點開始從左到右,從上到下計算圖像中每點的能量值,直到計算出所有點的能量值。圖像中(i, j)處的像素點的能量表示為M(i, j),則:其中,e(i, j)是式(1)得到像素點(i, j)的梯度值,遍歷完整幅圖像之后得到圖像的能量矩陣ME。
(3) 根據(jù)得到的能量矩陣ME,在最后一行找到能量值最小的像素點,然后從該像素點向上回溯并記錄回溯經(jīng)過的每個像素點,直到回溯到第一行。其記錄下來的像素點組成的一條縫就是代價最小的一條裁剪縫s*。
(4) 如果要將圖像縮小,則刪除s*即可;如果要放大圖像,則復(fù)制s*得到,然后將插入s*旁邊即可。
1.2角點檢測與高斯差分
角點作為表征圖像局部特征的一個重要因素,其集中體現(xiàn)了圖像的很多重要形狀信息。角點不僅具有旋轉(zhuǎn)不變性,而且也幾乎不受光照條件的影響。在圖像的數(shù)據(jù)信息沒有被破壞的情況下,角點是圖像最小化處理的數(shù)據(jù)量。由于角點具有以上的性質(zhì),所以角點檢測具有很強的實用性,近年來也得到了越來越多的研究者重視。
關(guān)于如何定義角點目前還沒有達(dá)成共識,但是研究者一般認(rèn)為:角點是圖像當(dāng)中梯度變化最大的點。為了檢測圖像的角點,研究者們提出了許多方法。Song等[11]認(rèn)為圖像中的噪聲嚴(yán)重的影響了角點檢測的性能且噪聲很難消除,針對這個問題提出了一種基于噪聲差異級別的角點檢測方法,該算法可以根據(jù)圖像的信噪比自適應(yīng)的設(shè)定閾值以過濾假的角點;Ramakrishnan等[12]認(rèn)為廣泛使用的ShiTomasi和Harris角點檢測方法需要手動的設(shè)定參數(shù)閾值,為此提出了一種基于迭代剪枝的策略改進了ShiTomasi和Harris的角點檢測算法;何中翔等[13]改進了一種基于Harris角點檢測算法的亞像素級角點檢測算法。而本文采用的角點檢測算法是基于高斯差分(difference of Gaussian, DOG)的。
對于二維圖像I(x,y),其尺度空間L( x, y,σ),由該圖像與高斯核G( x, y,σ)卷積得到:
其中,高斯核中的方差σ是尺度因子,決定著圖像被平滑的程度,連續(xù)改變σ就能構(gòu)造圖像的高斯金字塔。DOG空間D( x, y,σ) 是高斯金字塔中相鄰尺度空間函數(shù)之差,即:其中,k表示相鄰尺度空間的尺度比例系數(shù)。不同的k值可以得到不同的DOG空間,所有的DOG空間就構(gòu)成了DOG金字塔,然后檢測金字塔中間層(最高層和最底層除外)中每個像素點,如果一個像素點比相鄰的像素點的值都大或者都小,那么該點就是一個局部極值點,則將該點作為候選特征點,也就是角點。本文算法綜合考慮了算法的效果和時間復(fù)雜性,決定取3個不同的k值,這樣可以取得較好的效果和較快的速度。
常用的圖像主體區(qū)域檢測算法主要是基于圖像的顯著性,一般認(rèn)為圖像的顯著性圖顯示的區(qū)域即為圖像的主體區(qū)域[14],但目前常用的求顯著性的算法計算量都比較大。另外一種求圖像主體區(qū)域的算法是基于角點檢測和凸包算法,由于圖像的角點很少,所以該算法處理速度很快。
角點可以表現(xiàn)圖像的局部特征,并且具有旋轉(zhuǎn)不變性,幾乎不受環(huán)境光照的影響,而且角點的數(shù)量一般比較少,處理速度相對較快,所以可通過角點構(gòu)成的區(qū)域來表示圖像的主體區(qū)域。
由于圖像中角點比較少,所以本文決定采用Graham掃描算法[15]來求角點的凸包。Graham掃描算法首先需找到最小y軸坐標(biāo)點,然后按照其他點和該點的連線與x軸的夾角角度值排序,通過判斷相鄰頂點的空間位置關(guān)系,從而得到逆時針排序的凸包頂點,其時間復(fù)雜度為n log2(n),n表示頂點的數(shù)量。由于原始的Graham掃描算法在點集比較密集時效率會受到影響,吳文周等[16]對原始的Graham掃描算法進行了改進。具體的改進算法過程請參考文獻(xiàn)[16]。
3.1算法目的
本文提出了一種新的基于主體區(qū)域保持的圖像縮放算法,具有比較快的速度,且比縫裁剪算法和傳統(tǒng)的縮放算法能夠更好地保持圖像的主體區(qū)域。在圖像中的主體區(qū)域較大或主體區(qū)域與背景的對比度不明顯的情況下,也可以取得較好的效果。
3.2算法的步驟
本文算法使用DOG對圖像進行角點檢測,對角點使用凸包算法找出圖像中的主體區(qū)域,再利用式(1)計算出圖像的能量圖,對能量圖中位于主體區(qū)域的點進行加權(quán)處理,得到新的能量圖,然后在新的能量圖上使用縫裁剪算法對圖像進行縮放。
算法主要分以下5步:
(1) 求出圖像的 DOG圖。在等式(9)中選擇 3個不同的尺度比例系數(shù),如圖4所示,本文中選用的k值分別為0.750、0.857和0.875,得到3張不同的DOG圖。
(2) 根據(jù)步驟(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掃描算法求角點圖的凸包,得到的凸包區(qū)域即為圖像的主體區(qū)域。圖6(c)所示即為由圖6(b)的角點求得的凸包圖。
(4) 利用式(10)求圖像的初始梯度值圖Einit,再對位于凸包內(nèi)的像素點賦予權(quán)重,得到新的權(quán)重梯度值圖Enew,本文算法的梯度值圖Eours為初始梯度值圖Einit和新的權(quán)重梯度圖Enew的疊加。計算公式如下:
其中,式(10)中e(i,j)是根據(jù)式(1)得到的(i,j)處的梯度值,Einit(i, j)表示(i,j)處初始的梯度值;式(11) 中 w表示權(quán)重系數(shù),I表示圖像,H表示凸包;式(12)中Eours(i, j)表示本文算法得到的梯度值圖。不同的權(quán)重將會對主體區(qū)域進行不同程度的保護。例如圖7(b)中為初始梯度值圖Einit,圖7(c)為新的權(quán)重梯度圖Eours。根據(jù)圖像的不同選擇最適合的權(quán)重,對主體區(qū)域不足和過度保護都會對縮放后的圖像造成不良影響。
(5) 在本文算法得到的梯度值圖Eours上使用動態(tài)規(guī)劃算法得到新的能量圖Mours,在Mours上使用縫裁剪算法對圖像進行縮放。
圖4 3種不同比例系數(shù)的高斯差分圖
圖5 判斷極值點示意圖
圖6 本文算法得到的角點圖、凸包圖
圖7 本文算法的初始梯度值和加權(quán)后的梯度值
本文實驗硬件平臺為一臺2.40 GHz, 4 GB內(nèi)存的計算機,軟件平臺為MATLAB R2013a。本文將從主體區(qū)域的保持程度、本文算法與常用縮放算法的對比和本文算法的特點3個方面進行實驗。
4.1主體區(qū)域保持
由于本文算法對圖像的主體區(qū)域進行了加權(quán)保護,通過對位于主體區(qū)域和非主體區(qū)域的像素點給予不同的權(quán)重可實現(xiàn)不同程度的保護。相對于縫裁剪算法,本文算法在裁剪過程中可以更好地保持圖像的主體區(qū)域。
圖7(b)是本文算法得到的初始能量圖,圖7(c)是本文算法得到加權(quán)后的權(quán)重能量圖,圖7將式(11)中的權(quán)重值w設(shè)為5。通過對比2種算法得到的能量圖,可以看到因本文算法對圖像的主體區(qū)域進行了加權(quán),所以得到的能量圖更加突出圖像的主體區(qū)域,可以更好地保持圖像的主體區(qū)域。
縫裁剪算法將圖像壓縮到一定程度的時候,由于背景區(qū)域被反復(fù)裁剪從而形成了折橫,導(dǎo)致背景區(qū)域的能量變大,使得裁剪縫可能穿過圖像的主體區(qū)域,從而損壞了圖像的主體區(qū)域。圖8(a)、(c)中采用的縫裁剪算法得到的裁剪縫均通過圖像的主體區(qū)域,采用本文算法得到圖8(b)、(d)的裁剪縫則避開了圖像的主體區(qū)域。由此可看出本文算法可以更好地保持圖像的主體區(qū)域。
4.2常用的縮放算法的比較
從圖 9的實驗結(jié)果看出本文算法可以更好地保持圖像的主體區(qū)域,而且在盡可能的保證主體區(qū)域內(nèi)容完整性的情況下,取得了比較好的視覺效果。由于傳統(tǒng)的縮放算法在非等比例縮放的情況下會對圖像中的內(nèi)容進行壓扁或者拉伸,所以影響縮放后圖像的視覺效果??p裁剪算法可以保持圖像的主體區(qū)域,但是在某些情況下,特別是主體區(qū)域較大或者主體區(qū)域與背景對比度不明顯時,容易對主體區(qū)域造成破壞。比如圖9中海豚的尾巴、車窗的頂部、船上的桅桿和汽車左邊緣都被裁剪了,可見縫裁剪算法均沒有取得比較理想的效果,而本文算法則相對較好保持圖像的主體區(qū)域,取得了比較好的效果。
圖8 縫裁剪算法與本文算法在保持圖像主體區(qū)域的比較
圖9 傳統(tǒng)的縮放算法、縫裁剪算法和本文算法的比較
4.3本文算法的特點
由于在圖像縮放過程中每行或每列需要裁剪掉的像素數(shù)量是一定的,因此如果對圖像的主體區(qū)域進行了加權(quán)保護,就會對背景區(qū)域過多裁剪。從一方面來說這可以更好地保持圖像的主體區(qū)域;從另一方面來說本文算法相對于縫裁剪算法對背景區(qū)域的裁剪更多。如圖9中的第二排圖片所示,由于本文方法對車所在的區(qū)域進行了加權(quán)保護,所以車保存的比較完整,但是圖片右上角的公路卻比縫裁剪算法變形嚴(yán)重。因此對于主體區(qū)域的保護程度的取舍很重要,式(11)中不同的w值,會對主體區(qū)域進行不同程度的加權(quán),從而對主體區(qū)域進行不同程度的保護。w值越大對主體區(qū)域的保護越強,更傾向于裁剪背景區(qū)域;反之,w值越小對主體區(qū)域的保護越小。
本文提出了一種新的基于主體區(qū)域保持的圖像縮放算法,通過對圖像使用DOG進行角點檢測,然后利用角點通過Graham算法求凸包,凸包所在的區(qū)域即為圖像的主體區(qū)域;在計算圖像能量圖時先計算初始的能量圖,再對位于凸包內(nèi)的像素點的能量加權(quán)得到新的加權(quán)能量圖,然后將初始能量圖和加權(quán)能量圖疊加得到新的能量圖,最后在新的能量圖上采用縫裁剪算法對圖像進行縮放。實驗結(jié)果表明,本文對圖像的主體區(qū)域進行了加權(quán)保護,可以更好地保持圖像的主體區(qū)域。
本文算法也存在一定的局限性,如果圖像中存在多個主體,根據(jù)角點檢測得到的凸包必然會包含所有的主體區(qū)域,在某些情況下會將大量的非主體區(qū)域包含進來,從而保護了圖像中的非主體區(qū)域,這將破壞圖像縮放后的幾何結(jié)構(gòu)。如果圖像的主體背景較復(fù)雜,則本文算法也會遇到與顯著性算法相同的問題:無法準(zhǔn)確有效地檢測出圖像的主體區(qū)域,從而無法為主體區(qū)域提供準(zhǔn)確有效地保護,進而導(dǎo)致縮放效果不佳。
本文算法在給主體區(qū)域和非主體區(qū)域所使用的權(quán)重是手動指定的,根據(jù)圖片縮放要求的不同需要指定不同的權(quán)重來達(dá)到最好的縮放效果。這顯然不能滿足處理批量圖片的要求,為了處理批量圖片需要根據(jù)圖片的不同自適應(yīng)的指定權(quán)重,如何自適應(yīng)指定權(quán)重是今后研究的重點。
[1] 施美玲, 徐丹, 內(nèi)容感知圖像縮放技術(shù)綜述[J]. 中國圖象圖形學(xué)報, 2012, 17(2): 157-168.
[2] 施美玲, 徐丹, 錢志明. 基于成對比較的內(nèi)容感知圖像縮放效果主觀評估[J]. 計算機輔助設(shè)計與圖形學(xué)學(xué)報, 2013, 25(10): 1503-1513.
[3] 楊云峰, 蘇志勛, 胡金燕. 一種保持邊緣特征的圖像插值方法[J]. 中國圖象圖形學(xué)報, 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] 何中翔, 王明富, 楊世洪, 等. 遙感圖像客觀質(zhì)量評價方法研究[J]. 圖學(xué)學(xué)報, 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] 吳文周, 李利番, 王結(jié)臣. 平面點集凸包Graham算法的改進[J]. 測繪科學(xué), 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
國家自然科學(xué)基金項目(U1304616, 61133009, 61502220);國家“973”重點基礎(chǔ)研究發(fā)展規(guī)劃項目(2011CB302200)
鄒盼盼(1989–),男,湖北黃岡人,碩士研究生。主要研究方向為圖像視頻處理。E-mail:zou_pp@163.com
馬利莊(1963–),男,浙江余姚人,教授,博士,博士生導(dǎo)師。主要研究方向為計算機圖形學(xué)、數(shù)字媒體等。E-mail:ma-lz@cs.sjtu.edu.cn