一种求曲线极小特征点集的算法樊宏斌1,耿国华1,2,周明全1(11西北大学计算机科学系,陕西西安710069;21中国科学院自动化研究所模式识别国家重点实验室,北京摘要:在分析已有求数字曲线特征点集算法的基础上,提出了一种求数字曲线极小特征点集的递归算法。结果表明,该算法具有提取特征点集冗余小、准确度高、速度快、节省存储空间,并且搜索出的点更加适合表达曲线形状等特点。关键词:模式识别;拐点;曲线匹配文章编号:10002274X(2002)0220166203中图分类号:TP391.41文献标识码:A物体的形状特征在图像处理、模式识别及计算机辅助设计等多个领域有着广泛的应用。特征点是数字曲线上的高曲率点和曲线变化的关键点,它包含着物体形状的重要信息。因此,快速准确的提取一个数字曲线上极小特征点集的算法对曲线的形状匹配等应用是必不可少的。一个好的求曲线上极小特征点集的高性能算法不仅应该具有好的时间复杂进行选取,直到全部的点被筛选完为止。最后所选取的点的集合就是我们所要的结果。条带算法的一个缺点是,如果第3个点c落在条带外,那么拟合的曲线非常短,几乎达不到要求的目的。因此,从条带算法发展而来的有动态单、双条带算法,在克服这个缺点时都采取了一定的策略。由于条带算法采用的都是局部的错误容限法,是从局部出发的,缺少全局的考虑,它不一定能保证曲线上的高曲率点被找到。如果曲线的点数密度非常高,如通过等值线方法提取的图像上的点一般至少都是像素级的,甚至通过像素间插值得来的等值线比像素还要高一个级常见的求曲线特征点的算法1目前常用的方法主要有条带算法1,2。条带算法实质上是一个错误容限法,即就是给一个门限阈值,去控制筛选条件来得到想要的点。其基本思想如图1所示,以起始点a及与它相邻接的第一个点b组成中轴线,给定一个门限阈值l,以a,b点所在的直线为中轴线,以l为宽度求出它的上下界限,然后判断b点以后的点序列。依次计算这些点到条带的中轴线距离,如果点的距离大于l的值,如图1中的e点,以它的前一个点d与第一个点a组成的直线段代替由bbd组成的曲线接着以d为起始点图1条带算法原理图Fig.1Theprincipiumofstripalgorithm另外还有一类多边形逼近法,其算法的基本思想为:设数字曲线C由n个点组成,C表示第i个ni点。其算法思想是对Cn中的任意n1个点组成的曲线求它们的面积,然后与Cn的面积作比较找出一个差值最小的n-1个点集合。我们记这个曲线为Cn-1。那么消除的那个点是对Cn的形状影响最小的点,在对Cn-1用同样的方法求Cn-2,依次类推。在给定准则下可以找出一个序列的点集,但这种算法的缺点是空间与时间的费用高,并且找所需要的点序列的准则不好把握。因此,我们提出一个新的求极点,那么对递归算法的准确度就有一定的影响。2.2起始点与起始分段点的确定新的递归算法与起始点和起始分段点有一定的关系,起始点和起始分段点是求最小特征点集算法的初始点。因此,它们必须是曲线上的特征点,而且两个关键点选取的不同对所求的拐点集合的冗余量有一定影响。如果关键点选取的合理,所求的拐点集合,不但冗余量小,而且能更准确地描述原曲线的形状特征。求起始点和起始分段点,即找出两个最具有曲线几何特征的点,一般的方法是选取曲线上距离最大的两点,因为在数字曲线上,距离最大的两点代表了曲线的重要特征,并且影响曲线的形状信息。所以,在一般情况下,选取这两个点做为起始点和起始分段点。同时也可以曲线的几何中心为依据,结合具体应用,运用以上方法或别的方法找出这两个关键点。2.3算法的描述递归算法的基本思想为:1)用2.2中的方法,在点集Cn中求出一个起始点Pf与一个起始分段点Pl,并将Pf与Pl加入Cm中。2)求出Pf与Pl后,以这两个点做连线,把原始Cn分成两个有序点的子集Ca与Cn-a,此时Cn=Ca∪Cn-a∪{Pf,Pl}。对每个点Pk∈Ca,计算它的Lk(i,j),其中Pi=Pf,Pj=Pl;选取最大的Lk(i,j)所对应的Pk点。采用同样的方法,在Cn-a中求取一个点Pk′,同时得到Lk′(i,j)。3)如果Lk(i,j)大于或等于Lmin,则Pf,Pk和P2新算法的描述设Cn={P1,P2,P3,数字曲线的有序点集,Pi(i=,Pn},Cn是平面上的1,2,,n)是曲线的第i个点,Lk(i,j)表示点Pk到Pi和Pj所在直线的距离。距离门限阈值为Lmin,Cm为求得Cn点集中的极小特征点...