黃曉銘，楊 劍，陳 輝

(上海電力學院自動化工程學院，上海 200090)

隨著科學技術的發(fā)展，三維激光掃描設備的精度逐漸得到提升，通過掃描幾乎能夠采集到原始模型表面完整的數據.[1-2]但是，由于采集到的點云數據量大且密度高，如果直接對其進行處理，必將降低后續(xù)三維重建的效率，影響重構目標表面的光滑性，致使重建效果欠佳.與此同時，龐大的數據量在存儲、顯示方面也會對計算機提出很高的要求，導致數據處理效率不高.因此，在保留點云數據細節(jié)特征和不影響模型重建精度的前提下，需要對海量數據進行點云精簡[3-4]，以達到去除冗余點和提高重建效率的目的.

1 激光點云數據精簡算法的研究現(xiàn)狀

目前，國內外學者對點云數據進行了大量的研究，提出了許多可行的點云精簡算法.對于空間散亂點云，由于散亂點云數據之間沒有明顯的拓撲關系，如果對海量點云直接進行處理，就會嚴重影響算法的運行效率；因此應先對采集到的點云數據建立合適的幾何拓撲關系以縮短精簡時間.建立點云拓撲關系的方法主要有八叉樹法、空間均勻柵格劃分法和k-d樹法等[5-6]，流行的散亂點云數據精簡算法有三角網格法、隨機采樣法、聚類法、迭代法、均勻網格法、非均勻網格法和曲率采樣法等[7-9].

1996年，D J Weir等[10]提出了包圍盒法，將所有的點云數據包含在最小空間長方體中，根據設定的小包圍盒將長方體劃分為大小相同的包圍盒，保留小包圍盒的中心點，刪除其余點.該算法原理簡單，易于實現(xiàn)，適用于均勻分布點云數據的精簡，但中心點有可能并非原始點云數據，易造成細節(jié)特征的丟失.1997年，R R Martin等[11]提出了均勻網格法，將點云空間進行了均勻網格劃分，只保留各網格的中值點.該方法與包圍盒法類似，容易丟失特征點，不能保持原始模型的特征信息.2001年，K H Lee等[12]采用非均勻網格精簡點云數據，在均勻網格劃分的基礎上，根據點云的法矢偏差值對均勻網格進一步細分，即在特征區(qū)域劃分更多的網格，而非特征區(qū)域則相反.這使得特征區(qū)域能保留相對多的點，而非特征區(qū)域則保留較少的點，因此，與均勻網格法相比，該算法能較好地保留細節(jié)特征.2008年，N Dyn 等[13]通過構造非負函數來衡量每一個點云數據的重要性，并用迭代的方法對點云進行精簡.該方法取得了不錯的精簡效果，準確度高，但計算量較大.2013年，H Benhabiles等[14]將聚類分析法和由粗到細策略相結合，提出了一種可以保留銳利邊緣點的快速點云精簡算法.該算法與其他簡化算法相比，很好地處理了銳利邊緣點的問題.

國內研究學者也對精簡算法進行了大量研究.1999年，Chen Y H等[15]采用基于三角網格的點云精簡算法，對采集到的點云數據進行三角化處理，利用向量加權算法對三角網絡進行冗余判定，并刪除冗余的網格以達到精簡的目的.2004年，萬軍等[16]根據平均點距對點云進行精簡.該方法對特征點的識別度較差，容易丟失復雜區(qū)域的幾何特征.2007年，王宏濤等[17]采用八叉樹法對點云空間進行劃分，只保留葉節(jié)點中最靠近重心的點.該方法處理速度較快，但不能充分保留點云的特征點.2008年，周波等[18]研究了基于八叉樹的非均勻網格法，但該算法不能完整保留邊界點和細節(jié)特征.2011年，Shi B Q等[19]提出了基于K均值聚類的自適應點云精簡算法.該算法能夠保證原始模型邊界的完整性且點云分布較為合理，但是對噪聲比較敏感.2015年，袁小翠等[20]根據點云的微分信息對點云數據進行K均值聚類，然后對點云空間進行全局聚類，進而以聚類中心點代替該類數據點來達到精簡的目的.

然而，上述方法對點云進行精簡時未考慮點云特征問題，對點云的細節(jié)特征保留得不夠完整，無法很好地逼近點云原型，不適合具有復雜特征和多樣曲率的高密度散亂點云的數據精簡.[21]因此，近年來保持特征的精簡算法較為流行.目前，對特征信息的判別主要依據曲率變化的趨勢，通過點云微分信息將點云數據劃分為特征區(qū)域和非特征區(qū)域[22-23]，根據不同區(qū)域的特點采用不同策略進行精簡，確保在精簡的同時保留更多的模型細節(jié)特征.2006年，孫肖霞等[24]通過擬合最小二乘球來估算曲率，但該算法較為復雜,而且精簡后的點云在曲率較小處易出現(xiàn)空白.2009年，劉濤等[25]在包圍盒法的基礎上提出一種曲率精簡算法，該方法能很好地保留特征點，但在平坦區(qū)域容易產生空洞，不利于模型的三維重建.2010年，周煜等[21]結合八叉樹空間劃分法和平均曲率法，將點云模型包含在空間包圍盒內并設定閾值，當小包圍盒平均曲率大于閾值時細分包圍盒，反之保留曲率值最接近平均曲率值的點并刪除其余點.該算法能很好地保留數據的細節(jié)特征，但計算量大，效率有待提高.2011年，P F Lee等[26]利用離散形態(tài)算子對點云模型進行特征提取，可有效保留特征點，但易受噪聲干擾.2012年，朱煜等[27]根據點的空間主曲率對點云數據進行精簡，取得了較好的精簡效果，但主曲率的獲得需要對各點進行二次曲面擬合，運算過程耗時長，且難以實現(xiàn)海量點云的精簡.葛源坤等[28]提出一種曲率精簡算法，對空間進行劃分并搜索各點的K鄰域，然后計算各點的曲率值，合理設置曲率閾值.該算法雖然能獲得較好的精簡率，但是二次曲面擬合過程并不理想，不適用于包含豐富細節(jié)信息的點云模型.李鳳霞等[29]利用法向量夾角精簡點云數據，得到了較好的精簡效果，但該方法需要對點云中每個點進行最小二乘擬合，計算效率低.2013年，陳璋雯等[30]采用模糊熵迭代法精簡點云數據，有效地保留點云的細節(jié)特征，但涉及大量的曲率計算，耗時較大.2015年，Li H等[31]提出以點到局部平面的投影殘差來判定點云數據的保留與否，但該算法受噪聲的影響大，容易丟失點云模型中平滑區(qū)域的細節(jié)信息.2016年，楊秋翔等[32]以數據點主曲率的Hausdorff距離為依據提取點云數據特征點，該方法提高了簡化效率，但數據點主曲率的Hausdorff距離不一定都相等，導致精簡結果不均勻.此外，激光點云數據的精簡算法還有很多種且各具優(yōu)缺點.不同的精簡算法適用于不同的場景，在工程實際中，應根據需求來選擇合適的精簡算法，以期得到符合工程要求的結果.

總結上述精簡算法，將點云精簡算法歸納為3類：一類是基于概率的精簡法，如隨機采樣法等；二類是基于網格的精簡法，如包圍盒法、三角網格法和均勻網格法等；三類是基于特征信息的精簡法，如最小距離法、曲率精簡法等.點云精簡算法眾多，控制量不統(tǒng)一，缺乏定性和定量的比較.筆者在眾多方法中篩選出3種常用的方法，即包圍盒法、隨機采樣法和曲率精簡法進行性能比較.首先選取斯坦福大學提供的Bunny模型和三維重構中常用的椅子模型為實驗對象，然后在MATLAB中編程并控制其中的變量因素，最后對原始點云進行精簡處理，直觀比較輸出的精簡結果，分析各種算法的優(yōu)劣性和適用性.

2 幾種典型的點云數據精簡算法

2.1 包圍盒法

包圍盒法是一種傳統(tǒng)的點云數據精簡算法，它的工作原理為：構建一個包含所有點云數據的包圍盒，并將其分解成若干均勻大小的小包圍盒，選取最靠近中心的點來代替小包圍盒所有的點以達到精簡點云數據的目的，并通過控制小包圍盒的大小來控制精簡結果.該方法簡單高效且容易實現(xiàn)，是一種簡單的基于空間準則的精簡算法，對表面不復雜和曲率變化不大的物體的點云數據的精簡很有效.精簡后的點云比較均勻，能夠反映簡單模型的輪廓特征，但是當物體表面有大曲率曲面時，精簡曲面將不能很好地保持原有的模型特征，也無法確保精簡的精度，主要適用于模型表面的形狀相對簡單且對精度要求不高的場合.

2.2 隨機采樣法

隨機采樣法的基本思路是：針對散亂的點云數據設計一個隨機函數，使其產生的隨機數能夠覆蓋點云分布的所有范圍，然后依據隨機數將點云數據中與之對應的數據點以相等的概率予以刪除，直到點云數據中剩余的點數達到精簡要求.該方法對于海量點云數據有較高的精簡效率，實現(xiàn)過程簡單高效，運行速度快，但是沒有考慮到點云空間的具體特征和細節(jié)，容易丟失原始模型的空間幾何特征，而且隨機函數的隨機性導致每次運行后的精簡效果都不一致，從而點云數據的精簡結果無法控制.因此，該方法在點云模型要求較高的實際應用中有很大局限性，主要作為其他精簡算法的補充方法，對點云數據進行后續(xù)的精簡操作.

2.3 曲率精簡法

曲率精簡法以數據點的曲率為依據，在曲率大的區(qū)域精簡少量點，以保留足夠多的點來表達模型的幾何特征，而在曲率相對較小的區(qū)域精簡較多點以減少數據點的冗余.這是因為點云模型的曲率大小對應模型的幾何特征分布，表示點云模型的內部屬性：對于曲率大的區(qū)域，模型表面的變化相對劇烈，特征比較明顯；而在曲率較小的區(qū)域，模型表面的變化相對平緩，特征相對不明顯.因此，該方法在刪除冗余數據的同時，能盡量保留點云模型的細節(jié)特征，實際應用中可以采用反映曲率變化的曲面特征參數作為點云精簡的判別準則.相比其他點云精簡算法，曲率精簡法的優(yōu)點在于既能夠準確地保留原始模型的細節(jié)特征信息，又能有效地減少冗余的數據點，但是該方法存在曲率計算過程較為復雜、算法運行耗時長和對計算機的性能要求高等缺點.此外，在曲率較小的區(qū)域，該方法會刪除較多的數據點；在待刪除的數據點的選擇上，該方法并沒有遵循均勻精簡的規(guī)則，會造成局部空洞現(xiàn)象.

3 實例分析

筆者對同一目標點云分別使用包圍盒法、隨機采樣法和曲率精簡法進行精簡，在MATLAB平臺上實現(xiàn)編程.椅子模型和Bunny模型的原始點云及其經不同精簡算法處理后的圖像如圖1所示，各種算法的結果比較列于表1.

圖1 2個模型的原始點云及其精簡后的圖像Fig. 1 Original Point Cloud and Reduction Results of Two Models

模型組別點云個數精簡率/%精簡速度精簡效果椅子原始點云 49 960包圍盒法 16 94466.08一般可作初步精簡隨機采樣法16 98666.00快 需要解決特征點丟失問題曲率精簡法16 36967.24慢 需要控制時間模型組別點云個數精簡率/%精簡速度精簡效果Bunny原始點云 35 947包圍盒法 11 32568.50一般可作初步精簡隨機采樣法11 50368.00快 需要解決特征點丟失問題曲率精簡法12 09566.35慢 需要控制時間

從表1可以看出，在以上算法中，隨機采樣法速度最快而基于曲率的精簡算法速度最慢，包圍盒法從時間效率來說介于兩者之間.在精簡率相近的情況下，各算法都可以保持模型的整體樣貌，但有的喪失了一些重要的細節(jié)點.從圖1可以看出：經包圍盒法精簡后，點云分布比較均勻，但在平坦區(qū)域還是存在很多的冗余信息，在曲率變化較大的區(qū)域表面特征丟失比較嚴重；經隨機采樣法精簡后，點云分布比較均勻，但不能很好地突出模型的幾何特征，細節(jié)丟失嚴重，精簡效果的隨機性較大，不能很好地保留細節(jié)特征；經曲率精簡法精簡后，在曲率大的地方點云比較密集，說明較好地去除了點云的冗余數據并有效地保留了點云細節(jié)特征，但因分布不均勻，點云在曲率較小處出現(xiàn)了空洞現(xiàn)象.

4 結語

筆者重點綜述了激光點云數據模型的精簡算法，分析了點云精簡算法的國內外研究現(xiàn)狀，并對最常用的3種算法進行了簡單介紹及實驗驗證，分析了它們的優(yōu)缺點.點云精簡結果質量的好壞決定著后續(xù)配準及三維重建的效果，對點云精簡算法質量的衡量要綜合考慮精度、簡度、速度和適用性4個方面.理想的點云精簡算法是用最少的數據點表達出最重要的特征信息，并在這個過程中有較快的運行速度.在實際應用中，要求一個精簡算法同時滿足所有要求是十分困難的，而且單純使用一種方法一般無法取得滿足實際要求的精簡效果，因此對現(xiàn)有方法的改進和融合是將來的研究方向.