李昕

摘要：提出一種以梯田田坎面特征為提取依據(jù)的改進(jìn)法矢向量點(diǎn)云提取算法。該算法以梯田的點(diǎn)云的法矢向量為主要特征，根據(jù)需要梯田點(diǎn)云的特征，提出了一種基于距離權(quán)重的法矢向量計(jì)算方法，將梯田數(shù)據(jù)的坎面快速準(zhǔn)確的提取出來(lái)。

關(guān)鍵詞：點(diǎn)云；法向量；田坎面

中圖分類號(hào)：TP391.41 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1007-9416（2017）04-0099-02

在如今數(shù)字化世界的時(shí)代中，隨著計(jì)算機(jī)技術(shù)和傳感技術(shù)等領(lǐng)域的快速發(fā)展，極大促進(jìn)了測(cè)量測(cè)繪以及逆向工程等的發(fā)展[1]。在野外測(cè)量中，對(duì)復(fù)雜地形的信息采集以及數(shù)據(jù)建模等需求也越來(lái)越高，隨著機(jī)載雷達(dá)、車載雷達(dá)、無(wú)人機(jī)等工具的進(jìn)步，采集的地形信息也越來(lái)越全面，如何合理高效的利用這些數(shù)據(jù)來(lái)提取所需要的信息，對(duì)后續(xù)的三維建模，土地面積計(jì)算發(fā)揮著至關(guān)重要的作用[2][3]。

在對(duì)散亂三維點(diǎn)云的信息研究的過(guò)程中，三維點(diǎn)云的法向量作為三維點(diǎn)云空間的重要幾何特征，是點(diǎn)云信息提取尤其是三維邊界以及特征面提取的一個(gè)重要指標(biāo)，同時(shí)也有許多與之相關(guān)的研究方法[4][5]。因此本文提出一種基于距離權(quán)重的法矢向量計(jì)算方法，針對(duì)所要求的提取梯田坎面的目標(biāo)，對(duì)點(diǎn)云數(shù)據(jù)進(jìn)行K鄰域搜索，通過(guò)基于Delaunay的方法對(duì)數(shù)據(jù)點(diǎn)建立三角網(wǎng)，并基于鄰域點(diǎn)與目標(biāo)點(diǎn)的距離來(lái)重新對(duì)法矢向量值進(jìn)行估算，提高梯田田坎面提取的精度。

1 研究方法

由于散亂三維點(diǎn)云在空間分布上呈無(wú)序狀態(tài)，為提高計(jì)算效率，保證目標(biāo)特征點(diǎn)的提取，可對(duì)點(diǎn)云建立kd樹索引。K近鄰算法一般是通過(guò)計(jì)算與目標(biāo)點(diǎn)的距離，對(duì)采樣點(diǎn)搜索出最臨近的K個(gè)點(diǎn)。通過(guò)K近鄰算法對(duì)目標(biāo)點(diǎn)及其進(jìn)行擬合進(jìn)而計(jì)算出法矢向量，通過(guò)設(shè)置特征值來(lái)提取符合要求的數(shù)據(jù)點(diǎn)。

1.1 K鄰近點(diǎn)的搜索

Kd樹是一種分割K維數(shù)據(jù)空間的數(shù)據(jù)結(jié)構(gòu)，是二進(jìn)制空間分割樹的特殊情況。 在三維無(wú)序點(diǎn)云數(shù)據(jù)處理中，三維kd樹索引的建立能夠極大的提升臨近點(diǎn)的搜索效率[6]。

其基本構(gòu)建思路：首先對(duì)三維點(diǎn)云數(shù)據(jù)進(jìn)行遍歷，對(duì)X、Y、Z坐標(biāo)進(jìn)行方差計(jì)算，并以大小進(jìn)行排序來(lái)對(duì)分割軸進(jìn)行編號(hào)；依據(jù)編號(hào)選定坐標(biāo)域，以位于正中間的數(shù)據(jù)點(diǎn)為節(jié)點(diǎn)，對(duì)位于分割軸兩側(cè)的點(diǎn)進(jìn)行分割，確定左右空間；按照編號(hào)大小，對(duì)剩下的坐標(biāo)域以位于正中間的數(shù)據(jù)點(diǎn)為節(jié)點(diǎn)分割；遞歸上述過(guò)程，直至空間中只包含一個(gè)數(shù)據(jù)點(diǎn)為止。

在通過(guò)無(wú)序的點(diǎn)云數(shù)據(jù)建立Kd索引之后，通過(guò)目標(biāo)點(diǎn)P（PX、PY、PZ）坐標(biāo)與節(jié)點(diǎn)的坐標(biāo)值進(jìn)行比較，選取最近的根節(jié)點(diǎn)作為目標(biāo)節(jié)點(diǎn)進(jìn)行遍歷，搜索出的最近的K個(gè)點(diǎn)，即為目標(biāo)的K鄰域點(diǎn)集Pk={P1、P2、P3……Pk}。

1.2 改進(jìn)的法矢向量提取方法

1.2.1 法矢向量提取方法

法矢向量是離散空間點(diǎn)云的一個(gè)重要空間幾何特征，因此在三維點(diǎn)云空間特征提取中，估算點(diǎn)的法矢向量是一個(gè)關(guān)鍵的過(guò)程[6]。常見的點(diǎn)云法矢向量計(jì)算方法有：通過(guò)對(duì)點(diǎn)云進(jìn)行局部表面擬合和基于Delaunay的方法[7]。

本文利用基于Delaunay的方法來(lái)估算目標(biāo)點(diǎn)P的法矢向量，通常采用的辦法為：首先對(duì)P及其K鄰域點(diǎn)集Pk構(gòu)建Delaunay三角網(wǎng)；計(jì)算所有通過(guò)P點(diǎn)的三角面的法向量，并進(jìn)行法向量一致化處理，得到過(guò)P點(diǎn)的三角網(wǎng)的法向量集；通過(guò)三角面的法向量集Nk={N1、N2、N3}加權(quán)平均的方式對(duì)P點(diǎn)的法向量進(jìn)行估算。P點(diǎn)的法向量Np的估算表達(dá)式為：。

1.2.2 改進(jìn)算法

在基于Delaunay的方法過(guò)程中，法矢向量是由鄰近三角網(wǎng)的法矢向量加權(quán)平均進(jìn)行估算的，點(diǎn)云法向量的估算的準(zhǔn)確性和三角網(wǎng)的法矢向量有極高的關(guān)聯(lián)性。

在提取梯田田坎特征面的過(guò)程中，需將田坎點(diǎn)云數(shù)據(jù)中的田坎面點(diǎn)保留，同時(shí)盡可能的除去邊坡面點(diǎn)。為了更好的提取梯田田坎邊點(diǎn)以及保留梯田田坎面的特征，本文對(duì)點(diǎn)云估算方法進(jìn)行改進(jìn)：在目標(biāo)點(diǎn)進(jìn)行法向量估算構(gòu)建三角網(wǎng)的過(guò)程中，對(duì)通過(guò)目標(biāo)點(diǎn)三角網(wǎng)的法向量進(jìn)行加權(quán)，依據(jù)構(gòu)建三角網(wǎng)的點(diǎn)與目標(biāo)點(diǎn)的距離進(jìn)行權(quán)重賦值，降低遠(yuǎn)點(diǎn)對(duì)目標(biāo)點(diǎn)法矢向量計(jì)算的影響，得到新的點(diǎn)云法向量估算公式如下：

式中：L為點(diǎn)集Pk中與目標(biāo)點(diǎn)P歐式距離的最大值，La、Lb分別問(wèn)過(guò)P點(diǎn)三角網(wǎng)的其余兩頂點(diǎn)與點(diǎn)P的歐式距離。

1.2.3 梯田田坎特征面提取

根據(jù)得到的梯田點(diǎn)云法矢向量，對(duì)梯田數(shù)據(jù)點(diǎn)的法向量與其K鄰近點(diǎn)的法向量的夾角αi計(jì)算得到夾角集A，A={α1、α2、α3……αk}，并進(jìn)行加權(quán)運(yùn)算得到該點(diǎn)與K鄰域點(diǎn)的法向量夾角的均值αp；同時(shí)計(jì)算出點(diǎn)法向量與Z坐標(biāo)軸的夾角βp。通過(guò)設(shè)置閾值k1和k2，可根據(jù)αp與k1以及βp與k2的對(duì)比結(jié)果進(jìn)行分類，并進(jìn)行分類，當(dāng)αp>k1將其視為田坎邊界點(diǎn)，當(dāng)αpk2時(shí)，將其視為邊坡點(diǎn)，其余點(diǎn)則為田坎表面點(diǎn)。

2 實(shí)驗(yàn)分析

硬件為CPU為Intel雙核20G，操作系統(tǒng)為Windows 10，軟件為VC++6.0和GeomagicStudio2013，機(jī)載激光掃描數(shù)據(jù)為Riegle公司的 VZ-4000獲取的貴州某梯田三維點(diǎn)云數(shù)據(jù)。

2.1 數(shù)據(jù)預(yù)處理

首先將數(shù)據(jù)導(dǎo)入到GeomagicStudio2013里，通過(guò)軟件現(xiàn)有算法對(duì)數(shù)據(jù)進(jìn)行降噪處理，得到實(shí)驗(yàn)用數(shù)據(jù)（圖1）。

2.2 實(shí)驗(yàn)過(guò)程

（1）讀取處理后的梯田點(diǎn)云數(shù)據(jù)并表達(dá)（圖2），建立kd樹索引組織點(diǎn)云數(shù)據(jù)。

（2）對(duì)數(shù)據(jù)點(diǎn)P求出點(diǎn)的K鄰域點(diǎn)集，并依據(jù)改進(jìn)算法進(jìn)行法向量計(jì)算得到結(jié)果N。

（3）對(duì)目標(biāo)點(diǎn)P及其K鄰域點(diǎn)的法矢向量依據(jù)公式得到其與鄰域點(diǎn)法向量夾角均值αp和其與Z坐標(biāo)軸的夾角βp和設(shè)置的閾值進(jìn)行比較，這里k1取45°，k2取5°。

（4）對(duì)所有數(shù)據(jù)點(diǎn)依次遍歷進(jìn)行上述過(guò)程得到實(shí)驗(yàn)結(jié)果并表達(dá)（圖3）。

（5）通過(guò)GeomagicStudio進(jìn)行點(diǎn)云矢量數(shù)據(jù)操作，根據(jù)設(shè)置的閾值提取目標(biāo)點(diǎn)，得到結(jié)果（圖4），并通過(guò)人工識(shí)別的方法對(duì)兩數(shù)據(jù)結(jié)果進(jìn)行比對(duì)，檢驗(yàn)其保留的邊坡點(diǎn)。

得到的比對(duì)結(jié)果如表1。

3 結(jié)語(yǔ)

本文通過(guò)K鄰域算法，求取點(diǎn)云數(shù)據(jù)點(diǎn)及其鄰域并生成三角網(wǎng)得到相關(guān)面的法向量，通過(guò)賦予權(quán)值的方式對(duì)點(diǎn)云的法向量估算方法進(jìn)行改進(jìn)，設(shè)置合理的閾值同目標(biāo)點(diǎn)及其鄰域的法矢向量夾角均值比較來(lái)提取符合要求的點(diǎn)，從實(shí)驗(yàn)結(jié)果以及相關(guān)軟件的處理結(jié)果來(lái)看，該算法能夠相對(duì)快速的提取梯田田坎的表面點(diǎn)數(shù)據(jù)，且達(dá)到較小的誤差。

參考文獻(xiàn)

[1]Masatoshi Hikizu. Motion Planning System for Bin Picking Using 3-D Point Cloud[J]. Intelligent Control and Automation，2016，07（03）：73-83.

[2]王麗輝.三維點(diǎn)云數(shù)據(jù)處理的技術(shù)研究[D].北京：北京交通大學(xué)，2011.

[3]安毅.三維點(diǎn)云數(shù)據(jù)的幾何特性估算與特征識(shí)別[D].大連：大連理工大學(xué)，2011.

[4]趙衛(wèi)東，湯國(guó)安，徐媛，周春寅，錢家忠，馬雷.梯田地形形態(tài)特征及其綜合數(shù)字分類研究[J].水土保持通報(bào)，2013，01（056）：295-300.

[5]劉正.三維點(diǎn)云法向量估計(jì)方法研究[D].華北電力大學(xué)，2015.

[6]雷玉珍.三維點(diǎn)云數(shù)據(jù)處理中的若干關(guān)鍵技術(shù)研究[D].華中科技大學(xué)，2013.

[7]李寶，程志全，黨崗，金士堯.三維點(diǎn)云法向量估計(jì)綜述[J].計(jì)算機(jī)工程與應(yīng)用，2010，（23）：1-7.