一个抽取边界曲线特征点的新算法

1、一个抽取边界曲线特征点的新算法 3刘勇奎 , 刘向东 , 王春霞(大连民族学院 , 辽宁 大连 116600 )摘 要 : 景物的特征点抽取是模式识别及计算机视觉中的一个重要问题 ,已出现的多种检测特征点的方法中主要有角检测法和多边形逼近法 。在这两种方法基础之上 ,人们又提出了结合两种方法的综合方法 。提出了一种 新的综合方法 ,首先应用一个简单的角检测方法 ,然后利用前面计算曲率时的一些值在检测到的角点之间加入一些特征点 。实验结果表明新方法比传统方法执行速度更快 ,并且克服了传统方法的缺陷 。关键词 : 模式识别 ; 曲率 ; 特征点 ; 角检测 ; 多边形逼近文章编号 : 100123

2、695 ( 2006) 06 20148 205中图法分类号 : tp391文献标识码 : ao n d e tec tion of dom inan t po in ts on cu rve s of o b jec t con tou rl iu yong2ku i, l iu x iang2dong, wan g chun2xia(d a lian n a tiona lities u n iversity, d a lian l iaon ing 116600, c h ina)a b stra c t: d e tec ting dom inan t po in ts is an i

3、mpo rtan t sub jec t in p a tte rn recogn ition and comp u te r vision. co rne r de tec tion andpo lygona l app roxim a tion a re two m a jo r app roache s fo r dom inan t po in t de tec tion. b a sed on the two app roache s, com b ined m e2 thod s have been p ropo sed. in th is p ap e r, a new com

4、b ined m e thod is p re sen ted to de tec t the dom inan t po in ts. the new m e thod first app lie s a simp le co rne r de tec tion p rocedu re, then add s som e po in ts be tween de tec ted co rne r po in ts w ith the va lue of cu rva2 tu re comp u ta tion. exp e rim en ta l re su lts show tha t t

5、he new com b ined m e thod is mo re effic ien t than the conven tiona l m e thod s.a nd it ove rcom e s som e defec ts in the conven tiona l m e thod s.key word s: pa tte rn r ecogn ition; cu rva tu re; dom inan t po in ts; co rne r d e tec tion; po lygona l app roxim a tion之上 ,人们又提出了结合两种方法的综合方法 6,

6、7 。这种方法的一般步骤是 :先通过应用角检测方法得到曲线的角点 ,这些 点已是曲线的特征点 ,但不够完全 ; 再使用多边形逼近法在两 个连续角点之间分割曲线 ;最后把这些检测到的角点和分割点 作为曲线上的特征点 。本文将上述几种方法相结合 ,给出一种计算量小 、执行速 度快的综合方法 ,并且克服了前面提到的传统方法的缺陷 。1 引言景物的特征点抽取是模式识别及计算机视觉中的一个重要问题 。如果要描述一个物体的形状 ,检测出物体边界上的特 征点是必不可少的 。所谓特征点就是能够代表边界曲线特征 的一些点 (如拐点等 ) ,并且从人的视觉角度考虑 ,这些特征点 能够表达曲线上足够的信息来描绘物体

7、轮廓的特征 。特征点的概念已经应用到轮廓识别算法 ,基于点的运动估计方法以及编码方法中 ,我们把一个物 体轮廓的特征点作为它的 一种标 志 。在这些应用 中 ,特征点 检测是非常重要的预处理 步骤 之一 。a ttneave有一个非常著名的结论 : 描述一条曲线形状的信 息集中在具有高曲率的特征点上 1 。许多算法就是基于这个结论 。到目前为止 ,已出现了多种检测特征点的方法 。主要可分为两大类 ,即角检测法 2, 3, 9 和多边形 逼近法 4, 5, 8, 10 。角检 测法的一般步骤是 : 逐点计算曲线上每一点的曲率 ; 找出 曲率较大的那些点作为特征点 。而多边形逼近法则是从最初点开始

8、 ,不断向两个最初点之间的曲线段中加入分割点 ,直到满足一定的条件为止 。加入分割点的原则是在允许的误差条 件下使各段曲线尽量地长 。最后曲线上的点就被定为是特征点 。由于这两种方法有各自的缺陷 ,因此 ,在这两种方法基础2 特征点检测方法研究现状在角检测算法中 ,首先介绍两种简单的曲率估计方法 ,它们分别是由 ro senfe ld与 john ston和 teh与 ch in提出的 。在多 边形逼近方法中 ,首先介绍分割曲线的连续逼近方法和迭代逼 近方法 。前者是由 w a ll和 d an ie lsson提出 ,而后者由 r am e r提 出 。然后 ,介绍一种由 w u和 w an

9、g提出的综合方法 。在介绍算法之前 ,我们先对数字曲线进行一下描述 ,使用n个整数坐标序列 , 即c = p = ( x ,y , i = 1, 2, , n i )i i其中 , 点 pi + 1是点 pi 的邻接点 (以 n 为 模 ) 。曲 线 c 的 f ree2m an编码由 n个向量组成 : ci = pi - 1 pi而且 , 每个向量均可由一个从 0 7 的整数表示 , 如图 1 所示 ,向量与 x轴的夹角为 f / 4。曲线链码定义为 ci , i = 1, 2, , n 且 ci = ci n收稿日期 : 2003203215; 修返日期 : 2005206207基金项目

10、: 国家自然科学基金资助项目 ( 60473108)去掉一些特殊情况 ,一个是 co si, h为 - 1 的点 ; 另一个是如果对于点 pi , 它的左或右相邻点 pi - 1或 pi + 1也保留下来 ,而 且 co si, h co si - 1, h或 co si, h co si + 1, h , 则去掉点 pi。( 4)把剩余的点作为曲线 c 的特征点 。212 多边形逼近方法多边形逼近就是用一个多边形来表示边界曲线 ,所以人们 就借助这种思想得到了曲线的特征点检测算法 。把逼近的多 边形的顶点 (也称为断点 )作为其特征点 。多边形逼近方法一般分为两类 ,即连续逼近方法和迭代逼

11、近方法 。连续逼近方法的一般过程是从曲线上的某一点出发 ,通过顺序地合并相邻点得到符合一定条件的一段曲线 ,它是原 来曲线的一个子集 ,然后把该段曲线的最后一点作为下一个起始点 ,进行合并下一段符合条件的曲线 。如此下去 ,直到整条曲线被遍历到 。这些得到的一系列起始点就作为特征点 。但 这个方法有个缺点 ,它会丢失一些特征点 。因此出现了迭代逼近方法 。此方法先选择两个起始点分割曲线 ,如果不满足规定的测试条件 ,则继续分割下去 。在两个起始点之间找到一点 ,把曲线分割为两条更小的曲线 ,这个分割点作为被分割后形成 的小段曲线的起始点之一 。这个过程将继续下去 ,直到没有进一步分割的必要 。

12、在这个算法中 ,终止曲线分割一般采取这样 的测 试 条 件 , 那 就 是 对 一 段 待 分 割 的 曲 线 间 所 有 的 点 , 满 足211 角检测方法角检测方法的目的是要检测那些能够描述物体边界上出 现方向突变的地方的点 ,它首先要估算曲线上每一点的曲率 。 在实域平面上 ,曲率定义为斜率的变化和弧长函数的比值 。对 于曲线 y = f ( x ) ,曲线上某点的曲率表达为导数的形式 ,即22 3 /2cur ( x) = d ydy1 +dx2dx而对于数字曲线 ,计算其离散曲率时如果只是简单地通过一个像素点的变化来替代上式中的导数值 ,那么斜率细微的变 化将无法在计算中反映出来

13、,因为数字曲线上连续的斜率角的变化是 45 的倍数 。在角检测算法中一般都是采用扩 大范围的方式解决这个问题 ,即 k 1 ( k 是该点左右像素点的个数 ) ,称这个 k值为平滑因子 , 利用这个 k值可以得到计算该点曲率 的支撑区域 。估算离散曲率的方法有很多 ,这些方法一般有这样一个宗 旨 ,那就是必须准确地反映曲线真正的曲率 ,在此基础上要尽 量减少计算量 。这里 引 入 两 种 方 法 : 由 ro senfied 和 john s2ton 2 提出的 ,如图 2 ( a)所示 ,用 co s 来估计曲线上点 p 的曲ii率 cur i ,基于这一点 ,我们称它为 co s方法 ,

14、pi 是曲线上第 i个点 。 由 teh和 ch in 3 提出的改进方法 ,如图 2 ( b)所示 ,使 用偏差与弦长的比值作为点的曲率 ,其中这 个偏差值是点 pi 到弦 pi - k pi + k的距离 di , 它决定了点 pi 的支持区域 , 即它决定 了对应于点 pi 的弦中 k值的取法 , 即用 di /l i 表示曲线上第 i 点的曲率 。d t 则不再分割下去 , 其中 d 仍为偏差值 , t 是偏差限度 。i did根据上面的方法 ,产生了多种检测算法 , 最常用的有 r a2m e r算法 4 和分割 合并算法 5 。其中 ,后者要比 r am e r算法复杂一些 , r

15、 em e r算法只是一个分割的过程 。下面是分割 合 并算法的概括性描述 :( 1)沿边界分配几个点作为初始断点 ,顺序地连接这些点 形成初始的多边形 。( 2)在每两个相邻断点之间 ,沿着这一曲线段找到距离两断点连线的垂直距离最大的点 。如果这个距离大于我们预先 设定的一个阈值 ,那么把这一点作为新的断点 。这就是算法中 的“分割 ”过程 。一旦曲率估算出后 , 下一步就判断曲率是否大于某一阈值 tg ,若大于 ,则该点被认为是角点 , 即特征点 。但一 般情况 下 ,并不是简单地这样做 ,而是分两步来做 : 给出一个曲率阈值 ,去掉那些因曲率太小而不可能是特征点的点 ; 这一步称 为非最

16、大值筛选 过程 , 它是 把第 步过滤剩余的点再 进行处理 ,去掉那些在该点支撑区域内曲率不是极大值的点 ,这样把 最终剩余的点作为此曲线的特征点 。下面是 ro senfe ld2john ston算法的简单描述 :( 1 )定义曲线上点 pi 的两个 k 2向量和 co sik :( 3)在相邻的两个线段上比较连续的三 个断点 ,如 a、b、c,计算出曲线段 ac上点到线段 ac 的最大距离 ,如果这个距离在阈值范围内 ,则去掉 b 点 。这就是算法中的“合并 ”过程 。( 4)重复步骤 ( 2 )和步骤 ( 3 ) ,直到达到一个平衡状态 ,没有再进行“分割 ”和“合并 ”的必要 。21

17、3 综合方法角检测方法可以检测出一些重要的角点 ,但是有时检测出 的这些角点并不能很好地表示原边界曲线 ,例如对于具有一长 段缓慢变化的曲线段的边界线 , 这样的曲 线上就检测不出角 点 ,而要进行特殊处理 ,如图 3 所示 。多边形迭代逼近方法对 起始点的设置比较敏感 ,不同的起始点可能导致不同的逼近结 果 ,因此起始点的选择对这种方法很重要 。如果把这两种算法 结合起来 ,就可以克服它们各自的缺点 。a ik = ( x i - x i + k , y i - y i + k )bik = ( x i - x i - k , y i - y i - k )a bik ik, co sik

18、=a ik bik其中 , co sik是 k 2向量 aik和 bik夹角的余弦值 ,且 - 1 co sik 1 ,当其为 - 1时 ,说明这是一直线段 。( 2 )选择一平滑因子 m (根据 曲 线 c 的 具 体 情 况 或 者 为n / 15, 或者为 n / 10 ) , 对 c 上 每 一 点 pi 计 算 co sik , k = 1, 2, m 。( 3 )根据下式选出对于点 pi 的支撑区域 h i, 并且得出的曲率值 co si, h i : 6 pi因此 , a n sa ri和 d e lp 首先提出了一种综合方法 ,它首先是在边界曲线上找到一系列曲率的极大值 ,然后

19、运用上面提到 的“分割 合并 ”多边形逼近算法来检测特征点 。co sim co si, m - 1 0; 当 dik tg then将 b i 放到 d i 集合中 ;ac0e lse acac + d si ;if | ac | td then 将 b i 放到 d i 集合中 ;a c0 ( 4 )一些必要的处理 ,去掉不必要的点 。对于第 ( 3 ) 步得 到的集合 d i , 若 集 合 中 点 支 撑 区 域 k = 1, 则 把 pi 从 集 合( 3)最大误差 ( em ) :定义为 em ax = m ax a i1im 512 与传统算法的比较对新算法与在第 2 节中介绍的

20、三种算法分别在以下几个 方面进行比较 : 特征点的个数 ; 逼近误差 e2 和 em ax ; 算 法的 cpu 运行时间 。在这里我们引入了两种物体对象进行测 试 ,如图 9 ( a)和图 11 ( a)所示 。一般说来 ,一个好的特征点检 测算法应该在物体的大小或者是旋转角度发生变化时保持一 种稳定性 。因此 ,这里我们对每个物体在这些因素变化时也进 行了测试和比较 。这些变化的曲线连同原边界曲线如图 9 ( a)图 12 ( a) 所示 ,并且在图 9 ( be) 图 12 ( b e) 中分别对co s方法 、分割 2合并方法 、co s2maxd 方法以及新方法所检测 到的特征点作了

21、标记 ,并且在表 1和表 2中对得到的测试结果进行了总结 。如图 9所示 ,我们对第一个物体的边界曲线进行了特征点表 2 对于图 11 和图 12 的边界曲线新算法与其他算法的比较检测 。可以看到 ,使用 co s角检测方法只检测到了四 个特征点 (图 9 ( b) ) ,很明显 ,四个点检测出的正好是物体的 四个角 点 。但是 ,用这些点并不能很好地逼近该边界曲线 ,因为在边 界曲线上还有两段弧线 。而其他的三种方法均检测到了六个特征点 (图 9 ( ce) ) ,这样就能够较好地描述这条曲线 。下面我们在来观察一下图 10 ( a ) , 它与图 9 ( a ) 是同一个物体的边 界 ,只

22、是旋转了一定角度 。可以看到 ,使用 co s方法和新方法与旋转前得到的结果相同 (图 10 ( b, e)和图 9 ( b, e) ) ,而在分割 合并算法和 co s2maxd 方法中 , 产生了过多的冗 余特征 点 (图 10 ( c, d) ) 。所以可以看出只有新方法不仅检测到了合 适的特征点 ,而且得到了较好的一致性结果 ,这说明对物体的方向 、大小不敏感 。在表 1 中我们给出了比较结果 , co s角检测方法有最大的均值误差 ,而其他三种方法在这一方面比较相 近 。但在算法的运行时间上 ,新算法用时最少 ,这是因为在算法中引入了转折点的概念 ,减少了很多的计算量 。表 1 对于

23、图 9 和图 10 的边界曲线新算法与其他算法的比较6结束语一般来说 ,特征点检测算法均有下面三个步骤 :( 1)找出转折点 ;( 2)通过计算曲率 求 出 一 些 明 显 的 特 征 点 (曲 率 大 于 tg的点 ) ;( 3)通过一个逼近过程确定其余的特征点 ,使得特征点间 的连线较好地逼近原始曲线 。其中第 ( 3 )步要计算 pi 到 pi - k pi + k连线的距离 , 这需要大 量的计算 。而本文介绍的综合算法将上述的第 ( 2 ) 步和第 ( 3 )步合为一个步骤 。由于在上述过程的第 ( 2 ) 步计算曲率 di / l i时已经求出了 di , 所以该算法就利用 di

24、的累加值来代替上述 第 ( 3)步的 复 杂 计 算 , 这 同 样 可 以 达 到 很 好 地 逼 近 曲 线 的 目的 。实际上 ,通过设置逼近阈值 ,所有算法都可以进行任何程度的逼近 ,关键是在逼近的过程中所需计算量的多少 。实验及 比较结果表明 ,本文的新算法在选择适当的特征点及运算速度方面都比现有算法有较大的改进和提高 。参考文献 : 1 f a ttneave. som e info rm ationa l a sp ec ts of v isua l pe rcep tion j . p sycho l. r ev, 1954 , 61 ( 3 ) : 183 2193.a ro

25、 senfe ld, e john ston. a ngle d e tec tion on d igita l cu rves j . ieee tran s. on comp u te rs, 1973 , 22: 875 2878.c h teh, r t ch in. o n the d e tection of dom inan t po in ts on d igitalcu rve s j . ieee tran s. patte rn a na l on m ach ine in te lligence,1989 , 11 ( 8 ) : 859 2872.u r am e r

26、. a n ite ra tive p rocedu re fo r the po lygona l app roxim a tion ofp lane cu rve s j . comp u te r grap h ic s im age p roce ss, 1972 , 16 ( 1 ) :244 2256.t pavlid is, s l ho row itz. segm en ta tion of p lane cu rve s j . ieee tran s. on comp u te rs, 1974 , 23: 860 2870.n a n sa ri, e j d e lp.

27、 o n d e tec ting dom inan t po in ts j . pa tte rnr ecogn ition, 1991 , 24 ( 5 ) : 441 2451.w y w u, m j w ang. d e tecting the dom inan t po in ts by the cu rva2 tu re2ba sed po lygona l app roxim a tion j . cv g ip: grap h ica l model im age p roce ss, 1993 , 55 ( 2 ) : 79 288.k w a ll, p e d an

28、ie lsson. a fa st sequen tial m e thod fo r po lygona l ap 2 p roxim a tion of d igitized cu rve s j . comp u te rs v ision grap h ic s im age p rocess, 1984 , 28: 220 2227.soo2chang pe i, j i2hwe i ho rng. co rne r po in t d e tec tion u sing n e stmoving a verage j . patte rn r ecogn ition, 1994 , 27 ( 11 ) : 1533 21537. 2 3 图 11 ( b e ) 给出了四种方法对钥匙图像边界的检测结果 。可以看到 co s2maxd 算法和新方法