《对一种快速边缘跟踪算法的讨论.doc》由会员分享，可在线阅读，更多相关《对一种快速边缘跟踪算法的讨论.doc（5页珍藏版）》请在三一办公上搜索。
1、第 21 卷 第 6 期2000 年 6 月小 型 微 型 计 算 机 系 统M IN I- M ICRO SYST EMV o l121 N o 16J uen 2000文 章 编 号: 100021220 (2000) 0620641205对一种快速边缘跟踪算法的讨论史册( 浙江大学信息与电子工程学系 杭州 310027)摘 要: 本文首先介绍了一种快速边缘跟踪算法的原理, 然后针对如何提高该算法的处理速度所涉及的问题进行了深入的讨论.关 键 词:分 类 号:计算机视觉; 实时图象处理; 链码; 边缘跟踪文献标识码: AT P 391物体的边缘信息在计算机视觉中占有重要地位, 它在图象分割
2、、景物识别、图象理解等领域中起着关键作用. 因此, 边 缘提取在视觉信息处理中是一个必不可少的环节. 对数字图 象而言, 边缘由满足一定条件的像素 (称为边界点) 构成, 获得边界点的方法有多种, 如直方图2阈值法, 过零点检测等, 但仅 仅获得边界点是不够的, 必须通过边缘跟踪将它们从图象信 息转换为符号信息, 才有利于后续处理的使用. 边缘跟踪的结果通常是链码表示, 在此的基础上, 可以方便、快速地提取出角点1、直线2等多种重要信息.本文主要讨论如何在已获得边界点的二值图基础上, 以 尽可能快的速度获得边缘的链码表示. 作者先向读者介绍一 种比较好的边缘跟踪算法的思想, 然后对涉及到该算法
3、执行 速度的若干问题进行深入的讨论.沿 元 的 值 非 零. 根 据 考 察 点 是 目 标 点 还 是 背 景 点 分 别 取 正( Po sit iv ity, 记为 P ) 或负 (N ega t iv ity, 记为 N ). 参见图 1 和图2 中的 (c)、(d).跟踪方向规定如下: 目标点始终在前进方向的左边. 如各 图中箭头所示. 对于一个连通区域的外边界, 跟踪方向为逆时 针方向; 而内边界 (内部孔洞所形成的边界) 则为顺时针方向. 当在封闭链码基础上求面积时, 外边界链码所围成的区域面 积为正, 而内边界链码所围成区域面积为负, 从而在计算机视 觉的高层推理中很容易把内、
4、外边界区分开.显然, 边沿元的取值同时也表明了相应的跟踪方向, 因此以下用边沿元的方向来表明相应的跟踪方向. 如说某个边沿 元方向为正, 对水平边沿元而言, 跟踪方向向右; 对垂直边沿 元而言, 跟踪方向向上.跟踪过程中的标记打在当前边沿元的目标点上 (参见图1、2 中带 阴 影 的 目 标 点) , 以 区 分 该 边 界 点 是 否 已 经 被 跟 踪 过.1. 2 边沿元的记法:用 H 或 V 表示边沿元的类型 (水平还是垂直) , 后跟当前 考察点的坐标, 等号右边表明对边沿元的值. 如:“V ij=N ”即表示: 在考察点为ij和参考点为ij+ 1之间的边 沿元类型为 V 、值为 N
5、 (即跟踪方向向下的垂直边沿元). 为方便读者, 各边沿元的记法同时标在图 1、2 中.1算法的思想边缘跟踪算法主要包括扫描过程和跟踪过程, 不同算法的差异主要体现在跟踪过程中, 尤其是如何根据当前的情况 判断下一步的跟踪方向, 这是算法的核心. 这一部分就主要讨 论这个核心问题.本文采用 T. P av lid is 3对链码及方向的定义, 并以2 表示二值图中的背景点, 以+ 表示二值图中的目标点.1. 1 边沿元的定义本文假设边界存在于像素之间, 由边沿元构成, 分为水平(H o r izo n ta l, 记为 H ) 和垂直 (V e r t ica l, 记为 V ) 两种. 参见
6、图2、3 中的 (a)、(b ).设当前考察点坐标为ij, 判断是否存在水平边沿元以i+ 1j为参考点, 判断是否存在垂直边沿元以ij+ 1为 参考点.当考察点与参考点的值相同时, 这两个点之间没有边界 通过, 边沿元的值为零. 根据它们都是目标点还是背景点分为正 零 ( Po sit ive Ze ro , 记 为 P Z ) 和 负 零 (N ega t ive Ze ro , 记 为N Z) 两种.当考察点与参考点的值相异时, 两点之间有边界通过, 边图 1 水平边沿元 H图 2 垂直边沿元 V1. 3 后继边沿元的确定收稿日期: 1999204221 作者简介: 史册, 博士. 主要研
7、究方向为图像处理、计算机视觉、人工智能.前面说过, 边缘跟踪算法的核心在于如何判定下一步的跟踪方向. 这个判定方法非常重要, 它在很大程度上决定了算 法效率的高低. 下面首先讨论另外两种算法中判定方法的优 缺点, 并与本文的判定方法做对比, 然后再详细阐述本文的判定方法.文献4中的判定方法采用了查找表的方法. 取 22 大 小的观察窗口, 窗口中不同的位置赋予不同的权值. 跟踪时,以该窗口模板对图象中相应象素的加权和作为索引, 查找事先造好的查找表 ( 相当于本文的图 3 6) 就可得到下一步的 跟踪方向.这样做的好处是比较快 ( 对同一幅图, 4中的算法仅比 本文的算法慢 10% 左右) ;
8、 缺点是:( 1) 查找表中有重复. 例如, 图 3 (d ) 与图 4 (d ) 将具有相 同的索引值, 必须再参照当前的跟踪方向 (4中称为“上一步跟踪方向”) 才能区别.(2) 窗口中 各 点 的 取 值 已 足 以 判 断 出 下 一 步 的 跟 踪 方 向, 因此没有必要计算加权和.作者采用了4中的窗口思想, 但与4的不同之处在于:4以窗口的类型为出发点, 在必要时才判断当前的跟踪方 向; 而作者则以当前边沿元的类型及方向为基础, 辅以窗口其 它的点的取值情况.与4相比, 文献5中的方法与本文更加接近. 它类似地 定义了水平边界、垂直边界及其方向. 但它首先要计算出所有像素的水平边界
9、值和垂直边界值 ( 分为 0, 1 和- 1 三种) , 在 此基础上再根据每个像素的这两个边界值确定下一步的跟踪方向.5中利用像素的边界值来确定下一步跟踪方向的思想 非常巧妙, 但有以下两个不足之处:(1) 没有进一步区分两种不存在边界的情况. 这样, 对于 边界值为 0 的像素, 在跟踪时还要判定是同为目标点还是同 为背景点;( 2) 实验表明 ( 参见讨论四) , 对各像素的边界值的计算 是完全可以省略的.本文的判定方法与4、5相比, 有其长而无其短. 简略 来说, 其主要思想就是: 当当前考察点与参考点之间存在非零边 沿元时 (图 1 2 中的 (c)、(d) ) , 根据这两点所构成
10、的 22窗口中其余两点的情况, 来决定下一步的跟踪方向 (以下称为 后继边沿元).图 3 6 给出了所有以ij为当前考察点并在已知当前 边沿元的类型及方向的情况下, 所有可能的后继边沿元的类型及方向. 其中, 带阴影的目标点是当前边沿元的标记点.的两个像素ij+ 1和i+ 1j+ 1的取值有四种组合 ( 图 4( a ) (d ) ) , 每一种组合都确定了唯一的后继边沿元 ( 在各图 中标明). 容易证明: 对于图 3 6 中的任何一种情况, 其后继边沿元都是唯一的.图 4H ij= N 时的后继边沿元图 5V ij= P 时的后继边沿元图 6V ij= N 时的后继边沿元1. 4 边缘跟踪
11、算法如果用 succ 表示后继边沿元的类型及方向, 跟踪过程主 要处理如下:w h ile ( 没有返回到起点, 即跟踪过程没有结束) if (H ij= = P )if (H ij+ 1= = P Z)if (H ij+ 1= = N Z)if (H ij+ 1= = P )if (H ij+ 1= = N )if (H ij= = N )if (H ij21= = P Z)if (H ij21= = N Z)if (H ij21= = P )if (H ij21= = N )if (V ij= = P )if (V i21j= = P Z)if (V i21j= = N Z)if (V i
12、21j= = P )if (H i21j= = N )if (V ij= = N )if (V i+ 1j= = P Z)if (V i+ 1j= = N Z)if (V i+ 1j= = P )if (V i+ 1j= = N )Succ: V i+ 1j= NSucc: V ij= PSucc: H ij+ 1= PSucc: V i+ 1j= NSucc: V ij21= PSucc: V i+ 1j21= N Succ: V ij21= PSucc: H ij21= NSucc: H i21j+ 1= PSucc: H i21j= NSucc: V i21j= PSucc: H i21
13、j+ 1= PSucc: H ij= NSucc: H ij+ 1= PSucc: H ij= NSucc: V i+ 1j= N2算法的实现图 3 H ij= P 时的后继边沿元例如, 对于图 3, 当前边沿元为“H ij= P ”, 窗口右边作者主要研究计算机视觉中的实时 ( 指 25 帧秒的电视频率) 问题, 因此对一个算法的处理时间特别在意. 在考察上6 期史 册 等: 对一种快速边缘跟踪算法的讨论643述算法的处理速度时, 作者发现了一些有趣的结论. 下面以讨论的形式给出, 供有兴趣的读者参考.点扫描, 无孤立边界点) 的结果参见图 10- 12.讨论一: 4 方向还是 8 方向?根
14、据文献3的定义, 链码又可细分为 8 方向链码和 4 方 向 链码两种, 对于图 3 6 中 (a) (c) 的情况, 无论采用哪种 表 示, 后继边沿元都是相同的. 但对于图 3 6 中的 (d) , 采用 不 同的表示, 就有不同的后续边沿元. 如图 3 (d) , 如果采用 4 方 向链码, 后继边沿元就改为“V ij= P ”. 但无论采用哪 种链码, 图 3 6 中任何一种情况的后继边沿元都是唯一的.图 7BL O C K 原图图 10 BL O C K 边界跟踪结果图图 8 G IRL 原图图 11 G IRL 边界跟踪结果图图 9 BR ID GE 原图作者挑选了三副具有代表性的
15、图象 ( 2562568b it, 参 见图 7- 9) 作为实验对象. 第一副原始图象为自然光下的简 单人造物体图象 ( 记为 B lo ck , 多用于景物分析) , 分割后图中 有内外两条边缘; 第二副原始图象为自然光下的较复杂的人 物肖像 (记为 G ir l, 多用于图象编码) ; 第三副原始图象为多光 谱下较复杂的自然景物图象 (记为 B r idge, 多用于目标识别). 限于篇幅, 略去了这三幅图象的二值化图象, 其边缘跟踪 (逐图 12 BR ID GE 边界跟踪结果图一般认为 8 方向链码的结果比较精确, 而 4 方向链码的速度比较快. 但实际上这两者是差不多的. 这是因为
16、为了保证对于只有一个像素宽的斜线的正确跟踪, 必须修改 4 方向链 码的跟踪方式, 否则, 跟踪结果将是一个个孤立的边界点 (多数 情况下被丢弃) 而不是一个线段. 修改后, 4 方向链码与 8方向链码相差不多. 因此, 本文中提到的链码, 除明确说明外,均指 8 方向链码.讨论二: 图象的表示对于图象的表示, 有一维数组和二维数组两种表示. 从表 面上看, 一维数组会比二维数组要快一些. 因为在移动指针 时, 前者只需做加减法, 而后者必须做乘法. 但实践表明, 因采 用不同的表示而造成的速度差别并不象人们所想象的那么进一步的实验表明, 做一次判断所花费的时间很少: 106次判定的时间开销为
17、 25 拍. 就拿最坏情况下每一步都要重复4 次判断来说, 对 于 边 界 点 数 目 最 多 的 图 象 B r idge, 将 多 出98283 4 次判断, 算下来处理时间将相差 1 拍, 与表 4 正好相 符. 而且, 处理器速越高, 这种差别就更小. 这表明, 在本算法中使用 go to 语句所带来的好处并不大.另外, 在本算法中, 使用 go to 语句对程序结构、可读性及 维护等方面带来的影响也很小, 因此, 是否使用 go to 语句来避免重复判断, 要根据具体应用的环境来决定. 在实时系统中, 相差的这一拍也许就是任务分配的关键数据.讨论四: 各像素边界值的计算可以省略前文说
18、过, 文献5要对各像素计算水平边界值和垂直边 界值. 这一步实际上是可以省略的. 因为这两个值一次性的, 仅供跟踪时使用, 而且在跟踪过程中完全可以根据其原理边 判断, 边跟踪, 没必要单独扫描整个图象做计算. 为此, 作者做 了对比实验, 结果如表 3 所示.表 3 是否计算各像素边界值的速度差异多. 因为开发系统 (如 BC 3. 1, BC + +5. 0 等) 一般都对二维数组的引用做了优化处理, 因此, 二维数组与一维数组在引用上的速度差别大约是: 107 次相差 4 拍1. 对于一副 256256大小的图象而言, 相差不到 1 拍.受操作系统 DO S 的限制, 超过 64K (
19、16 B y te 大小的数据 块必须使用 h uge 指针, 才能保证数据的正确引用. 而 h uge 指 针受寻址方式的影响, 处理速度会急剧降低 (参见表 1).表 1 h uge 指针与非 h uge 指针的速度差异从表 3 可以得到下面两个结论:结论 1: 无论二值图的复杂程度 (边界点数目) 如何, 计算各像 素的边界值所花费的时间基本上是固定的, 即计算时间与图 象的复杂度无关.结论 2: 对同一幅图象, 在其它条件相同时, 省略该步骤可以 极大地加快处理速度.讨论五: 扫描方式一般的边缘跟踪算法采用逐点扫描的方式寻找新的尚未 跟踪过的边界点, 与处理图象的最终目的无关. 但在计
20、算机视 觉中, 因为信息量非常大, 而且具有很强的不确定性, 因此必 须结合最终目的尽早对处理加以引导, 防止信息量的过度增 长. 通常情况下, 只在一个特定的范围内 (大小与感兴趣对象 的大小有关) 而不是整个图象进行处理.为此, 作者采用网格扫描的扫描方式, 对选定的三副图象 做对比实验, 结果如表 4 所示, 网格的大小根据感兴趣的目标大小而定.表 4 逐行扫描与网格扫描的速度差异当在 32 位操作系统 (如W IN DOW S 95) 或专用处理芯片环境下, 就不存在此问题, 图象可以是任意大小. 考虑到程序的可 读性, 应尽量采用二维数组. 为避免 h uge 指针带来的影响, 可采
21、用宏定义, 使图象的表示具有二维的形式, 一维的实质. 作者正是如此处理的.讨论三: 是否使用 go to 语句避免重复判断.仔细研究前一部分给出的程序段就会发现其中存在着大 量的重复判断.假设当前第 k 步及下一步第 k + 1 步的边沿元类型及方 向如图 3 (a) 所示, 如果利用 go to 语句就可直接转到图 6 对其 余两个像素 (i+ 1j与i+ 1j+ 1) 进行判断, 得到第 k +2 步的跟踪方向; 否则, 就必须再判断图 3 (a ) 中的i+ 1j与i+ 1j+ 1两个像素的类型 (第 k + 1 步的边沿元的方向及 类型) 后, 才能到达图 6. 而这两个判断其实在第
22、 k 步时已经作过了, 即重复判断.这样的重复判断在跟踪过程中的每一步至少有 2 次, 最 多时有 4 次. 仔细观察图 3 6 就可知道, 图中 H 边沿元与 V 边沿元之间的转换占 34, 因此这种重复判断的数量是很高 的. 但出人意料的是, 实验表明, 这种重复并没有占多少时间(参见表 2).表 2 使用与不使用 go to 语句的速度差异对图象做网格扫描, 只有与网格线相交的区域才有可能被跟踪, 那些完全落在网格内的区域则被忽略. 因此, 本次实 验中边界点的数目有所减少. 表 4 表明, 采用网格扫描也可以极大地提高处理速度.1t ick , 1 s= 18. 2 t ick , 下
23、同. 实验环境为 IBM 386 (DO S). 之所以选择这样的实验环境是为了便于向并行处理平台移植.图象跟踪时间 (w itho u t go to )跟踪时间 (w ith go to )边界点数目B lo ck44986G ir l665121B r idge989828图象跟踪时间 (逐行扫描)跟踪时间 (1616 网格扫描)边界点数目B lo ck40. 6964G ir l61. 64251B r idge92. 87228图象跟踪时间跟踪时间 (h uge)边界点数目B lo ck420986G ir l6215121B r idge9329828图象计算各像素的边界值不计算各
24、像素的边界值边界点数目计算时间跟踪时间总计跟踪时间B lo ck64104986G ir l661265121B r idge6915998286 期史 册 等: 对一种快速边缘跟踪算法的讨论645另外, 还可以根据感兴趣的目标大小预先确定一个长度阈值, 对获得的链码进行选择: 只有长度大于该阈值的链码才 予以保留. 虽然此步对边缘跟踪算法本身的处理速度没有多大影响, 但它可以减少后续处理的数据量, 从而达到提高整个系统处理速度的目的.度来说, 处理速度的提升空间已经很有限. 欲满足实时处理系统 的要求, 最好的方法就是采用并行处理的环境和方法 ( 例 如: 将图象分块, 分布到多个处理器上同
25、时进行跟踪, 然后再合并跨分块的边界). 关于并行处理环境下, 边缘跟踪的快速算法问题, 另有专文进行论述, 本文就不再讨论.3结论参 考 文 献本文介绍了一种较好的快速边缘跟踪算法的思想, 并对实现过程中遇到的几个问题做了深入的探讨.本文给出的算法处理速度已经很快, 足以满足一般情况 下的实际应用. 但对于 25 帧秒的电视频率而言, 一帧图象的 处理时间只有 40m s, 这样的处理速度还是太慢. 但在目前单 处理器的实验环境下, 要想进一步大幅度提高处理速度, 已经 是不太可能了. 因为无论是从原理思想还是从具体实现的角费旭东. 实时图象理解中特征提取及符号表示的研究. D 浙江大学学位
26、论文. 1993, 5史册. 实时知识基图象理解系统. D 浙江大学学位论文. 1997, 1T. P av lid is. A lgo r ithm s fo r g rap h ic s and im age p ro ce ssing. M Com p u te r Sc ience P re ss, 1982吴宇岚. 实时图象理解系统中符号提取的设计与实现和小波变换 在图象处理中的应用. D 浙江大学学位论文. 1996, 1吴立德. 计算机视觉. M 上海. 复旦大学出版社. 1993, 1212345A D IS CUS S IO N O F A FAS T ALGO R ITHM
27、 FO R BO UNDAR Y TRAC INGSH I C e(Z h ej iang U n iv ersity , D ep t. of I nf orm a tion S cience & E lectron ic E ng ineer ing H ang z h ou 310027)A bstrac t T h is p ap e r f ir st in t ro duce s th e idea o f a fa st a lgo r ithm fo r bo unda ry t rac ing, th en d iscu sse s in de ta il how to reduceth e p ro ce ssing t im e o f th e a lgo r ithm.Key words Com p u te r v isio n; R ea l2t im e im age p ro ce ssing; C h a in co de; Bo unda ry t rac ing
