·4·　　 (总 474)　 　　　　　　　　　　　　　图象处理中多边形拟合的快速算法　　　　　　　　　　　 　　　 2001年 图 象 处 理 中 多 边 形 拟 合 的 快 速 算 法 Fast Polygonal Fitting Arithmetic of Image Process 　 　　　张　帆　　　　　　　　　　　　翟志华　　　　　　　　　　　　张新红　　　　 (江苏理工大学 镇江 212013) (河南大学 开封 475002) (河南省工商行政管理学校 郑州 475002) 【摘　要】　提出了一种简单高效的多边形拟合算法 ,不必采用递归调用的方法 ,仅在对目标图象的边界数据的一 次遍历中 ,即可计算出所有的多边形拟合点 ,避免了递归调用中的重复运算 ,有利于计算机图象的实时处理和在 线检测。 实践证明 ,采用这种算法可得到满意的结果。 【关键词】　图象处理 , 多边形拟合 , 快速算法 ABSTRACT　 A simple and hig hly efficie nt po lyg o nal fitting a rithme tic is inroduced, a nd the arithmetic can av oid r epea ting calcula- tio n during t raveling object image bo unda ry da ta and all po ly go nal fitting points can be computed w itho ut the metho d o f r ecur sion call, a nd benefits to co mputer imag e real time process and o n line test. The ideal result can be obtained thro ug h this approach in practice. KEYWORDS　 imag e processing , polyg o nal fit ting , fast a rithme tic 　　在计算机图象处理技术中 ,经常要提取目标图象 的形状特征 ,如长度、宽度、边长、面积等 ,以便于后续 的图象处理和识别。由于数字图象的数据量一般很大 , 计算机在处理这些复杂图形计算时会消耗大量机时。 为了减少数据量 ,提高效率 ,一般采取先确定目标图象 的边界 ,再以多边形拟合的方法 ,以直代曲 ,以多边形 来拟合目标图象不规则的边界曲线。 这样可以在形状 失真度很小的情况下有效地减少数据量。 得到这个拟 合多边形后 ,再计算多边形的长度、宽度、边长、面积等 是十分简便的。 由这些数据又可进一步计算一些描述 目标图象形状的特征值 ,如图形复杂度 ,动量矩等。 因 此 ,多边形拟合是计算机图象处理中的一个重要环节。 目前常用的多边形拟合技术是迭代端点拟合法。 这种 方法在编程调试时比较困难 ,而且运算量大 ,处理速度 较慢。为了进一步提高处理速度 ,我们在使用多边形拟 合技术中 ,摸索出一种简单高效的多边形拟合快速算 法。这种算法不采用递归调用的方法 ,仅在对目标图象 的边界数据的一次遍历中 ,即可计算出所有的多边形 拟合点 ,避免了递归调用中的重复运算 ,方便快捷 ,大 大提高了处理速度 ,有利于计算机图象的实时处理和 在线检测。 1　图象边缘检测 图象边缘检 测可以采用拉 普拉斯 ( La placian) 算 子 ,它定义为: 5 2 f ( x , y ) = 2 x 2 f (x , y ) + 2 y2 f ( x , y ) 以差分运算来代替微分运算 ,则: 5 2 f ( x , y ) = f ( x + 1, y ) + f ( x - 1, y ) + f ( x , y + 1) + f ( x , y - 1) - 4f ( x , y ) 由于拉普拉斯算子是一个二阶导数 ,二阶导数在 图象的边缘处为零 ,它将在边缘处产生一个陡峭的零 交叉。 但是 ,实验表明由于噪声的原因 ,采用拉普拉斯 算子进行边缘检测效果不理想 ,需要采用高斯 ( Gaus- sia n)低通滤波消除噪声。 高斯滤波表达式为: g (x , y ) = G( x , y )* f ( x , y ) = 1 2ce2 ex p( - x 2+ y 2 2e2 )* f ( x , y ) 式中: e是高斯函数的标准差 ; * 表示卷积。 可以把拉普拉斯算子和高斯脉冲响应组合为一个 高斯拉普拉斯算子: 5 2 1 2ce2 ex p( - x 2+ y2 2e2 )= 1 ce4 ( 1- x 2+ y2 2e2 ) ex p( - x 2+ y 2 2e2 ) 对经过高斯拉普拉斯算子滤波后的图象用零灰度 值进行二值化会产生闭合的、连通的轮廓并消除了所 有的内部点。 另外 ,在实验中采用边缘跟踪法并以 Freman 链 码表示图象的边缘信息也取得了很好的效果。 获得图象的边缘数据后即可进行多边形拟合。 * 　　 2000 11 20收到 , 2001 07 14改回 * * 　张帆 ,男 , 1967年生 ,工程师 ,硕士研究生 ,研究方向: 图象 处理、模式识别、多媒体数据库。 

第 14卷　第 10期　　　　　　 　　　　　　　　　电 脑 开 发 与 应 用　　　　 　　　　　　　　　　 (总 475)　　　 ·5· 2　迭代端点拟合法 迭代端点拟合法是一种迭代算法 ,利用了计算机 高级语言中递归调用的方法。 其算法步骤如下: ①设定一个阈值 T。 ②在目标图象的边界曲线选取两点 ,如图 1中的 A, B 。 ③计算在边界曲线上 A , B 两点间所有点到 AB 直线间的距离。确定距 AB 直线间的距离最大的点 ,如 图 1中的 C ,记最大距离为 H。 ④比较最大距离 H和阈值 T ,如果 H小于 T ,迭 代结束。 ⑤ C 点将目标图象的边界曲线分为 AC 和 CB 两 条曲线 ,对这两条曲线重复步骤②、③、④、⑤。 由于重 复上述步骤时都要产生两个分支 ,因此在算法上要采 用递归调用的方法 ,不断迭代求解 ,直到目标图象的边 界曲线上所有点与拟合多边形各边的距离小于设定的 阈值 T 。 从上面的算法可以看出 ,程序运行时不断重复调 用自身 ,目标图象的边界曲线的很多点都多次进行点 到直线间距离的计算。正是由于这种大量和重复计算 , 使处理速度较慢。 编程和调试时有一定困难。 图 1　迭代端点拟 合法示意图 图 2　多 边形拟合快 速 算法示意图　 3　多边形拟合快速算法 我们提出这种多边形拟合算法的出发点是避免重 复运算 ,提高处理速度。其基本思路是不采用递归迭代 的方法 ,而是以固定步长沿目标图象的边界曲线进行 搜索 ,只对约一半的边界象素点进行点到直线间距离 的计算 ,而且这种计算对这些象素点只进行一次 ,仅在 对目标图象的边界数据的一次遍历中 ,即可计算出所 有的多边形拟合点。 算法步骤及原理如下: ①设定一个阈值 T。 ②在目标图象的边界曲线选取一点作为出发点 , 如图 2中的 A 。 ③取从 A点沿目标图象的边界曲线向前 4 T 个象 素的点为第一步搜索的终点 ,如图 2中的 B。 ④取从 A 点沿目标图象的边界曲线向前 T 个象 素的点 ,如图 2中的 C。 取从 A 点沿目标图象的边界 曲线向前 3 T 个象素的点 ,如图 2中的 D。曲线段 A C 之间及曲线段 BD 之间的象素点数均为 T 个 ,在这两 曲线段上的象素点到 AB 直线间的距离均不可能大于 阈值 T ,因此可以不处理这些象素点。这样 ,在完成对 整条边界曲线的搜索后 ,将只对约一半的边界象素点 进行点到直线间距离的计算。 ⑤从 C 点开始到 D 点求每个象素点到 AB 直线 间 的距离 , 取 最大距 离处 的点 为 E , 并最 大 距离 为 H 。 ⑥如果 H 大于阈值 T ,则把 E 点作为一个多边 形的顶点。这样 ,把曲线段 AB 分成了两段。曲线段 A E 之间及曲线段 B E 之间的象素点数均小于 2 T 个 ,在 这两曲线段上的象素点分别到 A E 直线和 B E直线间 的距离均不可能大于阈值 T ,因此可以不再处理这些 象素点。 以 B 点作为出发点 ,重复步骤②、③、④、⑤、 ⑥。 如果 H 小于阈值 T ,则说明曲线段 CD 间也不存 在到 AB 直线间的距离大于阈值 T 的点。以 B 点做为 出发点 ,重复步骤②、③、④、⑤、⑥ ,进行下一步搜索 , 直至回到原始出发点。 4　对比实验 为了对比两种算法的运算效果 ,我们进行了对比 实验。处理图象是一幅烟叶图象 ,已通过边界跟踪算法 获得了边界数据 ,分别如图 3、图 4所示。 图 3　原始图象 图 4　目标图象的 　　边界曲线 　　为了使对比效果明显 ,采用小阈值 T = 2。 运算时 间包括绘制拟合多边形的时间。 对比实验结果如下: 图象数据: 尺寸　 510× 475　　边界象素点数　 1 548 从对比实验结果可以看出 ,我们的多边形拟合算法 明显优于迭代端点拟合法。迭代算法进行点到直线间距 离的计算次数是 11 729次 ,平均运算时间为 48. 59s。而 改进的算法仅为 970次 , 0. 32s。前者进行点到直线间距 (下转第 8页 ) 

·8· 　　 (总 478)　 　　　　　　　　　　　　 C+ + 中指针和引 用传递函数参数剖析　　　　　　　　　　　 　　 2001年 int* IncB( int i) {　 int b= 10; b+ = i; 　 r eturn & b;　 / /返回了一个局部变量的地址! } vo id main( ) {　 int* bPtr= IncB( 5) ;　 / /产生了悬挂指针! 　 int* a Ptr= IncA( 5) ; 　 cout < < "a= " < < * a Ptr < < endl; 　 cout < < "b= " < <* b Ptr < < endl; } 运行结果为: a = 15 b = 6 618 600 函数 Inc A( )将 a 的值正确地增加了 5,而 IncB( ) 却使 b的值变成了难以预料的后果。 这是因为 a 是全 局变量 ,它在全局变量内存区中一直存在 ,而 b 是局部 变量 ,它存在于函数的栈区 ,当函数 IncB( )调用过程 结束后便消失 ,因此返回的指针 b Pt r指向了一个不确 定的区域 ,使指针悬挂 ,便产生了以上的运行结果。 总 结起来 ,指针函数可以返回堆地址 ,可以返回全局或静 态变量的地址 ,但不能返回局部变量的地址。 在返回引用时 ,被调函数直接将全局变量返回给 调用函数 ,从而避免了栈空间中临时变量的产生 ,这使 程序的执行效率和空间利用率都得到了提高。 同样的 道理 ,函数也不可返回一个对局部变量的引用 ,即悬挂 引用。 3. 2　函数返回的引用作左值 因为引用返回时不产生任何变量的副本 ,而总是 与某个全局变量维系在一起 ,这意味着返回一个引用 可使一个函数调用成为左值表达式。 这是返回值或返 回指针所无法实现的。 例如: # include < io stream. h> char s [ 40 ]= " Hello , w o rld. "; char& repla ce(int i) { retur n s [i ]; } vo id main( ) { co ut < < s < < endl; 　 r eplace( 5)= "! ";　 / /将 s [ 5]的内容’ ,’ 更改为’ ! 　 cout < < s < < endl; } 运行结果为: Hello , w or ld. ’ Hello! w o rld. 4　结束语 指针和引用使函数的“黑盒”性被打破 ,函数可以 访问不属于自己栈空间的内容 ,这给函数调用带来了 极大的灵活性和很高的效率。 但这对把握不住 C+ + 的人来说是危险的 ,因为传址方式和引用方式会使所 传递的参数处于随时被修改的危险之中。 这时为了保 护实参不被修改 ,可以传递 const 指针和引用。如在上 述传递复数 co mplex 类时使用的是 const 引用。 在传 递引用的过程中还可能碰到的一个问题是 ,如果有两 个重载函数: f un( int x ) , f un( i nt& x ) ,若有调用语句: ind a = 3; f un( a ) ; 则会造成编译器无法确定使用哪 个重载函数 ,因为这两个重载函数在调用时实参格式 是相同的 ,这时只好放弃函数重载。虽然指针和引用作 函数参数带来了诸如可读性不强、调试过程复杂等问 题 ,但它给程序设计带来的高效足以掩盖这些弊病。广 大的 C+ + 程序员应当熟练地掌握指针和引用 ,设计 出更为高效的程序。本文所示程序段用 Bo rland C+ + 5. 0调试通过。 1　钱 能 . C+ + 程序 设计 教程 .北 京: 清华 大学 出版 社 , 1999: 参 考 文 献 145～ 203 2　方旭 ,张 克强 ,曲文路 . Bo r land C+ + 4. 0程 序设计 .北 京: 北京航空航天大学出版社 , 1995: 284～ 318 　　 (上接第 5页 ) 离的计算次数是后者的 12倍 ,在运算速度上改进算法 比迭代算法快了约 150倍。 图 5是采用多边形拟合 快速算法 ,取阈值 T = 20时 拟合出的多边形图象。这种多 边形拟合算法编程方法十分 简单 , 计算速度很快 ,在配置 较低的计算机上也可以快速 处理数据。而且这种改进的多 边形拟合算法可以在一定程 图 5　拟合出的多 　　边形图 象 度上修复目标图象边界曲线 的小缺陷 ,方便了后续的数据处理。 总之该算法是一种 简单高效的多边形拟合算法 ,避免了递归调用中的重复 运算 ,方便快捷 ,大大提高了处理速度 ,有利于计算机图 象的实时处理和在线检测。 1　 K R卡 斯 特 曼 .数 字 图 象 处 理 . 北 京: 电 子 工 业 出 版 社 , 参 考 文 献 1998: 434～ 440 2　 徐建 华 . 图象 处理 与分 析 .北 京: 科学 出 版社 , 1992: 169～ 172 3　 黄风 岗 ,宋克 欧 . 模式 识别 .哈 尔滨: 哈 尔滨 工程 大学 出版 社 , 1998: 112～ 121 4　戚飞虎 著 . 模式识别 与图象 处理 .上海: 上海 交通大学 出版 社 , 1990: 21～ 34