劉曉平， 何士雙

（合肥工業(yè)大學(xué)計(jì)算機(jī)與信息學(xué)院VCC研究室，安徽 合肥 230009）

目前，在工程應(yīng)用領(lǐng)域設(shè)計(jì)人員已經(jīng)廣泛使用CAD軟件進(jìn)行工程圖紙輔助繪制，但由于通用CAD軟件不具有表示工程圖紙的工程和物理屬性的功能，造成了工程圖紙的設(shè)計(jì)與理解過(guò)程的脫節(jié)。因此，正確地識(shí)別和匹配工程圖紙中的符號(hào)是完成圖紙的自動(dòng)理解、用料估算、自動(dòng)生成工藝工序卡片的重要前提。

當(dāng)前國(guó)內(nèi)外對(duì)圖形的識(shí)別和匹配做了相關(guān)研究。文獻(xiàn)[1]和文獻(xiàn)[2]分別提出基于規(guī)則和特征的方法對(duì)建筑圖紙進(jìn)行識(shí)別，然而對(duì)以圖形為工程符號(hào)主要特征的工程圖紙來(lái)說(shuō)，特征與規(guī)則的提取本質(zhì)上是對(duì)多連通域圖形的表示，因此難以總結(jié)具體規(guī)則。文獻(xiàn)[3]根據(jù)圖形作業(yè)批改的特點(diǎn)提出了基于圖元特征的匹配技術(shù)，然而其依靠圖形的絕對(duì)位置關(guān)系建立的匹配規(guī)則不適用于存在旋轉(zhuǎn)和縮放的工程圖紙符號(hào)識(shí)別。文獻(xiàn)[4]提出采用區(qū)域鄰接圖表示工程圖紙的方法，通過(guò)使用子圖匹配方法實(shí)現(xiàn)符號(hào)的識(shí)別，但其僅能處理各連通域鄰接的情況，對(duì)于包含連通則無(wú)法處理。

因此，根據(jù)多連通域圖形的特點(diǎn)提出采用包圍多邊形、連通多邊形完成對(duì)其進(jìn)行表示。針對(duì)圖形中存在的包含連通情況，通過(guò)使用三角劃分解決了連通多邊形間的定位問(wèn)題。應(yīng)用此方法，解決了多連通域圖形的旋轉(zhuǎn)、縮放匹配問(wèn)題。

1 多連通域圖形的表示

1.1 多連通域圖形

定義1多連通域圖形是由多個(gè)多邊形通過(guò)鄰接、包含組合產(chǎn)生的具有多個(gè)連通域的圖形。

按照多邊形所在區(qū)域間的覆蓋范圍可以分為鄰接和包含，對(duì)于多邊形存在區(qū)域交叉的情況則可以進(jìn)一步劃分多邊形為若干個(gè)子多邊形，最終仍可用鄰接和包含關(guān)系表示；按照多邊形區(qū)域的連接方式可以分為點(diǎn)連接、邊連接和空連接。如圖1所示，對(duì)于圖1(a)中的多邊形a和b，按照上述的組合方式可以組成8種多連通域圖形，其中圖1(d)的組合方式比較特殊，在工程圖紙中被用來(lái)表示兩個(gè)工程符號(hào)，因此不屬于多連通域圖形。

圖1 多邊形組合方式

由定義可知，多連通域圖形具有以下性質(zhì)：

性質(zhì)1不存在孤立邊，即每條邊的兩端必須連接其他邊；

性質(zhì)2不存在孤立的連通域，即多連通域圖形具有唯一的外輪廓。

1.2 包圍多邊形

定義2包圍多邊形是由若干條邊組成的首尾順序連接、用于表示多連通域圖形外輪廓的封閉邊鏈表。

由多連通域圖形的定義可知，包圍多邊形中可能會(huì)包含重復(fù)邊。利用多連通域圖形的特點(diǎn)，建立了起點(diǎn)與起邊概念，方便獲取包圍多邊形。

定義3起點(diǎn)是多連通域圖形中以<最小x，最小y>且x優(yōu)先的原則獲取的點(diǎn)。

定義4起邊是與起點(diǎn)連接的邊鏈表中按逆時(shí)針排序的第一條邊。

如圖2所示，點(diǎn)p1為包圍多邊形的起點(diǎn)，邊為包圍多邊形的起邊。由于起點(diǎn)滿足最小x特性，因此起邊必定在起點(diǎn)的右側(cè)。以起點(diǎn)、起邊為初始位置，按逆時(shí)針順序逐漸遍歷多連通域圖形，即可獲取圖形的外輪廓。

圖2 起點(diǎn)、起邊示意圖

1.3 連通多邊形

定義5 任取包圍多邊形內(nèi)不在邊上的任意點(diǎn)，稱包含該點(diǎn)的最小多邊形為連通多邊形。

根據(jù)上述定義，對(duì)于圖1的7種有效組合方式，獲取多連通域圖形的連通屬性如表1所示。其中，表示多邊形a、b去除重復(fù)邊的組合，a-b表示a、b兩個(gè)區(qū)域的差。

從表1中可以看出，對(duì)于鄰接連通，除去(f)之外，原a、b多邊形均可表示自身所在的連通域，而(f)則由于原a、b多邊形在內(nèi)部邊鄰接，因此連通多邊形發(fā)生了進(jìn)一步劃分，為，連通性轉(zhuǎn)變?yōu)猷徑舆B通；對(duì)于包含連通，雖然連通多邊形未發(fā)生變化，但連通域已經(jīng)發(fā)生改變。因此，對(duì)于包含連通，如何準(zhǔn)確定位連通多邊形之間的位置關(guān)系將是匹配的關(guān)鍵。

表1 連通屬性表

利用起點(diǎn)、起邊的性質(zhì)，通過(guò)順時(shí)針逐漸遍歷多連通域圖形，實(shí)現(xiàn)尋找連通多邊形。以下是獲取一個(gè)連通多邊形的算法：

Step 1獲取起點(diǎn)、起邊，若為空則退出；

Step 2設(shè)置起邊的另一端點(diǎn)為中心點(diǎn)，按順時(shí)針順序找出與中心點(diǎn)連接且起邊夾角最小的邊；

Step 3若該邊在邊鏈表已經(jīng)存在，則刪除鏈表中該邊至末尾的所有元素，設(shè)置當(dāng)前邊為起邊，當(dāng)前邊中心點(diǎn)的另一端點(diǎn)為起點(diǎn)，跳至Step 2；

Step 4若該邊與邊鏈表中的邊存在重復(fù)交點(diǎn)，則刪除鏈表中第一重復(fù)交點(diǎn)的邊至末尾的所有元素，設(shè)置當(dāng)前邊為起邊，當(dāng)前邊中心點(diǎn)的另一端點(diǎn)為起點(diǎn)，跳至Step 2；

Step 5若該邊不是起邊，則保存當(dāng)前邊，設(shè)置當(dāng)前邊為起邊，當(dāng)前邊中心點(diǎn)的另一端點(diǎn)為起點(diǎn)，跳至Step 2；

Step 6刪除起邊，刪除孤立邊，跳至Step 1，準(zhǔn)備獲取下一個(gè)連通多邊形。

2 基于三角劃分的多連通域圖形匹配算法

2.1 三角劃分

通過(guò)采用包圍多邊形與連通多邊形基本實(shí)現(xiàn)了對(duì)多連通域圖形的表示，但是由于圖形存在包含連通情況，僅僅通過(guò)包圍多邊形和連通多邊形并不能準(zhǔn)確表示圖形內(nèi)部結(jié)構(gòu)，因此如何表示包含連通是能否匹配成功的關(guān)鍵。在圖3中，矩形可以按任意旋轉(zhuǎn)角度放置在梯形中，而連通多邊形不變，如圖3 (a)、(b)所示。針對(duì)上述問(wèn)題，通過(guò)添加輔助線實(shí)現(xiàn)對(duì)包含連通的劃分，將包含連通分解為鄰接連通，通過(guò)鄰接連通實(shí)現(xiàn)圖形的定位。

圖3 包含連通

添加輔助線的思想是當(dāng)連通多邊形存在包含連通時(shí)，根據(jù)匹配編碼找出對(duì)應(yīng)邊，以匹配邊為基礎(chǔ)添加輔助線建立三角形，從而實(shí)現(xiàn)三角區(qū)域劃分。以下是添加輔助線的規(guī)則：

規(guī)則1在外層連通多邊形包含的區(qū)域內(nèi)，找出與邊兩端點(diǎn)的距離之和最近點(diǎn)，建立端點(diǎn)與最近點(diǎn)之間的邊，即滿足包含、最近距離原則；

規(guī)則2輔助線不能與任何邊有交叉，即滿足無(wú)遮擋原則。

規(guī)則確保兩個(gè)圖形在匹配的過(guò)程中能有效地對(duì)包含連通進(jìn)行有效劃分，但是對(duì)于某些特殊情況，可能會(huì)存在若干個(gè)可選最近點(diǎn)，因此為了匹配正確性，需要遍歷所有的可選點(diǎn)，如圖2(a)所示，存在著p1、p2兩個(gè)可選點(diǎn)，分別按照p1、p2建立輔助線。

2.2 包圍多邊形匹配

國(guó)內(nèi)外學(xué)者對(duì)多邊形匹配問(wèn)題已經(jīng)進(jìn)行了大量研究[5-6]，但是由于包圍多變形存在多個(gè)重復(fù)邊的情況，并且需要通過(guò)包圍多邊形的匹配來(lái)為下一次的匹配進(jìn)行定位，因此需要進(jìn)行特殊處理。通過(guò)建立<屬性邊、夾角>結(jié)構(gòu)，實(shí)現(xiàn)對(duì)包圍多邊形的幾何與拓?fù)浔硎?，并且同時(shí)滿足了連通多邊形的匹配要求。

其中，屬性邊是由邊長(zhǎng)度、匹配編碼號(hào)、輔助線標(biāo)記組成。匹配碼是兩個(gè)包圍多邊形匹配成功后對(duì)應(yīng)邊的編號(hào)，輔助線標(biāo)記表示是否為匹配過(guò)程中添加的輔助線。由于對(duì)每次包圍多邊形匹配的結(jié)果進(jìn)行了編碼，因此為多連通域圖形的全過(guò)程匹配提供了依據(jù)。

包圍多邊形主要是對(duì)多連通域圖形的外輪廓描述，在某些情況下會(huì)存在一定的對(duì)稱特性。因此，用于描述包圍多邊形結(jié)構(gòu)的<屬性邊、夾角>鏈表結(jié)構(gòu)將會(huì)存在重復(fù)。如圖4(a)、(b)所示，由于圖形外輪廓具有兩重對(duì)稱性，因此包圍多邊形具有兩個(gè)重復(fù)模式。在進(jìn)行匹配時(shí)，不同的匹配模式將會(huì)導(dǎo)致不同的三角劃分，如圖4 (a)、(b)中輔助線所示，因此在匹配多連通域圖形時(shí)需要遍歷包圍多邊形的所有匹配模式，以確保匹配的正確性。

圖4 兩重對(duì)稱的包圍多邊形

2.3 多連通域圖形匹配算法

多連通域圖形匹配的基本思想是利用包圍多邊形實(shí)現(xiàn)圖形的外輪廓匹配定位，在此基礎(chǔ)上通過(guò)匹配編碼刪除對(duì)應(yīng)的連通多邊形實(shí)現(xiàn)多連通域圖形的收縮，最終完成匹配。匹配的本質(zhì)是從外至內(nèi)不斷刪除連通域的過(guò)程，具體實(shí)現(xiàn)算法如下：

Step 1針對(duì)待匹配件進(jìn)行預(yù)處理，包括合并重復(fù)線、直線斷點(diǎn)補(bǔ)合、刪除孤立邊等；

Step 2獲取標(biāo)準(zhǔn)件與待匹配件的包圍多邊形，進(jìn)行包圍多邊形匹配；

Step 3若成功，則對(duì)圖形進(jìn)行編碼；若失敗，則退出；

Step 4分別找出編碼最小邊，找出該邊所在的連通多邊形，判斷連通多邊形是否存在包含連通，若存在，則根據(jù)該邊進(jìn)行三角劃分；

Step 5找出該邊所在的連通多邊形，進(jìn)行多邊形匹配；

Step 6若成功，則刪除該邊，刪除孤立邊，跳至Step 2；若失敗，則退出。

3 實(shí)驗(yàn)分析

3.1 圖形匹配實(shí)例

根據(jù)上述算法，以下給出了具有一個(gè)包含連通的簡(jiǎn)單圖形的匹配全過(guò)程。從表2中可以看出，總共經(jīng)過(guò)了5次匹配，分別在第1次和第3次添加了輔助線。其中，在第1次匹配時(shí)，首先根據(jù)原圖的包圍多邊形實(shí)現(xiàn)圖形的外輪廓匹配，從而確定具體的匹配邊，然后判斷出存在包含連通，因此依據(jù)匹配編碼添加了兩條輔助線（用虛線表示），將包含連通轉(zhuǎn)化為鄰接連通，完成了第1次匹配，成功地實(shí)現(xiàn)了連通域的刪除，收縮多連通域圖形的范圍，然后再經(jīng)過(guò)4次匹配即實(shí)現(xiàn)了圖形的匹配。

3.2 線束圖紙識(shí)別實(shí)例

論文提出的方法已經(jīng)在以AutoCAD為平臺(tái)使用ObjectARX進(jìn)行二次開(kāi)發(fā)的汽車線束工藝輔助設(shè)計(jì)系統(tǒng)的中得到了驗(yàn)證。該系統(tǒng)主要是通過(guò)對(duì)表示汽車線束連接關(guān)系的圖紙進(jìn)行理解分析，生成用于指導(dǎo)實(shí)際生產(chǎn)的工藝、工序卡片和進(jìn)行物料統(tǒng)計(jì)。

表2 多連通域圖形匹配過(guò)程

線束圖紙主要包括圖框、圖紙規(guī)格說(shuō)明、接插件、線束等部件，其中接插件是表示線束連接關(guān)系和進(jìn)行圖紙布局的主要部件，具有多連通域圖形的特點(diǎn)，因此是主要的識(shí)別對(duì)象。在對(duì)圖紙進(jìn)行自動(dòng)識(shí)別的過(guò)程中，該系統(tǒng)以接插標(biāo)準(zhǔn)件庫(kù)為基礎(chǔ)[7]，首先對(duì)線束圖紙進(jìn)行預(yù)處理，去除干擾信息；然后，遍歷標(biāo)準(zhǔn)件庫(kù)，依據(jù)多連通域圖形的唯一外輪廓特性，分別將標(biāo)準(zhǔn)件與線束圖紙中的各個(gè)孤立的外輪廓區(qū)域進(jìn)行匹配，找出在圖紙中使用的庫(kù)中的接插件。

圖5所示是型號(hào)為91601-V6050的汽車左頂線束總成圖，其中包含22個(gè)接插件，在圖紙中用箭頭所指示的放大圖形為示意。通過(guò)識(shí)別和匹配，找出了圖紙中的20個(gè)接插件。對(duì)于圖紙中用實(shí)線橢圓標(biāo)志的接插件，由于在標(biāo)準(zhǔn)件庫(kù)中不存在，未被成功識(shí)別；另外，對(duì)于用虛線橢圓標(biāo)志的接插件，由于設(shè)計(jì)者在繪制時(shí)發(fā)生圖形信息遺漏，同樣也未能識(shí)別。因此，可以分別通過(guò)引入模糊匹配思想和提高標(biāo)準(zhǔn)件庫(kù)的完整性的方法提高線束圖紙的識(shí)別率。

圖5 線束圖紙識(shí)別示意圖

4 總結(jié)與展望

工程圖紙的自動(dòng)識(shí)別是進(jìn)行圖紙理解的基礎(chǔ)。論文針對(duì)工程圖紙中出現(xiàn)的多連通域圖形匹配問(wèn)題，首先，提出通過(guò)添加輔助線實(shí)現(xiàn)三角劃分，解決了包含連通的定位問(wèn)題；然后，基于包圍多邊形和連通多邊形的匹配，根據(jù)匹配編碼逐步刪除連通域，收縮多連通域圖形，最終實(shí)現(xiàn)圖形匹配。

在圖紙識(shí)別過(guò)程中存在許多不確定性因素，僅僅通過(guò)精確匹配容易出現(xiàn)漏識(shí)別的現(xiàn)象，因此若將圖形相似特性引入到匹配中來(lái)將有效地提高識(shí)別率。文獻(xiàn)[6]已經(jīng)對(duì)多邊形的相似匹配做了研究，然而尚不能有效解決多連通域圖形的相似匹配問(wèn)題，因此找出一種可行、高效的方法是未來(lái)研究的重點(diǎn)。

[1]王蛛華, 曹 陽(yáng), 楊若瑜, 等. 基于規(guī)則的建筑結(jié)構(gòu)圖鋼筋用量自動(dòng)識(shí)別系統(tǒng)[J]. 軟件學(xué)報(bào), 2002, 3(4):574-579.

[2]沈 怡, 蔡士杰, 高 曉. 建筑工程圖符號(hào)的特征匹配識(shí)別方法[J]. 計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào),2003, 15(9): 1065-1069.

[3]劉就女, 吳東慶, 彭小敏, 等. 智能圖元特征提取與圖形匹配技術(shù)[J]. 工程圖學(xué)學(xué)報(bào), 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]王雪飛, 胡青泥. 基于分層加權(quán)的多邊形圖形匹配[J].工程圖學(xué)學(xué)報(bào), 2002, 23(2): 89-96.

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

[7]何士雙, 徐本柱, 吳 黃, 等. 基于AutoCAD的線束電器件庫(kù)的建立[C]//全國(guó)第18屆計(jì)算機(jī)科學(xué)與技術(shù)應(yīng)用(CACIS)學(xué)術(shù)會(huì)議, 2007: 937-940.