基于单义域邻接图的圆弧与圆识别

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

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

1 引言

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

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

2.1 游程分类

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

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

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

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

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

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

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

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.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 单义域拓扑分类

从单义域邻接图中很容易就可获得某一顶点的邻接点情况，单义域（顶点）根据其父子域（邻接点）可以分为七种拓扑类型（如图3所示）：

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

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

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

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

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

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

在图3.a中，孤立域1表示一个图元，即一条线段。在图3.b中，交叉域7连接起始域2和终止域3，组成一条线段，还表示该线段与另一线段相交于此。可以看出，单义域不仅为单一完整图元的获得提供几何数据，而且也为图元之间的拓扑关系提供线索，单义域邻接图比较完整地了表达图象的几何数据与拓扑关系。

4 圆弧识别

4.1 确定种子圆弧

本文采用假设验证法从单义域中提取圆弧域，主要思路是，先假设候选域为圆弧域，采用最小二乘法来其几何定义数据（圆心和半径）^[8]，并计算平均径向误差和最大径向误差，如果小于阈值，则判定为圆弧域，作为种子圆弧，以指导圆弧和圆的识别。

， 。

4.2 识别圆弧与圆

（1）从单义域邻接图的顶点集中提取弧形域，作为种子圆弧，设为当前域；

（2）如果当前域无邻接域，则转到（4）；

（3）取当前域的邻接域i，i从1到n，n为邻接域总数

{

如果邻接域i与种子圆弧同圆，则种子圆弧生长，并设邻接域i为当前域，同时返回（2）；

取邻接域i的邻接域j，j从1到m，m为邻接域i的邻接域总数

{

如果邻接域j与种子圆弧同圆，则种子圆弧生长，并设邻接域j为当前域，同时返回（2）；

}

}

（4）如果该路径为回路，则得一圆，否则得一圆弧，计算其几何数据，获得矢量表达。

本算法不仅能够识别单独的圆弧和圆，而且还兼顾圆弧（圆）与线段、圆弧（圆）的相交和相切等情况。在图4中，原始图象（a）经过图文分离和粗细分离，包含圆和多种圆弧，（b）对图象多义域进行分裂，（c）为图象的单义域表达，（d）为矢量化图形。由结果可以看出，该法识别能力很强，能处理多种圆弧和圆。

[1] Vijay Nagasamy and Noshir A. Langrana. Engineering Drawing Processing and Vectorization System. Computer Vision, Graphics, and Image Processing, 1990，49：379-397