改進測地活動輪廓模型的AOS實現(xiàn)

江東林,林震梅,王美清

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

2.福州大學數(shù)學與計算機科學學院,福州350108)

改進測地活動輪廓模型的AOS實現(xiàn)

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

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

2.福州大學數(shù)學與計算機科學學院,福州350108)

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

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

1 概述

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

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

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

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

2 GVF與氣球力混合作用的改進GAC模型

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

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

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

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

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

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

3 半隱式方案的AOS算法

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

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

3.1 半隱式方案

半隱式方案過程如下:

(1)離散化L

對LT項進行離散化。時間步長設為Δt,時間離散成tn=nΔt,n∈N。空間步長設為h,通常取h=1。表示像素點u(i,j)在時間tn時的近似值。L的離散化形式如下:

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

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

(2)離散化M

(3)離散化R

在R項中,由于ηg|▽V||▽u|具有雙曲特性,采用迎風方案,有:

其中:

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

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

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

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

整理式(16),有:

其中,I是單位矩陣。

3.2 AOS算法

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

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

式(20)和式(19)相比,僅相差高階的O(Δt2)項,兩式具有相同的誤差階數(shù)。但式(20)的系數(shù)矩陣I-2ΔtAl(un)是嚴格對角占優(yōu)的三角帶狀矩陣。可采用追趕法(Thomas算法［12］)高效求解。因為AOS算法是無條件穩(wěn)定的,所以可以適當增大時間步長,降低迭代次數(shù),從而提高算法的效率。

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

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

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

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

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

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

5 結束語

在GAC_GVF&B模型采用水平集方法的顯式數(shù)值方案實現(xiàn)中,時間步長需要采用較小的值和需要更多的迭代次數(shù),而采用半隱式數(shù)值方案可以解除步長的限制條件,但在計算上需要較長的時間和更大的存儲空間。因為加性算子分裂算法具有穩(wěn)定、高效、可分解等優(yōu)點,所以本文利用半隱式方案的AOS算法對GAC_GVF&B模型的計算進行加速,有效降低了所需的迭代次數(shù),縮短迭代時間和CPU運行時間,提高了分割速率。

［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］ 王大凱,候榆青,彭進業(yè).圖像處理的偏微分方程方法［M］.北京:科學出版社,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ù)值計算基礎［M］.上海:同濟大學出版社,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

國家自然科學基金資助項目“近景攝影測量中的自動圖像分割技術”(11071270)。

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

2013-11-25

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

中文引用格式:江東林,林震梅,王美清.改進測地活動輪廓模型的AOS實現(xiàn)［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.