應用于圖像分割的改進貪婪蛇算法

， ， ， ，

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

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

1 基本的貪婪蛇算法

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

圖1 貪婪蛇算法模型框架

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

基本的GSA的能量函數形式化描述為

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

(1)

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

蛇素的一步移動距離δ計算公式為

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

，

(2)

當k=1時， 蛇素一步移動距離取δ1∈{0, ±1}， 當k=2時，蛇素一步移動距離取δ2∈{0,±1,±2}。當k=1時，第i個蛇素的鄰域Gi如圖2所示。

?表示蛇素；◎表示Gi內的像素；○表示普通像素。圖2 蛇素的鄰域Gi

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

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

(3)

彎曲力Ecurv的能量函數為

(4)

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

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

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

圖像力的具體能量函數Eimage為

(5)

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

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

2 改進貪婪蛇模型

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

2.1 圖像灰度預處理

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

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

(6)

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

(7)

式中k表示位移系數。式(7)相對于式(6)的效率提升效果，將通過實驗數據加以驗證。

2.2 GSA的改進

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

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

(8)

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

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

(9)

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

2.3 貪婪策略

2.3.1 觀測點選取

當式(9)迭代一定次數后，IGSA完成蛇素的初始收斂。蛇素初始收斂過程可以保證蛇素點依序散落在真實目標輪廓周圍，但少量蛇素會因為彎曲力和連續(xù)力的綜合作用而偏離目標輪廓。圖像輪廓界定主要根據圖像邊界的梯度值，IGSA中使用的貪婪策略主要圍繞梯度值完成運算。將初始輪廓視作一個N邊形，則該N邊形的中心被稱為觀測點px,y。如圖4所示。

圖4 觀測點選取

px,y的坐標具有如下性質：

(10)

(11)

式中：A為由Px,y點出發(fā)的N條射線與輪廓的交點；Axi、Ayi為A點的坐標。當觀測點px,y位于目標輪廓外圍時，需要特殊考慮。此時的目標輪廓通常為凹形，對此我們設計出一套方法來解決此問題：

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

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

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

圖5 輔助點在外的情況

(12)

(13)

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

當觀測點px,y設在一個分辨率M×N的圖像中，對依據貪婪策略的曲線收縮步驟如下：

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

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

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

圖6 輪廓邊緣構造直線

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

3 實驗結果與分析

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

以一幅分辨率為2 560像素×1 600像素的圖像為例， 經過實際運算后， 整理的實驗數據如表1所示。

表1 權重系數Δ1、Δ2、Δ3取值對算法運行時間的影響

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

3.2 IGSA算法目標輪廓提取實驗

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

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

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

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

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

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

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

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

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

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

4 結語

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

參考文獻:

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

[2] 王靜文,劉弘. 基于Snake模型的植物葉片面積計算方法[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和邊界跟蹤的主動輪廓圖像分割[J]. 濟南大學學報(自然科學版), 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] 沈宋衍，陳瑩. 在線學習機制下的Snake輪廓跟蹤[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] 劉宏申，孫曉娜，汪量. 基于改進Snake的多目標分割算法[J]. 計算機工程與設計, 2014,30 (19):4455-4460.

[9] 周志宇，楊衛(wèi)成，汪亞明，等. 應用梯度矢量流Snake和灰預測的人臉輪廓跟蹤[J].光學精密工程, 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] 祝世平，高潔. 基于變化檢測和改進的GVF Snake模型的運動目標輪廓提取[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.