基于移動網(wǎng)格點云精簡算法的研究

常 鑫,郎 銳,董建業(yè)

(中國電波傳播研究所，山東 青島 266107)

近年來，三維激光技術(shù)在測繪鄰域的應(yīng)用越來越廣泛。然而由于通過掃描獲取的點云數(shù)據(jù)具有冗余量大、存在誤差以及規(guī)則性弱等特點，直接處理原始點云將會耗費大量時間和資源，因此一般在進行點云數(shù)據(jù)后處理之前都要進行預(yù)處理工作，包括點云去噪、點云精簡、數(shù)據(jù)分塊等等。點云精簡是最為基本且非常重要的一步，同時也是逆向工程目前的研究熱點之一。

點云精簡最初的一些方法只是簡單基于點之間距離、曲率、法向等原則，而目前點云精簡的方法主要集中在以下幾種典型方法：包圍盒法、基于幾何圖像精簡法、基于曲率精簡法、基于法向精度精簡法[1-7]。

國外很多學者早就在點云精簡這一鄰域探索出了很多解決方案。如Filip等人采用了包圍盒法來精簡點云數(shù)據(jù)[8]，速度非?？?，但只能用于處理均勻分布的點云；Alexa等人依據(jù)點云對最小二乘移動曲面的影響程度這一權(quán)重來進行點云的精簡，且通過重采樣保證了點云的密度[9]，但其算法過程較為復(fù)雜；Chen.Y.H提出了先對點云進行三角網(wǎng)格化，通過精簡三角網(wǎng)格數(shù)量來減少點云數(shù)量的方法[10]，但往往構(gòu)建三角網(wǎng)過程較繁雜。

國內(nèi)學者針對點云精簡也有很多研究，張麗艷在用Riemann圖建立散亂測點間k鄰近的基礎(chǔ)上，提出了簡化后數(shù)據(jù)集中點個數(shù)、數(shù)據(jù)集中點密度閾值及刪除一點引起法向誤差的閾值這3種簡化準則進行點云精簡[11]，3種算法效率較高且精簡效果較好，但是較算法中的鄰近點個數(shù)K難以確定合適值；Xiao Z提出了一種非均勻點云的精簡算法，主要依據(jù)各點與KD-tree包圍球中心法向內(nèi)積的閾值進行點云的精簡[12]，算法達到的精簡效果很好，但是KD-tree包圍球的半徑難以計算，且法向內(nèi)積計算量較大；王仁方等提出了基于幾何圖像的精簡算法和隨機采樣方法[13]，精簡效率非常高，但容易丟失點云特征；倪小軍提出了一種特征保留的點云自適應(yīng)的精簡算法，將點云劃分為特征點和非特征點，保留特征點，而非特征點則通過計算自適應(yīng)精簡距離閾值進行精簡處理[14]，算法速度較快，能夠較好地保留點云中的幾何特征，但算法較依賴于點集的權(quán)重系數(shù)和初始設(shè)定的距離閾值。

基于上述分析總結(jié)，本文提出一種可移動網(wǎng)格劃分的點云精簡算法，該算法主要通過空間網(wǎng)格對點云進行精簡，精簡速度優(yōu)勢較明顯，能夠達到預(yù)期效果，且該算法中二次網(wǎng)格精簡準則能夠?qū)⑸鲜鏊惴ǖ木啘蕜t納入其中。

1 大數(shù)據(jù)量點云精簡的性能瓶頸

針對大數(shù)據(jù)量點云精簡而言，如果直接依據(jù)給定距離閾值對點云模型進行空間網(wǎng)格劃分，即將點云整個包圍盒沿著空間3個方向劃分成無數(shù)個小網(wǎng)格，分別在小網(wǎng)格內(nèi)進行點云的篩選精簡，通常為方便小網(wǎng)格的二分查找，小網(wǎng)格整體應(yīng)按照其對應(yīng)編碼值按升序或降序排列，因此在進行每次二分插入時，通過二分查找確定相應(yīng)位置后，所有該位置后的小網(wǎng)格數(shù)據(jù)都要往后推，涉及到大量數(shù)據(jù)的拷貝問題，從而產(chǎn)生大數(shù)據(jù)點云精簡的性能瓶頸，其表現(xiàn)在隨著原始點云個數(shù)的逐漸增加，精簡消耗的時間越來越多，大大降低了精簡的效率。為解決這一性能瓶頸，本文采用了在劃分小網(wǎng)格之前先進行一次網(wǎng)格劃分，對點云模型首先進行分塊處理，使得小網(wǎng)格置于一次網(wǎng)格中，大大減少了小網(wǎng)格二分插入的時間消耗。

2 可移動網(wǎng)格劃分算法

本文在基于其他已有研究成果的基礎(chǔ)上，設(shè)計了一種可移動網(wǎng)格劃分算法。算法首先對模型點云進行空間格網(wǎng)化，再依據(jù)距離閾值對已有的格網(wǎng)進行二次網(wǎng)格劃分，依次遍歷二次網(wǎng)格內(nèi)點云，根據(jù)點云權(quán)重關(guān)系篩選出每個二次網(wǎng)格內(nèi)保留下的點。二次網(wǎng)格劃分結(jié)束后，平移點云整體包圍盒最小點，對模型點云進行移動網(wǎng)格劃分，最終篩選出所占權(quán)重較大的所有點云。

2.1 算法總體過程

算法具體過程可以分為以下3個模塊：一次網(wǎng)格劃分、二次網(wǎng)格劃分、移動網(wǎng)格劃分，其實現(xiàn)過程圖如圖1示。

圖1 可移動網(wǎng)格劃分算法實現(xiàn)過程

2.1.1 一次網(wǎng)格劃分

點云模型的一次網(wǎng)格劃分目的主要有兩個，一是便于后期的二次網(wǎng)格劃分的快速查找，二是篩選出點云個數(shù)大于給定點云個數(shù)閾值的區(qū)域。

在進行一次網(wǎng)格劃分前，首先要進行空間三個方向的網(wǎng)格間隔計算。為了保證后期劃分的二次網(wǎng)格不出現(xiàn)跨越一次網(wǎng)格的現(xiàn)象，就要使得一次網(wǎng)格間隔是二次網(wǎng)格間隔的整數(shù)倍。這里采用一種間隔估計算法，首先依據(jù)外業(yè)采集的三維激光掃描儀，確定其采樣點分辨率，根據(jù)實際工程需求，選取適當?shù)亩尉W(wǎng)格的間隔值為Interval，再根據(jù)其間隔和一次網(wǎng)格劃分各方向的估計個數(shù)值GridXYZ，依據(jù)點云包圍盒算出空間3個方向的包圍盒邊長存儲于數(shù)組BoxSide[3]中，通過BoxSide[i]/(GridXYZ*Interval)(i=0,1,2)計算出結(jié)果并取整，得到各個方向上一次網(wǎng)格間隔相對于二次網(wǎng)格間隔的整數(shù)倍數(shù)N[3]。因此，一次網(wǎng)格間隔就為N[i]*Interval(i=0,1,2)，重新按照BoxSide[i]/(N[i]*Interval)+1(i=0,1,2)計算出一次網(wǎng)格各個方向上的總個數(shù)。由于考慮到了取整問題，上述計算出的各個方向上的包圍盒個數(shù)均增加了一個，從而保證點云不會超出一次網(wǎng)格。

網(wǎng)格間隔計算結(jié)束后，開始進行點云模型的一次網(wǎng)格劃分。依據(jù)點云包圍盒的最小點坐標值，通過式(1)計算出點云所處一次網(wǎng)格的三維腳碼值II,JJ,KK。

(1)

為了方便后期查找一次網(wǎng)格，這里采用了一種線性編碼方法。例如，上文求出的一次網(wǎng)格X、Y、Z 3個方向上的包圍盒總數(shù)分別為Count1、Count2 、Count3，那么II、JJ、KK對應(yīng)的編碼值就為：II*Count2*Count3+JJ*Count3+KK。實質(zhì)上就是將一次網(wǎng)格從空間上的三維排列變成了線性排列，如圖2所示。依次遍歷所有點云執(zhí)行上述計算，相同編碼值的點云存儲于同一個一次網(wǎng)格內(nèi)，每個一次網(wǎng)格主要存儲編碼值和所包含的點云數(shù)據(jù)，完成一次網(wǎng)格的初步劃分。

待一次網(wǎng)格初步劃分結(jié)束后，遍歷所有的一次網(wǎng)格，篩選出點云個數(shù)超過給定的點云個數(shù)閾值的所有一次網(wǎng)格，并對這些一次網(wǎng)格再次進行一次網(wǎng)格劃分，其中劃分的個數(shù)估計值可改為GridXYZ/2。此時點云的包圍盒不再是整體點云的包圍盒，需重新進行計算，主要依據(jù)一次網(wǎng)格的編碼值反算出對應(yīng)的三維腳碼值，從而再根據(jù)整體點云包圍盒的最小值，計算出該一次網(wǎng)格的對應(yīng)點云包圍盒大小。迭代上述一次網(wǎng)格劃分，直到一次網(wǎng)格中點云個數(shù)均少于點云個數(shù)閾值，完成一次網(wǎng)格劃分的整個過程。

2.1.2 二次網(wǎng)格劃分

二次網(wǎng)格劃分主要目的是初步篩選出所有權(quán)重較大的點，其中每個二次網(wǎng)格中只存儲一個點。在進行一次網(wǎng)格劃分結(jié)束后，依次遍歷所有一次網(wǎng)格，再在每個一次網(wǎng)格中遍歷所有的點云。逐個取出單個點，根據(jù)式(1)同理計算出每個點的三維腳碼值，再計算其對應(yīng)的二次格網(wǎng)編碼值。此時上文一次網(wǎng)格的線性編碼方法不再適合，由于點云整體包圍盒X、Y、Z 3個方向上所含有的二次網(wǎng)格數(shù)量過大，如果再采用上述一次網(wǎng)格的線性編碼方法，那么二次網(wǎng)格的編碼值會非常大，且會造成大量空網(wǎng)格出現(xiàn)，從而導致其編碼值存儲存在問題。因此這里舍棄一次網(wǎng)格的線性編碼方法，采用任意線性編碼方法，主要就是將一次網(wǎng)格線性編碼的Count2、Count3換成兩個給定的任意固定值(保持前者是后者的平方值即可)，從而確保所有的二次網(wǎng)格編碼統(tǒng)一化。

每次存儲點云到二次網(wǎng)格中，都要進行篩選工作。計算出單點對應(yīng)的網(wǎng)格編碼值后，在當前一次網(wǎng)格內(nèi)查找是否已保存過該編碼值的二次網(wǎng)格。此處為了快速查找出是否存在已有編碼值的二次網(wǎng)格，采用了二分查找方法，如果查找到該代碼則返回對應(yīng)的位置，否則返回其他值。經(jīng)查找，如果未查找到，就創(chuàng)建一個二次網(wǎng)格，存儲其編碼值、該單點的坐標值以及該點的權(quán)重值(如，該點與當前二次網(wǎng)格中心的距離值、該點與掃描設(shè)備原點位置的距離值以及曲率值、法向值等)，然后再二分插入到當前一次網(wǎng)格中，從而達到二次網(wǎng)格編碼值按升序排列在一次網(wǎng)格中；如果查找到了，并獲取到相應(yīng)位置，則比較該單點的權(quán)重值p1和該二次網(wǎng)格中已存的權(quán)重值p0，如果p1>p0，則用該單點坐標和權(quán)重值p1替換二次網(wǎng)格中已保存的對應(yīng)數(shù)據(jù)。

完成每個一次網(wǎng)格遍歷后，將所有保留下的點云存儲到二次網(wǎng)格中，同時清空對應(yīng)的一次網(wǎng)格所有點云數(shù)據(jù)。當所有遍歷結(jié)束后，便完成了二次網(wǎng)格劃分整個過程。

2.1.3 移動網(wǎng)格劃分

移動網(wǎng)格劃分是本算法最核心部分，主要目的是對點云進行二次篩選。由于二次網(wǎng)格劃分中存在一個問題，雖然每個二次網(wǎng)格中都存儲了一個唯一的點，但是會出現(xiàn)兩個點的權(quán)重值非常相近，卻處在不同的二次網(wǎng)格中，從而導致很多密集點無法剔除的現(xiàn)象(如圖3所示，圖3(a)圖中紅色條狀區(qū)域內(nèi)即為密集點區(qū)域)。

通常情況下，采用的方法是將所有處于二次網(wǎng)格邊緣的點篩選出來，存放于一個點云容器中。在單個邊緣點存放前，首先遍歷該容器中已存放的所有點云，篩選出與該邊緣點距離小于二次網(wǎng)格閾值的點。若篩選到符合該條件的點，比較它們與該邊緣點的權(quán)重值，存在權(quán)重值差異小于權(quán)重閾值的情況，則不存放該邊緣點；否則存放。若沒篩選到，直接存放該邊緣點，從而解決了上述問題。但是，該方法在每次遍歷容器中點云消耗的時間非常之多，導致整體上精簡的效率非常的低。

另外如果不采用上述方法，采用單個二次網(wǎng)格鄰域搜索法，遍歷每個二次網(wǎng)格，通過搜索該二次網(wǎng)格周圍鄰近二次網(wǎng)格，尋找與該二次網(wǎng)格中的單點距離小于二次網(wǎng)格間隔的點，找到符合條件的點再進行權(quán)重比較，完成點云二次精簡。但這種方法中每個二次網(wǎng)格最少會與周圍4個二次網(wǎng)格、最多會與周圍26個二次網(wǎng)格存在上述密集點云現(xiàn)象(如圖4所示)，情況非常復(fù)雜，因此在執(zhí)行上會非常困難。

圖4 密集點云分布示意圖

為此，必須避免大量的點云數(shù)據(jù)遍歷以及復(fù)雜的鄰域搜索，本文提出了移動網(wǎng)格劃分的思想，能夠快速地解決上述問題。

移動網(wǎng)格劃分主要是將點云包圍盒的最小點進行平移，點云位置保持不變，重新依據(jù)新的包圍盒的最小點進行二次網(wǎng)格劃分。包圍盒最小點3個方向上的平移距離值可為二次網(wǎng)格間隔值的K倍(其中0

3 實例分析

為了實際分析和驗證本文提出的算法性能，分別對不同點云模型進行精簡實驗，并將其結(jié)果與商業(yè)軟件Geomagic精簡結(jié)果進行對比分析。本實驗的環(huán)境為：CPU：酷睿i5，內(nèi)存：3.0 G，GPU:GeForce GTX 650，操作系統(tǒng)：Windows 7 SP1。

通過對不同大小點云數(shù)據(jù)進行測試，分別得到Geomagic精簡和本文算法精簡的最終成果點云和分別消耗的時間。其中精簡消耗時間對比如表1所示，成果點云的效果圖對比如圖6所示。

圖5 移動網(wǎng)格劃分示意圖

圖6 精簡對比

精簡方法原始點云個數(shù)/萬個精簡后成果點云個數(shù)/萬個消耗時間/sGeomagic軟件距離精簡13.373 52.50042.791 7110.380 327.10 0547.949 1511.784 177.000可移動網(wǎng)格劃分精簡1 118.908 310.296 90.15677.537 51.435383.222 732.386

針對本算法的精簡效果準確性問題，采用誤差度量方法：將精簡后的點云P′進行三維重構(gòu)，生成三角網(wǎng)模型，然后計算原始點云中所有點到該三角網(wǎng)模型的距離。分別用3項指標進行精簡數(shù)據(jù)評估：Dmax、Davg以及Ratio，其中Dmax指的是原始點云集合P中所有點到精簡后點云P′構(gòu)建的三角網(wǎng)模型表面的距離最大值，Davg指的是原始點云集合P中所有點到精簡后點云P′構(gòu)建的三角網(wǎng)模型表面的距離平均值，Ratio指的是存在誤差的區(qū)域占總體區(qū)域百分比。精簡數(shù)據(jù)誤差度量結(jié)果如表2所示。

表2 精簡數(shù)據(jù)結(jié)果可靠性評估表

實驗結(jié)果得出以下結(jié)論：從算法的精簡效果以及效率對比可以看出，本算法精簡的簡度(精簡后點云個數(shù)相對原始點云個數(shù)的百分比)明顯降低，且在精度上很好地保留了點云的特征點，避免了點云“空洞”的現(xiàn)象發(fā)生，時間效率上也達到了明顯的優(yōu)勢。

對于可移動網(wǎng)格劃分的點云精簡算法，主要時間消耗在二次網(wǎng)格的數(shù)據(jù)二分插入上，仍涉及到大量數(shù)據(jù)的拷貝問題，從而導致該算法整體速度減慢。

4 結(jié) 論

本文在點云模型的空間網(wǎng)格劃分基礎(chǔ)上，采用了可移動網(wǎng)格劃分思想，對大數(shù)據(jù)點云進行了快速有效的精簡。

1)算法在對點云直接進行二次網(wǎng)格劃分前，先采用了一次網(wǎng)格劃分，對點云數(shù)據(jù)進行了分塊處理，將二次網(wǎng)格置于一次網(wǎng)格，大大減少了二次網(wǎng)格二分插入時所帶來的時間消耗，整體上加快了點云精簡的速率。

2)算法在進行二次網(wǎng)格劃分結(jié)束后，即第一次點云精簡后，采用了移動網(wǎng)格劃分思想，很好地解決了點云密集無法剔除的問題。

3)算法在進行點云篩選精簡時，能夠很好地兼容其他算法所采用的點云精簡準則，即算法中的二次網(wǎng)格所采用的權(quán)重值可為其他任何算法的權(quán)重值，如曲率值、法向值等等。

由于該算法中點云數(shù)據(jù)的二分插入仍然消耗了大量時間，降低了算法整體的精簡速度，因此如何解決點云的快速二分插入問題需要進一步研究。

[1] 陳達梟, 蔡勇, 張建生. 散亂點云精簡的一種改進算法[J]. 計算機應(yīng)用研究, 2016(9):2841-2843.

[2] 吳祿慎, 俞濤, 陳華偉,等. 基于自適應(yīng)橢圓距離的點云分區(qū)精簡算法[J]. 計算機應(yīng)用與軟件, 2016(2):42-45.

[3] 劉迎, 王朝陽, 高楠,等. 特征提取的點云自適應(yīng)精簡[J]. 光學精密工程, 2017, 25(1):245-254.

[4] 張雨禾, 耿國華, 魏瀟然,等. 保留幾何特征的散亂點云簡化算法[J]. 計算機輔助設(shè)計與圖形學學報, 2016, 28(9):1420-1427.

[5] 律帥. 基于最小生成樹的三維點云數(shù)據(jù)壓縮算法研究[D]. 南京：東南大學, 2016.

[6] 陳新河, 龐俊亭, 周波,等. 改進的分層曲率海量點云精簡算法[J]. 計算機應(yīng)用與軟件, 2016, 33(4):265-267.

[7] 麻衛(wèi)峰, 周興華, 徐文學,等. 一種基于局部曲率特征的點云精簡算法[J]. 測繪工程, 2015(11):13-16.

[8] ALEXA M, BEHR J, COHEN -OR D, et al. Point set surfaces[C]// Visualization, 2001. VIS '01. Proceedings. IEEE, 2001:21-28.

[9] YUAN H, PANG J, JIANWEN M O. Research on Simplification Algorithm of Point Cloud Based on Voxel Grid[J]. Video Engineering, 2015.

[10] CHEN Y H, NG C T, WANG Y Z. Data reduction in integrated reverse engineering and rapid prototyping[J].International Journal of Computer Integrated Manufacturing,1999,12(2):97-103.

[11] 張麗艷,周儒榮,蔡煒斌,等.海量測量數(shù)據(jù)簡化技術(shù)研究[J].計算機輔助設(shè)計與圖形學學報,2001,13(11):1019-1023.

[12] XIAO Z, HUANG W. Kd-tree Based Nonuniform Simplification of 3D Point Cloud[C]// International Conference on Genetic and Evolutionary Computing. IEEE, 2009:339-342.

[13] 王仁芳,張三元,葉修梓.點模型的幾何圖像簡化法[J].計算機輔助設(shè)計與圖形學學報, 2007,19(8):1022-1027.

[14] 倪小軍.點云數(shù)據(jù)精簡及三角網(wǎng)格面快速重構(gòu)技術(shù)的研究與實現(xiàn)[D].蘇州：蘇州大學,2010.