改進(jìn)的RANSAC 點(diǎn)云分割算法及其應(yīng)用

鄒 鵬，李蓓智，龔菊賢，楊建國

（1.東華大學(xué)機(jī)械工程學(xué)院，上海 松江 201620；2.上海航天設(shè)備制造有限公司，上海 閔行 200240）

1 引言

工件復(fù)雜型面的精確修磨是現(xiàn)代制造最常見的一種技術(shù)。三維激光掃描技術(shù)是二十世紀(jì)九十年代中期發(fā)展起來的一項(xiàng)高新技術(shù)，激光測(cè)量具有準(zhǔn)直性好、精度高、測(cè)量快速等特點(diǎn)。利用三維掃描儀獲取物體表面的三維坐標(biāo)信息為快速建立物體三維影像模型及精密測(cè)量提供了一種全新的技術(shù)手段[1]。在點(diǎn)云模型特征提取中點(diǎn)云特征分割是點(diǎn)云數(shù)據(jù)處理的關(guān)鍵步驟，點(diǎn)云模型分割依據(jù)空間結(jié)構(gòu)、紋理特征等對(duì)點(diǎn)云進(jìn)行分類，使得同一區(qū)域的點(diǎn)擁有相似的特征[2]。為后續(xù)利用點(diǎn)云分割模型確定型面特征幾何信息奠定基礎(chǔ)。

目前針對(duì)點(diǎn)云數(shù)據(jù)主要分割方法主要有以下幾類：區(qū)域增長法，聚類分割算法和隨機(jī)采樣一致性（RANSAC）算法等。區(qū)域增長算法基本思想是從點(diǎn)云中隨機(jī)選取一個(gè)種子，然后根據(jù)點(diǎn)云法向量夾角將種子周圍鄰域的點(diǎn)云歸為一類。該方法但對(duì)種子初選位置要求較高，區(qū)域增長過程中易受噪聲點(diǎn)影響[3]。聚類分割算法是多元統(tǒng)計(jì)學(xué)方法的一種，將點(diǎn)云數(shù)據(jù)看作具有一定關(guān)聯(lián)屬性的多維度數(shù)據(jù)集合。按照相同屬性對(duì)點(diǎn)云數(shù)據(jù)進(jìn)行聚類分割。該方法參數(shù)設(shè)置靈活、魯棒性好，但存在收斂速度慢效率低[4]。RANSAC 算法能夠抑制點(diǎn)云噪聲對(duì)特征分割的影響，且迭代計(jì)算效率較高[5]。但仍然還存在不足之處，對(duì)于含有較多干擾點(diǎn)的原始點(diǎn)云數(shù)據(jù)，每次隨機(jī)選擇初始樣本子集易受噪聲影響，或者無法找到足夠的點(diǎn)支撐樣本子集而被拋棄。針對(duì)傳統(tǒng)RANSAC 算法不足提出了改進(jìn)的RANSAC，首先對(duì)點(diǎn)云數(shù)據(jù)進(jìn)行濾波去除離散點(diǎn)，然后利用點(diǎn)云間歐式距離閾值進(jìn)行粗略分區(qū)，最后利用RANSAC 算法對(duì)工件型面點(diǎn)云數(shù)據(jù)進(jìn)行特征提取，工程運(yùn)用證明了以上算法的有效性。

2 隨機(jī)采樣一致性算法模型

隨機(jī)采樣一致性算法（RANSAC）最早由Fishier 和Bolles 于1982 年提出[6]，利用隨機(jī)采樣一致性算法分割點(diǎn)云是通過隨機(jī)取樣剔除局外點(diǎn)，構(gòu)建一個(gè)僅由局內(nèi)點(diǎn)數(shù)據(jù)組成的點(diǎn)集。其分割原理是：對(duì)輸入的點(diǎn)云數(shù)據(jù)隨機(jī)選取點(diǎn)集計(jì)算預(yù)設(shè)的判別模型參數(shù)，計(jì)算點(diǎn)集中所有的點(diǎn)到該模型的距離是否在閾值之內(nèi)，以此作為局內(nèi)點(diǎn)和局外點(diǎn)判別準(zhǔn)則，保存當(dāng)前模型系數(shù)將局內(nèi)點(diǎn)作為分割結(jié)果輸出。要求在保證一定置信度下，基本子集最小抽樣數(shù)M 與至少取得一個(gè)良性取樣子集的概率P（P＞ε）滿足如下關(guān)系：

式中：ε—局內(nèi)點(diǎn)與數(shù)據(jù)點(diǎn)集的比值；m—計(jì)算模型參數(shù)需要的最小數(shù)據(jù)量；P 值一般取值為（0.9～0.99）。

3 改進(jìn)RANSAC 算法的點(diǎn)云分割

3.1 初始化點(diǎn)云分區(qū)

攝影測(cè)量、三維激光掃描儀等設(shè)備獲取的點(diǎn)云數(shù)據(jù)量龐大、呈現(xiàn)無規(guī)律散亂分布，并且點(diǎn)云間無任何幾何拓補(bǔ)關(guān)系。因此，有必要建立點(diǎn)云間的拓補(bǔ)關(guān)系實(shí)現(xiàn)海量點(diǎn)云高效組織與管理。八叉樹是一種自頂而下逐級(jí)劃分空間的索引結(jié)構(gòu)[7-8]。利用八叉樹結(jié)構(gòu)對(duì)點(diǎn)云進(jìn)行體元剖分，首先依據(jù)點(diǎn)云空間模型的最小包絡(luò)立方體確立八叉樹根節(jié)點(diǎn)，然后將八叉樹根節(jié)點(diǎn)沿X、Y、Z 方向進(jìn)行等分，將立方體剖分為8個(gè)小立方體作為根節(jié)點(diǎn)的子節(jié)點(diǎn)。對(duì)所有節(jié)點(diǎn)及所包含的點(diǎn)集進(jìn)行遞歸細(xì)分，直到立方體邊長小于規(guī)定的閾值時(shí)停止剖分[9]。八叉樹剖分邏輯圖，如圖1 所示。通過建立的八叉樹數(shù)據(jù)結(jié)構(gòu)，對(duì)點(diǎn)云進(jìn)行K 鄰域搜索，計(jì)算每個(gè)點(diǎn)與K 鄰近點(diǎn)的間歐式距離R，將點(diǎn)距小于預(yù)設(shè)閾R0值的分為一類，進(jìn)行點(diǎn)云初步分割。

圖1 八叉樹剖分圖Fig.1 Octree Tree Split Diagram

3.2 分割模型判別準(zhǔn)則

主要針對(duì)激光掃描獲取工件表面點(diǎn)云模型進(jìn)行平面分割，在同一平面上的點(diǎn)滿足如下平面模型參數(shù)方程ρ：

式中：點(diǎn)（x，y，z）—點(diǎn)云空間坐標(biāo)；（A，B，C）—平面單位法向量，且A2+B2+C2=1；D—坐標(biāo)原點(diǎn)到平面的距離。從原始點(diǎn)云數(shù)據(jù)中分割型面，實(shí)則是求不同點(diǎn)云面片的平面參數(shù)。

建立好平面模型參數(shù)方程后，判別準(zhǔn)則的設(shè)計(jì)至關(guān)重要，這里評(píng)定方法為計(jì)算點(diǎn)集中P（x，y，z）到平面的距離為：

理論上，局內(nèi)點(diǎn)到平面的距離為零，但是三維掃描儀獲取的點(diǎn)云數(shù)據(jù)無規(guī)則、分布不均勻，并不完全處在同一平面。平面模型是具有一定厚度點(diǎn)云的擬合面片，設(shè)定點(diǎn)到平面模型距離閾值為τ。當(dāng)距離d 小于閾值τ 時(shí)稱為局內(nèi)點(diǎn)，反之為局外點(diǎn)。設(shè)置合理的閾值對(duì)點(diǎn)云平面分割具有重要影響，閾值τ 過大會(huì)導(dǎo)致平面分割不完全，閾值τ 過小會(huì)導(dǎo)致過度分割。閾值的選取需要根據(jù)激光掃描儀精度，采集點(diǎn)云數(shù)據(jù)空間波動(dòng)情況合理選取。

3.3 點(diǎn)云分割結(jié)果優(yōu)化

考慮到距離閾值選取會(huì)影響分割效果，可能造成位于同一點(diǎn)云面片區(qū)域過度分割為多個(gè)小區(qū)域。為保證表面特征的完整性，需要對(duì)分割后的點(diǎn)云進(jìn)行合并。首先計(jì)算兩模型平面上點(diǎn)P1、P2的法向量[10]按式（4）計(jì)算兩平面的夾角，然后按式（5）計(jì)算兩模型平面的距離，若小于一定閾值θ0就合并兩個(gè)平面區(qū)域。

3.4 改進(jìn)的算法流程

改進(jìn)RANSAC 算法的關(guān)鍵環(huán)節(jié)在于對(duì)點(diǎn)云數(shù)據(jù)集進(jìn)行平面分割提取時(shí)，利用八叉樹管理點(diǎn)云數(shù)據(jù)，然后從點(diǎn)集中提取出含局內(nèi)點(diǎn)較多的平面，通過不斷迭代直至提取出工件所有型面同時(shí)利用閾值判斷對(duì)分割結(jié)果進(jìn)行優(yōu)化，具體流程，如圖2 所示。

圖2 改進(jìn)的點(diǎn)云特征提取流程Fig.2 Improved Point Cloud Feature Extraction Proces

步驟如下：

（1）確定最小抽樣數(shù)M；

（2）點(diǎn)云八叉樹結(jié)構(gòu)建立及距離閾值判別；

（3）利用式（2）確立平面模型參數(shù)；

（4）對(duì)每個(gè)聚類中所有點(diǎn)利用式（3）計(jì)算距離d 并與閾值τ進(jìn)行比較，進(jìn)行局內(nèi)點(diǎn)與局外點(diǎn)判別；

（5）重復(fù)步驟（2）和步驟（3），選取分割出局內(nèi)點(diǎn)數(shù)最多的點(diǎn)集確定平面模型最優(yōu)模型參數(shù)；

（6）運(yùn)用式（4）與式（5）計(jì)算面片之間的法向夾角與距離，若小于閾值說明為過度分割，需要將這兩個(gè)面合并為同一平面。

4 點(diǎn)云分割算法實(shí)現(xiàn)

4.1 工程應(yīng)用環(huán)境

主要通過對(duì)DMG-ecoMill 635v 機(jī)床加工的上表面呈階梯狀的鋁制工件進(jìn)行激光點(diǎn)云數(shù)據(jù)采集，激光掃描設(shè)備采用加拿大LMI Gocator2330，每條輪廓包含 1280 數(shù)據(jù)點(diǎn)，Z 向分辨率（0.006～0.014）mm，視野（47～85）mm。軟件開發(fā)基于QT 編程平臺(tái)下，利用PCL 點(diǎn)云庫處理點(diǎn)云數(shù)據(jù)并提取鋁塊凹槽面。工件樣件，如圖3所示。工件點(diǎn)云模型，如圖4 所示。

圖3 待測(cè)工件Fig.3 Workpiece to be Tested

圖4 工件點(diǎn)云模型Fig.4 Workpiece Point Cloud Model

4.2 點(diǎn)云面片提取

4.2.1 點(diǎn)云濾波與精簡

獲取的點(diǎn)云數(shù)據(jù)包含1142183 個(gè)點(diǎn)，由于原始點(diǎn)云數(shù)據(jù)中包含有離群點(diǎn)和噪聲且數(shù)據(jù)量較大需對(duì)點(diǎn)云數(shù)據(jù)進(jìn)行濾波和數(shù)據(jù)精簡，以提高計(jì)算效率和平面提取的精確度[11-12]。首先使用統(tǒng)計(jì)濾波方法（StatisticalOutlierRemoval）移除離群點(diǎn)，然后通過體素濾波（VoxelGrid）算法對(duì)點(diǎn)云數(shù)據(jù)進(jìn)行三維體素柵格濾波[13]。其主要原理是：創(chuàng)建一個(gè)三維體素柵格，用每個(gè)柵格體素重心替代柵格內(nèi)其它點(diǎn)，以達(dá)到在保證點(diǎn)云形狀特征不變的條件下縮減點(diǎn)云數(shù)據(jù)量?？s減后的點(diǎn)云包含435521 個(gè)點(diǎn)，如圖5 所示。

圖5 點(diǎn)云模型濾波去噪Fig.5 Point Cloud Model Filtering Denoising

4.2.2 面片分割提取

工程應(yīng)用中，由于激光掃描儀獲取的點(diǎn)云點(diǎn)距約為0.042mm，可設(shè)置初始點(diǎn)云分區(qū)歐式距離閾值R0=0.06mm。隨機(jī)選取600 個(gè)點(diǎn)，點(diǎn)云Z 向坐標(biāo)波動(dòng)，如圖6 所示。由于受環(huán)境光照、信噪等影響，Z 軸最大波動(dòng)量約為0.1mm，可設(shè)置點(diǎn)到平面的距離閾值τ=0.05mm。由于銑床加工工件行成面與面之間的位置關(guān)系為平行與垂直，設(shè)定θ0=8°，分割出的面與面之間的閾值Δd=0.08mm。

圖6 點(diǎn)云平面Z 向波動(dòng)Fig.6 Point Cloud Plane Z-Direction Fluctuation

工件型面分割結(jié)果，如圖7 所示。利用這里方法能夠成功分離出工件凹槽上表面與下表面，且分割的點(diǎn)云平面質(zhì)量較好，點(diǎn)云邊界辨識(shí)度高且噪點(diǎn)少，有利于后續(xù)點(diǎn)云邊界特征曲線擬合及尺寸計(jì)算。工件凹槽幾何尺寸測(cè)量結(jié)果，如表1 所示。

圖7 分割后點(diǎn)云型面特征Fig.7 Point Cloud Surface Feature After Segmentation

表1 工件凹槽幾何尺寸測(cè)量結(jié)果Tab.1 Workpiece Groove Geometry Measurement Results

用0 級(jí)標(biāo)準(zhǔn)量塊對(duì)激光掃描儀進(jìn)行標(biāo)定可以確定掃描儀的精度為±10μm。通過點(diǎn)云數(shù)據(jù)獲得的槽幾何尺寸偏差大約為0.07mm 滿足工件加工要求。

5 結(jié)論

（1）利用改進(jìn)的RANSAC 點(diǎn)云平面分割方法，在一定的置信概下能夠較好的分割出凹槽上表面與下表面，通過對(duì)分離出的點(diǎn)云面片進(jìn)行法線和距離判定防止點(diǎn)云面片過度分割。

（2）算法設(shè)定的條件下對(duì)分割的點(diǎn)云平面進(jìn)行特征尺寸計(jì)算，獲取的尺寸信息在工件加工誤差范圍內(nèi)，說明這里算法處理點(diǎn)云數(shù)據(jù)精度滿足工程應(yīng)用，驗(yàn)證了算法的有效性。