陸建華，劉 闖， 呂志才

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

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

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

1 點(diǎn)云非均勻簡(jiǎn)化算法

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

1.1 特征點(diǎn)的提取

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

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

(1)

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

(2)

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

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

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

(3)

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

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

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

(4)

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

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

(5)

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

(6)

2 簡(jiǎn)化質(zhì)量評(píng)價(jià)

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

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

(7)

(8)

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

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

(9)

3 試驗(yàn)分析

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

圖1 配準(zhǔn)后的點(diǎn)云數(shù)據(jù)

3.1 特征點(diǎn)的提取

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

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

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

3.2 不同簡(jiǎn)化算法的對(duì)比分析

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

圖3 多種方法簡(jiǎn)化效果對(duì)比

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

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

表1 簡(jiǎn)化結(jié)果的速率評(píng)價(jià) s

表2 簡(jiǎn)化結(jié)果的信息熵評(píng)價(jià)

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

4 結(jié) 論

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