基于特征的矢量图形符号渐进识别方法

王新新

摘 要：矢量图形符号识别是工程图纸自动化处理技术的基础之一，但现有识别方法普遍效率较低，无法满足大批量图纸处理任务的需求。为提高矢量图形识别效率，提出一种将符号拆解为特征序列的渐进识别方法。以铁路车站施工图为例阐述核心思想，然后基于该思想设计一种基于特征序列的符号描述模型，并实现相关符號识别算法，最后分析算法时间复杂度与实验结果的关系。在一般情况下，搜索耗时与图档图元数目呈nlog（n）关系，从而证实了该方法的高效性。

关键词：矢量图形;符号识别;特征;工程图纸

DOI：10. 11907/rjdk. 201008 开放科学（资源服务）标识码（OSID）：

中图分类号：TP301文献标识码：A 文章编号：1672-7800（2020）005-0098-04

0 引言

计算机辅助设计（Computer Aided Design，CAD）源于美国麻省理工学院20世纪60年代提出的交互式图形学研究计划。时至今日，各种成熟的商用CAD软件已广泛应用于工程界，CAD制图软件逐渐代替手工制图画笔成为设计工作中不可或缺的工具，许多在手工制图年代需要人工完成的工作如材料价格预算[1]、图纸纠错[2]和图纸检索[3]等已可交由计算机完成。

符号识别是计算机自动化处理工程图纸的基础之一[4]，现已提出许多识别方法。这些方法可大致分为3类：基于统计的识别方法、基于结构的识别方法和基于统计与结构混合的识别方法[5]。基于统计的识别方法是指通过统计手段抽取符号特征向量，然后在待识别图档中匹配与模板符号特征向量相似的图形。其准确性和鲁棒性很大程度取决于特征选择[5]，该类方法主要应用于像素图像上的符号识别[7-8]。部分基于统计的识别方法[9-10]可直接应用于矢量图档，但待识别图档中只能有一个符号，识别算法通过计算其与模板符号特征向量的相似度判定两者是否相同;基于结构的识别方法则专用于矢量图档，其预先定义好模板符号组成结构，主要包括符号组成图元（简称组元）和组元间关系，再从待识别图档中寻找满足模板结构描述的图元组合，该类方法能有效表达出符号特征，识别准确度高，但通常计算量较大[5]。因此，便出现了融合统计与结构的基于矢量签名[11]的识别方法，其思想是利用矢量签名快速过滤待识别符号，再通过结构匹配进行精确查找。矢量签名一般通过统计手段从符号的结构化描述中进行提取[12]，文献[13]将其称作特征向量。这类混合方法继承了基于统计与结构两类方法的优点，主要解决了基于结构方法的效率问题，但用于快速筛选的矢量签名依然容易受到噪声及变形等影响，导致可能漏掉一些目标符号。

基于结构的识别方法由于在应对符号缩放、旋转、噪声、变形等方面具有优良的鲁棒性而受到大量关注，其核心问题是如何定义基本图元与图元间关系[2]。刘东明等[14]将基本图元分为4种：直线、折线、椭圆、圆弧，通过约束点表达图元间关系;WANG等[15]面向线、圆弧两种基本图元提出一种基于二元约束的符号结构化表示形式，该形式能描述线、圆弧和椭圆组成的符号;文献[16]则将基本图元归纳为5种：线段、圆弧、圆、箭头、信息点和特征点，采用二元几何关系和拓扑关系描述图元间约束;Ah-Soon等[17]定义一种描述符号的约束网络，其可以很容易扩展到任意类型图元上，不限于线段或圆弧等;孙聪等[18]将图元抽象为具有位置、尺寸和朝向属性的实体，以实体为节点、关系描述子为边构造双层树以描述符号;陆国栋等[19]以尺寸约束定义图元，以邻接组元连接方式描述组元间关系，此外还在符号层面定义了视图码、分类码和辅助码用于增强描述的区分度。本文采用类似于约束树的描述方式，相较于以往文献不同的是，本文引入图元间的多元关系。

搜索策略是设计基于结构的识别方法时需要考虑的重要部分，其能显著影响搜索效率。现有许多方法都是通过反复遍历图档查找符号组元，搜索时间复杂度极高。Guo等[2]、孙聪等[18]、杨若瑜等[20]和刘文印等[21]都提到了关键图元概念，其基本思想是：将符号某个组元作为关键图元，识别时首先在目标图档中快速定位到关键图元处，再从关键图元周围区域逐个寻找符号其它组元。从实验结果来看，该方法确实提高了搜索效率。但其存在两个不足：①单纯在关键图元周围搜索，没有有效利用关键图元信息;②在面对符号组元分散的情况时搜索范围明显扩大，导致效率下降。

为此，本文提出一种基于符号特征进行渐进搜索的方法。与常规约束树或约束网络不同，本文将符号分解为由若干特征组成的序列，在特征之间的图元上建立约束关系，识别时逐特征求解，当前求解特征的搜索范围由前序特征进行限制，从而能有效缩小搜索空间范围，进而提高搜索效率。

1 矢量图形符号构成分析

矢量图形符号（简称符号）是由若干基本矢量图元按照一定关系组成的具有代表意义的标识。一般而言，如果两个符号组元不同，或任意图元间关系不同，则认为两个符号不同。基于结构的符号识别方法就是利用该特性区分符号，接下来以铁路车站施工图中的信号机符号为例分析符号构成。

3 符号识别

3.1 空间四叉树

二叉树是一种常见数据结构，其变体二叉查找树常用于一维数据存储与查找，一般具有[O（log2n）]的搜索时间复杂度，相应地对于二维数据，采用四叉树进行存储以提高搜索效率。四叉树是一种每个节点包含4个子节点的树形数据结构，其用于存储二维图元（简称图元）时，通常采取四等分矩形区域的方式生成树。假设初始矩形区域内包含所有要存储的图元，将该矩形分割成4个等面积矩形作为子节点，再对子节点进行相同的四等分操作，如此递归便可将初始矩形分割成若干有层次关系的矩形区域，每个区域内存在若干图元。分割停止条件视图元存储方式而定，通常有两种存储方式：

（1）图元仅存储于叶节点内。如果四叉树某叶节点矩形区域与图元最小外包矩形（Minimum Bounding Rectangle， MBR）有交集，则将图元存储在该叶节点内，常以树最大深度或叶节点最大对象数量作为递归停止条件。该存储方式的优点在于查找准确，叶节点内元素都与叶节点相关，缺点在于存储数据有较大冗余。

（2）图元可存储于任意节点内。将图元存储在完全包含它的最小矩形节点中，在所有对象存储完成时停止递归。每个对象仅采用该方式存储一次，以避免存储空间浪费，但相比方式（1）查找准确率较低。查找某节点内存储对象时必须搜索祖先节点存储的对象，而祖先节点中对象可能与该节点无关。

根据本文搜索算法的特性，选择第一种存储方式，即仅存储图元于叶节点，最佳递归停止条件要视搜索需求而定。由于本文搜索的是符号组元，多数情况下这些图元相隔较近且聚集在符号中心周围，较好的停止条件是尽量将同一符号的组元划分到同一叶节点内。适当的最大深度和叶节点最大对象数量都可满足需求，本文以叶节点最大对象数量作为停止条件。

3.2 符号识别

为加快查找指定区域图元的速度，使用2.2章介绍的空间四叉树作为图元索引。查找某个区域[Dfk]内的图元时，首先在空间四叉树中找到与[Dfk]有交集区域的叶节点，再从叶节点中查找属于[Dfk]的图元。

4 实验结果分析

根据算法1编写符号识别程序，以信号机符号描述与铁路车站施工图为输入，以图档图元数量为变量进行识别实验，实验结果如图6所示。对于某个指定符号[S]，记图档中图元个数为[n]，当[k>1]时，[Dfk]中图元数目最多为[a]，每个搜索节点[fk]最多有[d]个满足约束关系的候选组合，[fk]组元数目为[c]，四叉树叶节点最大图元数目为[M]，区域[Dfk]最多与[b]个四叉树叶节点区域有交集，则搜索树最多有[ndS-1]个叶节点。针对[S]的某个特征[fk]，在四叉树中查找[Dfk]范围内图元的时间复杂度为[O（bM+log4n）]，搜索特征[fk]的时间复杂度为[O（ac）]。因此，识别整个符号的时间复杂度为[O（ndS-1（S-1）（ac+bM+log4n））]。由于[c]、[S]和[M]在搜索前已经确定，化简为[O（ndS（a+b+log4n））]。

对于特定符号，[a]、[ b]通常只与图档图元密集程度相关，且[a+b？n]，[d]仅与图形结构有关。对于本文的实验图档[d=1]，由于[Dfk]限制了[fk]候选解集大小，又因为特征本身具有区分度，所以[ fk]候选组合数目一般很少。因此，实际搜索耗时一般与图档图元数目呈[nlog4n]关系。

5 结语

本文以铁路车站站场施工图中的信号机符号为例，闡述基于特征的矢量符号渐进识别思想，然后设计基于特征的符号描述模型及相应符号识别算法，最后使用设计的算法进行实验，验证了该方法的有效性，印证了缩小搜索空间是提升组合搜索效率的有效途径。因此，缩小搜索空间可作为提高各类基于结构识别方法搜索效率的重要手段。另外，由于该方法的高效性，可被应用于图档内容检索、材料预算及图纸查错等大批量图档处理中。其不足之处在于符号定义较为复杂，使用难度大，所以需要一种自动生成符号描述的方法[20， 22]：用户输入易于人类编写与理解的信息，如手绘草图等，再通过计算机翻译成基于特征的符号描述，最后使用本文方法进行搜索。该方法既能保证用户使用的便利性，而且效率较高。

参考文献：

[1] HU Z， TANG J. The design of electronic engineering budget software based on construction drawing recognition technology[J]. Mechanical Engineering and Green Manufacturing，2010（34-35）：1258-1260.

[2] GUO T，ZHANG H，WEN Y. An improved example-driven symbol recognition approach in engineering drawings[J]. Computers & Graphics， 2012，36（7）：835-845.

[3] 周良. 基于内容的工程图档检索及其关键技术研究[D]. 南京：南京航空航天大学，2008.

[4] 路通，蔡士杰. 面向内容的工程图识别与理解综述[J]. 图学学报， 2012，33（5）：1-12.

[5] 谢艳文，张慧. 基于2-邻域局部结构的矢量图符号模糊识别方法[J]. 计算机辅助设计与图形学学报， 2014，26（10）：1613-1623.

[6] SANTOSH K C，LAMIROY B，WENDLING L. Symbol recognition using spatial relations[J]. Pattern Recognition Letters，2012，33（3）：331-341.

[7] ELYAN E，GARCIA C M，JAYNE C. Symbols classification in engineering drawings[C]. Rio de Janeiro：？International joint conference on neural networks，2018.

[8] YANG S. Symbol recognition via statistical integration of pixel-level constraint histograms： a new descriptor[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence，2005，27（2）：278-281.

[9] 储节磊，龚晖. 矢量图形的比较识别研究[J]. 计算机应用与软件，2010，27（12）：250-252.

[10] 曹明. 不变矩在矢量图形识别中的应用[D]. 大连：大连理工大学，2008.

[11] ZHANG W，WENYIN L. A new vectorial signature for quick symbol indexing， filtering and recognition [C].  Proceedings of the Ninth International Conference on Document Analysis and Recognition，2007：536-540.

[12] ZHANG W，WENYIN L，ZHANG K. Symbol recognition with kernel density matching[J].  IEEE Transactions on Pattern Analysis and Machine Intelligence， 2006，28（12）：2020-2024.

[13] QURESHI R J， RAMEL J， CARDOT H， et al. Combination of symbolic and statistical features for symbols recognition[C].  International Conference on Signal Processing， 2007：477-482.

[14] 刘东明，陈联，李昕岩. 基于可伸缩矢量圖形的手绘几何图形结构分析方法[J]. 计算机应用， 2016，36（4）：1163-1166.

[15] ZHAOQI W，HE H，XIANJIE Q， et al. Strict constraints on 2D primitive pairs for engineering symbol recognition：theory and application[J].  中国科学：信息科学（英文版），2012，55（5）：1032-1041.

[16] 刘国华. 基于工程语义的二维工程图的特征识别及三维重构[D]. 济南：山东大学， 2007.

[17] AH-SOON C，TOMBRE K. Architectural symbol recognition using a network of constraints[J]. Pattern Recognition Letters，2001，22（2）：231-248.

[18] 孙聪，施侃乐，雍俊海. 基于双层结构的矢量工程图符号识别算法[J]. 计算机辅助设计与图形学学报，2017，29（12）：2171-2179.

[19] 陆国栋，岳小莉，谭建荣. 图形相似的基本原理、方法及其在结构模式识别中的应用[J]. 计算机学报，2002，25（9）：959-967.

[20] 杨若瑜，胡笳，蔡士杰. 工程图对象识别规则自动获取方法的研究[J]. 计算机学报，2003（10）：1234-1240.

[21] 刘文印，唐龙，唐泽圣. 一种在矢量基础上进行图形识别的通用方法[J]. 软件学报，1997（5）：57-64.

[22] LU W，WU W，SAKAUCHI M. A drawing recognition system with rule acquisition ability [C]. International Conference on Document Analysis & Recognition. IEEE， 1995：512-515.

（责任编辑：黄 健）