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

王 鵬 ，姜壽山

(西北工業(yè)大學(xué) 機電學(xué)院，西安 710072)

0 引言

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

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

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

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

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

2 形狀分布算法主要步驟

2.1 選擇形狀分布函數(shù)

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

2.2 計算統(tǒng)計數(shù)據(jù)

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

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

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

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

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

2）數(shù)據(jù)點的隨機采樣方法

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

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

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

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

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

4）重復(fù)執(zhí)行2）與3）2N次獲得N個無偏數(shù)據(jù)采樣點對。

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

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

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

2.3 構(gòu)造形狀分布曲線

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

2.4 相似性度量

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

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

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

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

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

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

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

3 實例驗證與討論

為了驗證本文所提出的基于形狀分布的工程圖形整體相似性檢索方法的有效性，我們構(gòu)建了一個工程圖庫，該工程圖庫包括軸類、盤類、箱體類等各類零件模型共300個，工程圖形的數(shù)據(jù)格式統(tǒng)一采用DXF標準格式，以Microsoft Visual Studio 2008為集成開發(fā)環(huán)境驗證本文算法?；谠撃Ｐ蛶欤覀冞M行了如下兩個方面的實驗。

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

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

4 結(jié)束語

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

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

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

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

[1] 王玉,刑淵,阮雪榆.機械產(chǎn)品設(shè)計重用策略研究[J].機械工程學(xué)報,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.