江東林,林震梅,王美清

(1.龍巖學(xué)院數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院,福建龍巖364012;

2.福州大學(xué)數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院,福州350108)

改進(jìn)測地活動(dòng)輪廓模型的AOS實(shí)現(xiàn)

江東林1,林震梅2,王美清2

(1.龍巖學(xué)院數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院,福建龍巖364012;

2.福州大學(xué)數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院,福州350108)

基于偏微分方程的圖像處理技術(shù)由于能夠獲得連續(xù)單像素的邊緣而受到重視,其中梯度向量場與氣球力混合作用的改進(jìn)GAC模型——GAC_GVF&B克服了傳統(tǒng)GAC模型的缺點(diǎn),能準(zhǔn)確地收斂到多目標(biāo)圖像和形狀復(fù)雜圖像的目標(biāo)邊界。但該算法的運(yùn)行時(shí)間較長,影響算法的實(shí)際應(yīng)用。為此,利用半隱式方案的加性算子分裂(AOS)算法,適當(dāng)增大時(shí)間步長,降低迭代次數(shù),對GAC_GVF&B模型的計(jì)算進(jìn)行加速,在保證算法分割準(zhǔn)確性的同時(shí)提高算法的收斂速度。實(shí)驗(yàn)結(jié)果表明,采用半隱式方案的AOS算法具有較好的圖像分割效果,可有效減少所需的迭代次數(shù),降低迭代時(shí)間和CPU運(yùn)行時(shí)間,提高運(yùn)行速率。

圖像分割;測地活動(dòng)輪廓模型;梯度向量場;追趕法;水平集方法;加性算子分裂算法

1 概述

圖像分割是圖像處理技術(shù)中的關(guān)鍵步驟,它的精度將影響后續(xù)的圖像分析和識(shí)別,因此一直是研究的熱點(diǎn)之一。近年來基于PDE的圖像分割方法由于能夠得到連續(xù)單像素的邊緣線而受到廣泛關(guān)注。其中,測地線活動(dòng)輪廓(GAC)模型不依賴于曲線參數(shù),且能夠?qū)崿F(xiàn)曲線拓?fù)浣Y(jié)構(gòu)的變化［1］,所以受到重視,如文獻(xiàn)［2］的GNGVF、文獻(xiàn)［3］提出的DVF場等。

但是GAC模型對于圖像中有較深的凹陷邊界或多目標(biāo)時(shí),可能使曲線終止在某一局部極小值狀態(tài),無法收斂到正確的目標(biāo)邊界。很多研究針對此問題提出了各種改進(jìn)方案,如推廣的GAC模型［4］、基于梯度向量場［5］和氣球力［6］的GVF&B_GAC模型［7］和 GAC_GVF&B(GAC combining GVF with Balloon Force)模型等。其中,GAC_GVF&B模型將梯度向量場與氣球力相結(jié)合,能準(zhǔn)確地收斂到多目標(biāo)圖像和形狀復(fù)雜圖像的目標(biāo)邊界。

圖像分割PDE模型的求解主要是通過差分格式進(jìn)行顯式求解。該方案計(jì)算公式簡單,但是為了保證算法的穩(wěn)定性,需要采用迎分格式,且時(shí)間步長只能用較小的值,因此,需要較多的迭代次數(shù)和計(jì)算時(shí)間。近年來,研究者將半隱式格式的加性算子分裂(Addtive Operator Splitting,AOS)算法引入PDE圖像處理模型的求解中,獲得了較好的效果。AOS算子最早由 Weichert等人提出［8-9］,應(yīng)用于圖像去噪。它具有穩(wěn)定、高效、可分解等優(yōu)點(diǎn),可以解除步長的限制條件。

本文將AOS算法應(yīng)用于梯度向量場與氣球力混合作用的改進(jìn)GAC模型——GAC_GVF&B模型,首先給出該模型的半隱式方案,在此基礎(chǔ)上給出AOS迭代格式,并對該模型的顯式方案和AOS方案進(jìn)行了數(shù)值實(shí)驗(yàn)。

2 GVF與氣球力混合作用的改進(jìn)GAC模型

GAC模型無法收斂到凹陷邊界和分割多目標(biāo)圖像,推廣GAC模型雖然能夠有效解決這一問題,但是有可能產(chǎn)生過分割現(xiàn)象。梯度向量場(GVF)與氣球力混合作用的改進(jìn) GVF模型(GAC_ GVF&B,GAC combining GVF with Balloon Force)利用GVF場的有向邊界吸引力代替推廣GAC模型中的單向收縮力,較好地克服了過分割的缺點(diǎn)。同時(shí),當(dāng)輪廓曲線遇到圖像對應(yīng)的GVF場形成的鞍點(diǎn)和駐點(diǎn)時(shí),氣球力被激活,驅(qū)動(dòng)曲線越過這些點(diǎn)繼續(xù)演化,避免了GVF場無法分割多目標(biāo)和復(fù)雜形狀的問題。GAC_GVF&B模型對應(yīng)的曲線演化方程為:

其中,C為演化曲線;N是曲線的單位向內(nèi)法線向量;κ為曲線的曲率;c,η為參數(shù);sign為符號函數(shù);g為邊緣檢測函數(shù),通常取為:

其中,K為參數(shù)。

V=(v1,v2)是GVF力場中的向量,滿足下列方程:

其中,f(x,y)為邊映射函數(shù);Gσ為高斯平滑函數(shù)。

引入水平集函數(shù)u(u通常取為符號距離函數(shù)),則式(1)轉(zhuǎn)化為下列PDE演化方程:

3 半隱式方案的AOS算法

GAC_GVF&B模型的顯式數(shù)值方案為了保證算法的穩(wěn)定性,需要采用迎風(fēng)格式,且時(shí)間步長需要采用較小的值,因此迭代時(shí)間較長,不利于模型的實(shí)際應(yīng)用。本文利用半隱式方案的AOS算法對GAC_ GVF&B模型的計(jì)算進(jìn)行加速。AOS［10］算法具有穩(wěn)定、高效、可分解等優(yōu)點(diǎn),相對于顯式方案,AOS算法在效率上有很大的提高。

為便于說明,將式(4)改寫為如下形式:

3.1 半隱式方案

半隱式方案過程如下:

(1)離散化L

對LT項(xiàng)進(jìn)行離散化。時(shí)間步長設(shè)為Δt,時(shí)間離散成tn=nΔt,n∈N?？臻g步長設(shè)為h,通常取h=1。表示像素點(diǎn)u(i,j)在時(shí)間tn時(shí)的近似值。L的離散化形式如下:

將式(7)代入式(6),可整理得:

由于|▽u|在像素點(diǎn)四鄰域值可能為零,因此采用調(diào)和平均數(shù)［11］的有限差分格式代替算術(shù)均值,式(8)改寫為:

(2)離散化M

(3)離散化R

在R項(xiàng)中,由于ηg|▽V||▽u|具有雙曲特性,采用迎風(fēng)方案,有:

其中:

整理后可得GAC_GVF&B模型(式(4))的半隱式方案迭代格式:

把圖像上的所有像素點(diǎn)按行列首尾相連,將圖像寫成向量形式:

其中,矩陣Al(un)=(aijl(un))。

其中,Nl(i)表示像素點(diǎn)i在l=x方向或l=y方向上的相鄰位置。

整理式(16),有:

其中,I是單位矩陣。

3.2 AOS算法

1998年Weickert等人［8］最早提出用于求解圖像濾波的加性分裂算子(Additive Operator Splitting, AOS),其基本思想是將一個(gè)高維線性方程組的求解問題,拆解成多個(gè)關(guān)于一維線性方程組的求解問題。AOS算法是一種半隱式算法,允許選用較大的時(shí)間步長,計(jì)算速度明顯快于任何穩(wěn)定的顯式方案。本文將采用半隱式方案的AOS算法對GAC_GVF&B模型的計(jì)算進(jìn)行加速。

將式(17)改寫成如下形式:

式(20)和式(19)相比,僅相差高階的O(Δt2)項(xiàng),兩式具有相同的誤差階數(shù)。但式(20)的系數(shù)矩陣I-2ΔtAl(un)是嚴(yán)格對角占優(yōu)的三角帶狀矩陣?？刹捎米汾s法(Thomas算法［12］)高效求解。因?yàn)锳OS算法是無條件穩(wěn)定的,所以可以適當(dāng)增大時(shí)間步長,降低迭代次數(shù),從而提高算法的效率。

4 AOS算法的性能分析與比較

本文對不同形狀的圖像分別用GAC_GVF&B模型的顯式方案和AOS加速算法進(jìn)行對比實(shí)驗(yàn)。實(shí)驗(yàn)平臺(tái)為酷睿雙核2.10 GHz的CPU(2 GB內(nèi)存);操作系為Microsoft Windows XP;編程語言為Matlab 7.0。

圖1顯示的是GAC_GVF&B模型對復(fù)雜圖像和多目標(biāo)圖像的分割效果。表1給出了GAC_GVF&B模型采用2種不同數(shù)值方案時(shí)的迭代次數(shù)和運(yùn)算時(shí)間。GVF場中μ=0.02,二維高斯濾波器的標(biāo)準(zhǔn)方差為σ=3,c=1.5,η=7,顯式方案的迭代步長Δt為0.05,而AOS算法中迭代步長Δt為5。

圖1 GAC_GVF&B模型對不同圖像的分割結(jié)果

表1 2種不同數(shù)值方案分割實(shí)驗(yàn)的運(yùn)算量測定

從表1可以看出,采用半隱式方案的AOS算法分割圖像所需的迭代次數(shù)、迭代時(shí)間和CPU運(yùn)行時(shí)間均要比采用顯式方案所需的迭代次數(shù)、迭代時(shí)間和CPU運(yùn)行時(shí)間低。越形狀復(fù)雜的圖像,加速效果越明顯。

5 結(jié)束語

在GAC_GVF&B模型采用水平集方法的顯式數(shù)值方案實(shí)現(xiàn)中,時(shí)間步長需要采用較小的值和需要更多的迭代次數(shù),而采用半隱式數(shù)值方案可以解除步長的限制條件,但在計(jì)算上需要較長的時(shí)間和更大的存儲(chǔ)空間。因?yàn)榧有运阕臃至阉惴ň哂蟹€(wěn)定、高效、可分解等優(yōu)點(diǎn),所以本文利用半隱式方案的AOS算法對GAC_GVF&B模型的計(jì)算進(jìn)行加速,有效降低了所需的迭代次數(shù),縮短迭代時(shí)間和CPU運(yùn)行時(shí)間,提高了分割速率。

［1］ Caselles V,KimmelR,Sapiro G.Geodesic Active Contours［J］.International Journal of Computer Vision, 1997,22(1):61-79.

［2］ Guo Yanqing,Wang Meiqing,Lai Choi-Hong.An Improved GAC Model Combining with GNGVF［C］//Proceedings of DCABES'11.［S.1.］:IEEE Press,2011:197-201.

［3］ Zhu G,Zhang S,Zeng Q.et al.Gradient Vector Flow Active Contours with Prior Directional Information［J］.Pattern Recognition Letters,2010,31(1):845-856.

［4］ 王大凱,候榆青,彭進(jìn)業(yè).圖像處理的偏微分方程方法［M］.北京:科學(xué)出版社,2008.

［5］ Rodtook A,Makhanov S S.Continuous Force Field Analysis for Generalized Gradient Vector Flow Field［J］.Pattern Recognition,2010,43(1):3522-3538.

［6］ Cohen L D.On Active Contour Models and Balloons［J］.CVGPI:Image Understanding,1991,53(2):211-218.

［7］ Paragios N,Mellina-Gottardo O,Ramesh V.Gradient Vector Flow Fast Geodesic Active Contours［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence,2004,26(3):402-407.

［8］ Weickert J,Tter Haar Romeny B M,Viergever M A.Efficient and Reliable Schemes for Nonlinear Diffusion Filtering［J］.IEEE Transactions on Image Processing, 1998,7(3):398-410.

［9］ Weickert J.Applications of Nonlinear Diffusion in Image Processing and Computer Vision［J］.Acta Mathematica University Comenianae,2001,70(1):33-50.

［10］ Weickert J,Tter Haar Romeny B M,Viergever M A.Efficient and Reliable Schemes for Nonlinear Diffusion Filtering［J］.IEEE Transactions on Image Processing, 1998,7(3):398-410.

［11］ Weickert J.Applications of Nonlinear Diffusion in Image Processing and Computer Vision［J］.Acta Mathematica University Comenianae,2001,70(1):33-50.

［12］ 沈建華.數(shù)值計(jì)算基礎(chǔ)［M］.上海:同濟(jì)大學(xué)出版社,1999.

編輯 索書志

AOS Implementation of Improved Geodesic Active Contour Model

JIANG Donglin1,LIN Zhenmei2,WANG Meiqing2
(1.College of Mathematics and Computer Science,Longyan University,Longyan 364012,China;
2.College of Mathematics and Computer Science,Fuzhou University,Fuzhou 350108,China)

The Partial Differential Equation(PDE)image processing is an advanced technology due to the ability of obtaining continuous and one-pixel edges.The improved Geodesic Active Contour(GAC)model by using the gradient vector field and a balloon force——GAC_GVF&B is an important one,because it can convergence accurately to target edges on images with multi-object or complex objects.But the model suffers from long running time which blocks its application.By appropriately increasing the time step and reducing the number of iterations,a semi-implicit additive split operator——Additive Operator Splitting(AOS)is used to speed up the computing of the GAC_GVF&B model and improve the convergence rate with the same accuracy of the segmentation.Experimental results show that the AOS algorithm is correct and effective,can reduces the number of iterations required,and lowers iteration time and cpu time.Furthermore,it speeds up the segmentation.

image segmentation;Geodesic Active Contour(GAC)model;gradient vector flield;chasing method; level set method;Additive Operator Splitting(AOS)algorithm

1000-3428(2014)11-0220-05

A

TP391

10.3969/j.issn.1000-3428.2014.11.043

國家自然科學(xué)基金資助項(xiàng)目“近景攝影測量中的自動(dòng)圖像分割技術(shù)”(11071270)。

江東林(1971-),男,講師、碩士,主研方向:數(shù)字圖像處理;林震梅,碩士;王美清,教授、博士生導(dǎo)師。

2013-11-25

2014-01-22E-mail:donglin_402@163.com

中文引用格式:江東林,林震梅,王美清.改進(jìn)測地活動(dòng)輪廓模型的AOS實(shí)現(xiàn)［J］.計(jì)算機(jī)工程,2014,40(11):220-224.

英文引用格式:Jiang Donglin,Lin Zhenmei,Wang Meiqing.AOS Implementation of Improved Geodesic Active Contour Model［J］.Computer Engineering,2014,40(11):220-224.