基于法向量和密度的點(diǎn)云特征點(diǎn)提取問(wèn)題研究

馬聰聰 李 松 曹菁菁 于 蒙

(武漢理工大學(xué)物流工程學(xué)院 湖北 武漢 430063)

0 引 言

隨著三維掃描技術(shù)的飛速發(fā)展，三維點(diǎn)云數(shù)據(jù)的獲取方式更加豐富且越來(lái)越便捷，精度越來(lái)越高。激光掃描是現(xiàn)階段點(diǎn)云數(shù)據(jù)采集的主流方式，其速度快，獲得的點(diǎn)云數(shù)據(jù)量相當(dāng)龐大。點(diǎn)云數(shù)據(jù)的存儲(chǔ)以及顯示需要大量?jī)?nèi)存，同時(shí)需要較長(zhǎng)的運(yùn)算時(shí)間，這對(duì)后期模型重建的精度以及運(yùn)算復(fù)雜度有重要影響。因此，在保證模型準(zhǔn)確性的前提下提取特征點(diǎn)去除冗余點(diǎn)云數(shù)據(jù)，提高逆向工程各環(huán)節(jié)的運(yùn)算效率是十分必要的。

針對(duì)點(diǎn)云特征點(diǎn)的提取，國(guó)內(nèi)外研究人員做了大量研究。Woo等[1]基于八叉樹(shù)進(jìn)行三維網(wǎng)格劃分，通過(guò)曲率與法向量對(duì)特征點(diǎn)進(jìn)行提取，在考慮幾何形狀的同時(shí)對(duì)邊緣點(diǎn)進(jìn)行提取。Zhong等[2-3]提出內(nèi)在形狀特征(IntrinsicShapeSignature,ISS)算法，該算法具有較好的穩(wěn)定性并取得了較好的特征點(diǎn)提取效果。Wang等[4]將三維點(diǎn)云數(shù)據(jù)與二維光學(xué)圖像的優(yōu)點(diǎn)相結(jié)合，提出一種基于結(jié)構(gòu)信息的特征點(diǎn)提取方法，該方法能夠準(zhǔn)確、連續(xù)地提取點(diǎn)云特征。陶海躋等[5]對(duì)目標(biāo)點(diǎn)及其K鄰域內(nèi)各點(diǎn)云數(shù)據(jù)對(duì)應(yīng)的法向量夾角的算術(shù)平均值進(jìn)行計(jì)算，并以此作為特征點(diǎn)的判別標(biāo)準(zhǔn)實(shí)現(xiàn)了對(duì)特征點(diǎn)的快速提取。陳龍等[6]通過(guò)采用多個(gè)判別參數(shù)并對(duì)其賦予不同的權(quán)重對(duì)特征點(diǎn)進(jìn)行提取，該方法能夠較好地對(duì)尖銳特征點(diǎn)進(jìn)行檢測(cè)提取，但是對(duì)于薄壁物體的特征點(diǎn)提取會(huì)出現(xiàn)誤判的情況。張雨禾等[7]提出一種基于密度空間聚類的特征點(diǎn)提取算法，該算法具有較好的魯棒性，但是需要對(duì)反K近鄰進(jìn)行計(jì)算，影響了算法的運(yùn)行效率。陸帆等[8]提出反距離權(quán)重與密度相結(jié)合的算法，以邊界點(diǎn)作為特征點(diǎn)進(jìn)行提取，該方法運(yùn)算速度較快但對(duì)特征變化不明顯的點(diǎn)云進(jìn)行特征點(diǎn)提取時(shí)效果稍差。

采用單一判別因素進(jìn)行特征點(diǎn)提取容易導(dǎo)致特征點(diǎn)的漏判與錯(cuò)判，尤其對(duì)于特征變化不明顯的點(diǎn)云，上述算法難以取得較好的特征點(diǎn)提取效果。針對(duì)該問(wèn)題，本文提出一種基于點(diǎn)云法向量與點(diǎn)云密度相結(jié)合的特征點(diǎn)提取算法，有效改善點(diǎn)云特征點(diǎn)錯(cuò)判與漏判的情況，采用三組模型進(jìn)行實(shí)驗(yàn)，獲得了較好的特征點(diǎn)提取效果。

1 算法概述

設(shè)一點(diǎn)云數(shù)據(jù)集為X={xi|xi∈R3,i=1,2,…,n}，首先對(duì)無(wú)序散亂點(diǎn)云通過(guò)建立KD樹(shù)(K Dimension Tree)得到目標(biāo)點(diǎn)的K鄰域以提高點(diǎn)云數(shù)據(jù)的搜索速度。其次，通過(guò)主成分分析法(Principal Component Analysis,PCA)對(duì)點(diǎn)云法向量進(jìn)行計(jì)算。然后，計(jì)算點(diǎn)云密度，并將其與點(diǎn)云法向量對(duì)應(yīng)的特征度相結(jié)合組成特征點(diǎn)判別參數(shù)。最后，完成特征點(diǎn)的提取。算法流程如圖1所示。

圖1 特征點(diǎn)提取流程圖

其具體步驟如下：

1) 構(gòu)建點(diǎn)云拓?fù)浣Y(jié)構(gòu)。點(diǎn)云數(shù)據(jù)龐大且不具規(guī)律性，需要對(duì)其建立適當(dāng)?shù)耐負(fù)潢P(guān)系，通過(guò)建立KD樹(shù)以獲得各個(gè)數(shù)據(jù)點(diǎn)的K鄰域。

2) 采用PCA算法計(jì)算點(diǎn)云X中各點(diǎn)的法向量，并求得數(shù)據(jù)點(diǎn)與其K鄰域中各個(gè)點(diǎn)的法向量之間的數(shù)量積。

3) 計(jì)算點(diǎn)云X的密度，并與法向量間數(shù)量積對(duì)應(yīng)的特征度組成特征點(diǎn)判別參數(shù)。

4) 設(shè)定閾值，對(duì)符合條件的點(diǎn)進(jìn)行保留，將不滿足閾值要求的點(diǎn)剔除。

5) 根據(jù)點(diǎn)的K鄰域內(nèi)各點(diǎn)的特征，進(jìn)一步對(duì)提取到的點(diǎn)進(jìn)行篩選，得到最終的特征點(diǎn)集。

2 算法描述

2.1 點(diǎn)云拓?fù)潢P(guān)系構(gòu)建

通過(guò)三維掃描儀獲得的點(diǎn)云數(shù)據(jù)相當(dāng)密集且數(shù)量龐大，同時(shí)點(diǎn)云數(shù)據(jù)在分布上呈現(xiàn)出雜亂、無(wú)規(guī)律的特性，在對(duì)其進(jìn)行遍歷時(shí)將嚴(yán)重影響算法的運(yùn)行效率。K鄰域是最常用的索引方式，其中心思想是選取與目標(biāo)點(diǎn)最近的K個(gè)點(diǎn)構(gòu)成一個(gè)集合，而K鄰域的構(gòu)造主要通過(guò)構(gòu)建KD樹(shù)的方式來(lái)實(shí)現(xiàn)。

KD樹(shù)的構(gòu)建是一個(gè)遞歸的過(guò)程，本文以x、y、z三個(gè)坐標(biāo)軸所在的方向依次作為分區(qū)面，以歐式距離為標(biāo)準(zhǔn)進(jìn)行點(diǎn)云數(shù)據(jù)的劃分。首先，以x軸作為劃分平面將點(diǎn)云數(shù)據(jù)x軸對(duì)應(yīng)的坐標(biāo)值按從小到大的順序進(jìn)行排序，取中值點(diǎn)作為根節(jié)點(diǎn)，將小于中值點(diǎn)的點(diǎn)云數(shù)據(jù)劃分到左子樹(shù)，則右子樹(shù)中對(duì)應(yīng)的點(diǎn)云數(shù)據(jù)的坐標(biāo)值大于中值點(diǎn)。然后，以y軸作為分割坐標(biāo)軸，同樣將之前分割的子樹(shù)中的點(diǎn)云數(shù)據(jù)按y值大小排序，以中位數(shù)作為切割點(diǎn)，最后，在z軸按同樣的方式進(jìn)行左右子樹(shù)的劃分。循環(huán)上述過(guò)程，直至按照某個(gè)節(jié)點(diǎn)劃分結(jié)束后不能再劃分出子節(jié)點(diǎn)為止。

KD樹(shù)的搜索作為KD樹(shù)算法不可或缺的環(huán)節(jié)，主要包含查詢與回溯兩個(gè)過(guò)程[9]。給定目標(biāo)點(diǎn)，首先與根節(jié)點(diǎn)進(jìn)行比較，若該點(diǎn)的坐標(biāo)值小于根節(jié)點(diǎn)的值則進(jìn)入左子樹(shù)進(jìn)行搜索，反之在右子樹(shù)中進(jìn)行搜索，循環(huán)該過(guò)程，直到搜索到最后一個(gè)葉節(jié)點(diǎn)為止。將該節(jié)點(diǎn)作為當(dāng)前的最近點(diǎn)并進(jìn)行回溯，與該節(jié)點(diǎn)相比，如果在點(diǎn)云數(shù)據(jù)中存在更符合要求的點(diǎn)，則將該點(diǎn)進(jìn)行替換；否則尋找該節(jié)點(diǎn)對(duì)應(yīng)的父節(jié)點(diǎn)，然后對(duì)父節(jié)點(diǎn)對(duì)應(yīng)的其他子樹(shù)進(jìn)行校驗(yàn)。當(dāng)搜索進(jìn)行到根節(jié)點(diǎn)時(shí)，回溯停止，循環(huán)上述過(guò)程，直至獲得K個(gè)最近鄰點(diǎn)。

2.2 點(diǎn)云法向量計(jì)算

法向量是點(diǎn)云數(shù)據(jù)的一個(gè)重要的幾何特征，可以在一定程度上反映曲面的變化情況，當(dāng)曲面變化劇烈時(shí)，點(diǎn)云法向量的波動(dòng)也會(huì)更加頻繁，反之當(dāng)曲面變化平緩時(shí)，點(diǎn)云的法向量變化也隨之減小。采用PCA算法[10]對(duì)點(diǎn)云法向量進(jìn)行計(jì)算，具體流程如下：

Step 1 建立K鄰域后，計(jì)算各鄰域中心點(diǎn)的坐標(biāo):

(1)

Step 2 構(gòu)造點(diǎn)云數(shù)據(jù)的協(xié)方差矩陣Σ：

(2)

Step 3 計(jì)算協(xié)方差矩陣Σ的特征值以及對(duì)應(yīng)的特征向量，點(diǎn)云的法向量為最小的特征值對(duì)應(yīng)的特征向量。

ni·nxi≥0

(3)

對(duì)所有點(diǎn)云數(shù)據(jù)對(duì)應(yīng)的法向量計(jì)算完成后，對(duì)點(diǎn)云數(shù)據(jù)的特征度ti進(jìn)行計(jì)算，特征度以某點(diǎn)的法向量與其K鄰域內(nèi)各點(diǎn)法向量的點(diǎn)積的平均數(shù)進(jìn)行表示。

(4)

式中：ti表示點(diǎn)xi的特征度。

2.3 點(diǎn)云密度計(jì)算

點(diǎn)云密度對(duì)特征點(diǎn)的提取有重要影響，對(duì)于幾何特征變化較大的點(diǎn)云模型，將點(diǎn)云密度作為特征點(diǎn)檢測(cè)參數(shù)，會(huì)根據(jù)點(diǎn)云數(shù)據(jù)分布獲得更多的特征點(diǎn)。而對(duì)于幾何特征變化較小的點(diǎn)云模型，若僅以幾何特征作為特征點(diǎn)提取的判別標(biāo)準(zhǔn)，提取到的特征點(diǎn)較少，難以表述點(diǎn)云模型的特征，引入點(diǎn)云密度將會(huì)提升特征點(diǎn)提取效果。

點(diǎn)云密度主要有兩種表現(xiàn)形式，即基于分塊的點(diǎn)云密度提取以及基于距離的點(diǎn)云密度計(jì)算?；诜謮K的點(diǎn)云密度提取方法將點(diǎn)云數(shù)據(jù)劃分成若干塊，統(tǒng)計(jì)各塊內(nèi)點(diǎn)的數(shù)量并以此對(duì)點(diǎn)云密度進(jìn)行表示?；诰嚯x的點(diǎn)云密度計(jì)算則以點(diǎn)云數(shù)據(jù)間的距離為依據(jù)，本文以此作為點(diǎn)云密度的表示方法[7]：

(5)

式中：ρi為點(diǎn)的密度；dij表示K鄰域內(nèi)點(diǎn)xj與xi之間的距離?？梢钥闯?，當(dāng)點(diǎn)間距離較大，即點(diǎn)云分布較稀疏時(shí)，ρi的值較??；而當(dāng)點(diǎn)間距離較小時(shí)，點(diǎn)的分布相對(duì)密集，ρi的值隨之增大。

2.4 特征點(diǎn)提取

以點(diǎn)云法向量作為特征點(diǎn)提取的依據(jù)，當(dāng)點(diǎn)云數(shù)據(jù)間距離較大時(shí)，法向量的變化可能隨之變大，從而容易出現(xiàn)非特征點(diǎn)誤判的情況；而當(dāng)點(diǎn)云數(shù)據(jù)間距離較小時(shí)，法向量的變化程度也隨之減小，可能導(dǎo)致特征點(diǎn)漏判。針對(duì)上述問(wèn)題，本文將點(diǎn)云法向量對(duì)應(yīng)的特征度與點(diǎn)云密度相結(jié)合組成特征點(diǎn)判別參數(shù)，計(jì)算如下：

(6)

式中：Hi表示特征點(diǎn)判別參數(shù)；ρi對(duì)應(yīng)xi的點(diǎn)云密度；ρmin表示所有點(diǎn)云數(shù)據(jù)對(duì)應(yīng)的點(diǎn)云密度中的最小值；ρmax則為點(diǎn)云密度中的最大值。

當(dāng)完成所有點(diǎn)云數(shù)據(jù)的特征點(diǎn)判別參數(shù)計(jì)算后，與閾值進(jìn)行比較。將特征點(diǎn)判別參數(shù)小于閾值的點(diǎn)作為特征點(diǎn)，特征點(diǎn)參數(shù)大于閾值的點(diǎn)則為非特征點(diǎn)。當(dāng)點(diǎn)云密度較大時(shí)，特征點(diǎn)判別參數(shù)會(huì)隨之增大，從而使得更多的點(diǎn)大于閾值，因此特征點(diǎn)的概率隨之下降，減少了冗余點(diǎn)的存在。當(dāng)點(diǎn)云幾何特征變化強(qiáng)烈時(shí)，特征度的值也會(huì)隨之變大，該點(diǎn)作為特征點(diǎn)的可能性也隨之提高，將其與點(diǎn)云密度相結(jié)合，使得點(diǎn)間距離與幾何特征取得了更好的平衡，提升了特征點(diǎn)的判斷準(zhǔn)確性，使得特征點(diǎn)提取效果更好。

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

為驗(yàn)證本文算法的有效性，選擇三組點(diǎn)云模型進(jìn)行實(shí)驗(yàn)驗(yàn)證。實(shí)驗(yàn)環(huán)境為Win10 64位系統(tǒng)，i5-8300H CPU，8 GB內(nèi)存的計(jì)算機(jī)，通過(guò)MATLAB 2017b實(shí)現(xiàn)。為體現(xiàn)本文算法的優(yōu)越性，與ISS算法、文獻(xiàn)[5]的算法以及文獻(xiàn)[11]的算法進(jìn)行對(duì)比實(shí)驗(yàn)。ISS算法在剛性變換中對(duì)特征點(diǎn)進(jìn)行提取時(shí)具有較好的穩(wěn)定性和效果，應(yīng)用較為廣泛。點(diǎn)云幾何特性主要包括法向量與曲率，文獻(xiàn)[5]的算法以點(diǎn)云幾何特性中的法向量作為特征點(diǎn)判斷標(biāo)準(zhǔn)，而文獻(xiàn)[11]以曲率特性為依據(jù)對(duì)特征點(diǎn)進(jìn)行提取。因此，選擇上述三種算法與本文算法進(jìn)行對(duì)比驗(yàn)證更具代表性與說(shuō)服力。

(1) Bunny點(diǎn)云模型特征點(diǎn)提取效果。Bunny點(diǎn)云模型數(shù)據(jù)來(lái)源于斯坦福大學(xué)，該模型含有的點(diǎn)云數(shù)據(jù)量為40 097，各算法運(yùn)行所需的時(shí)間以及提取到的特征點(diǎn)數(shù)量如表1所示。本文算法所需的時(shí)間相對(duì)較少，提取到的數(shù)據(jù)量適中。

表1 Bunny模型特征點(diǎn)提取算法結(jié)果

三種算法得到的特征點(diǎn)提取效果如圖2所示。圖2(a)為Bunny模型的原始圖像，該模型的輪廓特征清晰，點(diǎn)云模型的邊界變化明顯，在耳朵、背部以及腿部等區(qū)域，點(diǎn)云模型的幾何特征變化強(qiáng)烈，法向量變化較大，點(diǎn)云密度也相對(duì)較大。圖2(b)為經(jīng)ISS算法運(yùn)行后得到的特征點(diǎn)提取結(jié)果，可以看出ISS算法提取到的特征點(diǎn)基本能夠反映模型的幾何形狀與變化特點(diǎn)，但是在耳朵以及尾巴部分得到的特征點(diǎn)有所欠缺。采用文獻(xiàn)[5]的算法得到的特征點(diǎn)提取效果如圖2(c)所示，該算法提取到了較多的特征點(diǎn)，但是包含了一些雜亂的冗余點(diǎn)，而輪廓作為該模型變化最豐富的區(qū)域，采用該算法獲得的輪廓效果稍差。采用文獻(xiàn)[11]的算法得到的特征點(diǎn)數(shù)量較少，其提取效果如圖2(d)所示，該算法在幾何特性變換明顯處得到的特征點(diǎn)效果不明顯，包含了一些非關(guān)鍵點(diǎn)，其運(yùn)行效率相對(duì)來(lái)說(shuō)也并不是最優(yōu)。采用本文算法得到的效果如圖2(e)所示，可以看出本文算法相對(duì)于ISS算法提取到了更多的特征點(diǎn)，尤其是在幾何特征變化明顯的區(qū)域獲得了更多的特征點(diǎn)，而與文獻(xiàn)[5]以及文獻(xiàn)[11]的算法進(jìn)行對(duì)比，可以看到本文算法提取到的特征點(diǎn)更能反映Bunny模型的輪廓特征，特征點(diǎn)提取效果更優(yōu)。

(a) Bunny模型 (b) ISS算法

(c) 文獻(xiàn)[5]算法 (d) 文獻(xiàn)[11]算法

(e) 本文算法圖2 Bunny點(diǎn)云模型不同算法特征點(diǎn)提取效果

(2) Dragon點(diǎn)云模型特征點(diǎn)提取效果。Dragon點(diǎn)云模型經(jīng)三種算法進(jìn)行特征點(diǎn)提取得到的結(jié)果如表2和圖3所示。Dragon模型的原始圖像如圖3(a)所示，Dragon模型的點(diǎn)云數(shù)據(jù)量為25 141，該模型幾何形狀更加復(fù)雜，細(xì)節(jié)更加豐富，因此，需要提取到更多的特征點(diǎn)才能盡可能表示模型的變化特點(diǎn)。圖3(b)為ISS算法提取到的特征點(diǎn)，可以看出，該算法提取到的特征點(diǎn)能夠較好地反映點(diǎn)云模型的變化特點(diǎn)，模型邊界相對(duì)完整，在變化較大的頭部以及細(xì)節(jié)豐富的主干部分獲得了較好的數(shù)據(jù)點(diǎn)。文獻(xiàn)[5]的算法獲得的特征點(diǎn)如圖3(c)所示，該算法得到的特征點(diǎn)提取效果較差，出現(xiàn)了特征點(diǎn)漏判的情況，且邊界不夠完整，細(xì)節(jié)不夠清晰。圖3(d)為文獻(xiàn)[11]得到的提取效果，該算法得到的特征點(diǎn)數(shù)量大大減少，但不能較好地反映模型的幾何變化特征。采用本文算法得到的結(jié)果如圖3(e)所示，可以看到本文算法提取到的特征點(diǎn)數(shù)量大于ISS算法，在細(xì)節(jié)豐富的主體部分獲得的點(diǎn)云數(shù)據(jù)能夠更好地反映模型特點(diǎn)，本文算法的效果同樣優(yōu)于文獻(xiàn)[5]與文獻(xiàn)[11]的算法，且相對(duì)于ISS算法以及文獻(xiàn)[11]的算法，本文算法的運(yùn)行效率更好。

表2 Dragon模型特征點(diǎn)提取算法結(jié)果

(c) 文獻(xiàn)[5]算法 (d) 文獻(xiàn)[11]算法

(e) 本文算法圖3 Dragon點(diǎn)云模型不同算法特征點(diǎn)提取效果

(3) Panda點(diǎn)云模型特征點(diǎn)提取效果。Panda點(diǎn)云模型的數(shù)據(jù)量為155 868，該模型的特征點(diǎn)提取效果如表3和圖4所示。圖4(a)為Panda模型的原始圖像，可以看出，該點(diǎn)云模型數(shù)據(jù)量大，而且模型中存在破損的孔洞以及連接處缺失等情況，因此，該模型的形狀特征較為豐富。經(jīng)ISS算法得到的特征點(diǎn)提取效果如圖4(b)所示，該算法得到的特征點(diǎn)分布與原型分布大體一致，雖然在三種算法中提取到最多的特征點(diǎn)，但是在一些細(xì)節(jié)處的特征點(diǎn)提取不夠完整。圖4(c)為文獻(xiàn)[5]的算法得到的特征點(diǎn)提取結(jié)果，該算法相較ISS算法得到的點(diǎn)云數(shù)據(jù)較少，且提取到的特征點(diǎn)質(zhì)量不高，在輪廓特征方面表示不清晰，且細(xì)節(jié)特征也不夠突出。采用文獻(xiàn)[11]的算法得到的結(jié)果如圖4(d)所示，該算法極大地降低了特征點(diǎn)數(shù)量，其中包含了一些非特征點(diǎn)，從而導(dǎo)致提取效果不佳。本文算法得到的特征點(diǎn)提取結(jié)果如圖4(e)所示，可以清晰地看到本文算法在變化較大的邊界處提取到了更多的特征點(diǎn)，在點(diǎn)云分布均勻的部分，提取到了較少的點(diǎn)云數(shù)據(jù)，減少了冗余點(diǎn)的數(shù)量且能夠更好地反映Panda模型的輪廓特征，取得了較好的特征點(diǎn)提取效果，且算法運(yùn)行效率較穩(wěn)定。

表3 Panda模型特征點(diǎn)提取算法結(jié)果

(a) Panda模型 (b)ISS算法

(c) 文獻(xiàn)[5]算法(d) 文獻(xiàn)[11]算法

(e) 本文算法圖4 Panda點(diǎn)云模型不同算法特征點(diǎn)提取效果

4 結(jié) 語(yǔ)

本文針對(duì)現(xiàn)有特征點(diǎn)提取算法存在的錯(cuò)判以及漏判等問(wèn)題，提出了一種基于點(diǎn)云法向量與密度相結(jié)合的特征點(diǎn)提取算法。特征點(diǎn)判別參數(shù)由特征度與點(diǎn)云密度共同組成，兼顧了幾何特征變化與點(diǎn)云間距離以及密度對(duì)特征點(diǎn)提取的影響。采用三組不同的點(diǎn)云模型對(duì)本文算法進(jìn)行了實(shí)驗(yàn)驗(yàn)證，結(jié)果表明本文算法相對(duì)于傳統(tǒng)算法提取到的特征點(diǎn)能夠更加清晰地表征模型幾何形狀變化，在細(xì)節(jié)豐富的區(qū)域提取到的特征點(diǎn)更加合理有效。