馬聰聰 李 松 曹菁菁 于 蒙

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

0 引 言

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

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

采用單一判別因素進行特征點提取容易導致特征點的漏判與錯判，尤其對于特征變化不明顯的點云，上述算法難以取得較好的特征點提取效果。針對該問題，本文提出一種基于點云法向量與點云密度相結合的特征點提取算法，有效改善點云特征點錯判與漏判的情況，采用三組模型進行實驗，獲得了較好的特征點提取效果。

1 算法概述

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

圖1 特征點提取流程圖

其具體步驟如下：

1) 構建點云拓撲結構。點云數(shù)據(jù)龐大且不具規(guī)律性，需要對其建立適當?shù)耐負潢P系，通過建立KD樹以獲得各個數(shù)據(jù)點的K鄰域。

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

3) 計算點云X的密度，并與法向量間數(shù)量積對應的特征度組成特征點判別參數(shù)。

4) 設定閾值，對符合條件的點進行保留，將不滿足閾值要求的點剔除。

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

2 算法描述

2.1 點云拓撲關系構建

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

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

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

2.2 點云法向量計算

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

Step 1 建立K鄰域后，計算各鄰域中心點的坐標:

(1)

Step 2 構造點云數(shù)據(jù)的協(xié)方差矩陣Σ：

(2)

Step 3 計算協(xié)方差矩陣Σ的特征值以及對應的特征向量，點云的法向量為最小的特征值對應的特征向量。

ni·nxi≥0

(3)

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

(4)

式中：ti表示點xi的特征度。

2.3 點云密度計算

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

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

(5)

式中：ρi為點的密度；dij表示K鄰域內點xj與xi之間的距離?？梢钥闯?，當點間距離較大，即點云分布較稀疏時，ρi的值較??；而當點間距離較小時，點的分布相對密集，ρi的值隨之增大。

2.4 特征點提取

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

(6)

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

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

3 實驗驗證與分析

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

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

表1 Bunny模型特征點提取算法結果

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

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

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

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

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

表2 Dragon模型特征點提取算法結果

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

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

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

表3 Panda模型特征點提取算法結果

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

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

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

4 結 語

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