一種基于形狀分布的工程圖形整體相似性檢索方法

王 鵬 ，姜壽山

(西北工業大學 機電學院，西安 710072)

0 引言

近幾十年來，隨著計算機技術的迅速發展，現代CAD系統提供強大的工具創建和編輯工程圖，如AutoCAD、UG、CATIA。雖然在工程圖應用領域重用過去的工程圖已經成為一種慣例，但是在當前CAD系統中并沒有提供相應的自動檢索機制。據資料估計，在產品開發中約有80%的設計為變形設計和自適應設計，其中約有40%是重用過去的部件設計，40%對已有部件稍作修改，而全新的設計僅占20%[1]。由此可知，已有的工程圖資料是企業進行新產品設計和開發的重要依據和基礎，準確地檢索出工程圖信息對于進行新產品的設計具有重要的意義。

圖形形狀的相似性比較是模式識別與圖形檢索領域的主要研究內容，目前有多種圖形形狀的相似性比較算法。常用的輪廓描述子是傅里葉描述子(Fourier descriptor, FD)[2]，傅里葉描述子具有選擇和比例不變性的特點，用于描述工程圖形的外輪廓。Legendre[3]描述子是正交描述子，具有比例不變性的優點，但是其不具有圖形旋轉不變性。形狀分布算法是由Osada[4,5]等率先提出，主要用于三維模型的形狀特征提取，可以很好的描述三維形狀的幾何特征，而二維形狀可以看作是三維形狀在二維空間中的投影，那么通過改進三維形狀分布方法，可以設計出一種二維形狀分布算法，其必然能夠很好地描述二維形狀的幾何特征。基于上述思想，本文提出了一種基于形狀分布的工程圖形整體相似性檢索方法。

1 基于形狀分布的工程圖整體相似性檢索方法總體思路

工程圖形整體相似性檢索與2D圖形形狀識別相對應。本文定義工程圖形整體相似性檢索為：給定一個工程圖A和一個工程圖庫L={Bi|0≤i≤n}，如何計算工程圖A與Bi之間的相似性，即D(A,Bi)，并且找到最相似的k個工程圖。在檢索過程中，尋找一個合適的圖形形狀描述符是工程圖整體相似性檢索效果的關鍵。本文從統計學角度提出通過從工程圖圖形上采集采樣點的形狀分布算法，其總體思路如圖 1所示。

圖1 工程圖整體相似性檢索算法整體思路

2 形狀分布算法主要步驟

2.1 選擇形狀分布函數

選擇形狀函數的目的是提取二維圖形的形狀信號，理想的形狀函數所提取的形狀信號具有變換不變性，即相同的工程圖圖形對旋轉、平移和縮放等變換具有相同的形狀信號。本文選用D[4,5]2形狀分布函數，其分布曲線是一些規范化的形狀，如圖2所示。通常，不同的圖形對應的分布是不一樣的，且連續改變的工程圖圖形對D2分布的影響是連續的。

2.2 計算統計數據

在設計好形狀函數之后計算統計數據。一般來講，給定一個圖形，隨機計算圖形上任意兩點的距離的復雜度非常大，根據統計理論，可以通過隨機采樣來解決。而要實施隨機采樣，就必須解決三個關鍵問題：一是如何對圖形進行表示才能設計出合理的隨機采樣方法；二是如何設計合理的隨機采樣方法；三是隨機采樣多少個數據點才能充分反映圖形的形狀特征，而且計算量在可接受的范圍內。下面給出上述三個問題的解決方法。

1）工程圖形的離散化表示

一個工程圖形由一些基本的幾何元素組成，如線段、圓弧、圓、樣條曲線等。為了更好更有效的對工程圖形進行數據點采樣，本文將工程圖形離散化為由一系列線段組成的集合。對于圓弧、圓、樣條曲線由一系列線段去近似。這樣一個工程圖形可以表示為：

S= {((xi, yi),(xi+1,yi+1))|0≤i≤n-1}

其中n為S中線段的個數，(xi, yi)與(xi+1,yi+1)分別為線段的起點與終點。

2）數據點的隨機采樣方法

合理的隨機采樣方法不僅能夠反映圖形的總體形狀特征，還要充分體現圖形局部的細節特征。為此，本文設計了一種基于查表算法的數據點采樣方法，該方法基于圖形的離散化表示，其詳細步驟如下：

1）計算二維工程圖形S中所有線段的總長度。每相加一個線段，就將該長度存入表T中，其大小為n，其中圖形線段的個數為n-1，則表T可以表示為一個線性數組，如式(1)所示。

其中L表示兩個點之間的歐氏距離。

2）隨機產生一個實數r(0≤r≤tn-1)；然后采用著名的二分法查找法找到值r在表T中的位置，該位置記為((xm,ym),(xm+1,ym+1))。

3）隨機產生一個實數l(0≤l≤1)，根據式(2)，可以獲得一個采樣數據點(xk,yk)，并且將其存入數據點采樣向量A。

4）重復執行2）與3）2N次獲得N個無偏數據采樣點對。

從統計學理論角度來講，采樣點的數量越多，就越能反映三視圖的形狀特征。但是采樣點越多，則計算量越大，需要的計算時間就越長，效率越低。因此，二者是矛盾的，必須尋找一個平衡點，即采樣點的數目既能充分反映圖形的形狀特征，又能將計算量控制在可接受的范圍內。

為了獲取該平衡點，選取不同數目的采樣點進行實驗，實驗結果如圖3所示，其中橫坐標代表采樣點的數目，縱坐標代表采樣過程所需時間或不同數目的采樣點描述圖形形狀的準確度。從圖3可以看出，當采樣點數目為103個時，即N=103效果比較好，即此時不僅能夠充分反映圖形的準確度，而且采樣過程所需時間又在可接受的范圍內。

圖3 采樣過程效率與準確度實驗測試結果

2.3 構造形狀分布曲線

本文采用統計理論對隨機信號進行參數化，并且對隨機點對之間的距離值進行統計，生成一個形狀直方圖。對于不同大小的工程圖形，其距離值跨度很大，因此需要對形狀分布直方圖的尺度進行歸一化。本文以D2距離的平均值的1/50作為區間長度，統計落在第i個區間的點對距離數量為Ni，以i的值作為橫軸，縱軸可以表示為100×Ni/499500，由此構建形狀直方圖，如圖4（a）所示，通過對形狀直方圖的擬合形成形狀分布曲線圖，如圖4（b）所示。隨機信號參數化的結果即把工程圖形的形狀信號參數化成為一個形狀分布直方圖(離散的)或形狀分布曲線圖(連續的)。

2.4 相似性度量

通過計算工程圖形上任意兩點之間的距離并進行統計，工程圖形的形狀特征被映射成為一個形狀分布曲線，這樣，工程圖形之間的相似性比較就可以轉化為形狀分布曲線之間的距離度量。距離越大，工程圖形之間的差別就越大，反義亦然。兩個分布之間的距離包括Minkowski距離、x2統計距離、二次距離等，本文采用EMD距離。

EMD距離是一種有效且正在被越來越廣泛使用的集合間或向量間距離計算方式[6]。它能只通過一次線性規劃計算出兩個具有不等(或相等)權值分布的不同(或相同)大小的集合或向量的距離。該算法產生于物理學，線性規劃中的運輸問題可作為其具體求解算法。

形象的解釋EMD距離算法就是：空間S中分布著M堆土Pi，i=1,…,M，每堆土的質量為wpi，同時分布有N個土坑Qi，i=1,…,N，每個坑可以裝土的質量為wqi。把所有土填到這些坑內，做的功表示為：

其中d(Pi,Qj)表示第i堆土到第j個坑的距離，稱其為基本距離或單位代價。fij表示從第i堆土到第j個坑的土的質量。d(Pi,Qj)fij表示把第i堆土中質量為fij的土運到第j個坑所做的功。式(3)滿足如下約束：

約束1說明，每次搬運的質量大于零時才做功。約束2說明，從第i堆土運到各個坑的土的質量總和，一定不會大于該堆土的質量。約束3說明從各堆土運到第j個坑的土的質量總和，一定不會大于該坑所能容納的土的質量。

從上述定義，不難把工程圖形的相似性度量問題轉化為EMD距離計算問題。當測量兩個工程圖形的距離時，把其中一個工程圖形的形狀分布分量映射成土堆，另一個工程圖形的形狀分布分量映射成土坑，則兩個工程圖形之間的距離，就是把所有的土填入坑內，在選擇最佳路徑的情況下，做功的最小值。因此，兩個工程圖形形狀分布的EMD距離定義為：

式(4)的分母是歸一化因子。分子同線性規劃中運輸問題的目標函數完全一致，約束條件也可以轉換為運輸問題的約束條件的標準形式，因此可以很方便地應用運輸問題的標準算法求解。

3 實例驗證與討論

為了驗證本文所提出的基于形狀分布的工程圖形整體相似性檢索方法的有效性，我們構建了一個工程圖庫，該工程圖庫包括軸類、盤類、箱體類等各類零件模型共300個，工程圖形的數據格式統一采用DXF標準格式，以Microsoft Visual Studio 2008為集成開發環境驗證本文算法。基于該模型庫，我們進行了如下兩個方面的實驗。

實驗1：形狀分布算法實例分析。給定一個圖形，從工程圖庫中檢索出與其最相似的5個圖形，其結果如表 1所示。從表 1可以看出，本文方法能夠實現工程圖形的整體相似性檢索，能夠檢索出所有與檢索圖形整體相似的圖形(共4個)，與人的相似性感知結論相同。優于文獻[2][7]中的方法。

圖5 工程圖形整體相似性檢索算法檢索性能曲線比較

4 結束語

本文提出了一種基于形狀分布的工程圖形整體相似性檢索方法，并將其應用到工程圖模型的相似性評價中。該方法首先對工程圖形進行無偏采樣，將一個工程圖形表達為一個形狀分布曲線，將工程圖形的整體相似性匹配問題轉化為兩個工程圖模型的形狀分布曲線比較問題，然后采用EMD距離計算出兩個圖形間的相似性。實驗結果顯示，本文算法能夠實現工程圖形的整體相似性檢索，并且形狀分布算法檢索性能優于文獻[2][7]所提出的方法。

表1 基于形狀分布的工程圖形整體相似性檢索算法實例

實驗2： 工程圖整體相似性檢索算法檢索性能比較.為了驗證本文算法的檢索性能，將本文方法與文獻[2][7]方法進行比較，其中“D2”代表本文的D2形狀分布算法，“Fourier”代表文獻[2]中提出的基于傅里葉描述子的工程圖整體相似性檢索算法，“Hough transform”代表文獻[7]中提出的方法。圖5繪制了三種方法的查全率—查準率曲線(PR曲線)，從圖5可以看出，本文提出的基于形狀分布的工程圖形整體相似性檢索方法的檢索性能

在下一階段研究中，我們將對工程圖模型構建索引描述子，依據索引描述子對模型進行分類，在此基礎上進一步改進本文算法，提高檢索效率；將本文算法與工程語義相結合，不但利用工程圖的空間關系和幾何信息，而且利用工程圖所包含的語義信息，使其更有利于設計人員設計新產品。

[1] 王玉,刑淵,阮雪榆.機械產品設計重用策略研究[J].機械工程學報,2002,38(5):145～148.

[2] Tabbone S,Wending L,Tombre K.Matching of graphical symbols in line-drawing images using angular signature information [J].Int J Doc Anal Recog,2003,6(2):115-125.

[3] Yun G E,Shu H Z,Luo L M.A new way of linear registration using the legendre orthogonal moment and application in 2-value image data [J].Acta Electronica Sinica,2001,29(1):54-56.

[4] Osada R,Funkhouser T,Chazelle B, Dobkin D.Shape distribution[J].ACM Trans Graph,2002,21(4):807-832.

[5] Osada R,Funkhouser T,Chazelle B,er al.Matching 3d Models with Shape Distributions[C]//International Conference on Shape Modeling and Applications.Geneba:IEEE Computer Society Press,2001:154-166.

[6] Y.Rubner,C.Tomasi,L.J.Guibas,The earth mover's distance as a metric for image retrieval[J].International Journal of Computer Vision,2000,40(2):99-121.

[7] Franti P,Mednonogov A,Kykri V,et al.Conten-based matching of line-drawing images using the hough transform [J].Int J Doc Anal Recog,2000,3(3):117-124.