李彩林，郭寶云，季　錚

1. 山東理工大學(xué)建筑工程學(xué)院，山東 淄博 255049； 2. 武漢大學(xué)遙感信息工程學(xué)院，湖北 武漢 430079

Global Optimization and Whole Registration Algorithm of Multi-view 3D Laser Point Cloud

LI Cailin1,GUO Baoyun1,JI Zheng2

1. Institute of Architecture and Engineering, Shandong University of Technology, Zibo 255049, China; 2. School of Remote Sensing and Information Engineering, Wuhan University, Wuhan 430079, China

Foundation support： The National Natural Science Foundation of China (No. 41301518); Geographic National Condition Monitoring Engineering Research Center of Sichuan Province (No. GC201512); The Young Teacher Development Support Foundation of Shandong University of Technology(No.114016); Doctoral Scientific Research Foundation of Shandong University of Technology (Nos. 413042; 413050)

多視角三維激光點(diǎn)云全局優(yōu)化整體配準(zhǔn)算法

李彩林1，郭寶云1，季錚2

1. 山東理工大學(xué)建筑工程學(xué)院，山東 淄博 255049； 2. 武漢大學(xué)遙感信息工程學(xué)院，湖北 武漢 430079

Global Optimization and Whole Registration Algorithm of Multi-view 3D Laser Point Cloud

LI Cailin1,GUO Baoyun1,JI Zheng2

1. Institute of Architecture and Engineering, Shandong University of Technology, Zibo 255049, China; 2. School of Remote Sensing and Information Engineering, Wuhan University, Wuhan 430079, China

Foundation support： The National Natural Science Foundation of China (No. 41301518); Geographic National Condition Monitoring Engineering Research Center of Sichuan Province (No. GC201512); The Young Teacher Development Support Foundation of Shandong University of Technology(No.114016); Doctoral Scientific Research Foundation of Shandong University of Technology (Nos. 413042; 413050)

摘要：提出一種已知多視激光點(diǎn)云配準(zhǔn)初值進(jìn)行自動全局優(yōu)化的整體配準(zhǔn)算法，并詳細(xì)推導(dǎo)了多視激光點(diǎn)云配準(zhǔn)全局優(yōu)化平差模型。本算法對多視角三維激光點(diǎn)云的掃描順序不作要求，可以處理無序散亂的多視三維激光掃描點(diǎn)云，同時(shí)可以獲得最小二乘意義下的最優(yōu)變換參數(shù)，實(shí)現(xiàn)多視三維激光點(diǎn)云的自動精確配準(zhǔn)。利用實(shí)際三維激光掃描點(diǎn)云數(shù)據(jù)進(jìn)行試驗(yàn)，得到了預(yù)期的結(jié)果，驗(yàn)證了本文方法的可行性和有效性。

關(guān)鍵詞：多視三維激光點(diǎn)云；全局優(yōu)化；點(diǎn)云配準(zhǔn)；最小二乘平差；整體配準(zhǔn)模型

1引言

近年來，三維激光掃描測量技術(shù)發(fā)展迅速，在逆向工程、工業(yè)測量、文物數(shù)字化保護(hù)等方面得到了廣泛的應(yīng)用[1-2]。在實(shí)際應(yīng)用中，為了獲取物體表面完整的三維點(diǎn)云需要對被測物體進(jìn)行多角度掃描，進(jìn)而需要將多視激光點(diǎn)云配準(zhǔn)到統(tǒng)一的坐標(biāo)系中，所以配準(zhǔn)精度會直接影響物體最終的三維重構(gòu)精度[3]。因此對初始配準(zhǔn)后的三維激光點(diǎn)云進(jìn)行全局優(yōu)化整體配準(zhǔn)將具有十分重要的現(xiàn)實(shí)意義。

計(jì)算機(jī)視覺界的相關(guān)學(xué)者對點(diǎn)云配準(zhǔn)領(lǐng)域的研究主要集中在兩視點(diǎn)云之間的配準(zhǔn)，大多都基于文獻(xiàn)[4]提出的最鄰近點(diǎn)迭代方法(iterative closest point，ICP)，通過迭代選擇對應(yīng)點(diǎn)計(jì)算滿足對應(yīng)點(diǎn)之間的距離誤差最小條件的旋轉(zhuǎn)平移變換矩陣[5-6]。在ICP算法的基礎(chǔ)上，很多論文對搜索最鄰近點(diǎn)的方法進(jìn)行了改進(jìn)[7-10]，如提出了point-point、point-to-plane、point-to-projection等方法搜索最鄰近點(diǎn)，文獻(xiàn)[11]采用K-D樹加快了最鄰近點(diǎn)的查找速度。此外，文獻(xiàn)[12]提出了基于彩色三維掃描數(shù)據(jù)的配準(zhǔn)方法，主要在ICP算法中考慮三維掃描點(diǎn)的紋理色彩信息進(jìn)行搜索最鄰近點(diǎn)。文獻(xiàn)[13—14]提出了基于曲率的點(diǎn)云數(shù)據(jù)配準(zhǔn)算法，并結(jié)合改進(jìn)的ICP算法對點(diǎn)云進(jìn)行精確配準(zhǔn)。但以上這些算法都局限于兩視點(diǎn)云之間的兩兩配準(zhǔn)。

在多視三維激光點(diǎn)云整體配準(zhǔn)領(lǐng)域的研究主要集中在依賴儀器的配準(zhǔn)和半自動配準(zhǔn)方面[15]。文獻(xiàn)[16]提出一種激光掃描多視三維點(diǎn)云的全自動無縫鑲嵌算法，應(yīng)用閉合條件約束的整體平差模型，實(shí)現(xiàn)了激光掃描儀多視三維點(diǎn)云的全自動無縫鑲嵌，但該方法只適用于特定硬件設(shè)備獲取的360°閉合有序的多視三維點(diǎn)云，對于覆蓋物體表面局部區(qū)域或散亂無序的多視點(diǎn)云全局優(yōu)化不適用。文獻(xiàn)[17]提出一種針對旋轉(zhuǎn)平臺獲取三維掃描點(diǎn)云數(shù)據(jù)的配準(zhǔn)方法，能夠?qū)崿F(xiàn)將多視三維掃描數(shù)據(jù)自動配準(zhǔn)到統(tǒng)一的坐標(biāo)系中，配準(zhǔn)精度與ICP配準(zhǔn)或標(biāo)志點(diǎn)配準(zhǔn)精度相當(dāng)。該方法自動化程度高，但需要借助旋轉(zhuǎn)平臺獲取物體表面的三維點(diǎn)云數(shù)據(jù)，同時(shí)需要標(biāo)定旋轉(zhuǎn)平臺與掃描儀之間的相對位置關(guān)系，因此適用性相對較低。文獻(xiàn)[18—19]提出一種基于光束法區(qū)域網(wǎng)平差的地面激光掃描多站點(diǎn)云自動定向方法和整體定向平差模型，該方法通過標(biāo)靶的布設(shè)以及標(biāo)靶的自動探測和重復(fù)標(biāo)靶的識別，實(shí)現(xiàn)全區(qū)域多站激光點(diǎn)云自動配準(zhǔn)。文獻(xiàn)[20]提出一種基于序列迭代的多視點(diǎn)云三維配準(zhǔn)方法，該方法有效抑制了序列配準(zhǔn)的累積誤差，但是配準(zhǔn)過程中人工操作比較多，因而還必須進(jìn)一步研究全局性、自動化的多視點(diǎn)云配準(zhǔn)方法。

本文為了提高物體表面三維模型的重構(gòu)精度，提出一種多視激光點(diǎn)云全局優(yōu)化整體配準(zhǔn)算法。該算法是在已知多視激光點(diǎn)云配準(zhǔn)初值的基礎(chǔ)上，通過估計(jì)點(diǎn)云的密度，自動檢測所有具有一定重疊度的兩視點(diǎn)云，然后利用K-D樹[21]搜索具有一定重疊度兩視點(diǎn)云中的近似同名點(diǎn)，并將其作為觀測值代入到全局優(yōu)化平差模型中，通過迭代平差計(jì)算，獲得多視激光點(diǎn)云各自最優(yōu)的旋轉(zhuǎn)平移變換參數(shù)，從而完成多視角三維激光點(diǎn)云的整體精確配準(zhǔn)。

2多視角三維激光點(diǎn)云配準(zhǔn)全局優(yōu)化平差模型的建立

假設(shè)對一個(gè)物體表面進(jìn)行多視角掃描，共獲取K個(gè)視角的三維點(diǎn)云，并且假定這K個(gè)視角的三維點(diǎn)云之間具有一定的重疊區(qū)域，同時(shí)K個(gè)視角點(diǎn)云已經(jīng)過初始配準(zhǔn)統(tǒng)一到同一個(gè)坐標(biāo)系中。初始配準(zhǔn)以后，為了進(jìn)一步提高三維模型整體的配準(zhǔn)精度，需要進(jìn)行多視點(diǎn)云全局優(yōu)化整體配準(zhǔn)。全局優(yōu)化的目的是確定旋轉(zhuǎn)平移參數(shù)Ri、ti(i=1,2,…,K)，使得整體配準(zhǔn)誤差e最小，如式(1)所示。

(1)

式中，m、n分別表示第m個(gè)視角和第n個(gè)視角的點(diǎn)云，即多視點(diǎn)云的視角序號；K表示多視三維點(diǎn)云的數(shù)量，即共有K個(gè)視角的點(diǎn)云；Nmn表示第m個(gè)視角點(diǎn)云和第n個(gè)視角點(diǎn)云重疊區(qū)域中的近似同名點(diǎn)對的數(shù)量；Pmi、Pni代表第m個(gè)視角點(diǎn)云和第n個(gè)視角點(diǎn)云中第i對近似同名點(diǎn)；Rm、tm分別表示將第m個(gè)視角的點(diǎn)云轉(zhuǎn)換到基準(zhǔn)坐標(biāo)系下的旋轉(zhuǎn)矩陣和平移向量；Rn、tn分別表示將第n個(gè)視角的點(diǎn)云轉(zhuǎn)換到基準(zhǔn)坐標(biāo)系下的旋轉(zhuǎn)矩陣和平移向量。式(1)中

將Rm、tm、Rn、tn、Pmi、Pni代入式(1)中，得到

(2)

將式(2)簡化后寫成

(3)

(4)

V=AX-L

(5)

式中

X=[Δφ2Δω2Δκ2ΔX2ΔY2ΔZ2…

ΔφKΔωKΔκKΔXKΔYKΔZK]T

L=-(f)

由于旋轉(zhuǎn)矩陣是由3個(gè)旋轉(zhuǎn)角的9個(gè)方向余弦值組成[22]，結(jié)合式(2)，經(jīng)推導(dǎo)可以得到誤差方程式中各偏導(dǎo)數(shù)的值。限于篇幅，各項(xiàng)偏導(dǎo)數(shù)的表達(dá)式從略。多視激光點(diǎn)云配準(zhǔn)全局優(yōu)化平差模型(式(5))為典型的間接平差模型，利用多視點(diǎn)云重疊區(qū)域中的近似同名點(diǎn)即可通過最小二乘法獲得多視點(diǎn)云各自的旋轉(zhuǎn)平移變換參數(shù)。

3算法實(shí)現(xiàn)

在經(jīng)過初始配準(zhǔn)后的多視點(diǎn)云的基礎(chǔ)上，本文提出一種多視點(diǎn)云全局優(yōu)化整體配準(zhǔn)算法。首先估計(jì)三維點(diǎn)云的密度，然后自動檢測多視三維點(diǎn)云中所有具有一定重疊度的兩視點(diǎn)云，最后采用K-D樹搜索重疊區(qū)域的最鄰近點(diǎn)對作為近似同名點(diǎn)對，代入到平差模型中整體解算多視點(diǎn)云之間的坐標(biāo)系變換參數(shù)。算法的詳細(xì)實(shí)現(xiàn)步驟如下：

(1) 對一個(gè)物體表面進(jìn)行多視角掃描，假定共獲取有K個(gè)視角的三維點(diǎn)云，并且相互之間具有一定重疊區(qū)域，對具有一定重疊區(qū)域的兩視點(diǎn)云可以通過手工選取同名點(diǎn)的方式進(jìn)行兩兩配準(zhǔn)，直到將K個(gè)視角的三維點(diǎn)云都變換到同一個(gè)坐標(biāo)系中，或通過配準(zhǔn)軟件將K視角三維點(diǎn)云初步統(tǒng)一到同一個(gè)坐標(biāo)系中。

(2) 估計(jì)多視角三維點(diǎn)云的密度D。這里假定多視角三維點(diǎn)云是使用同一種掃描手段獲取的，因此認(rèn)為K個(gè)視角的點(diǎn)云密度基本相同，以其中一個(gè)視角點(diǎn)云為例來介紹點(diǎn)云密度估計(jì)的方法：

(6)

式中，n為采樣點(diǎn)的數(shù)量。

(3) 遍歷經(jīng)過粗配準(zhǔn)后的K視三維點(diǎn)云，自動檢測所有具有一定重疊度的兩視三維點(diǎn)云，并將點(diǎn)云序號保存至動態(tài)數(shù)組中，具體檢測方法如下：①定義一個(gè)二維動態(tài)數(shù)組I，將第一維大小設(shè)置為K-1；②從第2視角到第K視角點(diǎn)云中，檢測與第1視角點(diǎn)云具有一定重疊度的三維點(diǎn)云，并將點(diǎn)云視角序號依次保存到I[0]中；③從第3視角到第K視角點(diǎn)云中，檢測與第2視角點(diǎn)云具有一定重疊度的三維點(diǎn)云，并將點(diǎn)云視角序號依次保存到I[1]中；④依次類推，直到檢測第K視角點(diǎn)云與第K-1視角點(diǎn)云是否具有一定重疊度，若有一定重疊度則將視角序號K保存到I[K-2]中。

本文中計(jì)算兩視點(diǎn)云重疊度的方法定義如下：

假設(shè)兩視點(diǎn)云中的三維點(diǎn)的數(shù)量分別為m和n，遍歷其中一個(gè)點(diǎn)云中的三維點(diǎn)，在另外一個(gè)點(diǎn)云中搜索與該三維點(diǎn)最鄰近的點(diǎn)，如果這兩點(diǎn)之間的距離小于一定閾值(閾值一般為3倍點(diǎn)云密度)時(shí)，則定義該兩點(diǎn)為近似同名點(diǎn)。利用K-D樹檢測該兩視點(diǎn)云中所有的近似同名點(diǎn)，并假定其數(shù)量為N，則該兩視點(diǎn)云的重疊度W計(jì)算公式如下

(7)

考慮到重疊度對配準(zhǔn)精度的影響，本文中定義當(dāng)W>0.2時(shí)，則判斷該兩視點(diǎn)云具有一定的重疊度。根據(jù)以上的描述，對于圖1所示的多視角三維點(diǎn)云，自動檢測得到的重疊度動態(tài)數(shù)組如圖2所示。其中點(diǎn)云1表示第1視角的點(diǎn)云，以此類推，點(diǎn)云4表示第4視角的點(diǎn)云。

圖1　多視角點(diǎn)云覆蓋范圍分布圖Fig.1　Coverage maps of multi-view point cloud

從重疊度動態(tài)數(shù)組中可以看出，與點(diǎn)云1具有一定重疊度的是點(diǎn)云2和點(diǎn)云4；與點(diǎn)云2具有一定重疊度的是點(diǎn)云3和點(diǎn)云4；與點(diǎn)云3具有一定重疊度的是點(diǎn)云4。實(shí)際上圖1中顯示的點(diǎn)云3和點(diǎn)云1也有部分重疊區(qū)域，但由于重疊度W<0.2，不滿足上述提出的具有一定重疊度的條件，所以判斷點(diǎn)云3與點(diǎn)云1不具有一定的重疊度。

圖2　重疊度動態(tài)數(shù)組Fig.2　Dynamic arrays of overlap

(4) 由步驟(3)可以檢測出K視角點(diǎn)云中所有具有一定重疊度的兩視點(diǎn)云，然后利用K-D樹搜索這些具有一定重疊度的兩視角點(diǎn)云中的近似同名點(diǎn)對，并將這些近似同名點(diǎn)對作為觀測值代入誤差方程式(4)中參與平差計(jì)算。

步驟(4)中，有幾點(diǎn)需要指出的是：

(1) 在平差過程中，對于具有一定重疊度的兩視點(diǎn)云中近似同名點(diǎn)對的確定方法是，考慮到多視點(diǎn)云初始配準(zhǔn)結(jié)果的精度有限，因此在前3次迭代中若兩最鄰近點(diǎn)距離小于3D(3倍點(diǎn)云密度)時(shí)就認(rèn)為是近似同名點(diǎn)；經(jīng)過3次迭代平差后，多視點(diǎn)云的配準(zhǔn)結(jié)果整體得到優(yōu)化，因此在第3次以后的迭代中，兩個(gè)最鄰近點(diǎn)之間距離滿足小于nD(1

(2) 由于每次循環(huán)迭代后，多視點(diǎn)云都會得到各自新的旋轉(zhuǎn)平移參數(shù)，因此每次迭代平差過程中的觀測值(即兩視點(diǎn)云中的近似同名點(diǎn))都需要重新進(jìn)行計(jì)算獲取，從而造成計(jì)算量較大。另外，近似同名點(diǎn)對數(shù)量越多即誤差方程個(gè)數(shù)越多，誤差方程規(guī)模也會越大。因此為了適當(dāng)降低計(jì)算量以及誤差方程的規(guī)模，本文采取的方法是，對于具有一定重疊度的兩視點(diǎn)云，在其中一個(gè)點(diǎn)云中通過間隔采樣點(diǎn)，利用K-D樹在另一個(gè)點(diǎn)云中搜索該采樣點(diǎn)的近似同名點(diǎn)。間隔采樣的程度根據(jù)兩視點(diǎn)云的重疊度和點(diǎn)的數(shù)量來確定。

(3) 迭代終止條件的確定。本文試驗(yàn)中迭代次數(shù)設(shè)定的最大值為50次，旋轉(zhuǎn)角參數(shù)的改正數(shù)限差設(shè)定為0.1′(3×10-5弧度)，平移參數(shù)的改正數(shù)限差設(shè)定為D/5。

綜上所述，本文提出的多視角三維點(diǎn)云全局優(yōu)化配準(zhǔn)算法的具體實(shí)現(xiàn)流程如圖3所示。

圖3　多視三維點(diǎn)云全局優(yōu)化配準(zhǔn)算法流程圖Fig.3　Flow chart of global optimization registration algorithm of multi-view 3D point cloud

4試驗(yàn)和分析

為了驗(yàn)證本文方法的有效性，利用武漢大學(xué)數(shù)字?jǐn)z影測量與計(jì)算機(jī)視覺研究中心提供的三維激光掃描儀掃描得到的一組玩偶模型數(shù)據(jù)進(jìn)行試驗(yàn)和分析。利用激光掃描儀對玩偶模型掃描共獲得8個(gè)視角的三維掃描數(shù)據(jù)，如圖4所示。

對掃描數(shù)據(jù)進(jìn)行了兩組試驗(yàn)，并對結(jié)果進(jìn)行比較分析。第1組試驗(yàn)，對具有一定重疊區(qū)域的兩視點(diǎn)云手動選取3對及以上同名點(diǎn)，計(jì)算初始剛體變換參數(shù)，然后利用ICP算法實(shí)現(xiàn)兩視點(diǎn)云的精確配準(zhǔn)，通過這種兩兩配準(zhǔn)的方法將所有掃描數(shù)據(jù)變換到同一個(gè)坐標(biāo)系中。第2組試驗(yàn)，應(yīng)用本文提出的多視點(diǎn)云全局優(yōu)化配準(zhǔn)算法，進(jìn)行整體平差后解求出各視角三維點(diǎn)云的變換參數(shù)，再根據(jù)解算出的變換參數(shù)將所有掃描數(shù)據(jù)統(tǒng)一到同一個(gè)坐標(biāo)系中，全局優(yōu)化配準(zhǔn)后的點(diǎn)云模型見圖5。

圖4　玩偶模型多個(gè)視角的三維點(diǎn)云數(shù)據(jù)Fig.4　Multi-view 3D point cloud data of doll model

圖5　全局優(yōu)化整體配準(zhǔn)后的點(diǎn)云模型　Fig.5　Point cloud model after global optimization registration

(8)

根據(jù)距離中誤差計(jì)算公式，第1組試驗(yàn)得到的配準(zhǔn)中誤差為0.41mm，第2組試驗(yàn)得到的配準(zhǔn)中誤差為0.18mm；經(jīng)計(jì)算得到玩偶三維掃描數(shù)據(jù)的點(diǎn)云密度為0.28mm。試驗(yàn)結(jié)果表明，全局優(yōu)化整體配準(zhǔn)精度要明顯優(yōu)于使用ICP算法進(jìn)行兩兩點(diǎn)云配準(zhǔn)的精度。另外從試驗(yàn)結(jié)果還可以看出，全局優(yōu)化配準(zhǔn)中誤差近似為0.6倍點(diǎn)云密度，因此全局優(yōu)化整體配準(zhǔn)的精度比較理想。

在算法迭代收斂方面，為了使本文提出的整體配準(zhǔn)算法和ICP算法的迭代收斂情況具有可比性，兩種算法均采用點(diǎn)與點(diǎn)間歐氏距離最近來搜索近似同名點(diǎn)，同時(shí)在兩種算法中設(shè)置相同的迭代終止條件(見算法實(shí)現(xiàn)步驟(4)中的說明(3))。另外考慮到ICP算法一般都應(yīng)用于兩視點(diǎn)云的精確配準(zhǔn)中，故設(shè)計(jì)如下試驗(yàn)：取8個(gè)視角點(diǎn)云中的任意兩視具有一定重疊度的點(diǎn)云(第1視角和第4視角點(diǎn)云)，使用本文算法進(jìn)行配準(zhǔn)，共迭代11次滿足平差終止條件，3個(gè)平移參數(shù)改正數(shù)收斂較快(第5次迭代時(shí)已收斂)，3個(gè)旋轉(zhuǎn)角參數(shù)的改正數(shù)迭代后期收斂相對較慢(第7次迭代時(shí)3個(gè)旋轉(zhuǎn)角參數(shù)的改正數(shù)絕對值都小于5×10-5，而本文中設(shè)定的限差為3×10-5)；使用ICP算法對該兩視點(diǎn)云進(jìn)行配準(zhǔn)，同樣共迭代了11次滿足了迭代終止條件。從上述兩視點(diǎn)云配準(zhǔn)的迭代試驗(yàn)可以看出整體配準(zhǔn)算法和ICP算法的迭代收斂效率基本相當(dāng)。

在算法運(yùn)行效率方面，由于ICP算法每次只能實(shí)現(xiàn)兩視點(diǎn)云的精確配準(zhǔn)，通過兩兩配準(zhǔn)的方法將所有掃描數(shù)據(jù)變換到同一個(gè)坐標(biāo)系中，因此8個(gè)視角點(diǎn)云的配準(zhǔn)至少需要經(jīng)過7次ICP算法的兩兩配準(zhǔn)。統(tǒng)計(jì)這7次ICP算法運(yùn)行的時(shí)間(沒有統(tǒng)計(jì)人工選取具有重疊區(qū)域的兩視角點(diǎn)云所需的時(shí)間)，總耗時(shí)為81s。應(yīng)用本文提出的多視點(diǎn)云整體配準(zhǔn)算法，共需要93s。由于整體配準(zhǔn)算法和ICP算法的迭代收斂效率基本相同，而前者所耗費(fèi)的時(shí)間稍大于后者，究其原因在于整體配準(zhǔn)算法需要程序自動估計(jì)多視點(diǎn)云中所有的具有一定重疊區(qū)域的兩視點(diǎn)云，另外在整體平差過程中需要搜索所有具有一定重疊區(qū)域的兩視點(diǎn)云中的近似同名點(diǎn)，因此對具有多度重疊區(qū)域的多視角點(diǎn)云來說，整體配準(zhǔn)算法則比ICP兩兩配準(zhǔn)方法相應(yīng)增加了搜索近似同名點(diǎn)的時(shí)間。全局優(yōu)化配準(zhǔn)過程的各項(xiàng)參數(shù)指標(biāo)見表1所示。

表1　玩偶模型全局優(yōu)化配準(zhǔn)的各項(xiàng)參數(shù)統(tǒng)計(jì)

5結(jié)論

本文介紹了一種已知多視激光點(diǎn)云配準(zhǔn)初值進(jìn)行自動全局優(yōu)化的精確配準(zhǔn)算法，并詳細(xì)推導(dǎo)了多視激光點(diǎn)云全局優(yōu)化整體平差模型，給出了算法詳細(xì)的實(shí)現(xiàn)步驟，獲得了最小二乘意義下的最優(yōu)變換參數(shù)。最后通過試驗(yàn)證明了本文方法的可行性和有效性，實(shí)現(xiàn)了多視角三維激光點(diǎn)云的整體精確配準(zhǔn)。文中提出的整體配準(zhǔn)算法至少需要兩視角點(diǎn)云，即算法適用于兩視角及以上視角點(diǎn)云的配準(zhǔn)，對兩視點(diǎn)云之間的配準(zhǔn)，整體配準(zhǔn)算法相比于經(jīng)典的ICP算法精度基本相當(dāng)，對具有多度重疊區(qū)域的多視角點(diǎn)云，從試驗(yàn)結(jié)果可以看出本文方法的配準(zhǔn)精度較ICP算法有較大的提高。

多視角三維激光點(diǎn)云整體配準(zhǔn)算法相對于ICP兩兩精確配準(zhǔn)算法，優(yōu)點(diǎn)是能夠自動地對散亂無序的掃描點(diǎn)云進(jìn)行整體精確配準(zhǔn)，配準(zhǔn)精度較ICP算法有較大的提高，同時(shí)減少了人工搜尋具有重疊區(qū)域的兩視點(diǎn)云的過程；缺點(diǎn)是整體配準(zhǔn)算法需要自動估計(jì)所有具有一定重疊區(qū)域的兩視點(diǎn)云，另外在整體平差過程中需要搜索所有具有一定重疊區(qū)域的兩視點(diǎn)云中的近似同名點(diǎn)，因此在計(jì)算效率上稍低于ICP兩兩精確配準(zhǔn)算法。未來的研究側(cè)重于實(shí)現(xiàn)GPU并行化處理，進(jìn)一步提高多視角三維點(diǎn)云全局優(yōu)化整體配準(zhǔn)算法的效率。

參考文獻(xiàn)：

[1]ZHENGLi. 3DMeasurementofIrregularSheetmetalPartsBasedonStructuredLight[D].Wuhan:WuhanUniversity，2007.(鄭莉. 基于結(jié)構(gòu)光的不規(guī)則鈑金件三維量測[D]. 武漢:武漢大學(xué), 2007.)

[2]ZHAIRuifang,ZHANGJianqing.AutomaticRegistrationofPointCloudsBasedonLaserScanner[J].GeospatialInformation, 2004, 2(6): 37-39.(翟瑞芳, 張劍清. 基于激光掃描儀的點(diǎn)云模型的自動拼接[J]. 地理空間信息, 2004, 2(6): 37-39.)

[3]LISKAC,SABLATNINGR.Adaptive3DAcquisitionUsingLaserLight[C]∥ProceedingsofCzechPatternRecognitionWorkshop.Praha:[s.n.], 2000:111-116.

[4]BESLPJ,MCKAYND.AMethodforRegistrationof3DShapes[J].IEEETransactionsonPatternAnalysisandMachineIntelligence, 1992, 14(2): 239-239.

[5]NATASHAG,LESLIEI,RZYMONR,etal.GeometricallyStableSamplingfortheICPAlgorithm[C]∥ProceedingsofInternationalConferenceon3DDigitalImagingandModeling.Banff:[s.n.], 2003: 260-267.

[6]ZHENGDehua,YUEDongjie,YUEJianping.GeometricFeatureConstraintBasedAlgorithmforBuildingScanningPointCloudRegistration[J].ActaGeodaeticaetCartographicaSinica, 2008, 37(4): 465-468.(鄭德華, 岳東杰, 岳建平. 基于幾何特征約束的建筑物點(diǎn)云配準(zhǔn)算法[J]. 測繪學(xué)報(bào), 2008, 37(4): 465-468.)

[7]CHENY,MEDIONIG.ObjectModelingbyRegistrationofMultipleRangeImages[J].ImageandVisionComputing, 1992, 10: 145-155.

[8]BERGEVINR,SOUCYM,GAGNONH,etal.TowardsaGeneralMulti-viewRegistrationTechnique[J].IEEETransactionsonPatternAnalysisandMachineIntelligence, 1996, 18(5): 540-547.

[9]RUSINKIEWICZS,LEVOYM.EfficientVariantsoftheICPAlgorithm[C]∥ProceedingsofThirdInternationalConferenceon3-DDigitalImagingandModeling.Piscataway:IEEE. 2001:145-152.

[10]PARKSY,SUBBARAOM.AnAccurateandFastPoint-to-planeRegistrationTechnique[J].PatternRecognitionLetters, 2003, 24: 2967-2976.

[11]ZOUJixiang.TheResearchofPointCloudDataRegistrationTechniqueBasedonKD-treeAcceleration[D].Hefei:AnhuiUniversity, 2013.(鄒際祥. 基于KD-tree加速的點(diǎn)云數(shù)據(jù)配準(zhǔn)技術(shù)研究[D]. 合肥: 安徽大學(xué), 2013.)

[12]JOHNSONAE,KANGSB.RegistrationandIntegrationofTextured3DData[J].ImageandVisionComputing, 1999, 17: 135-147.

[13]LUYinbei,ZHANGLei,PUJiexin,etal.Curvature-basedRegistrationAlgorithmofPointCloudsData[J].ComputerApplications, 2007, 27(11): 2766-2768.(路銀北, 張蕾, 普杰信, 等. 基于曲率的點(diǎn)云數(shù)據(jù)配準(zhǔn)算法[J]. 計(jì)算機(jī)應(yīng)用, 2007, 27(11): 2766-2768.)

[14]QIANPengpeng,ZHENGDehua.ANewAutomaticRegistrationMethodofScanningPointCloud[J].JournalofWaterResourcesandArchitecturalEngineering, 2013, 11(3): 162-165.(錢鵬鵬, 鄭德華. 一種新的掃描點(diǎn)云自動配準(zhǔn)方法[J]. 水利與建筑工程學(xué)報(bào), 2013, 11(3): 162-165.)

[15]DAIJinglan,CHENZhiyang,YEXiuzi.TheApplicationofICPAlgorithminPointCloudAlignment[J].JournalofImageandGraphics, 2007, 12(3): 517-521.(戴靜蘭, 陳志楊, 葉修梓.ICP算法在點(diǎn)云配準(zhǔn)中的應(yīng)用[J]. 中國圖象圖形學(xué)報(bào), 2007, 12(3): 517- 521.)

[16]ZHANGJianqing,ZHAIRuifang,ZHENGShunyi.AutomaticSeamlessRegistrationof3DMultipleRangeViews[J].GeomaticsandInformationScienceofWuhanUniversity, 2007, 32(2): 100-103. (張劍清, 翟瑞芳, 鄭順義. 激光掃描多三維視圖的全自動無縫鑲嵌[J]. 武漢大學(xué)學(xué)報(bào): 信息科學(xué)版, 2007, 32(2): 100-103.)

[17]ZHOULangming,ZHENGShunyi,HUANGRongyong.ARegistrationAlgorithmforPointCloudsObtainedbyScanningObjectsonTurntable[J].ActaGeodaeticaetCartographicaSinica, 2013, 42(1): 73-79. (周朗明, 鄭順義, 黃榮永．旋轉(zhuǎn)平臺點(diǎn)云數(shù)據(jù)的配準(zhǔn)方法[J]．測繪學(xué)報(bào), 2013, 42(1): 73-79．)

[18]YAOJili,MANing,JIAXiangyang,etal.Auto-registrationforTerrestrialLaserScanningMulti-stationsPointCloudswithBundleBlockAdjustmentMethods[J].ActaGeodaeticaetCartographicaSinica, 2014, 43(7): 711-716. (姚吉利, 馬寧, 賈象陽, 等. 光束法區(qū)域網(wǎng)平差的地面激光掃描多站點(diǎn)云自動定向方法[J]. 測繪學(xué)報(bào), 2014, 43(7): 711-716.)

[19]YAOJili,JIAXiangyang,MANing,etal.OverallOrientationAdjustmentModelofTerrestrialLaserScanningMulti-stationPointClouds[J].ActaGeodaeticaetCartographicaSinica, 2014, 43(8): 835-841. (姚吉利, 賈象陽, 馬寧, 等. 地面激光掃描多站點(diǎn)云整體定向平差模型[J]. 測繪學(xué)報(bào), 2014, 43(8): 835-841.)

[20]LIUJun，GENGGuohua.SequenceIterative3DRegistrationofMulti-viewPointCloudforArchaeologicalSite[J].ApplicationResearchofComputers, 2011, 28(10): 3970-3973.(劉軍, 耿國華. 古遺址多視點(diǎn)云的漸進(jìn)式三維配準(zhǔn)[J]. 計(jì)算機(jī)應(yīng)用研究, 2011, 28(10): 3970-3973.)

[21]MOUNTDM,ARYAS.ANN:ALibraryforApproximateNearestNeighborSearching[EB/OL]. 2010[2013-07-25].http:∥www.cs.u.md.edu/~mount/ANN/.

[22]ZHANGJianqing,PANLi,WANGShugen.Photogrammetry[M].Wuhan：WuhanUniversityPress, 2009: 28-29. (張劍清, 潘勵, 王樹根. 攝影測量學(xué)[M]. 武漢：武漢大學(xué)出版社, 2009: 28-29.)

[23]SEITZSM,CURLESSB,DIEBELJ,etal.AComparisonandEvaluationofMulti-viewStereoReconstructionAlgorithms[C]∥ProceedingsofInternationalConferenceon3DDigitalImagingandModeling.Banff:IEEEComputerSociety, 2003: 260-267.

(責(zé)任編輯：叢樹平)

修回日期： 2014-10-20

Firstauthor：LICailin(1985—),male,PhD,lecturer,majorsindigitalphotogrammetryandcomputervision,three-dimensionallaserscanningdataprocessing.

E-mail：licailin@whu.edu.cn

E-mail：guobaoyun@sdut.edu.cn

中圖分類號：P234

文獻(xiàn)標(biāo)識碼：A

文章編號：1001-1595(2015)02-0183-07

基金項(xiàng)目：國家自然科學(xué)基金(41301518); 四川省地理國情監(jiān)測工程技術(shù)研究中心資助項(xiàng)目(GC201512)；山東理工大學(xué)青年教師發(fā)展支持計(jì)劃經(jīng)費(fèi)(114016)；山東理工大學(xué)博士科研基金(413042; 413050)

收稿日期：2013-12-05

第一作者簡介：李彩林(1985—)，男，博士，講師，研究方向?yàn)閿?shù)字?jǐn)z影測量與計(jì)算機(jī)視覺、三維激光掃描數(shù)據(jù)處理等。

通信作者：郭寶云

Corresponding author：GUO Baoyun

Abstract：A global optimization and whole registration algorithm of multi-view 3D laser point cloud is presented. Detailed derivation of global optimization adjustment model of multi-view laser point cloud is showed in this paper. This algorithm can handle disordered and scattered multi-view 3D laser point cloud, at the same time optimal transformation parameters can be obtained. Practical 3D laser point cloud data are exemplified for the feasibility and effectiveness of proposed methods.

Key words：multiple-view 3D laser point cloud; global optimization; point cloud registration; least squares adjustment; whole registration model

引文格式：LI Cailin, GUO Baoyun, JI Zheng.Global Optimization and Whole Registration Algorithm of Multi-view 3D Laser Point Cloud[J]. Acta Geodaetica et Cartographica Sinica,2015,44(2):183-189.(李彩林，郭寶云，季錚. 多視角三維激光點(diǎn)云全局優(yōu)化整體配準(zhǔn)算法[J].測繪學(xué)報(bào)，2015,44(2)：183-189.) DOI:10.11947/j.AGCS.2015.20130737