基于特征的矢量圖形符號漸進識別方法

王新新

摘 要：矢量圖形符號識別是工程圖紙自動化處理技術的基礎之一，但現有識別方法普遍效率較低，無法滿足大批量圖紙處理任務的需求。為提高矢量圖形識別效率，提出一種將符號拆解為特征序列的漸進識別方法。以鐵路車站施工圖為例闡述核心思想，然后基于該思想設計一種基于特征序列的符號描述模型，并實現相關符號識別算法，最后分析算法時間復雜度與實驗結果的關系。在一般情況下，搜索耗時與圖檔圖元數目呈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.

（責任編輯：黃 健）