摘 要:采用主成分分析方法(PCA)定義了簡單的數(shù)學(xué)模型和軸向確定方法等來實(shí)現(xiàn)配準(zhǔn)。大量實(shí)驗(yàn)證明,算法能夠快速實(shí)現(xiàn)任意形狀、大小及位置的兩片點(diǎn)云配準(zhǔn)。
關(guān)鍵詞:點(diǎn)云處理; 配準(zhǔn); 主軸旋轉(zhuǎn)法; 軸向確定
在機(jī)器視覺眾多應(yīng)用領(lǐng)域中,如立體匹配、圖像配準(zhǔn)和形狀識別等,點(diǎn)云配準(zhǔn)操作一直都是一個關(guān)鍵步驟。點(diǎn)云配準(zhǔn)就是將一片點(diǎn)云(測試點(diǎn)集)的坐標(biāo)匹配到另一片點(diǎn)云(參考點(diǎn)集)的坐標(biāo)下,從而達(dá)到兩片點(diǎn)云坐標(biāo)的一致性,其配準(zhǔn)精度直接影響后續(xù)誤差分析的可靠性。目前,常用的配準(zhǔn)方法有遺傳算法、最小二乘匹配方法、三點(diǎn)對齊法以及ICP算法。遺傳算法和最小二乘匹配方法需要多次迭代處理,計算復(fù)雜度高并且配準(zhǔn)時間長;三點(diǎn)對齊法實(shí)現(xiàn)原理簡單,能夠很快地實(shí)現(xiàn)初始配準(zhǔn),但必須準(zhǔn)確地確定出3對基準(zhǔn)點(diǎn)的對應(yīng)關(guān)系[1];ICP算法是一種眾所周知的算法[2],傳統(tǒng)的ICP算法雖簡單,但在實(shí)際應(yīng)用中具有限制性,因?yàn)樗僭O(shè)每一個點(diǎn)都可以在對應(yīng)的點(diǎn)集中找到對應(yīng)點(diǎn),當(dāng)兩模型數(shù)據(jù)不一樣時,該假設(shè)就不成立。
在配準(zhǔn)過程中,涉及旋轉(zhuǎn)和平移矩陣的求取,EGGERT D W等人對比了奇異值分解法(SVD)、正交矩陣法(OM),單四元素法(UQ)以及雙四元素法(DQ)4種當(dāng)前流行和最有效算法的魯棒性和精確度[3],運(yùn)用分離算法測試了4種算法的穩(wěn)定性。在非退化數(shù)據(jù)點(diǎn)集的情況下,大多數(shù)情況SVD和UQ是相似的,少量情況下是SVD更好一點(diǎn),OM對于平面數(shù)據(jù)點(diǎn)集不穩(wěn)定,而DQ算法則沒有一種情況比其他3種算法好?;谶@些測試結(jié)果,本文采用SVD來得到旋轉(zhuǎn)矩陣。
1 本文算法
主成分分析方法(PCA)的基本思想是,采用統(tǒng)計方法,對多變量表示數(shù)據(jù)點(diǎn)集合尋找盡可能少的正交矢量表征數(shù)據(jù)信息特征。本文采用PCA定義了簡單的數(shù)學(xué)模型和軸向確定方法等。本文配準(zhǔn)算法簡單、穩(wěn)定可靠、計算速度快且計算復(fù)雜度小。
其中, n代表點(diǎn)集的個數(shù)。根據(jù)定義2、定義3計算慣量矩陣I,由定義4可以得到參考點(diǎn)集和測試點(diǎn)集的慣量矩陣I1、I2的特征值和特征向量。以I1為例,得到正交特征向量V1、V2和V3,以這3個特征向量建立坐標(biāo)系有8種情況,首先規(guī)定坐標(biāo)系必須滿足右手規(guī)則,便可去掉4種情況。2008年張樹森采用包圍盒到去掉配準(zhǔn)方向相反的情況,該方法計算速度非常慢[4]。本文先找到最大特征值對應(yīng)的正交特征向量V1,然后尋找點(diǎn)集中離質(zhì)心最遠(yuǎn)的點(diǎn),如果此點(diǎn)與特征向量V1的夾角小于90°,則u1=V1,反之,u1=-V1,同理可以求得u2,u3=u1×u2,大大提高了配準(zhǔn)速度。
得到了參考點(diǎn)集和測試點(diǎn)集的正交特征向量后,旋轉(zhuǎn)平移變換就轉(zhuǎn)換為求取兩組正交向量組的變換。由此可以得到待SVD分解的兩點(diǎn)集相關(guān)矩陣為[5]:
2 測試效果
以下所有測試實(shí)驗(yàn)均是在CPU為2.52 GHz,內(nèi)存為3.50 GB的環(huán)境下進(jìn)行的,采用了C++語言和OpenCV 2.3.1基礎(chǔ)庫,并在VS 2008軟件平臺上編譯運(yùn)行。為了驗(yàn)證算法的穩(wěn)定性,測試選用了不同的形狀,圖3所示為3種典型模型的配準(zhǔn)效果。其中,模型1為綿陽鐵??萍紥呙璧狞c(diǎn)云,模型2和模型3的點(diǎn)云采用的是Geomagic Qualify 12中的模型。從圖3可以看到,這3種模型都可以實(shí)現(xiàn)配準(zhǔn)。
表1為各種模型的兩片配準(zhǔn)模型的點(diǎn)云個數(shù)和粗配準(zhǔn)所需要的時間,可以看出,點(diǎn)云數(shù)據(jù)在幾十萬的情況下,配準(zhǔn)時間全都是ms級。
實(shí)驗(yàn)結(jié)果證明,本文采用的配準(zhǔn)方法算法簡單、穩(wěn)定可靠、計算速度快且計算復(fù)雜度小,對實(shí)現(xiàn)大量點(diǎn)云快速配準(zhǔn)具有使用價值。
參考文獻(xiàn)
[1] 嚴(yán)平,孫肖霞.基于CAD模型的渦輪葉片誤差檢測系統(tǒng)[J].北京航空航天大學(xué)學(xué)報, 2008,34(10):1159-1162.
[2] BESL P J, MCKAY N D. A method for registration of 3-D shapes[J].IEEE Transactions on Pattern Analysis and Machine Intelligence (S0162-8828),1992,2(14):239-256.
[3] EGGERT D W, LORUSSO A, FISHER R B. Estimating 3-D rigid body transformations: a comparison of four major algorithms[J]. Machine Vision and Applications (S0932-8092),1997,9:272-290.
[4] 張樹森,李瑋,程俊廷.基于逆向工程的三維測量點(diǎn)云數(shù)據(jù)與CAD數(shù)模配準(zhǔn)算法研究[J].制造技術(shù)與機(jī)床,2008(3);114-117.
[5] APLPERT M, BRADSHAW J G. The principal axes transformation-a method for image registration[J]. The Journal of Nuclear Medicine(S0161-5505),1990(31):1717-1722.