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

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

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

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

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

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

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

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

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

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

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

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

2.1 算法總體過程

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

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

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

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

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

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

(1)

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

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

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

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

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

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

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

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

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

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

圖4 密集點(diǎn)云分布示意圖

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

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

3 實(shí)例分析

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

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

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

圖6 精簡對比

精簡方法原始點(diǎn)云個(gè)數(shù)/萬個(gè)精簡后成果點(diǎn)云個(gè)數(shù)/萬個(gè)消耗時(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

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

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

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

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

4 結(jié) 論

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

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

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

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

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

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

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

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

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

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

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

[7] 麻衛(wèi)峰, 周興華, 徐文學(xué),等. 一種基于局部曲率特征的點(diǎn)云精簡算法[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].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào),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] 王仁芳,張三元,葉修梓.點(diǎn)模型的幾何圖像簡化法[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào), 2007,19(8):1022-1027.

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