基于移動網格點云精簡算法的研究

常 鑫,郎 銳,董建業

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

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

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

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

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

基于上述分析總結，本文提出一種可移動網格劃分的點云精簡算法，該算法主要通過空間網格對點云進行精簡，精簡速度優勢較明顯，能夠達到預期效果，且該算法中二次網格精簡準則能夠將上述算法的精簡準則納入其中。

1 大數據量點云精簡的性能瓶頸

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

2 可移動網格劃分算法

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

2.1 算法總體過程

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

圖1 可移動網格劃分算法實現過程

2.1.1 一次網格劃分

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

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

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

(1)

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

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

2.1.2 二次網格劃分

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

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

完成每個一次網格遍歷后，將所有保留下的點云存儲到二次網格中，同時清空對應的一次網格所有點云數據。當所有遍歷結束后，便完成了二次網格劃分整個過程。

2.1.3 移動網格劃分

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

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

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

圖4 密集點云分布示意圖

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

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

3 實例分析

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

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

圖5 移動網格劃分示意圖

圖6 精簡對比

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

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

表2 精簡數據結果可靠性評估表

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

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

4 結 論

本文在點云模型的空間網格劃分基礎上，采用了可移動網格劃分思想，對大數據點云進行了快速有效的精簡。

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

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

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

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

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

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

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

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

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

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

[7] 麻衛峰, 周興華, 徐文學,等. 一種基于局部曲率特征的點云精簡算法[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] 張麗艷,周儒榮,蔡煒斌,等.海量測量數據簡化技術研究[J].計算機輔助設計與圖形學學報,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].計算機輔助設計與圖形學學報, 2007,19(8):1022-1027.

[14] 倪小軍.點云數據精簡及三角網格面快速重構技術的研究與實現[D].蘇州：蘇州大學,2010.