基于LM和SVD結合的點云拼接算法研究

吳曉慶, 黃玉清

(西南科技大學信息工程學院，四川 綿陽 621010)

基于LM和SVD結合的點云拼接算法研究

吳曉慶, 黃玉清

(西南科技大學信息工程學院，四川 綿陽 621010)

點云拼接是場景三維重建過程中的重要環節。針對現有的拼接算法存在耗時長、拼接效果差等問題，通過利用正交映射，獲取三維點云與二維圖像之間的映射關系，并在二維圖像中獲取匹配點對。在此基礎上，提出了采用LM和SVD結合的方法來變換矩陣。首先根據正交映射，獲取三維點云所對應的二維圖像；其次利用SURF算法，提取圖像的特征點，并通過FLANN算法以及RANSAC算法，提取兩幅圖像中的特征拼接點對；最后將LM和SVD兩種方法相結合，求得變換矩陣。試驗結果表明，無論拼接精度，還是運行速度，該算法均較直接利用LM算法或SVD算法有所提高。

機器人; 點云拼接; 正交映射; 線性最小二乘法;LM算法;SVD算法; 變換矩陣

0 引言

隨著機器人技術的發展，其應用領域也不斷擴展，現在已經可以代替或者輔助人類完成很多艱巨的任務[1]。面對未知的環境，比如核輻射環境、太空等，要想實現對這些環境的識別，就必須要對機器人所“看到”的場景進行重建；而拼接又是重建過程中非常重要的組成部分。由于現實中攝像頭視場角度固定，很難一次性獲得場景的完整信息[2]，所以我們更加需要對獲取的三維圖像進行拼接。

迭代最近點(iterationclosestpoint，ICP)算法是三維點云廣泛使用的方法。該算法只針對兩個點云集初始相對位置已知的情況；當兩個點云的重合部分比較少時，該算法容易陷入局部最優值[3]。而且，當點云非常大時，運算速度就會非常慢且精度也不高。所以如何提高三維點云的匹配精度和速度的難題，一直困擾著我們。相對于三維點云拼接，二維圖像的拼接方法則相對成熟。例如尺度不變特征變換(scaleinvariantfeaturetransform，SIFT)算法，該算法對圖像的旋轉、尺度縮放、亮度變化等保持不變[4]；加速魯棒特征(speededuprobustfeatures，SURF)提取算法[5]，對外界具有很強的魯棒性。因此，利用二維圖像提取特征點，完成點云的拼接，為拼接提供了一個新的思路[6]。而在基于圖像特征的點云拼接中，也常利用隨機抽樣一致性(randomsampleconsensus，RANSAC)[7-8]算法魯棒優化，去除不可靠的匹配點對，同時結合奇異值分解(singularvaluedecomposition，SVD)[9-16]來獲取轉換矩陣。

而在點云拼接求取變換矩陣過程中，列文伯格-馬夸爾特法(levenbergmarquardt，LM)卻很少被人使用，該算法是最優化算法中的一種，具有高斯-牛頓法的局部收斂性和梯度下降法的全局特性，局部搜索能力非常強[12]。所以，本文在JuanLi[7]工作的基礎上，利用正交投影，獲得三維點云與二維圖像間轉換，將SURF、快速最近鄰算法(fastlibraryforapproximatenearestneighbors，FLANN)[9]以及RANSAC相結合提取特征點對。求取變換矩陣時，結合LM和SVD算法，最終實現點云的拼接。

1 算法描述

基于LM和SVD結合的點云拼接算法的基本思路是：首先利用正交映射將無序的彩色點云映射成二維圖像；然后利用SURF算法完成二維圖像的特征提取，并利用FLANN中KD-TREE快速搜索對特征點進行匹配，利用RANSAC算法刪除錯誤特征匹配點；根據三維與二維之間的映射關系，將二維圖像中的特征點對映射到三維點云中，獲取兩點云之間的特征點對；最后結合LM和SVD算法，通過特征點對獲取點云之間的變換矩陣，完成點云的拼接。算法流程圖如圖1所示。

圖1 算法流程圖

1.1 3D-2D的正交投影

(1)正交投影。

投影線垂直于投影面的投影屬于正交投影，也稱平行投影。設I與Z分別為具有二階矩的n維和m維隨機向量，如果存在一個與I同維的隨機向量&Icri滿足下列條件：①線性表示&Icri=A+BZ；②無偏性，E(&Icri)=E(I)；③正交，E[(I-&Icri)ZT]=0，則稱&Icri是I在Z上的正交投影(注：把矩陣Z的行換成相應的列，得到的新矩陣稱為Z的轉置矩陣，記為ZT)。

(2)三維與二維之間的映射。

計算位于OXYZ坐標系統的平均法向量，并且選擇平行于Z軸的法向量，三維(3D)平面就可以通過正交投影，映射到XOY的二維(2D)平面上。在3D坐標系統中，表面法向量可以被視為在表面上點的平均法向量[7]。令表面法向量為V(x,y,z)T和|V|=1，定義旋轉矩陣為：

(1)

(2)

則很容易證明：

(3)

向量(0,0,1)T是平行于Z軸的法向量。將點云中的每一個點都進行旋轉，可以得到一個新的表面，而這個新表面的法向量平行于Z軸。新表面的點Xnew和在原始點云上的點Xcloud之間的關系為：

(4)

3D表面和2D圖像的正交投影關系如圖2所示。

圖2 3D表面和2D圖像的正交投影關系示意圖

1.2 特征提取

(1)SURF特征點提取。

本文使用SURF算法提取特征點。雖然SIFT算法比較穩定，檢測到的特征點也比較多，但是其最大的缺點是計算復雜度較高。有很多學者對其進行了改進，如SIRF算法。SURF構造的金字塔圖像與SIFT有很大不同。SIFT采用的是DOG圖像，而SURF采用的是Hessian矩陣行列式近似值圖像[10]。

SURF算法的基本思路是利用積分圖像和盒子濾波建立尺度空間，使用Hessian矩陣進行特征點檢測，并使用Haar小波分析提取特征點的描述符[10]。它主要有以下五個步驟：①構建Hessian矩陣，該矩陣是SURF算法的核心；②構建尺度空間，圖像的尺度空間是該圖像在不同解析度下的表示；③精確定位特征點，在這個過程中，所有小于預設極值的取值都被丟棄，增加極值使檢測到的特征點數量減少，最終只有幾個特征最強的點會被檢測出來；④主方向確定；⑤特征點生成。

(2)FLANN與RANSAC結合獲取匹配點對。

由于噪聲、計算誤差等外界因素的影響，僅僅使用FLANN查找到的相應點存在誤匹配的情況，所以我們使用FLANN算法和RANSAC算法相結合的方式，來獲取較為準確的匹配特征點。通過FLANN算法，獲取特征點的初始匹配；進一步刪除錯誤匹配點；最終獲取更加準確的匹配點對。

1.3 變換矩陣求取

(1)LM算法。

LM算法是一種基于目標函數的微分迭代技術，現已成為求解非線性最小二乘法問題的標準方法，可以視為梯度下降法和Gauss-Newton法的結合[11]。LM算法的實現并不困難，其關鍵是用模型函數f對待估參數向量p在其領域內作線性近似，忽略二階以上的導數項，從而轉換為線性最小二乘法問題，具有收斂速度快等優點[12-14]。

LM算法是一種“信賴域法”。假設一個可以信賴的最大位移，以當前點為中心，在以最大位移為半徑的區域內搜索目標函數的一個最優點的近似，從而求得真正的位移。在得到位移后，再次計算目標函數值。如果該目標函數值的下降滿足一定條件，說明這個位移是對的，則按照此步驟迭代下去；如果不能滿足條件，則應該減小信賴域區域，重新求解。

(2)SVD算法。

奇異值分解是線性代數中一種重要的矩陣分解。矩陣奇異值分解的具體步驟和過程[13]如下。

①計算矩陣AHA的特征值λ1≥λ2≥…≥λr>λr+1=…λn=0。

②計算特征值對應的特征向量，并組成正交矩陣V：

(5)

③將V寫成分塊矩陣：

(6)

④計算U1：

U1=AV1∑-1

(7)

⑤將U1擴充為酉空間Cm的標準正交基，組成m階有矩陣U：

U=[U1U2]

(8)

⑥于是酉矩陣的奇異值分解為：

(9)

(3)LM和SVD的結合算法。

通過分別使用LM和SVD方法，對獲取的特征點對求取變換矩陣，最終完成點云拼接；然后通過式(10)，獲取最終的變換矩陣。

[RT]=α[RtmTtm]+(1-α)[RsvdTsvd]

(10)

式中：α為權重。經過反復測試，發現當權重是50%時，所取得的效果最佳。

權重分析如表1所示。

表1 權重分析

2 試驗結果

試驗平臺硬件環境為：深度攝像頭微軟kinect，軟件開發工具為Windows 7操作系統，vs2012，pcl 1.7.2，opencv 2.4.9。在同一個平臺下，對比了兩種算法的拼接時間和拼接誤差。試驗結果及分析如下。

①場景拼接。

針對點云的拼接效果，使用拼接誤差E來描述[16]，計算公式如下：

E=Er/Cr

(11)

式中：Er為所有有效拼接點對的距離誤差總和;Cr為有效憑借點對數。

②結果分析。

在點云拼接過程中，記錄了程序運行的拼接時間以及三種算法的拼接誤差，如表2所示。

表2 三種算法對比

三種算法都是在相同的平臺下作同樣的工作。可以看出，本文算法的運行時間和拼接誤差都是三種算法中最優的。

3 結束語

針對現在點云拼接算法中存在的拼接速度慢、特征拼接效果差的問題，運用三維映射到二維的正交映射，結合SURF特征提取、FLANN算法以及RANSAC獲取更加準確的匹配點對后，提出了采用LM和SVD相結合的算法，來獲取兩點云之間的變換矩陣，實現點云拼接的目的。

相較于通過傳統的ICP算法獲得變換矩陣，本文算法的耗時更短。在不影響拼接效果的前提下，點云的拼接速度得到了提高。試驗表明，本文提出的算法在拼接效果、速度方面表現非常好。

下一步改進方向為以下兩方面：①考慮將點云濾波加入算法，來濾除點云中的干擾項；②考慮在實現三維點云拼接的基礎上，實現多角度的全局拼接。

[1]BERTOZZIM.Vision-basedintelligentvehicles:stateoftheartandperspectives[J].Robotics&AutomationSystems,2000,32(1):1-16.

[2] 儲珺,聶春梅,王璐.基于SIFT特征的多視點云數據配準和拼接算法[J].半導體光電,2011,32(3):442-447.

[3]HELL,WANGS,PAPPASTN.3DSurfaceregistrationusingZ-SIFT[C]//IEEEIntrenationalConferenceonImageProcessing,2011:1985-1988.

[4] 王程冬,程筱勝,崔海華,等.SIFT算法在點云配準中的應用[J].傳感器與微系統,2012,31(2):149-152.

[5]LUOJ,GWUNO.SURFappliedinpanoramaimagestitching[C]//2ndInternationalConferenceonImageProcessingTheoryToolsandApplications,2010:495-499.

[6] 張曉,張愛武.基于圖像的點云初始配準[J].計算機工程與設計,2014,35(10).

[7]LIJ,JIANGG.Pointcloudsregistrationwithsurfacesoflowcurvatures[C]//2015IEEEInternationalConferenceonSignalProcessing,CommunicationsandComputing(ICSPCC),2015:1-5.[8] 常青,張斌,邵金玲.基于SIFT和RANSAC的特征圖像匹配方法[J].華東理工大學學報,2012,38(6):747-751.

[9]MUJAM,LOWEDG.Fastapproximatenearestneighborswithautomaticalgorithmconfiguration[C]//ProceedingsofIEEEConferenceonComputerVisionTheoryandApplications.Lisbon,Portugal:IEEEComputerSociety,2009:331-340.

[10]毛星云,冷雪飛,王碧輝,等.OpenCV3編程入門[M].電子工業出版社,2015:396-400.

[11]文成哲,劉財,郭智奇,等.遺傳算法和LM算法聯合反演銳雷波相速度[J].地球物理學進展,2010,25(1):303-309.

[12]張長勝,歐陽丹彤,岳娜,等.一種基于遺傳算法和LM算法的混合學習算法[J].吉林大學報,2008,46(4):675-680.

[13]魯鐵定,寧津生,周世鍵,等.最小二乘配置的SVD分解解法[J].測繪科學,2008,33(3):47-51.

[14]張玉濤,李亞清,鄧軍,等.煤炭自然災害過程突變特性研究[J].中國安全科學學報,2015,25(1):78-84.

[15]CHUMO,PHILBINJ,ZISSERMANA.Nearduplicateimagedetection:minhashandweighting[C]//Proceedingsofthe19thBritishMachineVisionConference,London,UK,2008:493-502.

[16]左超,魯敏,譚志國,等.一種新的點云拼接算法[J].中國激光,2012,39(12):1-8.

ResearchonthePointCloudStitchingAlgorithmBasedonCombinationofLMandSVD

WUXiaoqing,HUANGYuqing

(SchoolofInformationEngineering,SouthwestUniversityofScienceandTechnology，Mianyang621010,China)

Pointcloudregistrationisanimportantroleinthereconstructionof3Dscenes.Aimingattheproblemsexistingincurrentregistrationalgorithms,suchastime-consumingandpoorregistrationeffect,throughadoptingorthogonalmapping,themappingrelationsbetween3Dpointcloudand2Dimageisobtained,andthematchingpointpairsarecapturedin2Dimage.Onthisbasis,bycombininglevenberg-marquardt(LM)algorithmandsingularvaluedecomposition(SVD),thematrixistransformed.Firstly,inaccordancewiththeorthogonalmapping,the2Dimagecorrespondingtothe3Dpointcloudisacquired;thentheimagefeaturepointsareextractedbyusingSURFalgorithm,andwithFLANNalgorithmandRANSACalgorithm,thesplicingpointpairfortwoimagesisextracted;finally,thetransformationmatrixisobtainedbycombiningtheLMandSVD.TheresultsofthetestsindicatethatthemethodproposedgetsbettersplicingaccuracyandrunningspeedthenthosebyLMalgorithmorSVDalgorithm.

Robot;Pointcloudsregistration;Orthogonalmapping;Linearleastsquaremethod;LMalgorithm;SVDalgorithm;Transformationmatrix

國家自然科學基金資助項目(61401379)、國防應用技術項目資助(12zg610303)

吳曉慶(1991—)，女,在讀碩士研究生，主要從事圖像處理與機器視覺的研究。E-mail:1253742950@qq.com。黃玉清(通信作者)，女，碩士，教授，主要從事無線控制及無線通信技術、圖像處理與機器視覺、智能技術的研究。E-mail:hyq_851@163.com。

TH-3;TP

ADOI: 10686/j.cnki.issn1000-0380.201701008

修改稿收到日期:2016-07-27