面向三維殘缺點云圖像的數據精簡方法

尹金林，王春香，劉流，王齊超，潘杙成

(內蒙古科技大學機械工程學院，包頭 014010)

隨著逆向工程技術在各行各業得到廣泛應用，其點云數據采集技術也得到了飛速發展。許多具有自由曲面的零件都可以通過采集點云數據獲得。采集的點云模型能清楚地表達模型的表面細節，但是也會有冗雜數據。對于接下來的數據處理造成了不必要的數據計算和存儲的負擔，影響數據預處理的效率以及模型的曲面光順性，為解決上述問題，就需要對采集數據中的冗雜數據進行精簡處理。

中外學者對三維點云數據精簡開展了大量研究。文獻[1]通過基函數計算點云數據密度值，結合粗濾波和精去噪，保留了模型的細節。文獻[2]將粒子群優化算法引入到傳統的平均距離精簡法中，提高了算法的精簡精度。文獻[3]對點云法向量特征進行估計后，利用K均值和高斯球聚類來簡化點云數據。文獻[4]提出了一種基于K近鄰和聚類算法的三維點云簡化方法，使用K均值算法將3D點云劃分為簇，對每個簇執行熵估計以去除具有最小熵的數據點，以此達到數據精簡的目的。文獻[5]基于法向角的局部熵來作為點重要性的判別依據，通過刪除最不重要的點并逐步更新向量和重要性值，直至達到用戶指定的縮減率。以上早期對點云冗雜數據的精簡主要策略是刪除密集區域數據，無法做到較好的保留點云模型幾何特征數據點，精簡后模型的邊界及特征容易失真。

對此，也有許多學者針對保留特征點的點云精簡方法展開了研究，即在對點云數據進行有效精簡時，同時保留模型原有的特征點。文獻[6]對不同類型的點云數據采用不同的精簡策略，通過整合特征點和非特征點，實現了精簡的目的。文獻[7]提出了一種基于最優鄰域局部熵的精簡算法，較好地保留了模型的特征數據點。文獻[8]提出了一種基于共形幾何代數的點云簡化算法，該方法能有效地保留模型局部細節且總體誤差也較小。文獻[9]設計了一種自動遞歸細分方案來挑選代表點并去除冗余點，通過細算算法自適應地進行數據精簡，保持原始邊界的完整性。文獻[10]提出了一種具有特征保留的分散點云精簡算法，該方法對不同曲率模型的適應性較好，但計算效率較低。文獻[11]提出了一種基于自適應鄰域和局部貢獻值的點云精簡算法，按類別和貢獻值對點云進行精簡，更好的保留了模型原始面貌。文獻[12]提出了一種基于修改后的模糊均值聚類算法，根據點云特征信息和簡化參數簡化點云。文獻[13]利用ε-支持向量回歸(ε-support vector regression，ε-SVR)算法的平坦度特性識別掃描線高曲率區域中的點，有效地檢測鋒利邊緣附近的點且無需額外處理。文獻[14]利用稀疏矩陣檢測點云顯著性，在數據精簡后不產生表面空洞的情況下，保持了形狀特征。

以上的研究大多是針對完整模型的精簡方法，但在實際點云數據采集過程中由于模型表面反射，光線環境，操作技術，模型結構角度等限制，會導致采集數據缺失，形成孔洞。而在進行點云數據精簡時，需要保留模型原始邊界特征點及孔洞鄰域特征，以保證精簡后模型不失真和后續的孔洞修補處理。針對目前已有方法存在的不足，提出一種針對殘缺點云模型數據精簡方法，通過點云法向量夾角作為特征檢測算子，然后利用歐氏距離搜索特征近鄰數據點，完成殘缺模型特征點的提取。以平均曲率作為數據精簡閾值，實現對非特征區域數據的精簡，最后將提取到的特征數據點與精簡后的非特征數據點融合，從而完成針對殘缺點云的數據精簡。為后續對殘缺點云的修補等技術處理奠定了基礎。

1 邊界及孔洞初始特征點提取

1.1 點云空間索引的建立

由于采集的點云模型數據量比較龐大，且在空間內沒有明顯的特征規律。通過建立空間拓撲關系，可以加快點云查詢計算的效率。但激光掃描得到的點云數據，是三維空間，普通的二分樹不能滿足需求。而KD-tree(KD樹)數據結構，常用于大規模高緯度數據索引。其數據檢索方式，如圖1所示，共有12個數據點(p1～p12)。首先根據不同方向上坐標的方差大小決定起始分割方向(檢索方向選取x軸方向)，再按照該方向將數據從小到大排序，選取中值附近數據作為根節點，大于中值的數據p2，存儲在右子葉；小于中值的數據p3，存儲在左子葉，然后根據方差大小依次更新分割方向(y軸方向、z軸方向)，插入節點，直至所有點云數據包含在該樹中。

圖1 KD-tree數據索引方式

1.2 點云法向量計算

法向量的估計方法有很多，使用經典而簡單的主成分分析方法[15]來估計法向量。通過KD-tree空間點云拓撲關系，對點云數據進行鄰域范圍查找。對所求點周圍滿足一定條件的鄰域點進行局部微切平面擬合，以該點鄰域確定的微切平面法向量作為該點的法向量的估計值。

對于點云中的點pi，(i=1,2,…,k)，及其k個近鄰點，擬合平面F(n，d)由式(1)可得。

(1)

對方程中半正定協方差矩陣M的特征值分解，如式(2)所示，其最小特征值的特征向量是點p的法向量的估計值。

(2)

1.3 特征點的判別

一般在平緩區域內法向量夾角變化不明顯，但在點云數據邊界以及存在明顯特征的區域法向量變化比較明顯，如圖2所示，在模型的角點、平滑區域、邊界處法向量夾角各不相同。通過計算樣點與其鄰域內點云法向量的夾角，來進行特征點的提取。

圖2 模型不同特征處法向量夾角

記樣點p1的法向量為n1(x1，y1，z1)，其鄰域點p2的法向量為n2(x2，y2，z2)，兩個法向量夾角由式(3)計算可得，從而得到樣點與其鄰域點法向量夾角的集合，將最大值αmax和設定的閾值ε比較，遍歷全部數據。若αmax>ε，判斷該點為邊界特征點，并儲存該點。反之舍棄該點，從而完成特征點初始特征點提取，其流程如圖3所示。

圖3 初始特征點提取流程

(3)

采用上述方法對汽車翼子板、某汽車加強板、汽車保險杠外殼(部分)模型進行實驗分析，其中，汽車翼子板共18 634個數據點，如圖4(a)所示，由于數據采集時模型表面的反射造成的數據缺失。汽車某加強板件共126 128個數據點，如圖4(c)所示，該模型原本就存在圓柱特征孔，但在數據采集時由于模型角度的限制，導致無法完整的采集到圓柱特征孔數據。汽車保險杠外殼共152 069個數據點，如圖4(e)所示，該模型存在的特征較多，由于環境和操作的影響，在一些細小特征處造成了數據缺失。利用上述方法對以上模型進行特征點的初步提取，其提取的特征點如圖4(b)～圖4(f)所示。

圖4 點云模型及初始特征提取

2 邊界和孔洞領域提取

通過給定一個目標點集(提取到的初始特征點)，利用點云數據與目標點集的歐氏距離搜索其最近鄰，從而得到殘缺點云的特征鄰域點，使得提取出更多的邊界特征數據。搜索最近鄰域點數，其效果如圖5所示，識別數據量如表1所示，把識別到的邊界及孔洞鄰域特征點云數據從原始數據中提取保存，以便接下來對非特征數據精簡。

表1 識別結果數據量統計

KD-tree的最近鄰搜索步驟如下。

步驟1在KD-tree中找出包含初始特征點的葉結點：從根結點出發，依次的向下訪問。若目標點當前坐標值小于結點的坐標值，則移動到左子結點，否則移動到右子結點。直到子結點為葉結點為止。

步驟2以此葉結點為“當前最近點”。

步驟3遞歸的向上回退，在每個結點進行以下操作：①如果該結點保存的實例點比當前最近點距初始特征點更近，則以該實例點為“當前最近點”；②檢查另一個子結點對應的區域是否與以初始特征點為球心、以初始特征點與“當前最近點”間的距離為半徑的超球體相交。如果相交，可能在另一個子結點對應的區域內存在距離初始特征點更近的點，移動到另一個子結點。接著，遞歸的進行最近鄰搜索。如果不相交，向上回退。

步驟4當回退到根結點時，搜索結束。最后的“當前最近點”即為初始特征點的最近鄰點。

3 非特征數據精簡

曲率是衡量彎曲程度的一個度量。傳統的曲率精簡法是一種全局性的精簡方法，在數據精簡時，根據點云平均曲率值的大小，在曲率變化較小的區域，保留較少的點，而在曲率變化較大的區域，保留更多的點。本文結合對邊界和孔洞鄰域特征的提取，對非特征區域數據進行曲率精簡，以達到保留其特征的目的。

圖6 變量的幾何關系

(4)

式(4)中：α為向量-N和pqi之間的夾角；β為向量N和Mi之間的夾角。

式(4)的近似值可由式(5)得到。

(5)

設S是經過點p的平面，e1和e2是點p的主方向，對應的主曲率k1和k2都是未知的。未知參數θ為向量e1與X的夾角，θi為向量pQi投影到平面S上得到的向量X與向量pQi的夾角。根據歐拉公式，法曲率和主曲率的關系可表示為

i=1,2,…,j

(6)

寫成矩陣形式為

min‖Mμ-R‖2

(7)

式(7)中：

(8)

(9)

μ=[A,B,C]T

(10)

A=k1cos2θ+k2sin2θ

(11)

B=(k2-k1)cosθsinθ

(12)

C=k1sin2θ+k2cos2θ

(13)

點云的平均曲率計算公式為

(14)

計算所有數據點全局平均曲率的平均值，計算公式為

(15)

將非特征點精簡完成后的數據與提取到的邊界以及孔洞鄰域特征數據聯合，從而得到精簡后可以保留殘缺模型特征數據的點云模型，其精簡方法流程圖如圖7所示。

圖7 精簡方法流程圖

4 實驗結果對比

4.1 精簡效果對比

對于殘缺的點云模型，在數據精簡過程中，更需要保持其特征數據，以便于后續的數據處理和曲面重構。為驗證本文方法對殘缺點云模型數據精簡效果，基于點云庫PCL以Visual studio 2017為平臺，用C++語言實現以上方法，同時對某汽車薄壁類零件帶有殘缺的點云模型實現精簡，并將結果與Geomagic Wrap軟件中曲率精簡法和隨機精簡法，進行對比。如圖8～圖10所示，采用隨機精簡法時，模型孔洞以及邊界特征均有一定的失真。曲率精簡法雖然保留了模型高曲率區域的點云信息，但模型孔洞以及邊界特征數據信息丟失嚴重。而本文方法在對上述模型精簡時，在顧及模型細節情況下，隨著精簡比率的上升，仍較好地保留了模型的邊界特征數據。

圖8 汽車翼子板精簡效果

圖10 汽車保險杠外殼精簡效果

4.2 精簡誤差分析

為進一步評估本文精簡方法，采用標準偏差和曲面表面積變化率對上述四個模型精簡效果進行評價[17]。

標準偏差表達式為

(16)

式(16)中：d(p,p′)為原始曲面Fcurve上采樣點p到精簡后點云曲面F′curve上投影點的歐氏距離，由p的單位法向量Np可知，d(p,p′)=|Np(p′-p)|。

表面積變化率的表達式為

(17)

式(15)中：Scurve為原始模型的曲面表面積；S′curve為精簡后模型的曲面表面積。

如圖11、圖12所示，通過比較可以發現，總體上隨著精簡比率的上升，模型的標準偏差及表面積變化率也隨之上升。但隨機精簡法通過隨機刪除數據點的方法精簡，其精簡效果具有不穩定性，標準偏差存在一定的波動；曲率精簡法在對上述模型精簡時，僅保留模型曲率較高的數據，對于較平坦區域的數據會造成丟失，精簡結果并不佳，這也導致曲率精簡法的表面積變化率高于其他方法。采用本文方法精簡后的模型，其標準偏差和表面積變化率總體上大致處于均勻穩定狀態且均優于其他方法，并保留了殘缺點云模型的邊界特征。

圖11 模型精簡標準偏差比較

圖12 模型精簡后曲面表面積變化比較

5 結論

通過分析目前點云模型數據精簡方法中的不足，利用本文方法進行實驗驗證，得出如下結論。

(1)針對薄壁類殘缺的點云模型，提出了一種數據精簡方法。利用法向量夾角選取初始特征數據點，借助歐氏距離搜索其近鄰特征點，將模型數據點劃分為特征數據點和非特征數據點，并對非特征數據點采用曲率精簡的方法，實現局部數據的精簡，最后，把精簡的數據與提取的特征點合并，實現了一種保留其邊界以及孔洞鄰域特征點的數據精簡方法。

(2)實現對非特征點最大可能精簡又保證了邊界及其孔洞鄰域特征的不丟失，且精簡后的標準偏差以及曲面表面積變化率優于其他兩種方法。但本文方法在特征信息計算部分，僅提取到殘缺模型的邊界特征，針對殘缺模型局部特征的提取值還有待進一步研究。