基于HMM和仿射不變矩三維模型歸類與檢索算法

強(qiáng)會(huì)英，李雨虹，王洪申，楊笑蕊

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

0 引言

對(duì)機(jī)械零件三維模型的產(chǎn)品設(shè)計(jì)時(shí)，找出已有相似性產(chǎn)品并推斷其功能結(jié)構(gòu)和理念，可以有效重用各環(huán)節(jié)的設(shè)計(jì)成果，即如何快速地從大量的實(shí)例中檢索出所需要的相似性案例成為急需解決的問題。特征提取是三維模型相似性歸類與檢索的重要步驟，如何使提取的特征具有魯棒性是實(shí)現(xiàn)模型歸類與檢索的關(guān)鍵。不變矩是模型的相似性歸類與檢索中重要而有效的特征提取方法并且已經(jīng)成為使用較為廣泛的模型形狀描述子之一。Hu[1]于1962年第一次系統(tǒng)的提出不變矩的理論，他用代數(shù)不變量理論推到了7個(gè)經(jīng)典的不變矩，具有平移、旋轉(zhuǎn)和尺度不變性，但該矩也有一些缺點(diǎn)，其中之一是隨著矩的階數(shù)的升高計(jì)算量會(huì)迅速增長(zhǎng)，另一個(gè)缺點(diǎn)是這些矩不是源于正交函數(shù)族，所以包含了大量的冗余信息，盡管存在這些固有的局限性，但其經(jīng)常被用作模型形狀的首選描述子。Teague[2]在Hu不變矩的基礎(chǔ)上推導(dǎo)出了基于正交多項(xiàng)式的Zernike矩，使用Zernike矩可以很容易的計(jì)算任意高階矩不變量。D.Shen等[3]提出了基于小波變換的特征提取方法即小波矩不變量，李曉兵等[4]，張虹等[5]進(jìn)一步的將小波矩用于圖像和目標(biāo)的識(shí)別中，并取得了很好的效果。仿射不變矩在與視角無關(guān)的目標(biāo)識(shí)別中起到至關(guān)重要的作用，不僅被廣泛的應(yīng)用于圖像發(fā)生仿射形變的任務(wù)中，也經(jīng)常被用于替代投影不變量。第一次嘗試推導(dǎo)仿射變換下的矩不變量可在文獻(xiàn)[1]中找到，但有少許錯(cuò)誤，30年后，Reiss[6]，F(xiàn)lusser[7]和Suk[8]分別獨(dú)立的發(fā)現(xiàn)并更正了這一錯(cuò)誤，發(fā)表了新的仿射不變量集合，此后，李迎春等[9]將仿射不變矩與人工神經(jīng)網(wǎng)絡(luò)相結(jié)合用于飛機(jī)圖像的模式識(shí)別，路鷹[10]，徐勝等[11]將仿射不變矩用于三維模型的識(shí)別。Hu不變矩和仿射不變矩是圖像在整個(gè)空間中的統(tǒng)計(jì)特性，當(dāng)從不同的角度拍攝時(shí)，三維物體的正等測(cè)軸測(cè)圖會(huì)發(fā)生形變，也就是仿射變換，這時(shí)，只用Hu不變矩反映圖像的特征是不夠的，仿射變換被證明是模擬圖像視點(diǎn)變換的最佳方法即該變換具有仿射不變性?？镞d君等[12]結(jié)合這兩種不變矩各自的優(yōu)點(diǎn)，使用組合不變矩結(jié)合SVM分類器進(jìn)行圖像識(shí)別，當(dāng)圖像發(fā)生形變時(shí)，能夠穩(wěn)定、可靠地識(shí)別形狀差異較大的特征，提高了分類的準(zhǔn)確度并可以進(jìn)一步地?cái)U(kuò)大應(yīng)用范圍。

三維模型的歸類是將未知模型劃分到某個(gè)預(yù)先定義的模型類別中，即首先確定該模型所屬的類別，然后在此特定類別的范圍內(nèi)進(jìn)行檢索，從而減小了搜索范圍。因此，對(duì)海量三維模型進(jìn)行正確歸類與檢索有著十分重要的社會(huì)價(jià)值和經(jīng)濟(jì)意義。傳統(tǒng)的歸類方法在處理小樣本問題時(shí)不僅容易出現(xiàn)過學(xué)習(xí)現(xiàn)象，而且有可能會(huì)導(dǎo)致算法的推廣性和學(xué)習(xí)的性能差，使得在處理非線性問題時(shí)算法過于復(fù)雜。統(tǒng)計(jì)學(xué)習(xí)理論是一種專門針對(duì)小樣本的統(tǒng)計(jì)理論，基于統(tǒng)計(jì)學(xué)習(xí)理論的隱馬爾科夫模型是一種新的模型識(shí)別方法，不僅能夠較好的解決小樣本的學(xué)習(xí)問題，而且實(shí)現(xiàn)簡(jiǎn)單，算法訓(xùn)練時(shí)間短，識(shí)別率穩(wěn)定。2002年，HMM廣泛應(yīng)用于平面物體的歸類問題中[13]，后來Panuccio等[14]和劉小明等[15]將HMM用于基于內(nèi)容的三維物體的識(shí)別中，郭競(jìng)等[16]針對(duì)三維模型的歸類問題，提出了一種基于HMM和最大期望算法的三維模型自動(dòng)歸類方法并取得了很好的效果。故本文將Hu不變矩的7個(gè)分量V1，V2，…，V7和仿射不變矩的三個(gè)分量I1，I2，I3組合成一個(gè)包含10個(gè)特征元素的組合不變矩，通過隱馬爾科夫分類模型進(jìn)行機(jī)械零件的相似性歸類與檢索。

1 基于HMM的機(jī)械零件分類

隱馬爾科夫模型（Hidden Markov Model，HMM）[17]是一個(gè)雙重隨機(jī)過程，其中一個(gè)描述狀態(tài)轉(zhuǎn)移序列，另一個(gè)是描述狀態(tài)與觀測(cè)序列之間的關(guān)系，該模型由五種元素構(gòu)成，即 λ ={ π ,A,B,N,M}，其中N為隱狀態(tài)的個(gè)數(shù)，M為不同的觀測(cè)輸出個(gè)數(shù)，π為初始狀態(tài)概率分布矩陣，A為狀態(tài)轉(zhuǎn)移概率矩陣，B為狀態(tài)輸出概率矩陣。HMM作為一種統(tǒng)計(jì)分析模型，具有極強(qiáng)的建模能力和模式分類能力，它創(chuàng)立于20世紀(jì)70年代，80年代得到了傳播和發(fā)展，成為信號(hào)處理的一個(gè)重要方向，現(xiàn)已成功地用于圖像處理，語音識(shí)別，行為識(shí)別，文字識(shí)別以及模式分類等領(lǐng)域[18]。本文的研究是利用HMM來構(gòu)建機(jī)械零件三維模型的分類識(shí)別模式?；贖MM的機(jī)械零件的分類方法如圖1所示。

圖1 基于HMM的機(jī)械零件分類結(jié)構(gòu)框圖

由圖1可知，基于HMM的機(jī)械零件的分類過程為：首先使用Sobol算子提取三維模型的軸側(cè)投影圖，然后對(duì)該圖進(jìn)行Hu不變矩和仿射不變矩的特征提取，其次將提取到的特征值作為HMM的觀測(cè)輸入值，選取一部分作為標(biāo)準(zhǔn)樣本訓(xùn)練初始的HMM，得到HMM的優(yōu)化模型，將另一部分特征值輸入該優(yōu)化模型，進(jìn)行檢測(cè)，最后比較HMM的輸出對(duì)數(shù)似然函數(shù)值，依據(jù)HMM的模式識(shí)別方法，得出機(jī)械零件的識(shí)別結(jié)果。

2 機(jī)械零件三維模型的特征提取

2.1 機(jī)械零件三維模型的表示

由于三維模型中含有的信息量大，直接作為檢索對(duì)此無法滿足速度的要求，因此，通常將三維模型進(jìn)行特征提取，并形成描述子，通過描述子之間的比較實(shí)現(xiàn)模型檢索。機(jī)械零件三維模型正等測(cè)軸測(cè)圖的表達(dá)首先將該模型調(diào)整成軸測(cè)圖的位置，然后取得其圖像，再用Sobol算子[19]對(duì)圖像的邊緣輪廓圖進(jìn)行提取，獲得如圖2所示的機(jī)械零件三維模型及其軸測(cè)圖外部輪廓。

圖2 Sobol算子提取機(jī)械零件三維模型輪廓邊緣

2.2 特征提取

對(duì)機(jī)械零件的正等測(cè)軸測(cè)圖進(jìn)行特征提取時(shí)，在現(xiàn)實(shí)場(chǎng)景下，外界因素會(huì)影響物體成像，其中最困難的問題之一是如何從任意尺度和視角所獲取的同一場(chǎng)景的圖像中提取不變的特征。當(dāng)從不同的角度拍攝時(shí)，三維物體會(huì)發(fā)生形變，也就是仿射變換，這時(shí)，只用Hu不變矩反映目標(biāo)物體的特征是不夠的，仿射變換被證明是模擬圖像視點(diǎn)變換的最佳方法，Jan Flusser等體提取了仿射不變矩作為特征，并證明在物體圖像發(fā)生平移，比例，旋轉(zhuǎn)，傾斜變換下仍具有不變性。仿射不變矩與Hu矩一樣，也是源于代數(shù)不變性的，由Hu矩演變而來。通過將坐標(biāo)原點(diǎn)平移到目標(biāo)輪廓的中心（歸一化），可以實(shí)現(xiàn)圖像仿射不變矩的特征提取，從而進(jìn)行圖像的歸類與識(shí)別。故本文將Hu不變矩與仿射不變矩各自的優(yōu)點(diǎn)相結(jié)合形成組合不變矩，作為HMM的特征輸入值。對(duì)于二維連續(xù)函數(shù)f（x，y），中心矩定義為：

歸一化的中心矩為：

利用歸一化的中心矩，可以獲取對(duì)平移，縮放，鏡像和旋轉(zhuǎn)都不敏感的7個(gè)不變矩，定義如下：

離心率代表了圖像長(zhǎng)軸與短軸之間的比值，滿足幾何變換的不變性。離心率E的計(jì)算公式為：

仿射不變矩就是一種經(jīng)過仿射變換后依然保持不變的特征量，我們只選取前3個(gè)仿射不變矩參與圖像的相似性歸類與檢索。

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

3.1 算法原理

通過MATLAB軟件對(duì)機(jī)械零件三維模型的軸側(cè)投影圖提取上述7個(gè)Hu不變矩和3個(gè)仿射不變矩形成組合不變矩的特征值，如表1（只列出部分）所示，然后將這些特征值通過排序編碼的算法進(jìn)行編碼，如表2所示。將編碼后的10維特征向量作為模型的輸入觀測(cè)值，利用B-W算法進(jìn)行訓(xùn)練，獲得HMM的λ優(yōu)化模型，本文使用HMM模型中添加比例因子的多觀測(cè)值的B-W算法，公式如下：

參數(shù)重估公式為：

算法訓(xùn)練的過程如下：

首先收集形狀各異的K類圖像，將每一類圖像中的若干圖像分為兩部分，一部分用于樣本對(duì)于初始模型的訓(xùn)練，另一部分用來測(cè)試模型。根據(jù)圖像的先驗(yàn)知識(shí)首先為其初始一個(gè)HMM模型λ，然后利用樣本集進(jìn)行訓(xùn)練，執(zhí)行如下步驟：

步驟1：已知有K類圖像，每類圖像中有L個(gè)訓(xùn)練樣本，即L個(gè)觀察值序列，n表示迭代次數(shù)，初始時(shí)刻n=1；

表1 組合不變矩的特征值

步驟6：利用重估式(17)對(duì)模型進(jìn)行參數(shù)估計(jì)并得到新模型；

步驟7：判斷模型參數(shù)的迭代收斂條件，計(jì)算后驗(yàn)概率的對(duì)數(shù)似然函數(shù)值：

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

本實(shí)驗(yàn)所使用的模型主要來自于ESB模型庫(kù)[20]。在ESB模型庫(kù)中選取五類不同的機(jī)械零件三維模型，每一類模型中有十個(gè)相似模型。這五類模型的代表模型見圖3（每一類只列出兩個(gè)相似模型）。

表2 組合不變矩特征值的編碼

圖3 機(jī)械零件的三維模型

每一類模型中取前5個(gè)模型作為訓(xùn)練樣本集，將編碼后的特征向量作為HMM的觀測(cè)輸入值，通過上面所陳述的添加比例因子的多觀測(cè)值的B-W算法進(jìn)行訓(xùn)練。初始模型的參數(shù)根據(jù)先驗(yàn)知識(shí)設(shè)定為狀態(tài)總數(shù)N=5，輸出觀測(cè)值的個(gè)數(shù)M=5，初始概率π=（0.6，0.1，0.1，0.1，0.1），轉(zhuǎn)移概率矩陣A與輸出概率矩陣B由MATLAB隨機(jī)生成，這5類模型最后可以訓(xùn)練出5個(gè)優(yōu)化模型，分別為。接下來進(jìn)行模型的檢驗(yàn)和識(shí)別。在本實(shí)驗(yàn)中將每一類模型中的10個(gè)向量全部用于HMM優(yōu)化模型的檢驗(yàn)與識(shí)別，首先計(jì)算待識(shí)別模型的觀測(cè)序列在模型下的輸出后驗(yàn)概率對(duì)數(shù)似然函數(shù)值logP(Ol|λm),，1≤m≤5，計(jì)算取使得最大的模型，即輸出似然函數(shù)值最大的那一個(gè)為待識(shí)別模型的所屬類別。將本文所提方法Hu不變矩+仿射不變矩+HMM記為算法A，Hu不變矩+離心率+HMM記為算法B，Hu不變矩+仿射不變矩+歐氏距離記為算法C。表3是50個(gè)機(jī)械零件三維模型使用算法A在五類優(yōu)化后HMM模型下的檢測(cè)結(jié)果（只列出部分結(jié)果）。1號(hào)零件在這五類優(yōu)化模型下的輸出對(duì)數(shù)似然函數(shù)值分別為-6.6927，-8.1555，-7.4244，-6.9094，-7.3247，可以看出-6.9094是最大值，故判定該零件所屬類別為第四類模型，而實(shí)際上1號(hào)零件屬于第一類模型，所以該識(shí)別錯(cuò)誤；3號(hào)零件在這五類優(yōu)化模型下的輸出對(duì)數(shù)似然函數(shù)值分別為-6.3564，-9.3103，-6.957，-7.479，-7.3542，可以看出-6.3564是最大值，故判定該零件所屬類別為第一類模型，識(shí)別結(jié)果正確。故從表3可以看出，算法A對(duì)第一類模型正確識(shí)別的結(jié)果為8個(gè)，第二類模型為10個(gè)，第三類模型為9個(gè)，第四類模型為9個(gè)，第五類模型為6個(gè)。而算法B對(duì)這五類模型正確識(shí)別的結(jié)果分別為7，9，6，9，7個(gè)，算法C對(duì)這五類模型正確識(shí)別的結(jié)果分別為6，4，3，4，5個(gè)。表4和表5是這三種算法的檢索結(jié)果，圖4是這三種檢索結(jié)果所得的查準(zhǔn)率與查全率的效率曲線（由于篇幅限制，只列出優(yōu)化模型四和優(yōu)化模型五的檢索結(jié)果和效率曲線圖，并只列出相似性檢索結(jié)果排列在前9位的圖像）?？梢钥闯觯?dāng)使用相同的HMM這一分類器時(shí)，算法A的識(shí)別率高于算法B的識(shí)別率，是因?yàn)樵谔卣魈崛r(shí)仿射不變矩的仿射不變性對(duì)于圖像具有較高的描述能力，從而提高了識(shí)別的準(zhǔn)確度；當(dāng)使用相同的特征描述子Hu不變矩和仿射不變矩時(shí)，算法A的識(shí)別率高于算法C的識(shí)別率，是因?yàn)榛诮y(tǒng)計(jì)學(xué)習(xí)理論的HMM模型具有較強(qiáng)的分類能力并優(yōu)于傳統(tǒng)的基于歐式距離的判別方法。故本文所提算法具有一定的意義和使用價(jià)值。

圖4 優(yōu)化模型的檢索效率

表4 nut1在優(yōu)化模型三中的檢索結(jié)果排序

表5 screw1在優(yōu)化模型四中的檢索結(jié)果排序

4 結(jié)束語

對(duì)機(jī)械零件三維模型，本文首先使用Sobol算子提取其軸側(cè)投影圖，然后對(duì)該圖進(jìn)行Hu不變矩和仿射不變矩形成組合不變矩的特征提取，其次通過排序編碼的方法對(duì)該特征值進(jìn)行編碼，最后使用HMM模型中添加比例因子的多觀測(cè)值B-W算法進(jìn)行訓(xùn)練與識(shí)別，并將本文所提算法與另外兩種算法Hu不變矩與離心率結(jié)合HMM模型模式分類算法與Hu不變矩和仿射不變矩結(jié)合歐氏距離的判別算法進(jìn)行實(shí)驗(yàn)與對(duì)比，實(shí)驗(yàn)結(jié)果顯示根據(jù)本文所提出的算法可以實(shí)現(xiàn)機(jī)械零件三維物體模型的有效分類與識(shí)別，并能取得較高的查全率與查準(zhǔn)率。

本文是根據(jù)先驗(yàn)知識(shí)為HMM模型擬定一個(gè)初始值，并通過添加比例因子的多觀測(cè)值B-W算法進(jìn)行訓(xùn)練，但是B-W算法本身對(duì)初始值很敏感以及其爬山似的迭代搜索方式使訓(xùn)練得到最終的HMM模型對(duì)于細(xì)節(jié)比較豐富的機(jī)械零件的判別可能存在一定的誤差，因此接下來進(jìn)一步的研究?jī)?nèi)容是在HMM模型的初值選取和訓(xùn)練算法上做進(jìn)一步的改善和優(yōu)化。