陳華偉 袁小翠 吳祿慎

1(南昌大學(xué)機電工程學(xué)院 江西 南昌 330031) 2(南昌工程學(xué)院機械與電氣學(xué)院 江西 南昌 330099)

散亂點云特征面擬合與求交算法

陳華偉1袁小翠2*吳祿慎1

1(南昌大學(xué)機電工程學(xué)院 江西 南昌 330031)2(南昌工程學(xué)院機械與電氣學(xué)院 江西 南昌 330099)

逆向建模的主要目標就是通過曲面重構(gòu)，向CAD輸入NURBS等曲面模型。曲率是曲面的基本信息，采用二次曲面法估算點云曲率，結(jié)合曲率法和統(tǒng)計法對點云進行特征型面分割，有效識別了平面、圓柱面和球面等規(guī)則曲面。采用最小二乘擬合法求解曲面參數(shù)，擬合NURBS曲面，并采用Newton-Raphson迭代法求解面與面的相交線。實驗中規(guī)則模型的特征面識別率達到100%，復(fù)雜規(guī)則幾何模型的主要特征面能正確識別。實驗結(jié)果表明該方法在以規(guī)則型面為主要特征的零件模型重構(gòu)應(yīng)用中的有效性。

曲率估算 曲面擬合 曲面求交 曲面重構(gòu)

0 引 言

隨著精密加工的逐步發(fā)展，傳統(tǒng)的測量方法已經(jīng)無法滿足實際測量的需求，往往需要借助于非接觸等方式獲取機械零件表面的稠密點云數(shù)據(jù)，然后通過基于點云坐標數(shù)據(jù)的擬合手段來分析機械零件表面的尺寸參數(shù)。所以在逆向工程和大型鍛件行業(yè)中，研究基于點云數(shù)據(jù)的二次曲面擬合具有重要的意義。此外，曲面擬合廣泛應(yīng)用于計算機輔助設(shè)計與制造、計算機圖形學(xué)、計算機輔助幾何設(shè)計、計算機動畫、機器人等領(lǐng)域。特別是二次曲面(平面、圓柱面以及球面)，通常作為基本體素，通過交、并、差、補等布爾操作組成更復(fù)雜的實體。布爾運算的實質(zhì)是這些基本體素的求交運算，求交運算一直是 三 維實體造型的核心技術(shù)之一。

Levin[1]用隱式多項式方法表達二次曲面，利用矩陣的代數(shù)運算和參數(shù)方程求解二次曲面之間的相交問題，并提出不同坐標系中曲面的表達形式可通過坐標變換來實現(xiàn)。Miller等[2]對基本二次曲面 (球面、正圓柱、正圓錐 )提出用幾何參數(shù)表示二次曲面，求解平面與曲面、曲面與曲面之間的相交問題。文獻[3]介紹了一種二分方式的曲面求交算法，通過求解一個約束優(yōu)化問題選取起始點，根據(jù)相交曲面的微分幾何結(jié)構(gòu)跟蹤平面曲線，使用曲率確定的自適應(yīng)步長。文獻[4]提出了三角網(wǎng)格曲面求交算法，根據(jù)各層結(jié)點包圍盒相交檢測實現(xiàn)網(wǎng)格曲面相交區(qū)域快速定位，實現(xiàn)三角網(wǎng)格曲面求交。

文獻中交線求解方法主要針對已經(jīng)擬合的曲面進行計算，本文直接對散亂點云求解各特征面(平面、球面、圓柱面)的交線。在分割出特征面的前提下對各特征面求解其交線。

1 基于曲率的特征面類型識別

1.1 離散點云曲率估算

曲率是曲面的一種特性，它描述了曲面的局部性質(zhì)，高斯曲率、平均曲率、主曲率等微分信息有助于幾何物體的形狀特征分析和模型識別。對離散點云，可通過鄰域點集擬合參數(shù)化曲面的方法求解離散點的曲率。設(shè)點云模型的點集表示為：X={x1,x2,…,xN}，其中N為點云總數(shù)，任意一點xi的最近k鄰域表示為Neib(xi)。本文采用二次曲面擬合鄰域點集并估算離散點的曲率。

記二次曲面參數(shù)方程為：

Q12uv2+Q21u2v+Q02v2+Q20u2+Q22u2v2=

[1uu2]Q[1vv2]T

(1)

式中：Q為3×3的系數(shù)矩陣。

矩陣方程建立和參數(shù)求解步驟如下：

(1) 以xi為原點，該點法矢ni為z軸，構(gòu)造u-v-z局部直角坐標系。

(2) 鄰域Neib(xi)中的所有點經(jīng)坐標變換，換算為局部坐標點(u,v,z)。

(3) 所有坐標點(u,v,z)代入式(1)，并通過矩陣求解獲得待定系數(shù)。

根據(jù)曲面論直接計算高斯曲率K、平均曲率H和主曲率k12等曲率參數(shù)為：

1.2 點云區(qū)域所屬的特征面類型判斷

基于曲率信息即可初步確定點所在的局部曲面類型。根據(jù)高斯曲率K和平均曲率H，將點劃分至峰、阱、脊、谷、鞍形脊、鞍形谷、平面和極小曲面八種曲面類型，以此為初始聚類，可進一步分割出點云區(qū)域[5]。為了實現(xiàn)逆向設(shè)計中的曲面造型，還需要判斷點云區(qū)域所屬的特征面類型，例如機械零件表面造型中常見的平面、柱面、球面等。

盡管在理論上分割后的點云區(qū)域隸屬于一個曲面類型，但是由于計算誤差和噪聲等因素影響，區(qū)域中還會存在“異點”。為了有效剔除這些“異點”，將采用統(tǒng)計方法，依據(jù)曲率參數(shù)分布規(guī)律，劃分點云區(qū)域所屬的特征面類型。

以三種基本特征面為例，它們的曲率判斷條件如表1所示。其他參數(shù)化面，只要曲率分布有規(guī)律性，均可納入該表。

表1 三種特征面的曲率判斷條件

設(shè)xj為分塊點云X1中的任一點，點云數(shù)量為N，Ti(i= 0,1,2)對應(yīng)平面、球面、圓柱面三類基本造型面，則有以下判斷過程：

(1) 統(tǒng)計X1中所有點的曲率參數(shù)H、K、k1、k2的平均值和方差。

(2) 遍歷X1中的各點xj，按照表1判斷條件，將點劃分至Ti。

(3) 統(tǒng)計Ti中的點數(shù)Ni，比值Ni/N即為當前區(qū)域?qū)儆陬愋兔鎖的概率pi。

(4) 預(yù)設(shè)概率閾值pT= 0.67(假設(shè)Ti中屬于類型面i的點的個數(shù)超過該區(qū)域中點的個數(shù)的三分之二，即pT= 0.67)，如果pi>pT，則認定當前聚類屬于曲面類型i，返回曲面類型參數(shù)i。

2 特征面參數(shù)計算與求交

2.1 點云曲面的參數(shù)計算

已知點云區(qū)域的曲面類型，可以重構(gòu)出相應(yīng)的NURBS曲面，平面、球面、圓柱面三種類型曲面的重構(gòu)方法如下。

2.1.1 平面

為了提高平面擬合計算速度，不采用最小二乘法求解，直接根據(jù)已知點云區(qū)塊信息進行擬合，點云平面擬合步驟如下：

(1) 計算點云重心，作為待求平面的中心點Cp。

(2) 計算點云法矢重心，即平均法矢，作為待求平面的法矢n。

(3) 計算點云包圍盒，根據(jù)包圍盒長寬高參數(shù)獲得待求平面的長L(包圍盒長邊)和寬W(包圍盒中邊)。

(4) 將包圍盒長邊方向作為平面的第一方向F。

(5) 根據(jù)S=n×F計算平面的第二方向。

(6) 使用Cp、L和W、F和S，計算矩形平面的四個角點。

2.1.2 球面

首先要注意的是，只有點云在完整球面均勻分布時，點云重心才會與球心重合，如果是半球或球面片，點云重心將完全偏離球心，因此球心不能通過點云重心求得。針對球面一般方程x2+y2+z2+ax+by+cz+d=0，以待求參數(shù)a、b、c、d為未知數(shù)，方程變形為ax+by+cz+d=-(x2+y2+z2)，代入離散點坐標(xi,yi,zi)，采用最小二乘擬合方法計算球面參數(shù)，則有：

AX=B

如果球面的點云數(shù)量非常大，如超過(10萬個點)，若將所有點都用來擬合球面，采用最小二乘法擬合時得到的矩陣比較大，求解方程時速度比較慢，為了提高擬合速度，一般采用采樣法提取部分點集進行擬合，常用的有等間隔采樣或者隨機采樣[6]。

2.1.3 圓柱面

已知柱狀點云各點的法向為ni，并設(shè)待求圓柱高h，底圓半徑為r，圓心為Cp，軸線方向為l。圓柱面擬合一般先求得圓柱軸線方向，然后向軸線垂直的平面投影獲得投影平面上的圓狀投影點，再對圓狀投影點進行參數(shù)化擬合即可獲得圓柱底圓信息。

1) 圓柱軸線l的計算 直觀地，柱狀點云各點的法向與圓柱的軸線相互垂直，因此有l(wèi)·ni=0，可采用最小二乘法求解得到圓柱軸向。但是，超定線性方程組l·ni=0為齊次方程，且沒有常數(shù)項，因此只有恒定解l(0,0,0)，顯然此解無效，需要另尋解法。因為柱狀點云法矢的高斯投影在一個平面上(若點云塊各點的法矢是單位法矢，則投影為一個圓)，該平面的垂直方向即為圓柱軸線方向。因而，只需要任選兩條相交的法矢，叉乘即可獲得軸向。為了體現(xiàn)點云的統(tǒng)計特性，并提高軸線計算的精度，采用主成分分析法[7]，提取點云法矢分布的兩個主方向k1和k2，則有l(wèi)=k1×k2。

圖1 圓柱計算模型

3) 圓柱底圓半徑r和圓心Cp的計算 如圖1所示，構(gòu)造過原點O，以l為法向的平面pl′，柱狀點云各點投影至pl′，投影點為一圓狀點集。

2.2 特征面交線的計算

(1) 選初始點P0=S1(0.5,0.5)，即S1面的中點。

(4) 沿Tid向前進一個步長s：Pi=Pi+d×s×Ti。

(7) 根據(jù)相鄰迭代點的切矢夾角誤差eA更新步長s，轉(zhuǎn)(2)。

其中步長計算公式為：

s′=s×eA/acos[(Ti·Ti-1)/α]

式中：α為方向敏感參數(shù)，設(shè)定α>1將縮短步長，否則將加大步長，程序設(shè)計中可以根據(jù)前后兩個切矢的夾角∠TiTi-1或者設(shè)定步長閾值sT= 0.01等方式實時調(diào)整步長值。

步驟(2)和步驟(5)中的投影點計算，具體過程如下：

③ 否則計算交線主方向，更新迭代點，轉(zhuǎn)①。

建立如下線性系統(tǒng)：

通過對矩陣方程的求解得到新的投影點：Pi+1=XT。

3 實驗結(jié)果分析

使用VS2008和OpenGL開發(fā)平臺，在Windows 10下分步實現(xiàn)了上述算法，并使用多種模型驗證算法的有效性。實驗所用的計算機的配置為CPU Intel Core i3 3.4 GHz，內(nèi)存8 GB。實驗對4種不同的模型進行特征面識別、曲面重建和交線求解，實驗結(jié)果如圖2所示。圖2中列出了四種不同模型的實驗結(jié)果，每個模型從左到右列分別是原始模型，點云區(qū)域和類型劃分結(jié)果和特征面交線求解結(jié)果。

圖2 模型實驗

模型1為八面體，八個平面全部正確識別，交線求解正確；模型2中有11個平面、 2個圓柱面和少量過渡面，除過渡面外全部正確識別，交線求解正確；模型3中有8個平面、2個圓柱面和一個球面，全部正確識別，交線求解正確；模型4點云不均勻，主要由平面、圓柱面和過渡面組成，主要平面和圓柱面都能正確識別，交線求解正確。實驗中采用對所有重構(gòu)曲面進行兩兩求交的方法，交線實際為平面與平面的交線、平面與圓柱和球面的截交線，以及圓柱與圓柱的相貫線，交線的邊界為重構(gòu)曲面的邊界。

4 結(jié) 語

本文采用曲率法分割點云區(qū)域，并結(jié)合統(tǒng)計法識別特征面類型，通過參數(shù)化計算擬合NURBS面片，再采用迭代投影法求解曲面交線。選擇了以平面、圓柱面和球面為主要特征的點云模型進行實驗，正確識別了主要特征面及其特征交線，驗證了算法的有效性。然而，該方法最大的局限性在于小的過渡面和不規(guī)則曲面不能準確識別，但是對于以規(guī)則型面為主要特征的零件模型，選用本文方法作為主特征識別方案還是可行的。對于復(fù)雜和不規(guī)則曲面點云曲面的識別可以通過對點云進行分塊，再對局部區(qū)塊進行特征面識別和擬合可以起到更好的效果，此內(nèi)容為下一步研究工作。

[1] Levin J Z.Mathematical models for determining the intersections of quadric surfaces[J].Computer Graphics & Image Processing,1979,11(1):73-87.

[2] Miller J R,Goldman R N.Using Tangent Balls to Find Plane Sections of Natural Quadrics[J].IEEE Computer Graphics & Applications,1992,12(2):68-82.

[3] 陳曉霞,雍俊海,陳玉健,等.基于坐標變換的曲線曲面求交算法[J].計算機集成制造系統(tǒng),2005,11(9):1327-1332.

[4] 田中朝.三角網(wǎng)格曲面重建及求交理論、方法研究[D].山東理工大學(xué),2008.

[5] 鐘婷婷.基于特征的車身典型復(fù)雜曲面點云數(shù)據(jù)的分割[D].吉林大學(xué),2015.

[6] 林秀芳.逆向工程中的點云采樣算法研究[J].電子設(shè)計工程,2012,20(11):23-25.

[7] Hoppe H,Derose T,Duchamp T,et al.Surface reconstruction from unorganized points[C]//Conference on Computer Graphics and Interactive Techniques.ACM,1992:71-78.

[8] Ma Y L,Hewitt W T.Point inversion and projection for NURBS curve and surface:control polygon approach[J].Computer Aided Geometric Design,2003,20(2):79-99.

ALGORITHMSOFFEATURESURFACEFITTINGANDINTERSECTIONFORSCATTEREDPOINTCLOUD

Chen Huawei1Yuan Xiaocui2*Wu Lushen1

1(SchoolofMechanicalandElectricalEngineering,NanchangUniversity,Nanchang330031,Jiangxi,China)2(SchoolofMechanicalandElectrical,NanchangInstituteofTechnology,Nanchang330099,Jiangxi,China)

Surface reconstruction and its output of NURBS surface for CAD applications is the main object of reverse model. Curvature is the basic information of surface and the key parameter in surface reconstruction. In this paper，quadric surface method was used in curvature estimation for point cloud. By combining curvature method and statistical method, the feature surface of point cloud was segmented, and the regular surfaces such as plane, cylinder surface and sphere were identified effectively. Moreover, the least square fitting method was used to solve the surface parameters, and the NURBS surface was fitted. The Newton-Raphson iterative method was used to solve the intersection line of surface and surface. In the experiment, main features had been recognized and even 100% recognized for rule models. And the main feature planes of complex regular geometry model can be correctly recognized. The result manifests that the proposed methods are effective in surface reconstruction, especially for models composed mainly of rule feature surfaces.

Curvature estimation Surface fitting Surface intersection Surface reconstruction

2017-03-15。國家自然科學(xué)基金項目(51365037)。陳華偉，副教授，主研領(lǐng)域：逆向工程，機器視覺。袁小翠，講師。吳祿慎，教授。

TP399

A

10.3969/j.issn.1000-386x.2017.12.047