基于極半徑曲面矩和HMM的三維模型分類與檢索算法

王洪申，劉 敏，強(qiáng)會英

（1.蘭州理工大學(xué)機(jī)電工程學(xué)院，甘肅蘭州730050；2.蘭州交通大學(xué)數(shù)理與軟件學(xué)院，甘肅蘭州730070）

隨著計(jì)算機(jī)輔助設(shè)計(jì)（computer aided design，CAD）技術(shù)的發(fā)展和應(yīng)用，企業(yè)積累了大量工程數(shù)據(jù)。工程數(shù)據(jù)中蘊(yùn)含著豐富的專業(yè)知識，如何處理和分析這些工程數(shù)據(jù)并從中提煉出可重用的信息是一個(gè)亟待解決的問題。三維CAD 模型作為機(jī)械設(shè)計(jì)的產(chǎn)物，其數(shù)量巨大，這些三維CAD 模型中蘊(yùn)含著大量可重用的設(shè)計(jì)信息。為了能有效地利用這些信息，須對三維CAD模型的分類與檢索方法進(jìn)行研究，且提高檢索的準(zhǔn)確率和效率是關(guān)鍵。

不變矩是分類問題中重要而有效的特征量［1］，利用不變矩來提取三維模型的特征既簡單又快速。但是，在目前關(guān)于不變矩的研究中，大多采用Hu 不變矩［2］、Zernike 矩［3］和仿射不變矩［4-5］等圖像不變矩來提取三維模型的特征，使用時(shí)必須先將三維模型轉(zhuǎn)化為二維圖像，再利用圖像不變矩來提取特征，這可能會導(dǎo)致三維模型的特征信息丟失并引入新的干擾信息。例如：曹茂永等［6］采用極半徑不變矩對二維圖像的形狀進(jìn)行識別；李宗民等［7-8］提出了極半徑曲面矩，通過實(shí)驗(yàn)驗(yàn)證了其平移、縮放和旋轉(zhuǎn)不變性，并利用極半徑曲面矩評價(jià)了三維模型的相似性。研究表明，極半徑曲面矩能有效提取三維模型的幾何特征，避免了三維向二維的轉(zhuǎn)換過程，基于極半徑曲面矩的分類與檢索方法可穩(wěn)定、可靠地識別并區(qū)分三維模型的形狀差異，從而保證三維模型分類與檢索的準(zhǔn)確性。

隱馬爾可夫模型（hidden Markov model，HMM）［9］是一種可用于標(biāo)注問題的統(tǒng)計(jì)分析模型，具有很強(qiáng)的學(xué)習(xí)能力和模式分類能力。HMM 描述的是一個(gè)含有隱含未知參數(shù)的馬爾可夫過程，其狀態(tài)不能直接被觀察到，但可通過觀測隨機(jī)序列觀察到，其中每個(gè)觀測序列是由1個(gè)具有相應(yīng)概率密度分布的狀態(tài)序列產(chǎn)生的。HMM 可被視為一個(gè)具有雙重隨機(jī)過程的有限狀態(tài)自動(dòng)機(jī)，其每個(gè)狀態(tài)都代表一個(gè)可觀察的事件，狀態(tài)之間的轉(zhuǎn)換都可以用一定的概率來表示［10］。目前，HMM 已成功應(yīng)用于語音識別、行為識別、文字識別以及故障診斷等［11］。三維模型分類的目標(biāo)是將未標(biāo)注的三維模型劃分到某個(gè)預(yù)設(shè)的模型類別中［12］。但對于數(shù)量龐大的三維模型來說，利用人工標(biāo)注來分類是不可取的，而HMM 可有效解決該問題。

基于此，筆者擬采用極半徑曲面矩和HMM 來實(shí)現(xiàn)機(jī)械零件三維模型的分類與檢索。首先，通過計(jì)算極半徑曲面矩來提取三維模型的特征，并將排序編碼后的特征向量作為HMM 的觀測序列；然后，選取部分人工標(biāo)注過的三維模型作為訓(xùn)練樣本，采用添加比例因子的多觀測序列B-W（Baum-Welch）算法對HMM 進(jìn)行訓(xùn)練；最后，利用訓(xùn)練好的HMM對三維模型進(jìn)行分類與檢索。

1 基于極半徑曲面矩與HMM 的三維模型分類與檢索算法的原理

1.1 三維模型的特征提取

極半徑曲面矩是一種具有平移、縮放和旋轉(zhuǎn)不變性的不變量，其既可作為由連續(xù)區(qū)域構(gòu)成的三維模型的特征量，也可作為由分離區(qū)域組成的三維模型的特征量［8］。極半徑曲面矩的形式簡潔，可直接通過讀取三維模型表面的網(wǎng)格數(shù)據(jù)來計(jì)算，而不用對三維模型進(jìn)行體素化處理。

對于由三角面片構(gòu)成的三維模型，用D表示其表面區(qū)域，A表示其表面積，(xc，yc，zc)表示其形心的坐標(biāo)，r表示三角面片上的點(diǎn)到形心的距離，r=，則該三維模型的第p階極半徑曲面矩mp和極半徑曲面中心矩mcp為：

式中：ds為積分區(qū)域的微元；為極半徑平均值，。

歸一化后第p階極半徑曲面矩和極半徑曲面中心矩為：

用離散形式表示歸一化后的第p階極半徑曲面矩和極半徑曲面中心矩，為：

以STL（stereolithography，立體光刻）格式的三維模型文件為例，基于遍歷獲取的三維模型表面網(wǎng)格數(shù)據(jù)，通過計(jì)算得到由極半徑曲面矩和極半徑曲面中心矩組成的組合不變矩，并將其作為模型的特征向量。通過試驗(yàn)發(fā)現(xiàn)，偶數(shù)階的極半徑曲面矩的區(qū)分度較好，同時(shí)為了減小計(jì)算量，選取第4，6，8，10 和12 階極半徑曲面矩以及第2，4，6，8 和10 階極半徑曲面中心矩組成十維組合不變矩(m4，m6，…，m12，mc2，mc4，…，mc10)。

提取了三維模型的特征后，采用排序編碼的方式將組合不變矩轉(zhuǎn)換為HMM 的輸入觀測序列。具體方法如下：假定有L個(gè)三維模型，預(yù)設(shè)分類為K類，每個(gè)模型均用十維組合不變矩表示，首先將模型的每一維特征值按從小到大的順序排列，然后將同一維排列好的L個(gè)特征值按大小排序后再平均分為K份，第1 份特征值全編為0，第2 份特征值全編為1……第K份特征值全編為K-1，從而獲得排序編碼后的十維特征向量。

1.2 基于B-W算法的HMM訓(xùn)練

將排序編碼后的特征向量作為HMM 的輸入觀測序列，并采用添加比例因子的多觀測序列B-W 算法［1，13］對HMM進(jìn)行訓(xùn)練（B-W算法可有效減少HMM訓(xùn)練所需的樣本數(shù)量），以獲得優(yōu)化的HMM。

設(shè)添加比例因子的HMM 為λ，訓(xùn)練好的HMM為。t時(shí)刻下HMM 的觀測序列O對應(yīng)的前向概率和后向概率分別為［14］：

式中：N為HMM 中狀態(tài)的數(shù)量，分別為用于計(jì)算前向概率和后向概率的中間變量；ct是添加的比例因子；aij(aji)為狀態(tài)i(j)向狀態(tài)j(i)轉(zhuǎn)移的概率；bi(Ot)、bj(Ot+1)分別為觀測序列O在時(shí)刻t下對應(yīng)狀態(tài)i和時(shí)刻t+1下對應(yīng)狀態(tài)j的觀測概率。

對于HMM中第l（1≤l≤L）個(gè)觀測序列Ol，其在t時(shí)刻的隱狀態(tài)為Si的概率為：

HMM 中第l個(gè)觀測序列Ol在t時(shí)刻的隱狀態(tài)為Si且在t+1時(shí)刻的隱狀態(tài)為Sj的概率為：

由此可得，HMM參數(shù)的重估公式為：

式中：Tl為觀測序列Ol的訓(xùn)練時(shí)序；cl，t為觀測序列Ol的比例因子；k為觀測序列的觀測值。

利用參數(shù)重估公式對HMM進(jìn)行訓(xùn)練，得到優(yōu)化的HMM，具體流程如圖1所示。

圖1 基于B-M算法的HMM訓(xùn)練流程Fig.1 Training process of HMM based on B-M algorithm

2 基于極半徑曲面矩與HMM 的三維模型分類與檢索算法的實(shí)現(xiàn)與檢驗(yàn)

2.1 算例設(shè)計(jì)

在普渡大學(xué)工程標(biāo)準(zhǔn)模型庫［15］中選取5 類零件的三維模型，每類模型均有10個(gè)相似模型。計(jì)算各個(gè)三維模型的極半徑曲面矩和極半徑曲面中心矩，組成十維組合不變矩，再用排序編碼的方式將其轉(zhuǎn)化為HMM的觀測序列。取每類零件中的5個(gè)三維模型用于HMM的訓(xùn)練，最終得到對應(yīng)于不同零件的5個(gè)優(yōu)化的HMM。HMM的狀態(tài)數(shù)量為5，狀態(tài)轉(zhuǎn)移概率矩陣A與觀測概率矩陣B隨機(jī)生成，初始狀態(tài)矩陣π=[0.2 0.2 0.2 0.2 0.2]。所選取的5類零件的代表模型及其組合不變矩如表1所示。

表1 5類零件的代表模型及其組合不變矩Table 1 Representative models of five types of parts and their combined moment invariants

模型分類：將排序編碼后的50個(gè)三維模型的特征向量分別輸入訓(xùn)練好的5個(gè)HMM中，計(jì)算它們在5個(gè)HMM中的觀測序列出現(xiàn)概率，將其標(biāo)注為概率最大的HMM所對應(yīng)的零件類別。

模型的檢索：用極半徑曲面矩+一階Minkowski相對距離（即閔式相對距離）作為相似性判斷指標(biāo)，即計(jì)算得到的一階閔式相對距離越小，三維模型的相似性越高。在模型分類完成后，當(dāng)查找某個(gè)特定模型時(shí)，先在相似的類中用一階閔式相對距離直接檢索，以加快檢索效率，必要時(shí)可以直接利用極半徑曲面矩+一階閔式相對距離對所有模型進(jìn)行檢索，以找出所有相似模型。一階閔式相對距離d的計(jì)算式為：

式中：xh、yh為要計(jì)算相對距離的2個(gè)極半徑曲面矩。

2.2 算法的性能比較

將基于極半徑曲面矩和HMM 的分類與檢索算法記為算法A；基于極半徑曲面矩和一階閔式相對距離的分類與檢索算法［7］記為算法B；基于Hu不變矩、仿射不變矩和HMM的分類與檢索算法［1］記為算法C（使用canny算子，閾值為0.3）。表2所示為基于不同算法的5類零件的三維模型分類結(jié)果，表3至表5所示為是基于不同算法的nut類、bolt類和T shape類零件三維模型的檢索結(jié)果（由于篇幅限制，只列出3類零件的檢索結(jié)果）。圖2所示為基于不同算法的nut類、bolt 類和T shape 類零件三維模型的檢索效率曲線。表6所示為3 種算法的平均精度（mean average precision，mAP）。根據(jù)上述結(jié)果，對比算法A和算法C可得，利用極半徑曲面矩能夠更好地提取三維模型的特征；對比算法A 和算法B 可得，用HMM 作為分類器能夠得到更好的分類效果。

表6 3種算法的平均精度對比Table 6 Comparison of average accuracy of three algorithms

圖2 基于不同算法的3類零件的三維模型檢索效率對比Fig.2 Comparison of retrieval efficiency of three-dimensional models of three types of parts based on different algorithms

表2 基于不同算法的5類零件的三維模型分類結(jié)果Table 2 Classification results of three-dimensional models of five types of parts based on different algorithms

表3 基于不同算法的nut類零件三維模型的檢索結(jié)果Table 3 Retrieval results of three-dimensional models of nut type parts based on different algorithms

表4 基于不同算法的bolt類零件三維模型的檢索結(jié)果Table 4 Retrieval results of three-dimensional models of bolt type parts based on different algorithms

表5 基于3種算法的T shape類零件三維模型的檢索結(jié)果Table 5 Retrieval results of three-dimensional models of T shape type parts based on different algorithms

為進(jìn)一步驗(yàn)證本文算法的可靠性，擴(kuò)大試驗(yàn)樣本，從PTC（parametric technology corporation，參數(shù)技術(shù)公司）的標(biāo)準(zhǔn)件庫［16］中選取3類零件（flanges類、nut 類、screw 類），每類零件有100 個(gè)相似模型，每個(gè)模型均符合相應(yīng)類的國標(biāo)，且尺寸都不相同，保證差異性，部分代表模型如表7所示。HMM 的狀態(tài)數(shù)設(shè)為3，狀態(tài)轉(zhuǎn)移概率矩陣A與觀測概率矩陣B隨機(jī)生成，初始狀態(tài)矩陣π=[0.3 0.3 0.4]。基于算法A、B、C 的3 類零件的三維模型分類結(jié)果如表8所示（HMM 的訓(xùn)練樣本數(shù)量為40個(gè)）。在不同數(shù)量訓(xùn)練樣本下基于本文算法的3類零件的三維模型分類結(jié)果如表9所示。

表7 部分所選零件的代表模型及其對應(yīng)國標(biāo)Table 7 Representative models of some selected parts and their corresponding national standards

結(jié)合表2和表8可以看出，基于Hu不變矩、仿射不變矩和HMM 的分類與檢索算法的分類準(zhǔn)確率最低，主要原因是該算法用二維圖像矩作為三維模型的特征描述子，而三維模型轉(zhuǎn)化為二維圖像時(shí)損失了大部分特征，且用圖像矩提取二維圖像特征時(shí)存在噪聲干擾，若調(diào)高邊緣檢測算法中canny 算子的閾值，則會丟失細(xì)節(jié)，從而導(dǎo)致分類的準(zhǔn)確性降低。在對nut類零件的三維模型進(jìn)行分類時(shí)，算法C誤判了大量的異形螺母，比如六角鎖緊螺母、蓋型螺母和開槽螺母，由此說明基于Hu不變矩、仿射不變矩的算法易被復(fù)雜特征干擾，提取特征時(shí)的魯棒性不高。利用本文基于極半徑曲面矩和HMM 的分類與檢索算法得到的分類結(jié)果的準(zhǔn)確率較高，這是因?yàn)槔脴O半徑曲面矩提取三維模型特征時(shí)的穩(wěn)定性好，且HMM具有較強(qiáng)的抗干擾能力，采用添加比例因子的多觀測序列B-W 算法能訓(xùn)練出泛化能力更強(qiáng)的HMM。從表9中可以看出，基于極半徑曲面矩和HMM的檢索與分類算法的分類準(zhǔn)確率隨著訓(xùn)練樣本數(shù)量的增加而提高，由此說明該算法具有自我進(jìn)化的能力，可隨著訓(xùn)練次數(shù)的增加而不斷提高性能。

表8 基于不同算法的3類零件的三維模型分類結(jié)果Table 8 Classification results of three-dimensional models of three types of parts based on different algorithms

表9 不同數(shù)量訓(xùn)練樣本下基于本文算法的3類零件的三維模型分類結(jié)果Table 9 Classification results of three-dimensional models of three types of parts based on algorithm in this paper under different numbers of training samples

3 結(jié)論

本文使用極半徑曲面矩提取三維模型的特征并構(gòu)成組合不變矩，再將其排序編碼以作為HMM的觀測序列；運(yùn)用人工標(biāo)記的三維模型和添加比例因子的多觀測序列B-W 算法來訓(xùn)練HMM，再用訓(xùn)練好的HMM 對未標(biāo)記的三維模型進(jìn)行分類與檢索。本文算法以提取的三維模型的極半徑曲面矩為特征描述，可以避免對三維模型的體素化處理，提高了檢索效率，與使用二維圖像矩提取三維模型特征的方法相比，減少了信息的丟失和新噪聲的混入；本文算法引入了HMM，在實(shí)際應(yīng)用中可以用已正確分類的三維模型來訓(xùn)練HMM，提高了分類與檢索的準(zhǔn)確率。將本文算法與基于極半徑曲面矩和一階閔式相對距離的分類與檢索方法以及基于Hu不變矩、仿射不變矩和HMM的分類與檢索方法進(jìn)行了對比。結(jié)果顯示，本文算法對三維模型的分類與檢索效果更好，具有一定的實(shí)用價(jià)值。