趙夫群，周明全

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

基于二維圖像特征的點(diǎn)云配準(zhǔn)方法

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

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

為了提高低覆蓋率點(diǎn)云的配準(zhǔn)精度和收斂速度，提出了一種基于二維圖像特征的點(diǎn)云配準(zhǔn)方法。首先采用基于區(qū)域?qū)哟蔚狞c(diǎn)云配準(zhǔn)算法實(shí)現(xiàn)粗配準(zhǔn)；然后將三維點(diǎn)云轉(zhuǎn)換成二維圖像，再采用SURF算法提取二維圖像的特征，并求解其匹配像素點(diǎn)對(duì)；最后根據(jù)二維匹配點(diǎn)獲取相應(yīng)的三維點(diǎn)云相關(guān)點(diǎn)，并計(jì)算剛體變換，由此實(shí)現(xiàn)點(diǎn)云的快速精確配準(zhǔn)。試驗(yàn)結(jié)果表明，與迭代最近點(diǎn)(ICP)算法相比，該點(diǎn)云配準(zhǔn)方法的配準(zhǔn)精度和耗時(shí)分別提高了約20%和60%，是一種快速、高精度的點(diǎn)云配準(zhǔn)算法。

點(diǎn)云配準(zhǔn)；圖像特征；區(qū)域?qū)哟?；旋轉(zhuǎn)矩陣；迭代最近點(diǎn)

近年來(lái)隨著三維掃描技術(shù)的迅速發(fā)展，各種各樣的三維點(diǎn)云數(shù)據(jù)采集設(shè)備應(yīng)運(yùn)而生。三維掃描儀一次掃描只能獲取物體表面的部分點(diǎn)云信息，要想獲取其全局信息，需要進(jìn)行多次掃描，再通過(guò)點(diǎn)云配準(zhǔn)技術(shù)來(lái)實(shí)現(xiàn)。點(diǎn)云配準(zhǔn)是三維建模的關(guān)鍵技術(shù)之一，其主要目的是求解不同設(shè)備或角度采集到的兩個(gè)點(diǎn)云的最優(yōu)空間變換，使其能夠達(dá)到最佳配準(zhǔn)。目前，點(diǎn)云配準(zhǔn)已經(jīng)在三維重建[1-2]、地面場(chǎng)景配準(zhǔn)[3]、目標(biāo)識(shí)別[4-5]以及顱面復(fù)原[6]等領(lǐng)域得到了廣泛的應(yīng)用。

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

針對(duì)低覆蓋率的點(diǎn)云，本文提出一種基于二維局部特征的點(diǎn)云配準(zhǔn)算法。算法主要思想為：首先采用基于區(qū)域?qū)哟紊系淖詣?dòng)點(diǎn)云配準(zhǔn)算法實(shí)現(xiàn)粗配準(zhǔn)；然后將三維點(diǎn)云轉(zhuǎn)換成二維圖像，并采用SURF算法提取兩幅二維圖像的特征點(diǎn)；最后根據(jù)二維匹配點(diǎn)獲取兩個(gè)點(diǎn)云的三維相關(guān)點(diǎn)，并采用最小二乘逼近法計(jì)算最優(yōu)旋轉(zhuǎn)矩陣，由此實(shí)現(xiàn)點(diǎn)云的快速精確配準(zhǔn)。

1 粗配準(zhǔn)算法

粗配準(zhǔn)采用基于區(qū)域?qū)哟紊系狞c(diǎn)云配準(zhǔn)方法[14]，分為區(qū)域劃分、區(qū)域配準(zhǔn)、求解組合系數(shù)以及求解剛體變換等4個(gè)基本步驟。

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

(2) 進(jìn)行區(qū)域配準(zhǔn)。與點(diǎn)云配準(zhǔn)相比，區(qū)域配準(zhǔn)是一種規(guī)模更小的配準(zhǔn)過(guò)程，因此這里采用窮舉法將兩個(gè)點(diǎn)云中的所有對(duì)應(yīng)區(qū)域?qū)M(jìn)行配準(zhǔn)，并按照配準(zhǔn)后兩個(gè)區(qū)域的重疊比例來(lái)評(píng)價(jià)配準(zhǔn)的效果。

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

(1)

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

(2)

(3)

通過(guò)以上4個(gè)基本步驟，即可完成兩個(gè)點(diǎn)云的粗配準(zhǔn)，將兩個(gè)點(diǎn)云初步對(duì)齊后，即可采用基于D局部特征的點(diǎn)云配準(zhǔn)算法實(shí)現(xiàn)細(xì)配準(zhǔn)。

2 三維點(diǎn)云轉(zhuǎn)換成二維圖像

2.1 BA圖像

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

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

(4)

式中，ρi,j為第i個(gè)掃描層的第j個(gè)掃描點(diǎn)的測(cè)量值；ρi-1,j-1為第i-1個(gè)掃描層的第j-1個(gè)掃描點(diǎn)的測(cè)量值；dφ為相應(yīng)的角度增量。

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

2.2 BA圖像特征提取和匹配

前文已將三維參考點(diǎn)云和目標(biāo)點(diǎn)云轉(zhuǎn)換成了二維的BA圖像，下面采用基于特征的匹配方法來(lái)尋找BA圖像的相關(guān)點(diǎn)，即采用SURF(speed-up robust features)算法[17-18]來(lái)實(shí)現(xiàn)。

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

SURF提取的特征描述子可以確定特征點(diǎn)主方向及其鄰近點(diǎn)的64個(gè)特征矢量。BA圖像的特征點(diǎn)的匹配是通過(guò)計(jì)算兩個(gè)特征矢量的歐幾里得距離來(lái)實(shí)現(xiàn)的。匹配完成后，即可找到BA圖像的相關(guān)特征點(diǎn)。

3 求解三維變換矩陣

對(duì)于BA圖像的任意一個(gè)像素點(diǎn)，BAij就對(duì)應(yīng)初始三維點(diǎn)云中的第i個(gè)掃描層的第j個(gè)掃描點(diǎn)。三維點(diǎn)和二維像素是一種一對(duì)一的映像，因此二維圖像像素BAij的初始三維點(diǎn)就是pij。

下面求解兩個(gè)三維點(diǎn)云的最佳剛體變換。設(shè)兩個(gè)待配準(zhǔn)的三維點(diǎn)云為P和Q，它們通常有多于3對(duì)的相關(guān)點(diǎn)，因此求解P和Q的旋轉(zhuǎn)矩陣的問(wèn)題可以看作是一個(gè)正交Procrustes問(wèn)題。首先，假設(shè)平移是從P的質(zhì)心到Q的質(zhì)心。因此，不考慮平移變換的情況下，兩個(gè)點(diǎn)云可以寫(xiě)為

(5)

(6)

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

(7)

(8)

因此優(yōu)化形式可以進(jìn)一步寫(xiě)為

(9)

(10)

由于R是一個(gè)正交矩陣，因此該約束優(yōu)化問(wèn)題可以采用拉格朗日乘子來(lái)求解。拉格朗日乘子定義為

(11)

(12)

式(12)可進(jìn)一步寫(xiě)為

(13)

(14)

由式(14)可計(jì)算出，最佳旋轉(zhuǎn)矩陣為

R=UVT

(15)

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

(16)

4 試驗(yàn)結(jié)果與分析

試驗(yàn)數(shù)據(jù)源于Stanford 3D Scanning Repository[19]，采用了兩個(gè)兔子點(diǎn)云數(shù)據(jù)，如圖2所示。

圖2 待配準(zhǔn)點(diǎn)云

試驗(yàn)在CPU為Intel core i3 2.27 GHz，內(nèi)存為2 GB的32位Win7操作系統(tǒng)上實(shí)現(xiàn)配準(zhǔn)。對(duì)于圖2所示的點(diǎn)云數(shù)據(jù)，直接采用ICP算法進(jìn)行配準(zhǔn)，其配準(zhǔn)結(jié)果如圖3所示。

圖3 直接使用ICP算法的配準(zhǔn)結(jié)果

顯然配準(zhǔn)結(jié)果很不理想，主要是由于ICP算法對(duì)兩個(gè)點(diǎn)云的初始位置要求較高，而且對(duì)低覆蓋率點(diǎn)云的配準(zhǔn)結(jié)果較差。因此本文首先采用基于區(qū)域?qū)哟蔚淖詣?dòng)點(diǎn)云配準(zhǔn)算法實(shí)現(xiàn)粗配準(zhǔn)，粗配準(zhǔn)結(jié)果如圖4所示，然后再分別采用ICP算法和本文提出的基于二維圖像特征的點(diǎn)云配準(zhǔn)算法實(shí)現(xiàn)細(xì)配準(zhǔn)，其細(xì)配準(zhǔn)結(jié)果分別如圖5和圖6所示。

圖4 粗配準(zhǔn)結(jié)果

圖5 ICP算法的細(xì)配準(zhǔn)結(jié)果

圖6 本文算法的細(xì)配準(zhǔn)結(jié)果

在細(xì)配準(zhǔn)階段，ICP算法和本文提出的基于二維圖像特征的配準(zhǔn)算法的配準(zhǔn)誤差、算法耗時(shí)等參數(shù)見(jiàn)表1。

表1 細(xì)配準(zhǔn)階段的配準(zhǔn)參數(shù)

從圖4—圖6及表1的配準(zhǔn)結(jié)果來(lái)看，基于區(qū)域?qū)哟蔚淖詣?dòng)點(diǎn)云配準(zhǔn)算法能夠?qū)蓚€(gè)點(diǎn)云粗略配準(zhǔn)，ICP算法和基于二維圖像特征的點(diǎn)云配準(zhǔn)方法均可實(shí)現(xiàn)兩個(gè)點(diǎn)云的細(xì)配準(zhǔn)，但是基于二維圖像特征的點(diǎn)云配準(zhǔn)方法的配準(zhǔn)精度和速度要比ICP算法分別提高了20%和60%。因此，本文的點(diǎn)云配準(zhǔn)算法是一種快速、精確的點(diǎn)云配準(zhǔn)算法。

5 結(jié) 語(yǔ)

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

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

[2] 閆陽(yáng)陽(yáng),李永強(qiáng),王英杰,等.三維激光點(diǎn)云聯(lián)合無(wú)人機(jī)影像的三維場(chǎng)景重建研究[J].測(cè)繪通報(bào),2016(1):84-87.

[3] 鄭敏輝,臧玉府,梁福遜,等.不同場(chǎng)景的地面激光點(diǎn)云配準(zhǔn)方法研究[J].測(cè)繪通報(bào),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] 稅午陽(yáng),周明全,武仲科,等.數(shù)據(jù)配準(zhǔn)的顱骨面貌復(fù)原方法[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào),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] 戴玉成,張愛(ài)武.三維激光掃描數(shù)據(jù)快速配準(zhǔn)算法研究[J].測(cè)繪通報(bào),2010(6):8-11.

[14] 韓寶昌,曹俊杰,蘇志勛.一種區(qū)域?qū)哟紊系淖詣?dòng)點(diǎn)云配準(zhǔn)算法[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào),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

趙夫群，周明全.基于二維圖像特征的點(diǎn)云配準(zhǔn)方法[J].測(cè)繪通報(bào)，2017(10)：39-42.

10.13474/j.cnki.11-2246.2017.0313.

2017-03-10

國(guó)家自然科學(xué)基金(61373117)

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

P23

A

0494-0911(2017)10-0039-04