基于质心高度增量特征的目标识别算法

于 洋,郑 伟,宋建辉,刘砚菊

(沈阳理工大学自动化与电气工程学院,辽宁 沈阳 110159)

1 引言

目标识别与匹配作为计算机视觉领域的研究热点,广泛应用于图像检索、人脸识别、医学影像分析等领域。因为物体的形状具有十分稳定和重要的视觉特征,所以形状一直是目标匹配中一项有效且利用率较高的特征[1]。形状表示方法可以大体上分为三类:基于轮廓的形状表示、基于区域的形状表示和基于骨架的形状表示[2]。基于轮廓的表示方法是在提取图像轮廓的基础上对其外部边缘进行描述。国内外学者对基于轮廓特征的目标识别方法展开了广泛研究,提出了大量描述轮廓特征的方法[3]。

Belongie等[4]提出的形状上下文描述符,作为近年来最具有代表性的轮廓描述方法,因识别效果良好、抗干扰性强等优势被广泛应用于形状检索领域,但该描述符不具有旋转不变性。吴晓雨等[5]提出一种具有旋转不变性的形状上下文识别算法,通过寻找采样点最多的角度区间的方法改变图像角度,为形状上下文描述符加入旋转不变性。张桂梅等[6]将内部距离代替欧氏距离,提出内距离形状上下文描述符,对于存在非刚性和肢体变化的目标取得了较好的识别效果,但描述符构建复杂,计算量大。Mokhtarian等[7]提出曲率尺度空间描述符,对于边界噪声以及尺度变化具有良好的鲁棒性,但需要对轮廓进行进一步演化,增加了特征提取的工作量,且识别精度较低。Alajlan等[8]提出基于三角形区域表示的形状描述符,有效的获取了目标的全局以及局部信息,但该方法识别鲁棒性差,对相似形状的区分能力较低。

为解决传统目标识别算法识别准确率低、复杂度高等问题,本文提出基于质心高度增量特征的目标识别算法,根据轮廓点相对于质心高度的变化构建质心高度增量形状描述符,该描述符对于目标形状的平移、旋转、缩放以及翻转具有很好的不变性,引入轮廓顺序这一全局特征和平滑化处理降低描述符对噪声和非线性形变的敏感性。最后引入动态规划和形状复杂度分析相结合的方法实现目标的匹配识别。实验结果证明,与形状上下文等传统算法相比,本文算法能获得更稳定、准确的识别效果。

2 质心高度增量描述符

对于目标图像,首先选用Canny分割算法提取其边缘轮廓,对提取的轮廓均匀采样,得到轮廓部分点集记为P={pi}(i=1,2,…,N),其中N为采样点的个数,pi为轮廓第i个采样点。设采样点pi(xi,yi),轮廓质心W(x0,y0)的计算公式如下

(1)

目标轮廓提取及采样结果如图1所示,图1中(a)表示目标图像;(b)表示提取的目标轮廓;(c)表示轮廓采样点及质心分布。

图1 轮廓提取及采样效果图

要计算轮廓的质心高度增量,最重要的是求出采样点与质心的距离,即质心高度值,该值表征了采样点在轮廓上的位置,对于采样点pi(xi,yi),定义质心高度gi为该点与质心W(x0,y0)的欧氏距离,即

(2)

这样可以得到轮廓N个采样点的质心高度值,定义任一采样点pj(j=1,2,…N)与当前采样点pi的质心高度的差值为质心高度增量hi,j,即

hi,j=gj-gi(j=1,2,…N)

(3)

质心高度增量有正有负,正负号可以精确地表示点与点相对于质心的位置关系。由于轮廓顺序是一种自然存在的全局特征,可以与质心高度增量这一局部特征融合使用,因此将所有采样点相对于点pi的质心高度增量按轮廓点顺序排列,得到采样点pi的质心高度增量序列Hi,如式(4)所示

Hi=(hi,i,hi,i+1,..hi,N,hi,1,..hi,i-1)T

(4)

图2给出了不相似轮廓采样点的质心高度增量特征提取效果图,其中图(a)、(b)表示心形轮廓和蝙蝠轮廓均匀采样,分别标记了3个轮廓点A、B以及C;图(c)、(e)、(g)分别为心形轮廓A、B、C三点对应的质心高度增量特征,图(d)、(f)、(h)分别为蝙蝠轮廓A、B、C三点对应的质心高度增量特征。从图2可以看出,轮廓上的不同采样点,其质心高度增量特征具有唯一性,可以用来描述轮廓信息。将形状轮廓P上每个点对应的质心高度增量序列Hi按照轮廓点顺序排列,得到一个尺寸为N×N的矩阵:

图2 不同形状采样点的质心高度增量描述符

L(P)=(H1,H2,…,HN-1,HN)

(5)

式中L(P)表示轮廓的质心高度增量矩阵,矩阵的第i列表示轮廓P上采样点pi的质心高度增量描述符。该描述符描述了轮廓点与点之间的相对高度关系,不随轮廓的旋转和平移而变化,为使该描述符具有缩放不变性,对矩阵的每一行进行归一化处理

(6)

式(4)定义了采样点pi相对于轮廓所有采样点的质心高度增量,这样虽然有效的描述了轮廓信息,但对噪声引起的轮廓局部变形过于敏感,同时特征维数过高、计算复杂,在此采用文献[9]中的策略,在描述符的精确性、抗噪性、简洁性之间取得一个很好的折中,具体过程如下:

对于pi点的质心高度增量可表示为

(7)

该序列包含了N个元素,对应N个采样点相对于该点的质心高度增量,加入正整数系数k(1

(8)

式中t=1,2,…M。把M个均值数据进行有序排列,得到点pi经过平滑化处理后的特征序列Gi,即

Gi=(gi,1,gi,2,….gi,M-1,gi,M)T

(9)

经过平滑处理后,不仅提高了描述符对轮廓变形以及噪声干扰的鲁棒性,同时降低了特征向量的维度,方便后续的匹配。将所有采样点平滑后的描述符按序排列,得到轮廓P的质心高度增量特征矩阵E(P):

E(P)=(G1,G2,…,GN-1,GN)

(10)

3 形状相似性度量

在获取形状的特征描述符后,计算两个形状的相似程度,由于质心高度增量描述符包含轮廓点集顺序这一全局特征,本文选取了动态规划算法对得到的形状特征进行匹配。

3.1 基于动态规划算法的相似度匹配

质心高度增量描述符刻画的是轮廓点与点之间的特征关系,首先计算两个形状上采样点间的匹配代价,不同轮廓采样点之间的特征越相似,匹配代价越小。假设采样点pi和qj分别属于形状P和Q,定义匹配代价为pi、qj两点对应的质心高度增量特征Gi和Gj之间的距离。考虑到接近采样点pi和qj的质心高度增量的作用更大,为此设计权重系数wt突出轮廓的局部特征,计算公式如式(11)

(11)

在此基础上,得到匹配代价c(pi,qj)的计算公式如式(12)

(12)

式中d(gi,t,gj,t)表示pi、qj两点在其质心高度增量第t个分量上的数据差值。

在获得了任意两个点的匹配代价后,进行轮廓点集间的匹配,采用动态规划算法进行匹配,确定对应关系使得轮廓间每对轮廓点的匹配代价的总和最小,设形状P的采样点pi与形状Q中的采样点τ(pi)相匹配,则两个形状的距离差异定义为:

(13)

其中c(pi,τ(pi))为采样点pi和τ(pi)之间的匹配代价。由于形状的复杂度越高,对轮廓局部变形的敏感度越低,识别出的结果越具有可信性,因此引入形状复杂度进一步提升轮廓的匹配效果,定义形状轮廓的复杂度为:

(14)

式中std表示标准差.通过引入形状复杂度最终得到两个形状之间的距离S(P,Q):

(15)

式中C(P)和C(Q)分别为形状P和Q的复杂度,η为调整分母大小的参数,根据经验可适当调整。

此外实际识别过程中,往往会出现待识别目标存在翻转的情况,容易造成误匹配,因此采取一个简单的策略:将待检测目标P进行翻转得到形状PF,将形状P和PF分别与形状Q匹配,取两者中匹配的最小距离作为形状P和Q的最终匹配结果。

本文算法的结构框图如图3所示。

图3 算法框图

4 仿真与分析

为验证本文提出的目标识别算法的有效性,分别在MPEG-7和Kimia99这两种常用测试集上进行图像的匹配实验,并对算法的抗噪性能进行测试。在实验中,轮廓的采样点数取N=100,式(8)中的平滑系数取k=5,式(15)中调整分母的参数取η=0.45。

4.1 MPEG-7测试集识别测试

MPEG-7测试集包含70类形状,每类20张图片共1400张图片,涵盖动物、物体等多种形状,包括了形状的各种线性变换以及肢体变化、遮挡等非线性形变。采用Bull-eye得分获取本文算法在MPEG-7测试集上的检索识别性能,检索率定义为:对测试集中的每一个形状,识别出与其最相似的40个形状,统计这些形状中属于待识别形状类别的数目,对所有形状的统计数据求和之后除以28000(1400 × 20),即得检索率。表1所示为本文算法和其它部分算法在该测试集上的识别结果。从中可以看出,本文算法可以取得较好的识别效果,检索率达到了93.05%,优于表中提出的几种常用目标识别算法,较SC和CSS算法的优势尤为明显。

表1 MPEG-7测试集检索精度

表2给出了本文算法在MPEG-7测试集上的部分目标匹配结果,其中第1列为待测目标,第2～9列为匹配结果以及对应的形状距离值,待测目标1st～8th的形状距离值从小到大,表示与其第1到第8相似的识别结果,可以看出本文提出的算法能够较好的实现目标形状的识别。

表2 MPEG-7测试集部分目标匹配示例

4.2 Kimia99测试集匹配测试

Kimia99测试集包含9类形状,每类11张图片共99张,如图4所示。该测试集同样包含了形状的旋转、平移以及缩放等几何变换,被广泛应用于目标识别与分类中。对于测试集中的每个形状,统计出与其第1到第10相似的识别结果中识别正确的形状数目(不包含待识别目标本身),将所有形状的统计合计结果作为本文算法在Kimia99测试集上的检索表现,因为测试集共有99个形状,所以每组数值的最佳结果便为99。

图4 Kimia99图像测试集

表3给出了不同方法在该测试集上的识别结果,从中可以看出相较于其它算法,本文算法识别效果最佳,优于SC和IDSC等常见目标识别算法。

表3 多种方法在Kimia99测试集上的检索结果

本文算法在MPEG-7和Kimia99测试集上均取得优异的识别效果,这取决于以下原因:1)质心高度增量描述符对轮廓特征表达精确,这种轮廓点之间精细的描述提高了相似形状的类间区分度;2)无论是形状上下文还是内距离形状上下文,都是将轮廓点分散到各个区域,破坏了轮廓顺序这一全局特征,而本文方法则是将这一全局特征与质心高度增量特征有机的结合起来,有效的提升了识别准确率;3)本文将形状复杂度分析与动态规划相结合进行匹配识别,在动态规划求得形状相似度的基础上,通过评价轮廓的复杂度进一步提升了匹配结果的可信度。

4.3 噪声干扰下的检索效果测试

为测试本文算法的抗噪性能,本节对带有噪声的形状轮廓进行识别,获得带噪轮廓的方式如下:对Kimia99测试集的所有图片轮廓点的横纵坐标加入均值μ=0,标准差由σ=0.2到σ=0.8的高斯噪声,分别统计出与其第1到第10相似的识别结果中识别正确的形状数目(不包含待识别目标本身),将所有形状的统计合计结果作为本文方法在受到噪声干扰的Kimia99测试集上的检索结果,表4给出了本文方法在噪声环境下的检索结果。

表4 本文方法在受到噪声干扰的Kimia99测试集上的检索结果

由表4可以看出,噪声水平在0-0.4之间时,检索表现受噪声影响不大,噪声水平在0.6-0.8之间时,检索效果出现了较大程度下降,但仍能保持较高的识别精度。由此验证,本文方法对于轮廓噪声干扰的鲁棒性较强,这得益于本文算法引入轮廓顺序信息这一全局特征,对噪声干扰的敏感性降低,同时采用平滑技术处理特征向量,也有效提高了本文算法对于轮廓噪声的鲁棒性。

4.4 算法空间复杂度分析

目标识别算法的空间复杂度主要体现在形状特征描述符对应的数据量上,在形状数量S和轮廓采样点N一致的情况下,描述符的特征维度决定了算法的空间复杂度,根据本文实验对参数的最优设定,采样点数取N=100,平滑系数取k=5,本文描述符特征维度为M=[N/k]=20。表5给出了选取相同轮廓时,在轮廓采样点数均为N=100的情况下不同描述符的特征维度:SC描述符[4]直方图距离量化等级和角度量化等级分别为5和12,特征维度为60;IDSC描述符[6]中取直方图距离量化等级和角度量化等级分别为8和12,其特征维度为96;TAR描述符[8]特征维度为M=[(N-1)/2]=44;CSOPT描述符[14]中平滑系数取k=3,特征维度为M=[(N-1)/k]=33。通过分析可以看出,本文描述符的特征维度(20)明显低于上述经典描述符,由此可以看出,本文算法相较于其它常见算法在空间复杂度上有着显著的优势。

表5 不同描述符特征维度比较

5 结论

本文提出了基于质心高度增量特征的目标识别算法,在特征提取阶段,构造质心高度增量形状描述符,该描述符有效的描述了轮廓的全局以及局部信息,不仅计算简单,具有旋转、平移、缩放不变性,而且对于噪声和轮廓局部形变具有良好的鲁棒性。在目标匹配阶段选用动态规划算法进行形状匹配,同时引入形状复杂度分析提升了识别效果。通过对MPEG-7和Kimia99测试集进行仿真,证明了本文算法能取得良好的识别效果,且在复杂度、抗噪声干扰、识别准确率等方面的性能优于常见的目标识别算法。