最優鄰域二次誤差曲面的點云簡化算法

陸建華，劉 闖， 呂志才

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

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

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

1 點云非均勻簡化算法

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

1.1 特征點的提取

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

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

(1)

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

(2)

1.2 局部最優鄰域的確立

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

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

(3)

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

1.3 確定非特征點局部最優鄰域的權重

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

(4)

1.4 選取局部最優鄰域范圍內的最優點

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

(5)

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

(6)

2 簡化質量評價

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

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

(7)

(8)

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

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

(9)

3 試驗分析

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

圖1 配準后的點云數據

3.1 特征點的提取

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

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

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

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

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

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

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

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

表1 簡化結果的速率評價 s

表2 簡化結果的信息熵評價

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

4 結 論

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