基于區域分割的多視角點云精簡算法

梁正友，黃思捷，孫 宇，李軒昂

(1.廣西大學 計算機與電子信息學院，廣西 南寧 530004；2.廣西多媒體通信與網絡技術重點實驗室，廣西 南寧 530004)

0 引 言

由于微軟推出的體感設備Kinect V2在三維重建領域當中的點云信息采集上表現出操作簡單、易上手、價格廉價等優點[1]，受到了許多研究者的關注。Kinect V2獲取點云的數量非常龐大，平均每秒能夠獲取數以千計的點。這些點云不僅密度大，而且包含了許多重復點和冗余點。如果不對點云進行精簡，這些多余的點云會占用大量的存儲空間，直接進行曲面重建必定會浪費大量時間和計算資源[2]。因此，研究開發有效的點云精簡算法可有效地減少點云占用存儲空間，提高運算效率。

已經有不少學者研究開發各種點云精簡算法。唐澤宇等[3]提出一種基于加權最小二乘法曲率計算的點云精簡算法，能夠有效提升曲率計算的準確度，避免了孔洞現象。金露等[4]在利用自適應柵格法對點云進行精簡的基礎上，將ICP算法和RANSAC算法相結合，同時提高了點云配準精度和精簡的效率。賀一波等[5]提出了一種基于k均值(k-means)聚類的點云精簡方法，能較好地保留點云的細節特征，并且與原始數據的稠密稀疏分布更加一致。曹爽等[6]針對工業構件點云提出了基于曲面變化的點云精簡算法，通過計算點的曲率將點云分成特征不同的多個區域，并且在每一個區域設定閾值，為每個不同的特征區域計算其精簡比率，由精簡比率定義閾值完成精簡。陳達梟等人[7]利用包圍盒子把點云劃分成若干個子空間，利用每個子空間獲取K鄰域點集的擬合平面，根據擬合平面距離，把每個子空間分為保留區和刪除區，最后根據精簡率對刪除區內的點云進行精簡。Nallig Leal等[8]提出了一種基于點云局部密度估計的點云精簡方法，使用期望最大化算法對點云密度分布進行聚類，識別高曲率點作為非去除的點，最后采用線性規劃對去除點進行精簡。Yuan Xiaocui等[9]采用K均值聚類算法對點云進行全局聚類，隨后利用K-d樹的節點作為初始聚類中心，并且使聚類中心映射到高斯球，最后利用自適應均值漂移算法對高斯球中的數據進行精簡；Han Huiyan等[10]利用邊緣點比非邊緣點具有更強的幾何特征，區分邊緣點和非邊緣點并且保留邊緣點，對于非邊緣點利用歐幾里得距離的平均值來判定該點是否需要去除，來完成點云精簡。Whelan T等[11]提出了一種漸開線點云圖的增量平面分割方法和一種有效的平面曲面三角剖析方法來進行點云的精簡；Qi Junkun等[12]利用圖的光譜處理，判別出點云上不規則的點，提出基于圖濾波器點云精簡公式，對不規則的點進行精簡；Xuan Wei等[13]提出了一種簡化點云的新方法，該方法使用基于法向角的局部熵來評價該點是否為除去對象。Ji Chunyang等[14]提出一種細節特征點簡化算法。該算法設置k鄰域搜索規則以確保找到的點最接近樣本要點，對測量點的進行重要性評估，然后使用八叉樹結構來簡化剩余的點。該方法不僅可以簡化點云，同時對簡化目標點云的窄輪廓也有很好的效果。Li Haoyong等[15]提出了一種基于法向量標準差的點云快速簡化算法。該算法對下采樣后的稠密點云數據計算正態分布，通過相鄰點之間的法向夾角計算特征點與另一特征點之間的分離閾值，在特征點與其他特征點之間再逐步進行下采樣，實現點云的自適應簡化。該算法在短時間內實現了點云模型的有效簡化，很好地保持了原模型的特點和形狀。

盡管目前點云精簡算法研究取得了非常好的進展，但還有較大的提升空間。在對一個建模物體進行多視角采集點云的場景下，由于不同視角的兩個相鄰點云擁有局部重疊區域，在配準之后，使得重疊區域點云密度過大，出現占用過多的存儲空間和降低計算機效率等問題。針對這些問題，該文提出一種多視角點云精簡算法，對擁有局部重疊區域的多視角點云序列，使用包圍盒子提取兩個相鄰點云的重疊區域內的點云，將它們分割成重疊區域點云和非重疊區域點云。隨后提出一個分組隨機精簡算法對重疊區域內的點云進行精簡。對所有的重疊區域點云精簡之后，與非重疊區域點云再合并成一個整體點云，根據精簡率的要求在對整體點云進行一次精簡。對提出的精簡算法和基于包圍盒子精簡算法[16]進行實驗對比，分別使用基于包圍盒子的精簡算法和該文提出的精簡算法對原始點云在75%、50%、25%精簡率的實驗條件下進行對比。實驗結果表明，在相同的精簡率下，與基于包圍盒子的精簡算法相比，該文提出的點云精簡算法更能減少對目標物體點云細節的破壞，最大程度上保留目標物體的點云細節和特征。

1 提出的精簡算法

本節包括三個小節。第1.1節介紹基于包圍盒子的重疊區域內點云提取方法，用于將多視角點云分割成重疊區域和非重疊區域，以便對密度不同的區域進行不同的精簡。第1.2節提出一種基于分組的點云隨機精簡算法，對點云按一定的規則進行排序，然后按等點數量進行均勻分組，對每個分組精簡同樣數量的點。該算法能克服信息精簡分布不一致的問題，較好地保留點云的細節。第1.3節提出多視角點云精簡算法，使用包圍盒子重疊區域內點云提取方法將多視角點云分割成重疊區域點云和非重疊區域點云。隨后用分組隨機精簡算法對重疊區域內的點云進行精簡。對所有的重疊區域點云精簡之后，與非重疊區域點云再合并成一個整體點云，根據精簡率的要求再對整體點云進行一次精簡。

1.1 基于包圍盒子的重疊區域點云的提取

對有局部重疊區域的兩個點云A和B，如圖1所示，左邊矩形是點云A的包圍盒子，右邊矩形是點云B的包圍盒子，兩矩形相交形成的小矩形是點云A和點云B的重疊部分。

重疊區域點云提取算法步驟如下：

圖1 重復區域點云提取

(1)

1.2 基于分組隨機精簡法

基于包圍盒子的精簡算法[14]是一種均勻的精簡方法，它將點云空間均勻劃分成等大小的子包圍盒子，每個子包圍盒子僅保留一個中心點并去除子包圍盒子領域內的其他點。但是，Kinect V2采集到建模物體的點云并不是均勻分布在空間內的，有些區域的點非常稠密，而有些區域的點比較稀疏。因此，使用包圍盒子點云精簡算法會把點云空間均勻劃分成等大小的子包圍盒子，這會導致在每個區域內的點數量分布不一致，點會大量集中在某幾個子包圍盒子內，其他子包圍盒子只有少量點甚至沒有點；造成有些地方精簡過多，有些地方精簡過少，使得精簡效果不好。針對這些缺點，該文提出了基于分組隨機精簡算法。首先，對點云按一定的規則進行排序，然后按等點數量進行均勻分組，對每個分組精簡同樣數量的點。該算法能克服信息精簡分布不一致的問題，較好地保留點云的細節，具體描述如下。

在Kinect V2的世界坐標中，建模對象的寬度維度為x軸，深度維度為z軸，高度維度為y軸。為保留建模對象的細節，采用在y軸上的點以y坐標值從高到低排序的方式，讓無序點云變成有序點云。

由于是均勻分組，保證每一組點云精簡的數量是一定的。合適大小的分組能確保在隨機去除點的情況下，不會造成在某一區域過度精簡而導致空洞的出現，能最大程度地保留建模對象的點云細節和特征。

1.3 多視角點云精簡算法流程

對有局部重疊區域的多視角點云，重疊區域是稠密區域，而非重疊區域是稀疏區域。為了使得這些稠密區域被精簡多一點，稀疏區域被精簡少一點，首先對重疊區域進行一次精簡，然后對包括重疊區域在內的整體點云再精簡一次。每次精簡的程度用精簡率進行衡量。設原始點云D包含點數量為N，經過精簡后得到的點云Dl包。Dl含的點數量為M，則精簡率r定義為：

(2)

對有局部重疊區域的多視角點云精簡的總體思路是：對0°到180°內的多視角點云配準后，對兩個鄰接點云用1.1節方法提取重疊區域。然后，用1.2節提出的精簡方法對重疊區域進行精簡。得到的新點云在和鄰接的點云繼續采用1.1節方法提取重復區，并用1.2節提出的精簡方法對重復區域進行精簡。重復直到所有的重疊區域都被精簡了。然后對整體點云再進行一次精簡，以達到要求的精簡率。形式化描述如下：

/*多視角點云精簡算法*/

BEGIN

步驟一：

For(j=0;j

{

(2)Ej=Ej-Fj,j+1;Ej+1=Ej+1-Fj,j+1/*將重疊區域中的點云去掉*/

}

步驟二：D=D∪Ej；/*將最后的點云歸到整體點云中*/

步驟三：用1.2節提出的分組隨機精簡方法以精簡率r對整體D進行精簡，使精簡率到達要求。

END //算法結束

算法相關說明如下：

(1)算法第(2)步：等式Ej=Ej-Fj,j+1，Ej+1=Ej+1-Fj,j+1將重疊區域中的點云去掉，在下一輪中參與操作的Ej+1要將已經精簡過的部分排除出去，目的是防止在下一輪精簡時不再對已經精簡過的部分再次精簡，避免過度精簡，保持整體點云精簡率的一致性。

(3)步驟二中等式D=D∪Ej是將排除了重疊區域點云的最后點云Ej并入整體中。

多視角點云精簡算法的計算過程可用圖2進行示例說明。圖2(9)是待精簡的三個有重疊區域的多視角點云。在算法的循環第一輪，首先對E1和E2進行處理；第(1)和(2)步首先將E1和E2點云分割為三個區域：重疊區域點云F2和非重疊區域點云F1、F3，如圖2(2)所示。對重疊區域點云F2進行精簡得D2，將F1和D2并到整體點云中(圖2(3))。在算法的循環第二輪，對F3和E3進行同樣處理，得到F4、F5、F6點云(圖2(5))，將它們并到整體點云中，形成了精簡了重疊區域的整體點云(圖2(8))。最后對圖2(8)點云再進行一次精簡，使精簡率達到要求。

圖2 算法樣例

2 實驗結果與分析

2.1 數據采集與預處理

使用Kinect V2作為深度數據采集的設備，Kinect V2的深度攝像頭適用于室內弱光的環境，所以該文選擇在白天關閉照明的室內進行深度信息采集。在程序實現時，采用VS2015作為編譯環境，并且使用PCL點云庫和OpenCV作為第三方編程庫。所有程序代碼在PCL點云庫基礎上進行算法改進，采用C++實現，運行于Windows 10 64位系統，Inter(R)Core(TM)i7 - 7700HQ CPU@2.80 GHz處理器、8G內存的筆記本電腦上。圖3為Kinect拍攝場景和采集對象水果籃子、打印機。

圖3 采集對象和場景

圖3中該文使用的圓盒高3厘米、直徑10厘米。Kinect V2放置在高6厘米上的矩形石塊上，圓盒距離Kinect V2 23厘米。建模物體水果籃子高5厘米、長軸15厘米、短軸11厘米。建模物體打印機長17厘米、寬7厘米、高5厘米。

以水果籃子為例，該文使用Kinect V2對建模物體分別從正面、左側60°、右側60°三個視角進行采集，圖4中的A、B、C為Kinect V2采集到的原始點云。隨后要對原始點云進行預處理，去除離群點。采用PCL點云庫中RadiusOutlierRemoval濾波器對點云去除離群點。圖4中的D、E、F，在原始點云預處理之后，使用ICP算法[17]把正面、左側60°、右側60°的3片點云配準成一個整體后除去下面的圓盒點云。圖4中的G、H、I為配準成一個整體點云的正面、左側、右側視圖。

圖4 點云采集和處理

2.2 實驗結果分析

分別使用基于包圍盒子的精簡算法和該文提出的精簡算法對原始點云進行對比實驗。共進行三次對比實驗。基于包圍盒子的精簡算法每次只對整體點云精簡一次，精簡率分別為75%、50%、25%。而文中算法每次實驗是以精簡率rc對先重疊區域進行精簡和再以精簡率r對整體點云D進行精簡；在實驗中，通過調整(r,rc)使三次實驗總精簡率分別為75%、50%、25%。在本實驗中，當(r,rc)的值為(r=80%,rc=93%)、(r=75%,rc=70%)、(r=40%,rc=60%)時，文中算法總的精簡率分別達到75%、50%、25%，并且精簡效果最好，結果如圖5所示。

圖5 基于包圍盒子點云精簡算法和文中算法精簡效果對比 (列為精簡率(%)，行為精簡算法和視圖分布)

從圖5可以看到：

(1)在75%精簡率下，基于包圍盒子的精簡算法效果圖的正面視圖跟文中算法正面視圖相比，可以明顯看到基于包圍盒子的精簡算法讓原始點云的表面變得平滑，并且達到正面視圖25%左右的面積。在相同的位置下原始點云圖片可以明顯看到紋理細節的起伏，而文中算法相比原始點云，只是點云整體變“薄”了，但紋理起伏還是非常明顯的。

(2)在50%精簡率下，基于包圍盒子的精簡算法正面視圖將近一半的面積變得平滑，而文中算法還能看到更多的紋理細節，僅比精簡率75%的點云厚度更加“薄”一些。在左側視圖中，基于包圍盒子的精簡算法中，視圖中間部分的“空洞”開始被填補上，“空洞”已經變小。而相同的位置，文中算法還能明顯看到“空洞”的存在。

(3)在25%的精簡率下，基于包圍盒子的精簡算法中的平滑部分已經擴散到整個點云，從正面視圖、右側視圖，左側視圖中已經完全看不到任何紋理細節，并且由于包圍盒子設置過大，導致點與點之間的空隙非常大。文中算法由于缺少足夠點云的支撐，也開始慢慢出現空洞，但是從正面視圖還可以看到紋理細節起伏。

圖6是用兩種精簡算法對打印機點云進行精簡的效果圖。實驗中，參數(r,rc)取值與前面一樣。從圖6可以看出，基于包圍盒子的精簡算法和文中精簡算法精簡的效果差別不大。由于這次實驗對象為打印機，由于打印機的紋理呈現規則規律變化并且表面紋理變化不大。相比于圖5對水果籃子作為實驗對象來說，使用文中精簡算法和基于包圍盒子的精簡算法對打印機在相同精簡率情況下精簡效果差別不大。

圖6 基于包圍盒子點云精簡算法和文中算法精簡效果對比(列為精簡率(%)，行為精簡算法和視圖分布)

綜上所述，可以看到：

(1)基于包圍盒子的精簡算法對分布不均勻的點云，尤其是由多個多視角點云配準而成的組合點云，無法有效地保持紋理和輪廓等細節，因為該算法在精簡過程中不考慮點云的分布情況，而文中算法對這種類型的點云能有效地保持紋理和輪廓等細節，因為該算法通過排序和分組，在一定程度上按點云分布進行精簡，點云密集的地方多刪一些，分布少的地方少刪一些。

(2)從縱向來看，精簡率越低，保留下來的點云數量就越少，占用的存儲空間也就越少，能節省大量曲面重建的時間和計算資源，但是細節丟失的也多。

(3)從上述兩個實驗可知，文中算法對于擁有紋理呈現不規則并且變化幅度較大的精簡對象，在一定精簡率的情況下，能更好地保留精簡對象的紋理細節。

3 結束語

該文提出一種面向局部重疊區域的多點云序列的多視角點云精簡算法。使用包圍盒子提取多點云序列中兩個相鄰點云的重疊區域內的點云，將它們劃分成重疊區域點云和非重疊區域點云；用一個分組隨機精簡算法對重疊區域內的點云進行精簡。對所有的重疊區域點云精簡之后，與非重疊區域點云再合并成一個整體點云，根據精簡率的要求再對整體點云進行一次精簡。對文中精簡算法和基于包圍盒子的精簡算法進行實驗對比。實驗結果表明，在相同的精簡率下，文中精簡算法比基于包圍盒子的精簡算法更能減少對目標物體點云的細節破壞，最大程度上保留目標物體的點云細節和特征。下一步，將工作重點放在點云精簡過后的曲面重建問題上，并開發一個包含點云采集、點云預處理、點云配準、點云精簡、曲面重建等功能的實時快速三維重建系統。