改进测地活动轮廓模型的AOS实现

江东林,林震梅,王美清

(1.龙岩学院数学与计算机科学学院,福建龙岩364012;

2.福州大学数学与计算机科学学院,福州350108)

改进测地活动轮廓模型的AOS实现

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

(1.龙岩学院数学与计算机科学学院,福建龙岩364012;

2.福州大学数学与计算机科学学院,福州350108)

基于偏微分方程的图像处理技术由于能够获得连续单像素的边缘而受到重视,其中梯度向量场与气球力混合作用的改进GAC模型——GAC_GVF&B克服了传统GAC模型的缺点,能准确地收敛到多目标图像和形状复杂图像的目标边界。但该算法的运行时间较长,影响算法的实际应用。为此,利用半隐式方案的加性算子分裂(AOS)算法,适当增大时间步长,降低迭代次数,对GAC_GVF&B模型的计算进行加速,在保证算法分割准确性的同时提高算法的收敛速度。实验结果表明,采用半隐式方案的AOS算法具有较好的图像分割效果,可有效减少所需的迭代次数,降低迭代时间和CPU运行时间,提高运行速率。

图像分割;测地活动轮廓模型;梯度向量场;追赶法;水平集方法;加性算子分裂算法

1 概述

图像分割是图像处理技术中的关键步骤,它的精度将影响后续的图像分析和识别,因此一直是研究的热点之一。近年来基于PDE的图像分割方法由于能够得到连续单像素的边缘线而受到广泛关注。其中,测地线活动轮廓(GAC)模型不依赖于曲线参数,且能够实现曲线拓扑结构的变化［1］,所以受到重视,如文献［2］的GNGVF、文献［3］提出的DVF场等。

但是GAC模型对于图像中有较深的凹陷边界或多目标时,可能使曲线终止在某一局部极小值状态,无法收敛到正确的目标边界。很多研究针对此问题提出了各种改进方案,如推广的GAC模型［4］、基于梯度向量场［5］和气球力［6］的GVF&B_GAC模型［7］和 GAC_GVF&B(GAC combining GVF with Balloon Force)模型等。其中,GAC_GVF&B模型将梯度向量场与气球力相结合,能准确地收敛到多目标图像和形状复杂图像的目标边界。

图像分割PDE模型的求解主要是通过差分格式进行显式求解。该方案计算公式简单,但是为了保证算法的稳定性,需要采用迎分格式,且时间步长只能用较小的值,因此,需要较多的迭代次数和计算时间。近年来,研究者将半隐式格式的加性算子分裂(Addtive Operator Splitting,AOS)算法引入PDE图像处理模型的求解中,获得了较好的效果。AOS算子最早由 Weichert等人提出［8-9］,应用于图像去噪。它具有稳定、高效、可分解等优点,可以解除步长的限制条件。

本文将AOS算法应用于梯度向量场与气球力混合作用的改进GAC模型——GAC_GVF&B模型,首先给出该模型的半隐式方案,在此基础上给出AOS迭代格式,并对该模型的显式方案和AOS方案进行了数值实验。

2 GVF与气球力混合作用的改进GAC模型

GAC模型无法收敛到凹陷边界和分割多目标图像,推广GAC模型虽然能够有效解决这一问题,但是有可能产生过分割现象。梯度向量场(GVF)与气球力混合作用的改进 GVF模型(GAC_ GVF&B,GAC combining GVF with Balloon Force)利用GVF场的有向边界吸引力代替推广GAC模型中的单向收缩力,较好地克服了过分割的缺点。同时,当轮廓曲线遇到图像对应的GVF场形成的鞍点和驻点时,气球力被激活,驱动曲线越过这些点继续演化,避免了GVF场无法分割多目标和复杂形状的问题。GAC_GVF&B模型对应的曲线演化方程为:

其中,C为演化曲线;N是曲线的单位向内法线向量;κ为曲线的曲率;c,η为参数;sign为符号函数;g为边缘检测函数,通常取为:

其中,K为参数。

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

其中,f(x,y)为边映射函数;Gσ为高斯平滑函数。

引入水平集函数u(u通常取为符号距离函数),则式(1)转化为下列PDE演化方程:

3 半隐式方案的AOS算法

GAC_GVF&B模型的显式数值方案为了保证算法的稳定性,需要采用迎风格式,且时间步长需要采用较小的值,因此迭代时间较长,不利于模型的实际应用。本文利用半隐式方案的AOS算法对GAC_ GVF&B模型的计算进行加速。AOS［10］算法具有稳定、高效、可分解等优点,相对于显式方案,AOS算法在效率上有很大的提高。

为便于说明,将式(4)改写为如下形式:

3.1 半隐式方案

半隐式方案过程如下:

(1)离散化L

对LT项进行离散化。时间步长设为Δt,时间离散成tn=nΔt,n∈N。空间步长设为h,通常取h=1。表示像素点u(i,j)在时间tn时的近似值。L的离散化形式如下:

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

由于|▽u|在像素点四邻域值可能为零,因此采用调和平均数［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算法是一种半隐式算法,允许选用较大的时间步长,计算速度明显快于任何稳定的显式方案。本文将采用半隐式方案的AOS算法对GAC_GVF&B模型的计算进行加速。

将式(17)改写成如下形式:

式(20)和式(19)相比,仅相差高阶的O(Δt2)项,两式具有相同的误差阶数。但式(20)的系数矩阵I-2ΔtAl(un)是严格对角占优的三角带状矩阵。可采用追赶法(Thomas算法［12］)高效求解。因为AOS算法是无条件稳定的,所以可以适当增大时间步长,降低迭代次数,从而提高算法的效率。

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种不同数值方案时的迭代次数和运算时间。GVF场中μ=0.02,二维高斯滤波器的标准方差为σ=3,c=1.5,η=7,显式方案的迭代步长Δt为0.05,而AOS算法中迭代步长Δt为5。

图1 GAC_GVF&B模型对不同图像的分割结果

表1 2种不同数值方案分割实验的运算量测定

从表1可以看出,采用半隐式方案的AOS算法分割图像所需的迭代次数、迭代时间和CPU运行时间均要比采用显式方案所需的迭代次数、迭代时间和CPU运行时间低。越形状复杂的图像,加速效果越明显。

5 结束语

在GAC_GVF&B模型采用水平集方法的显式数值方案实现中,时间步长需要采用较小的值和需要更多的迭代次数,而采用半隐式数值方案可以解除步长的限制条件,但在计算上需要较长的时间和更大的存储空间。因为加性算子分裂算法具有稳定、高效、可分解等优点,所以本文利用半隐式方案的AOS算法对GAC_GVF&B模型的计算进行加速,有效降低了所需的迭代次数,缩短迭代时间和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］ 王大凯,候榆青,彭进业.图像处理的偏微分方程方法［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］ 沈建华.数值计算基础［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-),男,讲师、硕士,主研方向:数字图像处理;林震梅,硕士;王美清,教授、博士生导师。

2013-11-25

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

中文引用格式:江东林,林震梅,王美清.改进测地活动轮廓模型的AOS实现［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.