一種快速的三維點云自動配準方法

謝冬香，劉先勇

(西南科技大學 信息工程學院，四川 綿陽 621000)

在機器視覺眾多應(yīng)用領(lǐng)域中,如立體匹配、圖像配準和形狀識別等，點云配準操作一直都是一個關(guān)鍵步驟。點云配準就是將一片點云(測試點集)的坐標匹配到另一片點云（參考點集）的坐標下，從而達到兩片點云坐標的一致性，其配準精度直接影響后續(xù)誤差分析的可靠性。目前，常用的配準方法有遺傳算法、最小二乘匹配方法、三點對齊法以及ICP算法。遺傳算法和最小二乘匹配方法需要多次迭代處理，計算復(fù)雜度高并且配準時間長；三點對齊法實現(xiàn)原理簡單，能夠很快地實現(xiàn)初始配準，但必須準確地確定出3對基準點的對應(yīng)關(guān)系[1];ICP算法是一種眾所周知的算法[2],傳統(tǒng)的ICP算法雖簡單，但在實際應(yīng)用中具有限制性，因為它假設(shè)每一個點都可以在對應(yīng)的點集中找到對應(yīng)點，當兩模型數(shù)據(jù)不一樣時，該假設(shè)就不成立。

在配準過程中,涉及旋轉(zhuǎn)和平移矩陣的求取，EGGERT D W等人對比了奇異值分解法(SVD)、正交矩陣法(OM),單四元素法(UQ)以及雙四元素法(DQ)4種當前流行和最有效算法的魯棒性和精確度[3],運用分離算法測試了4種算法的穩(wěn)定性。在非退化數(shù)據(jù)點集的情況下,大多數(shù)情況SVD和UQ是相似的,少量情況下是SVD更好一點,OM對于平面數(shù)據(jù)點集不穩(wěn)定,而DQ算法則沒有一種情況比其他3種算法好?；谶@些測試結(jié)果，本文采用SVD來得到旋轉(zhuǎn)矩陣。

1 本文算法

主成分分析方法(PCA)的基本思想是,采用統(tǒng)計方法,對多變量表示數(shù)據(jù)點集合尋找盡可能少的正交矢量表征數(shù)據(jù)信息特征。本文采用PCA定義了簡單的數(shù)學模型和軸向確定方法等。本文配準算法簡單、穩(wěn)定可靠、計算速度快且計算復(fù)雜度小。

1.1 數(shù)學公式定義

定義1三維數(shù)字圖像的繞矩定義為：

繞矩mijk的次數(shù)定義為i+j+k。

定義2設(shè)三維數(shù)字圖像的質(zhì)心為(gx,gy,gz),則中心繞矩為：

定義3設(shè)數(shù)字圖像的慣量矩陣I定義為：

其中，Ixx=u200,Iyy=u020,Izz=u002，Ixy=Iyx=u110，Ixz=Izx=u101，Iyz=Izy=u011。

定義4由于慣量矩陣I是對稱的，因此一定存在實特征值。 設(shè) λ1、λ2、λ3是慣量矩陣的 3個實特征值,這 3個實特征值一定有3個不同的特征向量，正交化后一定存在一組對應(yīng)的正交特征向量 V1、V2和 V3，將這 3個特征向量稱為物體的一組主軸。將物體的質(zhì)心作為坐標原點并將其與這一組主軸一起定義為對象中心坐標系,如圖1所示。

1.2 算法流程

本文算法主要是通過計算測試點集到參考點集的平移和旋轉(zhuǎn)矩陣將測試點集配準到參考點集下，圖2為算法的流程圖。

圖2 算法流程圖

1.3 旋轉(zhuǎn)平移矩陣的獲取

計算參考點集和測試點集的質(zhì)心。為了提高算法的速度，本文采用以下質(zhì)心計算方法：

其中,n代表點集的個數(shù)。根據(jù)定義2、定義 3計算慣量矩陣 I，由定義 4可以得到參考點集和測試點集的慣量矩陣 I1、I2的特征值和特征向量。以 I1為例，得到正交特征向量 V1、V2和V3,以這3個特征向量建立坐標系有8種情況，首先規(guī)定坐標系必須滿足右手規(guī)則，便可去掉4種情況。2008年張樹森采用包圍盒到去掉配準方向相反的情況,該方法計算速度非常慢[4]。本文先找到最大特征值對應(yīng)的正交特征向量V1，然后尋找點集中離質(zhì)心最遠的點，如果此點與特征向量V1的夾角小于 90°，則u1=V1,反 之，u1=-V1， 同 理 可 以 求 得 u2，u3=u1×u2， 大 大 提高了配準速度。

得到了參考點集和測試點集的正交特征向量后，旋轉(zhuǎn)平移變換就轉(zhuǎn)換為求取兩組正交向量組的變換。由此可以得到待SVD分解的兩點集相關(guān)矩陣為[5]：

其中,Dci、Mci分別是參考點集和測試點集的正交特征向量組成的向量矩陣。設(shè)H的奇異值分解為H=USVT，因此旋轉(zhuǎn)矩陣R的最優(yōu)解為：

最優(yōu)的平移矩陣就是將測試點集的中心移動到參考點集的中心下。設(shè)測試點集和參考點集的中心分別為T0和C0，則可以得到平移矩陣T為：

最后得到旋轉(zhuǎn)平移矩陣M：

其中，R 為 3×3的矩陣，0為 3×1的矩陣，T為 1×3的矩陣。將所有測試點集乘以此旋轉(zhuǎn)平移矩陣并將其移動到參考點集下，實現(xiàn)了快速配準。

2 測試效果

以下所有測試實驗均是在CPU為2.52GHz,內(nèi)存為3.50 GB的環(huán)境下進行的,采用了C++語言和OpenCV 2.3.1基礎(chǔ)庫，并在VS 2008軟件平臺上編譯運行。為了驗證算法的穩(wěn)定性，測試選用了不同的形狀，圖3所示為3種典型模型的配準效果。其中，模型1為綿陽鐵?？萍紥呙璧狞c云,模型2和模型3的點云采用的是Geo-magic Qualify 12中的模型。從圖3可以看到，這3種模型都可以實現(xiàn)配準。

表1為各種模型的兩片配準模型的點云個數(shù)和粗配準所需要的時間，可以看出，點云數(shù)據(jù)在幾十萬的情況下，配準時間全都是ms級。

表1 配準點云數(shù)目和配準所需要的時間

實驗結(jié)果證明,本文采用的配準方法算法簡單、穩(wěn)定可靠、計算速度快且計算復(fù)雜度小，對實現(xiàn)大量點云快速配準具有使用價值。

[1]嚴平，孫肖霞.基于CAD模型的渦輪葉片誤差檢測系統(tǒng)[J].北京航空航天大學學報,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 andMachine 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]張樹森，李瑋,程俊廷.基于逆向工程的三維測量點云數(shù)據(jù)與CAD數(shù)模配準算法研究[J].制造技術(shù)與機床，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.