面向內容的工程圖識別與理解綜述

路 通， 蔡士杰

（南京大學計算機軟件新技術國家重點實驗室，江蘇 南京 210093）

作為體現設計意圖的主要載體，工程圖廣泛流通于機械、電子、航空航天、建筑、化學工程、服裝設計等在內的眾多應用領域。據統計，1995年美國和加拿大大約有 35億張各類工程圖，并以每年超過 2000萬的速度遞增（包括紙質及CAD電子格式）[1]。工程圖在數量及復雜性上迅速增加的同時，人工讀圖與解釋的方式相對滯后，其效率低、數據一致性及可重復性較差，顯然已無法滿足各種實際應用的需求。為適應工程圖信息自動提取與理解的需求，工程圖的識別與理解技術應運而生。

工程圖識別與理解的核心在于利用知識表示、圖形匹配、符號識別、幾何推理、語義表征及相關反饋等技術，以獲取工程圖中各種顯式描述（如幾何圖元、工程符號等）及隱式信息（如設計語義、工程對象等）為目標，實現工程圖中各種設計信息的有效提取與理解。在此基礎上，工程圖解釋可進一步擴展至諸如工程圖數據庫管理、工程設計信息復用、各種工程數據的自動計算、工程設計一致性審核及錯誤檢測、工程語義提取等具體應用。這種用于替代人工讀圖的智能化及自動化的計算機讀圖方式，無疑可極大地提高工程圖在各環節的流通效率，從而大幅縮短設計及應用周期并降低相應成本。工程圖的識別與理解的自動化、智能化已成為充分利用現存海量工程圖的有效途徑之一。

從20世紀70年代末至今，工程圖的自動識別與理解一直是文檔分析領域的研究熱點之一，其研究范圍包括最初將工程圖紙掃描位圖中轉換為CAD平臺可讀取的矢量描述，到近年來進一步應用于面向內容的工程圖解釋、設計復用與檢索、工程圖數據庫管理等。近年來先后提出了多種不同類型、適用于不同工程領域的工程圖解釋方法和原型系統，相關單位機構或系統包括法國LORIA研究所的Celesstin系統[2]、以色列工程技術大學的 MDUS系統[3-4]、美國伯克利大學[5]等。國內工程圖理解的主要研究機構包括浙江大學 CAD&CG國家重點實驗室[41,46-47,66]、南京大學軟件新技術國家重點實驗室[19,42,49,51,55,61,64-65,68]、中科院計算技術研究所和自動化研究所、清華大學CAD支撐軟件工程研究中心等。

一般而言，完整的工程圖識別與理解系統應包含如下3個階段：掃描位圖的矢量化與基本圖元（直線段、圓、弧段、曲線、文字）識別；位圖或矢量表示基礎上的工程符號識別；矢量描述基礎上的工程對象識別及工程語義提取。在此基礎上結合各種工程應用的需求，完成面向內容的工程圖檢索、計算或管理，或通過三維重建進一步完成三維環境下的各種應用。由于實際工程圖表示的復雜性與特殊性，上述3個階段之間并沒有嚴格的區分界限或次序，有時可相互作為驗證或解釋依據。

1 面向內容的工程圖識別與理解概述

各類工程圖以圖形化方式為不同應用提供包括設計、施工等在內的產品生命周期內各種信息與數據，是表達設計意圖、并在工程領域內各環節之間相互交流的主要媒體介質[6-10]。工程圖解釋的最終目標，則是從圖形化描述的二維線條工程圖（2D line engineering drawings）中，通過相應的識別與理解方法，自動提取其中各種幾何表示所對應的語義、功能描述等高層信息，并在此基礎上為各種不同應用提供數據。工程圖的自動解釋實際上是以圖形學、CAD及模式識別為基礎，以圖像處理、人工智能、計算機視覺及知識工程為支撐，并以位圖或矢量表示的線條工程圖為特定研究對象的相對獨立的研究體系。

二維工程圖主要有位圖與矢量圖兩種表示方式。早期工程制圖一般以繪圖板方式生成紙質工程圖，經掃描后可得到其位圖表示。近十年來隨著CAD技術的發展與普及，在大部分工程領域中，電子格式的矢量圖（如.dwg、.dxf等）已逐步取代了紙質圖。據統計，現存的各類工程圖中，紙質圖與電子圖比例大致為4:1。

無論以何種方式表示，典型的工程圖一般具有如下特點。首先，工程圖具有層次式的描述結構。工程圖一般由直線段、圓、弧段、各種曲線、字符串等基本圖元組成。基本圖元又進一步組合成各類結構化成分，如箭頭、點劃線、陰影線等；相關結構化成分可進一步組合為獨立于領域知識的各類工程符號（如尺寸線、軸線、對稱軸、孔洞等），或領域知識基礎上的各類工程實體對象。其次，工程圖中除存在各類基本圖元及其基礎上的結構化成分、工程符號、工程實體對象外，還存在各類隱式約束成分，用以指定圖元、結構化成分、工程符號、工程實體對象之間的各類隱式約束關系。如常見的尺寸線可用以指明工程對象的某種尺寸約束或比例關系，對稱軸可用于表明其兩側圖元及工程對象之間的映射關系等。其它常見的約束成分還包括距離約束（如距離靠近的不同成分之間可能存在匹配或組合關系）、引線約束（如標注字符串以一或多根連續引線引出，以遠離被標識對象）、位置約束、幾何約束等。第三，工程圖之間往往存在各種關聯關系，即單一工程圖一般只能給出某工程對象的部分信息，而無法對其進行完整描述。因此解釋某個工程對象時，必須充分發掘和利用該類關聯關系。典型例子是工程對象的三視圖表達方式，其中單一視圖僅能給出該對象的某個側面輪廓、尺寸及標注屬性；要對該工程對象進行完整描述，必須首先建立三視圖之間的幾何及語義上的關聯關系。

基于工程圖的上述特點，工程圖自動解釋又可分為3個層次：以關鍵詞檢索為基礎的圖文檔管理，基于形狀匹配與幾何推理的工程符號識別，以及在融合領域知識基礎上、以語義提取為主要目標的面向內容的設計信息檢索與復用。

關鍵詞檢索方法一般首先通過工程圖的版面分析（layout analysis）方法，提取工程圖中的圖簽描述框，再通過模板匹配等方法提取其中的工程圖名、圖類型、設計日期等關鍵字信息；在此基礎上結合工程圖中的特征字符串標注完成檢索。如工程圖為位圖表示方式，則事先應進行位圖去噪等預處理，并在此基礎上完成字符識別。該方法已應用于一些圖文檔管理系統中，用以從各種工程圖數據庫中檢索目標工程圖，或快速定位其中特定類型的工程對象。其主要缺點是關鍵字的確定具有一定的主觀性，難以實現通用的、基于工程圖內容提取的智能化管理。

基于形狀匹配與幾何推理的工程符號識別側重于從形狀分析與匹配入手，在工程圖基本圖元幾何關系分析基礎上（如相交、平行、垂直等），從復雜工程圖環境中提取各種特征信息，由此逐步完成工程符號識別。如 Yang[10]以統計約束直方圖方法生成特征向量描述子（feature vector descriptor），以此作為符號比較依據；Llados等[11]在區域鄰接圖（region adjacency graphs）基礎上以子圖匹配（subgraph matching）方法來識別符號，Kumazawa[12]則使用形狀特征匹配方法提取各類符號等。

融合領域知識基礎上、以語義提取為主要目標的面向內容的設計信息檢索與復用側重于提取工程圖所隱含的整體高層設計語義，在此基礎上進一步用于三維重建、工程數據的自動計算、工程圖關聯性及一致性檢查等，從而大幅提高工程圖應用效率。如Luo等[13]通過圖形知識推理以自動解釋工程圖，Prabhu等[14]利用結構化模式識別方法從 CADD工程圖提取對象特征以進行解釋，Zhi等[15]則從 CAD平面圖出發，使用基于圖的方法重建其中的拓撲關系，在此基礎上自動提取工程對象數據。

上述不同解釋層次可分別提取圖元、符號及各類工程實體對象，以滿足各種應用的需求。但總體上講，目前仍缺乏一種有效及通用的、可適合于實際工程圖解釋的方法。工程圖解釋的復雜性主要體現在以下幾個方面：首先，二維幾何描述與其所表達的復雜工程語義之間存在距離。幾何描述是表達工程語義信息的必要前提，但僅從幾何表示入手，并不能實現其隱含的設計信息的提取。只有建立在適當的領域知識表示基礎上、結合各種工程對象表示規則，才能實現面向內容的工程圖自動解釋；其次，從某種意義上講，工程圖可看作為工程性與藝術性的結合體，即工程圖既表達工程中所需的精確性描述（如通過尺寸線限定對象輪廓及形狀，以軸線指明其準確位置）。同時又使用大量的隱式表達方式（如常見的對稱、省略、引用、示意性表示），以在盡可能簡化工程圖描述、縮短制圖過程的前提下表達精確工程語義。但這類隱式表達往往給工程圖自動解釋帶來困難；第三，由于實際工程的自動解釋往往涉及一系列相關工程圖，不同工程圖之間、分布于各工程圖內的各工程實體對象或符號之間往往有各種關聯關系，如參考、引用、復制等。這種關聯或約束關系要求工程圖的自動解釋必須遵從一定的次序，如解釋復制對象之前，應該首先定位其源對象。而這種次序又隨著工程圖內容、乃至設計者的表達習慣而變化，并沒有確定的規律，有時還會出現多次循環參照的情況，由此也給工程圖的自動解釋帶來困難；最后，由于工程圖類型的多樣性，工程圖解釋在識別算法性能評測、基準庫生成等方面也存在一定的困難。

如上所述，在掃描位圖方式或CAD矢量繪制基礎上的工程圖解釋涉及的主要技術包括工程位圖的矢量化與圖元識別、工程符號識別、工程對象語義理解幾個部分。此外也涉及解釋系統的界面設計及用戶反饋基礎上的解釋優化等。圖1給出了一個完整的工程圖解釋系統的框架。

圖1 工程圖解釋系統框架

2 工程圖矢量化與基本圖元識別

矢量化及基本圖元識別所要解決的主要問題是將工程掃描位圖中的基本圖元轉換為 CAD平臺能夠讀取的各種矢量格式。作為最先提出的工程圖解釋技術之一，矢量化研究在國內外已開展了許多年，但由于工程圖本身的復雜性、保存和掃描過程中各種噪音干擾，目前自動識別與轉換算法的效率、準確性仍有諸多局限性，存在較大的研究與改進空間[16]。

現有矢量化與圖元識別方法大體可分為 3類：基于全局統計特征的矢量化、基于局部特征匹配與像素跟蹤的矢量化及基于整體化識別的矢量化。

2.1 基于全局統計特征的工程位圖矢量化

基于全局統計特征的方法側重于利用Hough函數、細化或骨架圖、輪廓提取等方法，生成工程位圖全局參數，以從其中提取完整的矢量信息，同時盡可能避免相交、粘連等的干擾。該方法可進一步分為兩類：全局參數提取與結構特征簡化。

全局參數提取方法側重于提取與計算工程位圖的參數描述或統計特征，并以此為依據，結合不同類型圖元的幾何約束來完成工程位圖中基本圖元的提取。全局參數提取方法中，基于霍夫變換（Hough Transform，HT）的圖元識別方法應用較為廣泛。如 Yang等[17]在線條連接分析基礎上使用 Hough變換來檢測位圖中的短線條；Ching[18]則利用位圖中線寬信息將交點轉換為帶（belts），然后應用Hough變換對各帶進行測試，并迭代生成位圖中的線段。但由于HT變換計算效率較低，其方法并不適用于數據量較大的工程圖矢量化。對此Song等[19]提出一種融合參數空間與圖像空間的 Hough變換方法，以解決傳統Hough變換僅作用于其參數空間、從而導致計算效率低較的問題。該方法通過基于圖像特征點的梯度預測（gradient prediction）來避免無關點干擾、從而加速Hough變換的累積過程，并引入邊界記錄器（boundary recorder）以消除線段識別的冗余校驗；在此基礎上進一步應用于檢測大型工程位圖中的直線段。除在二維空間中檢測直線段外，Hough變換亦可進一步用于在多維空間中檢測圓、橢圓等曲線[20-22]。Hough變換的其它改進包括隨機Hough變換（RHT）[23]、概率Hough變換（PHT）[24]、動態Hough變換（DHT）[25]、參數空間分解[26]等。一般而言，充分利用圖元的幾何特性，可有效降低Hough變換的維度及計算量。

除Hough變換外，全局參數提取方法還可提取距離、斜率、面積等參數，以引導矢量化過程。如Ray等[27]及Teh等[28]使用曲線上的最大及最小曲率處的控制點作為構造矢量圖元的依據；Leu等[29]則使用某像素處的最大垂直允許距離作為矢量化過程中是否生成新結點的依據。

相對于全局參數提取方法，結構特征簡化方法側重于通過細化（thinning）或輪廓生成等方法，提取其結構或拓撲特征，據此完成基本圖元的識別。其中細化方法較早應用于矢量化系統。細化方法的基本思想是采用各種邊界腐蝕操作逐層削去圖像的外邊界像素點，直到留下單像素寬的骨架（skeleton）并將其轉化成鏈碼表示，然后通過折線擬合將鏈碼轉化成低級矢量格式（直線段或折線段），最后用基于矢量的圖形識別方法在短線段中識別出其中的圖形對象[30-31]。此外，Zou等[32]在離散局部對稱性（discrete local symmetry）基礎上生成骨架描述，以充分利用識別對象的局部對稱性提高精度。Chang等[33]在直線掃掠操作（line sweep operation）基礎上給出了一個新的細化算法。該方法設定待識別對象為多邊形（polygon），然后在位圖中檢測所有平行的邊對（pairs of edges）并按距離等約束排序，最后在水平和垂直方向上將邊對組合為規則多邊形。Janssen等[34]則使用一種基于細化的自適應矢量化算法，該算法包括3個步驟：首先統計所有連接交點處包圍盒對角線長度直方圖（包圍盒邊分別與x軸及y軸平行），根據直方圖刪除過小對象并計算全局線寬，再以2倍全局線寬為長度閾值，通過骨架方法生成初步的粗糙矢量化結果；然后依次生成一系列錨點（anchor points），每個錨點定義為位圖中的控制點（如端點、交點、拐角等）；最后在兩兩錨點間進一步精細化矢量化描述。由于原始位圖用作圖元識別及驗證依據，因此該方法可看作一個自適應過程。

除細化方法生成工程位圖骨架描述外，Leymarie等[35]使用距離變換方法（distance transform）計算最小能量函數并得到其彈性邊界，然后將其與曲率極值等特征整合，在此基礎上生成Euclidean骨架表示（Euclidean skeleton representation），并以此作為二維對象的形狀描述識別依據。最近Shang等[36]及Gu等[37]在脈沖耦合神經網絡（pulse coupled neural networks, PCNNs）基礎上生成位圖的PCNN骨架描述，以便骨架信息中保留更多原始信息、提高識別準確度及魯棒性。

一般而言，細化方法及骨架化方法可大幅減少圖元識別過程中的計算開銷、同時保留了形狀的拓撲結構，且具有旋轉無關性。此外，大部分算法還可維持圖元之間的連接性和相交性。其主要缺點是容易受噪音干擾；由于細化過程丟失了線寬等形狀信息，容易導致在各種相交交點處（如“T”形、“L”形、“X”形相交等）產生畸變。此外細化過程中需反復遍歷像素點，并完成大量短線段合并，因而其速度較慢。

相對于骨架方法而言，輪廓方法[38-39]先提取出圖像的輪廓，然后找出匹配的輪廓對，在每個輪廓對之間用對應輪廓點的中點可以擬合出該段圖像的中心線，最后在所有中心線中搜索、拼接來恢復完整的圖形對象。這種方法雖然可以避免遍歷全部像素點并能保持線寬信息，但由于在相交、粘連處無法找到輪廓對，必然會將一個完整的圖形對象分為多段，并且當線條位圖退化時，輪廓之間的常常存在一對多的對應關系，給匹配帶來困難。

行程編碼方法(run length encoding)[40-42]先對圖像進行行程編碼(Run length encoding)；然后分析行段生成各種形式的鄰接圖結構，由圖像中的線狀區域的行段中點擬合而成的線段作為鄰接圖中的邊，非線狀區域（相交或粘連處）作為鄰接圖中的節點連接相鄰的邊；最后在圖結構上進行線段延伸、合并識別圖形對象。這類方法難以處理實際圖紙中的復雜情況，并且當圖紙質量較差時對節點的分析（如出、入度計算）非常困難。此外，這類方法對行程編碼的掃描方向的依賴性導致斜線矢量化的質量較差。有些方法通過水平、垂直雙向行程編碼對偏向水平、垂直的線段（以±45°角區分）分別進行處理，雖然提高了對接近水平、垂直的線段的處理能力，但卻大大增加了算法的復雜度和處理時間[19]。

基于全局統計特征的矢量化方法從位圖中各種特征描述、并以特征描述比較來完成工程位圖中的圖元識別，具有平移、旋轉、縮放不變性，可同時結合圖元幾何特性以提高精度與計算效率，因而在矢量化系統中應用較為廣泛。其主要缺點是難以正確處理各種圖形對象相交與粘連情況、受噪音干擾較大。

2.2 基于局部匹配與像素跟蹤的工程位圖矢量化

基于局部特征匹配與像素跟蹤的矢量化與圖元識別側重于從工程位圖局部特征出發，以像素跟蹤、參數匹配等方法追蹤基本矢量形式，并將其逐步從工程圖中剝離，完成圖元識別。如Chai等[43]提出正交 Zig-Zag (Orthogonal Zig-Zag，OZZ)方法對工程位圖稀疏取樣與檢測。該方法首先以水平掃描線每次間隔 10個像素從左到右掃描，若遇到一個黑像素，則進入該區域并開始一個 OZZ過程：若遇到區域邊界，則記錄該輪中間點像素，并繼續在黑像素區域內按正交方向掃描；否則在 30個像素的預定義閾值內延伸。水平掃描結束后按類似方法完成垂直掃描。由于OZZ方法對圖像稀疏采樣，其效率較高。OZZ方法的缺點是對噪音敏感，且只能追蹤直線段。Liu等[44]及Dori等[45]在此基礎上提出了稀疏像素矢量化算法（sparse pixel vectorization，SPV）。該方法從任意可靠中點開始，按預定步長沿水平或垂直方向進行跟蹤，獲得每一步的中點（對斜線則用水平和垂直方向交替跟蹤）。跟蹤完整個圖像后，對所得的中點序列加以折線化，以去除冗余點，最后在此基礎上識別圖元對象。相對于OZZ方法，SPV主要有以下幾點改進：在一次跟蹤過程中即可完成水平、垂直、傾斜掃描；對交點優化處理；充分利用中軸信息以提高跟蹤可靠性。與OZZ類似，SPV通過跳躍采樣減少了訪問象素點的次數，但掃描次數更少，因此其矢量化速度、可靠性有所提高。SPV算法的缺點在于若交點或粘連尺寸大于跟蹤步長閾值，跟蹤就會停止，從而造成圖元斷裂。

一般而言，局部匹配與像素跟蹤基礎上的工程位圖矢量化方法計算速度快、易于捕捉工程位圖局部特征信息，可作為基于全局統計特征矢量化方法的必要補充。其主要缺點是缺乏整體信息引導，在追蹤過程中容易生成各種短矢量，需要后期完成合并、優化等進一步處理，從而增加計算開銷，同時也容易產生其它錯誤。

2.3 基于整體化識別的工程位圖矢量化

基于全局統計特征的方法側重于模擬人的讀圖過程，利用圖元的整體約束及連續性，從工程位圖中提取完整的矢量信息；同時利用方向、線寬、長度、交點等約束信息，減少或避免相交、粘連及毛刺、噪音等的干擾，從而提高圖元識別效率。基于整體化識別的工程位圖矢量化是從工程位圖中提取各種圖元的有效方法之一。

Li等[46]將工程位圖同一行/列中所有連通黑像素集合定義為掃描串，并利用掃描串之間的連通關系和輪廓信息完成圖元矢量化。掃描串具有一定的整體特性，同時也可利用掃描串端點處的輪廓信息獲取局部識別特征；但由于該方法首先將工程位圖轉換為短折線表示，矢量化后通過擬合生成基本圖元，效率較低，且短折線擬合容易產生誤差。Li等[47]將有重疊關系的掃描段定義為圖段，并利用圖段的延伸性與幾何約束完成工程圖整體矢量化，但其缺點在于無法識別工程位圖中的短線條。Wang等[48]則首先檢測工程位圖中的線寬信息，然后按其寬度不同生成一系列梯形塊組成的條塊圖，并對不同條塊圖分別進行整體識別。Song等[49-51]進一步提出了從工程位圖中直接提取與識別各種圖元的整體矢量化方法。該方法首先從線條無相交、粘連的部分測得特征段，然后以該特征段的初始方向為指導、線寬為約束進行定向跟蹤，并在跟蹤過程中動態調整初始參數以提高準確性，同時排除粘連及噪音干擾。在此基礎上將工程位圖中的整體識別范圍從單一圖形元素擴大到線條網，并在線條網基礎上完成快速識別。

整體矢量化方法符合人的視覺認知原理，整體化過程中可利用已識別信息輔助判斷相交、粘連等復雜情況并指導后續識別，對噪音等魯棒性較好。整體矢量化方法較適合于識別工程位圖中大量存在的各類線條信息（包括直線段和曲線），并以此為引導，進一步完成后繼字符分割與識別。

矢量化研究是管理與復用現存的海量紙質工程圖的有效方法。除一些研究原型系統及方法外，其它較典型的商品化工程圖解釋系統包括德國Softelec公司的VPStudio/VPRaster Pro、美國Able公司的 R2V、挪威 RasterEx公司的RxAutoImage、日本Ravtek公司的Crucible Vector Conversion Engine等。不過，由于工程圖的復雜性和各種噪音、畸變等的影響，尚無任何一種系統可以實現準確、通用的矢量化識別。此外，工程位圖中的文本識別也是難點之一，其字體、字號、字符之間的分割方法、與周圍其它圖元（如線條、工程符號等）的粘連等因素均使得其識別準確率較低，仍存在較大的改進空間。

3 工程圖理解與語義提取

工程圖解釋系統的最終目標是從所給二維圖中得到設計及語義信息，并在全局整合基礎上完成工程圖中的錯誤檢測、一致性校驗、工程數據計算等應用。工程圖理解一般包括工程符號識別及工程對象識別兩個階段。此處的工程符號一般專指具有特定形狀和語義的圖元組合，如箭頭、尺寸線、標高符等領域無關的工程符號，或花灑、消防栓等領域相關的工程符號。工程對象一般指具有特定功能描述、領域相關的各類工程實體（engineering entities），如機械工程圖中的各類零件、建筑工程圖中的柱墻梁板結構構件的幾何描述等。

3.1 工程符號識別

工程符號識別大體可分為兩類：結構化工程符號識別與基于統計特征的工程符號識別。結構化工程符號識別首先將各類符號轉換為對應的幾何圖元（如直線段、弧、圓、矩形等）及其關系描述，然后從矢量表示的工程圖中通過子圖匹配、圖元約束檢測、可變形模板匹配（deformable template matching）等方法完成符號比較與識別。Seong等[52]首先將比較對象轉換為屬性關聯圖（attributed relational graphs）描述，然后通過比較圖的頂點、邊對于關聯距離度量（relational distance metric）的權重來計算形狀的相似度；比較過程中若某形狀對應的屬性關聯圖頂點數較多，則按子圖同構（subgraph isomorphism）方法進行細化比較。該方法的主要缺點是其計算效率較低，且屬性關聯圖的生成容易受噪音和變形干擾，使得精確比較（exact graph matching）相對困難。Lladós等[53]提出一種改進的容錯子圖同構（error-tolerant subgraph isomorphism）算法，用以在區域鄰接圖（region adjacency graphs）基礎上實現非精確比較（inexact graph matching）。Fahmy等[54]則使用預定義的圖語法（graph grammars）描述作為識別符號依據，并引入錯誤分析與檢測以處理各種變形。該方法適合于形狀可精確表示的各類符號的識別；類似方法還包括使用規則[55]或網絡圖[56]定義符號的幾何約束等完成符號檢測與識別。

基于統計特征的工程符號識別則一般從工程位圖中提取各類統計特征，然后在特征空間中通過特征向量比較完成符號識別。根據分析對象層次的不同，基于統計特征的工程符號識別進一步可分為3個層次：工程位圖像素分析、幾何統計特征提取及函數變換。工程位圖像素分析直接從位圖像素特征分析入手生成特征向量，如Belongie等[57]首先計算兩個形狀位圖中的對應點，然后對每個求解出的對應點分配一個形狀上下文描述子（shape context descriptor），用以捕獲其它對應點相對于其自身的分布情況；然后通過描述子的比較來計算形狀的近似度。該方法還通過計算每個像素的切線分布來保證旋轉不變性，但魯棒性較差。Su[10]首先用細化方法得到待識別符號的骨架表示，然后分別以骨架中每個像素為基準點，與骨架中其它所有像素建立角度約束分布直方圖；在此基礎上將所有分布直方圖整合為固定維的特征向量，作為符號檢測與識別依據。該方法具有縮放及全局旋轉不變性。幾何統計特征提取方法提取工程圖中的矩、曲率、對稱軸、環形面積等幾何特征，一般具有旋轉、平移、縮放不變性，計算也相對簡單；函數變換方法則利用函數變換（如Fourier變換、Fourier-Mellin變換等）生成特征向量，然后通過計算特征向量距離，或通過神經網絡、決策樹等方法完成工程符號識別與分類。

工程符號識別是工程圖解釋的重要組成之一。完成各類工程符號的分析與提取后，可從原始工程位圖或工程矢量圖中刪除對應符號組成圖元，以簡化搜索空間；同時由于工程符號往往與某工程對象關聯（如尺寸線用于指明工程對象某方向長度、標高符表明其高度），因此工程符號的識別也可用于引導后繼的工程對象識別。

3.2 工程對象識別

工程符號和工程對象的主要區別在于：工程符號幾何描述相對固定，可通過顯式約束、規則、符號模板等進行描述，因此工程符號的識別實質上可看作特征描述的匹配問題；而工程對象的幾何形狀、屬性等一般依賴于具體的工程圖設計環境而定，無法通過明確的幾何描述預定義；此外，隱含在工程對象幾何形狀中的高層設計語義信息（如對稱、復制、參考、索引等）均需要單獨予以分析與提取。工程對象識別是工程圖解釋的最終目標之一，并可在此基礎上進一步提取各種應用所需的工程數據。

工程對象識別與高層語義提取一直是工程圖解釋的難點[58-59]。現有方法一般側重于從三方面完成對象識別：領域知識的表示；使用特征提取、幾何結構分析等方法搜索工程對象可能的存在區域；在領域知識表示（結構化知識描述、規則庫等）基礎上，結合工程圖類型、全局及局部環境分析，完成特定工程對象的搜索與識別。

由于工程對象的領域相關性，領域知識的表示是工程對象識別需首先解決的問題。Joseph等[60]較早提出了一個基于知識描述的機械工程圖解釋系統 Anon，該系統通過一組顯式規則描述工程領域知識，并使用 LR(1)分析器完成規則讀取與解析；同時結合工程對象的示意性描述，結合自底向上、自頂向下兩種搜索策略完成工程圖的自動解釋。Wang等[55]使用類似的方法，首先生成一系列工程對象特征描述規則庫，然后在相關規則的約束下搜索特定工程對象。Yang等[61]在此基礎上進一步提出了基于特征提取與組合的識別規則自動生成與調整方法，在識別過程中動態擴充預定義識別規則庫，從而提高對新類型工程圖的識別適應能力。基于規則的工程圖對象識別系統實現較為簡單，但在實際應用中隨著規則庫的逐步擴充，規則間的關聯與約束關系難以維護。一些工程圖解釋系統采用結構化的知識描述方法引導工程對象的識別，如 Dov等[7]開發了用于工程圖解釋的 MDUS系統，將各類工程對象及其內部關聯關系組織為層次式結構，結構中包含特定的對象識別算法；輸入工程圖后，按該層次式結構依次搜索與識別。此外，Bimber等[62]使用BNF語法、Caetano等[63]使用模糊關系語法（fuzzy relational grammars）描述待識別對象的形狀、結構等信息，并以此為引導，在工程圖中完成搜索。

工程圖全局及局部環境的分析同樣對其中的工程對象識別起到關鍵作用。Lu等[64]首先利用符號識別方法從復雜工程圖中搜索簡單尺寸線，然后通過尺寸線組合、軸網生成、局部坐標系建立到全局坐標系整合，并在全局坐標基礎上建立多工程圖隱式關聯關系，最后逐步以坐標系網格點為內點搜索封閉輪廓，以各閉合輪廓為約束，在工程圖中完成各類工程對象的識別。Zhi等[15]使用基于圖的方法，首先從建筑工程平面圖中完成各閉合區域的識別，然后對各區域重建其拓撲關系，最后通過各區域間的位置、連接等關系完成單元劃分，并在此基礎上自動生成消防通道線路模擬。Prabhu等[14]則使用基于字符串的結構化模式識別方法從 CADD工程圖中提取工程對象特征。

工程對象識別基礎上的典型應用包括各類工程圖的三維重建[65-67]、工程數據生成[15]、4D建模[68]等。但一般而言，工程對象的自動識別與理解較大程度上依賴于特定的領域知識，大多數現有方法通過硬編碼、靜態規則庫等方法完成識別，通用性較差，擴充與維護相對困難。因此，對于各類實際復雜工程圖，仍需在知識表示、隱式語義信息提取、識別方法通用性等方面進一步完善。

4 工程圖識別性能評價

隨著工程圖識別與理解算法研究的深入及各商業系統的開發，由于各自測試數據集并不一致，如何對各類工程圖解釋系統進行客觀、統一的性能評價，也逐步成為工程圖解釋中的重要內容之一。

Kong等[69]提出了虛線圖元識別的性能評價方法，通過測試矢量線條和正確結果之間的夾角和距離，計算其匹配程度，據此測試識別算法性能。該方法覆蓋了端點測試、線型測試、正確率、誤識率等，但不包含線寬信息，也沒有考慮線條分裂、合并等錯誤。Hori等[70]對機械工程圖識別進行了性能評價，對線寬變化采用端點匹配閾值，提高了線寬變化的適應性；同時按線條長度加權匹配，部分消除了剛性匹配閾值的影響；但仍沒有考慮線條分裂、合并等錯誤的情況。Phillips等[71]則對包含直線段、圓、弧、文本塊的工程位圖矢量化性能進行了系統評價，提出了各種圖元匹配算法（包括線-線匹配、弧-弧匹配、弧-線匹配、弧-圓匹配、圓-圓匹配、字符-字符匹配 6種），并給出了漏識率、錯識率、識別精度、交互開銷等測試指標的計算方法，在此基礎上對現有識別算法進行了測試與比較。該方法的主要缺點是要求工程圖噪音干擾少，且不支持諸如多段線（polylines）等復雜圖元及工程符號的識別性能評價。Liu等[72]進一步提出了對像素級和矢量級分別給出轉換率和誤識率的定義和檢測方法，然后綜合各個獨立性能指標定義了反映光柵-矢量綜合轉換程度的整體性能指標[49]。此外，Song等[51]對矢量化中的弧識別性能進行了評測；Jaisimha等[73]則通過 Hausdorff距離計算矢量化后所得的單像素寬曲線與真實曲線之間的偏離值，以此作為矢量化算法性能評測依據；Wang等[74]對工程圖中的表格識別進行了評測，Bodansky等[75]則對局部矢量化偏差給出了性能評測指標。

用戶交互次數、時間也是的工程圖識別與理解性能評測的另一個指標。一般而言，自動解釋速度越快，所需完整交互的時間越少，識別率越高，所需人工交互工作量越小。Chhabra等[76]給出了一種基于用戶修改工作量的自動化解釋系統性能評價方法。

除上述各種性能評測方法與指標外，一些文檔分析領域的國際會議提供了圖元矢量化、各種類型與表示的工程符號識別的測試基準庫、評測指標，并開展矢量化、符號識別等國際競賽[77-78]。

5 存在的主要問題及展望

由于工程圖類型的多樣性和工程圖本身的復雜性，包括圖元矢量化與識別、各類工程符號識別、語義理解在內的工程圖解釋，在知識表示、識別算法設計、性能評測及實際應用等多個環節仍有深入研究與改進的空間：

1）工程圖中往往存在噪音干擾；如何有效消除各種噪音干擾、同時保證圖元識別率和識別的魯棒性，仍需進一步深入研究。此外，工程圖中往往存在各種相交和粘連情況（如線線相交、字線相交、字字相交等），容易給工程圖元識別帶來困難，應進一步深入研究；

2）工程圖高層語義信息的提取一直是工程圖自動解釋的難點之一。如何進一步借鑒人工讀圖方式、從工程圖幾何描述中提取其各種形式的隱式表達（如對稱、省略、引用、示意性表示）和設計語義信息，仍需進一步研究；

3）用戶交互與反饋是改進工程圖自動解釋系統的有效方法之一；應進一步深入研究適用于工程圖解釋的用戶相關反饋技術，允許主動學習用戶交互意圖，以在理解其主觀評價基礎上實現智能學習與理解；

4）識別性能評測仍需進一步深入研究，以達到較完整地覆蓋工程圖中常見的各種幾何圖元及其相交情況，并建立較完整的、面向識別的各類工程符號及工程對象數據庫；

5）領域知識的表示仍需改進，以適應工程圖圖元量大、工程符號或工程對象類型復雜、關聯性強等特點；

6）自動識別過程中必需的各種長度、角度、距離等閾值計算方法仍需改進，以適應動態、自適應的識別過程；

7）工程位圖中的字符識別算法受噪音、粘連等情況干擾較大，仍缺乏有效、通用的字符分割與識別算法；

8）工程圖識別與理解仍需和各種實際應用進一步結合，并與現有各CAD、CAD系統整合，以切實解決行業自動化問題。

[1]Nagasamy V, Langrana N A. Autoamted restoration of engineering drawings into a CAD daba base [J].Engineering with Computers, 1988, 4(3): 165-171.

[2]Vaxivière P, Tombre K. CELESSTIN IV: Knowledgebased analysis of mechanical engineering drawings [C]//Proceedings of IEEE International Conference on Systems Engineering, Kobe, Japan, 1992: 242-245.

[3]Dov D, Liu Wenyin. Automated CAD conversion with the machine drawing understanding system: concepts,algorithms and performance [J]. IEEE Transactions on Systems, Man and Cybernetics. Part A: Systems and Humans, 1999, 29(4): 411-416.

[4]Dori D. Dimensioning analysis: toward automatic understanding of engineering drawings [J].Communications of the ACM, 1992, 35(10): 92-103.

[5]Lewist R, Séquin C. Generation of 3D building models from 2D architectural plans [J]. Computer- Aided Design, 1998, 30(10): 765-779.

[6]Cardone A, Gupta S K, Karnik M V. A survey of shape similarity assessment algorithms for product design and manufacturing applications [J]. Journal of Computing and Information Science in Engineering,2003, 3(2): 109-118.

[7]Tombre K. Ten years of research in the analysis of graphics documents: achievements and open problems [C]//Proceedings of the 10thPortuguese Conf.on Pattern Recogniton, Portugal, 1998: 11-17.

[8]Yu Yuhong, Samal A, Seth S C. A system for recognizing a large lcass of engineering drawings [J].IEEE Transactions on Patter Recognition and Machine Intelligence, 1997, 19(8): 868-890.

[9]Zheng Yefeng, Li Huiping, Doermann D. A parallelline detection algorithm based on HMM decoding [J].IEEE Transactions on Patter Recognition and Machine Intelligence, 2005, 27(5): 777-792.

[10]Yang Su. Symbol recognition via statistical integration of pixel-level constraint histograms: a new descriptor [J]. IEEE Transactions on Patter Recognition and Machine Intelligence, 2005, 27(2):278-281.

[11]Llados J, Marti E, Villanueva J J. Symbol recongnition by error tolerant subgraph matching between region adjacency graphs [J]. IEEE Transactions on Patter Recognition and Machine Intelligence, 2001, 23(10): 1137-1143.

[12]Kumazawa I. Compact and parametric shape representation by a tree of sigmoid functions for automatic shape modeling [J]. Pattern Recognition Letters, 2000, 21(6-7): 651-660.

[13]Luo Yan, Liu Wenyin. Engineering drawings recognition using a case-based approach [C]//Proceedings of International Conference on Document Analysis and Recognition, 2003: 190-194.

[14]Prabhu B S, Pande S S. Intelligent interpretation of CADD drawings [J]. Computers & Graphics, 1999,23(1): 24-44.

[15]Zhi G S, Lo S M, Fang Z. A graph-based algorithm for extracting units and loops from architectural floor plans for a building evacuation model [J].Computer-Aided Design, 2003, 35(1): 1-14.

[16]Hilarie X, Tombre K. Robust and accurate vectorization of line drawings [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2006,28(6): 890-904.

[17]Yang M, Lee J S, Lien C C, et al. Hough transform modified by line connectivity and line thickness [J].IEEE Transactions on Pattern Analysis and Machine Intelligence, 1997, 19(8): 905-910.

[18]Ching Yutai. Detecting line segments in an image——a new implementation for hough transform [J].Pattern Recognition Letters, 2001, 22(3-4): 421- 429.

[19]Song Jiqiang, Lyu M. A hough transform based line recognition method utilizing both parameter space and image space [J]. Pattern Recognition, 2005,38(4): 539-552.

[20]Ho Chunta, Chen Ling. A fast ellipse/circle detector using geometric symmetry [J]. Pattern Recognition,1995, 28(1): 117-124.

[21]Raymond K K Y, Peter K S T, Dennis N K L.Modification of hough transform for circles and ellipses detection using a 2-dimensional array [J].Pattern Recognition, 1992, 25(9): 1007-1022.

[22]Ballard D H. Generalizing the hough transform to detect arbitrary shapes [J]. Pattern Recognition, 1981,13(2): 111-122.

[23]Xu Lei, Oja E. Randomized hough transform: basic mechanisms, algorithms and computational complexities [J]. CVGIP: Image Understanding, 1993,57(2): 131-154.

[24]Kiryati N, Eldar Y, Bruckstein A M. A probabilistic Hough transform [J]. Pattern Recognition, 1991,24(4): 303-316.

[25]Leavers V F. The dynamic generalized hough transform: its relationship to the probabilistic Hough transforms and an application to the concurrent detection of circles and ellipses [J]. CVGIP: Image Understanding, 1992, 56(3): 381-398.

[26]唐 珉, 胡占義. 參數空間分解法[J]. 計算機學報,1999, 22(9): 911- 917.

[27]Ray B K, Ray K S. Detection of significant points and polygonal approximation of digital curves [J].Pattern Recognition Letters, 1992, 13(6): 443-452.

[28]The C H, Chin R T. On the detection of dominant points on digital curves [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1989,11(8): 859-872.

[29]Leu J G, Chen L. Polygonal approximation of 2D shapes through boundary merging [J]. Pattern Recognition Letters, 1988, 7(4): 231-238.

[30]Lam L, Lee S W, Suen C Y. Thinning methodologies-a comprehensive survey [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1992,14(9): 869-885.

[31]León J, Yánez C, Guzmán G. Thinning algorithm to generate k-connected skeletons [C]//Lecture Notes in Computer Science, 2004, 3287: 605-612.

[32]Zou Jujia, Chang H H, Yan Hong. Shape skeletonization by identifying discrete local sysmetries [J]. Patter Recogniton, 2001, 34(10):1895-1905.

[33]Chang F, Lu Y C, Pavlidis T. Feature analysis using line sweep thinning algorithm [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1998,21(2): 145-158.

[34]Janssen R D T, Vossepoel A M. Adaptive vectorization of line drawing images [J]. Computer Vision and Image Understandng, 1997, 65(1): 38-56.

[35]Leymarie F, Levine M D. Simulating the grassfire transform using an active contour model [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1992, 14(1): 56-75.

[36]Shang Lifeng, Yi Zhang. A class of binary images thinning using two PCNNs [J]. Neurocomputing,2007, 70: 1096-1101.

[37]Gu Xiaodong, Yu Daoheng, Zhang Liming. Image thinning using pulse coupled neural network [J].Pattern Recognition Letters, 2004, 25(9): 1075-1084.

[38]Han C C, Fahn K C. Skeleton generation of engineering drawings via contour matching [J].Pattern Recognition, 1994, 27(2): 261-275.

[39]Fan Kuochin, Chen Denfong, Wen Minggang.Skeletonization of binary images with nonuniform width via block decomposition and contour vector matching [J]. Pattern Recognition, 1998, 31(7):823-838.

[40]Roseborough J B, Murase H. Partial eigenvalue decomposition for large image sets using run-length encoding [J]. Pattern Recognition, 1995, 28(3):421-430.

[41]譚建榮, 彭群生. 基于圖形約束的工程圖掃描圖像直線整體識別方法[J]. 計算機學報, 1994, 17(8):561-569.

[42]鄒榮金, 蔡士杰, 張福炎. 基于行程編碼的直線擬合方法及其誤差估計[J]. 軟件學報, 1997, (S1):404-410.

[43]Chai I, Dori D. Orthogonal Zig-Zag: an efficient method for extracting lines from engineering drawings [C]// Visual Form, Plenum Press, New York, London, 1994: 127-136.

[44]Liu Wenyin, Dori D. Sparse pixel tracking: a fast vectorization algorithm applied to engineering drawings [C]//Proceedings of 13thICPR, Austria,1999: 808-811.

[45]Dori D, Liu Wenyin. Sparse pixel vectorization: an algorithm and its performance evaluation [J]. IEEE Transaction on Pattern Analysis and Machine Intelligence, 1999, 21(3): 202-215.

[46]李偉青, 譚建榮, 彭群生. 基于圖段結構的整體識別方法的研究[J]. 計算機學報, 1998, 21(8):753-758.

[47]李 賓, 譚建榮, 彭群生. 一個基于掃描串的統一整體矢量化算法[J]. 軟件學報, 1998, 9(6):426-431.

[48]王金鶴, 歐宗瑛, 夏曉東. 工程掃描圖像的直線整體識別算法[J]. 中國圖象圖形學報，1998, 3(11):912-917.

[49]Song Jiqiang, Su Feng, Tai C L, el at. An object-oriented progressive-simplification-based vectorization system for engineering drawing: model,algorithm, and performance [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2002,24(8): 1048-1060.

[50]Song Jiqiang, Su Feng, Chen Jibing, el at. A highly efficient global vectorization method for line drawings [C]//Proceedings of the 3rd LAPR International Workshop on Graphic Recognition(GREC’99), 1999: 32-37.

[51]Song Jiqiang, Su Feng, Tai C L, el at. Line net global vectorization: an algorithm and its performance evaluation [C]//Proceedings of IEEE Conference on Computer Vision and Pattern Recognition(CVPR’00), South Carolina U.S.A., 2000, 1:383-388.

[52]Seong D S, Choi Y K, Park K H. An algorithm for optimal isomorphism between two random graphs [J].Pattern Recognition Letters, 1994, 15: 321-327.

[53]Lladós J, Martí E, Villanueva J. Symbol recognition by error-tolerant subgraph matching between region adjacency graphs [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2001, 23(10):1137-1143.

[54]Fahmy H, Blonstein D. A graph grammar programing style for recognition of music notation [J].Machine Vision and Applications, 1993, (6): 83-99.

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

[56]Ahsoon C, Tombre K. Architectural symbol recognition using a network of constraints [J].Pattern Recognition Letters, 2001, 22: 231-248.

[57]Belongie S, Malik J, Puzicha J. Shape matching and object recognition using shape contexts [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2002, 24(24): 509-522.

[58]Tombre K, Haralick R M, Dori D. Understanding engineering drawings: a survey [C]//Proceedings of First IAPR Workshop on Graphic Recognition,University Park, P.A, 1995: 217-228.

[59]Tombre K. Analysis of engineering drawings: state of the art and challenges [C]//LNCS, 1998, 1389:257-264.

[60]Joseph S H, Pridmore T P. Konwledge-directed interpretation of mechanical engineering drawings [J].IEEE Transactions on Pattern Analysis and Machine Intelligence, 1992, 14(9): 928-940.

[61]楊若瑜, 胡 笳, 蔡士杰. 工程圖對象識別規則自動獲取方法的研究[J]. 計算機學報, 2003, 26(10):1234-1240.

[62]Bimber O, Encarnao L M, Stork A. A multi-layered arthiecture for sketch-based interaction within virtual environments [J]. Computer & Graphics, 2000, 2(6):851-867.

[63]Caetano A, Goulart N, Fonseca M, el at. Javasketchit:issues in sketching the look of user interfaces [C]//Proceedings of AAAI Spring Symposium on Sketch Understanding, Palo Alto, CA, 2002: 9-14.

[64]Lu Tong, Tai C L, Su Feng, el at. A new recognition model for electronic architectural drawings [J].Computer-Aided Design, 2005, 37(10): 1053-1069.

[65]路 通, 楊若瑜, 楊華飛, 等. 三維結構構件漸進式整合與重組方法[J]. 計算機輔助設計與圖形學學報, 2007, 19(4): 491-495.

[66]高 瑋, 彭群生. 基于二維視圖特征的三維重建[J].計算機學報, 1999, 22(5): 481-485.

[67]Chen Kezhang, Zhang Xiwen, Ou Zongying, el at.Holo-extraction of information from paper drawings for 3D reconstruction [J]. Computer-Aided Design,2002, 34(9): 665-677.

[68]蔡士杰, 徐福培, 高 曉. 計算機讀圖與數字建筑[J].系統仿真學報, 2002, 14(12): 1652-1654.

[69]Kong B, Phillips I T, Haralick R M, el at. A benchmark: performance evaluation of dashed-line detection algorithms [C]//Lecture Notes in Computer Science, 1996, 1072: 270-285.

[70]Hori O, Doermann D S. Quantitative measurement of the performance of raster-to-vector conversion algorithms [C]//Lecture Notes in Computer Science,1996, 1072: 57-68.

[71]Phillips I T, Chhabra A K. Empirical performance evaluation of graphics recognition systems [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1999, 21(9): 849-870.

[72]Liu Wenyin, Dov D. A protocol for performance evaluation of line detection algorithms [J]. Machine Vision and Applications, 1997, 9: 240-250.

[73]Jaisimha M Y, Dori D, Haralick R. A methodology for the characterization of the performance of thinning algorithms [C]//Proceedings of International Conference on Document Analysis and Recognition,Tsukuba, Japan, 1993: 282-286.

[74]Wang Yalin, Phillips I T, Haralick R M. Table structure understanding and its performance evaluation [J]. Patter Recognition, 2004, 37(7):1479-1497.

[75]Bodansky E, Pilouk M. Using local deviations of vectorization to enhance the performance of raster-to-vector conversion systems [J]. International Journal on Document Analysis and Recognition,2000, 3(2): 67-72.

[76]Chhabra A K, Phillips I T. The second international graphics recognition contest-raster to vector conversion: a report [C]//Lecture Notes in Computer Science, 1998, 1389: 1390-1410.

[77]http://www.iupr.org/arcseg2005

[78]http://www.iupr.org/arcseg2007