應(yīng)用于圖像分割的改進(jìn)貪婪蛇算法

， ， ， ，

(1. 淮安信息職業(yè)技術(shù)學(xué)院 計(jì)算機(jī)與通信工程學(xué)院， 江蘇 淮安 223003； 2. 河海大學(xué) 計(jì)算機(jī)與信息學(xué)院， 江蘇 南京 210098；3. 南京信息工程大學(xué) 計(jì)算機(jī)與軟件學(xué)院， 江蘇 南京 210044； 4. 南京師范大學(xué) 商學(xué)院， 江蘇 南京 210023)

為實(shí)現(xiàn)一種可以高效地處理凹形圖像的貪婪蛇算法，本文中在原始貪婪蛇算法的基礎(chǔ)上提出一種改進(jìn)貪婪蛇算法(improved greedy snake algorithm，IGSA)。IGSA首先對(duì)原始圖像進(jìn)行灰度處理，然后使用一種改進(jìn)的GSA完成初始蛇素的收斂，最后通過一種貪婪算法完成蛇素的最終收斂。

1 基本的貪婪蛇算法

GSA中，蛇素的本質(zhì)是一組有序點(diǎn)，其連線為最終提取的圖像輪廓，因此，GSA也被認(rèn)為是一種包含多個(gè)蛇素點(diǎn)的輪廓逼近表示方法。GSA模型的框架如圖1所示。

圖1 貪婪蛇算法模型框架

GSA的計(jì)算目標(biāo)是通過外力和內(nèi)力，使初始蛇素最終移動(dòng)到目標(biāo)輪廓邊緣位置，并確保蛇素之間有序且均勻分布，因此GSA整體上是一類基于圖像屬性的算法[12]。在GSA中，算法外力主要包括彎曲力和連續(xù)力，內(nèi)力主要包括圖像力。

基本的GSA的能量函數(shù)形式化描述為

γiEimage[v(i),j]}，

(1)

式中：v(i)表示第i個(gè)蛇素；j為i蛇素鄰域Gi內(nèi)的第j個(gè)像素，j的取值與蛇素的一步移動(dòng)距離δ有關(guān)；α、β、γ是伸縮參數(shù)，用來控制各組成部分的權(quán)重關(guān)系;Eant為連續(xù)力；Ecurv為彎曲力；Eimage為圖像力。

蛇素的一步移動(dòng)距離δ計(jì)算公式為

j=i±δk，k∈{1,2}

，

(2)

當(dāng)k=1時(shí)， 蛇素一步移動(dòng)距離取δ1∈{0, ±1}， 當(dāng)k=2時(shí)，蛇素一步移動(dòng)距離取δ2∈{0,±1,±2}。當(dāng)k=1時(shí)，第i個(gè)蛇素的鄰域Gi如圖2所示。

?表示蛇素；◎表示Gi內(nèi)的像素；○表示普通像素。圖2 蛇素的鄰域Gi

在基本的GSA中，Gi集合由當(dāng)前蛇素和其周圍第1層像素構(gòu)成，蛇素總數(shù)為9。一些改進(jìn)算法，例如SGSA中[12]，蛇素一步移動(dòng)距離取δ2，則Gi集合由當(dāng)前蛇素與其周圍2層像素構(gòu)成，因此，SGSA的一步移動(dòng)距離δ2∈{0,±1,±2}，其中蛇素總數(shù)為25。相較于GSA，SGSA的搜索范圍增加，同時(shí)也意味著計(jì)算開銷增大。為保證算法執(zhí)行速度，IGSA中使用δ1∈{0,±1}、蛇素總數(shù)為9的模式。

連續(xù)力Econt的能量函數(shù)為

(3)

彎曲力Ecurv的能量函數(shù)為

(4)

式中 |v(i-1)-2v(i,j)+v(i+1)|表示對(duì)i-1、i+1個(gè)蛇素與Gi中的像素j進(jìn)行和向量計(jì)算， 如圖3所示。

?表示蛇素；◎表示Gi內(nèi)的像素。圖3 |v(i-1)-2v(i, j)+v(i+1)|的計(jì)算過程

圖3顯示，GSA通過|v(i-1)-2v(i,j)+v(i+1)|

圖像力的具體能量函數(shù)Eimage為

(5)

式中：I[v(i),j]表示Gi中第j個(gè)像素點(diǎn)的梯度值； min{I[v(i),j]}和max{I[v(i),j]}分別表示Gi所包含的像素的最小和最大梯度值。

在整個(gè)能量函數(shù)進(jìn)行極小化的過程中，連續(xù)力能量函數(shù)使蛇素均勻分布于當(dāng)前目標(biāo)輪廓，彎曲力能量函數(shù)使其輪廓盡可能平滑，圖像力使蛇素盡可能地停留在高梯度像素點(diǎn)。3個(gè)力同時(shí)作用，蛇素可以在外力的作用下不斷向真實(shí)具體的輪廓進(jìn)行移動(dòng)，內(nèi)力在保持蛇素拓?fù)湫暂^好的同時(shí)隨著蛇素點(diǎn)的移動(dòng)而不斷變化著，最終內(nèi)力和外力相互制約形成一個(gè)較好的輪廓。

2 改進(jìn)貪婪蛇模型

GSA算法要求初始化的蛇素只有在接近圖像邊緣的情況下才有比較好的收斂效果，并且無法提取凹形輪廓。為彌補(bǔ)上述不足，本文中提出了一種新的目標(biāo)輪廓提取算法IGSA。完整的IGSA由3個(gè)部分構(gòu)成，即圖像灰度預(yù)處理、蛇素初始收斂和貪婪收斂。

2.1 圖像灰度預(yù)處理

在一些圖像分割問題中，原始圖像往往存在斑點(diǎn)粗糙、噪點(diǎn)干擾等問題?；叶忍幚淼哪康氖鞘乖紙D像的特征更加明顯，使圖像邊緣化得到加強(qiáng)，去噪、銳化程度也相應(yīng)地提高?；叶忍幚砉綖?/p>

Grv(i), j=Δ1Rv(i), j+Δ2Gv(i), j+Δ3Bv(i), j，

(6)

式中：Grv(i), j表示某個(gè)像素點(diǎn)v(i)的灰度值；Rv(i), j、Gv(i), j、Bv(i), j分別表示紅色、 綠色、 藍(lán)色通道值；Δ1、Δ2、Δ3為權(quán)重系數(shù)，實(shí)踐表明，Δ1=0.299，Δ2=0.587，Δ3=0.114時(shí)，圖像灰度處理效果較為理想。當(dāng)圖像較大時(shí)，為避免浮點(diǎn)運(yùn)算影響計(jì)算速度，對(duì)式(6)算法進(jìn)行優(yōu)化。具體方法為

(7)

式中k表示位移系數(shù)。式(7)相對(duì)于式(6)的效率提升效果，將通過實(shí)驗(yàn)數(shù)據(jù)加以驗(yàn)證。

2.2 GSA的改進(jìn)

根據(jù)式(3)、(4)，Econt和Ecurv的取值范圍都在(0,1]。前期實(shí)驗(yàn)中，通過定量分析發(fā)現(xiàn)，I[v(i),j]通常為一個(gè)3位實(shí)數(shù)，|max{I[v(i),j]}-min{I[v(i),j]}|

通常為一個(gè)遠(yuǎn)小于1的實(shí)數(shù)。相對(duì)于Econt和Ecurv，Eimage的取值范圍過大，使得綜合力E[v(i),j]幾乎完全受Eimage影響。為了均衡3個(gè)力，本文中對(duì)Eimage進(jìn)行了歸一化處理，改進(jìn)后的圖像力公式為

(8)

式中Eimage的取值范圍在(0,1]。整個(gè)蛇形算法能量函數(shù)可以由式(9)表示為

γiEimage[v(i),j]}。

(9)

從直觀上看，式(9)為3項(xiàng)相加，而原始GSA中式(1)為加減混合計(jì)算。這樣的變化，使綜合力函數(shù)公式更加整潔，可控性更好。

2.3 貪婪策略

2.3.1 觀測點(diǎn)選取

當(dāng)式(9)迭代一定次數(shù)后，IGSA完成蛇素的初始收斂。蛇素初始收斂過程可以保證蛇素點(diǎn)依序散落在真實(shí)目標(biāo)輪廓周圍，但少量蛇素會(huì)因?yàn)閺澢瓦B續(xù)力的綜合作用而偏離目標(biāo)輪廓。圖像輪廓界定主要根據(jù)圖像邊界的梯度值，IGSA中使用的貪婪策略主要圍繞梯度值完成運(yùn)算。將初始輪廓視作一個(gè)N邊形，則該N邊形的中心被稱為觀測點(diǎn)px,y。如圖4所示。

圖4 觀測點(diǎn)選取

px,y的坐標(biāo)具有如下性質(zhì)：

(10)

(11)

式中：A為由Px,y點(diǎn)出發(fā)的N條射線與輪廓的交點(diǎn)；Axi、Ayi為A點(diǎn)的坐標(biāo)。當(dāng)觀測點(diǎn)px,y位于目標(biāo)輪廓外圍時(shí)，需要特殊考慮。此時(shí)的目標(biāo)輪廓通常為凹形，對(duì)此我們?cè)O(shè)計(jì)出一套方法來解決此問題：

步驟1 以觀測點(diǎn)px,y為端點(diǎn)，通過每個(gè)蛇素v(i)構(gòu)造出N條射線L(i)，i=1,2,…,N。

步驟2 對(duì)于每條與輪廓相交的射線Li，i=1,2,3,…n，找到其交點(diǎn)并且依次記錄，則這N個(gè)數(shù)據(jù)點(diǎn)表示為pxi,yi(i=1,2,3,…,n)，并且算出每條射線與輪廓交點(diǎn)的中點(diǎn)坐標(biāo)mxi,yi(i=1,2,3,…,n) 如圖5所示。

步驟3 此時(shí)，由這N/2組成的中點(diǎn)坐標(biāo)mxi,yi(i=1,2,3,…,n)算出最后的輔助點(diǎn)為

圖5 輔助點(diǎn)在外的情況

(12)

(13)

2.3.2 貪婪策略執(zhí)行過程

當(dāng)觀測點(diǎn)px,y設(shè)在一個(gè)分辨率M×N的圖像中，對(duì)依據(jù)貪婪策略的曲線收縮步驟如下：

步驟1 其中新的蛇形模型能量函數(shù)Eimage從圖像邊界開始迭代i次后，輪廓已經(jīng)初步收斂。

步驟2 以觀測點(diǎn)px,y作為此當(dāng)前蛇形模型能量函數(shù)Eimage的中心， 構(gòu)造出n條射線Lj(j=1, 2, …,n)， 從當(dāng)前輔助點(diǎn)px,y發(fā)出到此迭代i次后的輪廓邊緣。 此時(shí)， 2條相鄰直線的夾角為2π/n，如圖6所示。

步驟3 對(duì)于每條直線Lj(j=1,2,…,n)，定義Pv(i, j)是此直線Lj上的第i個(gè)點(diǎn)，計(jì)算每個(gè)點(diǎn)的梯度Gv(i, j)，選取這條線上梯度最大值max{Gv(i, j)}作為收斂的最終點(diǎn)。

圖6 輪廓邊緣構(gòu)造直線

步驟4 將每條直線Lj上的差距最大的值max{Gv(i, j)}連接構(gòu)造出收斂的輪廓。

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

3.1 灰度處理算法優(yōu)化后的性能測試

以一幅分辨率為2 560像素×1 600像素的圖像為例， 經(jīng)過實(shí)際運(yùn)算后， 整理的實(shí)驗(yàn)數(shù)據(jù)如表1所示。

表1 權(quán)重系數(shù)Δ1、Δ2、Δ3取值對(duì)算法運(yùn)行時(shí)間的影響

觀察表1可以發(fā)現(xiàn)： 當(dāng)k=0時(shí)， 式(7)就退化為式(6)。 同樣條件下式(6)在所有參數(shù)組合中所耗時(shí)間最多。 所有參數(shù)組合中，Δ1=38，Δ2=75，Δ3=15，k=7的效率最高。IGSA的灰度預(yù)處理則使用上述參數(shù)配置。

3.2 IGSA算法目標(biāo)輪廓提取實(shí)驗(yàn)

為了測試IGSA的性能，本文中進(jìn)行3組實(shí)驗(yàn)。對(duì)比了IGSA和SGSA這2種算法。2種算法的參數(shù)設(shè)置如下：α=2.0，β=2.0，γ=1.0，初始化蛇素規(guī)模為500，算法迭代次數(shù)為150。

圖7—9分別為SGSA和IGSA的蛇素收斂效果。

(a) 跳躍貪婪蛇算法 (b) 改進(jìn)貪婪蛇算法圖7 簡單凹形幾何圖形分割效果圖

(a) 跳躍貪婪蛇算法 (b) 改進(jìn)貪婪蛇算法圖8 等曲率凹形幾何圖形分割效果圖

(a) 跳躍貪婪蛇算法 (b) 改進(jìn)貪婪蛇算法圖9 不等曲率凹形幾何圖形分割效果圖

為了便于觀察，實(shí)驗(yàn)中用“?”符號(hào)標(biāo)記出了少量蛇素點(diǎn)位置。圖7為一個(gè)簡單凹形幾何圖形，擁有一個(gè)曲率不大的凹形區(qū)域。圖8、 9是2個(gè)較復(fù)雜的凹形幾何圖形。圖8中帶有4個(gè)曲率相同的凹形區(qū)域，圖9中帶有2個(gè)曲率較大的凹形區(qū)域和2個(gè)曲率較小的凹形區(qū)域。上述實(shí)驗(yàn)中，IGSA都取得了較好的實(shí)驗(yàn)效果，特別是凹形區(qū)域的蛇素收斂效果令人滿意。

為了進(jìn)一步驗(yàn)證IGSA處理真實(shí)圖像分割問題的有效性，本文中特別選取了2組真實(shí)圖像。圖10是一個(gè)擁有較大凹形曲率輪廓的真實(shí)圖像，圖11為一個(gè)復(fù)雜的人臉圖像，擁有較復(fù)雜的輪廓。在圖10中，SGSA只能完成粗糙的圖像分割，無法收斂到凹陷區(qū)域，而IGSA展示出了較好的凹陷區(qū)域收斂能力，分割出的邊界輪廓較為精準(zhǔn)。圖11中，在處理人臉輪廓提取問題上，SGSA雖然可以將整個(gè)人臉分割出來，但在細(xì)節(jié)上IGSA表現(xiàn)出了更好的分割效果。

(a) 跳躍貪婪蛇算法 (b) 改進(jìn)貪婪蛇算法圖10 真實(shí)圖像分割效果圖

(a) 跳躍貪婪蛇算法 (b) 改進(jìn)貪婪蛇算法圖11 人臉圖像分割效果圖

綜上所述，在處理真實(shí)圖像分割問題中，相較于SGSA，IGSA有更好的輪廓提取效果，特別是IGSA更善于處理曲率較大的凹形圖形。

4 結(jié)語

針對(duì)傳統(tǒng)Snake模型對(duì)初始位置敏感以及非凹性的問題，本文中在GSA的基礎(chǔ)上提出了一種IGSA。IGSA使用一種高效的灰度處理方法和一類改進(jìn)的Snake模型收斂策略，并融入了貪婪方法。貪婪策略的使用使得IGSA可以較好地處理凹形圖像輪廓提取問題。本文中通過凹形幾何圖像和真實(shí)圖像，實(shí)驗(yàn)驗(yàn)證了IGSA的有效性和高效性。IGSA雖然取得了較好的圖像分割效果，但也存在一些不足，如相較于GSA，IGSA在灰度預(yù)處理階段和最后的貪婪收斂階段要多占用一些系統(tǒng)開銷，但這些開銷相對(duì)于SGSA中每個(gè)蛇素每移動(dòng)一步都增加計(jì)算量的做法還是較低的。另外，為了彌補(bǔ)這一不足，本文中已經(jīng)通過實(shí)驗(yàn)方法對(duì)灰度預(yù)處理進(jìn)行了優(yōu)化。未來，考慮將IGSA算法應(yīng)用于三維圖像分割和人臉識(shí)別等一些實(shí)際問題。

參考文獻(xiàn):

[1] KASS M，WITKIN A. Snakes: active contour models[J]. International Journal of Computer Vision，1988，1(4):321-331.

[2] 王靜文,劉弘. 基于Snake模型的植物葉片面積計(jì)算方法[J]. 計(jì)算機(jī)工程，2013，39(1): 234-238.

[3] LIU C, XIAO Y Y, YANG J. A coastline detection method in polarimetric SAR images mixing the region-based and edge-based active contour models[J]. IEEE Transactions on Geoscience and Remote Sensing, 2017, 55(7): 3735-3747.

[4] 蔣小波，梁久禎，周世兵. 基于GVF Snake和邊界跟蹤的主動(dòng)輪廓圖像分割[J]. 濟(jì)南大學(xué)學(xué)報(bào)(自然科學(xué)版), 2015, 29(4): 269-274.

[5] ALMEIDA T M, CAVALCANTE T. Three-dimensional radial active contour model: a 3-D to 1-D image segmentation technique[J]. IEEE Latin America Transactions, 2017,15(2): 365-373.

[6] 沈宋衍，陳瑩. 在線學(xué)習(xí)機(jī)制下的Snake輪廓跟蹤[J].計(jì)算機(jī)工程，2015，41(4):195-198.

[7] COHEN L D, COHEN I D. Finite-element methods for active contour model and balloons for 2D and 3D images[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1993, 15(11):1131-1147.

[8] 劉宏申，孫曉娜，汪量. 基于改進(jìn)Snake的多目標(biāo)分割算法[J]. 計(jì)算機(jī)工程與設(shè)計(jì), 2014,30 (19):4455-4460.

[9] 周志宇，楊衛(wèi)成，汪亞明，等. 應(yīng)用梯度矢量流Snake和灰預(yù)測的人臉輪廓跟蹤[J].光學(xué)精密工程, 2014,19(11)：2744-2752.

[10] XU C Y. Gradient vector flow: a new external force for Snakes[C]//Proceedings of IEEE International Conference on Computer Vision and Pattern Recognition. Washington D C: IEEE Computer Society，1997: 66-71.

[11] 祝世平，高潔. 基于變化檢測和改進(jìn)的GVF Snake模型的運(yùn)動(dòng)目標(biāo)輪廓提取[J]. 光電子激光，2013，24(9):1083-1089.

[12] WILLIAMS D J, SHAH M. A fast algorithm for active contours and curvature estimation[J].CVGIP:Image Understanding, 1992, 55(1): 14-26.

[13] MUSTAFA S, LAM K M, YAN H. A faster converging snake algorithm to locate object boundaries[J]. IEEE Transactions on Image Processing，2013, 15(5): 1182-1191.