基于自適應橢圓距離的點云分區精簡算法

吳祿慎　俞　濤　陳華偉

(南昌大學機電工程學院　江西 南昌 330031)

?

基于自適應橢圓距離的點云分區精簡算法

吳祿慎俞濤陳華偉

(南昌大學機電工程學院江西 南昌 330031)

摘要利用傳統點云精簡算法進行散亂點云簡化會導致點云模型部分細節特征的丟失或模糊以及影響非平面區域的光順性。針對這些問題，提出基于自適應橢圓距離的點云分區精簡算法。首先，通過對鄰域點集進行微切平面與局部曲面的擬合，計算出各點的法矢及曲率等；其次，利用所得幾何特征信息，提取點云邊界特征以及完成點云平面區域與非平面區域的劃分；最后，采用改進后的精簡算法對不同區域進行簡化。實驗結果表明，該算法不但能夠快速完成符合要求精簡率的數據簡化，還能保護點云模型的細節特征以及保證模型非平面部分的光順性。經過軟件分析得出，精簡后模型與原始模型的距離誤差的標準偏差為0.015 mm。

關鍵詞點云精簡四元數最小距離法點云分區邊界提取

REDUCTION ALGORITHM OF POINT CLOUD SEGMENTATION BASED ON ADAPTIVE ELLIPTICAL DISTANCE

Wu LushenYu TaoChen Huawei

(School of Mechanical and Electrical Engineering, Nanchang University, Nanchang 330031,Jiangxi, China)

AbstractApplying traditional point cloud reduction algorithm to reducing scattered point cloud will lead to missing or fuzzy of some detail features of the point cloud model and affecting the smoothness of non planar region. Aiming at these problems, we put forward the adaptive elliptical distance-based point cloud segmentation reduction algorithm. First, by fitting the tangent plane and local surface on neighbourhood set, it calculates the normal vector and curvature of each point; secondly, it uses the derived geometric feature information to extract point cloud boundary characteristics and to complete the partition of planar regions and non planar regions of point cloud; finally, it uses the improved reduction algorithm to simplify different regions. Experimental results show that the algorithm can not only rapidly accomplish data simplification in accord with the required reduction rate, but can also protect the detail characteristics of point cloud model and ensure the smoothness of non planar portion of model. Through software analysis, it is found that the standard deviation between the reduced model and the original model is 0.015 mm.

KeywordsPoint cloud reductionQuaternionMinimum distance methodSegmentation of point cloudBoundary extraction

0引言

逆向工程中，光學三維掃描設備被廣泛用于精確、快速地獲取物件表面坐標信息，但會生成大量的冗余數據，且點云數據一般散亂無序、十分密集。若將全部點云都用于曲面重構，不僅占用大量的計算機資源，操作效率低，而且龐大的數據不便于后續的存儲、顯示及傳輸等。因此，在保證精度的前提下對數據進行有效地精簡顯得尤為重要。目前，許多學者對點云精簡做了大量研究，邵正偉[1]等先使用八叉樹法對散亂點云進行點云空間劃分，然后采用包圍盒法[2]完成點云的均勻精簡，能夠快速完成精簡，適合應用平面區域。李鳳霞[3]等提出采用鄰域點與采樣點法矢夾角平均值作為采樣點特征信息，對采樣點進行劃分成多個類別，然后對每一類按規定的精簡率完成點云數據簡化。徐亞軍[4]等提出采用最小曲面距離法，即用曲面距離代替歐式距離，對點云進行精簡。葛源坤[5]等通過計算所得點云高斯曲率，設定閾值，將點云劃分為平坦區域和突變區域，然后分別對不同區域采用包圍盒法和最小距離法進行點云精簡。朱煜[6]等采用鄰域點與采樣點距離的Hausdorff距離代替點云曲率對點云進行分段，然后在每段設定不同的Hausdorff距離閾值完成點云精簡。

本文考慮點云模型的諸多細節特征都關系到點云邊界特征和數據精簡直接影響到特征區域的光順性。因此根據所得點云曲率法矢信息完成點云邊界提取，以及點云平面區域與非平面區域的劃分，然后對邊界特征進行強制保留，對其附近數據進行保護性精簡，并且對非平面區域提出采用變化的橢圓距離作為閾值完成點云簡化，最終通過實驗驗證該算法的有效性。

1點云曲率、法矢的計算

1.1估算點云法矢

1.2計算點云曲率及法矢修正

全局坐標轉換為局部坐標的方法步驟為：

(1) 將全局坐標原點平移至于局部坐標原點(即pi)重合，則有平移向量為vi(xi,yi,zi)；

(2) 計算出Z軸nz(0,0,1)與H軸ni(xi,yi,zi)夾角α，然后繞方向RoAixs(xr,yr,zr)經過一次旋轉α角度使兩軸重合的；

其中：

cosα=nz·ni

(1)

RoAixs(xr,yr,zr)=nz×ni

(2)

(3) 由求得的旋轉參數構造旋轉四元數Quat(x,y,z,w)：

(3)

(4) 通過(3)中得到的四元數求取旋轉矩陣RoM：

(4)

(5)

將式(1)-式(4)代入式(5)計算可得出坐標系O-XYZ向坐標系pi-HUV變換的旋轉矩陣；

(5) 利用上述所求平移向量和旋轉矩陣，完成坐標轉換：

pm′T=RoM·(pm-vi)T

(6)

其中：m=0,1,…,k-1。

(7)

對于曲率，需要先求出曲面的第一基本量E、F、G和第二基本量L、M、N為:

E=fu·fuF=fu·fvG=fv·fv

(8)

(9)

(10)

(11)

2點云劃分及邊界提取

2.1點云的區域劃分

通過分析曲面曲率的幾何意義[6]可知：曲面上某點曲率是該點曲面形狀的體現，曲率的大小對應于曲面在該點處的彎曲變化程度。其中高斯曲率K是兩主曲率的乘積，根據其數值的大小，可以確定曲面上該點的類型——橢圓點(K>0)、拋物點(K=0)和雙曲點(K<0)，而平均曲率H是兩主曲率的平均值，其數值的大小表面曲面在該點處的凹凸性質。因此依據高斯曲率與平均曲率不同組合，可以將曲面大致分為表1中的八種類型：平面、脊、谷、峰、阱、鞍形脊、鞍形谷和極小曲面。

表1　曲面類型區分

對于本文中進行的點云精簡，只需要區分出平面與非平面，所以平面以外的七種類型的曲面可以統一考慮，全部當作為特征曲面處理。

2.2邊界特征提取

進行點云精簡時造成細節特征丟失或模糊的很大一部分因素是完成精簡后點云的邊界特征減少，因此在精簡前先對邊界特征進行提取保護。在點云中邊界特征存在的主要形式包括如圖1所示的3種。

圖1　三類點云邊界特征

對于非封閉邊界[8]d3，將目標點pi及K鄰域P{p0,q1,…,qk-1}投影到其微切平面上，如圖2所示。將所有鄰域投影點分別與pi投影點連線，判斷相鄰連線夾角，如果存在夾角大于夾角閾值(經驗值結合曲面重構三角化研究，設定閾值為120°)，則可以判定目標點pi為邊界特征點。

(a) pi為非封閉邊界點　　　(b) pi不是非封閉邊界點圖2　pi及其鄰域點的微切平面投影

f(pi)=d(p,L)/max{d(qj,L)}

(12)

當f(pi)>ε，點pi為邊界點；否則為內部點。其中ε為判定閾值，經過實驗總結，一般取為0.8~1.0，即可較好地提取點云模型的突變尖銳邊界特征。

對于過渡邊界d2，在完成區域劃分后，通過判斷目標點pi的K鄰域P{p0,q1,…,qk-1}中處于不同區域中點數目的比例來進行提取。

3基于分區的點云精簡

3.1最小距離法精簡算法

對于采樣點pi，查找其K鄰域點集P{p0,q1,…,qk-1}，并分別計算每一個鄰域點到采樣點的距離Di(i=1,2,…,k-1)。然后設定用于判斷鄰域點保留與否的最小距離閾值Dmin：

(13)

則最小距離法的精簡原則為：

fi=Di-σ×Dmin

(14)

其中，σ為距離調節系數，最后依次比較每一個鄰域點的fi數值，當其小于0時，標記qi點為刪除。

3.2自適應最小橢圓距離精簡算法

對于任一非平面采樣點pi,計算出整個鄰域點與pi點法矢的夾角余弦的平均值，法矢夾角精簡規定夾角小于平均夾角的鄰域點標記為刪除。但是往往其中與法矢的夾角小于夾角平均值的鄰域點，存在如圖3表達的兩種可能情況：(1)曲面在鄰域點與采樣點所構成方向上的彎曲程度較小；(2)曲面在鄰域點與采樣點所構成方向上有較大的彎曲，但該鄰域點距離采樣點比較近。

圖3　法矢夾角變化示意圖

對于情況(1)所屬方向上可以適當保留較少數據點，擬合后仍能夠很好地接近原始形狀；而對于情況(2)，為了能擬合出真實形狀，需要保留更多比例的數據點。

針對上述兩種情況，為滿足鄰域中在不同方向上精簡步距的不一致，同時考慮到曲面上采樣點在任意方向的曲率kn，提出橢圓思想構造變化距離閾值結合最小距離法來實現非平面區域數據簡化：

kn=k1·cos2θ+k2sin2θ

(15)

其中橢圓距離的確定方法為：對于每一個采樣點，均可以獲取兩個主曲率方向，以最小主曲率所在方向上確定的距離閾值d1為長軸。以最大主曲率所在方向確定的距離閾值d2為短軸，確定橢圓函數d(θ)，其中θ為任意方向與最小主曲率方向夾角，則在每一不同方向都會有相對應的距離閾值d(θ)：

(16)

在進行精簡過程時，首先綜合考慮法矢夾角閾值以及最小距離閾值，計算出兩主方向上的距離閾值；再求取所有任意鄰域點方向與最小主曲率方向的夾角；最后遍歷所有鄰域點，通過與其所處方向距離閾值比較判斷是否刪除數據點。

3.3精簡實施流程

散亂點云分3類進行處理：平面區域、非平面區域和突變邊界。

對于突變邊界點，采用強制保留。并且為了更好地保護點云細節特征，凡是距離邊界點小于平均鄰域點距的點都進行保留。

對于任意未被標記為刪除的采樣點pi，當pi在平面區域時，采用3.1節中介紹的最小距離法進行點云數據精簡。

對于任意未被標記為刪除的采樣點pi，當pi在非平面區域時，采用3.2節中介紹的改進的非平面區域點云精簡算法進行數據簡化。但是對于初步判定刪除的鄰域點，須進一步考察其之前未被當作采樣點使用過，否則不作刪除處理。

4實例應用

本文采用汽車某擋塊零件的一部分原始點云(總共64 418個點)作為對象，采用上述方法進行邊界提取與區域劃分，以及點云的精簡，完成的效果分別如圖4-圖6所示。

圖4　點云邊界特征

圖5　非平面區域

圖6　精簡后點云模型

精簡完成后，對原始點云模型以及精簡后點云(20165個點)進行曲面模型重構，并且對部分具有細節特征的區域進行放大處理，分別生成如圖7-圖10所示。通過觀察可以比較明顯地發現精簡前后兩者模型基本能夠保持一致。

圖7　原始點云重構模型

圖8　精簡前局部放大

圖9　精簡后點云重構模型

圖10　精簡后局部放大

進一步采用專業逆向軟件Geomagic對精簡前后模型進行距離誤差分析，其結果如圖11所示。

圖11　Geomagic軟件比較精簡前后模型誤差

經過軟件分析得出：精簡后模型與原始模型的距離誤差的標準偏差為0.015 mm。

5結語

本文通過對鄰域點進行局部曲面擬合，計算出點云的曲率法矢信息。接著進一步利用計算所得幾何特征信息對點云進行特征邊界提取以及平面與非平面區域的劃分。最后針對平面區域、非平面區域和兩者之間過渡區域點云各自的不同特點，分別采用不同的處理方法進行簡化。實例驗證表明：該算法不但能夠快速地完成符合要求精簡率前提的數據簡化，還能夠保護好點云模型的細節特征以及保證模型非平面部分的光順性。

參考文獻

[1] 邵正偉，席平.基于八叉樹編碼的點云數據精簡方法[J].工程圖學學報,2010(4):73-76.

[2] Sun W, Bradley C, Zhang Y F, et al. Cloud data modeling employing a unified non-redundant triangular mesh[J]. Computer-Aided Design,2001,33(2):183-193.

[3] 李鳳霞,饒永輝,劉陳,等.基于法向夾角的點云數據精簡算法[J].系統仿真學報,2012,24(9):1980-1983.

[4] 葛源坤,黎榮,李海倫．空間分割與曲率相融合的點云精簡算法研究[J].計算機應用研究,2012,29(5):1997-2000.

[5] 朱煜，康寶生，李洪安,等.一種改進的點云數據精簡方法[J].計算機應用,2012,32(2):521-524.

[6] 徐亞軍，魏永超.基于最小曲面距離的快速點云精簡算法[J].光電工程,2013,40(8):59-63.

[7] 肖天姿.散亂點云的數據預處理與曲面重建研究[D].大連：大連海事大學,2012.

[8] 周玉蓮.基于法矢信息的點云特征提取技術的研究[D].哈爾濱：哈爾濱工業大學,2012.

[9] 陳義仁.逆向工程中散亂點云預處理相關算法研究[D].合肥：中國科學技術大學,2012.

中圖分類號TP391

文獻標識碼A

DOI:10.3969/j.issn.1000-386x.2016.02.010

收稿日期：2014-09-18。國家自然科學基金項目(51065021，51365037)。吳祿慎，教授，主研領域：逆向工程及光機電一體化，虛擬現實技術。俞濤，碩士生。陳華偉，講師。