一种层次型的曲线拐点搜索算法.doc

一种层次型的曲线拐点搜索算法周激流郭晶朱辉龙建忠( 四川大学无线电系 成都 610064)摘 要 本文提出了一种快速准确的提取曲线拐点的算法。 算法的总体结构是层次型的, 它分级逐次淘汰伪拐点, 而对每一级的处理又是顺序的逐点考察。 因此, 这种层次型的结构可抑制误差。 实验表明, 该算法不仅处理时间短, 而且能保持原始曲线的总体形状, 搜索出的拐点冗余度小, 因 而要求的存储容量小。关键词 线性近似 图像压缩 曲线匹配 拐点分类号T P 394A L ayered Search in g A lgor ithm On Curve Cr it ica l Po in tsZho u J iliuGuo J in gZh u H u i L o n g J ian zho n g(D ep a r tm en t o f R ad io , S ich uan U n ive r sity, C h engdu 610064)A bstrac t A new fa st and accu ra te sea rch ing a lgo r ithm o n cu rve c r it ica l po in t s is p ropo sed. T h eg lo ba l st ruc tu re o f th e a lgo r ithm is m ak e up laye r upo n laye r. T h e in te re st ing fea tu re o f th e p ro 2 po sed a lgo r ithm is it s ab ility to c lean o u t th e fa lse c r it ica l po in t s step by step. A nd o n th e eve ry leve l, th e p ro ce ssing is p ro ceeded in sequence. So th e laye red st ruc tu re can co n t ro l th e e r ro r s. It h a s been show n by sim u la t io n s th a t no t o n ly th e p ro ce ssing is p ro ceeded fa st, bu t a lso th e o r ig ina l cu rve sh ap e is rem a ined, th e e r ro e o f c r it ica l po in t s is lim ited, in th e la st th e needfu l m e rm o ry ca2 p ac ity is reduced.Key words line r app ro x im a t io n, im age com p re ssio n, cu rve f it t ing, c r it ica l po in t s引言1数字曲线上的高曲率点, 称为拐点。这样的点包含着物体形状的重要信息, 因此, 在形状分析、模式识别、数据压缩和线性近似中, 高精度的提取那些能表征曲线整体形状的拐点是非常 关键的。一个好的拐点搜索算法, 应在精度和速度上经受考验。只有精确度高且拐点冗余度小,提取出来的拐点才能准确反映曲线形状。 同时, 当处理的数据量庞大时, 处理速度就显得很重 要。目前, 已经提出的许多算法1 6 实际上可分为两大类: 错误容限法和局部曲率最大法。前者 的原理是对数字曲线作逐段线性多边形拟合, 拟合依据一定的拟合优良度, 例如, 对满足原始 曲线上的每一数据点到拟合曲线的垂直距离在一个预定的错误容限之内, 而不要求拟合的曲 线上的数据点一定经过原始曲线。很多算法在这方面作出了努力, 有的目的在于使拟合线段的数目减少, 却以牺牲速度为代价, 另一些算法则不太考虑拟合线段的数目, 而致力于缩短时间, 国家自然科学基金( 批准号: 69572027) 、四川省应用研究基金资助项目技术报告第 6 期周激流等: 一种层次型的曲线拐点搜索算法57动态单条带算法可以说是这类算法的代表1 。而局部曲率最大法, 就是运用高曲率点来分割曲线, 其依据是, 在人类视觉系统的识别过程中, 曲线的拐角或曲率大的点往往提供了重要的信 息。 当一条平面曲线用另一条平面曲线表示时, 只要高曲率点保持不变, 则我们会认为这两条 曲线具有相同的形状。 因此, 曲线描述问题转换为拐点的检测问题, 拟合的曲线是用直线段连 接拐点构成, 动态双条带算法是这类算法的典型代表2 。无论是动态单条带算法还是动态双条带算法, 它们都是基于条带算法的, 因此, 我们首先 讨论条带算法。条带算法原理及分析R eum an 第一个提出用条带来拟合平面曲线, 如图 1 (a ) 示。 一个条带由一条中轴线和两 条边界线确定, 中轴线由两个参考点, 即曲线上的第一和第二个数据点决定, 如图中的点 o 和 点 a。两条边界线与中轴线平行且相距 d , d 一般称为错误容限。这样的两条边界线构成了一个 条带去约束拟合过程, 当找到第一个落在带子外的点 e 时, 则一个拟合线段就由点 o 和点 c 确 定了, 而 c 又作为起始点为下一个拟合进程使用。条带算法的一个主要问题是, 如果曲线上的第三个数据点就落在带子外, 则由此产生的拟 合曲线将非常短, 大量的这样短的拟合曲线, 大大增加了运算的时间复杂度, 如图 1 (b ) 示, 条带 2 显然比条带 1 更合乎要求, 因为它容纳了更多的点。2(a) 条带算法(b ) 单条带算法图 1 条带算法原理示意图(c) 双条带算法R o b e rge 改进了条带算法, 他选择的 a 点 (即中轴线的第二个参考点) 必须距离第一个参考点至少为 ( 1) , 其算法基于这样的分析: 第二个参考点距第一个参考点越远, 中轴线的 方向就越能更好的确定曲线的走向。但是, 的值不能预定, 并且, 目前也尚未有方法确定它的值, 而如果选用一个任意值, 则通常产生很差的效果。动态单条带算法的基本思想为, 以起始点为支点, 旋转条带以容纳尽可能多的数据点来获 得拟合曲线, 如图 1 (c) 示。以起始点 o 为支点, 旋转宽度为 2d 的条带, 使带子在某个方向上容 纳最多的数据, 同时又不使已落在带内的点落在带外, 为此, 每判断曲线上的下一个数据点是 否可包含在带内, 都要计算带子的最大上转角和最大下转角 (即带子分别向顺时针和逆时针方 向可能转动的最大角度) , 避免使带内的点在带子转动时又落到带外。 当曲线上的下一点不能 包含在带内时, 将当前点作为一个拐点, 又以它为起点, 寻找下一个拐点。可见, 动态单条带算法实质上是一种错误容限法, 它不一定能保持原始曲线上的高曲率 点, 用直线段连接拐点构成拟合曲线时, 它容许拟合曲线围绕原始曲线上下波动, 只要最大距离偏差小于 d。 因此有时会产生错误的局部凹凸性, 找出的点不一定是确定曲线形状的关键58通 信 学 报1999 年点。动态双条带算法利用了条带这个概念, 它不仅将带子的方向作为可变化的参数, 而且还将其宽度也作为可变化的参数。这样就得到曲线上每一点在不同带宽下的最佳 (即带子最长并最 细) 左右条带。 与动态单条带算法相比, 它最突出的优点是保持了原始曲线的总体形状, 失真 小, 但其不足也十分明显, 第一, 算法复杂, 计算量大。 在找出曲线每一点的最佳左右条带过程中, 要不断调整带子的方向和宽度, 以使尽可能多的数据点落在带子内, 同时又不能使已落入 带内的曲线上的点又落到带外, 这样的最佳带子对曲线上的每一点都要找出左右两条, 因此最 佳左右条带的搜寻费时不少。 第二, 由于它是利用局部曲率最大提取拐点, 它考察的是曲线上 每一点的曲率和它附近的点的曲率的相对大小, 而对于变化方向连续、变化幅度无突变的曲 线, 例如单调性变化的曲线、圆弧、圆等, 各点的曲率相差不大, 对圆来说, 各点的曲率相同, 根据局部曲率最大原则, 不能判断哪个点更具有代表性 , 无法进行点的消除, 出现了大量的冗余 拐点。因此, 我们利用双条带这个概念, 提出新算法如下。新算法描述本算法共分 4 个步骤: 依次为: (1) 依据曲线上点的方向链码变化, 直接将粗略的直线段从 原始曲线上分离出来, 以后的讨论, 将只集中在这些直线段的端点上, 而对端点间的点, 则一次 性淘汰掉; (2) 估算直线端点及曲线弯曲处点的曲率 F i 并再次淘汰 F i 0 的点; ( 3) 对剩余的 点集, 选择其中相对曲率大的点作为拐点; (4) 用距离偏差法作后处理。 下面, 我们将详细论述 每一步骤的具体实施。(1) 对原始曲线C oi, i= 1 N o, 提取直线段C 1 i, i= 1 N 1链码是数字曲线的紧凑表示。 对数字曲线上的任意两上连续点 P 1 和 P 2, P 2 相对于 P 1仅有 8 个可能的位置, 于是, 曲线可以用一连串的方向 的改变来表示。 如图 2 示, Pm , Pm + 1 是序列P i的第m , m + 1 点。 则 Pm + 2 在L 1 的方向概率最大, 其次为 L 2, L 8, 故在跟踪时, 应优先考虑 L 1 方向, 其次 为 L 2, L 8, 再次 L 3, L 7, 确定 Pm + 2 位置后, 若它在L 1 方向, 则沿该方向继续考查 Pm + 3, 否则得到一直线段, 又以 Pm + 1 点为起点, 进行直线段的提取, 如此3下去, 可得到由直线段端点组成的序列C 1 i , i =1, N 1, 很明显, N 1N O , 曲线上弯曲部分的点, 相当于长度为 1 的直线段。而这一阶段被淘汰的点, 仅有 在端点的 8 邻域内的点还要用来进行简单计算, 其余 的点以后不再做任何处理。(2) 对C 1 i中的每一点, 估算其弯曲程度 曲率是描述曲线弯曲程度的量, 曲率越大, 表示曲图 2 直线段提取示意图线的弯曲程度越大。 对于连续曲线 y = f (x ) , 曲率定义为斜率的变化率, 即:C (x , y ) = (dy 2 dx 2 ) 1+(dy dx ) 2 32(1)对数字曲线, 如果简单的用一阶差分来替换上式中的微分, 则相邻点的坡度变化只能是45的倍数, 因此, 它不能估算出斜率的小的变化量, 更一般的情况应该是定义 P i 点的斜率为:第 6 期周激流等: 一种层次型的曲线拐点搜索算法59C (x , y ) = (Y i+ k - Y i) (X i+ k - X i)其中 K 1, 而如果 K = 1, 则为通常的一阶差分。(2)式 (2) 算法简单, 但 K 的取值不易确定, 因为曲线上各点的局部特性不同, K 值的取值不应固定, 否则将影响曲率的估计。设 P 1、P r 分别表示C 1 i中最靠近 P i 点的左右端点, L 1 和L r 分别表示点 P 1、P r 到点P i 的长度, 为线段 P 1P i, P iP r 间的夹角, 我们定义参数 F i, 用它来衡量拐点 p i 的价值。F i= L 13 | 180- | 3 L r, 0 180(3)分析式 (3) 可见, 如果长度L 1 和L r 越长, 且所夹角度 越尖锐, 则 F i 越大, 反之, 如果L 1和L r 越短, 且所夹角度 越为钝角, 则 F i 越小, 因此, F i 作为衡量拐点 P i 价值的参数是有物 理意义的。计算出C 1 i中每点的 F i 后, 暂时排除 F i 近似为 0 的点, 剩余点又构成数量更小的新序 列C 2 i, i= 1 N 2, 同样的, 有N 2 N 1。在以上两个处理阶段中, 是根据点的自身性质决定取舍的, 第一阶段去掉的是曲率绝对为0 的点, 第二阶段暂时排除近似曲率为 0 的点, 这两步, 都未涉及点与点的相互关系。(3) 排除伪拐点对序列C 2 i中的点, 我们运用局部曲率最大值法则, 排除伪拐点, 进而提取那些具有全局 表征能力的拐点, 得到新的拐点序列C 3 i, i= 1,N 3, N 3 N 2。设点 P i 的左右邻域分别记为 P iL ef t 和 P iR igh t , 如果点Q 在点 P i 的左邻域内, 可表示为:Q P iL ef t左右邻域定义为最佳左右拟合带所覆盖的面积, 如图 3 所示。 如果满足下列条件之一, 则 P i 可被消除存在m , 只要 P iP j - m L ef t 和 P jL ef t P j - m L ef t 和 F j F j - m ;(1)(2)存在m , 只要 P iP j + m R ig h t 和 P i P j + m 和 F j T m ax , 则将D 吸收为拐点, 插入序列C 3 i中, 并继续用同样的方 法考察弧D tD t+ 2 上是否需要补充新拐点, 若 T T m ax 的C 1 i点。其次, 消除冗余拐点, 其目的是使某拐点与它邻域内的拐点, 不近似为一条直线, 即寻找全 局拐点。 为此, 令 T m in = 0. 3 0. 8 (经验值) , 则原理如图 4 (b ) 所示。(a) 补充拐点(b) 消除冗余点图 4 距离偏差后处理原理对新序列C 3 i, 当点D k 到弦D k - 1D k + 1 的垂直距离 T T m in , 则考察弧D kD k + 2, 检查点D k + 1 是否能被 消去。递增 K , 循环考察序列C 3 i, 直到不再有被消去的点。这一处理除了进一步去除冗余拐点外, 还可平滑因离散表示和量化误差引起的错误的局部凹凸性。4计算机模拟实验根据本文的拐点搜索算法, 我们在计算机上进行了模拟实验。图 5 是本文算法和文献1 、2算法的比较实例。 从图中可以看出, 第一, 文献1的拐点误差大, 漏掉的拐点多, 但速度较(a) 文献 1 算法(b ) 文献 2 算法图 5 算法处理实例(c) 本文算法第 6 期周激流等: 一种层次型的曲线拐点搜索算法61快, 第二, 文献2的拐点精度高, 几乎没漏掉关键拐点, 但冗余拐点多, 且速度慢。第三, 本文算法的冗余拐点的开销在文献1与2之间, 但提取的拐点精度高, 并且速度很快。 具体数据如 表 1 所示。表 1图 3 中各算法处理数据比较本文提出的拐点搜索算法, 总体结构是分级逐次淘汰伪拐点, 而每一级的处理过程又是顺序的逐点考察法。 它有两个突出特点。 第一, 速度快, 由于首先用简单快速的方法将直线段从 曲线中分离出来, 以后的处理仅对直线端点及曲线的弯曲部分进行考察, 逐级淘汰伪拐点, 因 此, 运算数据量大大减少。同时, 对大量的数据点采用简单快速的方法, 仅对少数不易判断的点 采用相对复杂的处理, 避免了大量繁杂的运算, 因而提高了搜索速度。 第二, 提取的拐点精度高, 由于局部曲率最大法和距离偏差法都被用来控制拐点的提取, 因而它克服了局部曲率最大 法冗余拐点多和距离偏差法容易丢失关键拐点的缺陷。从实验中可以看出, 本文算法产生的拐 点可以使曲线的整体形状得到很好的保持, 所要求的存储容量小, 具有一定的工程实用价值。参考文献12345leung M K. D ynam ic st r ip a lgo r ithm in cu rve f it t ing. Com p u te r V isio n G rap h ic s & Im age P ro ce ssing. 1991, 51: 146 165leung M K. D ynam ic tw o 2st r ip a lgo r ithm in cu rve f it t ing. P a t te rn R eco gn it io n. 1992, 23 ( 12) : 69 79Kop low itz