基于曲率特征的轮廓匹配方法_张志刚

Co m puter Engineering and A pplications 计算机工程与应用2008, 44(14) 　　57

基于曲率特征的轮廓匹配方法

张志刚, 周术诚, 马　君, 罗养霞

1211

ZHANG Zhi 2gang , Z HOU Shu 2cheng ,MA Jun , LUO Yang 2xia

1. 西安财经学院信息学院, 西安710061

2. 福建农林大学计算机与信息学院, 福州3500021. Depart m ent of I nfor mati on, Xi ’an University of Finance and Econom ics, ’an 2. College of Computer and I nf or mati on, Fujian Agriculture and Forestry E 2mail:zhoushuch@s ohu . com

ZHANG Zh i 2gang, ZHO U Shu 2cheng, M A et l 1Con i n on curva ture fea ture 1Co m puter Eng i n eer i n g and Appli ca ti on s, 2008, 44(14) :57-58.

Abstract:Cont by app r oxi m ati on . Next, curvature of polygonal vertices are calculated by Her m ite inter polati on . is measured by Hausdorff distance 1For geometrical characters of cont our have been taken advantage, this t o r otati on and has better perf or mance on p recisi on and s peed . Key words:cont our matching; curvature; Hausdorff distance

1

2

1

1

摘　要:首先对轮廓曲线进行多边形近似, 然后通过Her m ite 插值曲线求出多边形各顶点的曲率作为特征, 最后以Hausdorff 距离为准则进行轮廓线匹配。算法充分利用了轮廓线的几何信息, 匹配速度快, 准确度高, 具有一定的旋转不变性。关键词:轮廓匹配; 曲率; Hausdorff 距离DO I:10. 3778/j . issn . 100228331. 2008. 14. 015文章编号:100228331(2008) 1420057202文献标识码:A 中图分类号:TP391

1　前言

物体轮廓线的匹配是计算机视觉和模式识别中一个非常活跃的研究课题, 在指纹识别, 零件自动装配, 及碎片物体复原等领域都有着广泛的应用。关于这方面, 人们已经进行了大量的研究工作。文献[1]提出了一种基于多尺度的曲率的匹配方法, 其中曲率的计算占了很大的工作量。文献[2]给出了一种严格限制的方法, 设两条曲线, 其中一条是另一条的完全子曲线, 要搜索完全匹配且距离平方最小的对应子曲线段, 要计算子曲线的位移和旋转角度。文献[3]采用了同心圆技术, 求交点的计算量很大, 采样步长的选取较难。以上匹配算法或者计算复杂, 运算量大, 或者精度不高。在上述研究基础上提出了一种轮廓匹配方法:首先求出轮廓线的特征点作为多边形的顶点, 再利用Her m ite 插值求出各顶点处的曲率作为特征, 以Hausdorff 距离进行轮廓线的匹配。算法充分利用了轮廓线的几何信息, 计算简便, 匹配结果不受旋转, 位移等变换的影响。

边形表示法, 它可以检测出最大曲率, 而且与其它曲率拟合方法相比更容易实现。考虑到受输入设备, 或物体本身等因素的影响, 数字图像中的轮廓常常存在着很多冗余点和噪声, 剔除这些冗余点将提高后续多边形近似的精度及匹配的速度, 因此首先利用算法[4]对轮廓进行预处理:设原始轮廓线被表示为平面上的一个点列C ={p i (x i , y i ) |i =1, 2, …, N }, p i 和p i +1互为邻点(模N ) , 以p i 为起点, 依次判断C 中p i +1以后的点到直线p i p i +1的垂直距离, 剔除那些距离小于阈值ε的点, 直至检测到大于ε的点p j , 再以p j -1为新的起点重复上述过程, 直至C 中的点都被处理完毕, 这样得到了一个新的特征点集C ′={q i (x i , y i ) |i =1, 2, …, M }, (M

。

2　轮廓匹配算法211　预处理

提取二维物体的轮廓特征是整个匹配算法的基础。目前物体形状的表示常用两种方法:一种是诸如链码那样的原始表示方法; 另一种是分段光滑曲线逼近法, 逼近法中常用的是多

图1　预处理方法示意图

由于算法本身的局限, 上述所得多边形不一定能保证检测到曲线上的高曲率点, 因此需要在此基础上排除不重要的特征点, 获取更为简化, 有效的多边形近似表示, 这里采用一

基金项目:福建省自然科学基金(the Natural Science Foundati on of Fujian Pr ovince of China under Grant No . S0650005) 。

作者简介:张志刚(19702) , 男, 博士, 讲师, 主要研究领域:数字图像处理; 周术诚(19652) , 男, 博士, 副教授, 主要研究领域:图形图像处理;

马君(19632) , 女, 教授, 主要研究领域为软件工程、信息处理; 罗养霞(19742) , 女, 讲师, 主要研究领域为网络安全信息安全。

收稿日期:2007208228　　修回日期:2007211215

　2008, 44(14) 58　Co m puter Engineering and A pplications 计算机工程与应用

种基于邻域质心的方法来检测特征点[5], 设最终得到的轮廓的特征点集为C ″。

可能出现的误匹配, 可通过比较两个轮廓的周长或面积等方

法进行校验。

212　计算曲率

为进行轮廓匹配需要将轮廓曲线转换为一列形状信号描述的序列, 它们应体现曲线的特征, 符合这种描述最自然的属性是曲率, 因为一条2D 曲线与它的曲率函数间存在着一一对应的关系, 且曲率具有位移, 旋转不变性。但是对于数字曲线的离散化表示, 曲率的定义只能采用近似的方法来逼近连续的情况[6]。设曲线方程为s =s (t ) , 曲率的计算公式为

:

3　实验与结论

实验对象摄自一张任意撕扯后的纸票, 经轮廓提取, 细化处理后得到了轮廓曲线。图3(a ) 即为物体的原始轮廓线, 图3(b ) 、(c ) 是原物又被撕扯后的轮廓线, 与图3(a ) 相比残缺较大。图3(d ) 保存基本完整, , 且旋转了约30°左右。图3(e )

～(h ) 在利用, , , d ) 3(a ) 的匹配度最高。通过实验, , 且对轮廓曲线的旋转具有一定的由上一步得到轮廓的特征点集为C ″, 由它们组成了新的多边形, 将多边形上相邻三个顶点(p i -1, p i , p i +1) 圆弧上的三个点, p i 斜率, 如图2所示, 线段p i -1p i 和p i p i o , p i 点且垂直于op i 的直线L p i , 记为m i ,

图2　计算一阶导数

依次求得各点的一阶导数后, 每个子区间[p i , p i +1]上的三次Her m ite 插值曲线为:

　P i (t ) =H 0(t ) p i +H 1(t ) p i+1+H 2(t ) m i +H 3(t ) m i+1(2)

式中的H i (t ) |i =0, 1, 2, 3为混合函数, 对上式求二阶导数可得:

(0) =-6p i +6p i+1-4m i -2m i+1p i ″

(3)

图3　轮廓匹配实验结果

综合式(1) 、式(3) 可得p i 处的曲率为:

k (p i ) =

-6y +6y -4m -2m 1+m i

2

2

(4)

本文提出了一种轮廓曲线的匹配方法, 主要特点包括:首先通过预处理检测轮廓曲线的特征点, 再通过Her m ite 插值曲线求取各顶点的曲率, 该方法计算简便, 精度较高; 以Haus 2dorff 距离为准则进行轮廓线的匹配, 由于充分利用了轮廓线的特征信息, 匹配计算仅在少量的特征点集间进行, 故大大提高了算法的速度。

由上可得多边形上顶点p i 的曲率由p i -1, p i , p i +1, p i +24点决定, 因为轮廓线是封闭的, 因此每个顶点两边相邻点一定存在。按上述步骤可求得多边形上每个顶点的曲率。

参考文献:

[1]Leitao H C G, St olfi J 1A multi 2scale method for the re 2asse mbly of

frag mented objects [J ].I EEE Transacti ons on Pattern Analysis and Machine I ntelligence, 2002, 24(9) :1239-1251.

[2]Shwartz J T, Sharir M 1I dentificati on of partially obscured objects in

t w o di m ensi ons by matching of noisy characteristic curves[J ].I nter 2nati onal Journal of Robotics Res, 1987, 6(2) :29-44.

[3]Mather A 1Planar curve rep resentati on and matching[J ].I EEE Trans 2

acti ons on Pattern Analysis and Machine I ntelligence, 1995, 17(2) :167-174.

[4]LeungM K 1Dyna m ic stri p algorithm in curve fitting[J ].ComputerV i 2

si on Graphics &I m age Pr ocessing, 1991, 51:146-165.

[5]张志刚, 周明全1一种轮廓曲线的多边形近似算法[J ].计算机应

213　轮廓匹配

设有两组有限集合A ={a 1, a 2, …, a p }和B ={b 1, b 2, …,

b q }, 则A 、B 间Hausdorff 距离定义为

a i ∈A b j ∈B

[7]

:

　H (A, B ) =max (max m in ‖a i -b j ‖, max m in ‖b j -a i ‖) (5)

b j ∈B a i ∈A

式中║3║表示某种定义的距离范式, 括号内两项分别称为

A -B , B -A 的有向距离。Hausdorff 距离度量的是两个集合间的最大不匹配程度, 且计算简便, 也不苛求两个集合中点与点之间的一一对应关系, 因此很适于图像的匹配。

设两轮廓线的特征点曲率集合为C 1={k 1i |i =1, 2, …,

m }, C ={k j |j =1, 2, …, n}, 其中k i 和k j 分别是两个轮廓线

2

2

1

2

用, 2006, 26(3) :577-578.

[6]周石林, 廖文和, 王琪1平面非规则曲线匹配的一个判定条件[J ].

多边形近似后各顶点处的曲率值, 这里m 和n 不一定相等。在轮廓匹配时, 按上式计算两个曲率集的Hausdorff 距离, 其中值最小的一对即对应为可能匹配的轮廓对。与一般Haus 2dorff 距离较常采用的欧式距离度量不同, 这里的距离范式仅仅是曲率值的简单比较, 因此可大大提高算法的效率。对于

南京航空航天大学学报, 2003, 35(5) :561-564.

[7]Huttenl ocher D P, Klander man G A, Rucklidge W J 1Comparing i m a 2

ges using the Hausdorff distance[J ].I EEE Transacti ons on Pattern A 2nalysis and Machine I ntelligence, 1993, 15(9) :850-863.