張少玉

（西安工程大學　西安　710048）

1　引言

隨著經濟的發展、人們生活水平的提高，三維模型被廣泛應用于醫療、娛樂、教育等行業，由此帶來三維建模技術的發展，但是由于當前技術的局限性，并不能獲得完整的點云數據，每次只能獲得某個角度的點云數據，因此就需要多方位地進行三維掃描，這就使得在建模之前必須先進行點云配準，即將不同視角下的點云變換到同一坐標系下，它是圖像處理、虛擬現實、測繪工程等領域的一項關鍵技術，點云配準的精度和速度直接影響三維建模的精度和速度。

目前點云配準算法中，最常用的就是Besl［1］和Chen［2］等分別提出的迭代最近點（Iterative Closest Point，ICP）算法，該算法是通過兩片點云的對應點不斷迭代確定旋轉和平移矩陣，直到滿足收斂條件，但是使用該算法時，若兩片點云的初始姿態不好，則會形成局部最小化，造成迭代不能收斂到正確的結果；而且對應點的選取速度較慢。因此為了克服ICP算法自身的部分缺陷，許多研究人員對其進行了改進，其中很多人把點云的剛性特征應用進來，對其改進。點云的剛性特征有曲率、點法向與鄰域點法向的夾角、點法向、局部張量、點與鄰域重心的距離等［3～4］。特征法首先提取點云的剛性特征，利用特征進行粗配準，然后使用特征改進的ICP算法進行精配準。戴靜蘭等［5］、Yang等［6］使用曲率特征進行配準，但是估計曲率時需要用到近鄰點，就會受到噪聲的影響，而且估計曲率需要消耗大量的時間。Jiang等［7］使用夾角特征進行配準，雖然其方法提高了點云配準的誤差收斂速度，但是計算和比較點之間的K維夾角特征耗費了不少時間。RUSU等［8］提出了一種基于法矢量的特征直方圖，根據法矢量建立局部坐標系，用鄰近點的距離關系和法矢量夾角的直方圖表示該點的特征，但是該方法受噪聲干擾明顯，而且計算量較大。

本文提出一種使用尺度不變特征轉換（Scale Invariant Feature Transform，SIFT）特征點的改進方法。該方法的基本要求就是兩片點云數據有足夠的重合度。該方法直接使用求得的源點云的特征點與體素柵格下采樣后的目標點云進行配準，減少了計算特征描述子的環節，從而提高了配準速度，并通過隨機采樣一致算法（Random Sample Consensus，RANSAC）去除錯誤匹配點對，來提高配準的精度。雖然王程冬等［9］也提出使用SIFT特征進行點云配準，但是其方法是在二維圖像中進行SIFT特征檢測，通過映射關系來獲得三維對應特征點，而本文是直接在三維點云數據中進行SIFT特征點檢測，避免了因為映射關系可能會找到錯誤對應特征點的可能，同時也大大減少了算法的運行時間。

2　相關理論

2.1　體素柵格下采樣

由于獲取的點云數據數量比較大，若是全部用來做實驗，則會影響后續實驗的速度，因此采用部分點云來代替所有的點云來提高速度。PCL中的VoxelGrid類便可實現此目的，其通過輸入的點云數據創建一個三維體素柵格（可把體素柵格想象成微小的空間三維立方體的集合），然后在每個體素內用體素中所有點的重心來近似顯示體素中其他點。步驟如下：

1）立方體邊長 L 的確定［10～11］。 L 的確定非常關鍵，在L過大的情況下會降低搜索效率，如果L過小，則會出現很多空的柵格。小立方體柵格邊長為：L=α3s c，其中，α是用來調節小立方體柵格的邊長的比例因子，s是比例系數，c是小柵格中的點云數量。

3）求得每個小柵格的重心實現下采樣。每個柵格的重心為

用(X0，Y0，Z0)代表該小柵格中的所有點，實現點云的下采樣，達到精簡點云數據的目的。

通過體素柵格下采樣后，點云的數量減少了，但是點云的形狀特征并未發生變化，因此在點配準之前通過此方法來提高配準速度。如圖1所示，（a）為原點云數據，（b）為體素柵格下采樣后的數據，可以看出點云的形狀保持不變，只是顯得稍微稀疏。

圖1　體素柵格下采樣結果

2.2　SIFT算法

SIFT算法［12］是Lowe DG提出的一種基于尺度空間的圖像局部特征描述算法。雖然它只能描述圖像的局部特征，但是該特征對視角變化、仿射變換、噪聲保持一定的穩定性，對旋轉、尺度縮放、亮度變化保持不變性，其原理如下：

1）尺度空間的生成

把原圖像 I(x，y)與高斯核G(x，y，σ)的卷積定義為一幅圖像的尺度空間L(x，y，σ)：

其中，G(x，y，σ)是尺度可變高斯函數，σ為尺度空間因子，其決定圖像的平滑程度，(x，y)為圖像像素坐標。

2）檢測尺度空間極值點

其中，D(x，y，σ)為高斯差分函數，引入該函數是為了有效檢測出尺度空間中的穩定特征點，式（8）中，k為常量。在檢測極值點時，每個像素點要與26個點（同尺度的相鄰的8個像素點和其上下相鄰尺度的9×2個點）進行比較，如果該像素點的DoG（Dif-ference ofGaussian）算子在這26個鄰域中為最大或最小，則該點為特征點。

3）精確定位極值點

通過擬合三維二次函數以精確定位特征點的位置和尺度（達到亞像素精度），同時去除低對比度的特征點和不穩定的邊緣響應點，以增強匹配穩定性，提高抗噪聲能力。對尺度空間DoG函數進行曲線擬合，利用DoG函數在尺度空間的泰勒展開式：

其中，向量 X=(x，y，σ)，對式（5）進行求導并使一階導數為0，可得特征點精確位置的偏移向量：

4）為每個特征點指定方向參數

利用特征點鄰域像素的梯度方向分布特性為每個特征點指定方向參數，使算子具備旋轉不變性。每個像素的梯度模和方向分別為

在以特征點為中心的鄰域窗口內采樣，并用直方圖統計鄰域像素的梯度方向。梯度直方圖的范圍是0°～360°，每10°為一柱，以梯度模 M作為貢獻權重，即離中心點越遠的鄰域其對直方圖的貢獻就越小。

至此，圖像的特征點已檢測完畢，每個特征點有三個信息：位置、所處尺度和方向。如圖2所示，是通過SIFT算法對兩幅圖像進行檢測的結果。

圖2　兩幅圖像SIFT特征檢測結果

因此，PCL中的SIFTKpoint類將二維圖像中的SIFT算子調整移植到了3D空間中，該類可以計算出點云的SIFT特征點，使SIFT算子實現了在3D空間中的直接應用。如圖3所示，是在一片點云中求得SIFT特征點的結果，圖中小圓點部分為人體上半身的點云數據，方形點就是檢測出來的SIFT特征點。

圖3　點云的SIFT特征點檢測結果

2.3 RANSAC算法

RANSAC是一種隨機參數估計方法，于1981年由 Fischler和Bolles［13］最先提出，主要思路是通過采樣和驗證的策略，求解大部分樣本都能滿足的數學模型參數。具體步驟為

針對應用需求，綜合考慮各種通訊方式的傳輸帶寬、覆蓋范圍、實時性、資費，最終選擇采用GPRS/3G/衛星通信相結合的多模傳輸方式。主控制器的數據發送線程實現系統的多模數據發送功能，采用wvdial腳本和ppp腳本配置華為E261聯通3G無線上網卡和SIM900A型GPRS模塊連接網絡[13]，衛星通信模塊采用ORBCOMM公司的OG2衛星調制解調器，在3G和GPRS無網絡的情況下系統自動切換至衛星通信模式，通過串口將定位和報警信息數據包發送給衛星通信模塊，經衛星通信模塊發送至服務器。

1）從樣本集中選取4對匹配點作為內點集合，使用最小方差估計算法對這個集合計算模型參數；

2）用1）中得到的模型去測試所有的其它匹配點對，如果小于設定閾值，則加入內點集合；

3）如果迭代次數大于設定的閾值，則退出；否則重復步驟1）和2），選取內點個數最多的一組作為合格的匹配點集，并根據新的內點集合重新估計模型。

如圖4所示，是RANSAC算法在二維數據集中的簡單應用。圖4（a）圖既包含了局內點又包含了局外點，圖4（b）中圓形為局內點，方形為局外點，直線就是基于RANSAC得到的適應數據的模型。

圖4　RANSAC算法原理示意圖

3　本文配準方法

3.1　ICP算法

ICP算法是一個經典的點云配準算法，它的基本原理是不斷地尋找對應點集和求解變換關系，直到找到源點云和目標點云之間的旋轉矩陣R和平移向量T，最終使源點云與目標點云滿足某種條件下的最優匹配。

設源點云為 P={pi|pi∈R3，i=1，2，…，N} ，目標 點 云 為 Q={qj|qj∈R3，j=1，2，…，M} ，其 中N≤M。

步驟如下：

2）在目標點云Q中尋找源點云P每個點 pi的最近點pi'；

3）計算出源點云和目標點云的剛體變換矩陣R和T；

4）更新源點云P，計算得出P'=Rpi+T；

5）計算均方誤差：

6）若dm-dm+1＜γ或者達到迭代次數，則停止迭代；否則反復執行2）～5）。

3.2　方法步驟

隨著掃描技術的發展，獲取的點云數量越來越大，這就對后期的處理帶來不便，而經典的ICP算法計算效率不高，而且花費時間較多，因此本文提出一種改進方法。首先對兩片點云進行體素柵格下采樣，通過減少點云的數量來減少運行時間，其次用源點云的SIFT特征點與目標點云進行配準，并用RANSAC算法去除錯誤配對點，為了提高配準的精度，進行變換估計后，保留源點云，重復上述過程直到滿足設定條件，步驟如下：

1）設定閾值λ＞0，用來判斷程序是否終止；

2）對兩片點云進行體素柵格下采樣；

3）求取源點云的SIFT特征點。首先定義SIFT特征點檢測；其次設置尺度相關參數，包括點云對應體素柵格中體素的最小尺寸，檢測特征點時體素空間尺度的數目和為在每一個體素空間尺度下計算高斯空間的尺度時所需要的參數；然后設置候選特征點應有的對比度下限；最后輸入點云，進行計算，對結果進行保存；

4）調用ICP算法，用保存的源點云SIFT特征點集與下采樣后的目標點云進行配準；

5）采用RANSAC算法來剔除錯誤的匹配點對；

6）保留變換后的源點云，重復2）～5），若歐氏適合度評分（源點云到目標點云對應點對的距離平方和）（其中n為對應點對的數目，和是一對對應點中的兩個點）小于給定的閾值λ，則一直重復2）～5），否則退出。

本文方法流程圖如圖5所示。

圖5　本文方法流程圖

4　實驗結果與分析

本文用Kinect采集到的人體數據來驗證本文方法的有效性。在圖6中，（a）為采集到的兩片點云數據，紅色為目標點云，綠色為源點云，（b）為直接采用ICP算法進行配準的結果，可以看到（b）圖中的源點云與（a）中稍有移動，但是不太明顯，使得配準后的兩片點云并沒有成功融合在一起；（c）為采用本文方法提取的源點云的SIFT特征點，與原數據相比點云數量減少了很多，（d）為采用本文方法配準的結果，可以看到兩片點云成功配準，與（b）相比效果良好。

圖6　實驗結果

表1是ICP算法與本文方法在時間和精度上的比較，可以看到本文方法在時間上比ICP算法減少了，歐氏適合度評分也比ICP算法小，因此本文方法取得了令人滿意的效果。

表1　ICP算法與本文方法比較

5　結語

針對ICP算法迭代耗時、精度較差的問題，本文提出結合SIFT特征點的方法對其進行改進。首先求出源點云的SIFT特征點，然后用該特征點集與目標點云進行配準，并通過RANSAC算法去除錯誤匹配點對，然后保留變換后的源點云進行重復，滿足設定條件后退出程序。經實驗表明本文方法得到了較好的配準精度和收斂速度。在實際應用中，有較高的使用價值。但是對于SIFT特征不明顯的點云，配準效果較差，這也是本文下一步的研究方向。

［1］Besl P J，Mckay N D.A method for registration of 3D shapes［J］.IEEE Transactionson Pattern Analysisand Machine Intelligence，1992，14（2）：239-256.

［2］Chen Y，Medioni G.Objectmodeling by registration of multiple range images［C］//The 1991 IEEE International Conference on Robotics and Automation，Sacramento，CA，USA，1991：2724-2729.

［3］Wang Sen，Wang Yang，Jin Miao，etal.Conformalgeometry and its applications on 3D shapematching，recognition，and stitching［J］.Medical Engineering&Physics，2007，29（7）：1209-1220.

［4］?str?mK，Karlsson J，EnquistO，etal.Automatic feature point correspondences and shape analysiswithmissing data and outliers using MDL［J］.Image Analysis，2007，4522（5）：21-30.

［5］戴靜蘭，陳志楊，葉修梓.ICP算法在點云配準中的應用［J］.中國圖像圖形學報，2007，12（3）：517-521.DAIJinglan，CHEN Zhiyang，YE Xiuzi.The Application of ICP Algorithm in Point Cloud Registration［J］.Journal of Image and Graphics，2007，12（3）：517-521.

［6］Yang Shen，Shen Xukun，QiYue，etal.An automated registration method for range images［C］//Proceedings of the 2ndInternationalConferenceonTechnologiesfor E-Learning and Digital Entertainment.Heidelberg，Berlin，Germany：Springer-Verlag，2007：772-783.

［7］Jiang Jun，Chen Jun，Chen Xinglin.Registration for 3-D point cloud using angular-invariant feature［J］.Neuro Computing，2009，72（16-18）：3839-3844.

［8］RUSU R B，BLODOW N，BEETZM.Fast point feature histograms（FPFH）for 3D registration［C］//IEEE International Conference on Robotics and Automation，May 12-17，2009，Kobe，Japan，2009：3212-3217.

［9］王程東，程筱勝，崔海華，等.SIFT算法在點云配準中的應用［J］.傳感器與微系統，2012，31（2）：149-152.WANG Chengdong，CHENG Xiaosheng，CUI Haihua，et al.The Application of SIFTAlgorithm in PointCloud Registration［J］.Transducer and Microsystem Technolodies，2012，31（2）：149-152.

［10］YU H，WANG R，CHEN J，et al.Saliency computation and simplication of point cloud data［C］//Proc.2012 2nd International Conference on Computer Science and Network Technology（ICCSNT 2012）.Changchun，China：IEEEPress，2012：1350-1353.

［11］ZHAO X，WEN MH.Kd-tree based non-uniform simplication of 3D point cloud［C］//Proc.2009 3rd International Conference on Genetic and Evolutionary Computing（ICCSNT 2009）.Guilin，China：IEEE Press，2009：339-342.

［12］Lowe D G.Distinctive image features from scale-invariant key points［J］.International Journal of Computer Vision，2004，60（2）：91-110.

［13］Fischler MA and Bolles R C.Random Sample Consensus：A Paradigm for Model Fitting with Applications to Image Analysis and Automated Cartography［J］.Communicationsof the ACM，1981，24（6）：381-395.