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

王洪申，劉 敏，強會英

（1.蘭州理工大學機電工程學院，甘肅蘭州730050；2.蘭州交通大學數理與軟件學院，甘肅蘭州730070）

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

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

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

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

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

1.1 三維模型的特征提取

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

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

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

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

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

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

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

1.2 基于B-W算法的HMM訓練

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

設添加比例因子的HMM 為λ，訓練好的HMM為。t時刻下HMM 的觀測序列O對應的前向概率和后向概率分別為［14］：

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

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

HMM 中第l個觀測序列Ol在t時刻的隱狀態為Si且在t+1時刻的隱狀態為Sj的概率為：

由此可得，HMM參數的重估公式為：

式中：Tl為觀測序列Ol的訓練時序；cl，t為觀測序列Ol的比例因子；k為觀測序列的觀測值。

利用參數重估公式對HMM進行訓練，得到優化的HMM，具體流程如圖1所示。

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

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

2.1 算例設計

在普渡大學工程標準模型庫［15］中選取5 類零件的三維模型，每類模型均有10個相似模型。計算各個三維模型的極半徑曲面矩和極半徑曲面中心矩，組成十維組合不變矩，再用排序編碼的方式將其轉化為HMM的觀測序列。取每類零件中的5個三維模型用于HMM的訓練，最終得到對應于不同零件的5個優化的HMM。HMM的狀態數量為5，狀態轉移概率矩陣A與觀測概率矩陣B隨機生成，初始狀態矩陣π=[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個三維模型的特征向量分別輸入訓練好的5個HMM中，計算它們在5個HMM中的觀測序列出現概率，將其標注為概率最大的HMM所對應的零件類別。

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

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

2.2 算法的性能比較

將基于極半徑曲面矩和HMM 的分類與檢索算法記為算法A；基于極半徑曲面矩和一階閔式相對距離的分類與檢索算法［7］記為算法B；基于Hu不變矩、仿射不變矩和HMM的分類與檢索算法［1］記為算法C（使用canny算子，閾值為0.3）。表2所示為基于不同算法的5類零件的三維模型分類結果，表3至表5所示為是基于不同算法的nut類、bolt類和T shape類零件三維模型的檢索結果（由于篇幅限制，只列出3類零件的檢索結果）。圖2所示為基于不同算法的nut類、bolt 類和T shape 類零件三維模型的檢索效率曲線。表6所示為3 種算法的平均精度（mean average precision，mAP）。根據上述結果，對比算法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類零件的三維模型分類結果Table 2 Classification results of three-dimensional models of five types of parts based on different algorithms

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

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

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

為進一步驗證本文算法的可靠性，擴大試驗樣本，從PTC（parametric technology corporation，參數技術公司）的標準件庫［16］中選取3類零件（flanges類、nut 類、screw 類），每類零件有100 個相似模型，每個模型均符合相應類的國標，且尺寸都不相同，保證差異性，部分代表模型如表7所示。HMM 的狀態數設為3，狀態轉移概率矩陣A與觀測概率矩陣B隨機生成，初始狀態矩陣π=[0.3 0.3 0.4]?；谒惴ˋ、B、C 的3 類零件的三維模型分類結果如表8所示（HMM 的訓練樣本數量為40個）。在不同數量訓練樣本下基于本文算法的3類零件的三維模型分類結果如表9所示。

表7 部分所選零件的代表模型及其對應國標Table 7 Representative models of some selected parts and their corresponding national standards

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

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

表9 不同數量訓練樣本下基于本文算法的3類零件的三維模型分類結果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 結論

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