周建釗，顏雨吉，陳 晨，杜文超

(陸軍工程大學(xué) 野戰(zhàn)工程學(xué)院，江蘇 南京 210007)

0 引言

點(diǎn)云數(shù)據(jù)獲取、點(diǎn)云數(shù)據(jù)處理以及模型重構(gòu)是逆向工程中必不可少的三個(gè)重要環(huán)節(jié)[1]。其中，點(diǎn)云數(shù)據(jù)處理是逆向工程中的重要環(huán)節(jié)，其精度以及效率將直接影響著三維模型的最終效果。在點(diǎn)云數(shù)據(jù)處理環(huán)節(jié)中，點(diǎn)云數(shù)據(jù)的特征提取是其中的一項(xiàng)重要研究內(nèi)容[2]，為幾何分析、數(shù)據(jù)分割、曲線匹配和拼接、曲面重建等幾何處理提供依據(jù)，對后期精確的點(diǎn)云配準(zhǔn)、模型重建等研究起關(guān)鍵作用。

特征點(diǎn)是最基本的曲面幾何形狀的特征基元，對于幾何模型的外觀及其準(zhǔn)確表達(dá)具有重要作用[3]，點(diǎn)云數(shù)據(jù)的特征提取是指從點(diǎn)云模型中識別出幾何模型的輪廓、尖銳處、凸凹處和過渡光滑處等結(jié)構(gòu)特征及形狀特征的過程[4]。特征提取是點(diǎn)云數(shù)據(jù)處理底層的技術(shù)之一，為后續(xù)點(diǎn)云數(shù)據(jù)的存儲、圖像處理、模型分析、特征點(diǎn)匹配、曲面重建等提供支持。

目前，針對散亂點(diǎn)云特征提取的研究方向可以大致分兩類，一類是基于網(wǎng)格模型的思想，將點(diǎn)云數(shù)據(jù)網(wǎng)格化，再利用網(wǎng)格模型的特征提取方法；而另一類是直接對點(diǎn)云數(shù)據(jù)進(jìn)行特征提取，不需要建立網(wǎng)格信息。無論哪種方法提取點(diǎn)云數(shù)據(jù)特征點(diǎn)，都涉及點(diǎn)云幾何參數(shù)的計(jì)算，計(jì)算點(diǎn)云幾何參數(shù)就要選取采樣點(diǎn)局部鄰域，局部鄰域大小的選擇影響幾何參數(shù)計(jì)算精度，同時(shí)現(xiàn)有的基于單一特征描述參數(shù)的特征提取方法的準(zhǔn)確性有待提高，因此研究了一種鄰域自適應(yīng)的雙閾值點(diǎn)云特征提取方法，實(shí)驗(yàn)證明該方法提高了特征點(diǎn)提取的準(zhǔn)確性和穩(wěn)定性。

1 基于法向量和曲率的特征提取算法

1.1 法向量提取特征點(diǎn)

法向量是點(diǎn)云數(shù)據(jù)模型中很重要的幾何屬性，局部鄰域內(nèi)點(diǎn)的法向量夾角可以反映曲面的變化信息[5-6]。圖1是法向量反映不同曲面信息[7],區(qū)域曲面內(nèi)法向量變化平緩時(shí)，表征該區(qū)域比較平坦，法向量變化較大時(shí)，反映該區(qū)域起伏大，根據(jù)鄰域k內(nèi)法向量的變化，設(shè)定適當(dāng)?shù)拈撝悼勺R別出點(diǎn)云數(shù)據(jù)的特征點(diǎn)。

圖1 法向量反映曲面信息

求出每個(gè)點(diǎn)的法向量，再計(jì)算每個(gè)點(diǎn)與其鄰近點(diǎn)法向量的夾角，定義點(diǎn)云數(shù)據(jù)中某點(diǎn)pi的法向量變化程度fi如下：

(1)

式中k是指與點(diǎn)pi歐氏距離最近的k個(gè)點(diǎn)，θij是指點(diǎn)pi與鄰近點(diǎn)pj的法向量夾角，將某點(diǎn)法向量變化程度fi與設(shè)定的合適閾值比較，即可有效提取點(diǎn)云數(shù)據(jù)特征點(diǎn)?；诜ㄏ蛄康奶卣魈崛∮?jì)算簡單，但依賴于鄰域的選取，同時(shí)對噪聲較為敏感，對于孤立的特征點(diǎn)因?yàn)槿狈忺c(diǎn)信息所以無法提取，對于細(xì)節(jié)特征較多、較復(fù)雜的點(diǎn)云數(shù)據(jù)提取效果不佳。

1.2 曲率提取特征點(diǎn)

圖2 曲率變化反映特征信息

由微分幾何知識可知，曲面的主曲率能夠反映采樣點(diǎn)處的局部特征，表1列出了點(diǎn)云局部曲面類型與主曲率取值的對應(yīng)關(guān)系，有助于點(diǎn)云局部的初步判斷。

表1 主曲率取值與局部曲面類型

曲率提取特征點(diǎn)過程概括如下[8-9]：

(1)以所求點(diǎn)pi為坐標(biāo)原點(diǎn)，曲面在pi點(diǎn)處的法向量方向?yàn)閆軸方向，X、Y軸在pi點(diǎn)處的切平面上，X、Y、Z軸兩兩正交，建立(X，Y，Z)坐標(biāo)系。

(2)根據(jù)二次曲面基本方程:

(2)

代入鄰域點(diǎn)坐標(biāo)pj(j=1,2,3…)，依據(jù)最小二乘法，可求得曲面基本方程。

(3)由曲面基本方程，求方程的一階、二階偏導(dǎo)可獲得擬合所得曲面的第一基本量(E、F、G)和第二基本量(L、M、N)，結(jié)合曲面參數(shù)方程可計(jì)算出主曲率ρ1、ρ2、高斯曲率τ和平均曲率H：

(3)

(4)將上述計(jì)算所得的曲率值與設(shè)定的閾值進(jìn)行比較，保留曲率值大于閾值的點(diǎn)作為特征點(diǎn)。

基于曲率的特征提取方法識別點(diǎn)云特征信息比較準(zhǔn)確，對曲面突變區(qū)域和平緩區(qū)域的細(xì)節(jié)特征都可以準(zhǔn)確提取，可以有效地保留模型特征信息。但是使用曲率提取特征點(diǎn)的方法對噪聲點(diǎn)十分敏感，魯棒性較差，因此采用曲率提取點(diǎn)云模型特征的方法并不適用于含有噪聲點(diǎn)的點(diǎn)云數(shù)據(jù)，同時(shí)計(jì)算也比較復(fù)雜，算法的運(yùn)行效率不高。

2 自適應(yīng)鄰域選擇的雙閾值特征提取算法

基于不同特征描述參數(shù)的點(diǎn)云特征提取都存在一個(gè)共同的過程，就是對特征描述參數(shù)的計(jì)算，無論是利用法向量、曲率，還是基于其他參數(shù)的特征提取，都需要精確地計(jì)算這些參數(shù)才能保證提取出的特征點(diǎn)的準(zhǔn)確性。而計(jì)算上述參數(shù)的過程中，都涉及采樣點(diǎn)局部鄰域信息的計(jì)算，現(xiàn)有的采樣點(diǎn)局部鄰域構(gòu)建方法有兩類：近鄰點(diǎn)k搜索和半徑搜索，如圖3所示。近鄰點(diǎn)k搜索的原理是查找距離采樣點(diǎn)pi最近的k個(gè)點(diǎn)，以此構(gòu)建點(diǎn)云局部鄰域；半徑搜索是通過查找以采樣點(diǎn)pi為圓心，半徑為r的球內(nèi)所有的點(diǎn)。

圖3 兩種局部鄰域搜索方法原理圖

然而無論基于哪一種方法，都需要考慮鄰域點(diǎn)k的個(gè)數(shù)或者半徑r的大小，目前的處理方法更多地是根據(jù)實(shí)驗(yàn)的效果，人為主觀地進(jìn)行調(diào)整，直到尋找到一個(gè)合適的鄰域大小，將其應(yīng)用于整個(gè)點(diǎn)云數(shù)據(jù)的計(jì)算。這種方法的缺點(diǎn)有兩個(gè)方面，一是通過人為調(diào)整尋找最佳鄰域大小效率低下，存在主觀隨意性；二是通過此方法獲取的鄰域大小單一固定，當(dāng)點(diǎn)云模型較為復(fù)雜，局部特征信息較豐富時(shí)，單一的鄰域大小難以保證整體模型處理的效果，并影響后續(xù)過程的結(jié)果。因此尋找一種適應(yīng)不同情況可進(jìn)行調(diào)整的自適應(yīng)鄰域選取方法十分必要。

根據(jù)單一的特征描述參數(shù)對點(diǎn)云數(shù)據(jù)特征進(jìn)行提取，得到的特征點(diǎn)冗余數(shù)據(jù)多，存在非特征點(diǎn)誤識別的情況，在穩(wěn)定性、準(zhǔn)確性方面都有一定的局限性?；谝陨蟽蓚€(gè)方面的考慮，本文利用自適應(yīng)鄰域選擇結(jié)合法向量和曲率雙閾值判別，提出一種新的特征提取方法，并通過實(shí)驗(yàn)驗(yàn)證方法的可行性。

2.1 基于局部鄰域熵函數(shù)的自適應(yīng)鄰域選擇

由微分幾何知識可知，點(diǎn)云數(shù)據(jù)中任意一點(diǎn)pi的局部鄰域都可以通過一個(gè)微切平面進(jìn)行擬合，pi及其k鄰域局部擬合所得平面P可通過最小二乘原理進(jìn)行表達(dá)，公式如下：

(4)

(5)

點(diǎn)pi的局部鄰域協(xié)方差矩陣C是對稱的半正定矩陣，因此可以將式(5)矩陣表示為：

(6)

式中λ1、λ2、λ3為矩陣C的特征值，e1、e2、e3為對應(yīng)的特征向量。C是對稱的半正定矩陣，所以特征值都為非負(fù)數(shù)，令λ3≥λ2≥λ1，λ2、λ3分別代表平面相應(yīng)的特征向量方向偏離值，λ1代表法向方向的偏離值，根據(jù)文獻(xiàn)[10]的理論,特征值能夠反映局部鄰域維度特性：

(1)λ3?λ2≈λ1時(shí)，可判定局部鄰域?yàn)榫€型；

(2)λ3≈λ2?λ1時(shí)，可判定局部鄰域?yàn)槠矫妫?/p>

(3)λ3≈λ2≈λ1時(shí)，可以判斷局部鄰域?yàn)槿S曲面。

鄰域協(xié)方差矩陣C的特征值能反映鄰域維度信息的特性，構(gòu)建以下度量參數(shù)[11]：

(7)

式中Lλ、Pλ、Sλ分別代表局部鄰域一維線型、二維平面、三維曲面維度特性，描述了點(diǎn)云局部鄰域內(nèi)數(shù)據(jù)的空間分布情況。利用信息熵理論結(jié)合構(gòu)建的度量參數(shù)Lλ、Pλ、Sλ可以建立點(diǎn)云局部鄰域熵函數(shù)的表達(dá)式如下：

Ef=-Lλln(Lλ)-Pλln(Pλ)-Sλln(Sλ)

(8)

由表達(dá)式及特征值維度特性可知Ef的值越小，局部鄰域的某一種維度特征就比較突出，表示該鄰域下數(shù)據(jù)點(diǎn)之間的空間分布特性相近，也就說明該鄰域大小所對應(yīng)的鄰近點(diǎn)個(gè)數(shù)k或者鄰域半徑r的值趨于最優(yōu)。因此最佳鄰域尺寸的選取可以依賴于局部鄰域熵函數(shù)的最小準(zhǔn)則：

roptimum=argmin(Ef)

(9)

鑒于點(diǎn)云數(shù)據(jù)點(diǎn)的局部協(xié)方差矩陣的特征值能夠直接反映該點(diǎn)鄰域范圍內(nèi)鄰域點(diǎn)的分布特性，文獻(xiàn)[12]提出另一種表征鄰域維度信息的度量參數(shù)μi(μi=λi/∑λi)，為計(jì)算局部鄰域協(xié)方差矩陣C得到的特征值，其估計(jì)的最優(yōu)鄰域大小精度高于利用參數(shù)Lλ、Pλ、Sλ計(jì)算的最小熵函數(shù)所對應(yīng)的鄰域大小：

(10)

根據(jù)局部鄰域熵函數(shù)取值判定最優(yōu)鄰域選取，當(dāng)Eμ取極小值時(shí)對應(yīng)的局部鄰域大小即認(rèn)定為最優(yōu)鄰域。自適應(yīng)鄰域選擇算法流程如圖4所示。

圖4 自適應(yīng)鄰域選擇算法流程圖

2.2 基于法向量和曲率的雙閾值特征判斷

基于法向量和曲率的雙閾值特征判斷是利用點(diǎn)云局部鄰域內(nèi)點(diǎn)的法向量夾角和平均曲率特征權(quán)值的閾值，進(jìn)行特征信息的提取，由于受法向量和曲率兩個(gè)限制條件的約束，該方法在穩(wěn)定性和準(zhǔn)確性方面有明顯的改善。

點(diǎn)云法向量能反映曲面的信息，利用法向量夾角構(gòu)建特征判斷約束條件：設(shè)定采樣點(diǎn)pi與其k鄰域內(nèi)一點(diǎn)pj的法向量夾角用θij表示：

(11)

定義點(diǎn)云數(shù)據(jù)中某點(diǎn)pi的法向量夾角變化程度fi：

(12)

定義采樣點(diǎn)pi在其鄰域k內(nèi)的平均曲率局部特征權(quán)值wH[13]：

(13)

式中H為采樣點(diǎn)pi在其鄰域k內(nèi)的平均曲率。通過計(jì)算得到的法向量夾角變化程度fi和平均曲率局部特征權(quán)值wH來判定點(diǎn)云數(shù)據(jù)中的點(diǎn)是否屬于特征點(diǎn)：首先判斷法向量夾角fi的變化程度是否大于設(shè)定閾值，若fi大于設(shè)定閾值，則將點(diǎn)劃分到潛在特征點(diǎn)集中；若fi小于設(shè)定閾值，則為非特征點(diǎn)。然后再計(jì)算潛在特征點(diǎn)集中點(diǎn)的平均曲率局部特征權(quán)值wH，若wH大于設(shè)定的閾值，則該點(diǎn)為特征點(diǎn)，加入特征點(diǎn)集；若wH小于設(shè)定的閾值，該點(diǎn)為非特征點(diǎn)，并將點(diǎn)從潛在特征點(diǎn)集中去除。

2.3 算法步驟

綜上所述，自適應(yīng)鄰域選擇的雙閾值特征提取算法的步驟如下：

(1)假定鄰域搜索半徑大小為r，設(shè)定鄰域搜索半徑的極值rmin、rmax,初始化搜索半徑ri使得ri=rmin，同時(shí)規(guī)定每一次步進(jìn)計(jì)算的步長Δr；

(2)從ri=rmin開始計(jì)算對應(yīng)鄰域大小下局部鄰域協(xié)方差矩陣C的特征向量和特征值，通過計(jì)算所得特征值，計(jì)算對應(yīng)的局部鄰域信息熵函數(shù)值Eμ;

(3)設(shè)置ri+1=ri+Δr，若ri+1rmax;

(4)比較計(jì)算所得的每個(gè)鄰域ri所對應(yīng)的局部鄰域信息熵的大小，根據(jù)局部鄰域熵函數(shù)最小準(zhǔn)則，確定該鄰域尺寸為最優(yōu)鄰域大??；

(5)在步驟(4)確定的最優(yōu)鄰域大小內(nèi)計(jì)算：點(diǎn)云法向量和法向量夾角變化程度fi，平均曲率局部特征權(quán)值wH；

(6)比較fi與設(shè)定的閾值大小，若fi大于閾值，將采樣點(diǎn)加入到潛在特征點(diǎn)集latent-featurepoints，若fi小于閾值，將采樣點(diǎn)加入到非特征點(diǎn)集normalpoints；

(7)比較潛在特征點(diǎn)集latent-featurepoints中點(diǎn)的平均曲率局部特征權(quán)值wH，若wH大于閾值，將采樣點(diǎn)加入到特征點(diǎn)集featurepoints中，若wH小于閾值，將該點(diǎn)從latent-featurepoints中移除到非特征點(diǎn)集normalpoints。直到所有點(diǎn)搜索完畢，結(jié)束程序，點(diǎn)集featurepoints即為特征點(diǎn)。

算法的具體流程圖如圖5所示。

圖5 鄰域自適應(yīng)的雙閾值特征點(diǎn)提取算法流程圖

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

本文的實(shí)驗(yàn)基于Microsoft Visual Studio 2015平臺，使用C++作為開發(fā)語言，結(jié)合開源庫PCL(Point Cloud Library)[14]和編譯工具CMake3.11.1進(jìn)行實(shí)驗(yàn)驗(yàn)證，實(shí)驗(yàn)環(huán)境配置如表2所示。本文實(shí)驗(yàn)數(shù)據(jù)來自于現(xiàn)有設(shè)備(3D CaMega CPC-400光學(xué)三維掃描儀，如圖6所示)采集和網(wǎng)上點(diǎn)云數(shù)據(jù)庫。

表2 實(shí)驗(yàn)環(huán)境配置

圖6 實(shí)驗(yàn)數(shù)據(jù)采集環(huán)境

利用濾清器和減速器殼體點(diǎn)云對本文算法和基于曲率的特征提取結(jié)果進(jìn)行對比分析，實(shí)驗(yàn)效果如圖7和圖8所示。

圖7 濾清器點(diǎn)云特征提取效果

圖8 減速器殼體點(diǎn)云特征提取效果

圖7和圖8分別是濾清器和減速器殼體點(diǎn)云數(shù)據(jù)征提取實(shí)驗(yàn)效果，其中圖(a)是采集的原始點(diǎn)云數(shù)據(jù)點(diǎn)，圖(b)是基于曲率的特征提取效果，圖(c)是本文算法的特征提取效果。從兩組實(shí)驗(yàn)中可以看出，對于模型的邊界特征兩種方法都能較好地取得相應(yīng)的效果，而對于模型的細(xì)節(jié)方面，如減速器端蓋處螺栓的效果都未取得滿意的結(jié)果；第一組實(shí)驗(yàn)中，本文算法提取的特征點(diǎn)更為細(xì)致全面，基于曲率的方法提取結(jié)果在部分區(qū)域缺失明顯；第二組實(shí)驗(yàn)中，本文算法對螺栓孔的提取效果不太理想，曲率提取的方法對噪聲的抗性更差。由于利用雙閾值限制特征點(diǎn)的判別，本文算法提取的特征點(diǎn)穩(wěn)定性和準(zhǔn)確性比單一曲率方法更高，也更為精簡，并且能夠通過有限的點(diǎn)有效地表達(dá)曲面的特征信息，基于曲率的特征提取有很多冗余數(shù)據(jù)，兩者提取的詳細(xì)數(shù)據(jù)如表3所示。

表3 不同方法特征提取數(shù)據(jù)

4 結(jié)論

本文研究了散亂點(diǎn)云特征提取方法，對基于法向量、曲率等不同點(diǎn)云描述參數(shù)的特征提取算法進(jìn)行研究，針對特征提取過程中人為調(diào)參和比較機(jī)械式的最佳鄰域選擇以及單一的特征描述參數(shù)特征提取穩(wěn)定性、準(zhǔn)確性差等問題，基于法向量和曲率計(jì)算，研究了一種鄰域自適應(yīng)的雙閾值特征提取算法，實(shí)驗(yàn)證明本文的特征點(diǎn)提取算法在特征點(diǎn)識別的穩(wěn)定性、準(zhǔn)確性方面有較大改善。