基于DBSCAN 的改進(jìn)RANSAC 點(diǎn)云平面擬合算法

摘要：針對隨機(jī)采樣一致性（random sample consensus，RANSAC）算法對含有噪聲的點(diǎn)云數(shù)據(jù)進(jìn)行平面擬合時(shí)效果不佳和容易產(chǎn)生誤識(shí)別的問題，對算法進(jìn)行改進(jìn). 通過基于密度的噪聲應(yīng)用空間聚類（density-based spatial clustering of applications with noise，DBSCAN）算法改變RANSAC算法初始點(diǎn)集合的選擇策略，并使用主成分分析法（principal component analysis，PCA）計(jì)算點(diǎn)云各點(diǎn)法向量，以點(diǎn)到平面距離以及點(diǎn)的法向量與平面法向量夾角兩個(gè)約束條件同時(shí)作為RANSAC算法平面擬合模型內(nèi)點(diǎn)判定的準(zhǔn)則. 采用無噪聲與分別含有300個(gè)噪聲點(diǎn)和500個(gè)噪聲點(diǎn)的點(diǎn)云仿真數(shù)據(jù)進(jìn)行測試，本文算法擬合結(jié)果均接近理論值且內(nèi)點(diǎn)距離標(biāo)準(zhǔn)差分別為1.007×10-8、0.003、0.007，優(yōu)于RANSAC算法. 采用實(shí)際工件點(diǎn)云數(shù)據(jù)在兩種工況場景下進(jìn)行測試，本文算法擬合平面內(nèi)點(diǎn)比率相對于傳統(tǒng)RANSAC 算法分別提高24.7% 和24.6%，平面提取完整度及準(zhǔn)確率同樣優(yōu)于RANSAC算法. 仿真模擬及實(shí)例分析證明了本文算法的有效性.

關(guān)鍵詞：點(diǎn)云平面擬合；隨機(jī)采樣一致性；噪聲；密度聚類；主成分分析

中圖分類號：TP301.6 文獻(xiàn)標(biāo)志碼：A

隨著人工智能的不斷發(fā)展，三維空間信息的獲取與處理顯得越來越重要［1］. 點(diǎn)云數(shù)據(jù)即空間中點(diǎn)的集合，是物體幾何形狀的一種具體數(shù)字化體現(xiàn). 點(diǎn)云數(shù)據(jù)的獲取方法主要有激光測距法、結(jié)構(gòu)光法、RGB-D相機(jī)法、三維掃描法等，由于其相較二維圖像，具有可量化復(fù)雜環(huán)境［2］，提供三維空間信息的特點(diǎn)，被廣泛應(yīng)用于三維重建、增強(qiáng)和虛擬現(xiàn)實(shí)、智能導(dǎo)航等領(lǐng)域［3］. 點(diǎn)云的豐富信息為研究者提供了深入理解和模擬真實(shí)場景的機(jī)會(huì)，近年來，對點(diǎn)云數(shù)據(jù)的處理成為研究熱點(diǎn).

點(diǎn)云場景中常包含大量平面特征，故點(diǎn)云平面擬合作為一項(xiàng)基礎(chǔ)的任務(wù)，在實(shí)際應(yīng)用中意義重大.例如，在機(jī)器人導(dǎo)航與定位中，通過擬合地面點(diǎn)云平面，可以幫助機(jī)器人實(shí)現(xiàn)精準(zhǔn)的定位和路徑規(guī)劃；在無人駕駛和智能車輛領(lǐng)域，點(diǎn)云平面擬合也被廣泛應(yīng)用于道路和交通場景的建模和理解，為自動(dòng)駕駛系統(tǒng)提供重要的環(huán)境感知能力；在工業(yè)制造中，通過對工件表面進(jìn)行點(diǎn)云數(shù)據(jù)采集和平面擬合，可以實(shí)現(xiàn)對工件表面的幾何特征和質(zhì)量狀態(tài)進(jìn)行檢測和分析，為工業(yè)制造提供了高效、精準(zhǔn)的質(zhì)量控制解決方案. 綜上，由于點(diǎn)云平面擬合對于場景理解、物體識(shí)別和機(jī)器人感知等應(yīng)用起著至關(guān)重要的作用，故實(shí)現(xiàn)精準(zhǔn)的點(diǎn)云平面擬合非常必要. 點(diǎn)云平面擬合的辦法包括特征值法、最小二乘法、霍夫變換法、隨機(jī)采樣一致性（random sample consensus，RANSAC）等，其中，由于RANSAC算法較其他算法具有一定魯棒性，故應(yīng)用較廣. 但RANSAC算法的魯棒性并不是絕對的，在點(diǎn)云數(shù)據(jù)含有較多噪聲點(diǎn)時(shí)，仍然容易導(dǎo)致平面擬合精度下降. Zheng 等［4］提出了一種結(jié)合RANSAC算法和改進(jìn)特征值算法的點(diǎn)云平面擬合方法，提高了平面擬合的精度. Kang等［5］基于貝葉斯定理，使用多個(gè)初始基元并行檢測的策略優(yōu)化RANSAC 算法. Chen 等［6］采用局部采樣方法改進(jìn)RANSAC算法，在針對建筑物屋頂點(diǎn)云平面擬合提取時(shí)，有良好效果. Oehler等［7］通過霍夫變換，生成多分辨率聚類，然后再使用RANSAC算法識(shí)別擬合平面，以此提升算法準(zhǔn)確性，但霍夫變換需要耗費(fèi)較大內(nèi)存，有著較高的計(jì)算成本. Li等［8］使用正態(tài)分布變換，通過在每次循環(huán)中選取一個(gè)平面無損檢測單元作為最小樣本的方式，提高了RANSAC算法在采樣時(shí)的準(zhǔn)確度，但單元大小的選取較為復(fù)雜煩瑣. Yang等［9］采用啟發(fā)式搜索策略來構(gòu)建初始點(diǎn)集合，能較為有效地提取室內(nèi)空間環(huán)境的平面，但其內(nèi)點(diǎn)判定仍然只以距離閾值為標(biāo)準(zhǔn)，存在誤識(shí)別的可能性. 通過上述分析可知，現(xiàn)有改進(jìn)算法大多面臨著復(fù)雜的計(jì)算問題，且內(nèi)點(diǎn)判定準(zhǔn)則均較為單一，而錯(cuò)誤的內(nèi)點(diǎn)判定將對最終的擬合結(jié)果造成較大影響.

本文基于DBSCAN，在經(jīng)過預(yù)處理的點(diǎn)云數(shù)據(jù)中搜索RANSAC 平面擬合算法所需要的初始點(diǎn)集合，并使用主成分分析法計(jì)算點(diǎn)云數(shù)據(jù)中各點(diǎn)的法向量，增加法向量夾角這一約束條件，將其與點(diǎn)到平面的距離一同作為內(nèi)點(diǎn)判定準(zhǔn)則. 與其他改進(jìn)算法相比，本文算法避免了高成本的計(jì)算，方便算法后續(xù)的硬件實(shí)現(xiàn)，且完善了內(nèi)點(diǎn)判定準(zhǔn)則，進(jìn)一步降低誤識(shí)別概率. 仿真試驗(yàn)與實(shí)物實(shí)驗(yàn)分析表明，本文算法較常規(guī)RANSAC算法，具有更好的擬合效果.

1 RANSAC 算法

RANSAC算法是一種魯棒性的估計(jì)分析方法，通過不斷迭代的方式，估算擬合數(shù)據(jù)集的模型參數(shù). 使用RANSAC算法可以將數(shù)據(jù)集劃分為內(nèi)點(diǎn)（inliers）和外點(diǎn)（outliers），內(nèi)點(diǎn)即分布在所求模型上的點(diǎn)，外點(diǎn)即模型之外的點(diǎn).

RANSAC算法原理本質(zhì)上可概括如下：首先，從數(shù)據(jù)集中隨機(jī)選取最小樣本集，這個(gè)樣本集的大小通常取決于所要擬合模型的參數(shù)個(gè)數(shù)，使用所選的樣本集對模型進(jìn)行擬合，求出模型的初始參數(shù). 接著，給定一個(gè)合適的閾值，計(jì)算所有數(shù)據(jù)點(diǎn)到此前求出的擬合模型的誤差，確定數(shù)據(jù)集中所有符合模型要求的數(shù)據(jù)點(diǎn)，擬合誤差小于或等于閾值的點(diǎn)，被認(rèn)為是內(nèi)點(diǎn)，而其余點(diǎn)，則被認(rèn)為是外點(diǎn). 多次重復(fù)上述兩個(gè)步驟，選擇擁有最多內(nèi)點(diǎn)或最小內(nèi)點(diǎn)誤差的模型作為最終估計(jì).

當(dāng)RANSAC算法具體應(yīng)用到擬合空間點(diǎn)云平面時(shí)，其平面擬合示意圖如圖1所示.

基本步驟如下：

1）由于至少3個(gè)點(diǎn)才能確定一個(gè)平面，所以擬合平面時(shí)，需要從數(shù)據(jù)集中隨機(jī)選取3個(gè)點(diǎn)作為初始的最小樣本集，針對這3個(gè)點(diǎn)計(jì)算平面模型參數(shù).

2）設(shè)置合適的距離閾值dt，計(jì)算所有剩下的點(diǎn)到該平面的距離di，將符合di≤dt 的點(diǎn)視作內(nèi)點(diǎn)，將其余點(diǎn)視作外點(diǎn). 當(dāng)內(nèi)點(diǎn)數(shù)量滿足要求時(shí)，保留此平面模型.

3）繼續(xù)重復(fù)上述兩步，如果當(dāng)前模型的內(nèi)點(diǎn)數(shù)量大于此前保存的最大內(nèi)點(diǎn)數(shù)量，則更新模型參數(shù).不斷迭代，直到達(dá)到迭代閾值，將內(nèi)點(diǎn)個(gè)數(shù)最多的模型作為最終的平面模型.

2 改進(jìn)的RANSAC 算法

使用RANSAC算法進(jìn)行點(diǎn)云平面擬合時(shí)，由于對原始點(diǎn)云數(shù)據(jù)集中3個(gè)初始樣本點(diǎn)的選取完全隨機(jī)，極大增加了取到數(shù)據(jù)集中平面外的點(diǎn)的可能性，由此得到的模型參數(shù)往往無法滿足要求，當(dāng)采樣次數(shù)一定時(shí)，初始點(diǎn)選取平面外的點(diǎn)的次數(shù)越多，符合要求的模型集就越少，最后得到最優(yōu)模型的概率就越小，平面擬合的準(zhǔn)確度也將越低. 同時(shí)，RANSAC算法對內(nèi)點(diǎn)的判定僅僅以數(shù)據(jù)集中的點(diǎn)到平面模型的距離為依據(jù)，只要符合距離要求的點(diǎn)就被視為內(nèi)點(diǎn)，這也有可能導(dǎo)致誤識(shí)別. 針對以上問題，本文提出一種基于DBSCAN的改進(jìn)RANSAC算法，通過改變初始點(diǎn)的選擇策略以及內(nèi)點(diǎn)的判定方式，提高RANSAC算法的準(zhǔn)確度. 改進(jìn)RANSAC點(diǎn)云平面擬合算法流程圖如圖2所示，首先對原始點(diǎn)云進(jìn)行預(yù)處理，接著使用主成分分析法（principal componentanalysis，PCA）計(jì)算各點(diǎn)法向量［10］，通過DBSCAN 尋找RANSAC算法的初始點(diǎn)集合，在初始點(diǎn)集合中隨機(jī)選取3個(gè)點(diǎn)進(jìn)行平面擬合，將滿足點(diǎn)到平面距離閾值和點(diǎn)與擬合平面法向量角度閾值的點(diǎn)判定為內(nèi)點(diǎn)，保留內(nèi)點(diǎn)個(gè)數(shù)滿足要求的模型，迭代后選擇內(nèi)點(diǎn)個(gè)數(shù)最多的模型作為平面擬合結(jié)果.

2.1 點(diǎn)云濾波與下采樣

一般來說，3D點(diǎn)云原始數(shù)據(jù)往往包含較多的噪聲以及離群點(diǎn)，且數(shù)據(jù)量龐大，為了進(jìn)一步提高平面擬合的準(zhǔn)確度和算法效率，需要對點(diǎn)云進(jìn)行預(yù)處理.

基于統(tǒng)計(jì)學(xué)原理利用統(tǒng)計(jì)濾波去除大部分噪聲點(diǎn)［11］. 通過構(gòu)造多維二叉樹（K-dimension tree，KD）的方式，建立點(diǎn)云間的拓?fù)潢P(guān)系，并由此找到每一個(gè)點(diǎn)的k1 個(gè)近鄰點(diǎn)，即距離每一個(gè)點(diǎn)最近的k1 個(gè)點(diǎn). 計(jì)算每一個(gè)點(diǎn)與其k1 個(gè)近鄰點(diǎn)之間的平均距離，并計(jì)算這些平均距離的均值與標(biāo)準(zhǔn)差，計(jì)算方法如下：

式中：Sˉj 為點(diǎn)云中第j 個(gè)點(diǎn)與其k1 個(gè)近鄰點(diǎn)之間的平均距離；Sij 為點(diǎn)云中第j 個(gè)點(diǎn)到其第i 個(gè)近鄰點(diǎn)的距離；μ 為平均距離的均值；σ 為標(biāo)準(zhǔn)差；n 為點(diǎn)云中點(diǎn)的個(gè)數(shù). 設(shè)s 為標(biāo)準(zhǔn)差倍數(shù)，當(dāng)某個(gè)點(diǎn)與其k1 個(gè)近鄰點(diǎn)之間的平均距離在區(qū)間[ μ - sσ，μ +sσ]內(nèi)時(shí)，將此點(diǎn)保留，否則，將其視為噪聲點(diǎn)，予以剔除.

統(tǒng)計(jì)濾波示意圖如圖3所示，當(dāng)k1=3時(shí)，以圖中A 點(diǎn)與B 點(diǎn)為例，A 點(diǎn)到其距離最近的3個(gè)點(diǎn)的平均距離滿足閾值區(qū)間要求，將其保留，而B 點(diǎn)到其距離最近的3個(gè)點(diǎn)的平均距離超出要求范圍，將其視作噪聲點(diǎn)，予以剔除.

. 根據(jù)點(diǎn)云數(shù)據(jù)的坐標(biāo)，分別求出X、Y、Z 3個(gè)坐標(biāo)軸上的最大值xmax、ymax、zmax 及最小值xmin、ymin、zmin，由此計(jì)算3 個(gè)坐標(biāo)軸上的點(diǎn)云最小包圍盒邊長lx、ly、lz，計(jì)算過程如下：

由所得的點(diǎn)云最小包圍盒邊長計(jì)算體素柵格的尺寸，計(jì)算過程如下：

式中：r 為本文所設(shè)置的體素單元邊長；Dx、Dy、Dz 分別為3個(gè)坐標(biāo)軸方向上體素柵格的尺寸；符號? ? 表示向下取整. 計(jì)算點(diǎn)云中每個(gè)體素單元內(nèi)的索引編號h，計(jì)算過程如下：

對索引h 里的元素按從小到大排列，求出每一個(gè)體素單元的重心點(diǎn)，用重心點(diǎn)代替體素單元內(nèi)的所有點(diǎn)，若體素單元的重心點(diǎn)不存在，則使用體素單元內(nèi)距離重心最近的數(shù)據(jù)點(diǎn)代替重心點(diǎn). 通過使用體素降采樣，達(dá)到簡化縮小點(diǎn)云數(shù)據(jù)且保留點(diǎn)云形狀結(jié)構(gòu)特點(diǎn)的目的. 體素降采樣原理圖如圖4所示.

2.2 點(diǎn)云法向量估計(jì)

為了估計(jì)點(diǎn)云的法向量，采用基于鄰域的近似計(jì)算方法，該方法的主要思想如下.

對于點(diǎn)云中的每一個(gè)點(diǎn)，通過KD，再次搜索與其距離最近的k2 個(gè)近鄰點(diǎn)，用最小二乘法擬合這些最近鄰域點(diǎn)的局部平面，表示如下：

式中：n 為局部平面P 的單位法向量；d 為坐標(biāo)軸原點(diǎn)到局部平面P 的距離；pi 為當(dāng)前點(diǎn)局部鄰域中的第i個(gè)點(diǎn)，坐標(biāo)為（xi，yi，zi ）.

把由此擬合出的局部平面的單位法向量稱作當(dāng)前點(diǎn)的法向量［13-15］，而局部平面的單位法向量可以使用主成分分析法求得. 主成分分析法通過降低維度的思想，利用線性變換，將一組變量轉(zhuǎn)化為另一組不相關(guān)的變量，轉(zhuǎn)化后，變量總方差不變，且最大的方差在第1個(gè)分量上，稱為第1主成分，第2大的方差在第2個(gè)分量上，稱為第2主成分，以此類推. 點(diǎn)云數(shù)據(jù)的變量為坐標(biāo)的集合，通過變換，得到3個(gè)主成分. 對于點(diǎn)云中的平面，由于垂直于平面的方向，點(diǎn)云分布集中，方差最小，所以平面的第3主成分即為平面的單位法向量，如圖5所示，求解平面單位法向量的問題轉(zhuǎn)為求解平面點(diǎn)構(gòu)成的協(xié)方差矩陣最小特征值對應(yīng)的特征向量的問題.

由分析可知，局部平面P 經(jīng)過當(dāng)前點(diǎn)k2 個(gè)最近鄰域點(diǎn)的三維質(zhì)心p0（x0，y0，z0 ），其坐標(biāo)值如下：

式中：上標(biāo)T代表轉(zhuǎn)置運(yùn)算. 展開可得：

式中：Δxi = xi - x0；Δyi = yi - y0；Δzi = zi - z0. 對協(xié)方差矩陣M 進(jìn)行特征值分析，即：

M ? vj = λj ? vj，j = 0，1，2 （11）

式中：vj 為協(xié)方差矩陣的第j 個(gè)特征向量；λj 為協(xié)方差矩陣的第j 個(gè)特征值. 協(xié)方差矩陣Μ 的最小特征值所對應(yīng)的特征向量即為局部平面P 的單位法向量，即當(dāng)前點(diǎn)的法向量. 由于所求點(diǎn)的法向量通常具有二義性，所以需要指定視點(diǎn)pv 對法向量進(jìn)行定向，過程如下：

式中：ncur 為當(dāng)前點(diǎn)的法向量；pcur 為當(dāng)前點(diǎn)坐標(biāo).

2.3 DBSCAN 求初始點(diǎn)集合

DBSCAN 是一種基于密度的空間聚類算法，通過分析鄰域進(jìn)而分析樣本集的緊密程度［16-19］，參數(shù)（reps，kmin Pts ）用來描述樣本數(shù)據(jù)點(diǎn)分布的緊密情況. 其中，reps 為鄰域半徑，即當(dāng)前點(diǎn)的鄰域距離閾值，kmin Pts為鄰域半徑范圍內(nèi)數(shù)據(jù)點(diǎn)的最小個(gè)數(shù). 關(guān)于DBSCAN，有

1）核心對象：對于點(diǎn)云數(shù)據(jù)中的任意一點(diǎn)p，如果在其以reps 為鄰域半徑的鄰域范圍內(nèi)，至少包含kmin Pts個(gè)樣本點(diǎn)（包括當(dāng)前點(diǎn)自身），則稱點(diǎn)p為核心對象.

2）密度直達(dá)：如果點(diǎn)p 是核心對象，當(dāng)點(diǎn)q 位于點(diǎn)p 以reps 為鄰域半徑的鄰域范圍內(nèi)時(shí)，則稱點(diǎn)q 由點(diǎn)p 密度直達(dá).

3）密度可達(dá)：如果在點(diǎn)云樣本中，存在序列點(diǎn)p1，p2，p3，…，pm，滿足點(diǎn)pi + 1 由點(diǎn)pi 密度直達(dá)，且i =1，2，3，…，m - 1，則稱點(diǎn)pm 由點(diǎn)p1 密度可達(dá).

4）密度相連：如果對于點(diǎn)p 和點(diǎn)q，存在核心對象點(diǎn)o，使得點(diǎn)p 和點(diǎn)q 均可由點(diǎn)o 密度可達(dá)，則稱點(diǎn)p 和點(diǎn)q密度相連. 將密度相連的點(diǎn)的最大集合定義為簇.

DBSCAN示意圖如圖6所示，當(dāng)kmin Pts=5時(shí)，紅色圓點(diǎn)的鄰域半徑范圍內(nèi)的樣本點(diǎn)都至少為5個(gè)，所以紅色圓點(diǎn)都是核心對象，位于它們各自鄰域半徑范圍內(nèi)的點(diǎn)（除去它們自身），即圖6中的綠色圓點(diǎn)，都可由它們密度直達(dá). 圖6中，使用藍(lán)色箭頭連接起來的核心對象，構(gòu)成一組密度可達(dá)的核心對象樣本序列，這些樣本序列的鄰域半徑范圍內(nèi)的所有樣本點(diǎn)相互都是密度相連的，所有紅色圓點(diǎn)與綠色圓點(diǎn)構(gòu)成一個(gè)簇.

運(yùn)用DBSCAN，尋找初始點(diǎn)集合的步驟如下：在平面的密度緊密區(qū)域，根據(jù)事先設(shè)置的reps、kmin Pts，隨機(jī)選擇一個(gè)核心對象點(diǎn)，將其標(biāo)記為已處理，通過KD樹，搜索可由其密度直達(dá)的點(diǎn)，將這些點(diǎn)加入隊(duì)列，在隊(duì)列中，繼續(xù)尋找未處理的核心對象點(diǎn)，并重復(fù)上述步驟直到隊(duì)列中找不到未處理的核心對象點(diǎn)為止，由此得到的隊(duì)列集合，便構(gòu)成一個(gè)點(diǎn)云簇. 經(jīng)過DBSCAN后，得到的這個(gè)點(diǎn)云簇，由于是在平面密度緊密區(qū)域計(jì)算的密度相連點(diǎn)的最大集合，簇內(nèi)點(diǎn)為平面內(nèi)點(diǎn)的概率將大大增加，所以，這個(gè)點(diǎn)云簇便是本文所求的初始點(diǎn)集合.

2.4 平面模型擬合及內(nèi)點(diǎn)判定

在所求的初始點(diǎn)集合內(nèi)，隨機(jī)抽取3個(gè)點(diǎn)，根據(jù)這3個(gè)點(diǎn)的坐標(biāo)，計(jì)算求得平面模型參數(shù). 空間平面方程如下：

Ax + By + Cz + D = 0 （13）

式中：A、B、C 為平面單位法向量的3個(gè)坐標(biāo)分量值，即滿足A2 + B2 + C2 = 1；D 為坐標(biāo)原點(diǎn)到平面的距離. 使用點(diǎn)云數(shù)據(jù)集中余下的所有點(diǎn)對平面模型進(jìn)行驗(yàn)證.

計(jì)算所有剩余點(diǎn)到擬合平面的距離：

di = | Ax | i + Byi + Czi + D／根號下A2 + B2 + C2 =| Axi + Byi + Czi + D |（14）

設(shè)置距離閾值dt，將di gt; dt 的點(diǎn)直接歸為外點(diǎn)，對di ≤ dt 的點(diǎn)進(jìn)行進(jìn)一步判斷.

計(jì)算di ≤ dt 的點(diǎn)法向量與擬合平面的法向量夾角：

θj = arccos np ? nj／| np || nj |= arccos（np ? nj ） （15）

式中：np 為擬合平面的法向量；nj 為滿足距離要求的點(diǎn)的法向量；| np |，| nj |為法向量的模，其值均為1.

點(diǎn)與擬合平面法向量夾角如圖7所示. 理論上，平面上的點(diǎn)，其法向量與平面法向量相互平行，由此設(shè)置角度閾值α，將θj≤ α 的點(diǎn)視為內(nèi)點(diǎn). 本文算法的內(nèi)點(diǎn)判定準(zhǔn)則為：將同時(shí)滿足點(diǎn)到平面距離閾值要求和點(diǎn)與擬合平面法向量夾角閾值要求的點(diǎn)視為內(nèi)點(diǎn)，以此降低誤識(shí)別概率.

記錄內(nèi)點(diǎn)個(gè)數(shù)滿足要求的模型，重復(fù)上述步驟，直到采樣次數(shù)達(dá)到迭代次數(shù)閾值，結(jié)束迭代. 迭代結(jié)束后，從記錄的模型中選出內(nèi)點(diǎn)個(gè)數(shù)最多的平面模型作為最終平面擬合的結(jié)果.

RANSAC算法的迭代次數(shù)閾值與抽取到合格樣本概率的關(guān)系為：

ω = 1 - （1 - ε3 ）N （16）

式中：ω 為采樣過程中選取的3個(gè)初始點(diǎn)均為平面點(diǎn)的概率；ε 為從初始點(diǎn)集合中選取到一個(gè)平面點(diǎn)的概率；N 為迭代次數(shù)閾值. 由式（16）可知，本文算法相對傳統(tǒng)RANSAC算法，在經(jīng)過DBSCAN得到初始點(diǎn)集合之后，ε 將得以提高，在迭代次數(shù)閾值N 相同的情況下，選取到的3個(gè)初始點(diǎn)均為平面點(diǎn)的概率ω 也將提高，即N 相同時(shí)，本文算法的點(diǎn)云平面擬合準(zhǔn)確度優(yōu)于傳統(tǒng)RANSAC算法.

3 實(shí) 驗(yàn)

為了驗(yàn)證本文算法的效果，基于Windows10系統(tǒng)和Intel（R）Core（TM）i7 - 7700HQ CPU @ 2.80 GHz處理器，在Visual Studio2017上用C++語言進(jìn)行算法程序的編寫.

3.1 仿真分析

使用仿真數(shù)據(jù)進(jìn)行試驗(yàn)分析. 令待擬合的點(diǎn)云空間平面方程為：

含不同數(shù)量異常噪聲的仿真數(shù)據(jù)如圖8所示.使用MATLAB 軟件隨機(jī)選取待擬合點(diǎn)云平面上的1 000個(gè)點(diǎn)，如圖8（a）所示. 分別在1 000個(gè)點(diǎn)的仿真數(shù)據(jù)中任意加入300個(gè)和500個(gè)異常值作為噪聲點(diǎn)，如圖8（b）和圖8（c）所示，其中紅色點(diǎn)為待擬合平面上的點(diǎn). 分別用傳統(tǒng)RANSAC算法、最小二乘法、結(jié)合特征值的改進(jìn)RANSAC 算法（以下簡稱特征RANSAC算法）和本文算法對圖8中的各仿真數(shù)據(jù)進(jìn)行平面擬合，得到的仿真結(jié)果分別如表1、表2和表3所示，各算法對圖8（b）和圖8（c）仿真數(shù)據(jù)的平面擬合效果分別如圖9和圖10所示.

表1、表2和表3中的σd 為擬合平面的內(nèi)點(diǎn)到擬合平面的距離標(biāo)準(zhǔn)差，計(jì)算方法如下：

式中：nin 為內(nèi)點(diǎn)個(gè)數(shù)；dj 為第j 個(gè)內(nèi)點(diǎn)到擬合平面的距離. 由表1可知，當(dāng)點(diǎn)云數(shù)據(jù)中沒有異常噪聲點(diǎn)干擾時(shí)，4種算法所得的平面系數(shù)結(jié)果與設(shè)定的理論值近似相同，擬合效果都較為理想，但本文算法所得平面系數(shù)與設(shè)定的理論值最為接近，且距離標(biāo)準(zhǔn)差σd最小，所擬合的平面離散程度最低，擬合精度高于另外3種算法. 由圖9和圖10可知，當(dāng)點(diǎn)云數(shù)據(jù)中分別包含300個(gè)和500個(gè)異常噪聲點(diǎn)時(shí)，最小二乘法擬合效果均表現(xiàn)最差，特征RANSAC算法所擬合平面與理論平面上的點(diǎn)均存在一定偏離，但相比傳統(tǒng)RANSAC算法具有改進(jìn)；本文算法所擬合平面均與理論平面上的點(diǎn)最為貼合，擬合效果均表現(xiàn)最佳. 結(jié)合表2和表3可知，當(dāng)點(diǎn)云數(shù)據(jù)中含有異常噪聲點(diǎn)時(shí)，最小二乘法受干擾最為嚴(yán)重，所得平面系數(shù)與設(shè)定的理論值具有較大偏差，且噪聲點(diǎn)越多，偏差越大. 由于傳統(tǒng)RANSAC算法具有一定魯棒性，故所得結(jié)果略好于最小二乘法，但擬合結(jié)果與預(yù)測精度同樣欠佳. 特征RANSAC 算法擬合效果優(yōu)于傳統(tǒng)RANSAC算法，但所得平面系數(shù)與設(shè)定的理論值也存在一定偏差. 本文算法所得平面系數(shù)，在兩種噪聲情況下，均接近理論設(shè)定值，且距離標(biāo)準(zhǔn)差相較其他3種算法最小，擬合效果與預(yù)測精度以及算法穩(wěn)定性均優(yōu)于其他3種算法.

3.2 實(shí)例驗(yàn)證

為了更好地驗(yàn)證本文算法的效果，對實(shí)際工件點(diǎn)云進(jìn)行實(shí)驗(yàn)分析. 通過RVCX3D結(jié)構(gòu)光相機(jī)，在水平放置工件以及豎直放置工件兩種工況下，掃描并獲取帶V形槽矩形工件的點(diǎn)云數(shù)據(jù).帶V形槽的矩形工件如圖11所示.

RVCX3D 結(jié)構(gòu)光相機(jī)的測量工作距離為200～3 000 mm，Z 向精度最高可達(dá)0.005 mm，點(diǎn)云合成頻率最高可達(dá)15 Hz. 從獲取到的點(diǎn)云數(shù)據(jù)中提取工件點(diǎn)云，并進(jìn)行濾波與體素降采樣，由此得到的矩形工件點(diǎn)云如圖12所示.

分別采用傳統(tǒng)RANSAC算法、最小二乘法、特征RANSAC算法和本文算法，在兩種工況下，對工件上表面的平面點(diǎn)云進(jìn)行擬合，并利用擬合結(jié)果，分割提取平面點(diǎn)云. 工件上不屬于上表面的點(diǎn)以及工件外的點(diǎn)均為噪聲點(diǎn). 水平放置和豎直放置工件時(shí)各算法的擬合效果分別如圖13和圖14所示，分割工件上表面點(diǎn)云效果分別如圖15和圖16所示，工件上表面的擬合結(jié)果分別如表4和表5所示.

由圖13可知，在水平放置工件時(shí)，本文算法所擬合平面相較于另外3種算法，與矩形工件上表面最為貼合. 觀察圖15可知，使用4種算法對水平放置的工件上表面點(diǎn)云進(jìn)行分割時(shí)，最小二乘法丟失較多平面信息［圖15（b）］，對比圖15（a）與圖15（b）可知，傳統(tǒng)RANSAC算法分割效果優(yōu)于最小二乘法，但提取到的平面點(diǎn)云完整度欠佳. 對比圖15（a）與圖15（c）可知，特征RANSAC 算法分割效果較傳統(tǒng)RANSAC算法有所提升，但提取到的平面點(diǎn)云仍不完整，且邊緣處存在誤識(shí)別的噪聲點(diǎn). 由圖15可知，本文算法分割所得平面完整度較高，且不存在明顯誤識(shí)別噪聲點(diǎn)，分割效果優(yōu)于另外3種算法. 由表4可知，在對水平放置的帶V形槽的矩形工件上表面的平面點(diǎn)云進(jìn)行擬合時(shí)，使用本文算法得到的距離標(biāo)準(zhǔn)差為0.007，小于其他3種算法，并且內(nèi)點(diǎn)比率高于另外3 種算法，相較傳統(tǒng)RANSAC 算法提高了24.7%，相較特征RANSAC 算法提高了10.9%，且點(diǎn)云離散程度最低，平面擬合精度高于其他3種算法，所得結(jié)果與圖示結(jié)果吻合. 分析圖14和圖16以及表5可知，當(dāng)工件豎直擺放時(shí)，本文算法對工件上表面的擬合效果與分割效果和工件水平放置時(shí)所得結(jié)論一致，同樣優(yōu)于另外3 種算法. 內(nèi)點(diǎn)比率相較傳統(tǒng)RANSAC算法提高了24.6%，相較特征RANSAC算法提高了9.4%.

4 結(jié) 論

本文基于DBSCAN，改變傳統(tǒng)RANSAC 算法完全隨機(jī)的初始點(diǎn)選點(diǎn)策略，并使用PCA法計(jì)算點(diǎn)云各點(diǎn)法向量，增加法向量夾角這一內(nèi)點(diǎn)判定條件，來提高RANSAC算法擬合點(diǎn)云平面的準(zhǔn)確性. 仿真試驗(yàn)與實(shí)例分析結(jié)果均表明，本文所提算法相較傳統(tǒng)RANSAC 算法以及結(jié)合特征值的改進(jìn)RANSAC 算法，具有更為可靠的擬合效果，在點(diǎn)云平面擬合方面具有一定的實(shí)際意義. 但本文算法也存在局限性，需要人為設(shè)置法向量夾角閾值以及點(diǎn)到平面距離閾值，這將是未來需要完善以及深入研究的地方.

參考文獻(xiàn)

［1］ 李明磊，李廣云，王力，等．采用八叉樹體素生長的點(diǎn)云平面提取［J］．光學(xué)精密工程，2018，26（1）： 172-183．

LI M L，LI G Y，WANG L，et al． Planar feature extractionfrom unorganized point clouds using octree voxel-based regiongrowing［J］. Optics and Precision Engineering，2018，26（1）：172-183．（in Chinese）

［2］ 官云蘭， 程效軍， 施貴剛. 一種穩(wěn)健的點(diǎn)云數(shù)據(jù)平面擬合方法［J］．同濟(jì)大學(xué)學(xué)報(bào)（自然科學(xué)版），2008，36（7）：981-984．

GUAN Y L，CHENG X J，SHI G G．A robust method for fitting aplane to point clouds［J］． Journal of Tongji University （NaturalScience），2008，36（7）： 981-984．（in Chinese）

［3］ 李宗民，姚純純，劉玉杰，等．點(diǎn)云場景下基于結(jié)構(gòu)感知的車輛檢測［J］． 計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2021，33（3）：405-412．

LI Z M，YAO C C，LIU Y J，et al． Vehicle detection based onstructure perception in point cloud［J］． Journal of Computer-Aided Design amp; Computer Graphics，2021，33（3）：405-412．（inChinese）

［4］ ZHENG L M，WANG R D，WANG S Y，et al.Point cloud planefitting based on RANSAC and robust eigenvalue method［C］//2022IEEE 8th International Conference on Computer and Communications（ICCC）， December 9-12，2022. Chengdu，China： IEEE，2022：1368-1372．

［5］ KANG Z Z，LI Z. Primitive fitting based on the efficientmultiBaySAC algorithm［J］. PLoS One， 2015， 10（3）： e0117341．［6］ CHEN D，ZHANG L Q，MATHIOPOULOS P T，et al． Amethodology for automated segmentation and reconstruction ofurban 3-D buildings from ALS point clouds［J］．IEEE Journal ofSelected Topics in Applied Earth Observations and RemoteSensing， 2014， 7（10）： 4199-4217．

［7］ OEHLER B，STUECKLER J，WELLE J，et al． Efficient multiresolutionplane segmentation of 3D point clouds［M］//LectureNotes in Computer Science． Berlin，Heidelberg：Springer BerlinHeidelberg，2011：145-156．

［8］ LI L，YANG F，ZHU H H，et al． An improved RANSAC for 3Dpoint cloud plane segmentation based on normal distributiontransformation cells［J］．Remote Sensing，2017，9（5）：433．

［9］ YANG L N，LI Y C，LI X C，et al．Efficient plane extraction usingnormal estimation and RANSAC from 3D point cloud［J］ ．Computer Standards amp; Interfaces，2022，82：103608．

［10］ 李茂月，趙偉翔，馬康盛，等．結(jié)構(gòu)光檢測點(diǎn)云精簡與重構(gòu)參數(shù)自動(dòng)調(diào)節(jié)方法［J］．儀器儀表學(xué)報(bào)，2022，43（8）：122-130．

LI M Y，ZHAO W X，MA K S，et al． Point cloud simplificationand reconstruction parameters’ automatic adjustment method ofstructured light detection［J］． Chinese Journal of ScientificInstrument，2022，43（8）：122-130．（in Chinese）

［11］ OUYANG Q，LIN Y H，ZHANG X L，et al． Application of 3Dreconstruction technology based on an improved MC algorithm in ashotcreting robot［J］．Applied Optics，2022，61（29）：8649-8656．

［12］ SHI W J，XU J W，ZHU D C，et al． RGB-D semanticsegmentation and label-oriented voxelgrid fusion for accurate 3Dsemantic mapping［J］. IEEE Transactions on Circuits and Systemsfor Video Technology，2022，32（1）：183-197．

［13］ 尹佳琪，王世勇，李范鳴．基于改進(jìn)主成分分析的分焦平面偏振圖像去噪算法［J］．光學(xué)學(xué)報(bào)，2021，41（7）： 64-73．

YIN J Q，WANG S Y，LI F M． Division-of-focal-planepolarization image denoising algorithm based on improvedprincipal component analysis［J］． Acta Optica Sinica，2021，41（7）： 64-73．（in Chinese）

［14］ 馮林，李斌兵．一種基于最小廣義方差估計(jì)的TLS點(diǎn)云抗差法向量求解方法［J］． 武漢大學(xué)學(xué)報(bào)（信息科學(xué)版），2018，43（11）： 1647-1653．

FENG L，LI B B． A robust normal estimation method forterrestrial laser scanning point cloud based on minimumcovariance determinant［J］． Geomatics and Information Scienceof Wuhan University，2018，43（11）：1647-1653．（in Chinese）

［15］ 白創(chuàng)，陳立，閆昱．一種基于PVDAC描述子的RGB-D三維點(diǎn)云配準(zhǔn)方法［J］．湖南大學(xué)學(xué)報(bào)（自然科學(xué)版），2023，50（2）：95-101．

BAI C，CHEN L，YAN Y．A RGB-D 3D point cloud registrationmethod based on PVDAC descriptor［J］． Journal of HunanUniversity （Natural Sciences），2023，50（2）：95-101．（inChinese）

［16］ QIU Z B，MA Y，F(xiàn)AN F，et al． Improved DBSCAN for infraredcluster small target detection［J］． IEEE Geoscience and RemoteSensing Letters，2023，20：5511905．

［17］ CHOWDHURY S，NA H L，CORDEIRO DE AMORIM R．Feature weighting in DBSCAN using reverse nearest neighbours［J］.Pattern Recognition， 2023，137：109314．

［18］ ROS F，GUILLAUME S，RIAD R，et al． Detection of naturalclusters via S-DBSCAN a self-tuning version of DBSCAN［J］．Knowledge-Based Systems，2022，241：108288．

［19］ LIU Y T，ZHANG L，LI P J，et al． Laser radar data registrationalgorithm based on DBSCAN clustering［J］． Electronics，2023，12（6）：1373．

基金項(xiàng)目：國家重點(diǎn)研發(fā)計(jì)劃資助項(xiàng)目（2018YFB1308603）， National Key Research and Development Program of China（2018YFB1308603）；福建省高校產(chǎn)學(xué)合作項(xiàng)目（2022H6016），F(xiàn)ujian Province Industry Academia Cooperation Project（2022H6016）；教育部產(chǎn)學(xué)合作協(xié)同育人項(xiàng)目（231003084265411），Collaborative Education Project of the Ministry of Education（231003084265411）