自动化学报
ACTA AUTOMATICA SINICA
1999年 第25卷 第6期 Vol.25 No.6 1999



线状图形矢量化中的行段分析与后处理
邹荣金　蔡士杰　张福炎
摘　要　针对目前工程图纸识别中存在的几项难点技术，提出基于行程编码的矢量化方法，对小弯度直线的纠正问题、特征线段的延伸与合并算法进行了研究.同时使用图像局部形态分析的方法，直接在原图像上进行识别，保证了图像信息的完整性和可检测性.该项研究结果在建筑工程图纸的自动识别及自动计算中得到了较好的应用.
关键词　图像扫描，行段，工程图矢量化，识别.
GRAPH SEGMENT ANALYSIS AND POST-PROCESSING
OF LINE GRAPHICS IN ENGINEERING
DRAWINGS VECTORIZATION
ZOU Rongjin　CAI Shijie　ZHANG Fuyan
(State Key Laboratory of Software Novel Technology, Multimedia Research Institute,
Nanjing University, Nanjing　210093)
Abstract　This paper proposed a vectorization method based on the run length coding for recognition of engineering drawings. We studied the aspects of the small bend line correction problem as well as the combining and extending algorithm of the vectorization line segments. At the same time, image morphology analysis method was also used in the research, which ensured the information integrity and graphic testability when directly using the original scanning image of the engineering drawings. The achievements have been used for automatical recognition and calculation of architecture engineering drawings.
Key words　Image scanning, graph segment, engineering drawings vectorization, recognition.
1　引言
　　长期以来，人们一直在努力解决图纸自动输入的问题.随着近年来扫描仪的迅速发展和计算机性能的大幅度提高，工程图纸的矢量化已成为学术界与业界关注的一个热点，这方面的研究对多媒体技术中的各种图、表等信息的自动输入和应用是一个极大的推动.
　　计算机能否读懂一张图纸，其中有许多关键技术问题需要解决：1)图纸的矢量化，2)字符标识的识别，3)图形的理解.近年来的研究［1～3］往往是使用细化的算法抽取骨骼线，然后设法连成线.这种方法的缺点是图形失真、检出线段短和丢失线宽信息.
　　本文采用的基于行程编码的矢量化算法与识别方法较好地利用了图像信息的完整性，可以通过形态分析获取工程图纸上的字、线、符号等多种信息.

2　基于行程编码的矢量化方法
　　工程图纸扫描进入计算机后，一般量矢量化为二值化图像，与灰度相比占的存储空间较小，即使这样，一幅A0的工程图纸按400dpi扫描成二值图像其空间也要占40MB左右.从工程图纸的表现形式看，在整个幅面上由线(黑色像素)占的像素很少，空白处较多，因此使用行程编码来表示黑色像素部分的线或字是极为有效的一种方法.
　　行程编码是记录每一行上黑色连续像素的位置，称之为一个行段(Segment).如果行程终止点位置由扫描行的始点算起并由到达行程终点的像素计数确定，便称为行程终点编码.如果行程终点位置由前一终点的相对距离确定，则称为行程长度编码.
　　目前大多数矢量化方法是采用细化的算法，细化虽然一定程度上可获取骨骼线，但会导致大量信息的丢失，尤其对于图纸上各种不同对象形态的整体理解较为困难.使用行程编码能有效地表达图像形态特征及其相互关系.
　　为进行有效地对行段进行跟踪，首先建立如下定义.
　　定义1.一段直线是一组等长行段的有续排列(如图1(a)所示).


(a)行段的表示形式


(b)等长行段跟踪


(c)行段的转折点表示
图1　直线的行段定义
　　组成一段有效直线的必要条件是：(1)组成该直线的连续行段的行长相等，即l0=l1=li=…=ln-1，在有毛刺的情况下，至少应满足｜li+1-li｜<ε(这里li表示第i段行段的长度)；(2)相邻行段的中心的水平位移应小于线的最大宽度.
　　定义2.若上下两个行段的长度差超过最大线宽，则表示它们属于两个不同的直线段(如图1(b)).
　　定义3.若上下两个行段的中心位移大于最大线宽，则表示该点为直线的一个转折点(拐点)，如图1(c)所示.
　　定义4.若存在两个行段，属于连续的相邻扫描行，且黑色像素之间重迭或最多相差一个像素，则称该两行段为上下相邻行段.
　　在递归扫描相邻行段的过程中，对已遍历的行段建立一个特定的标识，以防止重复遍历.当对整个图像遍历一次后，就自动形成了行段与行段之间的链接关系.这样，当要获取这些行段链组成的直线时，只要找前趋指针为空指针的节点，并按照其后继可将连续行段全部取出(直至其后继为空)构成所需要的直线线段.一般而言，只要连接首尾行段的中心点，即可获得矢量线的两端点坐标.
　　由于组成直线的连续行段的形态不同，其直线的形状、位置也不同.为此，进一步建立以下定义.
　　定义5.水平直线是由一组连续的行长大于最大线宽的行段组成.直线的端点由中心行段的首尾坐标点表示，线宽等于行段数(如图1(a)所示).
　　定义6.垂直直线或斜直线是由一组行段数小于最大线宽的连续行段组成.直线的端点用首尾行段的中心点坐标来表示(如图1(a)).
　　对于在跟踪方向行段呈连续分布的退化情况(如图2(a))，需将连续行段再做行段形态分析，以确定它们是属于一段直线还是多段直线组成的直线.分割的方法采用了Fractal的逐次细分的思想，即首先由首尾两行段中心连线()，检测出中间行段的中心点的最大距离H1的一个行段(如5).这样，直线就被分割为两段和，再对和两条子线段中间的行段做上面同样的测试，直到中间行段到各个直线子线段的距离Hk<ε为止.对检测出的转折行段(或拐点)标以特定标识，按照标识位置即可确定每一子线段直线.


(a)行段的特征退化


(b) Fractal的逐次细分
图2　采用逐次细分的Fractal方法获取直线段
3　小弯度直线端点纠正问题
　　在基于行程编码的矢量化过程中，对于大弯度直线具有很高的识别精度，其拐点的行段变化(方向，行长)具有明显的特征.但在小弯度情况下，其拐点处的特征就较为模糊，如图3(a)所示.


(a)小弯度直线拐点的模糊性


(b)用包围矩形确定直线的端点和直线的宽度
图3　小弯度直线的行段特征与端点定位
　　在P1，P2两处拐点的行长处于一种均衡(增长或缩短)的变化过程，即

由此，可以给出以下一般直线的判别条件：
　　1)若｜li+1-li｜<ε，则在行段i处存在一拐点；
　　2)若对所有段，存在｜li-lj｜<ε，　i,j∈［0,m］，则为平稳的行段组成的直线；
　　3)若｜li+1-l1｜<ε，但lm-l0｜>δ，则为小弯度直线.
　　小弯度直线的端点位置确定可依据行长变化的方向来确定，其判别规则为
　　1)若li+1>li,i∈［0,m］，则直线长度为l0，宽度为m,如；
　　2)若li+1<li,i∈［0,m］，则直线长度为lm，宽度为m,如.
　　依据区段内的有效行段，可以确定直线的端点坐标.
　　在扫描图像质量不高、有较多毛刺的情况下，对大倾角的直线用行程编码的行段分析进行矢量化仍然具有很高的精度.对小角度、小弯度的水平直线作上述算法处理时直线方向一般较准，但端点精度会受到一定影响，因此可做以下的进一步验证.
　　在区段内中心做一动态矩形，然后采用迭代方法逐次放大矩形，直到该矩形最大限度包围区段内的所有行段(如图3(b)所示，矩形的最小高度或宽度为一个像素).
　　动态迭代矩形算法如下：
　　1)从段内的中心，依据方向(如)做一小矩形；
　　2)矩形向四边方向延伸一个Δ值(Δ=1)；
　　3)判别矩形边上的采样点是否完全落在区段内某一行段上，即若矩形k边上的采样点不在区段的某一行段上，则该边终止向外延伸；若矩形k边上的采样点仍在区段的某一行段上，则返回2).

4　矢量化线段的延伸与合并算法
　　基于细化的矢量化方法往往产生紊乱的连接关系，粗线、细线被连在一起，没有交点的地方由于图像质量等因素而产生了许多多余的交点.用行程编码分析行段的形态识别方法所产生的直线是散列的线段构成的矢量线，一般它们较好地确定了各段直线的方向、线宽，但直线的逻辑连接关系还没有确定.
4.1　散列矢量线的交点计算
　　基于行程编码的矢量化方法所得到的独立线段不会产生多余的拐点，而只是本应重合的两个点在逻辑上还没有重合，这时需要在矢量空间进行相交直线的交点归并.
　　对于多数情况的两条直线相交，如图4(a)所示，若，则直线与直线相交，并取.对于多数直线相交于同一点的情况(如图4(b)，用同样方法，取ε范围内的全部交点的平均位置0点作为各段直线相应端点的坐标值.


(a)直线段相交


(b)多段直线交于同一点


(c)两条直线的合并


(d)多条直线的合并
图4　相交直线端点的计算与同向、同属性直线的合并
4.2　同向相连直线的合并
　　按照直线矢量化的基本思想，具有同属性的一组行段组成一个矢量图元，如直线段或圆弧段.但由于实际工程图形的复杂性，有时会将同一根直线由于相交、噪声等因素分割为两段或多段，这样就要借助于模仿人的某些理解图形图像的思维方式，将某些割断的信息重新组合为一个完整的图形信息，这就好比一个人看一个污染或残缺不全的字或图形时，他会知道不清楚的地方应是什么.
　　如图4(c)所示，直线应是一条直线，但由于直线与之相交，而使直线被分割为两段，因此对相交的两条直线需判定二者是否合并为一条直线，其合并的条件为
　　1)直线l1与l2相交于一点，即存在；
　　2)直线l1与l2同方向，即l1∥l2；
　　3)直线l1与l2具有相同的线宽.
4.3　直线的探测延伸
　　在直线的矢量化过程中，由于图形要素的大小、比例差异较大，很难给出一个拒识阈值来处理所有的情况.往往对于较均匀分布的图纸，其适应性较强，而对于不均匀、具有特殊性的图纸，某些图形由于阈值的不适应性而拒识.采用自适应、学习或交互的方法都会化去大量的时间，使软件应用效率降低.
　　本文提出的思想是，在前面矢量化的基础上，对图形、图像作进一步的局部光栅矢量混合探测，自动纠正由于参数、阈值的不适应性而导致的拒识.如图5所示，一般用人眼较容易识别出图5(a)中的箭头和图5(b)中的两根钢筋，而用计算机识别时，上面所描述的特征在这里就失去了，因此还必须进一步完善行段分析的方法.


(a)箭头的特征被混淆


(b)平行相连直线的模糊性


(c)探测三角形


(d)直线的动态探头
图5　特殊组合图形特征的模糊性与推理探测
　　对箭头而言(如图5(c))，在前面矢量化的基础上，可得到行段的局部特征，这时假设在0端点处有一箭头，其比例略小于实际箭头.设箭头的长度｜L｜，直线的参数方程为

由，即｜(x0,y0), (x1,y1)｜=｜L｜，其中x1=x0+(x4-x0)t1, y1=y0+(y4-y0)t1.代入上式，可计算出t1，从而确定了点的坐标.再设箭头的宽度为2w，与相垂直的直线方向为；直线的长度为｜M｜=.所以，点的坐标为和
　　然后再判别三角形边上的点是否落在黑色像素内，若满足条件则表示存在一个三角形箭头.
　　用这种基于行段的链接变化特征直接识别图像的形状，具有准确性高、信息完整、速度快等特点.如果使用细化算法，则无法保证这种面状图形的整体信息，而且产生细化后的图形变形较大，以致无法识别.
5　实验与结论
　　工程图纸线状图形矢量化是复杂图形识别与理解的基础.整体识别可以在信息较完整的情况下获取较准确的结果，使用行程编码具有信息量小、数据搜索快等特点，它一般要求图像的连通域较完整，对于图面质量不高的图纸，扫描后可先做1～2次的膨胀收缩处理，以改进其连通性.本文针对建筑结构图的识别做了一定试验性研究，该项目由香港有利建筑集团资助，目的是实现钢筋结构图的自动识别和自动预算.图6(a)表示了一根梁的图纸扫描图像，图6(b)是相应的矢量化结果.


(a)图纸的扫描图像


(b)矢量化后的图形
图6　行段分析的图形矢量化方法用于建筑结构图的识别实例
作者简介：邹荣金　1962年出生，南京大学计算机科学系博士、副教授.研究方向为图形学、图像处理与识别.
　　　　　蔡士杰　1945年出生，南京大学计算机科学系教授、博士生导师.研究领域为图形学、CAD技术.
　　　　　张福炎　1941年出生，南京大学计算机科学系教授、博士生导师.研究领域为多媒体技术、图形学.
作者单位：南京大学软件新技术国家重点实验室　南京　210093
参考文献
1　Nagasamy V, Langrna N A. Engineering drawing processing and vectorization system.Computer Vision Graphics and Image Processing,1990，49：379～397
2　Haralick R M, Queeney D. Understanding engineering drawing drawings.Computer Vision Graphics and Image Processing,1982，20：244～258
3　Osamu Hori et al. Line drawing interpretation using probabistic relation.Machine Vision and Applications,1993，23：100～109
收稿日期　1997-09-22　收修改稿日期　1998-02-18
