基于RANSAC的三維點(diǎn)云目標(biāo)閾值分割算法*

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

（貴州大學(xué)大數(shù)據(jù)與信息工程學(xué)院，貴陽 550025）

1 引言

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

2 點(diǎn)云預(yù)處理

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

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

圖1 體素柵格過濾原理圖

3 RANSAC分割

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

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

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

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

進(jìn)而可得出迭代次數(shù)：

4 高斯濾波去噪

針對采樣點(diǎn)周圍的噪聲和離群點(diǎn)對分割結(jié)果的影響，在原有RANSAC算法的基礎(chǔ)上，利用高斯函數(shù)經(jīng)傅里葉變換后仍具有高斯函數(shù)特性的特點(diǎn)，令指定區(qū)域的權(quán)重為高斯分布，可將高頻噪聲點(diǎn)濾除。

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

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

點(diǎn)云中所有點(diǎn)云的距離應(yīng)該構(gòu)成高斯分布，給定均值和方差以達(dá)到降噪效果。

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

圖2 本算法分割流程圖

5 實(shí)驗(yàn)與分析

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

圖3 PCA-P/S600型MEMS 3D相機(jī)

表1 相機(jī)主要參數(shù)

本次實(shí)驗(yàn)以生活中常見的公仔、讀卡器作為檢測目標(biāo)，使用微軟Window系統(tǒng)平臺和由供應(yīng)商提供的SDK連接3D相機(jī)，拍攝目標(biāo)獲取密集激光點(diǎn)云文件。實(shí)驗(yàn)裝置及現(xiàn)場環(huán)境如圖4所示。

圖4 實(shí)驗(yàn)現(xiàn)場環(huán)境圖

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

圖5 圖片點(diǎn)云處理效果

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

圖6 點(diǎn)云處理效果對比

對實(shí)驗(yàn)獲得數(shù)據(jù)加以歸納。采樣前后的點(diǎn)云數(shù)據(jù)量如表2所示，采用不同算法進(jìn)行分割后得到的點(diǎn)云數(shù)據(jù)和使用時(shí)間如表3所示。

表2 采樣前后點(diǎn)云數(shù)據(jù)量

表3 不同算法分割對比實(shí)驗(yàn)數(shù)據(jù)

從生成的點(diǎn)云圖像和表中的數(shù)據(jù)可以看出，三種算法都實(shí)現(xiàn)了目標(biāo)的提取分割，但區(qū)域生長算法分割出的目標(biāo)較為粗糙，在輸出的目標(biāo)點(diǎn)云數(shù)據(jù)邊緣存在細(xì)小噪聲，導(dǎo)致整體分割效果欠佳；RANSAC在提取目標(biāo)過程中速度比區(qū)域生長快，但所分割的目標(biāo)結(jié)果同樣存在異常噪聲；本算法在實(shí)現(xiàn)點(diǎn)云分割過程中，有效去除了異常噪聲點(diǎn)，同時(shí)在運(yùn)行時(shí)間上也有所提升。

6 結(jié)束語

新改進(jìn)的分割算法，針對的是傳統(tǒng)方法在目標(biāo)分割中出現(xiàn)效果不佳等問題。利用引入距離閾值的RANSAC算法，通過擬合平面后計(jì)算點(diǎn)到平面的距離，設(shè)置閾值，對閾值內(nèi)外各點(diǎn)加以篩選，成功改善了對被測目標(biāo)的分割。實(shí)驗(yàn)結(jié)果表明所提方法在分割平面背景和提取目標(biāo)點(diǎn)云特征上都有較為理想的表現(xiàn)，具有一定的實(shí)際應(yīng)用價(jià)值。