基于模板库的自动图像对象分割方法研究*

(海军陆战学院 广州 510430)

基于模板库的自动图像对象分割方法研究*

徐清华魏小磊李中良

(海军陆战学院 广州 510430)

针对现实世界中外观不一,而形态上有模式可循的对象,提出了一种基于模板库的自动对象分割方法。采用模板描述对象形态,构建模板库作为对象的先验知识,将未知的匹配模板视为隐变量,采用由按位编码方式组成的复合模板与图像特征进行匹配确定隐变量的取值空间;然后,对隐变量求积分得到图像中对象的边缘概率。最后,求解边缘概率所对应的能量函数,实现基于模板库的自动对象分割。实验结果验证了论文方法的正确性和有效性。

对象分割;图割;模板;能量函数

ClassNumberTP391.4

1 引言

计算机对不同场景下的任意对象进行自动分割一直以来都是研究者所致力追求的目标,要实现这一目标,必须先让计算机掌握关于对象的知识,它是以图像中对象的特征所表现的,这种特征是它区别于其他的独特属性。

由于对象本身可能就不是一个内部特征均匀的整体,其内部差异会导致它形成不同的区域,而更复杂的情况如对象与背景的边界模糊,对象与背景的颜色相似或重叠,或者出现遮挡等等,仅依靠图像颜色、梯度等低层特征就希望得到好的结果是不切实际的。高层特征是与对象所属的类相关的,是对其形状、轮廓、外观等特征所具有的共性的提取和学习,通常由对象识别领域引入,通过图像中的角点、线、边缘、图像块等形式[1～6]给出。但是,现实世界中的对象类别丰富,特定的知识只适用于特定的对象,因此,自动分割方法往往仅针对某一类或几类特定对象,而且知识往往需要预先根据一定数量的训练数据经过复杂的机器学习过程得到,导致这些方法的应用范围受到很大限制。

通过模板来描述对象的特征,关于对象类的知识模型采用模板库形式,避免了训练知识模型的复杂过程,使得知识可以非常方便地补充。由于事先并不知晓具体哪个模板能与图像中的待分割对象匹配,无法直接构建包含先验信息的能量函数进行求解,因此,将未知的匹配模板视为隐变量,采用由按位编码方式组成的复合模板与图像特征进行匹配确定隐变量的取值空间;然后,对隐变量求积分得到图像中对象的边缘概率。最后,求解边缘概率所对应的能量函数,实现基于模板库的自动对象分割。

2 图像对象分割问题数学建模

对于给定图像D,设S={si|i=1,…,n}为一随机变量集合,其中,变量si与图像元素di(D={di|i=1,…,n})对应,用A来表示对S的标记,A={A1,A2,…,An},其中,Ai∈L,L为标签集合,在本文的图像对象分割问题中,L={obj=1,back=0}。A可看作是S～L的映射,它的不同取值对应了对S的不同标记即对图像D分割的结果,A的取值空间即所有可能的标记,取决于变量和标签集合的大小,可表示为笛卡尔积:Γ=L×L×…×L=Ln,则图像对象分割问题就是在Γ空间中寻找最佳标记A*的问题。然而,图像对象分割的实质是对图像内容的视觉感知组织,它是由图像数据本身和先验知识所共同决定,用Ψ表示先验知识,则根据最大后验概率准则,图像对象分割问题的最佳标记解A*可表示为

(1)

式中,P(A|D,Ψ)表示给定图像数据D与先验知识Ψ的条件下标记A的概率。

图像本身所具备的局部相关性,使得可采用条件随机场对其建模,又根据MRF与Gibbs分布的等价性原理[7]可以导出:

P(A|D,Ψ)=Z-1×e-E(A;D,Ψ)

(2)

式中,Z=∑A∈Γe-E(A;D,Ψ)为归一化常数;E(A;D,Ψ)=∑c∈CVc(A;D,Ψ)为随机场中所有子团势能之和。子团是S中元素的子集,其中的元素必互相邻,即对任意si,sj∈c,i≠j有sj∈Neighbor(si),子团势能Vc(A;D,Ψ)则是定义在子团上的函数。通常采用大小不超过2的低阶子团,相应的能量函数表达为

(3)

即式(1)的对象分割问题可转化为能量函数最小化问题:

(4)

由此,在处理对象分割问题时,只需关注随机变量对应的图像元素、标签选定、能量函数定义以及能量函数最小化方法。

3 基于模板库的自动对象分割方法原理

Eapp(Ai;D,ΘX)=

(5)

其中,ρ为控制参数。

此外,匹配的模板可以视为对象的形状先验信息,为了保证分割结果具有模板的外形轮廓,可以定义包含模板信息的能量项:

Etemp(Ai,Aj,X)=ω×dist(si,sj,X)

(6)

其中,dist(si,sj,X)为两相邻像素中点到模板轮廓的最短欧式距离。对象和背景交界处的两相邻像素其中一个必属于对象而另一个必属于背景,因此两相邻像素的中点即可视为对象和背景交界上的点,而匹配的模板轮廓指示了对象和背景的交界,因此相邻像素中点到模板轮廓的距离就可以用来表示该相邻像素落在交界上可能性,即距离越远可能性越小而相应的在能量值上的反映则越大,反之亦然。ω决定了能量值随距离变化的程度。

同时为了保证分割结果能较好地保持图像边缘,可以定义包含对比信息的能量项,即鼓励相似的相邻像素取相同标签,而相异的相邻像素取不同标签:

Econ(Ai,Aj;D)=δ·dist-1(si,sj)·exp(-β-1·‖di-dj‖2)

(7)

其中,dist(si,sj)为si和sj之间的欧几里德距离;‖di-dj‖2度量了变量si和sj间在颜色空间的L2范数;δ为缩放系数,β为控制阈值,取为β=2〈‖di-dj‖2〉,其中〈·〉表示数学期望。最终,在给定图像D且已知匹配模板X的情况下,对象分割问题的能量函数为

(8)

其中,U为定义在S上的邻域系统中所有相邻像素对的集合。这里,|Ai-Aj|保证了二阶子团势能函数具有子模性条件,从而使得求解式(8)的能量函数最小化解,可以采用图割方法[8]进行快速、精确地求解。

对于基于模板库的自动对象分割而言,先验知识已经由已知的匹配模板变为了包含众多模板的模板库,设模板库中肯定有与待分割对象大致匹配的模板,那么当前已知的信息仅是匹配模板的存在性,但并不知道具体哪个或哪些模板能匹配图像中的待分割对象,匹配程度也未知,这也进一步导致了对象和背景外观信息无法获取。因此,无法直接建立式(8)来求解,需要寻求其他途径。

若将未知的匹配模板X视为隐变量,根据贝叶斯规则,可得A关于D的边缘概率:

(9)

其中,Τ⊂Φ为隐变量X的取值空间,则对象分割问题可以表示为

(10)

即若已知隐变量X的取值空间Τ,对象分割问题就可转为求解使边缘概率P(A|D)最大的A*。其中,P(A,X|D)又可以分解为

P(A,X|D)=P(A|D,X)·P(X|D)

(11)

P(A|D,X)为A关于D和X的后验概率,而P(X|D)则是X在给定D的条件下的先验概率,又可视为X在Τ中的权重,简记作wX=P(X|D)。则:

(12)

(13)

(14)

即基于模板库的对象分割问题可以表示为最小化下面的能量函数:

·(Etemp(Ai,Aj;D,X)+Econ(Ai,Aj;D))

(15)

求解的关键在于确定未知匹配模板的取值空间Τ,以及该空间中各模板的权值。

基于模板库的自动对象分割方法框架可描述为:

设模板库为Φ,Φ={Φ1,Φ2,…,Φk}包含k个模板,待分割图像为D。

步骤1:根据图像的低层特征判断模板库Φ中匹配模板X的取值空间Τ={Τi}以及各模板的权值wΤi。

步骤2:根据Τi∈Τ所给出的对象和背景区域信息,进行采样,构建Τi的对象和背景的外观颜色模型。

步骤3:构造相应的图拓扑,利用图割方法进行求解。

4 基于模板库的自动对象分割方法关键技术实现

4.1 模板库的建立

为了实现对图像中目标对象的自动分割,必须首先建立关于目标对象的模板库。其中,模板由二值图像表示,其像素的灰度值表示该像素是否为模板中的特征像素。本节模板库中的模板分为基模板和衍生模板,基模板为原始模板,通常由用户从图像中提取对象轮廓得到,而衍生模板由基模板变换得到,这里,对于非铰链式刚体对象,仅考虑缩放和旋转变换,缩放比例范围为基模板大小的0.7～1.3,间隔为0.1,而旋转角度范围为-15°～15°,间隔5°,因此,一个基模板就可以衍生出7×7个衍生模板。如图1所示为两个基模板与由其衍生而得的衍生模板的例子,黑色表示模板特征像素,白色为非特征像素。

图1 模板库中模板示例

4.2 基于边缘特征的匹配模板取值空间确定

本文依托重庆市华岩隧道西延伸段项目体外预应力连续梁桥设计施工过程，采用ABAQUS有限元软件建立体外预应力锚固块有限元模型，对锚固块进行仿真分析，得出如下结论：

模板取值空间的确定利用了图像的边缘特征,它是对象形状在图像空间的表征。本文将利用基于Hausdorff距离的特征匹配思想[9],在距离变换空间内实现对待分割对象的位置和形状的估计,用以确定模板的取值空间。如图2所示为确定模板取值空间的过程示意图:首先对待分割图像进行边缘特征提取;然后对边缘特征图进行距离变换得到它的距离映射图;最后利用基于Hausdorff距离的特征匹配方法确定匹配模板的取值空间和相应在图像中的匹配坐标。下面将分步进行阐述。

图2 确定模板取值空间的示意图

1)待分割图像的边缘特征提取

为使提取出的边缘特征具有较高的可信度,采用Canny边缘算子提取图像的边缘特征,如图3所示为对洗发水瓶的图像进行边缘提取的例子。

图3 基于Canny算子的边缘特征提取

2)边缘特征的距离映射

图4 图像边缘特征的距离映射图

3)基于Hausdorff距离的特征匹配

基于Hausdorff距离的特征匹配方法以特征集合之间的Hausdorff距离作为匹配质量的测度,同大多数匹配方法不同,Hausdorff距离的计算并不基于相应特征集合上的明确的点对点距离,即不要求图像特征像素点与模板特征像素点之间具有一一对应关系,它仅是一种相似程度的度量。此外,基于Hausdorff距离的方法不需要进行光流计算等复杂计算。因此,选择它来待分割对象进行定位和匹配。

本文所采用的Hausdorff距离定义如下:假设有两组特征集合ΗX={hX,1,hX,2,…,hX,p}和ΗI={hI,1,hI,2,…,hI,p}分别对应模板特征和图像特征,其中,hX,i表示了模板中的轮廓像素点,而hI,i则对应了边缘图中的边缘像素点。这两个点集合之Hausdorff距离定义为

(16)

其中

(17)

符号‖·‖为定义在点hX,i和hI,j上的某种距离范数。式(18)表示模板X中的特征点hX,i到边缘图中边缘特征点的最小距离,即距离映射图中相应像素的灰度值,而ћ(·)是距离截断函数:

(18)

其中,τ作为阈值用来消除因遮挡或漏测的边缘特征对匹配的影响。因此,式(18)就表示了模板特征与图像边缘特征的截断平均Hausdorff距离匹配度。

(19)

4.3 基于匹配模板的外观模型建立

设X∈Τm为对象m的匹配模板空间中的一个模板,其在图像中的参数为tX={ΦX,xX,yX},其中,ΦX为其在模板库中对应的模板,(xX,yX)为模板在图像中的坐标。它的内部和外部区域大致指示了对象和背景区域,通过对各区域中的像素进行采样,建立对象和背景外观的高斯混合模型ΘX。则式(5)中的P(di|Θ)为

(20)

其中,M为高斯混合模型中的成分数,M=5;Θ={αm,θm|m=1,2,…,M},θm=(μm,∑m)为高斯混合模型的参数(αm为混合参数,μm为均值向量,∑m为斜方差矩阵)。

4.4 基于模板库的对象分割问题求解

在确定了图像中各对象的匹配模板取值空间,空间中各模板的权值和在图像中的匹配位置,以及由匹配模板所确定的对象和背景外观模型以及轮廓信息后,就可以如建立式(15)所示的能量函数,利用图割方法求解,能量函数到图拓扑的映射关系如表1所示。

5 实验与讨论

本文基于模板库的自动对象分割方法的开发运行环境为普通个人计算机、Windows XP操作系统、Visual C++ 6.0。预设能量函数中的参数ρ=50.0,ω=6.0,δ=2.0。

表1 基于模板库的能量函数到图拓扑弧容量的映射表

图5所示为图3中的瓶子对象经确定匹配模板空间后基于模板库的自动分割结果。图6为当图像中有多于一个对象与模板库中模板匹配时,自动分割的结果,它们根据各自匹配模板取值空间及对应信息分别构建图拓扑进行求解。

图5 自动分割结果

图5和图6所示的效果验证了基于模板库的自动对象分割方法的正确性和有效性,在建立典型的瓶管状对象的模板库后,本文方法可以对大部分具有相似形态的对象自动地分割出较正确的结果,且对于一般形态的对象,只需在模板库中随时添加相应模板即可进行自动分割,不再需要任何人工干预。但是若存在阴影或者对象和背景外观部分严重重叠等复杂情况,匹配模板不一定能较好切合待分割对象,则可能导致分割结果的边界出现一些瑕疵,如图7所示,从而使分割结果因没有完整边界而失败。

图6 图像含多个匹配对象的分割结果

图7 自动分割失败示例

6 结语

首先利用随机场模型来结合低层图像数据和高层先验知识对对象分割问题进行统一建模,并根据马尔科夫随机场与Gibbs分布的等价性以及贝叶斯最大后验概率准则进一步将对象分割问题转化为能量函数最小化问题,这样我们只需专注于随机变量所对应的图像元素和标签的选定、能量函数的定义以及能量函数最小化方法的选择。实验结果表明此方法在确保分割速度的前提下,可以获得较高的准确度,这在数字图像处理、计算机视觉领域中是非常必要的。一方面,良好的对象分割效果是处理更高层的问题(如:图像分析、图像理解等)所不可缺少的关键环节;另一方面,在实际生活中,它的应用涉及影视特效、医学影像处理、工业检测等等,覆盖了从工、商业到艺术、文化等各个领域。

[1]K. Mikolajczyk, C. Schmid. A performance evaluation of local descriptors[J]. PAMI,2005,27(10):1615-1630.

[2]N. Dalal, B. Triggs. Histograms of oriented gradients for human detection[C]. CVPR,2005(1):886-893.

[3]Matas, J., Chum, O., Urban, M., et al. Robust wide-baseline stereo from maximally stable extremal regions[J]. IVC,22(10):761-767.

[4]Per-Erik Forssen, David G. Lowe. Shape descriptors for maximally stable extremal regions[C]//Rio de Janeiro:ICCV,2007.

[5]E. Borenstein, S. Ullman. Learning to segment[C]//ECCV, Springer(LNCS),2004,3023:315-328.

[6]E. Borenstein, J. Malik. Shape guided object segmentation[C]//CVPR,2006.

[7]Li, Stan. Z. Markov Random Field Modeling in Image Analysis(3rd Edition)[M]. Berlin:Springer,2008.

[8]Boykov Y, Kolmogorov V. An experimental comparison of mincut/maxflow algorithm for energy minimization in vision[J]. PAMI,2004,26(9):1124-1137.

[9]邱志敏,李军,葛军,等.基于Hausdorff距离的自动目标识别算法的研究[J].红外技术,2006,28(4):199-202.

[10]Felzenszwalb P, Huttenlocher D. Distance transforms of sampled functions[R]. Cornell University, TR2004-1963,2004.

AutomaticImageObjectSegmentationApproachResearchBasedonTemplate-library

XU Qinghua WEI Xiaolei LI Zhongliang

(Naval Marine Academy, Guangzhou 510430)

For some objects with different appearance but following definite mode on contour in the real-world, a template-library-based automatic object segmentation approach is provided. First of all, template is used to describe the object contour, and build a template library as the prior knowledge of objects. Afterward, the unknown matched template is regarded as a hidden variable, and by matching the bit-encoded composited template and image features, the value space of variable is determined. Then the integral operation is utilized to get the marginal probability of the labeling given the image data. Finally the energy function is solved corresponding to the marginal probability to achieve template-library-based automatic object segmentation. Experimental results demonstrate that the approach is accurate and effective.

object segmentation, graph cut, template, energy function

2013年11月15日,

:2013年12月17日

徐清华,男,硕士,讲师,研究方向:计算机仿真。

TP391.4DOI:10.3969/j.issn1672-9730.2014.05.026