一種距離特征融合的機(jī)械三維模型檢索方法

楊 巖，張 紅，何 苗，路世青

（重慶理工大學(xué)機(jī)械工程學(xué)院，重慶 400054）

1 引言

隨著三維CAD 技術(shù)及數(shù)字化設(shè)計(jì)技術(shù)的發(fā)展，三維模型已經(jīng)在機(jī)械設(shè)計(jì)、動(dòng)畫設(shè)計(jì)及分子生物學(xué)等領(lǐng)域得到了廣泛的應(yīng)用。統(tǒng)計(jì)分析表明，在現(xiàn)代工業(yè)產(chǎn)品的設(shè)計(jì)中，約40%是重用過(guò)去的設(shè)計(jì)，約40%是對(duì)已有設(shè)計(jì)的微小修改，只有約20%是完全新的設(shè)計(jì)[1]。所以，在新產(chǎn)品研制過(guò)程中，快速準(zhǔn)確地找到與設(shè)計(jì)需求相似的已有模型并加以重用，是提高機(jī)械設(shè)計(jì)效率、縮短產(chǎn)品開發(fā)周期的關(guān)鍵之一。針對(duì)三維模型檢索，文獻(xiàn)[2]提出了D2 形狀算子，其通過(guò)計(jì)算任意點(diǎn)對(duì)間的歐式距離，并構(gòu)建形狀直方圖來(lái)描述模型的特征，以此進(jìn)行模型匹配。文獻(xiàn)[3]采用模型表面頂點(diǎn)關(guān)聯(lián)的三角形面積構(gòu)造了面積序列，然后對(duì)其進(jìn)行歸一化操作和傅里葉變換等處理，最終得到面積分布算子，取得了較好的檢索效果。文獻(xiàn)[4]提出了一種基于曲度特征的三維模型檢索算法，可同時(shí)克服平均曲率對(duì)平滑模型的不敏感性和高斯曲率分布較均勻的缺點(diǎn)，能夠更真實(shí)地反映三維模型的局部彎曲程度，非常適用于曲面模型的特征描述，但不能直接用于機(jī)械零件的檢索。文獻(xiàn)[5]采用準(zhǔn)隨機(jī)數(shù)發(fā)生器產(chǎn)生隨機(jī)數(shù)，計(jì)算任意兩點(diǎn)有向線段距離及所在面面積之間的比值，同時(shí)以距離、面積比為坐標(biāo)軸構(gòu)建網(wǎng)格坐標(biāo)系，統(tǒng)計(jì)出現(xiàn)在相應(yīng)網(wǎng)格中特征點(diǎn)的頻次，形成距離-面積特征分布矩陣，算法在應(yīng)用于農(nóng)機(jī)CAD 模型時(shí)，得到了較好的檢索性能。文獻(xiàn)[6]提出一種局部匹配方法，首先選取零件已有的典型結(jié)構(gòu)，然后通過(guò)典型結(jié)構(gòu)的面之間的拓?fù)潢P(guān)系進(jìn)行檢索。

提出一種結(jié)合D2 距離與協(xié)方差距離的三維模型檢索方法，對(duì)三維模型的特征描述更充分。不僅能有效提高檢索效率，同時(shí)對(duì)噪聲、采樣密度的變化也具有較好的魯棒性，在對(duì)機(jī)械三維模型檢索時(shí)取得較好的效果。

2 算法原理

協(xié)方差描述子[7]可以看作是一種對(duì)點(diǎn)的領(lǐng)域信息的抽象表示，它將代表不同特征的信息融合作為聯(lián)合分布的采樣，弱化了領(lǐng)域點(diǎn)的空間分布信息，且具有旋轉(zhuǎn)、平移和縮放不變的特征，相比直方圖描述子更具魯棒性。

首先采用蒙特卡洛算法在三維模型表面隨機(jī)取點(diǎn)，計(jì)算隨機(jī)點(diǎn)對(duì)的D2 距離和協(xié)方差距離。然后對(duì)D2 距離和協(xié)方差距離進(jìn)行聯(lián)合統(tǒng)計(jì)，形成距離分布矩陣，以此矩陣作為模型的特征描述符。算法的實(shí)現(xiàn)步驟如下：（1）隨機(jī)取點(diǎn)：在模型表面生成隨機(jī)采樣點(diǎn)。（2）計(jì)算特征距離：首先計(jì)算所有隨機(jī)點(diǎn)的D2 距離，然后計(jì)算隨機(jī)點(diǎn)對(duì)間的協(xié)方差矩陣，并得到協(xié)方差距離。（3）構(gòu)建距離分布矩陣：以隨機(jī)點(diǎn)對(duì)D2 距離為x 軸，協(xié)方差距離為y 軸構(gòu)建一平面網(wǎng)格，統(tǒng)計(jì)網(wǎng)格中距離出現(xiàn)的頻次，從而得到一個(gè)m×n 的特征矩陣。（4）模型相似性評(píng)價(jià)：采用曼哈頓距離評(píng)估模型之間的相似性。

3 算法實(shí)現(xiàn)

3.1 模型表面隨機(jī)取點(diǎn)

采用文獻(xiàn)[2]提出的蒙特卡洛方法進(jìn)行隨機(jī)取點(diǎn)，以模型表面三角形面片的面積大小為依據(jù)。首先，定義一個(gè)三角形面片Ti，利用海倫公式計(jì)算三角形面片的面積Si。

式中：qi（qi=（ai+bi+ci）/2）—三角形周長(zhǎng)的一半。將所有三角形面片面積相加得到模型表面積S，則隨機(jī)選取三角面片Ti的概率可表示為：

把［0，1］區(qū)間等分成k 段，其中，第i 段的長(zhǎng)度與P（Ti）在數(shù)字上是相等的，第j 個(gè)節(jié)點(diǎn)數(shù)值為前（j-1）個(gè)三角形面片的和，只要在［0，1］之間生成一個(gè)隨機(jī)數(shù)，即能找到三角形面片的索引號(hào)i，如圖1 所示。

圖1 三角形選取示意圖Fig.1 The Diagram of Triangle Selection

隨機(jī)點(diǎn)的位置將從上述選取的三角形中生成，方法是隨機(jī)生成2 個(gè)介于［0，1］區(qū)間的數(shù)字 r1和 r2，隨機(jī)點(diǎn) p 的位置可表示為：

3.2 協(xié)方差距離及D2 距離計(jì)算

采用基于模型三角網(wǎng)格信息來(lái)提取特征，所以忽略模型顏色屬性、材料屬性等特征。根據(jù)文獻(xiàn)[7]，協(xié)方差描述子可定義為隨機(jī)變量從點(diǎn)云中提取出的一些列幾何特征。文中只考慮三個(gè)角度特征，這樣可以大大減小計(jì)算量，且具有平移、縮放和旋轉(zhuǎn)不變性。建立協(xié)方差描述子的第一步是建立特征向量φ。

φ=（P1，P2，…，Pm-1，Pm）表示三角形 ABC 鄰接三角形的中心點(diǎn)集合，α 是隨機(jī)點(diǎn) P 法向量 n 和的夾角，它表示以P 點(diǎn)為中心的局部凹凸?fàn)顩r，如圖2 所示。β 表示Pi點(diǎn)的法向量和的夾角，它可衡量P 點(diǎn)領(lǐng)域內(nèi)的局部曲率。γ 是P 點(diǎn)的法向量和Pi點(diǎn)法向量的夾角，作為一個(gè)3D 的空間角，它以一種非模糊的方式表示了局部曲面信息。隨機(jī)點(diǎn)所在位置的局部特征將用這三個(gè)角度進(jìn)行表征。

圖2 協(xié)方差矩陣計(jì)算Fig.2 Calculation of Covariance Matrix

它們分別可用如下公式進(jìn)行計(jì)算：

因此，隨機(jī)點(diǎn)P 的協(xié)方差描述矩陣可表示為：

式中：up—三角形ABC 所有鄰接三角形特征向量φ 的平均值；m—ABC 鄰接三角形的個(gè)數(shù)。C（P）—一個(gè)3×3 的正定矩陣，它的對(duì)角線元素表示的是每個(gè)特征分布的變化，而非對(duì)角線上的元素表示兩兩特征的相互關(guān)聯(lián)特性。這樣，每個(gè)隨機(jī)點(diǎn)處的局部特征都由一個(gè)協(xié)方差矩陣來(lái)表示，而兩個(gè)隨機(jī)點(diǎn)的協(xié)方差矩陣之間的距離即為兩點(diǎn)的協(xié)方差距離，它可表示兩點(diǎn)局部特征的相似性。文中采用曼哈頓距離來(lái)計(jì)算矩陣的距離。D2 距離采用文獻(xiàn)[2]中方法進(jìn)行計(jì)算，該方法較為簡(jiǎn)單，故此處不再贅述。設(shè)模型的任意兩個(gè)隨機(jī)點(diǎn) pA=（xA，yA，zA），pB=（xB，yB，zB） 對(duì)應(yīng)的協(xié)方差矩陣分別為mA和mB，則D2 距離d 和協(xié)方差距離D 可表示為：

3.3 距離分布矩陣計(jì)算

以D2 距離為x 軸，協(xié)方差距離為y 軸統(tǒng)計(jì)兩種距離特征的概率分布，以形成距離分布矩陣。具體步驟如下：

（1）將D2 距離和協(xié)方差距離區(qū)間分別劃分為n1和n2等分，節(jié)點(diǎn)處的值分別為 di、Di。

（2）當(dāng) D2 距離和協(xié)方差距離同時(shí)滿足 dk≤di≤dk+1，Dm≤Di≤Dm+1時(shí)，網(wǎng)格平面所對(duì)應(yīng)的小方格加1，由此可以統(tǒng)計(jì)出D2 距離和協(xié)方差距離的概率分布。

（3）利用一個(gè)n1×n2的矩陣M 來(lái)表示上述網(wǎng)格，從而將三維模型特征用距離分布矩陣M 來(lái)表示。

3.4 模型的相似性度量

歐式距離和Manhattan 距離是兩種常用的相似性度量方法，都具有計(jì)算簡(jiǎn)單、易實(shí)現(xiàn)的優(yōu)點(diǎn)，但歐式距離在計(jì)算中沒有充分考慮到各個(gè)分量之間的相關(guān)性，區(qū)分能力不足。所以文中采用Manhattan 距離來(lái)評(píng)價(jià)兩個(gè)模型之間的差異性。Manhattan 距離是兩個(gè)特征向量對(duì)應(yīng)分量差值的絕對(duì)值求和。設(shè)三維模型A 與B的距離分布矩陣分別為MA和MB，則模型A 和模型B 的相似性度量函數(shù)為：

3.5 檢索性能的評(píng)價(jià)

采用查全率-準(zhǔn)確率曲線來(lái)評(píng)價(jià)算法檢索性能，具體描述為：設(shè)查詢模型為q，模型庫(kù)Q 中與q 相似的模型數(shù)量為S，在Q中檢索q 得到的檢索結(jié)果集合為M，M 中與q 相似的三維模型數(shù)量為N，則查全率、準(zhǔn)確率計(jì)算如下：

對(duì)于一個(gè)給定的查詢模型，其查準(zhǔn)率與返回的模型數(shù)量成反比關(guān)系，查全率與返回的模型數(shù)量成正比關(guān)系，查準(zhǔn)率會(huì)隨著查全率的增大而減小。所以查準(zhǔn)率-查全率曲線是一條逐漸下降的曲線。在理想的情況下，查準(zhǔn)率-查全率曲線應(yīng)該為一條值為1的水平線。

4 實(shí)例檢索與結(jié)果分析

為驗(yàn)證算法的有效性，采用普渡大學(xué)工程標(biāo)準(zhǔn)模型庫(kù)ESB（Engineering Shape Benchmark）中的部分零件和來(lái)自微耕機(jī)傳動(dòng)機(jī)構(gòu)中的部分零件作為檢索對(duì)象，共計(jì)160 個(gè)三維模型，模型格式為OFF。實(shí)驗(yàn)平臺(tái)為：IntelCorei3-3220CPU@3.3GHz。文中以代表性較強(qiáng)的齒輪類、軸類、端蓋類零件作為實(shí)例檢索對(duì)象，設(shè)置隨機(jī)點(diǎn)個(gè)數(shù)為500 個(gè)，然后分別采用D2 距離算法[2]、直方圖算法[8]、距離夾角形狀分布算法[9]、算法進(jìn)行實(shí)驗(yàn)，并按模型相似性從大到小順序返回前9 個(gè)模型。實(shí)例檢索結(jié)果，如圖3 所示。查準(zhǔn)率-查全率曲線，如圖4 所示。不同算法平均時(shí)間，如表1 所示。

圖3 不同檢索算法的結(jié)果Fig.3 The Results of Different Retrieval Methods

圖4 查準(zhǔn)率-查全率曲線圖Fig.4 Precision-Recall Graph

表1 不同算法平均時(shí)間（ms）Tab.1 Mean Time of Different Methods（ms）

從檢索結(jié)果不難看出，算法性能明顯優(yōu)于文獻(xiàn)[2、8]中算法，特別是檢索軸類零件時(shí)，文獻(xiàn)[8]算法檢索結(jié)果中僅僅只有一個(gè)是正確的。從形狀上看，齒輪零件與軸類零件相差很大，但由于其空間點(diǎn)云分布相近，所以會(huì)被判定為同一類。這也顯露出單一特征對(duì)模型形狀描述不足的缺點(diǎn)。文獻(xiàn)[9]和文中算法都采用了特征融合的方法，效果明顯好于文獻(xiàn)[2、8]。對(duì)于文獻(xiàn)[9]中算法，雖然在檢索效果上略優(yōu)于文中算法，但相差并不大，另外，從算法平均時(shí)間上看，文中算法較文獻(xiàn)[9]算法快了接近0.1s，0.1s 雖然對(duì)于只有160個(gè)模型的小型數(shù)據(jù)庫(kù)來(lái)說(shuō)很少，但當(dāng)應(yīng)用于大型模型庫(kù)檢索時(shí)，則可大大減少算法時(shí)間。所以，綜合考慮查準(zhǔn)率-查全率曲線和算法平均時(shí)間，文中算法較其它三種算法具有更好的檢索性能。從全局特征和局部特征的思路出發(fā)，綜合考慮D2 距離特征和協(xié)方差距離特征，避免了單一特征對(duì)模型特征描述不全的問(wèn)題，提高了三維模型檢索效率。

（1）采用的協(xié)方差距離特征同時(shí)考慮了隨機(jī)點(diǎn)處的局部凹凸?fàn)顩r和局部曲率狀況，對(duì)模型局部特征具有更好的描述能力，另外，協(xié)方差矩陣只受局部向量夾角的影響，而與模型的姿態(tài)無(wú)關(guān)，所以它還具有平移、旋轉(zhuǎn)和縮放不變性。（2）D2 距離算法僅通過(guò)隨機(jī)點(diǎn)間的距離來(lái)表征模型，無(wú)法全面的描述模型特征。這里在D2 距離算法的基礎(chǔ)上引入了協(xié)方差距離描述符，可同時(shí)從全局特征和局部特征兩方面對(duì)三維模型進(jìn)行描述，避免了單一特征對(duì)模型特征描述不全面的問(wèn)題，從而提高檢索效率。實(shí)驗(yàn)表明，這里算法在時(shí)間和性能都能較好的滿足檢索需求，可適用于機(jī)械零件三維模型的在線實(shí)時(shí)檢索。綜上所述，這里算法一定程度上提高了機(jī)械三維模型檢索的綜合性能，對(duì)三維模型在線實(shí)時(shí)檢索具有一定的參考意義。