摘要CAD推广和普及的关键步骤之一，主要解决已有大量图纸再利用问题。在工程图纸扫描图象识别研究中，圆弧识别是识别算法中的重点和难点。传统的圆弧识别多是基于线段逼近。本文提出一种基于单义域邻接图的圆弧及圆识别算法，可以直接提取圆弧。对二值图象作水平黑游程编码，相关游程基于线宽与拓扑的一致性构成条形域，对其中多义域进行分裂得单义域（线段域和圆弧域）。单义域邻接图可较好描述图象的几何属性与拓扑关系。单义域具有明显的形状意义（线段、圆弧、箭头等），提高了识别的整体性。圆弧及圆的识别先从邻接图顶点中抽取圆弧域，作为种子圆弧，然后从此出发遍历图，按照同圆来建立路径，进行整弧和整圆增长，最终获得圆弧和圆的几何表达。实例表明，本算法可以较好地处理圆弧与线段及圆弧的相交与相切，适应性较强、识别率较高。

关键词 工程图纸，矢量化，圆弧识别，条形域，单义域邻接图。

1 引言

圆弧和圆是工程图形中的重要图元，已有多种识别算法，可分为两种：逼近法和直接法。细化方法先跟踪中心骨架象素得到短小线段，再用来逼近圆弧和圆[1]。正交扫描法（orthogonal zig-zag）是先获得条，再用中垂线跟踪（perpendicular bisector tracing）分割圆弧[2]。文献[3]以梯形域来逼近圆弧和圆。这三种方法都是以线段来逼近圆弧和圆，如果线段过短，会造成数据冗余；如果线段过长，将难以识别短小圆弧，需要后续处理。轮廓匹配法可直接获得圆弧和圆，但，轮廓获取及其匹配都很复杂[4]。文献[5]采用图段与圆进行模式匹配，确定圆的种子图段，然后跟踪其它图段，最终获得圆弧和圆的图形表示。

本文提出一种新的识别方法，以相关游程线宽和拓扑为约束生成条形域，对其中多义域作分裂获得单义域：线段域和圆弧域，并建立其邻接图，选取弧形域，以此为起始点，基于同圆几何要求，通过深度优先搜索来遍历图，完成圆弧和圆识别。下面分为四部分，先介绍条形域构建和多义域分裂，然后给出建立单义域邻接图方法，并对整弧和整圆增长算法进行详细论述，最后对多种圆弧与圆的识别结果作出分析。

2 条形域构建和多义域分裂

2.1 游程分类

在同一线宽的二值图象中，一个游程唯一属于单一图元，所以，对工程图纸扫描图象先作图文分离再作粗细分离[3]，然后对同一线宽图象进行处理。本文采用自上而下和从左到右扫描，定义同一行中连通黑象素为一水平黑游程，并以此对图象进行编码。如果当前游程是参考游程的上（或下）一行，且左右至少一端搭接（包括邻接），则称两个游程相关，具有父子（或子父）关系。游程可以根据其父子游程进行分类[6]，本文针对工程图纸扫描图象特点，分为七类（如图1所示）：

（1）孤立游程：没有父游程和子游程；

（2）起始游程：没有父游程，只有一个子游程；

（3）终止游程：没有子游程，只有一个父游程；

（4）单一游程：只有一个父游程和一个子游程；

（5）分叉游程：有多个子游程，至多一个父游程；

（6）汇合游程：有多个父游程，至多一个子游程；

（7）交叉游程：有多个父游程和多个子游程。

2.2 构建条形域

（1）游程相关；

（2）首游程不是分叉游程和交叉游程，末游程不是汇合游程和交叉游程；

（3）游程宽度没有较大变化；

（4）孤立游程和交叉游程单独构成条形域。

条件（1）保证条形域的连通性，（2）确保交叉域、汇合域和分叉域的准确建立，（3）是条形域宽度一致性的要求，（4）处理特殊情况。

（1）移游程到新建条形域中，设为当前游程，如果是孤立游程、分叉游程或交叉游程，则转到（4）;

（2）取当前游程的子游程，如果与当前条形域游程平均宽度相差较大，则转到（4），否则，设为当前游程;

（3）如果当前游程是单一游程，则加入条形域，并返回（2）；如果是分叉游程或终止游程，则加入条形域；

（4）完成条形域构建。

2.3 分裂多义域

在这里，多义域是开环的，且单调，相对一般曲线拟合要简单些，本文采用首尾相连最大距离法来分裂[7]。对多义域，先用一条直线连接首尾游程中点，计算多义域游程中点与直线的最大距离差，并以此点为一分裂点，然后判定所分裂的两段是否为单义域，如仍为多义域则继续分裂，一直进行到都是单义域为止，这是一个递归的过程。下面给出分裂步骤：

（1）输入条形域，如为单义域，则转到（5）;

（2）对多义域以最大距离法分为两段：域1和域2，输出分裂点；

（3）如果域1（域2）为多义域，则返回（2）；

（4）对分裂点以其y坐标作从小到大排序；

（5）根据分裂点，输出单义域。

3单义域邻接图的建立及其拓扑分类

3.1 建立单义域邻接图

（1）加单义域到邻接图的顶点表中；

（2）取顶点i，i从1到n，n为图的顶点总数，

取顶点j，j从1到n，

如果顶点j是顶点i的父域，则加顶点j到顶点i的父邻接表，且加顶点j到顶点i的邻接表；

如果顶点j是顶点i的子域，则加顶点j到顶点i的子邻接表，且加顶点j到顶点i的邻接表；

图2给出圆的图表示，顶点1的父邻接表为空，子邻接表包含顶点2和3；顶点2的父邻接表包含顶点1，子邻接表包含顶点4；顶点3的父邻接表包含顶点1，子邻接表包含顶点4；顶点4的父邻接表包含顶点2和3，子邻接表为空。

3.2 单义域拓扑分类

从单义域邻接图中很容易就可获得某一顶点的邻接点情况，单义域（顶点）根据其父子域（邻接点）可以分为七

转贴于 大学生素质网 Http://Www.Uscc.Com.Cn

本文引用地址：http://www.uscc.com.cn/Discourse/Demonstrate/Science/Engineering/200609/Discourse_5101.htm