基于二維圖像特征的點云配準方法

趙夫群，周明全

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

基于二維圖像特征的點云配準方法

趙夫群1,2，周明全2,3

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

為了提高低覆蓋率點云的配準精度和收斂速度，提出了一種基于二維圖像特征的點云配準方法。首先采用基于區域層次的點云配準算法實現粗配準；然后將三維點云轉換成二維圖像，再采用SURF算法提取二維圖像的特征，并求解其匹配像素點對；最后根據二維匹配點獲取相應的三維點云相關點，并計算剛體變換，由此實現點云的快速精確配準。試驗結果表明，與迭代最近點(ICP)算法相比，該點云配準方法的配準精度和耗時分別提高了約20%和60%，是一種快速、高精度的點云配準算法。

點云配準；圖像特征；區域層次；旋轉矩陣；迭代最近點

近年來隨著三維掃描技術的迅速發展，各種各樣的三維點云數據采集設備應運而生。三維掃描儀一次掃描只能獲取物體表面的部分點云信息，要想獲取其全局信息，需要進行多次掃描，再通過點云配準技術來實現。點云配準是三維建模的關鍵技術之一，其主要目的是求解不同設備或角度采集到的兩個點云的最優空間變換，使其能夠達到最佳配準。目前，點云配準已經在三維重建[1-2]、地面場景配準[3]、目標識別[4-5]以及顱面復原[6]等領域得到了廣泛的應用。

目前的點云配準算法中，應用最為廣泛的是由P.J.Besl等[7]提出的迭代最近點(iterative closest point,ICP)算法，該算法簡單，易于理解和實現，但是算法的運行效率較低，而且對兩個點云的初始位置要求較高。鑒于此，國內外學者提出了很多改進的ICP算法[8-13]。雖然這些改進算法在點云配準的精度、速度及抗噪性等方面有了一定程度的提高，但是依舊不能很好地描述點云的局部特征，而且對于低覆蓋率的點云的配準效果也不佳。

針對低覆蓋率的點云，本文提出一種基于二維局部特征的點云配準算法。算法主要思想為：首先采用基于區域層次上的自動點云配準算法實現粗配準；然后將三維點云轉換成二維圖像，并采用SURF算法提取兩幅二維圖像的特征點；最后根據二維匹配點獲取兩個點云的三維相關點，并采用最小二乘逼近法計算最優旋轉矩陣，由此實現點云的快速精確配準。

1 粗配準算法

粗配準采用基于區域層次上的點云配準方法[14]，分為區域劃分、區域配準、求解組合系數以及求解剛體變換等4個基本步驟。

(1) 進行區域劃分。對于待配準的兩個點云，分別對其均勻采樣，然后計算每個采樣點的基于歐氏距離的Voronoi圖作為劃分的區域，即以均勻采樣點為初始聚類中心，執行多次基于歐氏距離的C-均值聚類，即可將每個點云劃分為一系列互不相交的區域。通常，劃分區域的數目與物體的形狀和點云的重疊比例有關，通常設置為1～20個。

(2) 進行區域配準。與點云配準相比，區域配準是一種規模更小的配準過程，因此這里采用窮舉法將兩個點云中的所有對應區域對進行配準，并按照配準后兩個區域的重疊比例來評價配準的效果。

(3) 求解組合系數。這里引入可信性和一致性的概念，通過最大化能量函數來求解組合系數，該能量函數定義為

(1)

(4) 求解剛體變換。上個階段求解的線性變換一般不是剛體變換，因此要將該線性變換分解為一個旋轉矩陣R和一個平移向量t，這里的R采用四元數法[15]表示

(2)

(3)

通過以上4個基本步驟，即可完成兩個點云的粗配準，將兩個點云初步對齊后，即可采用基于D局部特征的點云配準算法實現細配準。

2 三維點云轉換成二維圖像

2.1 BA圖像

通常三維圖像的深度圖像用于將三維點云轉換成二維圖像，不能用于表示三維點云中的點及其鄰域點之間的關系。與深度圖像不同，BA圖像(bearing angle image)[16]可以突出由角度形成的邊緣，因此可以從中提取到更多的信息。

對于一個三維形狀的物體，其BA圖像的像素灰度水平定義為從該點到一個連續點的激光束和矢量之間的夾角，如圖1所示。點pij和pi-1, j-1是兩個測量點，點o是點云的源點，也就是掃描儀的位置，點pij的角度值BAij定義為

(4)

式中，ρi,j為第i個掃描層的第j個掃描點的測量值；ρi-1,j-1為第i-1個掃描層的第j-1個掃描點的測量值；dφ為相應的角度增量。

圖1 BA圖像的像素灰度水平

2.2 BA圖像特征提取和匹配

前文已將三維參考點云和目標點云轉換成了二維的BA圖像，下面采用基于特征的匹配方法來尋找BA圖像的相關點，即采用SURF(speed-up robust features)算法[17-18]來實現。

SURF算法是一個尺度不變的二維圖像特征檢測方法，與SIFT算法相似，SIFT算法比較穩定，檢測特征點更多，但是復雜度較高，而SURF要運算簡單，效率高，運算時間更短。SURF算法由以下幾個步驟組成：①構建黑森(Hessian)矩陣；②生成尺度空間；③利用非極大值抑制初步確定特征點和精確定位特征點；④構造SURF特征點描述子。

SURF提取的特征描述子可以確定特征點主方向及其鄰近點的64個特征矢量。BA圖像的特征點的匹配是通過計算兩個特征矢量的歐幾里得距離來實現的。匹配完成后，即可找到BA圖像的相關特征點。

3 求解三維變換矩陣

對于BA圖像的任意一個像素點，BAij就對應初始三維點云中的第i個掃描層的第j個掃描點。三維點和二維像素是一種一對一的映像，因此二維圖像像素BAij的初始三維點就是pij。

下面求解兩個三維點云的最佳剛體變換。設兩個待配準的三維點云為P和Q，它們通常有多于3對的相關點，因此求解P和Q的旋轉矩陣的問題可以看作是一個正交Procrustes問題。首先，假設平移是從P的質心到Q的質心。因此，不考慮平移變換的情況下，兩個點云可以寫為

(5)

(6)

令新的相關點云分別為云Pc和Qc的。由于最佳旋轉角R意味著最小的變換誤差，因此R可表示為

(7)

(8)

因此優化形式可以進一步寫為

(9)

(10)

由于R是一個正交矩陣，因此該約束優化問題可以采用拉格朗日乘子來求解。拉格朗日乘子定義為

(11)

(12)

式(12)可進一步寫為

(13)

(14)

由式(14)可計算出，最佳旋轉矩陣為

R=UVT

(15)

因此，最佳剛體變換可表示為

(16)

4 試驗結果與分析

試驗數據源于Stanford 3D Scanning Repository[19]，采用了兩個兔子點云數據，如圖2所示。

圖2 待配準點云

試驗在CPU為Intel core i3 2.27 GHz，內存為2 GB的32位Win7操作系統上實現配準。對于圖2所示的點云數據，直接采用ICP算法進行配準，其配準結果如圖3所示。

圖3 直接使用ICP算法的配準結果

顯然配準結果很不理想，主要是由于ICP算法對兩個點云的初始位置要求較高，而且對低覆蓋率點云的配準結果較差。因此本文首先采用基于區域層次的自動點云配準算法實現粗配準，粗配準結果如圖4所示，然后再分別采用ICP算法和本文提出的基于二維圖像特征的點云配準算法實現細配準，其細配準結果分別如圖5和圖6所示。

圖4 粗配準結果

圖5 ICP算法的細配準結果

圖6 本文算法的細配準結果

在細配準階段，ICP算法和本文提出的基于二維圖像特征的配準算法的配準誤差、算法耗時等參數見表1。

表1 細配準階段的配準參數

從圖4—圖6及表1的配準結果來看，基于區域層次的自動點云配準算法能夠將兩個點云粗略配準，ICP算法和基于二維圖像特征的點云配準方法均可實現兩個點云的細配準，但是基于二維圖像特征的點云配準方法的配準精度和速度要比ICP算法分別提高了20%和60%。因此，本文的點云配準算法是一種快速、精確的點云配準算法。

5 結 語

點云配準是三維建模的一個關鍵步驟，其應用范圍涉及多個領域。本文利用二維圖像特征，提出了一種快速、高精度的低覆蓋率點云配準方法。該方法首先通過區域劃分、區域配準、求解組合系數及求解剛體變換等步驟快速實現點云的粗配準，然后基于二維圖像特征提出了一種快速、高精度的點云的細配準算法，由此實現了點云的精確配準。在以后的點云配準算法研究中，要綜合考慮多種因素，作進一步的深入研究，如進一步完善二維特征提取算法，以提高點云配準精度；針對點云中存在的問題作進一步的研究，提高算法的抗噪性；將點云配準算法應用到兵馬俑碎塊拼接或顱面復原研究中，以擴大算法的應用范圍。

[1] LUO Y,GUAN T,WEI B,et al.Fast Terrain Mapping from Low Altitude Digital Imagery[J].Neurocomputing,2015(156):105-116.

[2] 閆陽陽,李永強,王英杰,等.三維激光點云聯合無人機影像的三維場景重建研究[J].測繪通報,2016(1):84-87.

[3] 鄭敏輝,臧玉府,梁福遜,等.不同場景的地面激光點云配準方法研究[J].測繪通報,2015(8):30-34.

[4] GAO Y,WANG M,TAO D,et al. 3-D Object Retrieval and Recognition with Hypergraph Analysis[J].IEEE Transactions on Image Processing,2012,21(9):4290-4303.

[5] GAO Y,WANG M,JI R,et al. 3-D Object Retrieval with Hausdorff Distance Learning[J].IEEE Transactions on Industrial Electronics,2014,61(4):2088-2098.

[6] 稅午陽,周明全,武仲科,等.數據配準的顱骨面貌復原方法[J].計算機輔助設計與圖形學學報,2011,23(4):607-614.

[7] BESL P J,MCKAY N D.A Method for Registration of 3-D Shapes[J].IEEE Transactions on Pattern Analysis & Machine Intelligence,2002,14(2):239-256.

[8] ZHU J,DU S,YUAN Z,et al.Robust Affine Iterative Closest Point Algorithm with Bidirectional Distance[J].Iet Computer Vision,2012,6(3):252-261.

[9] HAN J,YIN P,HE Y，et al.Enhanced ICP for the Registration of Large-scale 3D Environment Models:An Experimental Study[J].Sensors,2016,16(2):1-15.

[10] DU S,LIU J,ZHANG C.Probability Iterative Closest Point Algorithm for m-D Point Set Registration with Noise[J].Neurocomputing,2015(157):187-198.

[11] DU S,ZHENG N,XIONG L.Scaling Iterative Closest Point Algorithm for Registration of m-D Point Sets[J].Journal of Visual Communication and Image Representation,2010,21(5-6):442-452.

[12] ZHAO L,SHEN X,LONG X.Robust Wrinkle-aware Non-rigid Registration for Triangle Meshes of Hand with Rich and Dynamic Details[J].Computers & Graphics,2012,36(5):577-583.

[13] 戴玉成,張愛武.三維激光掃描數據快速配準算法研究[J].測繪通報,2010(6):8-11.

[14] 韓寶昌,曹俊杰,蘇志勛.一種區域層次上的自動點云配準算法[J].計算機輔助設計與圖形學學報,2015,27(2):313-319.

[15] HORN B K P.Closed-form Solution of Absolute Orientation Using Unit Quarternions[J].Journal of the Optical Society of American, 1987,4(4):629-642.

[16] SCARAMUZZA D,HARATI A,SIEGWART R.Extrinsic Self Calibration of a Camera and a 3D Laser Range Finder from Natural Scenes[C]∥Proceedings of the 2007 IEEE/RSJ International Conference on Intelligent Robots and Systems.San Diego:IEEE,2007:4164-4169.

[17] BAY H,ESS A,TUYTELAARS T,et al.Speeded-up Robust Features(SURF).Computer Vision and Image Understanding,2008,110(3),346-359.

[18] Bay H,Tuytelaars T,VAN GOOL L.SURF:Speeded Up Robust Features[C]∥Computer Vision-ECCV 2006.Berlin:Springer,2006：404-417.

[19] Stanford Computer Graphics Laboratory.The Stanford 3D Scanning Repository[EB/OL].(1996-9-10)[2016-06-15].http:∥graphics.stanford.edu/data/3Dscanrep.

PointCloudRegistrationMethodBasedon2DImageFeature

ZHAO Fuqun1,2，ZHOU Mingquan2,3
(1. School of Education Science, Xianyang Normal University, Xianyang 712000,China; 2. Shool of Information Science and Technology,Northwest University,Xi’an 710127,China; 3. School of Information Science and Technology,Beijing Normal University,Beijing 100875,China)

A point cloud registration method is proposed in the paper in order to improve the registration accuracy and convergence rate of low overlapping point clouds.Firstly,a point cloud registration algorithm based on region level is used to complete coarse registration;Secondly,3D point cloud is converted into 2D image,SURF(speeded up robust features)algorithm is used to extract 2D image features,and the matching pixel pairs are solved;Finally,3D corresponding points are gotten according to the 2D matching pixels,and the rigid transformation is solved,then the fast and accurate registration of point cloud are achieved.The experimental results showed that the registration accuracy and convergence rate of proposed point cloud registration method improved about 20% and 60% respectively compared with iterative closest point(ICP)algorithm,it is a high accurate and fast point cloud registration method.

point cloud registration;image feature;region level;rotation matrix;iterative closest point

趙夫群，周明全.基于二維圖像特征的點云配準方法[J].測繪通報，2017(10)：39-42.

10.13474/j.cnki.11-2246.2017.0313.

2017-03-10

國家自然科學基金(61373117)

趙夫群(1982—)，女，博士生，講師，主要研究方向為圖形圖像處理。E-mail:fuqunzhao@126.com

P23

A

0494-0911(2017)10-0039-04