點云模型特征面分割與識別方法

袁小翠,陳華偉

(1.南昌工程學(xué)院 江西省精密驅(qū)動與控制重點實驗室,南昌 330099; 2.貴州師范大學(xué) 機(jī)電工程學(xué)院,貴陽 550025)

0 概述

在逆向工程應(yīng)用領(lǐng)域,重建的產(chǎn)品外形比較復(fù)雜,由多個連續(xù)性或種類不同的特征面按照不同的拼接條件構(gòu)成,如平面、球面、圓柱面和過渡面。對一些復(fù)雜曲面，單純用一種幾何模型去擬合得到的擬合曲面準(zhǔn)確性差。在對產(chǎn)品的CAD模型重構(gòu)之前,一般需要將復(fù)雜產(chǎn)品的不連續(xù)曲面分割成若干個連續(xù)曲面,準(zhǔn)確識別每個特征曲面的類型后對不同的曲面分別建模,再將這些曲面拼接以構(gòu)成完整產(chǎn)品。因此,點云模型特征面分割與識別是曲面準(zhǔn)確重建的基礎(chǔ)。

散亂點云數(shù)據(jù)分割主要分為基于三角網(wǎng)格模型和基于散亂點云的數(shù)據(jù)分割方法[1]。基于三角網(wǎng)格模型分割需要對點云進(jìn)行曲面重建,然而三維點云曲面重建比較耗時,基于點云的數(shù)據(jù)分割直接對點云模型進(jìn)行分割,不需要對曲面進(jìn)行重建,吸引了越來越多的關(guān)注。目前,點云數(shù)據(jù)分割方法可以歸納為3類,分別是基于邊界檢測、區(qū)域增長和聚類的分割算法[2]?；谶吔绲姆指罘椒ㄖ饕ㄟ^查找點云模型的不同特征面的過渡邊界,對邊界線擬合從而將一個復(fù)雜曲面劃分為多個獨立的特征面。文獻(xiàn)[3]通過提取點云的幾何屬性值如法向量和曲率等,將點云的法向量映射到高斯球上,不同連續(xù)曲面映射到高斯球上的不同區(qū)域,同一片連續(xù)曲面映射到高斯球上的同一片區(qū)域,再根據(jù)邊界線的區(qū)域分割出如二次曲面、拉伸面和直紋面等特征曲面。基于區(qū)域生長的模型分割方法的關(guān)鍵在于種子點的選取和生長規(guī)則,通過選定種子點,按照一定的生長規(guī)則將滿足條件點合并在同一區(qū)域中。比如:文獻(xiàn)[4]采用區(qū)域生成算法對LiDAR點云提取建筑物和植被區(qū)域,且取得了滿意的結(jié)果;文獻(xiàn)[5]計算每個采樣點的法向量,然后根據(jù)點云法向量檢測出點云模型中平滑區(qū)域,利用區(qū)域增長法對點云模型進(jìn)行分割，與基于區(qū)域增長的分割算法相比,聚類方法并不需要初始化種子點和設(shè)計生長規(guī)則,其關(guān)鍵在于確定點云聚類模式;文獻(xiàn)[6]采用K-means聚類法對三維點云模型進(jìn)行分割,但是該方法的缺點在于聚類中心初始化和K值的確定;文獻(xiàn)[7]基于3D活動輪廓模型對點云進(jìn)行分割,通過提取模型的輪廓,將點云數(shù)據(jù)模型分割成若個干不同的區(qū)域;文獻(xiàn)[8]利用譜聚類算法對點云數(shù)據(jù)分塊,根據(jù)歸一化的非對稱Laplacian矩陣構(gòu)造譜聚類空間,通過特征精簡,在更低維的空間中進(jìn)行點云分割。

目前雖然已有不少點云數(shù)據(jù)分割的方法,但許多點云處理專業(yè)軟件，如Geomagic和Imageware,都不能實現(xiàn)完全點云自動分割,只能通過手動和算法相結(jié)合的方法實現(xiàn)數(shù)據(jù)分塊,模型分割和特征面識別速度和準(zhǔn)確性有待改進(jìn)。為此,本文在準(zhǔn)確估算點云法矢的基礎(chǔ)上采用高次曲面估算點云曲率,并根據(jù)平均曲率和高斯曲率將點云劃分為8種類型,通過引入二維圖像處理的連通區(qū)域標(biāo)記法對同種類型的點云數(shù)據(jù)進(jìn)行分割,并根據(jù)概率統(tǒng)計法和點云曲率特性,識別連通區(qū)域特征面點云的所屬特征曲面類型。

1 點云模型特征面

1.1 微分信息估算

1.1.1 法向量估算

法向量是點云的重要屬性之一,點云法向量的有效估計是點云分割的基礎(chǔ)。點云法向估計方法可分為局部鄰域擬合法和Voronoi/Dalaunay方法兩類[9]。局部鄰域擬合法在點云法向量估算中應(yīng)用比較廣泛,由文獻(xiàn)[10]提出,稱之為主成分分析法,該方法能快速有效地估算光滑曲面的法向量,但當(dāng)曲面包含尖銳特征時估算的法向量不準(zhǔn)確。一般來說產(chǎn)品的CAD模型是由多個基面組成的復(fù)雜模型,在多個基面交界的區(qū)域(特征區(qū)域)主成分分析方法估算的法矢被平滑,為了更準(zhǔn)確地估算點云法向量,研究人員提出了許多改進(jìn)方法[11-13]。其中,文獻(xiàn)[11]所提方法能快速、準(zhǔn)確地估算包含尖銳特征復(fù)雜模型的點云法矢,且參數(shù)具有自適應(yīng)性,無需人工設(shè)置參數(shù)。本文采用文獻(xiàn)[11]的方法進(jìn)行法矢估計。

給定點集X={x1,x2,…,xN},其中,N為點云總數(shù),任意一點xi的最近k鄰域表示為Nb(xi),文獻(xiàn)[11]對點xi的k鄰域擬合的平面表示為:

(1)

wr(ri)=exp(-(ri/σr)2),wn(ni)=exp(-‖ni-nj‖/σn2)和wn(xi)=exp(-‖xi-xj‖/σd2)分別為鄰域點對當(dāng)前點的殘差、法向偏差和距離高斯權(quán)重,σd、σr和σn分別是距離、殘差和法矢偏差帶寬,用來控制各鄰域點對當(dāng)前點作用的大小。式(1)可以轉(zhuǎn)化為對式(2)中半正定協(xié)方差矩陣C進(jìn)行特征值分解。

(2)

C可以分解為3個特征向量v2、v1和v0,3個特征向量對應(yīng)的特征值分別是λ2,λ1,λ0,其中,λ2≥λ1≥λ0。最小特征值對應(yīng)的特征向量為平面的法向量,即點xi的法向量ni=v0。

通過分解式(2)得到的法向量方向不一致,為了后續(xù)計算需要,把各點的法向量方向調(diào)整為一致方向。本文采用最小成本路徑傳播方法進(jìn)行法矢方向調(diào)整[10]。圖1是2種不同模型法矢估算和方向調(diào)整的結(jié)果,參數(shù)t=5,圖中估算的法矢與相應(yīng)局部面近似垂直。

圖1 2種不同模型散亂點云法向量估算結(jié)果

1.1.2 離散點云曲率估算

通過法矢計算和方向調(diào)整,獲得了比較準(zhǔn)確的法矢。以法矢為鄰域曲面的局部支撐,即可通過鄰域構(gòu)造離散點的局部參數(shù)化曲面,從而對離散點估算其曲面特性參數(shù)。

設(shè)待擬合鄰域曲面為z(u,v),通過Tylor級數(shù)展開,去掉高階無窮小,即可獲得近似曲面表達(dá)式:

z(u,v)=TA,d(u,v)+O(d+1)

(3)

本文構(gòu)造4次曲面估算點云曲率,曲面Tylor表達(dá)式為:

z(u,v) ≈TA,4(u,v) =

A0,0+ (A1,0u+A0,1v) +

(A2,0u2+2A1,1uv+A0,2v2)/2 +

(A3,0u3+3A2,1u2v+3A1,2uv2+A0,3v3)/6+

(A4,0u4+4A3,1u3v+6A2,2u2v2+

4A1,3uv3+A0,4v4)/24

(4)

引入新的矢量表達(dá)式:

P= (1,u,v,u2,uv,v2,u3,u2v,uv2,v3,u4,u3v,u2v2,uv3,v4)

則4次參數(shù)曲面可表示為如式(5)所示的矩陣形式。

PTQ=Z

(5)

其中,矩陣P中的u,v值為局部坐標(biāo)系下的(u,v)參數(shù),Q為待定系數(shù)Ak-i,i構(gòu)成的矩陣,Z為局部坐標(biāo)系下的z坐標(biāo)值。將點及其鄰域點的坐標(biāo)(ui,vi,zi)代入矩陣方程即可求出所有待定系數(shù)Ak-i,i。

求解曲面基本參數(shù)E、F、G和L、M、N,并構(gòu)造Weingarten曲率矩陣W[14]:

(6)

Weingarten矩陣的特征值就是主曲率k1、k2,特征向量就是主曲率方向,由k1、k2直接求高斯曲率K和平均曲率H。

曲率推導(dǎo)過程中,平均曲率H與法矢向量正相關(guān),因而其符號與法矢方向正相關(guān)。法矢實際是由曲率主方向叉乘而來,如果曲率在法矢方向調(diào)整之前就已計算,則在法矢方向調(diào)整后,曲率方向和符號也要進(jìn)行相應(yīng)調(diào)整。如圖2所示,法矢n反向后,對應(yīng)最小主曲率k1和最大主曲率k2應(yīng)反向互換。由H=(k1+k2)/2關(guān)系式可知,平均曲率H也要變號,由關(guān)系式K=k1×k2知,在k1和k2均變號的情況下,高斯曲率K不變號。

圖2 曲率方向調(diào)整示意圖

采用二次曲面法計算各點曲率,曲面坐標(biāo)系在點的k鄰域局部構(gòu)建,各點之間的坐標(biāo)構(gòu)建相對獨立,因而計算結(jié)果中的曲率值標(biāo)準(zhǔn)并不統(tǒng)一。根據(jù)點云分割需要,需對各曲率參數(shù)H、K、k1、k2進(jìn)行歸一化。同一物體的點云分割應(yīng)采用同一判斷標(biāo)準(zhǔn),采用曲率法對點所屬曲面類型進(jìn)行判斷,還涉及曲率零值和符號的確定問題,因而必須事先對所有點的曲率做全局歸一化處理,并保證曲率在零值附近的分布規(guī)律不變。對此,本文采用零值對齊的歸一化方法,從而保證了曲率數(shù)值符號的不變性。圖3所示為4種歸一化情況,其中M和m分別為曲率最大值和最小值,y為任一點曲率,不同情況的曲率歸一化方法如下:

1)如果M>m>0,則置最大曲率為1,最小曲率為m/M,其他點的曲率按y=y/M計算。

2)如果M>0,m<0,M>abs(m),處理方法同第1種情況。

3)如果M>0,m<0,M

4)如果m

圖3 不同情況曲率歸一化示意圖

1.2 特征面的分割與識別

1.2.1 點云初始聚類

基于離散點的高斯曲率K和平均曲率H,可以將點附近的曲面形狀劃分為峰、阱、脊、谷、鞍形脊、鞍形谷、平面和極小曲面8種類型,如表1所示。據(jù)此可將點云劃分為8種類型,實現(xiàn)點云的初始聚類。

表1 曲面分類

高斯曲率由最小和最大主曲率乘積而得,會引入高階誤差,一般采用平均曲率作為上述劃分的依據(jù)。在曲率歸一化處理的前提下,根據(jù)表1的判斷條件即可確定點所屬面域特征。此時,曲率零值的設(shè)定將對曲面類型劃分結(jié)果產(chǎn)生較大影響,本文處理方法是預(yù)設(shè)極小值e作為零值。經(jīng)實驗測定,推薦平均曲率H的零值閾值為[0.001,0.005],一般可預(yù)設(shè)eH=0.005,高斯曲率K的零值可按eK=eH/4設(shè)定,并將這2個閾值參數(shù)作為用戶輸入?yún)?shù),便于調(diào)整。

1.2.2 點云連通區(qū)域分割

點云的初始聚類只是將所有離散點歸屬至8種曲率類型,但是同種類型的點云可能分屬于不同的模型表面,如圖4所示,黑色點集和白色點集都屬于平面類型點,但是分別位于不同的面片,2個平面點集之間并不連通。因而,需要對同一種類型的點判斷其連通性,將不連通的區(qū)域分割出來,實現(xiàn)點云的特征面分割。

圖4 同種類型點云不連通情況示意圖

從初始點云的角度看,2個分離區(qū)域必然存在鄰域不連續(xù)的點,同一連通區(qū)域(局部相鄰)內(nèi)的點必定是全局相鄰的。本文將二維圖像處理中連通區(qū)域標(biāo)記理論引入至三維點云區(qū)域分割[15],對三維點云連通性進(jìn)行判斷。

連通區(qū)域識別步驟如下:

1)當(dāng)前點xi加入當(dāng)前連通區(qū)域Ccidx_cur。

2)采用上述判斷條件,對xi的局部鄰域點xj進(jìn)行全局連通性判斷。

3)如果兩者全局相鄰,則判斷xj是否已追加至其他連通區(qū)域Ccidx_merge,如果是則合并Ccidx_cur和Ccidx_merge。

4)否則,將xj加入當(dāng)前連通區(qū)域Ccidx_cur。

經(jīng)過連通區(qū)域分割后同種類型的面被分割成不同的塊,需對各塊點云進(jìn)行特征面識別。

1.2.3 分塊點云的曲面類型識別

CAD模型一般由規(guī)則型面組成,例如平面、圓柱面等規(guī)則特征曲面用于安裝面、孔、倒角等加工特征,逆向工程中的特征面識別也主要是針對此類規(guī)則面。經(jīng)過連通區(qū)域分析,已經(jīng)獲得分片點云,可以進(jìn)一步展開典型造型面(平面、球面、圓柱面等)的類型判斷。從統(tǒng)計角度上看,經(jīng)分塊后的點集同屬一個曲面類型。因此,本文采用數(shù)學(xué)統(tǒng)計法對分塊點云所屬曲面類型進(jìn)行判斷,對區(qū)域點集中的點逐一判斷其所屬曲面類型,統(tǒng)計該區(qū)域中屬于不同曲面類型的點的數(shù)目,將最大數(shù)目對應(yīng)的曲面類型作為整個區(qū)域的曲面類型。

設(shè)xj為連通點云數(shù)據(jù)塊X2∈X1中的任一點,Ti(i=0,1,2)對應(yīng)平面、球面、圓柱面3類基本造型面,根據(jù)曲率條件,將點xj存入相應(yīng)的類型數(shù)組Ti。3種特征面的判斷條件如下:

1)平面:xj的最小曲率和最大曲率均等于0,即k1=k2=0,亦即K=H=0。如果過濾掉曲率突變點,則法矢夾角法更為直觀,可優(yōu)先識別平面。

2)圓柱面:xj的最小曲率等于0,最大曲率為常數(shù),即k1=0,k2=C,亦即K=0,H=C。

3)球面:xj的最小曲率和最大曲率相等,即k1=k2=C=1/R,亦即K=1/R2,H=1/R(R為球半徑)。

考慮到計算和浮點誤差,在實際程序處理中,需對零值和兩值是否相等的判斷做特殊處理,預(yù)設(shè)極小值e,對零值和兩值是否相等分別使用x

基于概率統(tǒng)計的曲面類型判斷算法步驟如下:

1)對數(shù)據(jù)塊X2中各點曲率做統(tǒng)計分析,獲得曲率參數(shù)H、K、k1、k2的平均值和方差。

2)遍歷X2中的所有點,按照點云所屬曲面類型判斷方法,將點劃分至Ti。

3)統(tǒng)計Ti中的點數(shù)Ni,比值Ni/N即為當(dāng)前區(qū)域?qū)儆诿骖愋蚷的概率pi。

4)按標(biāo)準(zhǔn)正態(tài)分布3σ原則預(yù)設(shè)概率閾值pT(pT=0.68)。如果pi>pT,則認(rèn)定當(dāng)前聚類屬于曲面類型i,返回曲面類型參數(shù)i。

2 實驗與結(jié)果分析

使用VS2008和OpenGL開發(fā)平臺,在Windows 10下分步實現(xiàn)了上述算法,并使用多種模型驗證算法的有效性。實驗所用的計算機(jī)的配置為CPU Intel Core i3 3.4 GHz,內(nèi)存8 GB。

實驗結(jié)果如表2、圖5～圖9所示。其中,在表2中,N為模型點云數(shù)量,面特征列第一個數(shù)字表示特征面類型(1-平面,2-圓柱面,3-球面),括號內(nèi)的數(shù)字為該類型面的數(shù)目,r、eH分別表示曲率突變比例、平均曲率零值閾值。表中識別率表示算法對模型特征面所屬曲面類型識別的正確率,是當(dāng)前模型中正確識別的面片與總面片數(shù)的比值。圖5～圖9分別是模型1～模型5幾種不同模型的分割和特征面識別結(jié)果。在計算參數(shù)中,模型2選用了較低的r值,是為了避免將部分圓柱面點納入突變點,模型4選用較高的r值,以將前端溝槽處的棱線納入突變點。此外,各模型的eH取值范圍在[0.001,0.005]都能取得較好的分割效果。在接下來的點云識別計算中,規(guī)則模型1～模型3無過渡面,型面曲面類型全部正確識別,識別率達(dá)到100%,模型4除了過渡面之外全部正確識別,總體識別率達(dá)到95%,模型5除了過渡面未識別之外,其他面域識別均是正確的,主要型面的曲面類型識別率大于90%。面面相交實驗顯示,模型1～模型4的交線全部正確提取,模型5提取了主要平面與圓柱,以及圓柱與圓柱交線(相貫線)。此外,從計算效率來看,點云數(shù)量在50 000以下的模型各節(jié)點耗時都在0.65 s以內(nèi)。

表2 參數(shù)設(shè)置及實驗結(jié)果

圖5 模型1點云分割與特征面識別結(jié)果

圖6 模型2點云分割與特征面識別結(jié)果

圖7 模型3點云分割與特征面識別結(jié)果

圖8 模型4點云分割與特征面識別結(jié)果

圖9 模型5點云分割與特征面識別結(jié)果

3 結(jié)束語

本文提出基于連通區(qū)域標(biāo)記和統(tǒng)計法的散亂點云特征面分割與識別方法,在準(zhǔn)確估算點云法矢的基礎(chǔ)上,以估算的法矢作為4次曲面曲率局部坐標(biāo)系的坐標(biāo)軸。根據(jù)點云的曲率特性分析曲面的型面并進(jìn)行點云預(yù)分割,引入二維圖像處理中的連通區(qū)域標(biāo)記法對點云連通區(qū)域分割,并采用統(tǒng)計法對點云所屬特征類型面進(jìn)行判斷。實驗結(jié)果表明，該方法能夠取得較好的點云分割和識別效果。