保留灰度特征的配準點云數據精簡算法?

仇倩雨 黎 寧 李亞紅 李明磊

（南京航空航天大學電子信息工程學院 南京 211106）

1 引言

近幾年，隨著3D 傳感技術的迅猛發展，點云成為三維物體及其周圍環境的一種重要而有效的表現形式，廣泛應用于諸多領域，如虛擬現實、3D 打印、移動道路測量和歷史文物掃描［1］等。

典型地，我們可由激光掃描儀從真實物體的表面捕獲原始數據點，并在幾分鐘內產生包含數百萬個采樣點的點云，這些點云通常是無序的。同時，對于復雜物件，我們需從多個視點掃描，并將其進行配準。Besl和McKay［2］于1992年提出的ICP算法是最經典的點云配準算法，但其全局最優的收斂性和運行速度嚴重依賴于初始配準位置。因此，在此基礎上許多改進的方法被提出，Chetverikov［3］提出按照配準的重疊率保留用于計算變換參數的點數，從而解決部分重疊點云的配準問題；戴靜蘭［4］等在利用主方向貼合法完成粗略配準后，根據曲率特征點及KDTree 查找最鄰近點，有效地提高了ICP 算法的效率；Per Bergstr?m［5］等通過迭代重加權的最小二乘法來提升配準的魯棒性。李彩林［6］等在已知點云配準初值的基礎上，實現了一種自動全局優化的整體配準方法，用于處理無序的多視角激光掃描的三維點云。周朗明［7］等提出了基于旋轉平臺的點云數據配準策略，不需要提取點云特征完成匹配，只需記錄旋轉平臺每次轉動的角度，以此來推導多視點云間的旋轉矩陣，從而完成自動配準。然而，經過配準最終獲取的點云不可避免地存在數據冗余，龐大的數據量會影響后續處理的運行效率。同時，由于配準存在的誤差及厚度和間距間的不均勻分布等問題，會導致法向量計算的不準確。而三維點的定向法向量在物體識別和表面重建中至關重要，因為它們提供了局部表面信息并且幫助區別底層形狀的內部和外部［8～9］。因此，提升配準后的點云的分布質量，對點云進行精簡是點云數據處理的一個重要課題。

針對過密的散亂點云數據，國內外許多學者已經提出了大量的精簡算法。Sun［10］等提出了包圍盒法，通過對點云建立最小包圍盒并將其劃分為多個小柵格，用距離柵格中心最近的點來代替柵格中的所有點來實現點云的精簡。在此基礎上，李忠仁［11］等結合包圍合法對輸入數據進行K 鄰域距離計算法線估計來確定柵格重心，以重心代替中心作為柵格內的保留點，能夠較好地保留數據的幾何特征，但是此類方法特征丟失較嚴重。因此，Lee［12］等提出非均勻柵格法，通過計算柵格內數據點的法矢偏差，將大于閾值的柵格繼續劃分來實現部分模型特征的保留。Song 等［13］根據每點是否可以由其鄰域內的點代替來評估每點的重要性，迭代去除重要性小的點，可在簡化點云的同時保留其尖銳邊緣，但是對時間和內存的消耗很大。Benhabiles［14］等通過基于體素的聚類算法，利用曲率將點云劃分為尖銳邊緣點和簡單點，實現保留點云尖銳特征的快速精簡。陳龍［15］等提出了一種自適應K-means 聚類點云精簡算法，通過混合多判別參數法［16］提取點云數據內的尖銳點及邊界特征，然后利用自適應八叉樹提供初始化聚類中心，將曲率差大于閾值的聚類繼續迭代細分，以此保留點云的細節特征。傅思勇［17］等提出了一種基于柵格動態劃分的點云精簡方法，用柵格內點平面擬合后的平整度代替點云的微分信息來區分特征和非特征區域，再根據區域采取合適的精簡方法，以此提高精簡后模型的偏差。

然而，當前主流的點云精簡算法沒有考慮精簡后點云分布的均勻性，均勻分布的點云能夠增加點云法向量估計的準確性，提高后續處理的可靠性。同時，很多點云精簡算法沒有考慮灰度信息，而灰度信息作為點云的一種重要特征在某些實際應用中不可或缺。因此，本文針對配準后厚度和間距分布不均的點云數據，提出了一種有效的點云精簡算法。首先，利用基于體素格的方法生成一個粗點云，然后將其投影到給定的點云上，用每點領域內的近似重心點來代替原點位置。同時，加上正則化約束，摻入局部排斥力為距離過近的點增加罰項來保證點云的均勻分布，通過不動點迭代算法實現點云的重采樣。最后，利用KDTree 在初始點云內查找重采樣后點的最鄰近點，將最鄰近點的灰度信息映射至重采樣后的點。針對配準后點云數據的特點，本文算法通過以上三個步驟，獲取分布密度均勻，同時保留原始形狀及灰度特征的點云。

2 算法介紹

本算法用于解決配準后點云存在的數據冗余及厚度和間距間的不均勻分布等問題。算法利用體素柵格及重采樣步驟中關于重心點處理的相關性，將兩者結合，利用體素柵格下采樣后的數據作為LOP 算法的初始迭代點云，加快迭代速度。同時，在改善點云分布情況基礎上，可以通過控制柵格大小直接決定點云精簡的比例。算法輸入配準后的點云，輸出一個新的點集，保持原點云的形狀和灰度，同時使點云的分布密度均勻。

2.1 體素格下采樣

點云配準將從各角度獲取的點云數據轉換到相同坐標系下，由于重疊區域的存在，配準后的點云必然存在冗余的部分，為后續處理的計算增加了難度。對于給定的點集，可以利用基于體素柵格的方法進行下采樣，通過控制體素柵格的大小來決定下采樣的比例，在減少數據量的同時保持點云的形狀特征。

我們可以通過以下幾步完成體素柵格的創建及點云的下采樣。首先根據點云數據在xyz 三個方向的最大及最小坐標值計算包圍點云的最小邊界框盒，框盒的邊長定義如下：

其中，λ 是修正邊長的參量，用于保證數據包含于框盒的內部。然后將框盒劃分為若干個邊長為d的三維體素柵格，d 的選值與點云的平均密度成反比，定義如下：

其中，α 是比例因子，用于控制下采樣的比例；s 是比例系數；N 表示點云數據中點的總數。體素柵格劃分完成后，去除沒有數據點的小柵格。對于現存的小柵格，將距離重心最近的點保留，去除柵格內的其他點，以實現點云的下采樣。

采用體素柵格進行下采樣的原因如下：首先，經過體素柵格下采樣后的點云可以覆蓋原點云的整個表面，符合采樣前的幾何特征。其次，根據式（2）的變形，簡單地通過調整體素柵格d 的大小即可控制下采樣的比例，從而控制點云數據下采樣后的密度。圖1 通過經典的bunny模型展示了體素格邊長的大小對下采樣率的影響。其中，bunny 模型的Lx=0.12，Ly=0.15，Lz=0.15 ，N 約為3.6 萬。當體素邊長選擇0.002 和0.004時下采樣的比例分別為50%和10%。

圖1 不同體素大小對bunny模型的下采樣率的影響比較

2.2 點云重采樣

經過上一步的操作，可以濾除大量的冗余數據，但是點云不均勻分布的問題沒有得到很好的改善。Lipman［18］等于2007 年提出LOP 算子，將其用于點云的幾何重建。本文應用與其相似的數學機制，來解決配準后點云數據分布不均的問題。

式（4）的右邊兩項形式相似，但是表達的意義不同，第一項可以理解為每點領域內的近似重心點，使得結果對離群點及噪聲具有魯棒性；第二項是正則化約束項，通過摻入局部排斥力為距離過近的點增加罰項來保證點云的均勻分布。我們可以通過調整參數μ 的值來調整兩項間的平衡。根據經驗，通常選取μ=0.45 可以獲得較好的效果。收斂時，就是最后重采樣的結果點。

2.3 灰度映射

點云在重采樣的過程中，不動點迭代算法僅考慮了點與點之間的位置信息，因而會丟失灰度信息。由于點云重采樣的過程可以看做是對配準點云的投影，因此重采樣后的點云與配準點云位于同一坐標系下相同的空間位置。為了獲取精簡后點云的灰度信息，本文在配準點云數據內查找距離重采樣后的點最近的點，將最鄰近點的灰度信息映射到重采樣后的點上。為了加快最鄰近點的搜索速度，本文采用了一種分割k 維數據空間的數據結構KDTree，省去對大部分數據的搜索，從而減少計算量。具體步驟如下：

1）對配準點云數據構建KDTree；

2）對重采樣后點云數據內的每一點，根據歐式距離在配準后點云數據內搜索最鄰近點；

3）將最鄰近點的灰度值映射至重采樣后的點云。

3 實驗結果與分析

我們利用多種真實世界的點云數據來測試本文提出的方法，實驗結果證明我們提出的點云精簡算法的有效性。

圖2 通過水杯點云數據來展示本文提出方法的主要處理步驟。輸入的點云數據如圖（a）所示，該數據是基于結構光［19］的三維重建實驗平臺［20］獲取的多角度點云配準結果，點云數據量約為22 萬個，圖（c）用深色標注出由于配準造成的重疊區域，該部分屬于冗余數據。結合圖（c）及圖（a）的放大區域，我們可以看出點云分布不均勻，因配準造成的重疊區域的點云密度大于非重疊區域。為了獲得分布均勻且保持原有幾何和灰度特征的點云數據，首先，我們利用體素柵格對輸入數據進行簡化，選取的體素柵格的邊長為0.8mm，下采樣后的結果如圖（d）所示，下采樣后的點云數據量約為6.3 萬，該步驟在去除大量無用數據的同時保留了形狀特征。然后，我們經過一個迭代投影步驟重采樣（d）中的點云數據，通過平衡原始分布和點與點間斥力的約束，生成一個分布均勻的新點集，如圖（e）。最后，為了恢復重采樣后丟失的灰度信息，利用KDTree 在輸入點云內搜索（e）內各點的最鄰近點，并將灰度信息進行映射，最終得到的點云數據如圖（b）所示。與原始數據相比，簡化率約為71.36%，精簡后的點云保留原始的幾何特征和灰度特征。同時，根據圖（a）和圖（b）的放大部分可知，由于配準造成的重疊區域數據冗余及點云密度不均的問題得到了解決。

圖2 使用本文算法對水杯數據進行實驗得到的結果

為了說明本文方法對于點云精簡均勻性方面的優越性，我們將本文算法與文獻［11］及經典的移動最小二乘法（MLS）［21］進行對比。開源點云庫PCL 內的Surface 模塊內的模板類Moving-LeastSquares 提供了一種重采樣方法，通過對點云進行MLS映射，可以用于精簡配準后的數據。我們這里采用定量的度量規則，數據點到鄰域點距離的平均標準偏差來評價點的分布情況，表達式如下：

其中Npi表示pi點的鄰域表示點集內元素的個數，μ 表示pi與其鄰域內點距離的均值。σˉ越小表明點的分布越均勻。具體的對比結果如圖3 及表1 所示，圖（a）為機械部件點云數據模型，該數據是基于結構光的三維重建實驗平臺獲取的多角度點云配準結果，點云數據量約為46 萬，數據點到鄰域點距離的平均標準偏差為1.08mm。圖（b）、（c）、（d）分別是文獻［11］、MLS 方法和本文方法精簡后的點云模型，在簡化率均為84%左右時，通過式（5）計算可得，模型數據點到鄰域點距離的平均標準偏差分別為0.544mm、0.537mm 和0.421mm。由此可得，通過本文模型精簡后的點云較文獻［11］和MLS方法而言分布更加均勻。

圖3 機械部件點云數據實驗結果

表1 算法均勻性比較

本 文 的 實 驗 平 臺 為Intel（R）Core（TM）i7-6500U CPU@2.6GHz，8GB 內存，Windows 10，64位操作系統。表2 展示了圖2、3 中例子的統計信息。根據表2 內的結果可知，我們可以通過控制體素柵格邊長的大小來決定點云下采樣率，體素格邊長越大，點云的簡化率越高。同時，通過對比處理前后σˉ的計算結果可知，精簡后的點云分布較初始點云相比更加均勻。

表2 實驗統計結果

此外，我們還分析了精簡操作對法向量估計的影響，如圖4 所示。我們展示了原始點云的法向量結果和精簡后點云的法向量結果，法向量的計算均采用經典的加權PCA 法［9］。由于配準造成的誤差及密度分布不均等問題，計算出的法線結果在點云重疊區域存在明顯的錯誤和噪聲。這些會干擾諸如特征提取、表面重建等后續處理。而經過本文算法處理后的數據有均勻的點分布，去除了重疊區域的冗余數據，提高了法向量估計的準確性，增加了后續處理步驟的可靠性。

圖4 點云法向量估計

4 結語

在本文中，我們提出了一種有效的配準點云數據精簡算法，用于處理配準后的點云數據，解決其存在的數據量過大、點密度不均等問題，同時可以保留點云的灰度特征。本算法結合了體素柵格法與基于能量優化的LOP 算法的思想，并應用基于KDTree 的最鄰近搜索，以此來獲取保留初始點云形狀及灰度特征同時分布均勻的點集。實驗結果表明，本文的算法能夠成功應用于各類配準后點云數據的精簡。此外，它可以為常規的點云處理技術提供精確的數據點，如法向量估計，物體識別和曲面重建。