周建釗，顏雨吉

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

逆向工程（Reverse Engineering，簡稱 RE）是根據(jù)現(xiàn)有的模型，利用數(shù)字化測試設(shè)備獲取實(shí)體數(shù)據(jù)，對數(shù)據(jù)進(jìn)行處理后進(jìn)而重構(gòu)出完整的三維模型，在此基礎(chǔ)上，進(jìn)行模型優(yōu)化、創(chuàng)新設(shè)計(jì)、二次開發(fā)[1]。逆向工程廣泛應(yīng)用于機(jī)械制造、文物修復(fù)和地理信息構(gòu)建等方面，如圖1所示。點(diǎn)云數(shù)據(jù)獲取、點(diǎn)云數(shù)據(jù)處理以及模型重構(gòu)是逆向工程中三個(gè)必要環(huán)節(jié)。點(diǎn)云數(shù)據(jù)處理是逆向工程中最重要的環(huán)節(jié)，其精度以及效率將直接影響著三維模型的最終效果。而特征提取是點(diǎn)云數(shù)據(jù)處理中的一項(xiàng)重要內(nèi)容，如何有效的提取點(diǎn)云數(shù)據(jù)的特征點(diǎn)，將對后續(xù)點(diǎn)云模型的分析、配準(zhǔn)、匹配以及曲面重建產(chǎn)生巨大的影響。

圖1 逆向工程應(yīng)用

特征點(diǎn)是最基本的曲面幾何形狀的特征基元，對于幾何模型的外觀及其準(zhǔn)確表達(dá)具有重要作用。點(diǎn)云數(shù)據(jù)的特征提取是指從點(diǎn)云模型中識別出幾何模型的輪廓、尖銳處、凸凹處和過渡光滑處等結(jié)構(gòu)特征及形狀特征的過程[3]。特征提取可分為基于三維網(wǎng)格模型的特征提取和基于散亂點(diǎn)云的特征提取，本文研究內(nèi)容主要基于后者。

通過三維激光掃描儀獲取的散亂點(diǎn)云數(shù)據(jù)通常不具備網(wǎng)格信息，且數(shù)據(jù)點(diǎn)分布不均勻、數(shù)據(jù)量龐大、存在冗余和噪聲、無法直觀反應(yīng)物體的真實(shí)信息，因此，尋找有效地提取點(diǎn)云數(shù)據(jù)的可靠特征信息的方法，對點(diǎn)云數(shù)據(jù)處理和幾何模型重建的精度及效率的提高具有重要意義。

為了能清晰地表達(dá)點(diǎn)云幾何信息，常用點(diǎn)云特征描述參數(shù)（法線和曲率、點(diǎn)特征直方圖、快速點(diǎn)特征直方圖、文理特征、視點(diǎn)特征直方圖等）對點(diǎn)云進(jìn)行描述?；诓煌狞c(diǎn)云幾何描述參數(shù)有不同的特征提取算法，下面從不同的特征描述參數(shù)分析特征提取的關(guān)鍵技術(shù)。

1 基于法向量的特征提取

法向量是點(diǎn)云數(shù)據(jù)模型中很重要的幾何屬性，點(diǎn)云數(shù)據(jù)配準(zhǔn)、分割、特征提取和曲面重建等處理，都依賴于法向量的準(zhǔn)確估算[4-5]。大多數(shù)情況下三維設(shè)備獲取的點(diǎn)云沒有法向，也不具有幾何拓?fù)浣Y(jié)構(gòu)，因此需要依靠點(diǎn)云空間位置信息從初始點(diǎn)云中進(jìn)行法向量的估算。如圖2所示，區(qū)域曲面內(nèi)法向量變化平緩時(shí)，表征該區(qū)域較平坦，法向量變化較大時(shí)，反映該區(qū)域起伏大，根據(jù)領(lǐng)域k內(nèi)法向量的變化，設(shè)定適當(dāng)?shù)拈撝悼勺R別出點(diǎn)云數(shù)據(jù)的特征點(diǎn)。

圖2 法向量反映曲面信息

點(diǎn)云法向量的計(jì)算可以分為以下兩種方法：

（1）三維設(shè)備獲取的點(diǎn)云數(shù)據(jù)是物體表面的樣本點(diǎn)，故可先對物體表面的幾何進(jìn)行估計(jì)，使用低階多項(xiàng)式對點(diǎn)云數(shù)據(jù)進(jìn)行局部擬合[6-7]，得到采樣點(diǎn)對應(yīng)的曲面，然后再用曲面模型計(jì)算其表面的法線，如圖3所示。此方法的缺點(diǎn)時(shí)在特征比較尖銳的地方，法線計(jì)算容易被平滑，可以用迭代權(quán)重的方法來修正，先用平面局部擬合，然后給局部點(diǎn)計(jì)算權(quán)重，以點(diǎn)離平面的距離確定權(quán)重，然后再用帶權(quán)重的點(diǎn)再次進(jìn)行局部平面擬合，反復(fù)迭代可獲得更精確的特征點(diǎn)。

圖3 擬合計(jì)算點(diǎn)云數(shù)據(jù)法向量

（2）直接從點(diǎn)云數(shù)據(jù)中計(jì)算曲面法線[4，8，9]，把估計(jì)某個(gè)點(diǎn)的表面法線問題簡化為從該點(diǎn)的k鄰域計(jì)算協(xié)方差矩陣的特征向量和特征值，并進(jìn)行分析，從而估計(jì)一點(diǎn)處的表面法線，此方法所計(jì)算出的法線精確度依賴于k鄰域的選取。

式中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ì)算簡單，但依賴于k鄰域的選取，同時(shí)對噪聲較為敏感，對于孤立的特征點(diǎn)因?yàn)槿狈忺c(diǎn)信息所以無法提取，對于細(xì)節(jié)特征較多、較復(fù)雜的點(diǎn)云數(shù)據(jù)提取效果也不佳。

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

2 基于曲率的特征提取

曲線的曲率（curvature）是針對曲線上某個(gè)點(diǎn)的切線方向角對弧長的轉(zhuǎn)動率，通過微分來定義，表明曲線偏離直線的程度。曲面的曲率可以經(jīng)曲線的曲率推導(dǎo)而來：設(shè)在歐幾里德空間中存在一個(gè)三維曲面，規(guī)定過某點(diǎn)的曲率為過該點(diǎn)的法向量和某一切向量所確定的平面與曲面的交集（是一條曲線）的曲率。由于過某點(diǎn)可以確定無數(shù)條曲線，即曲面上某點(diǎn)的曲率不唯一，所以定義曲面的主曲率、高斯曲率和平均曲率：

主曲率：過曲面上某個(gè)點(diǎn)上具有無窮個(gè)正交曲率，其中存在一條曲線使得該曲線的曲率為極大，這個(gè)曲率為極大值kmax，垂直于極大曲率面的曲率為極小值kmin，這兩個(gè)曲率定義為主曲率。

高斯曲率：兩個(gè)主曲率的乘積即為高斯曲率，又稱總曲率，反映某點(diǎn)上總的彎曲程度。

平均曲率：是空間上曲面上某一點(diǎn)任意兩個(gè)相互垂直的正交曲率的平均值。如果一組相互垂直的正交曲率可表示為ki，kj，則平均曲率則為：k=（ki+kj）/2，見圖5所示。

圖5 曲面某點(diǎn)法向量與主曲率[10]

點(diǎn)云數(shù)據(jù)中的任意一點(diǎn)都存在某曲面逼近該點(diǎn)其近鄰點(diǎn)云，因此可以通過該點(diǎn)及其鄰域點(diǎn)擬合獲得局部曲面，利用擬合所得曲面的曲率近似表征該點(diǎn)的曲率。常用最小二乘擬合可獲得某點(diǎn)近鄰區(qū)域的曲面參數(shù)方程，根據(jù)參數(shù)方程和曲面曲率性質(zhì)則可以計(jì)算出對應(yīng)的主曲率、高斯曲率和平均曲率，過程概括如下[11-12]：

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

（2）根據(jù)二次曲面基本方程：

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

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

將上述計(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)行效率不高。

3 基于PFH和F PFH特征提取

3.1 點(diǎn)特征直方圖（PFH）

法向量和曲率估計(jì)是某個(gè)點(diǎn)周圍的幾何特征基本表示法，計(jì)算快速容易，但是僅使用幾個(gè)參數(shù)值來近似表示一個(gè)點(diǎn)的k鄰域的幾何特征，所包含的信息有限，對點(diǎn)云全局的特征信息反映較少。點(diǎn)特征直方圖（Point Feature Histograms，PFH）三維特征描述子[13-14]，能夠較好的反映點(diǎn)云全局特征。PFH通過計(jì)算點(diǎn)云中某一個(gè)查詢點(diǎn)與該點(diǎn)k鄰域點(diǎn)之間的空間差異并將其參數(shù)化表達(dá)，合成一個(gè)高維直方圖，借此描述點(diǎn)及鄰域點(diǎn)的幾何屬性。

基于點(diǎn)云法線和構(gòu)建的局部坐標(biāo)系可以計(jì)算出點(diǎn)云數(shù)據(jù)中點(diǎn)的特征直方圖PFH，具體過程概括如下[15-16]：

（1）以點(diǎn)pi為圓心，r為領(lǐng)域半徑，確定鄰域計(jì)算范圍，再將鄰域范圍內(nèi)的所有點(diǎn)兩兩相連構(gòu)建點(diǎn)對，如圖6所示。

圖6 P F H計(jì)算原理

（2）基于鄰域內(nèi)的任意點(diǎn)對pk1，pk2，對應(yīng)的法線為 nk1，nk2構(gòu)建局部坐標(biāo)系（u，v，w），如圖 7 所示。

圖7 局部坐標(biāo)系

（3）利用點(diǎn)的法向量和構(gòu)建的局部坐標(biāo)系計(jì)算出點(diǎn)的四個(gè)參數(shù)值 α、β、γ、d：

d是點(diǎn)pk1，pk2的距離，實(shí)踐證明忽略d這一參數(shù)對點(diǎn)云PFH特征提取影響很小，且大大降低算法的時(shí)間復(fù)雜程度，因此忽略d的計(jì)算。其余三個(gè)參數(shù)分別將上述三個(gè)特征參數(shù)按值劃分為n個(gè)子區(qū)間進(jìn)行統(tǒng)計(jì)，進(jìn)而會有n3種組合情況，直方圖則產(chǎn)生n3個(gè)區(qū)間，分別統(tǒng)計(jì)落在這些區(qū)間的點(diǎn)云數(shù)目，最后合成點(diǎn)的特征直方圖。提取獲得的桌面上書本和杯子的點(diǎn)特征直方圖（Point Feature Histograms，PFH）情況。

3.2 快速點(diǎn)特征直方圖（FPFH）

PFH的計(jì)算依賴于每個(gè)點(diǎn)與周圍鄰域點(diǎn)的局部坐標(biāo)系（u，v，w）的建立、法向量的求解、法向量與坐標(biāo)軸之間的幾何特征值的計(jì)算，并由此計(jì)算特征值合成直方圖。如果點(diǎn)云P中有n個(gè)點(diǎn)，那么它的PFH的理論計(jì)算復(fù)雜度是O（n*k2），其中k是點(diǎn)云P中每個(gè)點(diǎn)pi計(jì)算特征向量時(shí)考慮的鄰域點(diǎn)數(shù)量。實(shí)際應(yīng)用中，計(jì)算密集點(diǎn)云的PFH，會導(dǎo)致計(jì)算過于復(fù)雜，時(shí)間效率不高。于是學(xué)者們又提出了快速點(diǎn)云特征直方圖（Fast Point Feature Histograms，F(xiàn)PFH）特征提取算法[17]。

FPFH特征提取算法過程如下[15-16]：

（1）計(jì)算點(diǎn)pi與其k鄰域內(nèi)的點(diǎn)所構(gòu)成的點(diǎn)對的PFH特征參數(shù)，稱其為簡化的點(diǎn)特征直方圖（Simple Point Feature Histograms，SPFH）

（2）對點(diǎn) pi鄰域內(nèi)的各點(diǎn)（pk1，pk2，pk3，pk4，pk5）分別計(jì)算其鄰域內(nèi)點(diǎn)的SPFH，如圖8所示。

（3）計(jì)算pi的FPFH特征，計(jì)算公式如式（11）。

式中ωj是pi到點(diǎn)鄰域內(nèi)任意點(diǎn)pj的距離，作為計(jì)算權(quán)重。

圖8 F P F H計(jì)算原理

由于減少了點(diǎn)pi的k鄰域內(nèi)的各點(diǎn)兩兩組成點(diǎn)對的運(yùn)算，僅計(jì)算pi與鄰域點(diǎn)的PFH，大大減少了運(yùn)算量，計(jì)算復(fù)雜度由原來的O（n*k2）降低至O（n*k），提高了算法時(shí)間效率。

4 其他特征提取方法

點(diǎn)云特征提取技術(shù)涉及逆向工程、地理空間信息、計(jì)算機(jī)視覺等學(xué)科領(lǐng)域，是一項(xiàng)應(yīng)用十分廣泛的數(shù)據(jù)處理技術(shù)，因而除了上述特征提取方法，不少專家學(xué)者提出了許多的基于不同理論，應(yīng)用于不同類型點(diǎn)云的提取算法，下面對其中的部分算法進(jìn)行簡單的分析總結(jié)：

（1）多特征判別參數(shù)提取點(diǎn)云特征[11]。通過對法向量、曲率、點(diǎn)到鄰域重心距離等多個(gè)幾何參數(shù)的計(jì)算比較，設(shè)定合適閾值，當(dāng)計(jì)算所得點(diǎn)云的多個(gè)參數(shù)都大于閾值時(shí)，判定為特征點(diǎn)。

（2）基于離散Morse理論提取點(diǎn)云特征[18]。先利用局部鄰域的協(xié)方差，計(jì)算出每個(gè)數(shù)據(jù)點(diǎn)的特征度量，標(biāo)定為潛在特征點(diǎn)。然后將潛在特征點(diǎn)與其鄰域點(diǎn)在主方向上所形成的夾角平均值作為局部特征檢測算子，利用該算子計(jì)算該點(diǎn)的離散梯度。最后，利用線性插值法計(jì)算離散梯度并構(gòu)建離散梯度向量域，離散梯度向量域中的梯度極值點(diǎn)判定為特征點(diǎn)。

（3）基于DBSCAN聚類提取點(diǎn)云特征[19]。該算法首先定義散亂點(diǎn)云上點(diǎn)的反k近鄰作為特征描述子，初步判定其是否具有局部突變性；其次，將點(diǎn)的反k近鄰尺度作為點(diǎn)的密度值，基于密度聚類分析的方法，將具有相似局部幾何特征的點(diǎn)聚為一類，然后根據(jù)局部曲率突變點(diǎn)是否同時(shí)為潛在曲面上的曲率突變點(diǎn)來對聚類邊界點(diǎn)進(jìn)行判定，若同時(shí)為局部及全局曲率突變點(diǎn)，則判定為特征點(diǎn)。

（4）凹凸特性提取點(diǎn)云特征[20]。曲面凹凸性質(zhì)在點(diǎn)云數(shù)據(jù)中可以直觀的表現(xiàn)出來，因此可以根據(jù)鄰域點(diǎn)的凹凸特性提取特征點(diǎn)。定義鄰域重心q，通過判斷查詢點(diǎn)到q的連線構(gòu)成的向量與查詢點(diǎn)的法向量的內(nèi)積的正負(fù)性判斷凹凸性質(zhì)（正為凸點(diǎn)，負(fù)為凹點(diǎn)），計(jì)算凸點(diǎn)到鄰域重心的距離d，設(shè)定d的閾值，大于閾值的為特征點(diǎn)。

5 結(jié)束語

本文通過對三維點(diǎn)云特征特征提取技術(shù)的學(xué)習(xí)研究，總結(jié)了基于法向量、曲率、PFH和FPFH等不同特征提取參數(shù)的點(diǎn)云特征提取方法，介紹了基于多判別參數(shù)及其他特征提取的方法，為現(xiàn)有的點(diǎn)云特征提取算法的精度和時(shí)間復(fù)雜度的提高和改進(jìn)理清思路，找到出發(fā)點(diǎn)。

點(diǎn)云特征提取技術(shù)在裝備制造、文物修復(fù)、地理信息識別、計(jì)算機(jī)視覺等諸多學(xué)科領(lǐng)域都有廣泛的應(yīng)用，因而精確高效的點(diǎn)云特征識別與提取算法對裝備逆向制造精度、地理信息準(zhǔn)確反映以及視覺識別技術(shù)的提高起重要的作用，本文通過較為深入的總結(jié)分析，為后續(xù)的探索研究提供重要參考。