結(jié)合形態(tài)描述和直方圖特征改進(jìn)的點(diǎn)云配準(zhǔn)

黃 鵬,丁海勇,劉春雷

(1.南京信息工程大學(xué)遙感與測(cè)繪工程學(xué)院,江蘇 南京 210044； 2.南京龍測(cè)測(cè)繪技術(shù)有限公司,江蘇 南京 210031)

1 引 言

目前,三維激光掃描技術(shù)已被廣泛應(yīng)用于各種場(chǎng)景的測(cè)量與三維重建。使用三維激光掃描技術(shù)可快速獲取建筑物、文物[1]、工程構(gòu)件的完整幾何信息,便于后續(xù)測(cè)量處理。但在實(shí)際掃描過(guò)程中,由于掃描對(duì)象所處的位置及自身的形狀遮擋了光線,無(wú)法得到掃描對(duì)象的完整點(diǎn)云,只能獲取對(duì)象表面部分點(diǎn)云信息[2]。利用點(diǎn)云配準(zhǔn)技術(shù)可以將不同角度獲取的點(diǎn)云數(shù)據(jù)進(jìn)行配準(zhǔn),從而得到掃描對(duì)象的完整點(diǎn)云。

目前廣泛應(yīng)用的點(diǎn)云配準(zhǔn)算法是Besl等提出的迭代最近點(diǎn)(Iterative Closest Point,ICP)算法[3]。但該算法對(duì)配準(zhǔn)點(diǎn)云的初始位置依賴性較強(qiáng),初始位置較差會(huì)陷入局部最優(yōu)狀況,導(dǎo)致配準(zhǔn)效果不佳。為避免上述情況,有學(xué)者采用粗配準(zhǔn)與精配準(zhǔn)相結(jié)合的策略。利用特征描述符來(lái)獲取點(diǎn)與點(diǎn)的對(duì)應(yīng)關(guān)系進(jìn)行粗配準(zhǔn),如點(diǎn)特征直方圖(Point Feature Histograms,PFH)[5]和快速點(diǎn)特征直方圖(Fast Point Feature Histograms,FPFH)[6]、以及方向直方圖(Signatures of Histograms of Orientations,SHOT)[7]等。采用特征點(diǎn)與特征描述符相結(jié)合的方法,以提高點(diǎn)云配準(zhǔn)效率。如李仁忠等將ISS(Intrinsic Shape Signatures)特征點(diǎn)和FPFH相結(jié)合[8]；李宇翔等將ISS特征點(diǎn)和SHOT特征描述符相結(jié)合[2]；荊路等將SIFT(Scale Invariant Feature Transform)特征點(diǎn)和FPFH特征描述符相結(jié)合[9]；劉雷等將SIFT特征點(diǎn)與BSHOT(Binary Signatures of Histograms of Orientations)特征描述符相結(jié)合[10]。這些配準(zhǔn)方法具有較好的整體配準(zhǔn)效果,但這些方法中使用了SIFT法提取特征點(diǎn)或利用SHOT、FPFH特征描述符進(jìn)行SAC-IA粗配準(zhǔn),均會(huì)導(dǎo)致配準(zhǔn)時(shí)間較長(zhǎng)。

針對(duì)點(diǎn)云配準(zhǔn)過(guò)程中配準(zhǔn)效率和精度無(wú)法兼得的問(wèn)題,本研究提出一種將內(nèi)部形態(tài)描述ISS特征點(diǎn)和二進(jìn)制方向直方圖BSHOT[11]特征描述符相結(jié)合的改進(jìn)的點(diǎn)云配準(zhǔn)算法。該方法先對(duì)點(diǎn)云進(jìn)行體素格網(wǎng)下采樣,再采用ISS算法提取特征點(diǎn),降低點(diǎn)云數(shù)量。然后對(duì)ISS特征點(diǎn)計(jì)算SHOT局部特征描述符,并將其轉(zhuǎn)化為二進(jìn)制的BSHOT方向直方圖特征描述符,再采用隨機(jī)采樣一致性算法(RANSAC)去除誤匹配點(diǎn)對(duì),獲得點(diǎn)云配準(zhǔn)的初始變化矩陣。最后利用改進(jìn)的ICP算法進(jìn)行精配準(zhǔn),即將傳統(tǒng)ICP的輸入值改變?yōu)樵袋c(diǎn)云特征點(diǎn)與整體目標(biāo)點(diǎn)云進(jìn)行點(diǎn)云配準(zhǔn)。

2 特征點(diǎn)算法

2.1 形態(tài)描述特征點(diǎn)

特征點(diǎn)是指通過(guò)一定的數(shù)學(xué)運(yùn)算和標(biāo)準(zhǔn)獲取具有豐富信息、穩(wěn)定且獨(dú)特的點(diǎn)集,其數(shù)量遠(yuǎn)小于原始點(diǎn)云數(shù)量。內(nèi)部形態(tài)描述ISS提取特征點(diǎn)是利用鄰域內(nèi)協(xié)方差矩陣的特征值之間關(guān)系來(lái)選取具有代表性和穩(wěn)定性的點(diǎn)集。主要計(jì)算過(guò)程如下[2]:

(1)對(duì)點(diǎn)云數(shù)據(jù)每個(gè)點(diǎn)pi建立局部坐標(biāo)系。搜索半徑區(qū)域?yàn)閞內(nèi)的所有點(diǎn)pj,計(jì)算其與中心點(diǎn)pi的距離權(quán)值wij,如式(1):

(1)

(2)計(jì)算pi與鄰域內(nèi)所有點(diǎn)pj的協(xié)方差矩陣cov(pi),如式(2):

(2)

(3)計(jì)算cov(pi)特征值,從大到小排序?yàn)棣?、λ2、λ3,并設(shè)定閾值ε1、ε2(其值均小于1),若滿足式(3)關(guān)系,則該點(diǎn)為ISS特征點(diǎn):

(3)

2.2 直方圖特征描述

3D特征描述符中SHOT是較為先進(jìn)、描述性較好的直方圖特征描述符。但由于SHOT最終的向量特征整體維度較高(352維),會(huì)導(dǎo)致在后續(xù)配準(zhǔn)中耗時(shí)較長(zhǎng),降低配準(zhǔn)效率。因此將352維的SHOT直方圖向量特征轉(zhuǎn)化為352位的二進(jìn)制數(shù)表示的BSHOT直方圖特征描述符。該方法不僅大幅度減少內(nèi)存空間的占用率,而且使計(jì)算復(fù)雜度降低,可提高后續(xù)配準(zhǔn)的計(jì)算效率。將SHOT特征描述符轉(zhuǎn)化為BSHOT特征描述符,主要是將352維的SHOT特征描述符按4個(gè)為一組進(jìn)行二進(jìn)制轉(zhuǎn)化[11]。設(shè)SHOT特征描述符為{S0,S1,…,S351},每四個(gè)為一組分為A1,A2…A88,每組的和為Ssum,則轉(zhuǎn)化規(guī)則如下[12]:

①若A中任意Si=0,則對(duì)應(yīng)的Bi也為0;

②當(dāng)A不滿足①時(shí),若存在Si大于90 %的Ssum,則對(duì)應(yīng)的Bi=1,其余為0;

③當(dāng)A不滿足①和②時(shí),若存在Si+Sj大于90 %的Ssum,則對(duì)應(yīng)的Bi=Bj=1,其余為0;

④當(dāng)A不滿足①、②和③時(shí),若存在Si+Sj+Sk大于90 %的Ssum,則對(duì)應(yīng)的Bi=Bj=Bk=1,其余為0;

⑤若A對(duì)于①～④均不滿足,則任意Si所對(duì)應(yīng)的Bi均為1;

⑥將88個(gè)組的Bi組合成352位的BSHOT特征描述符{B0,B1,…,B351}。

3 點(diǎn)云配準(zhǔn)

點(diǎn)云配準(zhǔn)過(guò)程分為兩部分:粗配準(zhǔn)和精配準(zhǔn)[13]。粗配準(zhǔn)常用于位置未知的情況,對(duì)兩片點(diǎn)云進(jìn)行配準(zhǔn),獲取較好的位置姿態(tài),為精配準(zhǔn)提供良好配準(zhǔn)環(huán)境。而精配準(zhǔn)是在粗配準(zhǔn)基礎(chǔ)上進(jìn)行二次配準(zhǔn),使點(diǎn)云在配準(zhǔn)后誤差達(dá)到最小。

3.1 粗配準(zhǔn)

在粗配準(zhǔn)中結(jié)合形態(tài)描述ISS法和BSHOT直方圖特征完成粗配準(zhǔn)。兩者的結(jié)合一方面可以降低點(diǎn)云配準(zhǔn)時(shí)所需的數(shù)量,另一方面可減少后續(xù)配準(zhǔn)點(diǎn)相似性計(jì)算的復(fù)雜度。

在計(jì)算配準(zhǔn)特征的相似性時(shí),常用歐式距離來(lái)衡量。但本研究采用漢明距離計(jì)算相似性確定匹配點(diǎn)對(duì)。通過(guò)對(duì)二進(jìn)制數(shù)值進(jìn)行簡(jiǎn)單的異或運(yùn)算,統(tǒng)計(jì)結(jié)果為1的個(gè)數(shù),總數(shù)即為漢明距離。當(dāng)漢明距離最小時(shí),可認(rèn)為對(duì)應(yīng)的兩個(gè)特征點(diǎn)為同一匹配對(duì)。漢明距離的計(jì)算如式(4):

(4)

式中,d為漢明距離；x和y表示兩片點(diǎn)云中對(duì)應(yīng)的BSHOT直方圖特征描述符；⊕表示異或運(yùn)算,即相同則為0,不同則為1。

由于點(diǎn)云的稀疏性、噪聲等影響,僅采用漢明距離計(jì)算相似性匹配容易形成錯(cuò)誤匹配對(duì)。為避免此類情況,研究中也引入隨機(jī)采樣一致性(RANSAC)算法去除點(diǎn)云中錯(cuò)誤的匹配對(duì),從而估計(jì)初始變化矩陣。

3.2 精配準(zhǔn)

傳統(tǒng)的點(diǎn)對(duì)點(diǎn)ICP配準(zhǔn)算法中,可分為兩種情況:(1)未使用特征點(diǎn)時(shí),將全部的源點(diǎn)云數(shù)據(jù)與目標(biāo)點(diǎn)云數(shù)據(jù)進(jìn)行點(diǎn)與點(diǎn)的計(jì)算配準(zhǔn),但該方法由于是全部點(diǎn)云參與計(jì)算,其配準(zhǔn)精度較高,但耗時(shí)較長(zhǎng)。(2)引入特征點(diǎn)時(shí),采用兩片點(diǎn)云的特征點(diǎn)作為參與值,其配準(zhǔn)速度較快,但精度不如使用全部點(diǎn)云配準(zhǔn)效果好,易受特征點(diǎn)影響。

因此在ICP精配準(zhǔn)中本研究將上述兩種方法結(jié)合形成一種新的改進(jìn)的ICP算法,即在精配準(zhǔn)過(guò)程中,源點(diǎn)云使用特征點(diǎn),而目標(biāo)點(diǎn)云使用全部點(diǎn)數(shù)據(jù),作為ICP配準(zhǔn)的輸入值。該方法既采用了特征點(diǎn)的代表性又結(jié)合了全部點(diǎn)的整體性,一方面可保留一定的配準(zhǔn)精度,另一方面也可減少參與配準(zhǔn)的點(diǎn)云數(shù)量,使配準(zhǔn)時(shí)間縮小。

3.3 配準(zhǔn)過(guò)程

點(diǎn)云配準(zhǔn)流程圖如圖1所示。

圖1 點(diǎn)云配準(zhǔn)算法流程

研究中的點(diǎn)云配準(zhǔn)其主要過(guò)程為:①使用體素格網(wǎng)對(duì)初始點(diǎn)云下采樣,減少點(diǎn)云數(shù)量。②使用形態(tài)描述ISS提取方法提取特征點(diǎn)。③使用SHOT特征描述符對(duì)特征點(diǎn)進(jìn)行描述。④使用二進(jìn)制轉(zhuǎn)換規(guī)則將SHOT特征描述符轉(zhuǎn)化為BSHOT直方圖特征描述符。⑤使用漢明距離尋找對(duì)應(yīng)的特征點(diǎn)點(diǎn)對(duì)。⑥使用RANSAC剔除錯(cuò)誤特征點(diǎn)點(diǎn)對(duì),獲取初始變化矩陣。⑦使用改進(jìn)的ICP算法進(jìn)行迭代配準(zhǔn),獲取最終精確變化矩陣,完成點(diǎn)云配準(zhǔn)。

改進(jìn)的配準(zhǔn)算法在粗配準(zhǔn)時(shí)采用BSHOT直方圖特征描述符和漢明距離相似性度量方法,相比于傳統(tǒng)的SAC-IA算法可減少配準(zhǔn)時(shí)間。因此基于配準(zhǔn)時(shí)間較短的基礎(chǔ)上,采用改進(jìn)的配準(zhǔn)方法可提高點(diǎn)云最終配準(zhǔn)的精度,形成一個(gè)較高效率性與精確性共存的點(diǎn)云配準(zhǔn)算法。

4 實(shí)驗(yàn)與分析

4.1 實(shí)驗(yàn)數(shù)據(jù)

實(shí)驗(yàn)數(shù)據(jù)采用斯坦福大學(xué)掃描的Bunny數(shù)據(jù)、Armadillo數(shù)據(jù)和Dragon數(shù)據(jù),三組點(diǎn)云數(shù)據(jù)如圖2。實(shí)驗(yàn)平臺(tái)為Intel(R)Core(TM)i7-10700 CPU@2.90GHz處理器,16G運(yùn)行內(nèi)存,操作系統(tǒng)為Windows10 64位操作系統(tǒng),編譯環(huán)境為Visual Studio 2017 C++,并結(jié)合第三方工具開源點(diǎn)云庫(kù)PCL1.9.。

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

4.2 實(shí)驗(yàn)結(jié)果與分析

由于三組點(diǎn)云的數(shù)據(jù)量較大,bunny數(shù)據(jù)共35,947個(gè)點(diǎn),armadillo數(shù)據(jù)共172,974個(gè)點(diǎn),dragon數(shù)據(jù)更是高達(dá)437,645個(gè)點(diǎn)。而大量點(diǎn)云會(huì)降低配準(zhǔn)效率,因此實(shí)驗(yàn)過(guò)程中先進(jìn)行體素格網(wǎng)下采樣,再提取關(guān)鍵點(diǎn)來(lái)降低點(diǎn)云數(shù)量,提高點(diǎn)云配準(zhǔn)效率。

為驗(yàn)證算法的高效率性與精確性,將所提出算法與文獻(xiàn)[10]的SIFT+BSHOT算法、文獻(xiàn)[8]的ISS+FPFH+SAC-IA算法、以及ISS+SHOT+SAC-IA算法進(jìn)行對(duì)比。為更好對(duì)比實(shí)驗(yàn),控制體素格網(wǎng)下采樣和關(guān)鍵點(diǎn)提取的點(diǎn)云個(gè)數(shù)保持一致。對(duì)三組點(diǎn)云,四種算法進(jìn)行點(diǎn)云的粗配準(zhǔn)結(jié)果如圖3所示。

圖3 四種算法的粗準(zhǔn)結(jié)果圖

本文算法在精配準(zhǔn)中使用改進(jìn)的ICP精配準(zhǔn)方法,其余三種對(duì)比算法采用傳統(tǒng)的點(diǎn)對(duì)點(diǎn)ICP配準(zhǔn)方法。為確保實(shí)驗(yàn)算法的可比性,精配準(zhǔn)中相關(guān)參數(shù)設(shè)置一致。對(duì)三種不同數(shù)量點(diǎn)云,利用四種算法進(jìn)行精配準(zhǔn)。為便于體現(xiàn)最終效果的差異,我們僅截取局部區(qū)域(Bunny的嘴部；Armadillo的右臂；Dragon的頭部)進(jìn)行顯示,其結(jié)果如圖4。

圖4 四種算法的精配準(zhǔn)局部結(jié)果圖

為驗(yàn)證配準(zhǔn)精度,通過(guò)計(jì)算配準(zhǔn)后兩點(diǎn)云間的均方根誤差RMSE對(duì)比不同算法的精度,RMSE的計(jì)算如式(5):

(5)

式中,N表示點(diǎn)云總數(shù)；T表示最終變化矩陣；pi和pj分別表示源點(diǎn)云與目標(biāo)點(diǎn)云。

不同算法對(duì)點(diǎn)云的配準(zhǔn)效果不同,本研究在配準(zhǔn)精度和時(shí)間兩個(gè)方面進(jìn)行量化對(duì)比評(píng)估,表1、表2、表3分別代表三組不同數(shù)量點(diǎn)云的配準(zhǔn)結(jié)果統(tǒng)計(jì)表。

表1 Bunny點(diǎn)云數(shù)據(jù)的不同算法配準(zhǔn)效果評(píng)估表

表2 Armadillo點(diǎn)云數(shù)據(jù)的不同算法配準(zhǔn)效果評(píng)估表

表3 Dragon點(diǎn)云數(shù)據(jù)的不同算法配準(zhǔn)效果評(píng)估表

將不同算法配準(zhǔn)效果評(píng)估表中的精配準(zhǔn)均方根誤差和配準(zhǔn)時(shí)間用直方圖表示,可明顯對(duì)比其精確性和高效性,如圖5所示。

圖5 四種算法配準(zhǔn)效果對(duì)比圖

從配準(zhǔn)結(jié)果圖、效果評(píng)估表和效果對(duì)比圖分析可知:

(1)在特征點(diǎn)提取方面。本文算法采用ISS特征點(diǎn)提取方法,相較于SIFT+BSHOT算法中的SIFT提取方法具有較大的優(yōu)勢(shì)。從表1～表3中兩種特征點(diǎn)提取的時(shí)間可得出同樣結(jié)論,在提取相同個(gè)數(shù)的特征點(diǎn)時(shí),ISS特征點(diǎn)由于其計(jì)算的簡(jiǎn)潔性,使得所耗費(fèi)時(shí)間遠(yuǎn)小于SIFT特征點(diǎn)。

(2)在配準(zhǔn)精度方面。本文算法基于BSHOT特征描述符采用漢明距離、RANSAC算法進(jìn)行粗配準(zhǔn),從表1～表3可知其粗配準(zhǔn)精度不如對(duì)比算法中SAC-IA方法的精度。原因?yàn)镾HOT特征描述符轉(zhuǎn)為二進(jìn)制BSHOT直方圖特征描述符時(shí),存在一定程度的信息缺失。另外從圖5(a)中可知,本文所提出的點(diǎn)云配準(zhǔn)方法提高了點(diǎn)云的最終配準(zhǔn)精度。尤其對(duì)于點(diǎn)數(shù)較多的點(diǎn)云集,其精度提高效果會(huì)更好。從表1～表3中的精配準(zhǔn)均方根誤差可知,對(duì)于三種不同數(shù)量的點(diǎn)云:Bunny、Armadillo、Dragon數(shù)據(jù),本文所提出的方法相較于對(duì)比算法中精度最高的算法(ISS+SHOT+SAC-IA算法)的RMSE分別提高了0.08 mm,0.11 mm,0.53 mm。對(duì)于Dragon數(shù)據(jù),其精度提高了約80.3 %。

(3)在配準(zhǔn)時(shí)間方面,從圖5(b)中可知,無(wú)論是點(diǎn)云數(shù)量較少的Bunny數(shù)據(jù),還是Armadillo數(shù)據(jù),或是數(shù)量較多的Dragon數(shù)據(jù),本文算法的總配準(zhǔn)時(shí)間均少于其余三種配準(zhǔn)算法的配準(zhǔn)時(shí)間。但隨著點(diǎn)云數(shù)量的增加,其配準(zhǔn)效率優(yōu)勢(shì)也會(huì)減弱。從表1和表3可知本文算法與對(duì)比算法中耗時(shí)最少的算法(ISS+FPFH+SAC-IA算法)的時(shí)間相比,Bunny數(shù)據(jù)配準(zhǔn)時(shí)間減少了4.204 s,但對(duì)于Dragon數(shù)據(jù)本文算法在時(shí)間方面僅減少了0.899 s。

對(duì)比分析可知,本文算法在配準(zhǔn)耗時(shí)上,比其余三種算法效率更高、時(shí)間更短。且算法中將形態(tài)描述ISS與BSHOT直方圖特征以及改進(jìn)后的ICP算法結(jié)合,其最終的配準(zhǔn)精度也均高于其余算法精度。這證明了本研究所提出的配準(zhǔn)算法同時(shí)具備較高的效率性與精確性。

5 結(jié) 語(yǔ)

針對(duì)點(diǎn)云配準(zhǔn)過(guò)程中配準(zhǔn)效率和精度無(wú)法兼得的問(wèn)題,本研究提出一種新的點(diǎn)云配準(zhǔn)算法。該算法基于內(nèi)部形態(tài)描述ISS特征提取和BSHOT直方圖特征配準(zhǔn)的快速性,再結(jié)合改進(jìn)的ICP算法進(jìn)行精確配準(zhǔn)。通過(guò)對(duì)不同數(shù)量點(diǎn)云數(shù)據(jù)(Bunny數(shù)據(jù)、Armadillo數(shù)據(jù)和Dragon數(shù)據(jù))進(jìn)行實(shí)驗(yàn)對(duì)比,結(jié)果表明所提出算法在配準(zhǔn)精度和時(shí)間方面均高于SIFT+BSHOT算法、ISS+FPFH+SAC-IA算法、以及ISS+SHOT+SAC-IA算法。說(shuō)明本研究提出的算法在點(diǎn)云配準(zhǔn)方面具有較高的精確性與效率性,且當(dāng)點(diǎn)云數(shù)量較多時(shí),其配準(zhǔn)精度的提高效果會(huì)有所增強(qiáng),但配準(zhǔn)效率的優(yōu)勢(shì)會(huì)減弱。