基于三角划分的多连通域图形匹配研究
2010-03-21刘晓平何士双
刘晓平， 何士双
（合肥工业大学计算机与信息学院VCC研究室，安徽 合肥 230009）
目前，在工程应用领域设计人员已经广泛使用CAD软件进行工程图纸辅助绘制，但由于通用CAD软件不具有表示工程图纸的工程和物理属性的功能，造成了工程图纸的设计与理解过程的脱节。因此，正确地识别和匹配工程图纸中的符号是完成图纸的自动理解、用料估算、自动生成工艺工序卡片的重要前提。
当前国内外对图形的识别和匹配做了相关研究。文献[1]和文献[2]分别提出基于规则和特征的方法对建筑图纸进行识别，然而对以图形为工程符号主要特征的工程图纸来说，特征与规则的提取本质上是对多连通域图形的表示，因此难以总结具体规则。文献[3]根据图形作业批改的特点提出了基于图元特征的匹配技术，然而其依靠图形的绝对位置关系建立的匹配规则不适用于存在旋转和缩放的工程图纸符号识别。文献[4]提出采用区域邻接图表示工程图纸的方法，通过使用子图匹配方法实现符号的识别，但其仅能处理各连通域邻接的情况，对于包含连通则无法处理。
因此，根据多连通域图形的特点提出采用包围多边形、连通多边形完成对其进行表示。针对图形中存在的包含连通情况，通过使用三角划分解决了连通多边形间的定位问题。应用此方法，解决了多连通域图形的旋转、缩放匹配问题。
1 多连通域图形的表示
1.1 多连通域图形
定义1多连通域图形是由多个多边形通过邻接、包含组合产生的具有多个连通域的图形。
按照多边形所在区域间的覆盖范围可以分为邻接和包含，对于多边形存在区域交叉的情况则可以进一步划分多边形为若干个子多边形，最终仍可用邻接和包含关系表示；按照多边形区域的连接方式可以分为点连接、边连接和空连接。如图1所示，对于图1(a)中的多边形a和b，按照上述的组合方式可以组成8种多连通域图形，其中图1(d)的组合方式比较特殊，在工程图纸中被用来表示两个工程符号，因此不属于多连通域图形。
图1 多边形组合方式
由定义可知，多连通域图形具有以下性质：
性质1不存在孤立边，即每条边的两端必须连接其他边；
性质2不存在孤立的连通域，即多连通域图形具有唯一的外轮廓。
1.2 包围多边形
定义2包围多边形是由若干条边组成的首尾顺序连接、用于表示多连通域图形外轮廓的封闭边链表。
由多连通域图形的定义可知，包围多边形中可能会包含重复边。利用多连通域图形的特点，建立了起点与起边概念，方便获取包围多边形。
定义3起点是多连通域图形中以<最小x，最小y>且x优先的原则获取的点。
定义4起边是与起点连接的边链表中按逆时针排序的第一条边。
如图2所示，点p1为包围多边形的起点，边
图2 起点、起边示意图
1.3 连通多边形
定义5 任取包围多边形内不在边上的任意点，称包含该点的最小多边形为连通多边形。
根据上述定义，对于图1的7种有效组合方式，获取多连通域图形的连通属性如表1所示。其中，
从表1中可以看出，对于邻接连通，除去(f)之外，原a、b多边形均可表示自身所在的连通域，而(f)则由于原a、b多边形在内部边邻接，因此连通多边形发生了进一步划分，为
表1 连通属性表
利用起点、起边的性质，通过顺时针逐渐遍历多连通域图形，实现寻找连通多边形。以下是获取一个连通多边形的算法：
Step 1获取起点、起边，若为空则退出；
Step 2设置起边的另一端点为中心点，按顺时针顺序找出与中心点连接且起边夹角最小的边；
Step 3若该边在边链表已经存在，则删除链表中该边至末尾的所有元素，设置当前边为起边，当前边中心点的另一端点为起点，跳至Step 2；
Step 4若该边与边链表中的边存在重复交点，则删除链表中第一重复交点的边至末尾的所有元素，设置当前边为起边，当前边中心点的另一端点为起点，跳至Step 2；
Step 5若该边不是起边，则保存当前边，设置当前边为起边，当前边中心点的另一端点为起点，跳至Step 2；
Step 6删除起边，删除孤立边，跳至Step 1，准备获取下一个连通多边形。
2 基于三角划分的多连通域图形匹配算法
2.1 三角划分
通过采用包围多边形与连通多边形基本实现了对多连通域图形的表示，但是由于图形存在包含连通情况，仅仅通过包围多边形和连通多边形并不能准确表示图形内部结构，因此如何表示包含连通是能否匹配成功的关键。在图3中，矩形可以按任意旋转角度放置在梯形中，而连通多边形不变，如图3 (a)、(b)所示。针对上述问题，通过添加辅助线实现对包含连通的划分，将包含连通分解为邻接连通，通过邻接连通实现图形的定位。
图3 包含连通
添加辅助线的思想是当连通多边形存在包含连通时，根据匹配编码找出对应边，以匹配边为基础添加辅助线建立三角形，从而实现三角区域划分。以下是添加辅助线的规则：
规则1在外层连通多边形包含的区域内，找出与边两端点的距离之和最近点，建立端点与最近点之间的边，即满足包含、最近距离原则；
规则2辅助线不能与任何边有交叉，即满足无遮挡原则。
规则确保两个图形在匹配的过程中能有效地对包含连通进行有效划分，但是对于某些特殊情况，可能会存在若干个可选最近点，因此为了匹配正确性，需要遍历所有的可选点，如图2(a)所示，存在着p1、p2两个可选点，分别按照p1、p2建立辅助线。
2.2 包围多边形匹配
国内外学者对多边形匹配问题已经进行了大量研究[5-6]，但是由于包围多变形存在多个重复边的情况，并且需要通过包围多边形的匹配来为下一次的匹配进行定位，因此需要进行特殊处理。通过建立<属性边、夹角>结构，实现对包围多边形的几何与拓扑表示，并且同时满足了连通多边形的匹配要求。
其中，属性边是由边长度、匹配编码号、辅助线标记组成。匹配码是两个包围多边形匹配成功后对应边的编号，辅助线标记表示是否为匹配过程中添加的辅助线。由于对每次包围多边形匹配的结果进行了编码，因此为多连通域图形的全过程匹配提供了依据。
包围多边形主要是对多连通域图形的外轮廓描述，在某些情况下会存在一定的对称特性。因此，用于描述包围多边形结构的<属性边、夹角>链表结构将会存在重复。如图4(a)、(b)所示，由于图形外轮廓具有两重对称性，因此包围多边形具有两个重复模式。在进行匹配时，不同的匹配模式将会导致不同的三角划分，如图4 (a)、(b)中辅助线所示，因此在匹配多连通域图形时需要遍历包围多边形的所有匹配模式，以确保匹配的正确性。
图4 两重对称的包围多边形
2.3 多连通域图形匹配算法
多连通域图形匹配的基本思想是利用包围多边形实现图形的外轮廓匹配定位，在此基础上通过匹配编码删除对应的连通多边形实现多连通域图形的收缩，最终完成匹配。匹配的本质是从外至内不断删除连通域的过程，具体实现算法如下：
Step 1针对待匹配件进行预处理，包括合并重复线、直线断点补合、删除孤立边等；
Step 2获取标准件与待匹配件的包围多边形，进行包围多边形匹配；
Step 3若成功，则对图形进行编码；若失败，则退出；
Step 4分别找出编码最小边，找出该边所在的连通多边形，判断连通多边形是否存在包含连通，若存在，则根据该边进行三角划分；
Step 5找出该边所在的连通多边形，进行多边形匹配；
Step 6若成功，则删除该边，删除孤立边，跳至Step 2；若失败，则退出。
3 实验分析
3.1 图形匹配实例
根据上述算法，以下给出了具有一个包含连通的简单图形的匹配全过程。从表2中可以看出，总共经过了5次匹配，分别在第1次和第3次添加了辅助线。其中，在第1次匹配时，首先根据原图的包围多边形实现图形的外轮廓匹配，从而确定具体的匹配边，然后判断出存在包含连通，因此依据匹配编码添加了两条辅助线（用虚线表示），将包含连通转化为邻接连通，完成了第1次匹配，成功地实现了连通域的删除，收缩多连通域图形的范围，然后再经过4次匹配即实现了图形的匹配。
3.2 线束图纸识别实例
论文提出的方法已经在以AutoCAD为平台使用ObjectARX进行二次开发的汽车线束工艺辅助设计系统的中得到了验证。该系统主要是通过对表示汽车线束连接关系的图纸进行理解分析，生成用于指导实际生产的工艺、工序卡片和进行物料统计。
表2 多连通域图形匹配过程
线束图纸主要包括图框、图纸规格说明、接插件、线束等部件，其中接插件是表示线束连接关系和进行图纸布局的主要部件，具有多连通域图形的特点，因此是主要的识别对象。在对图纸进行自动识别的过程中，该系统以接插标准件库为基础[7]，首先对线束图纸进行预处理，去除干扰信息；然后，遍历标准件库，依据多连通域图形的唯一外轮廓特性，分别将标准件与线束图纸中的各个孤立的外轮廓区域进行匹配，找出在图纸中使用的库中的接插件。
图5所示是型号为91601-V6050的汽车左顶线束总成图，其中包含22个接插件，在图纸中用箭头所指示的放大图形为示意。通过识别和匹配，找出了图纸中的20个接插件。对于图纸中用实线椭圆标志的接插件，由于在标准件库中不存在，未被成功识别；另外，对于用虚线椭圆标志的接插件，由于设计者在绘制时发生图形信息遗漏，同样也未能识别。因此，可以分别通过引入模糊匹配思想和提高标准件库的完整性的方法提高线束图纸的识别率。
图5 线束图纸识别示意图
4 总结与展望
工程图纸的自动识别是进行图纸理解的基础。论文针对工程图纸中出现的多连通域图形匹配问题，首先，提出通过添加辅助线实现三角划分，解决了包含连通的定位问题；然后，基于包围多边形和连通多边形的匹配，根据匹配编码逐步删除连通域，收缩多连通域图形，最终实现图形匹配。
在图纸识别过程中存在许多不确定性因素，仅仅通过精确匹配容易出现漏识别的现象，因此若将图形相似特性引入到匹配中来将有效地提高识别率。文献[6]已经对多边形的相似匹配做了研究，然而尚不能有效解决多连通域图形的相似匹配问题，因此找出一种可行、高效的方法是未来研究的重点。
[1]王蛛华, 曹 阳, 杨若瑜, 等. 基于规则的建筑结构图钢筋用量自动识别系统[J]. 软件学报, 2002, 3(4):574-579.
[2]沈 怡, 蔡士杰, 高 晓. 建筑工程图符号的特征匹配识别方法[J]. 计算机辅助设计与图形学学报,2003, 15(9): 1065-1069.
[3]刘就女, 吴东庆, 彭小敏, 等. 智能图元特征提取与图形匹配技术[J]. 工程图学学报, 2005, 26(4):146-150.
[4]Llados J, Marti E, Villanueva J J. Symbol recognition by error tolerant subgraph matching between region adjacency graphs [J]. IEEE Trans on Pattern Analysis and Machine Intelligence, 2001, 23(10): 1137-1143.
[5]王雪飞, 胡青泥. 基于分层加权的多边形图形匹配[J].工程图学学报, 2002, 23(2): 89-96.
[6]谭建荣, 岳小莉, 陆国栋. 图形相似的基本原理、方法及其在结构模式识别中的应用[J]. 计算机学报,2002, 25(9): 959-967.
[7]何士双, 徐本柱, 吴 黄, 等. 基于AutoCAD的线束电器件库的建立[C]//全国第18届计算机科学与技术应用(CACIS)学术会议, 2007: 937-940.
