基于三角劃分的多連通域圖形匹配研究

劉曉平， 何士雙

（合肥工業大學計算機與信息學院VCC研究室，安徽 合肥 230009）

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

當前國內外對圖形的識別和匹配做了相關研究。文獻[1]和文獻[2]分別提出基于規則和特征的方法對建筑圖紙進行識別，然而對以圖形為工程符號主要特征的工程圖紙來說，特征與規則的提取本質上是對多連通域圖形的表示，因此難以總結具體規則。文獻[3]根據圖形作業批改的特點提出了基于圖元特征的匹配技術，然而其依靠圖形的絕對位置關系建立的匹配規則不適用于存在旋轉和縮放的工程圖紙符號識別。文獻[4]提出采用區域鄰接圖表示工程圖紙的方法，通過使用子圖匹配方法實現符號的識別，但其僅能處理各連通域鄰接的情況，對于包含連通則無法處理。

因此，根據多連通域圖形的特點提出采用包圍多邊形、連通多邊形完成對其進行表示。針對圖形中存在的包含連通情況，通過使用三角劃分解決了連通多邊形間的定位問題。應用此方法，解決了多連通域圖形的旋轉、縮放匹配問題。

1 多連通域圖形的表示

1.1 多連通域圖形

定義1多連通域圖形是由多個多邊形通過鄰接、包含組合產生的具有多個連通域的圖形。

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

圖1 多邊形組合方式

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

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

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

1.2 包圍多邊形

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

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

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

定義4起邊是與起點連接的邊鏈表中按逆時針排序的第一條邊。

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

圖2 起點、起邊示意圖

1.3 連通多邊形

定義5 任取包圍多邊形內不在邊上的任意點，稱包含該點的最小多邊形為連通多邊形。

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

從表1中可以看出，對于鄰接連通，除去(f)之外，原a、b多邊形均可表示自身所在的連通域，而(f)則由于原a、b多邊形在內部邊鄰接，因此連通多邊形發生了進一步劃分，為，連通性轉變為鄰接連通；對于包含連通，雖然連通多邊形未發生變化，但連通域已經發生改變。因此，對于包含連通，如何準確定位連通多邊形之間的位置關系將是匹配的關鍵。

表1 連通屬性表

利用起點、起邊的性質，通過順時針逐漸遍歷多連通域圖形，實現尋找連通多邊形。以下是獲取一個連通多邊形的算法：

Step 1獲取起點、起邊，若為空則退出；

Step 2設置起邊的另一端點為中心點，按順時針順序找出與中心點連接且起邊夾角最小的邊；

Step 3若該邊在邊鏈表已經存在，則刪除鏈表中該邊至末尾的所有元素，設置當前邊為起邊，當前邊中心點的另一端點為起點，跳至Step 2；

Step 4若該邊與邊鏈表中的邊存在重復交點，則刪除鏈表中第一重復交點的邊至末尾的所有元素，設置當前邊為起邊，當前邊中心點的另一端點為起點，跳至Step 2；

Step 5若該邊不是起邊，則保存當前邊，設置當前邊為起邊，當前邊中心點的另一端點為起點，跳至Step 2；

Step 6刪除起邊，刪除孤立邊，跳至Step 1，準備獲取下一個連通多邊形。

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

2.1 三角劃分

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

圖3 包含連通

添加輔助線的思想是當連通多邊形存在包含連通時，根據匹配編碼找出對應邊，以匹配邊為基礎添加輔助線建立三角形，從而實現三角區域劃分。以下是添加輔助線的規則：

規則1在外層連通多邊形包含的區域內，找出與邊兩端點的距離之和最近點，建立端點與最近點之間的邊，即滿足包含、最近距離原則；

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

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

2.2 包圍多邊形匹配

國內外學者對多邊形匹配問題已經進行了大量研究[5-6]，但是由于包圍多變形存在多個重復邊的情況，并且需要通過包圍多邊形的匹配來為下一次的匹配進行定位，因此需要進行特殊處理。通過建立<屬性邊、夾角>結構，實現對包圍多邊形的幾何與拓撲表示，并且同時滿足了連通多邊形的匹配要求。

其中，屬性邊是由邊長度、匹配編碼號、輔助線標記組成。匹配碼是兩個包圍多邊形匹配成功后對應邊的編號，輔助線標記表示是否為匹配過程中添加的輔助線。由于對每次包圍多邊形匹配的結果進行了編碼，因此為多連通域圖形的全過程匹配提供了依據。

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

圖4 兩重對稱的包圍多邊形

2.3 多連通域圖形匹配算法

多連通域圖形匹配的基本思想是利用包圍多邊形實現圖形的外輪廓匹配定位，在此基礎上通過匹配編碼刪除對應的連通多邊形實現多連通域圖形的收縮，最終完成匹配。匹配的本質是從外至內不斷刪除連通域的過程，具體實現算法如下：

Step 1針對待匹配件進行預處理，包括合并重復線、直線斷點補合、刪除孤立邊等；

Step 2獲取標準件與待匹配件的包圍多邊形，進行包圍多邊形匹配；

Step 3若成功，則對圖形進行編碼；若失敗，則退出；

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

Step 5找出該邊所在的連通多邊形，進行多邊形匹配；

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

3 實驗分析

3.1 圖形匹配實例

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

3.2 線束圖紙識別實例

論文提出的方法已經在以AutoCAD為平臺使用ObjectARX進行二次開發的汽車線束工藝輔助設計系統的中得到了驗證。該系統主要是通過對表示汽車線束連接關系的圖紙進行理解分析，生成用于指導實際生產的工藝、工序卡片和進行物料統計。

表2 多連通域圖形匹配過程

線束圖紙主要包括圖框、圖紙規格說明、接插件、線束等部件，其中接插件是表示線束連接關系和進行圖紙布局的主要部件，具有多連通域圖形的特點，因此是主要的識別對象。在對圖紙進行自動識別的過程中，該系統以接插標準件庫為基礎[7]，首先對線束圖紙進行預處理，去除干擾信息；然后，遍歷標準件庫，依據多連通域圖形的唯一外輪廓特性，分別將標準件與線束圖紙中的各個孤立的外輪廓區域進行匹配，找出在圖紙中使用的庫中的接插件。

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

圖5 線束圖紙識別示意圖

4 總結與展望

工程圖紙的自動識別是進行圖紙理解的基礎。論文針對工程圖紙中出現的多連通域圖形匹配問題，首先，提出通過添加輔助線實現三角劃分，解決了包含連通的定位問題；然后，基于包圍多邊形和連通多邊形的匹配，根據匹配編碼逐步刪除連通域，收縮多連通域圖形，最終實現圖形匹配。

在圖紙識別過程中存在許多不確定性因素，僅僅通過精確匹配容易出現漏識別的現象，因此若將圖形相似特性引入到匹配中來將有效地提高識別率。文獻[6]已經對多邊形的相似匹配做了研究，然而尚不能有效解決多連通域圖形的相似匹配問題，因此找出一種可行、高效的方法是未來研究的重點。

[1]王蛛華, 曹 陽, 楊若瑜, 等. 基于規則的建筑結構圖鋼筋用量自動識別系統[J]. 軟件學報, 2002, 3(4):574-579.

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

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

[6]譚建榮, 岳小莉, 陸國棟. 圖形相似的基本原理、方法及其在結構模式識別中的應用[J]. 計算機學報,2002, 25(9): 959-967.

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