基于特征的矢量圖形符號(hào)漸進(jìn)識(shí)別方法

王新新

摘 要：矢量圖形符號(hào)識(shí)別是工程圖紙自動(dòng)化處理技術(shù)的基礎(chǔ)之一，但現(xiàn)有識(shí)別方法普遍效率較低，無(wú)法滿足大批量圖紙?zhí)幚砣蝿?wù)的需求。為提高矢量圖形識(shí)別效率，提出一種將符號(hào)拆解為特征序列的漸進(jìn)識(shí)別方法。以鐵路車站施工圖為例闡述核心思想，然后基于該思想設(shè)計(jì)一種基于特征序列的符號(hào)描述模型，并實(shí)現(xiàn)相關(guān)符號(hào)識(shí)別算法，最后分析算法時(shí)間復(fù)雜度與實(shí)驗(yàn)結(jié)果的關(guān)系。在一般情況下，搜索耗時(shí)與圖檔圖元數(shù)目呈nlog（n）關(guān)系，從而證實(shí)了該方法的高效性。

關(guān)鍵詞：矢量圖形;符號(hào)識(shí)別;特征;工程圖紙

DOI：10. 11907/rjdk. 201008 開(kāi)放科學(xué)（資源服務(wù)）標(biāo)識(shí)碼（OSID）：

中圖分類號(hào)：TP301文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1672-7800（2020）005-0098-04

0 引言

計(jì)算機(jī)輔助設(shè)計(jì)（Computer Aided Design，CAD）源于美國(guó)麻省理工學(xué)院20世紀(jì)60年代提出的交互式圖形學(xué)研究計(jì)劃。時(shí)至今日，各種成熟的商用CAD軟件已廣泛應(yīng)用于工程界，CAD制圖軟件逐漸代替手工制圖畫筆成為設(shè)計(jì)工作中不可或缺的工具，許多在手工制圖年代需要人工完成的工作如材料價(jià)格預(yù)算[1]、圖紙糾錯(cuò)[2]和圖紙檢索[3]等已可交由計(jì)算機(jī)完成。

符號(hào)識(shí)別是計(jì)算機(jī)自動(dòng)化處理工程圖紙的基礎(chǔ)之一[4]，現(xiàn)已提出許多識(shí)別方法。這些方法可大致分為3類：基于統(tǒng)計(jì)的識(shí)別方法、基于結(jié)構(gòu)的識(shí)別方法和基于統(tǒng)計(jì)與結(jié)構(gòu)混合的識(shí)別方法[5]?；诮y(tǒng)計(jì)的識(shí)別方法是指通過(guò)統(tǒng)計(jì)手段抽取符號(hào)特征向量，然后在待識(shí)別圖檔中匹配與模板符號(hào)特征向量相似的圖形。其準(zhǔn)確性和魯棒性很大程度取決于特征選擇[5]，該類方法主要應(yīng)用于像素圖像上的符號(hào)識(shí)別[7-8]。部分基于統(tǒng)計(jì)的識(shí)別方法[9-10]可直接應(yīng)用于矢量圖檔，但待識(shí)別圖檔中只能有一個(gè)符號(hào)，識(shí)別算法通過(guò)計(jì)算其與模板符號(hào)特征向量的相似度判定兩者是否相同;基于結(jié)構(gòu)的識(shí)別方法則專用于矢量圖檔，其預(yù)先定義好模板符號(hào)組成結(jié)構(gòu)，主要包括符號(hào)組成圖元（簡(jiǎn)稱組元）和組元間關(guān)系，再?gòu)拇R(shí)別圖檔中尋找滿足模板結(jié)構(gòu)描述的圖元組合，該類方法能有效表達(dá)出符號(hào)特征，識(shí)別準(zhǔn)確度高，但通常計(jì)算量較大[5]。因此，便出現(xiàn)了融合統(tǒng)計(jì)與結(jié)構(gòu)的基于矢量簽名[11]的識(shí)別方法，其思想是利用矢量簽名快速過(guò)濾待識(shí)別符號(hào)，再通過(guò)結(jié)構(gòu)匹配進(jìn)行精確查找。矢量簽名一般通過(guò)統(tǒng)計(jì)手段從符號(hào)的結(jié)構(gòu)化描述中進(jìn)行提取[12]，文獻(xiàn)[13]將其稱作特征向量。這類混合方法繼承了基于統(tǒng)計(jì)與結(jié)構(gòu)兩類方法的優(yōu)點(diǎn)，主要解決了基于結(jié)構(gòu)方法的效率問(wèn)題，但用于快速篩選的矢量簽名依然容易受到噪聲及變形等影響，導(dǎo)致可能漏掉一些目標(biāo)符號(hào)。

基于結(jié)構(gòu)的識(shí)別方法由于在應(yīng)對(duì)符號(hào)縮放、旋轉(zhuǎn)、噪聲、變形等方面具有優(yōu)良的魯棒性而受到大量關(guān)注，其核心問(wèn)題是如何定義基本圖元與圖元間關(guān)系[2]。劉東明等[14]將基本圖元分為4種：直線、折線、橢圓、圓弧，通過(guò)約束點(diǎn)表達(dá)圖元間關(guān)系;WANG等[15]面向線、圓弧兩種基本圖元提出一種基于二元約束的符號(hào)結(jié)構(gòu)化表示形式，該形式能描述線、圓弧和橢圓組成的符號(hào);文獻(xiàn)[16]則將基本圖元?dú)w納為5種：線段、圓弧、圓、箭頭、信息點(diǎn)和特征點(diǎn)，采用二元幾何關(guān)系和拓?fù)潢P(guān)系描述圖元間約束;Ah-Soon等[17]定義一種描述符號(hào)的約束網(wǎng)絡(luò)，其可以很容易擴(kuò)展到任意類型圖元上，不限于線段或圓弧等;孫聰?shù)萚18]將圖元抽象為具有位置、尺寸和朝向?qū)傩缘膶?shí)體，以實(shí)體為節(jié)點(diǎn)、關(guān)系描述子為邊構(gòu)造雙層樹(shù)以描述符號(hào);陸國(guó)棟等[19]以尺寸約束定義圖元，以鄰接組元連接方式描述組元間關(guān)系，此外還在符號(hào)層面定義了視圖碼、分類碼和輔助碼用于增強(qiáng)描述的區(qū)分度。本文采用類似于約束樹(shù)的描述方式，相較于以往文獻(xiàn)不同的是，本文引入圖元間的多元關(guān)系。

搜索策略是設(shè)計(jì)基于結(jié)構(gòu)的識(shí)別方法時(shí)需要考慮的重要部分，其能顯著影響搜索效率?，F(xiàn)有許多方法都是通過(guò)反復(fù)遍歷圖檔查找符號(hào)組元，搜索時(shí)間復(fù)雜度極高。Guo等[2]、孫聰?shù)萚18]、楊若瑜等[20]和劉文印等[21]都提到了關(guān)鍵圖元概念，其基本思想是：將符號(hào)某個(gè)組元作為關(guān)鍵圖元，識(shí)別時(shí)首先在目標(biāo)圖檔中快速定位到關(guān)鍵圖元處，再?gòu)年P(guān)鍵圖元周圍區(qū)域逐個(gè)尋找符號(hào)其它組元。從實(shí)驗(yàn)結(jié)果來(lái)看，該方法確實(shí)提高了搜索效率。但其存在兩個(gè)不足：①單純?cè)陉P(guān)鍵圖元周圍搜索，沒(méi)有有效利用關(guān)鍵圖元信息;②在面對(duì)符號(hào)組元分散的情況時(shí)搜索范圍明顯擴(kuò)大，導(dǎo)致效率下降。

為此，本文提出一種基于符號(hào)特征進(jìn)行漸進(jìn)搜索的方法。與常規(guī)約束樹(shù)或約束網(wǎng)絡(luò)不同，本文將符號(hào)分解為由若干特征組成的序列，在特征之間的圖元上建立約束關(guān)系，識(shí)別時(shí)逐特征求解，當(dāng)前求解特征的搜索范圍由前序特征進(jìn)行限制，從而能有效縮小搜索空間范圍，進(jìn)而提高搜索效率。

1 矢量圖形符號(hào)構(gòu)成分析

矢量圖形符號(hào)（簡(jiǎn)稱符號(hào)）是由若干基本矢量圖元按照一定關(guān)系組成的具有代表意義的標(biāo)識(shí)。一般而言，如果兩個(gè)符號(hào)組元不同，或任意圖元間關(guān)系不同，則認(rèn)為兩個(gè)符號(hào)不同?；诮Y(jié)構(gòu)的符號(hào)識(shí)別方法就是利用該特性區(qū)分符號(hào)，接下來(lái)以鐵路車站施工圖中的信號(hào)機(jī)符號(hào)為例分析符號(hào)構(gòu)成。

3 符號(hào)識(shí)別

3.1 空間四叉樹(shù)

二叉樹(shù)是一種常見(jiàn)數(shù)據(jù)結(jié)構(gòu)，其變體二叉查找樹(shù)常用于一維數(shù)據(jù)存儲(chǔ)與查找，一般具有[O（log2n）]的搜索時(shí)間復(fù)雜度，相應(yīng)地對(duì)于二維數(shù)據(jù)，采用四叉樹(shù)進(jìn)行存儲(chǔ)以提高搜索效率。四叉樹(shù)是一種每個(gè)節(jié)點(diǎn)包含4個(gè)子節(jié)點(diǎn)的樹(shù)形數(shù)據(jù)結(jié)構(gòu)，其用于存儲(chǔ)二維圖元（簡(jiǎn)稱圖元）時(shí)，通常采取四等分矩形區(qū)域的方式生成樹(shù)。假設(shè)初始矩形區(qū)域內(nèi)包含所有要存儲(chǔ)的圖元，將該矩形分割成4個(gè)等面積矩形作為子節(jié)點(diǎn)，再對(duì)子節(jié)點(diǎn)進(jìn)行相同的四等分操作，如此遞歸便可將初始矩形分割成若干有層次關(guān)系的矩形區(qū)域，每個(gè)區(qū)域內(nèi)存在若干圖元。分割停止條件視圖元存儲(chǔ)方式而定，通常有兩種存儲(chǔ)方式：

（1）圖元僅存儲(chǔ)于葉節(jié)點(diǎn)內(nèi)。如果四叉樹(shù)某葉節(jié)點(diǎn)矩形區(qū)域與圖元最小外包矩形（Minimum Bounding Rectangle， MBR）有交集，則將圖元存儲(chǔ)在該葉節(jié)點(diǎn)內(nèi)，常以樹(shù)最大深度或葉節(jié)點(diǎn)最大對(duì)象數(shù)量作為遞歸停止條件。該存儲(chǔ)方式的優(yōu)點(diǎn)在于查找準(zhǔn)確，葉節(jié)點(diǎn)內(nèi)元素都與葉節(jié)點(diǎn)相關(guān)，缺點(diǎn)在于存儲(chǔ)數(shù)據(jù)有較大冗余。

（2）圖元可存儲(chǔ)于任意節(jié)點(diǎn)內(nèi)。將圖元存儲(chǔ)在完全包含它的最小矩形節(jié)點(diǎn)中，在所有對(duì)象存儲(chǔ)完成時(shí)停止遞歸。每個(gè)對(duì)象僅采用該方式存儲(chǔ)一次，以避免存儲(chǔ)空間浪費(fèi)，但相比方式（1）查找準(zhǔn)確率較低。查找某節(jié)點(diǎn)內(nèi)存儲(chǔ)對(duì)象時(shí)必須搜索祖先節(jié)點(diǎn)存儲(chǔ)的對(duì)象，而祖先節(jié)點(diǎn)中對(duì)象可能與該節(jié)點(diǎn)無(wú)關(guān)。

根據(jù)本文搜索算法的特性，選擇第一種存儲(chǔ)方式，即僅存儲(chǔ)圖元于葉節(jié)點(diǎn)，最佳遞歸停止條件要視搜索需求而定。由于本文搜索的是符號(hào)組元，多數(shù)情況下這些圖元相隔較近且聚集在符號(hào)中心周圍，較好的停止條件是盡量將同一符號(hào)的組元?jiǎng)澐值酵蝗~節(jié)點(diǎn)內(nèi)。適當(dāng)?shù)淖畲笊疃群腿~節(jié)點(diǎn)最大對(duì)象數(shù)量都可滿足需求，本文以葉節(jié)點(diǎn)最大對(duì)象數(shù)量作為停止條件。

3.2 符號(hào)識(shí)別

為加快查找指定區(qū)域圖元的速度，使用2.2章介紹的空間四叉樹(shù)作為圖元索引。查找某個(gè)區(qū)域[Dfk]內(nèi)的圖元時(shí)，首先在空間四叉樹(shù)中找到與[Dfk]有交集區(qū)域的葉節(jié)點(diǎn)，再?gòu)娜~節(jié)點(diǎn)中查找屬于[Dfk]的圖元。

4 實(shí)驗(yàn)結(jié)果分析

根據(jù)算法1編寫符號(hào)識(shí)別程序，以信號(hào)機(jī)符號(hào)描述與鐵路車站施工圖為輸入，以圖檔圖元數(shù)量為變量進(jìn)行識(shí)別實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果如圖6所示。對(duì)于某個(gè)指定符號(hào)[S]，記圖檔中圖元個(gè)數(shù)為[n]，當(dāng)[k>1]時(shí)，[Dfk]中圖元數(shù)目最多為[a]，每個(gè)搜索節(jié)點(diǎn)[fk]最多有[d]個(gè)滿足約束關(guān)系的候選組合，[fk]組元數(shù)目為[c]，四叉樹(shù)葉節(jié)點(diǎn)最大圖元數(shù)目為[M]，區(qū)域[Dfk]最多與[b]個(gè)四叉樹(shù)葉節(jié)點(diǎn)區(qū)域有交集，則搜索樹(shù)最多有[ndS-1]個(gè)葉節(jié)點(diǎn)。針對(duì)[S]的某個(gè)特征[fk]，在四叉樹(shù)中查找[Dfk]范圍內(nèi)圖元的時(shí)間復(fù)雜度為[O（bM+log4n）]，搜索特征[fk]的時(shí)間復(fù)雜度為[O（ac）]。因此，識(shí)別整個(gè)符號(hào)的時(shí)間復(fù)雜度為[O（ndS-1（S-1）（ac+bM+log4n））]。由于[c]、[S]和[M]在搜索前已經(jīng)確定，化簡(jiǎn)為[O（ndS（a+b+log4n））]。

對(duì)于特定符號(hào)，[a]、[ b]通常只與圖檔圖元密集程度相關(guān)，且[a+b？n]，[d]僅與圖形結(jié)構(gòu)有關(guān)。對(duì)于本文的實(shí)驗(yàn)圖檔[d=1]，由于[Dfk]限制了[fk]候選解集大小，又因?yàn)樘卣鞅旧砭哂袇^(qū)分度，所以[ fk]候選組合數(shù)目一般很少。因此，實(shí)際搜索耗時(shí)一般與圖檔圖元數(shù)目呈[nlog4n]關(guān)系。

5 結(jié)語(yǔ)

本文以鐵路車站站場(chǎng)施工圖中的信號(hào)機(jī)符號(hào)為例，闡述基于特征的矢量符號(hào)漸進(jìn)識(shí)別思想，然后設(shè)計(jì)基于特征的符號(hào)描述模型及相應(yīng)符號(hào)識(shí)別算法，最后使用設(shè)計(jì)的算法進(jìn)行實(shí)驗(yàn)，驗(yàn)證了該方法的有效性，印證了縮小搜索空間是提升組合搜索效率的有效途徑。因此，縮小搜索空間可作為提高各類基于結(jié)構(gòu)識(shí)別方法搜索效率的重要手段。另外，由于該方法的高效性，可被應(yīng)用于圖檔內(nèi)容檢索、材料預(yù)算及圖紙查錯(cuò)等大批量圖檔處理中。其不足之處在于符號(hào)定義較為復(fù)雜，使用難度大，所以需要一種自動(dòng)生成符號(hào)描述的方法[20， 22]：用戶輸入易于人類編寫與理解的信息，如手繪草圖等，再通過(guò)計(jì)算機(jī)翻譯成基于特征的符號(hào)描述，最后使用本文方法進(jìn)行搜索。該方法既能保證用戶使用的便利性，而且效率較高。

參考文獻(xiàn)：

[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] 周良. 基于內(nèi)容的工程圖檔檢索及其關(guān)鍵技術(shù)研究[D]. 南京：南京航空航天大學(xué)，2008.

[4] 路通，蔡士杰. 面向內(nèi)容的工程圖識(shí)別與理解綜述[J]. 圖學(xué)學(xué)報(bào)， 2012，33（5）：1-12.

[5] 謝艷文，張慧. 基于2-鄰域局部結(jié)構(gòu)的矢量圖符號(hào)模糊識(shí)別方法[J]. 計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)， 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] 儲(chǔ)節(jié)磊，龔暉. 矢量圖形的比較識(shí)別研究[J]. 計(jì)算機(jī)應(yīng)用與軟件，2010，27（12）：250-252.

[10] 曹明. 不變矩在矢量圖形識(shí)別中的應(yīng)用[D]. 大連：大連理工大學(xué)，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] 劉東明，陳聯(lián)，李昕巖. 基于可伸縮矢量圖形的手繪幾何圖形結(jié)構(gòu)分析方法[J]. 計(jì)算機(jī)應(yīng)用， 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]. ?中國(guó)科學(xué)：信息科學(xué)（英文版），2012，55（5）：1032-1041.

[16] 劉國(guó)華. 基于工程語(yǔ)義的二維工程圖的特征識(shí)別及三維重構(gòu)[D]. 濟(jì)南：山東大學(xué)， 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] 孫聰，施侃樂(lè)，雍俊海. 基于雙層結(jié)構(gòu)的矢量工程圖符號(hào)識(shí)別算法[J]. 計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2017，29（12）：2171-2179.

[19] 陸國(guó)棟，岳小莉，譚建榮. 圖形相似的基本原理、方法及其在結(jié)構(gòu)模式識(shí)別中的應(yīng)用[J]. 計(jì)算機(jī)學(xué)報(bào)，2002，25（9）：959-967.

[20] 楊若瑜，胡笳，蔡士杰. 工程圖對(duì)象識(shí)別規(guī)則自動(dòng)獲取方法的研究[J]. 計(jì)算機(jī)學(xué)報(bào)，2003（10）：1234-1240.

[21] 劉文印，唐龍，唐澤圣. 一種在矢量基礎(chǔ)上進(jìn)行圖形識(shí)別的通用方法[J]. 軟件學(xué)報(bào)，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.

（責(zé)任編輯：黃 ?。?/p>