基于誤差閾值控制的ICP點云配準(zhǔn)算法研究

張晶，葉含笑，楊麟

（1.中國美術(shù)學(xué)院，杭州 310002；2.浙江中醫(yī)藥大學(xué)，杭州 310053）

一、背景

文物是由人類創(chuàng)造的在社會文明發(fā)展過程中保存下來的具有歷史、人文、藝術(shù)和科考研究價值的寶貴遺跡。絕大部分文物在時間沉淀中會自然風(fēng)化或被人為損壞。文物修復(fù)在考古和文物研究中是最為關(guān)鍵的、技術(shù)性極強(qiáng)的工作，很多搶救性的文物修復(fù)往往任務(wù)繁重，時間緊迫。通過虛擬復(fù)原技術(shù)不僅可以降低傳統(tǒng)文物修復(fù)的難度，減少貿(mào)然修復(fù)過程中的人為因素對文物的損壞，數(shù)字化文物虛擬復(fù)原的模型還可應(yīng)用于虛擬博物館的數(shù)字化文物展，通過互聯(lián)網(wǎng)技術(shù)實現(xiàn)文物資源共享，從而極大提高科考等的工作效率。因此文物數(shù)字圖像三維虛擬修復(fù)具有極大的技術(shù)研究價值，同時具有重要的應(yīng)用研究及社會人文價值。

二、點云數(shù)據(jù)采集

點云數(shù)據(jù)采集可以通過數(shù)碼相機(jī)或激光掃描獲得，數(shù)碼相機(jī)主要用來測量點的三維坐標(biāo)和顏色信息。移動激光掃描系統(tǒng)一般由激光掃描儀和導(dǎo)航系統(tǒng)組成，移動激光掃描系統(tǒng)主要用于測量點的三維坐標(biāo)和點的激光反射強(qiáng)度；根據(jù)數(shù)碼相機(jī)和移動激光掃描系統(tǒng)采集的數(shù)據(jù)可以得到點云數(shù)據(jù)，通過這種方式采集到的點云包含顏色信息、激光反射強(qiáng)度和三維坐標(biāo)。通常點的三維坐標(biāo)屬于本地坐標(biāo)系中的坐標(biāo)。

通過對文物進(jìn)行全息記錄和轉(zhuǎn)化可以將文物以數(shù)字化形式保留下來，文物數(shù)字化可以搶救性地記錄和保全文物信息，為文物展示、研究等的應(yīng)用提供取之不盡用之不竭的數(shù)字化信息。本文涉及的文物數(shù)字化信息通過三維激光掃描獲得，未經(jīng)過其他處理手段，三維掃描獲得的點不僅包含了三維坐標(biāo)的信息，同時也包含了顏色、光照反射強(qiáng)度值、分類值、時間等的信息，像素點的顏色信息首先通過相機(jī)獲取，同時將像素的顏色信息（RGB）賦予坐標(biāo)位置上對應(yīng)點云中的點上。光照反射強(qiáng)度信息由激光掃描儀接收裝置所獲取，此強(qiáng)度信息與文物表面的材質(zhì)、粗糙程度、入射角的方向，以及發(fā)射光的強(qiáng)度、激光波長有關(guān)。對于復(fù)雜三維外形，其坐標(biāo)軸之間并沒有被以某種規(guī)律或某種數(shù)值關(guān)系確定下來，所以采集到的點無法建立縱橫坐標(biāo)之間的聯(lián)系，點云配準(zhǔn)就是為了把不同坐標(biāo)系中的點云映射到相同坐標(biāo)系中，因此點云配準(zhǔn)在計算機(jī)視覺輔助工程應(yīng)用中具有重要作用，也是計算機(jī)視覺研究的關(guān)鍵問題之一，如逆向工程、同步定位與建圖、圖像處理和模式識別等。

三、文物掃描數(shù)據(jù)點云配準(zhǔn)

點云配準(zhǔn)（Point Cloud Registration，PCR）過程就是指通過求兩個點云之間的旋轉(zhuǎn)變換和平移變換（Euclidean Transform and Rigid Transform），將處于不同視角下獲得的點云整合到指定坐標(biāo)系下的過程。具體可以描述為：由于間斷掃描或移動掃描，使得完整的文物數(shù)據(jù)信息處在了不同坐標(biāo)系上，從而導(dǎo)致對應(yīng)的兩組點云出現(xiàn)，把原點云Ps（Source Cloud）和目標(biāo)點云Pt（Target Cloud）通過旋轉(zhuǎn)變換，組合到相同的坐標(biāo)系下，再通過位移矩陣T，使得Ps和Pt的重合達(dá)到盡可能最優(yōu)。變換矩陣可以是剛性的（Rigid），也可以不是剛性的，本文只考慮剛性變換，即點云變換只包括平移、旋轉(zhuǎn)。剛性點云配準(zhǔn)可以被分為粗略配準(zhǔn)（Coarse Registration）和精細(xì)配準(zhǔn)（Fine Registration）兩個步驟。粗略配準(zhǔn)指的是在兩幅不同坐標(biāo)系上點云之間的變換在完全未知的情況下進(jìn)行較為粗略的配準(zhǔn)，可以被看作是為精配準(zhǔn)提供預(yù)處理的初值變換；精配準(zhǔn)則是根據(jù)在粗略配準(zhǔn)基礎(chǔ)上給定的一個初始變換，進(jìn)一步優(yōu)化后得到更為精確的變換。

對于靜態(tài)場景，目前應(yīng)用最為廣泛的點云精準(zhǔn)配準(zhǔn)算法依然是迭代最近點算法（Iterative Closest Point，ICP），本算法由Besl and McKay 1992年在A Method for Registration of 3-D Shapes文章中最先提出，以及ICP 算法的各種變種算法，比如point to plane ICP、穩(wěn)健ICP、Point to line ICP、NICP、MBICP和GICP等。

四、ICP算法描述

三維文物掃描點云配準(zhǔn)為了將不在同一坐標(biāo)系下的兩組或多組點云通過點云的旋轉(zhuǎn)和平移變換統(tǒng)一到同一參考坐標(biāo)系下。這個變換過程，可以通過映射操作來完成。要得到精確值在現(xiàn)實中是難以實現(xiàn)的，因此為了獲得精確的點云配準(zhǔn)，通常情況下，會盡可能多的尋找被匹配的對應(yīng)點對，以便盡可能地提高變換矩陣預(yù)設(shè)參數(shù)的精度。

圖1為文物三維掃描傳統(tǒng)的ICP算法點云配準(zhǔn)三維重建效果圖，由圖可以看出重建后的文物產(chǎn)生了部分傾斜。

圖1 I CP算法點云配準(zhǔn)三維重建效果圖

五、ICP算法的原理與計算步驟

傳統(tǒng)ICP算法的基本原理就是在擬匹配的目標(biāo)點云Q和源點云P中，分別按照預(yù)先設(shè)置的約束條件，找到最鄰近的點（pi，qi），最后計算出源點云和目標(biāo)點云點對的最優(yōu)匹配參數(shù)R和T，并且要讓點對之間的誤差函數(shù)最小。假定點對之間的誤差函數(shù)用E（R，T）表示，其計算表達(dá)式如公式（1）所示：

公式中qi為目標(biāo)點云Q中與原點云中的一點pi對應(yīng)的最近點，pi即為原點云P中的一點，n表示最鄰近點對的數(shù)量，R為旋轉(zhuǎn)矩陣，T為平移向量。

（一）ICP算法的計算步驟

1.取點pi∈P，P為源點云集；

2.通過計算，尋找對應(yīng)點qi∈Q，Q為目標(biāo)點云，使得||qi-pi||=min；

3.計算平移矩陣T和旋轉(zhuǎn)矩陣R，使得誤差函數(shù)的值最小；

4.根據(jù)上一步求得的平移矩陣T和旋轉(zhuǎn)矩陣R，對pi進(jìn)行平移和旋轉(zhuǎn)變換，獲得新的對應(yīng)點集

5.計算對應(yīng)點集qi與新的對應(yīng)點的平均距離；

6.如果d大于預(yù)設(shè)的最大迭代次數(shù)或者小于預(yù)先給定的閾值，則停止迭代計算。如果不滿足以上條件，則返回第2步計算，直到滿足收斂。

（二）ICP算法的關(guān)鍵

1.原始點集的采集手段，采集的具體方法有：均勻采樣、隨機(jī)采樣和法矢采樣。

2.確定對應(yīng)點集：點到點、點到投影、點到面。

3.計算變化矩陣，具體包括：四元數(shù)法、SVD奇異值分解法

六、基于誤差閾值控制的ICP優(yōu)化算法

ICP算法點集P{Pi,i=1,2,…,N}表示空間第一個點集，目標(biāo)點集Q的坐標(biāo)為為在第k次迭代中，計算與源點集P坐標(biāo)中相對應(yīng)的點的坐標(biāo)，設(shè)計并計算P與Qk之間的變換矩陣，并對原變換矩陣進(jìn)行更新，直到源點與目標(biāo)點的數(shù)據(jù)間平均距離小于給定值τ。算法的關(guān)鍵是求解P與Qk之間的變換矩陣，即求R，T兩個矩陣，滿足誤差函數(shù)式（2）最小：

這種算法是合理的，因為總體點集誤差的倍數(shù)應(yīng)該小于不匹配部分的

容許誤差倍數(shù)，即總體上的誤差控制要嚴(yán)格，局部點集的誤差控制可以比較大。因為在實際的配準(zhǔn)問題中，確實會存在部分點完全無法匹配的情況，此時局部點集的誤差會很大。而本優(yōu)化算法可大大節(jié)約循環(huán)次數(shù)，減少運算代價。圖2為基于誤差閾值控制的ICP算法點云配準(zhǔn)三維重建效果圖。

圖2 I CP優(yōu)化算法點云配準(zhǔn)三維重建效果圖

說明在上述的容許誤差倍數(shù)下，不匹配點占總點數(shù)的比率小于等于25%才能獲得能接受的配準(zhǔn)效果。顯然，t越大，即總體配準(zhǔn)的接受容許度越大，比率越大，越能容許更多的不匹配點；K越大，即不匹配點的誤差很大，則比率越小，只能容許較少的不匹配點。

七、結(jié)果

利用三維掃描儀獲得文物點云數(shù)據(jù)，利用 ICP 算法進(jìn)行初步配準(zhǔn)，得到初始模型，由圖1發(fā)現(xiàn)重建后的數(shù)字化文物出現(xiàn)了變形效果。對 ICP 算法通過誤差閾值控制等方法進(jìn)行優(yōu)化后，在實驗中發(fā)現(xiàn)優(yōu)化后的算法文物的配準(zhǔn)速度和精度都得到大幅度提升。實驗結(jié)果表明ICP 算法要獲得最優(yōu)效果，還有很長的路可走，可進(jìn)行多種優(yōu)化，ICP算法優(yōu)化后獲得的三維模型比三維掃描儀自帶的點云自動配準(zhǔn)軟件獲得的模型更加精確。