基于概率迭代最近點的點云配準算法*

趙夫群 周明全 王 靜

(1.咸陽師范學院教育科學學院 咸陽 712000)(2.西北大學信息科學與技術學院 西安 710127)

基于概率迭代最近點的點云配準算法*

趙夫群1,2周明全1,2王 靜1

(1.咸陽師范學院教育科學學院 咸陽 712000)(2.西北大學信息科學與技術學院 西安 710127)

針對迭代最近點(Iterative Closest Point,ICP)算法中由噪聲帶來的配準效果不佳或失敗的問題,論文提出了一種有效的含噪聲點云的配準算法,即概率迭代最近點算法(Probability Iterative Closest Point,PICP)。首先,建立兩個點云之間的一一對應關系,以提高算法的配準精度;然后,采用高斯概率模型解決剛體變換的問題,由此實現兩個含噪聲點云的精確配準。實驗結果表明,該算法不僅能夠快速準確地實現同一物體不同角度的帶有噪聲點云的配準,還能準確有效地實現剛體碎塊間的斷裂面的完全匹配和部分匹配問題,是一種準確、快速的配準,并能有效避免噪聲和外點的干擾,適用范圍更加廣泛。

點云配準; 迭代最近點; 高斯模型; 概率; 噪聲

Class Number TP391.4

1 引言

圖像配準也叫圖像匹配或圖像對齊,是圖像處理的一項重要技術,是圖像拼接或融合的前提[1～2]。配準(registration)是指將不同成像手段所獲得的同一圖像的地理坐標進行匹配的過程,按照匹配的維度,主要分為二維配準和三維配準兩種類型。點云配準就是一種常用的三維配準技術,是指通過固定一組點云數據的位置將另外一組點云數據向其做剛體變換的過程。目前,點云配準已經在碎片拼接[3]、圖像裁切[4～5]、目標識別[6～7]以及顱面復原[8]等方面得到了廣泛的應用。

在點云配準算法中,應用最為廣泛的是由Besl等[9]提出的迭代最近點(Iterative Closest Point,ICP)算法,該算法步驟簡單且易于實現,但是要求兩個待匹配的初始點集之間存在著包含的關系,并且要求兩個待配準點集的初始位置與真實位置比較接近,若不滿足該條件,將會影響ICP的收斂結果甚至產生錯誤的匹配。針對以上問題,國內外研究者提出了很多改進的ICP算法[10～13]。Jianda Han等[14]提出了一種加強的ICP算法實現了三維環境模的快速和精確配準。Chunjia Zhang等[15]提出了一種基于有界旋轉角的點云配準算法,解決了因旋轉角度變化而引起的配準精度不高的問題。這些算法在一定程度上提高了配準的精度、速度或魯棒性,但是對于存在噪聲的點云數據,其配準效果不佳。2016年,Pavlos Mavridis等[16]通過結合模擬退火搜索算法和稀疏ICP算法來提高配準算法的性能,在抗噪性方面取得了一定的改進效果。Shaoyi Du等[17]提出了一種概率迭代最近點算法,克服了ICP算法中由噪聲帶來的配準失敗問題,在一定程度上解決了m維的含噪聲點云的精確配準問題。

本文針對帶有噪聲的點云數據,提出了一種基于概率迭代最近點(Probability Iterative Closest Point,PICP)的點云配準算法。該算法以基本ICP算法為研究基礎,首先建立兩個點云之間的一一對應關系,這樣不僅可以抑制不重要的點,而且還能保持點對的原始信息不被噪聲干擾,達到較高的配準精度。然后,本文又將高斯概率模型引入ICP算法中,采用高斯概率模型的方差由大到小逐步更新的方法,使得點云配準能夠由粗到細地進行,這樣既實現了粗配準,又實現了細配準,大大提高了帶有噪聲的點云的配準速度和精度。

2 基本ICP算法

(1)

其中,R為旋轉矩陣,t為平移矩陣。

ICP算法在每次迭代過程中,都要在Y中通過尋找距離X最近的點來建立相關性,并實現剛體變換。ICP算法的基本步驟描述如下:

(2)

Step2:計算X和Y的剛體變換,其數學描述如下:

(Rk,tk)=

(3)

重復步驟Step1和Step2直到達到迭代終止條件為止。由于ICP算法是一個局部收斂算法,因此旋轉矩陣和平移矩陣的初值非常重要。好的初值不僅保證算法能收斂到全局最小值,而且能大大提高算法的執行效率。初值的選取可參考文獻[18～19]的選取方法。

3 PICP算法

PICP算法是在基本ICP算法的基礎上引入高斯概率模型來實現的。點集X和Y之間的概率是在每次迭代過程中實時計算得到的。整體來說,因為噪聲點的距離較遠,所以高斯模型計算的概率較小。因此用PICP算法進行配準時,噪聲點對配準結果的影響并不大。那么,兩個帶有噪聲的點集X和Y之間的配準就可以轉化成概率密度估計的問題。根據全概率定理,點集X的概率公式可表示為

(4)

若點集X和Y都滿足高斯概率模型,那么它們之間的關系可描述為

(5)

這里為了簡化模型,假設模型點集Y服從均勻分布,即

(6)

(7)

PICP算法分為兩個主要實現步驟:

1) 根據第k-1步的剛體變換Rk-1和tk-1,建立點集X和Y的相關性,其數學描述如下:

(8)

該步驟建立了點集X和Y之間的一對一相關性。由于這個過程抑制了不重要的點并保持了點對的原始信息不受噪聲的干擾,因此可以大大減少計算時間并在一定程度上提高配準精度。

2) 基于第1)步求解新的剛體變換,并用奇異值分解(Singular Value Decomposition,SVD)方法來計算相關點的概率,再根據兩個點集之間的距離和方差就計算出后驗高斯概率。這里,由于高斯概率模型的方差是從大到小逐步變化的,這就使得配準過程是從粗到細的,避免算法陷入局部最小值。

首先,建立新的目標函數如下

(9)

(10)

(11)

(12)

(13)

方差可以表示為

(14)

那么,高斯概率方差的更新公式為

(15)

其中,λ稱作退火系數。當λ=1時,方差不會更新,就是所謂的ICP算法。當λ取值較大時,就可以有效地提高迭代速度,但是容易陷入局部最小值。因此一般λ的取值在1～2之間,具體取值由實驗來決定。

因此,后驗高斯概率的計算公式為

(16)

重復執行1)和2)兩個步驟就實現了PICP算法的兩個點集的配準問題。PICP算法的終止條件為:在每次迭代結束時,都判斷算法是否達到終止條件,若相鄰兩次迭代的RMS的差值|RMSk-RMSk-1|小于給定閾值ε或達到最大迭代次數Stepmax,算法就停止迭代,此時算法取得了最優最小值,從而實現了兩個點集的配準。

下面給出PICP算法的具體實現步驟:

Step2:令X=R0X+t0,迭代次數k=0;

Step3:令k=k+1,利用式(8)建立相關性ck(i),i=1,2,…,Nx;

Step4:利用式(12)的SVD方法計算旋轉矩陣Rk和平移矢量tk;

Step5:利用式(14)計算兩組點集的方差;

Step6:利用式(15)更新高斯概率的方差;

Step7:利用式(16)計算后驗高斯概率直到滿足|RMSk-RMSk-1|<ε或k>Stepmax。

4 實驗結果與分析

本文的實驗數據源于Stanford 3D Scanning Repository[20],采用了兩組帶有噪聲的點云數據進行配準實驗,分別如圖1和圖2所示。圖1是第一組點云數據,采用了bun000和bun045兩個點云數據,分別如圖1(a)和圖1(b)所示,圖1(c)是點云bun000和bun045的初始相對位置。圖2是第二組點云數據,采用了dragonStandRight_0和dragonStandRight_24兩個點云數據,分別如圖2(a)和圖2(b)所示,圖2(c)是點云bun000和bun045的初始相對位置。

實驗中,分別采用ICP算法和PICP算法對第一組點云數據和第二組點云數據進行配準,其配準結果分別如圖3和圖4所示。圖3是第一組點云數據的配準結果,圖3(a)是ICP算法的配準結果,圖3(b)是PICP算法的配準結果。圖4是第二組點云數據的配準結果,圖4(a)是ICP算法的配準結果,圖4(b)是PICP算法的配準結果。從圖3和圖4的配準結果來看,PICP算法較ICP算法的配準結果更好,得到了更多的配準點對,配準的精度更高,誤差更小。其具體的配準點數、RMS、迭代次數和耗時等配準結果參數如表1所示。

圖1 第一組待配準的兩個點云

圖2 第二組待配準的兩個點云

圖3 第一組點云的配準結果

圖4 第二組點云的配準結果

表1 兩組點云的配準結果參數(時間單位:s)

從表1可見,對于第一組點云,與ICP算法相比,PICP算法的配準點數提高了35.6%,RMS降低了43.5%,迭代次數降低了38.1%,耗時降低了30.8%。對于第2組點云,與ICP算法相比,PICP算法的配準點數提高了32.4%,RMS降低了41.4%,迭代次數降低了35.8%,耗時降低了32.1%。由此可見,PICP算法的配準效果要遠優于ICP算法的配準效果,該算法大大提高了帶有噪聲的點云的配準個數,降低了RMS、迭代次數和耗時,并具有較強的魯棒性。因此說,PICP算法是一種快速、精確的點云配準算法,并且配準結果不受噪聲的干擾。

5 結語

點云配準技術研究已久,各種配準算法都是圍繞著配準的精度、速度以及魯棒性等方面展開的,本文主要針對帶噪聲點云的配準問題,提出了一種基于概率迭代最近點的點云配準算法。該算法不僅通過建立兩個點云之間的點的一一對應關系在一定程度上排除了不重要的點和噪聲點,大大提高了點云配準的精度,而且還通過引入高斯模型的方式,通過求解其概率模型的距離和方差實現了點云由粗到細的配準,進一步提高了配準的精度。該算法不僅是對ICP算法在配準精度、速度等方面的一個改進,更是一種針對噪聲點云的有效配準算法。在今后的研究中,會將該算法引入到更加復雜剛體碎塊的復原研究中,如含有大量噪聲的復雜秦俑碎塊的虛擬拼接復原,以進一步提高碎塊匹配的精度、速度、魯棒性和抗噪性。

[1] 龔倫,劉璨,胡均譜.一種改進Harris角點與SIFT的圖像拼接技術[J].計算機與數字工程,2015,43(11):2055-2060. GONG Lun, LIU CAN, HU Junpu. A New Image Stitching Technology Based on Harris Corner and SIFT[J]. Computer & Digital Engineering,2015,43(11):2055-2060.

[2] 孫曉寧,陸文駿.一種新的霧天圖像顯著性檢測方法[J].計算機與數字工程,2015,43(11):2029-2034. SUN Xiaoning, LU Wenjun. A New method of Salient Object Detection in Foggy Images[J]. Computer & Digital Engineering,2015,43(11):2029-2034.

[3] E. Altantsetseg, K. Matsuyama, K. Konno. Pairwise matching of 3D fragments using fast fourier transform[J]. Visual Computer,2014,30:929-938.

[4] L. Zhang, M. Song, Q. Zhao, et al. Probabilistic Graphlet Transfer for Photo Cropping[J]. IEEE Transactions on Image Processing,2013,22:802-815.

[5] L. Zhang, M. Song, Y. Yang, et al. Weakly Supervised Photo Cropping[J]. IEEE Transactions on Multimedia,2014,16:94-107.

[6] Y. Gao, M. Wang, D. Tao, et al. 3-D Object Retrieval and Recognition With Hypergraph Analysis[J]. IEEE Transactions on Image Processing,2012,21:4290-4303.

[7] Y. Gao, M. Wang, R. Ji, et al. 3-D Object Retrieval With Hausdorff Distance Learning[J]. IEEE Transactions on Industrial Electronics,2014,61:2088-2098.

[8] 稅午陽,周明全,武仲科.數據配準的顱骨面貌復原方法[J].計算機輔助設計與圖形學學報,2011,23(4):607-614. SHUI Wuyang, ZHOU Mingquan, WU Zhongke. An Approach of Craniofacial Reconstruction Based om Registration[J]. Journal of Computer-Aided Design & Computer Graphics,2011,23(4):607-614.

[9] P.J. Besl, N.D. McKay. A method for registration of 3-Dshapes[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence,1992,14:239-256.

[10] C.V. Stewart, C.-L. Tsai, B. Roysam. The dual-boot strap iterative closest point algorithm with application to retinal image registration[J]. IEEE Transactions on Medical Imaging,2003,22:1379-1394.

[11] M. Herrmann, M. Otesteanu, M. Otto. Fast and robust point cloud matching based on EM-ICP prepositioning[C]//2012 10thInternational Symposium on Electronics and Telecommunications(ISETC),2012:99-103.

[12] F. Aghili, M. Kuryllo, G. Okouneva, et al. Robust vision-based pose estimation of moving objects for Automated Rendezvousamp; Docking[C]//2010 International Conference on Mechatronics and Automation(ICMA),2010:305-311.

[13] S. Du, N. Zheng, L. Xiong, et al. Scaling iterative closest point algorithm for registration of m-D point sets[J]. Journal of Visual Communication and Image Representation,2010,21:442-452.

[14] Jianda Han, Peng Yin, Yuqing He. Enhanced ICP for the Registration of Large-Scale 3D Environment Models: An Experimental Study[J]. sensors,2016,16(228):1-15.

[15] Chunjia Zhang, Shaoyi Du, Juan Liu, et al. Robust 3D Point Set Registration Using Iterative Closest Point Algorithm with Bounded Rotation Angle[J]. Signal Processing,2016,120:777-788.

[16] Pavlos Mavridis, Anthousis Andreadis, Georgios Papaioannou. Efficient Sparse ICP[J]. Computer Aided Geometric Design,2015,35:16-26.

[17] Shaoyi Du, Juan Liu, Chunjia Zhang. Probability iterative closest point algorithm for m-D point set registration with noise[J]. Neurocomputing,2015,157:187-198.

[18] C.V. Stewart, C. Tsai, B. Roysam. The dual-boot strap iterative closest point algorithm with application to retinal image registration[J]. IEEE Trans. Med. Imaging,2003,22:1379-1394.

[19] L. Liu, X. Hu,Y. Chen, et al. A new close-form solution for initial registration of ICP. Adv. Mater. Res.,2011,143:287-292.

[20] The Stanford 3D Scanning Repository[EB/OL]. 1996. http://graphics.stanford.edu/data/3Dscanrep/.

Point Cloud Registration Algorithm Based on Probability Iterative Closest Point

ZHAO Fuqun1,2ZHOU Mingquan1,2WANG Jing1

(1. College of Education Science, Xianyang Normal University, Xianyang 712000) (2. College of Information Science and Technology, Northwest University, Xi’an 710127)

Aiming at the failure registration of iterative closest point (ICP) algorithm brought by noise, the paper proposes a point cloud registration algorithm with noise based on Expectation Maximum (EM) estimation, which is named probability iterative closest point (PICP) algorithm. Firstly, a point-to-point correspondence is built between two point clouds, thus the registration accuracy is improved greatly. Then, Gaussian model is introduced into ICP algorithm, the singular value decomposition (SVD) method is used to solve the problem of rigid body transformation, thus the accurate registration of two point clouds is completed. The experimental results show that PICP algorithm not only can complete point clouds registration with noise of the same object from different angles rapidly and accurately, but also can achieve complete matching and partial matching of fracture surfaces between rigid body blocks effectively. It is an accurate and fast algorithm which can effectively avoid noise and external interference. It has more extensive application scopes.

point cloud registration, iterative closest point, Gaussian model, probability, noise

2016年9月5日,

2016年10月13日

國家自然科學基金項目(編號:61373117)資助。

趙夫群,女,博士研究生,講師,研究方向:圖形圖像處理。周明全,男,教授,博士生導師,研究方向:圖形圖像處理,三維重建。王靜,女,碩士,研究方向:信息技術及其應用。

TP391.4

10.3969/j.issn.1672-9722.2017.03.002