基于表面間三棱錐體積測度的點云配準

張 梅 文靜華 張祖勛 張劍清

1.貴州財經學院,貴陽,550004 2.武漢大學,武漢,430079

0 引言

三維激光掃描是近年來迅速發展起來的一種新型空間數據獲取手段和工具,在物體建模研究與應用方面受到越來越廣泛的關注。隨著激光掃描技術的發展及成本的降低,這方面的研究受到越來越多的關注[1]。然而,由于激光掃描原理和物體本身形狀的限制,使得重建出一個準確而高效的三維模型目前還存在著許多困難,其中之一便是點云的配準。

在三維掃描過程中,許多因素決定了無法通過單個視覺傳感器一次掃描完成整個物體的測量。通常把物體表面分成多個局部相互重疊的子區域,從多個角度分別獲取它們的表面信息,從而得到多個獨立的三維點云,稱為多視(multi—view)點云。在掃描不同的子區域時,所得三維點云在各自測量位置對應的局部坐標系下,而多次測量所對應的局部坐標系并不一致。把各次測量對應的局部坐標系統一到一個全局坐標系下即為多視點云的配準[2]。點云配準有手動配準、依賴儀器的配準和自動配準。通常我們所說的點云配準技術即是指最后一種[3]。點云自動配準技術是通過一定的算法或者統計學規律,利用計算機計算兩片點云之間的錯位,從而達到把兩片點云自動配準的效果。

針對上述多視點云配準方法的不足,本文提出一種基于離散對應特征和表面間平均三棱錐體積誤差測度的改進ICP算法來計算多視點云變換矩陣。先利用基于離散對應特征點的方法求出一個初始的位姿,再使用基于表面間平均三棱錐體積誤差測度的改進ICP算法進行迭代求精。與傳統ICP算法的比較結果表明,本文改進算法可以高效而精確地解算出點云模型配準所需的各種坐標變換參數。

1 初始位姿估計

利用離散的對應特征進行粗略配準以估計初始位姿。基于對應特征的配準方法,就是先設法在兩個相鄰視圖的點云模型P和M(基準點云模型)中找到n(n≥3)組特征對(或稱為對應特征),每一組特征對都對應了實際物體的同一特征。利用點云模型P中的n個特征(P1,P2,…,Pn)和點云模型M中的n個特征(M1,M2,…,Mn)的變換關系Mi=R0Pi+t0(i=1,2,…,n)來求解出剛性變換參數(R0,t0),從而實現粗略配準。

一般常被選作對應特征的幾何特征是點[11],首先用基于幾何特征的視覺技術目視判斷得到初值:如拐角、折痕、邊界,在兩個相鄰視圖的點云模型中手工指定n(n＞3)組對應特征點,然后通過一個線性最小二乘最優化的過程求解出(R0,t0),最后將變換的(R0,t0)應用到點云模型P上得到其剛性變換后的點云模型P′=R0×P+t0,從而將兩個點云模型P和M粗略配準到同一坐標系(M為基準點云模型)。

2 三棱錐體積計算

誤差測度和有效點對的選擇策略對ICP算法的配準精度和收斂速度有很大的影響[12-13],只有盡可能地排除偏離點的影響,定義一個能夠真正反映深度像重疊區域吻合程度的誤差測度,才能使算法具有更強的魯棒性,得到更加準確的配準結果。現有的配準算法[14-15]在誤差測度的選擇上始終都沒有跳出點對或者點面歐氏距離的范疇。本文提出另外一種衡量配準誤差的概念:表面間平均三棱錐體積測度,將兩片激光點云重疊區域間的三維空間三棱錐體積作為誤差測度,并采用一種與之相匹配的點對選取策略完成三角網格的精確配準。

點云模型配準就是要找到輸入點云P和目標點云 Μ之間的一個空間位置變換關系矩陣T(旋轉矩陣R與平移向量t),使得某種形式的誤差測度E在T下最小。目前,最常用的一種誤差測度方法,是由Besl等[4]提出的對應點歐氏距離平方均值法:

式中,N為點云模型P上頂點的個數。

與式(1)中基于距離的誤差測度不同,本文提出了一種基于點云數據重疊區域間平均體積的誤差測度,如圖1所示。

2.拓寬企業融資渠道。深化債券市場融資功能，引導企業通過發行企業債、公司債、中期票據、資產支持票據、短期融資券、超短期融資券、項目收益債等融資方式，擴大融資規模；發揮政府投資引導基金作用，支持產業鏈核心企業發起、引導社會資本共同參與設立產業創投基金，為產業鏈上下游企業提供資金支持。鼓勵有條件的民營企業聯合發起設立民營資本投資公司。設立廣西并購引導基金，推動工業企業重組整合壯大。積極爭取投貸聯動試點，大力推動市場化法治化債轉股工作。

本文改進算法的目的就是要找到一種適合進行空間位置關系變換的方法,使得兩個點云模型重疊區域間的三維空間最小。兩個點云模型重疊區域間點與對應三角形所夾的體積可以表示為

式中,x為點云RP+t上的頂點;H(M,x)為點x到點云模型M上所有頂點歐氏距離的最小值;d(x,mi)(i=1,2,3)為頂點x到3個頂點mi之間的距離;Atri為對應三角形的面積;hi為點云RP+t上頂點x到點云模型M上對應三角形的3個頂點距離的均值。

3 改進的迭代最近點(ICP)配準算法

3.1 基于平均三棱錐體積的誤差測度

由式(2)可以定義誤差測度為

實驗結果表明,式(3)定義的誤差測度具有較強的魯棒性和較高的配準精度。

基于平均三棱錐體積的誤差測度計算步驟如下:

(1)根據體積最小原則,找到點云P上所有點在點云M上的對應三角形。

(2)E(|T|)=0,N=0,對點云P上的每一個頂點x,①找到其對應三角形上的每一個頂點m1、m2、m3,并計算頂點 x到3個頂點之間的距離d(x,mi)(i=1,2,3)的值;②利用海倫公式:

根據邊長 a、b、c,求出m1、m2、m3所圍三角形面積

3.2 基于平均體積誤差測度的點云配準

假設兩片點云數據向量P和M(將P配準到M),配準算法是首先利用基于離散對應特征點的方法得到剛體變換的初始估計。然后對P應用轉換關系矩陣T(旋轉矩陣R與平移向量t)生成P′;從P′中拾取一點p,到M中尋找與p最近的一點m,構成點對(p,m),去除間距特別大的對應點對,去除有頂點位于點云模型邊界上的對應點對,最后形成有效點對集合(Ps,Ms);利用旋轉向量,按照Gelfand等[13]的方法線性化旋轉矩陣R,從而通過求解一個線性系統得到新的變換關系矩陣Tk。計算Ps與Ms所夾的三維空間平均體積測度誤差,如果小于設定的值則結束,否則進行下次迭代。改進的最近點迭代配準算法步驟如下:

(1)利用基于離散對應特征點的方法計算初始位姿(R0,t0)。

(2)k=0,迭代開始:①k←k+1,對點云模型P中的所有點應用轉換矩陣Tk—1(旋轉矩陣Rk—1 與平移向量tk—1)生成P=Rk—1P+tk—1;②計算Tk—1下點云模型M和P所夾三維空間的平均體積誤差測度E(Tk—1);③找到點云模型P中所有點在M上的最近對應點,并取所有對應點對中距離最近的90%作為有效的對應點對;④利用旋轉向量,按照Gelfand等[13]的方法線性化旋轉矩陣Rk,從而通過求解一個線性系統得到新的變換關系矩陣Tk,直到 E(|Tk—5|)—E(|Tk|)≤10—4或者k=kend,迭代終止。

(3)輸出最優的變換關系Tk=(Rk,tk)。

4 實驗結果與分析

將掛鉤放在旋轉平臺的中心,旋轉平臺每轉動10°,三維激光掃描儀 VIVID910掃描一次,分別獲取在旋轉角度為 0°、10°、20°、30°、…、350°時的掛鉤激光點云數據。實驗目的在于對依次相鄰視點獲取的激光掃描數據進行配準,驗證本文提出的改進迭代最近點算法的有效性、正確性和可行性,比較本文方法與以往方法的配準精度與收斂速度,為后續曲面物體深度圖像的分割提供完整三維幾何模型。

首先對掛鉤的 36片激光點云用文獻[11,16-17]中的方法進行平滑、濾波、去噪、簡化等數據預處理。然后選取角度為0°的位置作為空間參考坐標系,依次對其他視角獲取的點云數據配準到該參考坐標系。將多視角點云模型的配準轉化成依次進行的兩兩配準,并按照本文的改進算法完成。

限于篇幅,只用初始位置0°(基準模型)和旋轉10°兩視角的點云模型進行配準,并將其配準結果、配準精度和時間效率與文獻[18]基于對應點距離平方均值誤差測度的算法進行比較。圖2a所示為位于初始位置0°、用三維激光掃描儀VIVID910得到的基準點云模型,含有51 322個三維數據點;圖2b所示為旋轉10°后用三維激光掃描儀VIVID910得到的點云模型,含有51 397個三維數據點。

圖3a所示為文獻[18]算法的配準結果,該算法利用兩個三維點云模型之間的平均歐氏距離作為誤差測度。其中,圖3b所示為本文算法的配準結果。對照圖2可以看出,圖3b的配準結果要明顯優于圖3a的配準結果。基于對應點對距離的配準算法往往陷入局部最優而無法得到正確的空間變換關系,而本文算法卻可以得到比較精確的配準結果。

圖4所示為圖3中兩種配準算法收斂速度的比較。由于配準誤差的單位不一樣(本文算法的單位是mm3,文獻[18]算法的單位是mm),因此分別在兩幅圖中顯示了兩種算法迭代100次的誤差分布。表1所示為圖3中配準結果的定量比較,這些結果是在Pentium Ⅳ,2.66GHz CPU,960MB內存的PC機上計算得到的,開發平臺是MATLAB7.0。

由于利用海倫公式求解三角形面積需要更多的計算,因此本文算法每一次迭代的運行時間會略長。然而,如表1中有效點對數量的統計,由于滿足條件的三角形對的數量要遠遠小于對應點對的數量,因此,本文算法只需較少的時間就可以計算出新的空間位置變換關系,從而保證了每一次迭代的運行時間和文獻[18]算法相比差距不大,再考慮迭代次數,顯然本文算法具有更快的收斂速度。

表1 圖3中配準結果的定量比較

圖5所示是按照本文改進算法和實驗方法依次完成所有36個掛鉤點云模型兩兩配準后,得到的完整掛鉤多視角點云模型配準融合三維幾何曲面模型。

5 結束語

本文在分析了現有點云模型配準方法的基礎上,提出了一種基于表面間點與對應三角形所夾三棱錐平均體積誤差測度的三角網格精確配準算法,與現有ICP框架下的迭代配準方法相比,該算法主要有兩個貢獻:一是提出了表面間平均體積測度的概念,該測度衡量的不是對應點對或者點面之間的歐氏距離,而是點與對應三角形所夾三棱錐的平均體積;二是采用一種與表面間平均體積測度相匹配的選點策略,通過從點與對應三角形的質心所形成的點對中選取最近對應點對,有效地排除了偏離點的影響,確保了算法的精度和速度。

[1]戴靜蘭,陳志楊,葉修梓.ICP算法在點云配準中的應用[J].中國圖像圖形學報,2007,12(3):517-521.

[2]路銀北,張蕾,普杰信,等.基于曲率的點云數據配準算法[J].計算機應用,2007,27(11):2766-2769.

[3]朱延娟,周來水,張麗艷.散亂點云數據配準算法[J].計算機輔助設計與圖形學學報,2006,18(4):475-480.

[4]Besl P J,McKay N D.A Method for Registration of 3—D Shapes[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,1992,14(2):239-256.

[5]Chen Y,Medioni G.Object Modeling by Registration of Multiple Range Images[C]//Proceedings of IEEE International Conference on Robotics and Automation.Sacramento,CA,1991:2724-2729.

[6]Blais G,Levine M D.Registering Multi—view Range Data to Create 3D Computer Graphics[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,1995,17(8):820-824.

[7]Li Q,Griffiths J G.Iterative Closest Geometric Objects Registration[J].Computers and Mathematics with Applications,2000,40(10):1171-1188.

[8]張學昌,習俊通,嚴雋琪.基于點云數據的復雜型面數字化檢測技術研究[J].計算機集成制造系統—CIMS,2005,11(5):727-731.

[9]Helmut P,Stdfan L,Michael H.Registration without ICP[J].Computer Vision and Image Understanding,2004,95:54-71.

[10]Masuda T,Sakaue K,Yokoya N.Registration and Integration of M ultiple Range Images for 3—D Model Construction[C]//Proceedings of the 13th International Conference on Pattenrn Recognition.Vienna,1996:879-883.

[11]吳敏,周來水,王占東,等.測量點云數據的多視拼合技術研究[J].南京航空航天大學學報,2003,35(4):552-555.

[12]賈云得.機器視覺[M].北京:科學出版社,2000.

[13]Gelfand N,Ikemoto L,Rusinkiewicz S,et al.Geometrically Stable Sampling for the ICP Algorithm[C]//Proceedings of the 4th International Conference on 3D Digital Imaging and Modeling.Banff,2003:260-267.

[14]張鴻賓,謝豐.基于表面間距離度量的多視點距離圖像的對準算法[J].中國科學 E輯:信息科學,2005,35(2):150-160.

[15]Turk G,Levoy M.Zipped Polygon Meshes from Range Image[C]//Proceedings of ACM,Siggraph.Orlando,1994:311-318.

[16]李劍.基于激光測量的自由曲面數字制造基礎技術研究[D].杭州:浙江大學,2001.

[17]Dalley G,Flynn P.Range Image Registration:a Software Platform and Empirical Evaluation[C]//Proceedings of the 3rd International Conference on 3D Digital Imaging and Modeling.Quebec,2001:246-253.

[18]Pulli K.Multi—view Registration for Large Data Sets[C]//Proceedings the 2nd International Conference on 3D Digital Imaging and Modeling.Ottawa,1999:160—168.