陸建華，劉 闖， 呂志才

(蘇州市測繪院有限責任公司，江蘇 蘇州 215000)

三維激光掃描儀采用非接觸測量方式，能夠迅速獲取大量三維坐標等信息，產(chǎn)生少則幾十萬，多則上億的密集點云，給后續(xù)數(shù)據(jù)計算和存儲帶來巨大挑戰(zhàn)，因此，有必要探索一種使用最少點云描述目標物表面完整信息的方法，即實現(xiàn)點云簡化的目的。

目前，點云簡化算法主要分為均勻簡化和非均勻簡化兩大類。以格網(wǎng)簡化算法為代表的均勻格網(wǎng)簡化算法易出現(xiàn)大量的點云空洞。為提高簡化質(zhì)量，學者們越來越注重非均勻簡化算法，較為代表性的算法有聚類、信息熵簡化算法和迭代簡化等。Song等提出了先對點云進行歸類，然后對歸類后的數(shù)據(jù)進行全局聚類簡化方法[1]；Shi等依據(jù)最大法向量偏離值對點云進行K均值分類，并結(jié)合邊界識別算法和區(qū)域特征優(yōu)化算法，提出了一種自適應遞歸細分的點云簡化算法[2]；宋大虎等利用點云鄰域的幾何信息構(gòu)建評估函數(shù)模型，通過迭代刪除評估值最小點，提出了一種具有穩(wěn)健性的基于邊界特征點保留的簡化算法[3]。上述簡化算法，均未對簡化結(jié)果進行量化評價。楊榮華依據(jù)信息熵的理論提出了點云信息量的概念，并提出了基于點特征信息量的簡化算法[4]；陳西江等依據(jù)最小熵函數(shù)原則進行點云簡化，探索了一種在精度和速度上平衡最優(yōu)的非均勻簡化算法，提出了利用法向量夾角構(gòu)建信息熵對點云的特征進行直接評價，以避免誤差二次傳遞的點云簡化算法[5]。借鑒上述思想，為克服利用固定鄰域進行點云簡化造成的誤差累計與傳遞問題，引入最優(yōu)鄰域及二次曲面擬合誤差最小理論，提出了最優(yōu)鄰域二次曲面誤差的點云簡化算法。

1 點云非均勻簡化算法

鄰域表面的曲率并不是目標物表面采樣點固有的特征，其數(shù)值大小取決于鄰域的大小范圍[6]，本文通過最優(yōu)鄰域熵函數(shù)理論確定最優(yōu)鄰域的范圍以克服上述問題，并結(jié)合二次曲面擬合誤差最小理論以提高精度，提出了最優(yōu)鄰域二次誤差曲面的點云非均勻簡化算法，即保留特征點，對非特征點按照二次曲面誤差最小的原則進行點云的簡化。其具體步驟如下所述。

1.1 特征點的提取

為保證后續(xù)曲面重建形狀的精確性，本文重點提取代表鄰域表面凹凸特性的輪廓點和代表曲面尖銳形狀區(qū)域特性的角點等特征點。若點p為特征點，則以該點為采樣中心構(gòu)建的局部鄰域的曲率值相對較大，從幾何意義上，該局部鄰域范圍內(nèi)的點云至過點p處的微切平面的距離之和也較大，反之亦然。

局部鄰域范圍內(nèi)點云至微切平面的平均距離表達式為

(1)

式中，{pj}為p點的局部鄰域范圍內(nèi)的點云；np為p點處的平均法向量；(p-pj)·np為鄰域內(nèi)點云pj到過點p的微切平面的距離。如果dis(p)的結(jié)果大于閾值，則認為該點為特征點，否則認為該點為非特征點。為了有效區(qū)分特征點和非特征點，有效控制特征點的比例，依據(jù)式(2)設(shè)置閾值。其中，N為鄰域內(nèi)點云數(shù)量。

(2)

1.2 局部最優(yōu)鄰域的確立

通過經(jīng)典的PCA(主成分分析)算法求得局部鄰域點云的特征值及特征向量，依據(jù)特征值組建表示形狀的維度特征，并構(gòu)建基于維度特征的最優(yōu)鄰域熵函數(shù)。其具體做法如下：

Ef=-α1Dlnα1D-α2Dlnα2D-α3Dlnα3D

(3)

首先，確定鄰域搜索半徑的下限和上限及變化步長rΔ，并設(shè)定初始搜索半徑r為rmin，并依次令r=r+rΔ，根據(jù)搜索半徑，對局部鄰域內(nèi)的點云分別運用PCA算法計算相應的維度特征和熵函數(shù)值，直至r>rmax。最后，比較并選出最小熵函數(shù)值并將其對應半徑所覆蓋的區(qū)域作為最優(yōu)鄰域。

1.3 確定非特征點局部最優(yōu)鄰域的權(quán)重

完整的目標物表面原始點云數(shù)據(jù)是由兩站或更多站的具有重疊區(qū)域的點云數(shù)據(jù)配準而成，使得重疊區(qū)域的點云比其他區(qū)域的點云密度大；受目標物表面凹凸、掃描入射角和掃描距離等因素的影響，同一物體不同區(qū)域的點云密度不同。為快速有效地進行簡化，得到高質(zhì)量的目標物表面點云簡化數(shù)據(jù)，本文依據(jù)不同鄰域的密度確定其權(quán)重。本文對每個點云依據(jù)其局部鄰域的密度計算其權(quán)重為

(4)

1.4 選取局部最優(yōu)鄰域范圍內(nèi)的最優(yōu)點

該簡化算法的核心是對非特征點云的局部最優(yōu)鄰域選取最優(yōu)點，并以該點取代該鄰域范圍內(nèi)的所有點云。在簡化過程中，將二次曲面誤差最小原則引入到鄰域最優(yōu)點的選取工作中，力求達到最佳的點云簡化效果。為計算每個以采樣點c為中心的最優(yōu)鄰域范圍內(nèi)的最優(yōu)點云，定義一個二次曲面誤差函數(shù)為

(5)

式中，R為最優(yōu)鄰域半徑；x為最優(yōu)鄰域范圍內(nèi)的最優(yōu)點(該點是否為鄰域最優(yōu)點，還需進一步判斷)；{wj}為由式(4)定義的權(quán)重；pj為最優(yōu)鄰域范圍內(nèi)的點云；nj為pj處的法向量；nj·(x-pj)代表點x到過pj點處的微切平面的距離；GR(‖‖)為類高斯函數(shù)，其表達式為

(6)

2 簡化質(zhì)量評價

目前，點云簡化算法的優(yōu)劣主要從簡化度和速度兩個量化方面及簡化前后圖像對比圖進行比較分析，未對簡化質(zhì)量進行充分的量化分析。本文引入信息熵評價指標對簡化結(jié)果進行定量的精度分析。利用精度、簡化度和速度3個指標進行定量分析，在視圖效果與速度、簡化度和精度等量化指標上分別進行對比分析，完成點云簡化及簡化結(jié)果的質(zhì)量評價工作。

信息熵是信源的平均不確定性描述，是信源總體信息在平均意義上的測度，是自信息的數(shù)學期望，其值由該點的概率確定，概率大時，不確定度小，反之則大，因此，信息熵可用來表示信息的價值。本文采用信息熵的理論對點云的重要性進行評價。從后續(xù)曲面重建的角度出發(fā)，為避免誤差的傳遞與累積，計算了最優(yōu)鄰域表面的二次曲面誤差，通過構(gòu)建基于二次曲面誤差的信息熵進行點云簡化質(zhì)量的評價。

(7)

(8)

式中，Qi、Qj為局部鄰域采樣點處的二次曲面誤差；

qi、qj分別為種子點和鄰域點的二次曲面誤差的概率分布。信息熵越大，代表平坦區(qū)域的點云越多，點云簡化質(zhì)量越差；信息熵越小，代表目標物表面特征尖銳區(qū)域的點云越多。為評價目標物整體簡化結(jié)果，引入點云平均熵，其表達式為

(9)

3 試驗分析

為驗證本文簡化方法的有效性，采用Rigel-VZ400三維激光掃描儀，設(shè)置采樣間隔為0.002 m，對獅子雕塑進行掃描，配準后的效果如圖1所示(不同灰度代表不同測站的點云)。為使簡化效果更加直觀，本文以其中一個測站的點云數(shù)據(jù)為例。

圖1 配準后的點云數(shù)據(jù)

3.1 特征點的提取

在點云簡化時，為保留最佳數(shù)量的精細特征，保證簡化質(zhì)量，首先應進行特征點的提取。為提取適宜于獅子雕塑的特征點云，對式(4)中距離閾值的尺度因子α分別取不同的值進行驗證，以確定能夠保留特征點最佳的距離閾值的尺度因子，其結(jié)果如圖2所示。

由圖2可知，當α=1.75時，雕塑表面特征尖銳區(qū)域的點云均已提取出來，但當α=1.5時，含有較多的非最尖銳特征區(qū)域的點云；當α=2.0及2.25時，軀干及額頭表面特征點云缺失較多。因此，本文選取α=1.75時的點云數(shù)據(jù)處理結(jié)果進行后續(xù)的簡化處理。

圖2 不同尺度因子的特征點提取結(jié)果

3.2 不同簡化算法的對比分析

Awwad等[7]指出：為進行有效的PCA解算，鄰域范圍內(nèi)點云應在10個以上，結(jié)合獲取掃描目標物的點云間隔，本文設(shè)定最小搜索半徑rmin為0.004 m,步長rΔ為0.004 m，設(shè)置最大搜索半徑為0.03 m(鄰域搜索半徑一般為點云間隔的10倍為宜[8]，最優(yōu)鄰域半徑一般較為接近最小搜索半徑[9]，綜合考慮以上因素和迭代效率確定了最大搜索半徑)，采用最優(yōu)鄰域二次誤差曲面點云非均勻簡化算法的結(jié)果如圖3(a)所示。為了驗證所提方法的有效性，實現(xiàn)了自適應曲率簡化算法和均勻格網(wǎng)簡化算法，其簡化結(jié)果分別如圖3(b)、圖3(c)所示。

圖3 多種方法簡化效果對比

由圖3可知，最優(yōu)鄰域二次誤差曲面點云非均勻簡化算法由于是從曲面擬合誤差最小的角度出發(fā)，未出現(xiàn)點云空洞，該方面明顯優(yōu)于均勻格網(wǎng)簡化算法；保留的點云數(shù)據(jù)在能夠描述目標物信息的前提下，更具平滑性，該方面優(yōu)于自適應曲率簡化算法。

除了對簡化結(jié)果進行視覺對比分析，本文還對簡化結(jié)果在簡化度、速度和精度等方面進行了量化分析，分析結(jié)果見表1、表2。

表1 簡化結(jié)果的速率評價 s

表2 簡化結(jié)果的信息熵評價

由表1和表2可知，自適應曲率簡化算法的3個指標均介于基于二次曲面誤差的點云非均勻簡化算法與均勻格網(wǎng)簡化算法之間。最優(yōu)鄰域二次誤差曲面點云非均勻簡化算法由于受選擇最優(yōu)鄰域時迭代運算的影響，耗時最久，但是精度最高，即信息熵最小，保留了更多的特征尖銳區(qū)域的點云且表面更為平滑；格網(wǎng)簡化算法不涉及點云特征等信息的分析，速度最快，但出現(xiàn)了大量的點云空洞，而且與其他方法相比，保留的特征點更少，效果更差。

4 結(jié) 論

本文通過將最優(yōu)鄰域理論與二次曲面擬合誤差控制理論引入到點云簡化算法中，減弱簡化過程中的累計誤差與傳遞誤差，并保證簡化結(jié)果的平滑性，更好地服務(wù)于后續(xù)的曲面重建。通過試驗表明，基于二次曲面誤差的點云非均勻簡化算法整體效果明顯優(yōu)于自適應曲率簡化和均勻格網(wǎng)簡化方法，有更好的應用價值。