基于RANSAC的三維點云目標閾值分割算法*

涂浩文，丁 召，周 驊，趙 麒

（貴州大學大數據與信息工程學院，貴陽 550025）

1 引言

隨著現代化工業的快速發展，3D點云在計算機視覺領域得到了廣泛應用。點云是在同一空間參考系下表達目標空間分布的點集合。獲取點云的技術包括接觸式掃描儀、激光雷達、結構光、三角測距等多種。以結構光技術為原理的MEMS-3D相機，被應用在工業焊接、三維物體重建等場景。然而通過相機所獲取的三維激光點云數據，通常包含百萬級數據量，因此需要采用合適算法，去除采集到目標的三維點云中的背景。近年來，國內外學者在點云分割領域進行了深入研究。文獻[1]融合RGB圖像和三維點云數據，建立點云到像素點的映射，將邊緣點作為區域生長分割的種子點，改善了對點云的欠分割與過分割。文獻[2]提出將區域生長算法與RANSAC算法相結合的方法，提升了復雜場景的分割精確度。文獻[3]從點云法向量入手，采用點法式方程求得點云法向量來估計局部平面，利用法向量夾角作為權重迭代，提高平面分割效果。文獻[4-5]在RANSAC基礎上，利用局部徑向基函數計算點云曲率，選擇曲率最小點作為初始種子點，雖提高了點云分割的效率，但對目標細節位置不能進行有效分割。盡管目前眾多的點云分割算法已相對成熟，但應用在不同場景所發揮的效果仍存在提升空間。上述的改進研究大多依賴點云的法向量、曲率等信息，這也導致容易造成分割不足或過度分割。為克服此類弊端，在此嘗試采用一種引入高度參數分割指定閾值的RANSAC算法，對采集到的點云數據進行分析測試，改善分割模型的完整度和運行耗時。

2 點云預處理

點云濾波作為常見的點云處理方法，往往是點云處理的第一步。由于使用高分辨率相機等設備對目標進行三維點云數據采集，包含大量散列點、孤立點，在獲取點云數據時，由于設備精度、操作者經驗、環境因素帶來的影響，以及電磁波衍射特性、被測物體表面性質變化、數據拼接配準操作準確性等的影響，點云數據中將不可避免出現一些噪聲。龐大的點云數量會對后續分割工作帶來困難。

體素格濾波器[6]可以做到向下采樣的同時不破壞點云本身集合結構的效果。其原理是通過輸入的點云數據創建一個三維體素柵格，將每個柵格內的所有的點，都用這個柵格的重心點來表示，如圖1所示。圖中的立方就是一個體素柵格，其中包含多個點云數據，在運算時所有點都按重心點來算，就縮減了點云的數量。選擇距離采樣點最近的點作為最終的下采樣點[7]，對所有體素進行處理后得到過濾后的點云。

圖1 體素柵格過濾原理圖

3 RANSAC分割

RANSAC算法最早由Fischler等人[8-9]在1987年共同提出，起初是作為數據處理的算法。該算法的主要作用是在原始數據包含眾多噪聲的情況下提取出數據中符合某些特征的數據。

作為一種通過迭代的方法來從包含有離群點的數據中估計正確數學模型參數的算法，RANSAC算法的原理為：從輸入點云中隨機選出能組成數學模型的最小數目的元素使用這些元素計算出相應模型的參數，選出的元素數目是能決定模型參數的最小數目；檢查數據中得到符合第一步模型的元素，根據閾值判定元素是否為需要的內點；將這個過程重復多次，最終選出包含元素最多的模型。

RANSAC算法在空間點云中擬合平面的過程為:在點云中隨機選取三個點組成一個平面，然后計算其余點到平面的距離，根據閾值判斷其余點是否處在同一平面。如果處在同一平面的點超過一定個數，便將組成該平面的點集合保存下來并標記匹配。迭代多次后提取出擁有最大匹配點的平面，直到沒有可匹配的元素為止。

假設內點在數據中的占比為t，每次計算模型使用n個點，迭代k次并且每次都采樣到“離群點”，以此計算模型概率，采集到正確的n個點去計算正確模型的概率為：

進而可得出迭代次數：

4 高斯濾波去噪

針對采樣點周圍的噪聲和離群點對分割結果的影響，在原有RANSAC算法的基礎上，利用高斯函數經傅里葉變換后仍具有高斯函數特性的特點，令指定區域的權重為高斯分布，可將高頻噪聲點濾除。

點云高斯濾波主要原理是基于統計學方法對噪聲點進行去除，通過對點云數據和鄰域點間距統計分析后得到點云密度，依據采樣點附近的點云密度確定是否為噪聲點，若某塊的點云數據小于某密度，則將其去除。其算法流程是基于KD-Tree依次搜尋每個點云周圍的k個鄰域點，并計算出采樣點到其k個鄰域點的平均歐氏距離。

設P={pi(xi,yi,zi|i=1,2,…,n)}為原始點云數據。對其進行KD-Tree搜索后，得到的數據集為Pij={pi(xij,yij,zij|j=1,2,…,k)}。定義di為已經得到的點pi到其k個鄰域點的平均距離，di為di的均值，σ為di的標準差，則有：

點云中所有點云的距離應該構成高斯分布，給定均值和方差以達到降噪效果。

綜上所述，本算法的分割流程可歸納為：首先采用體素濾波對原始點云數據進行下采樣，保存點云形狀特征的同時減少點的數量；然后利用RANSAC算法，先擬合平面然后計算點到平面的距離，設置閾值，將點到平面的距離在閾值范圍外的點刪除；最終添加高斯濾波對分割后的點云進行去噪處理。分割的完整流程如圖2所示。

圖2 本算法分割流程圖

5 實驗與分析

實驗采用無錫微視傳感科技有限公司所研制的型號為PCA-P/S600的3D深度相機。該相機采用MEMS光柵結構光投影裝置掃描目標表面三維信息，并利用圖像恢復算法重建出物體的真實三維點云數據，具有精度高、功耗低、體積小等優點。相機實物如圖3所示。主要的相機參數如表1所示。

圖3 PCA-P/S600型MEMS 3D相機

表1 相機主要參數

本次實驗以生活中常見的公仔、讀卡器作為檢測目標，使用微軟Window系統平臺和由供應商提供的SDK連接3D相機，拍攝目標獲取密集激光點云文件。實驗裝置及現場環境如圖4所示。

圖4 實驗現場環境圖

首先從3D相機獲取未經處理的點云數據，其包含待分割目標和背景點。未經處理的原始點云有很多噪聲點。為減少計算量、提升計算效率，采用三維網格體素濾波下采樣，在保留原始點云特征信息的前提下，減少整體點云數量。圖片處理前后對比如圖5所示。

圖5 圖片點云處理效果

實驗采用PC機安裝的Ubuntu16.04操作系統，配置為酷睿i5-3470 CPU@3.20GHz、16GB內存，基于C++編程語言，使用PCL1.10.0點云庫處理點云數據。將相機采集到的原始點云數據分別采用區域生長算法、RANSAC算法、以及本算法進行實驗。三種算法生成的點云圖像效果對比如圖6所示。

圖6 點云處理效果對比

對實驗獲得數據加以歸納。采樣前后的點云數據量如表2所示，采用不同算法進行分割后得到的點云數據和使用時間如表3所示。

表2 采樣前后點云數據量

表3 不同算法分割對比實驗數據

從生成的點云圖像和表中的數據可以看出，三種算法都實現了目標的提取分割，但區域生長算法分割出的目標較為粗糙，在輸出的目標點云數據邊緣存在細小噪聲，導致整體分割效果欠佳；RANSAC在提取目標過程中速度比區域生長快，但所分割的目標結果同樣存在異常噪聲；本算法在實現點云分割過程中，有效去除了異常噪聲點，同時在運行時間上也有所提升。

6 結束語

新改進的分割算法，針對的是傳統方法在目標分割中出現效果不佳等問題。利用引入距離閾值的RANSAC算法，通過擬合平面后計算點到平面的距離，設置閾值，對閾值內外各點加以篩選，成功改善了對被測目標的分割。實驗結果表明所提方法在分割平面背景和提取目標點云特征上都有較為理想的表現，具有一定的實際應用價值。