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

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; 修返日期 : 200520620

10、7基金项目 : 国家自然科学基金资助项目 ( 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 ,基于这一点

14、 ,我们称它为 co s方法 , 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

15、 am e r算法复杂一些 , r 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 ) ,直到达到一个平衡状态 ,没有再进行“

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

18、a ×bik ik, co sik =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 << co si, h i co si, h i - 1 7 对于 co si, h i co sj, h j中所有的 j, 若点 pi;| i - j | h i / 2, 则保留w u和 w ang 提出了一种基于曲率的多边形逼近的综合方法 ,称为 co s2maxd 方法 。它把角检测 法得到的角点作为( y i -y i - 1 ) x i - 2 - ( x i - x i - 1 ) y i - 2 +

20、 x i y i - 1 - x i - 1 y i =多边形迭代逼近方法的起始点 ,先通过一种角检测方法得到最重要的特征点 ,然后在这些点分割的小曲线段上进行多边形逼 近 ,这样会得到很好的效果 。然而 ,以上提到的算法也有一个缺点 ,检测特征点算法本 应该不受物体的大小和方向的影响 ,也就是说 ,当物体的大小和方向发生变化时 ,我们检测到的特征点的数量不应该变化 ,而且特征点的位置也不应该偏离太多 。但上面的算法做不到 这一点 ,我们在本文中提出了一种有效并且速度更快的综合方法 ,并且对物体的大小和方向的变化不那么敏感 。y i x i - 2 - y i - 1 x i - 2 - x

21、i y i - 2 + x i - 1 y i - 2 + x i y i - 1 - x i - 1 y i =- ( y i - y i - 2 )x i - 1 - ( x i - x i - 2 ) y i - 1 + x i y i - 2 - x i - 2 y i 最后的表达式与 dsi - 1的表达式的分子式相同 , 只是符号相反 , 这正是我们要证明的 。 关于 dsi 的符号 , 我们有( y i + 1 - y i - 1 ) x i - ( x i + 1 - x i - 1 ) y i + x i + 1 y i - 1 - x i - 1 y i + 1ds =i2

22、 +) 2( y i + 1 - y i - 1 ) i + 1 i - 1( x- x将 pi + 1点代入式 ( 1 )的左边 , 我们得到相同的结论 :( y i - y i - 1 ) x i + 1 - ( x i - x i - 1 )y i + 1 + x i y i - 1 - x i - 1 y i =3 新综合方法的基本原理y i x i + 1 - y i - 1 x i + 1 - x i y i + 1 + x i - 1 y i + 1 + x i y i - 1 - x i - 1 y i =- ( y i + 1 - y i - 1 )证毕 。x i - ( x

23、 i + 1 - x i - 1 ) y i + x i + 1 y i - 1 - x i - 1 y i + 1 综合方法的原理是很直观的 。像角检测方法一样 ,该方法也是先计算各初始点的曲率并找出一些明显的角点 ;同时它还 像多边形逼近方法那样 ,从这些角点开始逐渐向边界上加入一些特征点 ,直到满足一定的条件为止 。新方法的最主要的特征 是对各点到弦的距离 di (如果小于设定的阈值 ) 进行累加 (相当于曲率的累加 ) ,该累加值累加到一定的值时则增加一个特征点 ,并重新开始累加 。这样对于缓慢变化的曲线也可找到一 些特征点 ,对其进行描述 。这个综合方法克服了角检测方法的上述缺陷 ,

24、同时又比多边形逼近方法提高了速度 ,这一速度的提高是因为它使用了点到弦距离 di 的累加来决定应在何处加 点 。而 di 在计算各点的第一个弦的曲率 (即由其相邻的两点 连线计算出的曲率 )时已算出 ,这样在决定是否加点时在每一 点只需计算一次弦的曲率而不必像多边形逼近方法那样算多次弦 (包括非相邻两点间连线 )得出的曲率以判断是否满足某 条件 。由图 4可以看出 , di 的累加值可以很好地表示边界曲线的弯曲及被逼近程度 ,尤其对于平滑曲线 。因此 ,综合算法就判 断这个累加值是否大于某个阈值 td 。若是 , 则应加一特征点 ;否则 , 继续累加 。在累加 di 的过程中 ,如果在相邻两点

25、处曲线向不同侧弯曲 , 则此时要用减法操作 ; 否则用加法 ,如 图 5 所现在 , 我们有如下的结果 :如果曲线在相邻的两点 pi - 1和pi 处向不同侧弯曲 , 则将另两点 pi - 2和 pi + 1分别代入式 ( 1 ) 的 左边将产生不同的符号 。这些符号又分别与 dsi - 1和 dsi的符号 相反 , 所以在这种情况下 , dsi - 1的符号与 dsi 的符号是相反的 。这样 , 在下面的算法中我们总是将每 一点的 dsi 进行累加 , 实际上是对曲线弯曲的累加 , 这时的累加是带符号的 。实际上 , 当曲线弯向一侧时 , 相当于将 dsi 的绝对值加到累加值中 ; 而 曲线

26、弯向另一侧时 , 相当于从累加值中减去 dsi 的绝对值 。当累加值达到一定量时 ,即使没有角点出现 ,也要增加一个特征点 ,以适应缓慢弯曲的曲线 。4 算法实现411 预处理我们在利用边界跟踪算法得到一个物体的边界链码时 ,要 对这一链码进行一些处理 。( 1)除去边界中所有宽度为一个像素的突起 。这种很细微的细节问题不能由图像的分辨率所解决 ,而且它是由噪声和 量化误差引起的 。一个像素宽度的突起就是这样引起的 ,我们 必须除去 。这样的例子如图 6所示 。( 2)由于在直线上的点不能作为特征点 ,所以我们要排除曲线上的这些点 ,这可以通过检查链码来完成 。设曲线的链码示 。观察图 5我们

27、会发现 ,如果曲线在某两点pi - 1和pi 处向不同侧弯曲 , 则其前后两点 pi - 2和 pi + 1一定在 pi - 1和 pi 连线的不同侧 。该连线的方程式可以写为( y i - y i - 1 ) x - ( x i - x i - 1 ) y + x i y i - 1 - x i - 1 y i = 0( 1 )为序列 c1 , c2 , c3 , cn , 那么如果 ci - 1 = ci , 则点 pi 不可能这样 , 将 b i - 2点和 b i + 1点分别代入上式 ,左边一定会产生不同符号的值 。是特征点 。例如在图 7中 , 由于 c4 = c5 = c6 =

28、7, 所以 p5 和 p6点不可能是特征点 ; 而 p4 和 p7 点则可能是特征点 ,可能的特 征点我们称为转折点 ,在图 7中由 ®表示 。这样我们只需在转折点处计算曲线的曲率 ,因而减少了大量的计算 。为了减少算法的计算量 ,我们使用带 符号的距离 dsi , 并且 di = | dsi | 。下面的定理是新方法的基础 。定理dsi - 1的符号与将点 pi - 2代入式 ( 1)左边所得值的符号 相反 ; dsi 的符号与将点 pi + 1代入式 (1)左边所得值的符号相反 。412 确定支撑区域在上面提到的算法中 ,均要求输入一些参数 ,特别是在计 算曲线上每一点的曲率时

29、,要求必须有一个支撑区域 ,这个区 域的确定是基于两个方面 : 该曲线的长度 ,也就是该数字曲( y i - y i - 2 ) xi - 1 - ( x i - x i - 2 ) y i - 1 + x i yi - 2 - x i - 2 y i证明 : dsi - 1 =22( y i - y i - 2 ) + ( x i - xi - 2 )由于上式的分母一定是正的 , 所以 dsi - 1的符号只 由上式的分子决定 。现将点 pi - 2代入式 ( 1)左边得 :线所包括像素的个数 ; 当前计算的点附近的细节状况 。一般情况下 ,对一个变化急剧频繁的曲线而言确定一个合适的支撑 区

30、域是很困难的 ,太大了会平滑掉曲线上一些特征 ,使很明显 的特征点被忽略掉 ;而太小的支撑区域会产生很多冗余的特征点 。在确定支撑区域时 ,我们所用的方法是对 ro senfe ld2john s2ton角检测方法的一种改进 。在 ro senfe ld2john ston 方法中 ,如 果输入的平滑参数选择不恰当 ,将会导致某些点的支撑区域和曲率的计算均出现错误 。为了克服这一缺点 ,我们采用了对曲 线上每一点分别计算其所需的支撑区域 ,这一方面使算法对不 同的被检测边界曲线以及曲线上不同的细节保证了其独立性 ;另一方面 ,减少了算法的输入参数 。这样一旦支撑区域确定下来 ,那么在检测特征点

31、时 ,才能保证每一点曲率计算的正确性 。 从而我们得到了这样一个结论 :特征点的检测不仅依靠特征值(一般为曲率 )计算的正确性 ,而且更主要的是依靠支撑区域的精确测量 。这与传统检测方法的说法有所不同 ,在传统方法 中 ,离散曲率的正确测量被认为是检测可靠的特征点的主要因素 。下面是确定支撑区域的过程 : d i 中除去 。若点 pi - 1或 pi + 1也在集合 d i 中 ,也就是说 ,曲线上连续 的两点都是转折点 ,而且经计算后 ,均通过了筛选 。这时如果 cur ( pi ) cur ( pi - 1 )或者 cur ( pi ) cur ( pi + 1 ) 则也把 pi从集合 d

32、 i 中除去 。这一过程可以与步骤 ( 3)并行操作 。5 实验结果比较与算法分析511 分析结果的标准从模式识别角度讲 ,在数字曲线上检测特征点可看作是曲 线的一种压缩 ,或者说是曲线有效的表示 。连接相邻的特征点 得到的多边形用来逼近这个曲线 。我们在本文中定义了一些 标准来反映它们之间的关系和分析算法实现结果 。如果用数 据压缩的观点来衡量 ,是期望得到尽量少的特征点 ,然而特征 点太少又不能很好地反映原曲线 。因此应该在权衡这两方面 的基础上 ,得到较好的综合考虑的标准 。我们在这里使用了三 个标准来衡量算法的实现 。( 1)压缩比 ( cr ) , 即曲线上的点数与 所检测到的特征点

33、 数的比值 。定义为 cr = n /m , 其中 , n 是被检测曲线点的个数 (如果为封闭曲线 , 则 n = n, n 是曲线链码的个数 ; 否 则 , n =n + 1) 。而 m 是通过检测算法后检测到的特征点 。这个压缩 比越大 , 说明这个算法在数据的压缩上越有效 。( 2)均值误差 ( e2 )用来估计原曲线和逼近多边形的差别 ,它是所有逼近多边形的边与原曲线所夹面积的平均值 。定义( 1 )定义点 pi - k和 pi + k的弦长 。 lik =pi - k pi + k, 并且定义dik为点 b i 到弦 pi - k pi + k的垂直距离 , 如图 2 ( b)所示

34、。( 2 )从 k = 1开始 , 计算 lik和 dik直到满足条件 : lik li, k + 1或者dik di, k + 1dik di, k + 1当 dik > 0; 当 dik < 0。1 m likli, k + 1likli, k + 1为 e2 = a i , 其中 , m 是曲线被分割后的曲线段数 (如果为m i = 1封闭曲线 , 则 m =m ; 否则 , m = m - 1 ) , 而 a i 为原曲线和弦这样 , 我们把满足条件 或者条件 的点作为点 pi 的支撑区域 , 用 s ( pi ) 表示 : s ( pi )pi + k ) |条件 或者条

35、件 。413 新算法描述= ( pi - k , pi - 1 , pi , pi + 1 ,v iv i + 1 (v i 是第 i个特征点 ) ,如图 8所示 。面积的大小我们采用曲线段上所有点到弦的垂直距离来估算 。这个参数反映了 逼近多边形在多大程度上逼近原有的曲线 。很明显 ,这个值越小 ,这种算法越有效 。在前面讨论的基础上 ,我们对新算法进行以下描述 :输入 : td (对于 di的累加值设定的阈值 ) ; tg (对曲率估算 值 di /l i 设定的阈值 ) ; pi (原始取样点集 ) 。输出 : d i (求出的特征点集 ) 。 算法 :( 1 )得到被测物体的边界曲线链

36、码 pi 。( 2 )通过检测由 pi 形成的链码找出转折点 , 即从 pi 得 到转折点集 b i 。( 3 )找出所有的特征点 ,其过程如下 :ac0;fo r每一个 b i do计算 d si和 l i ;if | d si /l i | > 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

37、从 集 合( 3)最大误差 ( em ) :定义为 em ax = m ax a i1im 512 与传统算法的比较对新算法与在第 2 节中介绍的三种算法分别在以下几个 方面进行比较 : 特征点的个数 ; 逼近误差 e2 和 em ax ; 算 法的 cpu 运行时间 。在这里我们引入了两种物体对象进行测 试 ,如图 9 ( a)和图 11 ( a)所示 。一般说来 ,一个好的特征点检 测算法应该在物体的大小或者是旋转角度发生变化时保持一 种稳定性 。因此 ,这里我们对每个物体在这些因素变化时也进 行了测试和比较 。这些变化的曲线连同原边界曲线如图 9 ( a)图 12 ( a) 所示 ,并且

38、在图 9 ( be) 图 12 ( b e) 中分别对co s方法 、分割 2合并方法 、co s2maxd 方法以及新方法所检测 到的特征点作了标记 ,并且在表 1和表 2中对得到的测试结果进行了总结 。如图 9所示 ,我们对第一个物体的边界曲线进行了特征点表 2 对于图 11 和图 12 的边界曲线新算法与其他算法的比较检测 。可以看到 ,使用 co s角检测方法只检测到了四 个特征点 (图 9 ( b) ) ,很明显 ,四个点检测出的正好是物体的 四个角 点 。但是 ,用这些点并不能很好地逼近该边界曲线 ,因为在边 界曲线上还有两段弧线 。而其他的三种方法均检测到了六个特征点 (图 9

39、( ce) ) ,这样就能够较好地描述这条曲线 。下面我们在来观察一下图 10 ( a ) , 它与图 9 ( a ) 是同一个物体的边 界 ,只是旋转了一定角度 。可以看到 ,使用 co s方法和新方法与旋转前得到的结果相同 (图 10 ( b, e)和图 9 ( b, e) ) ,而在分割 合并算法和 co s2maxd 方法中 , 产生了过多的冗 余特征 点 (图 10 ( c, d) ) 。所以可以看出只有新方法不仅检测到了合 适的特征点 ,而且得到了较好的一致性结果 ,这说明对物体的方向 、大小不敏感 。在表 1 中我们给出了比较结果 , co s角检测方法有最大的均值误差 ,而其他

40、三种方法在这一方面比较相 近 。但在算法的运行时间上 ,新算法用时最少 ,这是因为在算法中引入了转折点的概念 ,减少了很多的计算量 。表 1 对于图 9 和图 10 的边界曲线新算法与其他算法的比较6结束语一般来说 ,特征点检测算法均有下面三个步骤 :( 1)找出转折点 ;( 2)通过计算曲率 求 出 一 些 明 显 的 特 征 点 (曲 率 大 于 tg的点 ) ;( 3)通过一个逼近过程确定其余的特征点 ,使得特征点间 的连线较好地逼近原始曲线 。其中第 ( 3 )步要计算 pi 到 pi - k pi + k连线的距离 , 这需要大 量的计算 。而本文介绍的综合算法将上述的第 ( 2 )

41、 步和第 ( 3 )步合为一个步骤 。由于在上述过程的第 ( 2 ) 步计算曲率 di / l i时已经求出了 di , 所以该算法就利用 di 的累加值来代替上述 第 ( 3)步的 复 杂 计 算 , 这 同 样 可 以 达 到 很 好 地 逼 近 曲 线 的 目的 。实际上 ,通过设置逼近阈值 ,所有算法都可以进行任何程度的逼近 ,关键是在逼近的过程中所需计算量的多少 。实验及 比较结果表明 ,本文的新算法在选择适当的特征点及运算速度方面都比现有算法有较大的改进和提高 。参考文献 : 1 f a ttneave. som e info rm ationa l a sp ec ts of v

42、 isua l pe rcep tion j . p sycho l. r ev, 1954 , 61 ( 3 ) : 183 2193.a ro 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

43、 a na l on m ach ine in te lligence,1989 , 11 ( 8 ) : 859 2872.u r am e r. 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. 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