馬偉麗，2，王健，孫文瀟

(1.山東科技大學，山東 青島 266590；2.山東省水利勘測設(shè)計院，濟南 250101)

0 引言

在物體表面三維重構(gòu)[1]中，點云數(shù)據(jù)配準是最為重要的步驟。使用三維激光掃描技術(shù)[2-3]，可以得到被測物體表面點云數(shù)據(jù)，通過在多個視角下測量的點云數(shù)據(jù)，然后對多測站數(shù)據(jù)進行配準，最終獲得完整的三維物體模型。點云數(shù)據(jù)配準精度，對三維物體模型重構(gòu)和應用有著直接的影響。

目前，國內(nèi)外提出了很多數(shù)據(jù)配準的算法，其中使用最為廣泛的算法就是1992年Besl等[4]提出的迭代最近點算法(ite-rative closest point，ICP)以及它的改進算法[5-6]。為了使數(shù)據(jù)配準的結(jié)果更加準確，ICP算法使用時必須要滿足2個條件：點云之間存在包含關(guān)系、點云之間初始位置不可以相差過大。數(shù)據(jù)配準常用方法有：特征點提取法[7-10]，根據(jù)曲率特征、法向量等信息提取特征點，由得到的特征點對完成配準；質(zhì)心重合法[11]，計算點集的質(zhì)心，并將2個點集作相對于質(zhì)心的平移；標志點法[12-13]，人工粘貼標志點，通過標志點配準。上述配準方法，對點云間位姿和噪聲程度有嚴格要求，同時容易陷入局部最優(yōu)。

針對上述點云數(shù)據(jù)在配準中存在的問題，本文采用散亂點云建立的曲率信息研究點云的配準方法，在基于曲率特征配準的基礎(chǔ)上，引入現(xiàn)在比較成熟的模擬退火法(simulated annealing，SAA)對點云數(shù)據(jù)拼接誤差的參數(shù)進行尋優(yōu)，避免局部最優(yōu)。因此提出基于隨機抽樣一致性算法(random sampling consensus，RANSAC)提取曲率特征點，然后用距離最近原則尋找對應點對，最后使用模擬退火法防止陷入局部最優(yōu)完成最終配準。

1 經(jīng)典ICP算法

經(jīng)典ICP算法[14]利用最小二乘最優(yōu)匹配原理，通過迭代進行點云之間的剛體變換。首先已知兩塊待配準的重疊點云M和N，其中M為待配準點云，N為參考點云。M點集中的每一點Mi以最小距離原則在N中尋找對應點，對應點構(gòu)成新的點集。所有對應點對的拼接誤差[15]

(1)

式中：Mi為目標點集；Ni為待配準點集；n為匹配點對總數(shù)；λ、R、T分別表示點集M與點集N之間剛體變換的縮放參數(shù)、旋轉(zhuǎn)參數(shù)、平移參數(shù)。反復迭代求出滿足式(1)且收斂于給定閾值的轉(zhuǎn)換參數(shù)，即為ICP算法配準的最終目的。ICP算法過程描述如下：

①尋找對應點對M’、N’；

②計算配準轉(zhuǎn)換參數(shù)λ、R、T；

③修正待配準點云M得到新的點云M’；

④計算相鄰兩次迭代點集的距離差值di，點對匹配均方差收斂于閾值τ，即di-di+1<τ，則停止迭代，否則令i=i+1，并返回步驟①。

2 改進ICP算法

2.1 曲率特征點集的提取

數(shù)據(jù)配準時，對于待配準點云M和基準點云N，如果對所有點云進行匹配點的搜索，會非常繁瑣且浪費時間，同時因為噪聲的存在也會對特征點的選取產(chǎn)生影響。本文在進行曲面擬合局部點云時，加入RANSAC算法，以消除噪點的影響，最后利用曲率極值法來提取曲率特征點。

在三維歐幾里得空間中，幾何體結(jié)構(gòu)的特征主要由曲率和法矢量來描述[16]。曲率是一種不隨平移、旋轉(zhuǎn)、縮放變化的特征，該特征可用高斯曲率KG、平均曲率KM、主曲率k進行描述，首先引入曲率度量公式[17]

(2)

(3)

式中：k1代表最大曲率；k2表示最小曲率；α代表度量曲率相似度。通過公式(2)、公式(3)度量曲率相似度，提取出具有相似結(jié)構(gòu)的點云，然后配準2片點云。特征點提取的具體步驟描述如下：

①選任意一點為種子點，選取K領(lǐng)域計算包含的點個數(shù)，計算迭代次數(shù)L[18]由式(4)得出：

(4)

(5)

式中：A為點云數(shù)；a為擬合曲面方程所需最小點個數(shù)，在本文中a=6，P為a個點均為有效點的概率；ε是數(shù)據(jù)的錯誤率，表示局外點與總數(shù)據(jù)量之比。

②對點云任意一點，建立鄰域點集合，設(shè)曲面方程[19]為

(6)

在K鄰域內(nèi)隨機選取a個點，計算Qij的初始參數(shù)。

④重復步驟②～③，直到循環(huán)次數(shù)達L次，找到最大局內(nèi)點，由參數(shù)曲面方程解出最優(yōu)參數(shù)Qij。

(7)

(8)

⑥由求得的高斯曲率與平均曲率可直接求解主曲率

(9)

(10)

⑦判斷該點主曲率k1或k2在對應的主方向上是否為極值，若為極值，則保留該點，進行下一個種子點判斷。重復步驟⑦～⑧，直到遍歷完所有的數(shù)據(jù)。

⑧曲率極值越大特征越明顯。為曲率極值設(shè)定一個閾值ω，大于該設(shè)置閾值則保留曲率特征點，反之刪除。選取曲率特征點集流程圖如圖1所示。

圖1 選取曲率特征點集流程圖

2.2 獲取全局最優(yōu)轉(zhuǎn)換參數(shù)

配準的過程即是求解待配準點云到基準點云的縮放參數(shù)λ、剛性旋轉(zhuǎn)R和平移T的過程。待配準點云M中的A點和基準點云N中的B點，表示的是地球表面物體的同一個點，可以通過縮放、旋轉(zhuǎn)和平移變換把A點和B點重合在一起。A點坐標XA，YA，ZA，B點坐標XB，YB，ZB，轉(zhuǎn)換的公式為：

(11)

在實際測量中，點云的采集不可避免帶入噪聲，雖然根據(jù)曲率特征選取特征點，以距離最近為判斷依據(jù)獲得相對應的特征點對，但是點云間數(shù)據(jù)沒有絕對的一一對應關(guān)系，因此引入模擬退火法，得到使目標函數(shù)最小的最優(yōu)轉(zhuǎn)換參數(shù)λ、R、T，避免配準時出現(xiàn)局部最優(yōu)解。目標函數(shù)的形式多樣化，本文使用拼接誤差公式(1)作為目標函數(shù)。

在1953年，Metropolis[20]等率先提出了模擬退火法。模擬退火法是一種非線性反演，能夠避免使反演陷入局部極大值，是一個不斷尋優(yōu)的過程。在此過程中，擬合度隨迭代次數(shù)的增加呈現(xiàn)一種跳躍起伏的現(xiàn)象，但總體的趨勢是變小或變大，然而正是由于模擬退火允許擬合誤差變大或擬合度變小，進而使得模型從局部的最優(yōu)值中跳出來，最終得到全局的最優(yōu)化模型。因此引入模擬退火法，在點云拼接過程中以拼接誤差Eλ，R，T為目標函數(shù)，進行優(yōu)化求解。

在模擬退火法的迭代過程中，要求溫度隨著迭代次數(shù)的增加而緩慢降低，由冷卻進度表控制溫度t的逐步下降，同時依概率接受惡化解。接受概率參數(shù)是關(guān)于溫度t的函數(shù)，隨著t不斷的降低，接受概率也不斷降低，直到最后不再接受任何惡化解。本文采用雙曲下降型[21]退火方案。模擬退火法尋找轉(zhuǎn)換參數(shù)的最優(yōu)具體解步驟：

①初始化目標函數(shù)模型參數(shù)λ0、R0、T0，確定參數(shù)變化范圍，選擇初始溫度t0=1°。

②計算目標函數(shù)值E0λ0，R0，T0。

③對當前模型參數(shù)進行擾動，產(chǎn)生新的模型參數(shù)λ1、R1、T1。

④計算新模型參數(shù)下的目標函數(shù)值E1(λ1，R1，T1)。

⑤計算目標函數(shù)差ΔE，ΔE=E1-E0。

⑥判斷新模型參數(shù)是否接受，依Metropolis準則[22]為判斷依據(jù)：若ΔE<0則接受；若ΔE>0，則新模型參數(shù)以概率P進行接受。

P=exp-ΔE′/t

(12)

式中：t為溫度。

⑦接受新的模型參數(shù)時，設(shè)置λ0=λ1，R0=R1，T0=T1。

⑧在溫度t下重復一定次數(shù)的擾動接受。

⑨降溫t

tG=t0αG1/a

(13)

式中：t0為初始溫度；G為迭代次數(shù)；α為給定常數(shù)，本文α=1。

⑩重復步驟③至⑨，直到收斂條件滿足。

2.3 改進ICP算法流程

改進配準點云的ICP算法步驟如下：

①讀取需要配準的2個點云：待配準點云M，基準點云N。

②利用RANSAC算法的二次曲面法對其K鄰域進行曲面擬合。

③根據(jù)結(jié)合式(9)、公式(10)計算該點主曲率k1、k2，并判斷是否為曲率極值點，遍歷所有點云數(shù)據(jù)，并刪除小于閾值μ的曲率特征點，得到基準點集M’。

④根據(jù)②、③計算待配準點云數(shù)據(jù)的曲率特征點，得到待配準點集N’。

⑤令為M’0、N’0迭代運算初始點集

⑥以距離最近為依據(jù)，查詢特征點對(M’0、N’0)。

⑦根據(jù)步驟⑥獲得的對應點集使用四元數(shù)法計算，獲取縮放參數(shù)λ、旋轉(zhuǎn)參數(shù)R、平移參數(shù)T。

⑧使用步驟⑥獲得的λ、R、T對點云M利用公式(11)進行變換，得到新的點云。

⑨依模擬退火法判斷是否為全局最優(yōu)，既公式(1)全局最小，是則保留，否則重復⑤至⑧直到拼接誤差為全局最優(yōu)，最終完成配準，算法流程圖如圖2所示。

圖2 算法流程圖

3 實驗驗證與結(jié)果分析

為了驗證本文算法的正確性、有效性和實用性，進行以下2組實驗。實驗數(shù)據(jù)采用斯坦福大學的Horse點云模型和Trimble TX8掃描儀采集某教學樓點云數(shù)據(jù)進行數(shù)據(jù)配準實驗。所選用的2組數(shù)據(jù)都有十多種點云視角數(shù)據(jù)，在每組數(shù)據(jù)中隨機選取2種視角進行配準，并與經(jīng)典ICP算法進行比較。本文算法是在經(jīng)典ICP算法基礎(chǔ)上進行的改進，算法中加入了噪聲點的剔除和避免出現(xiàn)局部最優(yōu)，使其相對于經(jīng)典ICP算法針對部分重疊點云的配準問題得到較好的結(jié)果。實驗在Matlab 2010b軟件環(huán)境下編程實現(xiàn)。

3.1 實驗一

圖3 Horse點云配準結(jié)果

為驗證本文方法的正確性，本文對所選用斯坦福大學的Horse點云數(shù)據(jù)進行配準，并將本文方法與經(jīng)典ICP算法配準結(jié)果進行比較。圖3為Horse點云配準結(jié)果圖，紅色點云為基準數(shù)據(jù)，綠色點云為待配準數(shù)據(jù)，其中圖3(b)為經(jīng)典ICP算法配準結(jié)果，圖3(c)為本文所提改進算法配準結(jié)果。

從圖3可以直觀地看出采用經(jīng)典ICP算法配準結(jié)果較差，兩站點云不能很好地貼合在一起，雖然兩站點云有一部分可以配準在一起，但是仍有大量點云數(shù)據(jù)配準失??；而本文所提算法配準結(jié)果較好，經(jīng)計算對應特征點對距離中誤差為2.7×10-3mm。雖然本文所提算法會增加配準時間，但配準結(jié)果可以體現(xiàn)出本文所改進的算法可以很好地克服經(jīng)典ICP算法容易陷入局部最優(yōu)解的情況。

3.2 實驗二

為驗證本文算法的通用性和實用性，選取Trimble TX8掃描儀采集某教學樓的點云數(shù)據(jù)為實例進行驗證。所選用的某教學樓點云數(shù)據(jù)有十多站點云視角，在實驗數(shù)據(jù)中隨機選取兩站數(shù)據(jù)進行配準，并與經(jīng)典ICP算法進行比較。圖4為兩站點云配準前后對比圖，紅色點云為待配準點云M，綠色點云為基準點云N。未配準的兩站數(shù)據(jù)如圖4(a)所示，用本文算法配準后點云數(shù)據(jù)如圖4(b)所示。

圖4 整體點云配準前后對比圖

本文為驗證該方法的穩(wěn)定性和避免局部最優(yōu)，采用2種算法對某教學樓的2個不同視角的點云進行配準。圖5為2種算法局部配準結(jié)果圖，其中圖5(a)為ICP經(jīng)典算法的精確配準圖，圖5(b)為為本文算法的精確配準圖。

圖5 2種方法局部配準結(jié)果

從圖5可以直觀地看出利用經(jīng)典ICP算法配準后，待配準數(shù)據(jù)和基準點云數(shù)據(jù)之間有傾斜、錯層現(xiàn)象。本文所提算法使兩站點云數(shù)據(jù)相互重合優(yōu)于經(jīng)典ICP算法。因此，利用本文算法可以更為精準地進行配準，同時穩(wěn)健性更強。

為定量描述本文方法的配準效果，在配準后的點云數(shù)據(jù)中選取房屋角點作為特征點，計算配準后對應角點的距離，繪制距離誤差圖，如圖6所示。在獲取到的點云數(shù)據(jù)中，很難找到2個對應的點數(shù)據(jù)表示真實物體的角點，本文利用平面擬合獲取待評價角點周圍的3個平面信息，進而通過3個面相交得到角點坐標。

圖6 配準后對應角點距離殘差

從圖6可以清晰看出利用經(jīng)典ICP算法配準后，大部分檢核點的配準誤差在2 mm左右，但有部分檢核點配準誤差大于5 mm，這是由于通過經(jīng)典ICP算法進行配準，出現(xiàn)局部最優(yōu)情況而產(chǎn)生影響。本文算法在提取的特征點時加入結(jié)合RANSAC算法，從而去除噪聲的影響提取特征點，同時利用模擬退火算法得到最優(yōu)的轉(zhuǎn)換參數(shù)，使配準誤差優(yōu)于2.5 mm，且誤差分布較均勻。實驗配準圖和實驗獲得的對比數(shù)據(jù)，充分表明本文所提配準方法比經(jīng)典ICP算法更穩(wěn)定、精度更高。

4 結(jié)束語

在多視角測得散亂點云數(shù)據(jù)的情況下，利用經(jīng)典的ICP算法得到的配準結(jié)果穩(wěn)定性不高，容易陷入局部最優(yōu)。針對這一問題，本文在經(jīng)典ICP算法的基礎(chǔ)上，引入了一種模擬退火算法尋找全局最優(yōu)的配準方法。該方法的核心思想是結(jié)合RANSAC算法剔除粗差點從而達到穩(wěn)健的效果，采用模擬退火算法避免點云配準陷入局部最優(yōu)使得拼接誤差最小，得到全局最優(yōu)完成數(shù)據(jù)精確的配準。實驗結(jié)果表明，本文數(shù)據(jù)配準算法提高了配準的穩(wěn)定性和配準精度，能夠滿足多視角點云數(shù)據(jù)的配準要求，驗證了本文提出算法的可行性。