散亂點云的圓柱提取和擬合

周 穎 林 意

(江南大學人工智能與計算機學院 江蘇 無錫 214122)

0 引 言

隨著激光掃描設備在各個領域的應用,人們可以用較低的成本快速獲取物體表面的三維坐標,其中對圓柱點云擬合的應用是工業(yè)上比較常見的問題。圓柱擬合在工業(yè)上的應用包括特征提取[1]、對象識別[2]、自主導航[3]、幾何質量檢測[4]、施工測試[5]等。目前,研究人員對圓柱擬合做了一系列的研究,解決了工業(yè)上的一些難題。常用的圓柱擬合方法歸納起來有:遺傳算法[6]、高斯圖法[7]、坐標轉換[8]、圓度判別法[9]等。這些方法原理復雜、計算量大。對此,張益澤等[10]提出了任意初值的圓柱擬合方法,通過對傳統(tǒng)的誤差方程進行改進,減少了各參數之間的關聯,在方程中賦予任意初值,利用附有條件方程的間接平差求解圓柱參數;劉支亮等[11]在文獻[10]的基礎上,提出了自適應調整權陣的穩(wěn)健加權總體算法,以3倍準差為閾值,剔除粗差,構建穩(wěn)健的最小二乘擬合算法。迭代計算對初值的要求很高,研究人員對迭代初值做了進一步的改進:Wu等[12]通過協(xié)方差估計點云的法向量,再根據最小二乘法來估計軸線方向向量;申旭等[13]提出了三點共線法求得直線方向向量,把直線方向向量作為初始值代入誤差方程迭代求解。此外,Paláncz等[14]利用期望最大化和最大似然估計來尋找高斯混合分布情況下的圓柱參數;Al-Subaihi[15]提出了一種基于最小化正交平方距離和最小的圓柱擬合方法,即最小化點到圓柱的正交距離,并用梯度下降法求解;梁雪等[16]研究了一種一邊擬合一邊去噪的方法來獲取圓柱參數,先隨機選取一定量的點,根據圓柱面的方程擬合圓柱,再選取一個閾值,把每一個點代入方程,計算的結果與閾值相比較,若小于閾值,則為內點,否則為噪聲點。以上算法大部分都需要迭代計算,計算量大,計算時間長,然而迭代對初始值的要求很高,容易陷入局部最優(yōu)陷阱,對計算結果產生影響。

在工業(yè)測量中,受到場地和儀器的限制,很難采集到規(guī)則的沒有噪聲的點云。由于采集到的點云是雜亂的,不能對初始點云直接進行圓柱擬合,因此,本文先對點云進行預處理,采用統(tǒng)計濾波消除噪聲點,然后用體素濾波器進行降采樣[17],得到數目較少且沒有噪聲的點云。接下來通過區(qū)域生長算法對點云進行分割,提取分割后的圓柱點云,再進行圓柱面擬合。圓柱面可以看作是一組到定直線的距離為定值的點的集合,這一特征表明了圓柱需要7個參數來唯一確定,這7個參數分別是圓柱中心軸線的方向向量(a,b,c)、中心軸線上一點(x0,y0,z0),以及圓柱面的半徑r,如圖1所示,計算點到直線的距離,列出誤差方程,利用奇異值分解求出軸線方向向量,再通過旋轉,使得軸線與z軸平行,將點云平行投影到xoy平面,把三維問題轉換為了二維平面問題,再根據最小二乘原理擬合圓求出半徑。本文方法理論簡單,易于實現,而且避免了迭代計算。

1 點云預處理

1.1 統(tǒng)計濾波器

1.2 體素降采樣

密集的點云在進行分割和特征提取的時候會增加計算難度和計算時間,用體素濾波器進行降采樣能在減少點云數量的同時不改變點云的幾何結構。體素是一個三維空間的小立方體,在進行降采樣時,體素內所有的點用它們的重心來近似表示,最后,所有體素的重心組成濾波后的點云。如圖2所示,圖2(a)為創(chuàng)建的體積為l×l×l的包圍盒,圖2(b)為降采樣后的用體素重心表示的點云。體素邊長l的大小控制著采樣率,當l過小,采樣后的點云仍然密集,效果不明顯;當l過大,采樣后的點云過于稀疏,導致局部特征丟失。

(a) (b)圖2 體素降采樣示例

1.3 圓柱提取

點云分割有聚類分割[18]、區(qū)域生長[16]、RANSA方法分割[19]和語義分割[20]等,本節(jié)采用區(qū)域生長算法對點云進行分割從而提取圓柱。區(qū)域生成算法的基本思想是將具有相同特征的點加入到同一區(qū)域,本文的相同特征是指兩個點云的法向量的夾角小于設置的平滑閾值。設一組點云數據為P={P1,P2,…,Pn},區(qū)域生成具體步驟包括種子點的選取、生長準則、終止條件。種子點選取的是曲率值最小的點,即最平滑的點。具體步驟如下:

(1) 對點Pi用kd_tree查找其鄰域。kd_tree是一種帶有約束條件的二叉查找樹,每一級都在當前維度上劃分開所有的節(jié)點,每個節(jié)點都表示一個超平面。kd_tree的示例如圖3所示。

圖3 kd_tree示例

(2) 設Ci為Pi的k個鄰域點構成的協(xié)方差矩陣,則有:

假設求得式(3)的特征值滿足λi1≤λi2≤λi3,對應的特征向量為vi1、vi2、vi3,則最小特征值λi1對應的特征向量vi1即為Pi的法向量,鄰域曲率[21]為:

鄰域曲率反映了該點的鄰域所構成的曲面的彎曲程度,σi越小表明曲面越平坦越接近平面。計算出每一點的鄰域曲率σi,對σi進行排序,選擇σi最小的點作為種子點。

(3) 在進行區(qū)域生長的時候,計算鄰域點與種子點的法向量之間的夾角,若夾角小于設置的平滑閾值,則把該鄰域點加入到當前區(qū)域。

(4) 當所有滿足條件的點都被合并到當前區(qū)域之后,在沒有被合并的點中選擇曲率最小的點作為種子點,返回第(3)步。終止條件是所有點都被合并。

(5) 點云分割完成之后,直接把圓柱點云提取出來即可。

2 圓柱擬合

2.1 直線擬合

設圓柱中心軸線所在的直線為L,L的方向向量為(a,b,c),對L的方向向量進行歸一化處理,得到a2+b2+c2=1。設L上某一點的坐標為(x0,y0,z0),則L的標準式方程為:

把式(5)寫成參數方程為:

式中:t為參數變量。則L可以表示為:

L=v0+Dt

(7)

式中:v0=(x0,y0,z0)T;D=(a,b,c)T。

圖4 點到直線的距離

建立目標方程:

式中:n為測量點的個數。

首先,求初始值v0。對v0求導并令其導數為零:

故:

又有:

因此:

即證明了L過測量點的重心。

把式(9)展開用點的坐標表示:

(a(xi-x0)+b(yi-y0)+c(zi-z0))2]

(15)

對各測量點去重心:

式(15)變形為:

對各參數求導并令其為0,變換成矩陣形式為:

對矩陣進行特征值分解,最大特征值對應的特征向量即為L的方向向量。

2.2 半徑擬合

旋轉點云使L與z軸平行,再將點云投影到xoy平面上,如圖5所示,將三維問題轉換為二維問題,再利用最小二乘原理擬合圓。

圖5 擬合半徑

首先將點云繞x軸旋轉θ角度,使L與yoz平面平行,旋轉矩陣為R1:

其中:

再將點云繞y軸旋轉β角度,使L與z軸平行,旋轉矩陣為R2:

其中:

設點云的半徑為r,圓心坐標為(xa,ya),根據最小二乘原理寫出誤差方程:

對各參數求導并等于0,令:

變換為矩陣形式為:

(26)

解方程求出圓心坐標(xa,ya),代入求導公式中,求出r,再通過反坐標變換求出在圓柱上的圓心點。

3 實例與分析

為驗證本方法的有效性,采用三維掃描儀對桌面進行掃描,對得到的數據進行處理,可視化如圖6(a)所示。按照第2節(jié)提到的方法,首先對初始點云點云進行統(tǒng)計濾波去噪,本文選擇的鄰域點個數是100,標準差倍數是0.8,去噪后的點云如圖6(b)所示,數目為130 251,可以看出,原始點云中的噪聲點基本已去除,靠近圓柱邊緣的點還存在小部分,在進行區(qū)域生長的時候會剔除掉。為了縮短后續(xù)區(qū)域分割的時間和提高圓柱擬合的效率,接下來對點云進行降采樣,降低點云的密度。設置體素邊長為0.03 m時,點云數目為18 428,如圖7(a)所示,可以很明顯地看到點云密度降低了,并且保留了點云的形狀特征;設置體素邊長為0.06 m時,點云數目為5 237,如圖7(b)所示,點云更加稀疏,且形狀特征沒有發(fā)生變化。本文選用邊長為0.06 m的體素進行降采樣。

(a) 原始點云 (b) 去噪后的點云圖6 點云濾波去噪

(a) 體素邊長0.03 m(b) 體素邊長0.06 m圖7 不同邊長的體素對點云進行降采樣

在進行區(qū)域生長分割時,根據實際情況選擇合適的曲率閾值和平滑閾值,本文中設置的平滑閾值為0.05π,曲率閾值為0.01,將點云分割成平面、圓柱和邊緣噪聲點,再通過設置最小簇類數目將噪聲點剔除,分割完成之后,把圓柱點云提取出來,如圖8所示。

圖8 提取出來的圓柱點云

提取出圓柱點云之后,按照本文方法對圓柱進行擬合,求出的軸線方向向量為(0.025 31,-0.999 67,-0.005),擬合半徑r=0.762 87 m,圓柱的軸線方程可以表示為:

式中:t為參數變量。

平面圓的圓度是指點到圓心的距離與半徑之差,同理擴展到三維空間,圓柱的圓度[4]是指圓柱面上的點到中心軸線的距離與半徑之差,計算結果如表1所示,圖9為圓度折線。對圓度進行統(tǒng)計,圓度均值為-0.01 mm,標準差為0.45 mm。

表1 部分觀測點的圓度值

圖9 圓度折線

為了進一步驗證本文方法的正確性和有效性,采用文獻[4]中的算法和數據進行圓柱擬合,本文算法中的(x0,y0,z0)與文獻[4]中的(x0,y0,z0)都表示軸線上一點,但是意義不同,所以沒有可比較性,只需要比較另外四個參數值即可。表2是本文方法與文獻[6]和文獻[10]中方法的比較,圖10是三種方法的圓度比較,可以看出,三種方法的差異是比較小的,且本文方法的圓度標準差略小,說明了本文方法的正確性。

表2 與文獻[6]和文獻[10]結果對比

圖10 圓度對比

4 結 語

本文介紹了從散亂點云中提取圓柱點云并進行圓柱擬合的一種方法。本文方法首先用統(tǒng)計濾波器和體素濾波器對點云進行預處理,然后采用區(qū)域生長算法對點云進行分割,得到擬合算法需要的數據,然后利用點到直線的距離建立方程,求出軸線,然后通過旋轉和投影,將三維問題轉換為二維平面問題,最后利用最小二乘法擬合出半徑。本文方法原理簡單,便于實現,而且具有很好的精度,最大的特點是避免了迭代。通過實驗分析和比較,證明了本文方法的有效性和正確性。

在用濾波統(tǒng)計器進行去噪的時候,鄰域點的個數和標準差倍數的選取對結果是有直接影響的,這里值得進一步研究。