李紅彥，王韓波

(建設綜合勘察研究設計院有限公司，北京 100007)

隨著三維激光掃描技術的發(fā)展，利用三維激光掃描儀采集信息，構建三維模型成為了熱門的課題。三維激光掃描技術采用高速激光掃描，能夠快速、精確地獲取物體表面的信息，主要用于重構物體三維模型。由于受到觀測環(huán)境和觀測方向等影響[1]，無法一次性地獲得物體的所有的點云數(shù)據(jù)，因此不同視角下點云數(shù)據(jù)的配準成為了三維建模中的關鍵技術，直接影響了最終的重合結果以及模型精度。配準算法作為三維掃描技術的核心，已然成為了當今國內外研究的熱點之一。本文利用主方向貼合法和最近點迭代算法(ICP算法)作為點云數(shù)據(jù)的配準算法，對點云數(shù)據(jù)進行配準，驗證編碼的正確性。最后，對實際案例運用該算法進行點云數(shù)據(jù)配準，得出配準結果和配準精度。

1 配準算法的發(fā)展以及研究現(xiàn)狀

最初配準算法指的是平面圖像的配準，而平面圖像的配準也只是實現(xiàn)曲線的配準。隨著研究的深入，配準算法實現(xiàn)功能也越發(fā)強大。配準算法運用于三維空間，從二維空間中的算法理論照搬到三維空間進行計算，然而，兩個空間的事物必然存在一定的差距，算法無法適用于其中[2]。為解決這一問題國內外專家學者提出了諸多配準方法，如：迭代配準算法、基于曲面的配準算法、基于幾何特征的配準算法和主方向貼合法。迭代配準算法，最具代表性的是最近點迭代(ICP)算法，1992 年由Besl和Mckay提出[3]。該算法以四元數(shù)算法為基礎，利用搜索算法尋找兩組對應點云的最近點，采用歐式距離作為目標函數(shù)，通過不斷地迭代逼近目標函數(shù)的最小值，求得變換矩陣。文獻[4]在ICP算法的基礎上做出了改進，提出了一種基于迭代最近直線(ICL)和迭代最近三角片面(ICT)的算法。該算法對兩個配準點集中的點進行連接或者三角化操作，然后找出幾何特征相似線段或者三角片，然后用四元數(shù)法對目標函數(shù)求解，求得旋轉矩陣。周儒榮等[5]提出了一種基于幾何特征點云配準算法，使對應關系不明確的點云數(shù)據(jù)可以快速、有效地配準。王育堅等[6]提出了主方向貼合法，能夠快速縮小點云的旋轉和平移錯差，且對點云的大小沒有特殊要求。

2 配準算法在三維建模中作用

通常情況下重構物體的三維模型時，需要對物體進行全方位掃描。由于受到觀測環(huán)境、觀測方向和物體自身形狀的影響，無法一次性地獲得物體的所有點云數(shù)據(jù)。因此，點云數(shù)據(jù)的配準成為了三維建模中的關鍵技術，直接影響了最終的重合結果以及模型精度。建立物體的三維模型如圖1所示。

圖1 三維建模流程

圖中點云去噪是采用濾波平滑的方法去掉離散點與噪聲點，點云粗配準中采用主方向貼合法，用matlab語言實現(xiàn)該算法，然后對點云數(shù)據(jù)進行配準，以驗證編碼的正確性。選取ICP算法作為精配準算法，在matlab上進行實現(xiàn)，再對已經(jīng)粗配準的點云數(shù)據(jù)進行配準，驗證編碼的正確性。

3 基于主方向貼合法點云數(shù)據(jù)的粗配準

為了減小點云間旋轉、平移的錯位，使得精確配準擁有良好的初始位置，不至于在配準過程中不斷趨向錯誤的方向。本文研究的方法為主方向貼合法，其具有簡單、快捷、易于實現(xiàn)的特點。

3.1 主方向貼合法

3.1.1 主方向貼合法介紹

每個點云在空間上都存在一個主方向，該主方向可以用所計算的點云中所有點的特征向量求得，還能得到和主方向垂直的兩個次方向。對于重疊率較大的數(shù)據(jù)，配準的問題就轉換為坐標變換的問題，只需要把兩個坐標系變換一致[6]。

主方向有正反兩個方向，有可能會出現(xiàn)配準后點云相差180°的情況，所以在配準前還應該設置一個值，使向量指向同一側。本文是通過計算兩個點云對應的參考坐標系的坐標軸相點乘，如果它們的值小于所設定的值，那么認為坐標軸的方向指向不同側，需要調整其中一個坐標軸的方向180°[7]。待方向確定后，根據(jù)坐標系的坐標軸的方向向量，求得旋轉矩陣，然后再求出平移矩陣，作為粗配準的結果。

為了達到良好的配準效果，本文采用了人機結合的方式，在算法實現(xiàn)前，先粗略地提取兩個點云可以重疊的部分，這種方法適用于點云數(shù)據(jù)重疊區(qū)域小的情況，可以減少噪音的影響。

3.1.2 主方向貼合法算法流程

(1)首先讀取參考點云與目標點云；

(2)分別粗略地提取兩個點云中可以重疊的部分；

(3)計算點云的重心；

(4)對點云進行中心化處理；

(5)分別求算點云的特征值與特征向量，特征向量依次作為x、y、z軸，建立坐標系；

(6)設置一個閾值，確定坐標軸方向指向同一側；

(7)計算點云之間的旋轉矩陣、平移矩陣，結束[8]。

3.2 算法的實現(xiàn)

根據(jù)上述流程，利用matlab編寫主方向貼合法實現(xiàn)代碼，所用的數(shù)據(jù)為美國斯坦福大學的深度圖像數(shù)據(jù)庫中標準參考數(shù)據(jù)，數(shù)據(jù)點為400 097 個，數(shù)據(jù)讀取格式為asc格式。

算法運行后，得出的旋轉矩陣R為：

(1)

平移矩陣T為：

(2)

點云數(shù)據(jù)配準前，顯示圖像如圖2所示，利用主方向貼合法配準之后如圖3所示。

圖2 點云粗配準前三維顯示效果圖

圖3 點云粗配準后三維顯示效果圖

由圖可見，兩個點云數(shù)據(jù)的重疊區(qū)域較大，可以直接對整個數(shù)據(jù)進行特征值和特征向量的提取，配準之后，點云的重疊效果良好，滿足精確配準的要求。主方向貼合法的優(yōu)點在于算法思想簡單，便于編程實現(xiàn)，而且對于大量的數(shù)據(jù)，該算法可以很快地計算出結果該算法僅用了0.095 986 s，但它的缺點也顯而易見，只適用于那些點云數(shù)據(jù)重疊率較大的情況，如果重疊區(qū)域太小，噪音對點云主方向的影響較大，配準后的效果不佳，僅僅是適當?shù)乜s小了點云之間錯位誤差，但仍然達不到精配準的要求。

4 基于ICP算法的點云數(shù)據(jù)的精配準

ICP算法自提出以來，通過不同學者的研究，已經(jīng)日益趨于成熟。其以迭代的方式逼近最佳的成果，在理想的時間下得出人們滿意的結果。由于它的算法特性，也決定了它對數(shù)據(jù)集的初始位置需要一個較高的要求，不然則會出現(xiàn)配準錯誤。這就需要粗配準為ICP算法提供一個良好的初始位置，而主方向貼合法的配準結果也很好地滿足了這一要求[9]。

4.1 ICP算法

4.1.1 ICP算法介紹

Besl等在1992 年提出了最近點迭代算法(ICP算法)這種算法不需要精確的控制點，它只是對每次迭代中的目標函數(shù)中的最近點控制點，用于估算變換矩陣的參數(shù)。迭代計算過程中，以兩次迭代目標函數(shù)的值得變化小于某一個閾值為結束。

對于數(shù)據(jù)集X，其中每一個數(shù)據(jù)點在點云數(shù)據(jù)Y中都可以計算找到對應的點，將這些點組合起來形成對應點集Yk，這需要運用到最近點算法，將這種操作記為：

Yk=C(X,Y)

(3)

對于對應點集X、Yk，運用四元數(shù)算法估算配準參數(shù)，操作記為：

(H,d)=sysf(X,Yk)

(4)

對于點云數(shù)據(jù)X的每一個數(shù)據(jù)點，通過變換矩陣H的旋轉平移變換，操作記為：

H(X)=R(X)+T

(5)

上述操作構成了ICP算法的基本操作，ICP算法的基礎為尋找最近點，其思路為迭代逼近最佳值，核心為四元數(shù)算法計算配準參數(shù)。

4.1.2 ICP算法流程

(1)尋找最近點：由公式Yk=C(X,Y)對點云數(shù)X中的每個數(shù)據(jù)點，計算其在點云數(shù)據(jù)Y中的最近點，構成點集Yk；

(3)更新數(shù)據(jù)集：由公式H(X)=R(X)+T，利用變換矩陣H對數(shù)據(jù)集X進行更新；

(4)迭代計算：對更新后的數(shù)據(jù)集重復1、2操作，得到新的配準參數(shù)H′和估計誤差。如果連續(xù)兩次計算得到的估計誤差的變化小于某一閾值時，即為‖d-d′‖?≤τ，則停止迭代，輸出結果。

4.2 算法的實現(xiàn)

根據(jù)上述流程，利用matlab編寫ICP算法，部分代碼如下：

function Yk=C(X0,Y) %X0為目標數(shù)據(jù)經(jīng)過變換矩陣變換后的數(shù)據(jù)集

Y0= delaunayn(Y'); %Y0為對參考數(shù)據(jù)Y進行三角剖分

k = dsearchn(Y',Y0,X0'); %利用matlab中自帶的尋找最近點的函數(shù)，

Yk = Y(:,k); %Yk為Y中對應X中數(shù)據(jù)點的最近點

Rqr=[q0^2+q1^2-q2^2-q3^2 2*(q1*q2-q0*q3) 2*(q1*q3+q0*q2);2*(q1*q2+q0*q3) q0^2-q1^2+q2^2-q3^2 2*(q2*q3-q0*q1);2*(q1*q3-q0*q2) 2*(q2*q3+q0*q1) q0^2-q1^2-q2^2+q3^2]; %特征向量構成的旋轉矩陣

……

在粗配準的基礎上進行，算法運行后，得出的旋轉矩陣R為：

(6)

平移矩陣T為：

(7)

通過上述算法，設置的閾值為0.000 000 5，經(jīng)過了11次迭代，配準結果如圖4所示。

圖4 點云數(shù)據(jù)精配準后三維顯示效果圖

ICP算法思想在于迭代，控制閾值的大小，決定了結果的精度、迭代次數(shù)以及運算時間?？梢?，它們之間的關系式相互矛盾的，要想得到較高的精度，將閾值設置得盡量地小，但迭代次數(shù)隨之增加，運算時間也變長；同樣的，為了節(jié)省時間，縮小迭代次數(shù)，卻會犧牲結果的精度。這就需要根據(jù)要求確定合適的閾值，使得精度、運算時間和迭代次數(shù)都可以達到一個可以接受的狀態(tài)。

5 實例分析

依據(jù)文章中所提的數(shù)據(jù)采集的方法，數(shù)據(jù)采集的對象為鏡湖邊的焦作路礦學堂大門，通過考察后設計的測量方案中決定采取兩站對物體進行測量，分別位于焦作路礦學堂大門的正面和背面。實地測量時，三維激光掃描儀開始工作，采集到的數(shù)據(jù)為焦作路礦學堂大門以及其周圍事物的空間信息，得到的焦作路礦學堂大門的點云數(shù)據(jù)在軟件上的顯示如圖5、圖6所示。按照上述方法，首先提取兩份點云數(shù)據(jù)的重疊區(qū)，大致為大門內側，第二，運用RealWorks Survey Advanced 6.4對點云數(shù)據(jù)進行處理；第三，利用主方向貼合法對數(shù)據(jù)進行粗配準；第四，利用ICP算法對數(shù)據(jù)進行精配準；最后，對最終的配準結果，進行評定。該數(shù)據(jù)最終配準后的結果進行精度評定，得到的配準誤差為0.048 7 mm。

圖5 焦作路礦學堂背面三維顯示

圖6 焦作路礦學堂正面三維顯示

首先，主方向貼合法主要適用于重疊率較大的點云數(shù)據(jù)，對于重疊率小的數(shù)據(jù)，其主方向的生成守干擾因素較大，必須先進行人工處理，即粗略地選取點云數(shù)據(jù)中可以重疊的區(qū)域。本文實例所采用的數(shù)據(jù)十分龐雜，不僅包含了對象物體的空間數(shù)據(jù)，還有許多其他事物的空間數(shù)據(jù)，而重疊區(qū)域僅為路礦學堂大門內側的一部分，所占比例極小，如果直接用于粗配準，誤差必然很大，因此，需要先選取出點云數(shù)據(jù)中可以重疊的區(qū)域。

其次，主方向貼合法適用于物體表面不規(guī)則的情況，例如雕像等。對于物體表面光滑的情況，該算法顯現(xiàn)出明顯的不足，例如豎直墻面等。

最后，對于兩個點云數(shù)據(jù)，如果它們的點的分布規(guī)則不同，比如其中一個是均勻分布的點，另一個則是不規(guī)則分布的點，這就對它們的重心的選取產(chǎn)生了影響，進而對點云數(shù)據(jù)的配準產(chǎn)生了影響。重心選取的誤差，使得點云數(shù)據(jù)雖然得到了較為正確的旋轉，但在平移以后出現(xiàn)了很大的偏差，所提供的點云的初始迭代位置無法滿足精確配準的要求，進而是得精配準后出現(xiàn)了這種圖像交叉的現(xiàn)象。

6 結 論

點云數(shù)據(jù)的配準是三維建模中的一項關鍵技術，配準的結果好壞關系到了構建模型的完整性以及精確性，配準效果不良會導致物體的信息數(shù)字化的速度下降，將會影響整個三維數(shù)據(jù)處理工作，最終影響整個三維建模的質量。由于主方向貼合法和ICP算法有思路清晰、算法簡單易于編程實現(xiàn)等特點，本文選取了這兩種算法進行了matlab的實現(xiàn)，通過調試良好后對采集的數(shù)據(jù)進行了配準。文中精度評定是根據(jù)點云數(shù)據(jù)中配準點未達到配準要求的點所占總點數(shù)的比例來判定的。從配準結果中可看出主方向貼合法適用于重疊率較大的點云數(shù)據(jù)，對于重疊率小的數(shù)據(jù)，其主方向的生成守干擾因素較大，必須先進行人工處理，即粗略地選取點云數(shù)據(jù)中可以重疊的區(qū)域。ICP算法只是對每次迭代中的目標函數(shù)中的最近點最為控制點，用于估算變換矩陣的參數(shù)。迭代計算過程中，以兩次迭代目標函數(shù)的值得變化小于某一個閾值為結束。因此，該算法對于初次迭代時點云的相對實際位置的要求較高。如果點云的初始相對位置相差很大，那么迭代很難保證單調收斂于最佳結果，極有可能出現(xiàn)局部精確配準，實際相差甚遠的效果。綜上所述文章的兩種配準算法均得到了滿意效果。