袁小翠 陳華偉

1(南昌工程學院江西精密驅動與控制重點實驗室 江西 南昌 330099)2(貴州師范大學機械與電氣工程學院 貴州 貴陽 550025)

0 引 言

三維掃描儀可以快速獲取物體表面的三維信息，對三維點云數據處理可以實現曲面重建和產品再制造等應用。然而，三維掃描儀獲取的數據一般只有三維坐標信息，無任何拓撲結構，點云數據處理時需要以點云的鄰域為基礎。點云鄰域的準確性直接影響點云處理結果，如法向量估計、去噪和曲面重建等。

點云數據處理一般基于點云的k鄰域。對任意點pi求其k鄰域最直接的方法是計算該點與其他數據點的歐氏距離，取距離最近的k個點。然而，這種方法計算量大、效率低。為了提高計算效率，提出了許多快速鄰域搜索算法。這些方法可以大致分為四類：多步遞歸法，并行法，柵格法(空間劃分法)和數據重組算法[1]，柵格法和數據重組法是比較常用的點云鄰域搜索方法。

柵格法[2-5]計算鄰域的思路是：對點云模型構建最大包圍盒，對包圍盒進行空間劃分得到八個子立方體，再對這八個立方體進行遞歸劃分直到子立方體不包含點云或者立方體的邊長小于給定閾值。對任意點在其周圍26個子立方體中搜索得到k鄰域。文獻[2-3]利用柵格法搜索鄰域對曲面進行重建和提取點云模型空洞。文獻[6]利用子塊擴張方法避免搜索相鄰子空間，但是該方法只適合規(guī)則點云。文獻[4]解決了柵格法對大規(guī)模點云數據k鄰域搜索效率低和分塊不均勻的問題。

數據重組方法[1，7-10]主要是將數據劃分為樹狀結構，它將整個數據集劃分為多級子空間，這些子空間根據遞歸分裂規(guī)則用于構建樹節(jié)點。因此，分裂規(guī)則決定了這些算法的搜索效率。例如，Cell樹[8]通過將數據空間劃分為大小相等的立方單元，從而構建了Cell樹。VP樹[9]通過劃分數據空間建立二進制數。KD樹[10]采用樹節(jié)點來存儲分區(qū)數據空間，從而縮小搜索范圍?；贙D樹的鄰域搜索方法速度快，可以用于任何無規(guī)則點云，廣泛應用于點云數據處理中。

以上點云鄰域搜索方法主要專注于如何提高鄰域構建算法效率，忽略了鄰域的準確性。對于光滑曲面，點云k鄰域可以比較準確地描述局部曲面信息，進而準確計算點云的相關信息，如點云微分信息和曲面重建等。但是，當點云處于高曲率區(qū)域，或者點云位于多個不連續(xù)曲面交界區(qū)域，這些方法計算得到的點云鄰域位于多個不同連續(xù)曲面上。點云處理基于這種鄰域容易造成嚴重的處理誤差或者丟失曲面的細節(jié)信息，針對這些問題，提出各向異性鄰域搜索方法。

1 鄰域搜索方法

1.1 法矢估計及特征點檢測

法向量估計的目的是將特征點的k鄰域映射到高斯球形成多個獨立的數據簇。一般利用點云的鄰域擬合點云的切平面，切平面對應的法向量為點云的法向量。當點云模型處處光滑，通過鄰域擬合的切平面法向量能準備描述點云的法向量。當點云處于高曲率區(qū)域，點云鄰域位于多個不連續(xù)曲面上，擬合的切平面不準確，法向量被平滑。鄰域擬合法估計法向量在文獻[11]中被首次提出，被稱為主成分分析法PCA(Principal Component Analysis)，該方法計算快速，廣泛應用于點云法向量估計。文獻[12-13]改進了文獻[11]的法向量估計方法，這些方法均能比較準確地估計尖銳特征模型的點云法向量，但是比較耗時。本文利用文獻[11]方法粗略估計點云法矢，并對特征區(qū)域的法矢進行修正來獲得較準確的點云法向量。

(1)

C被分解為三個特征向量：v2、v1、v0。三個特征向量對應的特征值分別為λ2、λ1、λ0，其中λ2≥λ1≥λ0。λ0對應的特征向量v0即為切平面法向量。

點的曲面變化表示為：

(2)

一般來說，當ωi=0時，表示點xi位于平面點，ωi值不為0，表示點xi處于非平坦區(qū)域，且ωi越大，表示點xi所處曲面越尖銳。因此，可以根據ωi值判斷點xi的類型，即特征點和非特征點，如果ωi大于給定閾值Thresh，表示點xi為候選特征點。圖1為經典模型Smooth-feature法矢和特征點檢測結果，其中(c)為(b)中矩形框中折角面的放大圖?；疑珔^(qū)域點表示檢測的特征點，線條表示法向量。

(a) Smooth-feature模型 (b) 點云法向量

(c) 局部區(qū)域法矢 (d) 特征點圖1 Smooth-feature模型法向量及其特征點

為了快速得到準確法向量，用平坦區(qū)域準確的法矢修正特征點的法矢。本文采用前期研究工作——鄰域迭代加權法[14]修正特征點的法向量，特征點法矢修正表示為：

(3)

式中：σd、σn分別是距離帶寬和法向偏差帶寬，一般都取0.2，即σd=σn=0.2。

圖2是法向量修正結果，圖2(a)為Fandisk PCA方法估算得到的法向量，經過3次迭代(t=3)后修正結果如圖2(b)所示，可以看出修正后的法向量幾乎垂直所對應的局部曲面。

(a) PCA方法估計的法向量 (b) 修正后的法向量圖2 Fandisk點云模型法向量修正結果

1.2 各向同性鄰域分割

點云高斯映射[15]的目的是將特征點的各向同性鄰域映射到高斯球上形成不同的數據簇。

高斯映射的特點：如果點云模型是一連通的平面，則該連通平面上的點云映射為高斯球上的一點；反之，如果點云模型的高斯圖為高斯球上的一點，則該點云模型為一平面[15]。然而，估算的點云法向量與標準法向量總是存在一定的偏差，所以連通平面的點云映射為高斯球上密集的一個數據簇。

若估算的點云法矢比較準確，在局部區(qū)域連續(xù)曲面的法矢接近平行，該區(qū)域的點云高斯映射時形成一個密集分布的數據簇。若局部區(qū)域曲面不連續(xù)，不同曲面間的法矢夾角較大，高斯映射時形成多個數據簇，且數據簇的個數與曲面的個數一致。圖3 (a)是由三個連續(xù)曲面相交形成的轉角曲面模型，估算的法矢如圖3(b)所示，斯映射示意圖如圖3(c)所示。局部區(qū)域不連續(xù)曲面的越尖銳，高斯球上不同數據簇的距離越遠。

(a) 轉角曲面點云 (b) 點云法向量 (c) 高斯圖圖3 特征區(qū)域高斯映射示意圖

將特征點的Kb(一般Kb=3k)鄰域映射到高斯球，在高斯球上形成不同的數據簇，再對高斯球上的數據簇聚類分割，將數據簇分為多個獨立的子類，各子類對應不同連續(xù)曲面上的點云，即特征點的各向同性鄰域被分割為多個子鄰域，且各子鄰域各向異性。因為無法確知特征點的各向同性鄰域包含的各向異性子鄰域的個數，所以需要用無參聚類分割法對高斯球上的數據分類。層次聚類和均值漂移算法是兩種常用的無參聚類法，對特征空間中的樣本點進行聚類時，無需指定聚類數目。均值漂移法對高斯球上的數據分割時容易產生多個聚類數目，每個類包含的點的個數少，使聚類結果不準確，因而，本文采用層次聚類法對數據分類。

假設特征點xi的Kb鄰域組成的數據集合為：Psub={xi,i=1,2,…,Kb}，則高斯球上的數據集表示為：

G(Psub)={g(x),x∈Psub}={ni,i=1,2,…,Kb}

式中：g(x)為點x的法向量，ni為點集Psub中第i個點的法向量，經過高斯映射后為高斯球上的第i個點。層次聚類分為凝聚和分裂聚類，本文采用凝聚層次聚類，該方法對數據樣本聚類時將每個點作為一個單獨的數據簇，合并這些原子數據簇為越來越大的簇，直到滿足終止條件，且以平均距離為度量準則合并數據。簇間平均距離Dc表示為：

(4)

式中：|C1|、|C2|分別表示類C1、C2點的數量。d(ni,nj)為高斯球上ni、nj間的歐氏距離。且：

d(ni,nj)=2(1-〈nix,niy〉)

高斯球上點ni、nj的值為一行三列的單位向量，因此〈nix,niy〉表示單位法向量的內積nix、niy，當高斯球上的歐式距離小于T時合并為同類，即，樣本數據的距離小于T=2(1-cosθ)時合并為同類數據簇，θ為法向量的夾角。高斯球上聚類結果對應為特征點k鄰域點云分割結果，選取包含數據點最多的一個聚類對應的點云為所求鄰域。

2 實驗結果與分析

2.1 參數選擇

本文點云鄰域搜索算法中有4個參數需要用戶設定(其他參數均為默認值)，分別為特征點檢測閾值Thresh、點云的KD樹鄰域的k值、特征點Kb鄰域和層次聚類合并閾值θ。

(1)Thresh需要用戶設定，參考值為0.01。

(2) 建立KD樹，由用戶選取點云的k鄰域，當點云為平坦點，k鄰域即為點云的各向異性鄰域。

(3)Kb是特征點進行高斯映射的鄰域，需要將Kb鄰域分割來獲得最優(yōu)鄰域，Kb的大小與k有關，本文取Kb=3k。因為特征點至少是兩個曲面的交叉形成，為了使特征點的鄰域大小與平坦點的鄰域盡可能一致，需要根據曲面的復雜度來設定Kb值。例如，若點云的特征點由兩個以上曲面交叉形成，可以取Kb=2k，若點云的特征點由三個以上曲面交叉形成，可以取Kb=3k，依次類推，本文默認取Kb=3k，且k=16。

(4)θ為高斯球上法向量夾角，當高斯球上兩點的距離小于2(1-cosθ)時合并為同類數據簇。θ值影響各向同性鄰域被分割為子鄰域的個數。當點云及其鄰域為平坦點，點云法向量接近平行，法向量之間的夾角比較小，因而，平坦區(qū)域點云鄰域映射為高斯球上一個密集分布的數據簇。當兩點的法向量夾角比較大，這兩點一般來自兩片不同的連續(xù)曲面，而且不連續(xù)曲面的特征區(qū)域的曲面越尖銳，法向量之間的夾角越大，即高斯球上的距離越大。當θ設為較小的值，特征點的各向同性鄰域被分割為許多個小的各向異性鄰域，當θ設為較大值，被分割后的鄰域仍然是各向同性。文獻[12-13]在測量估算法向量準確性時，計算標準法向量與測量法向量的夾角，當兩者的夾角小于10°時認為該點為平坦點；當兩者的夾角大于10°時，認為該點為特征點。考慮到估算的點云模型法向量與標準法向量存在一定的偏差，并受文獻[12-13]的啟發(fā)，本文將θ值設為10°，即當高斯球上簇與簇之間或者點與點之間的距離小于0.173(T=0.173)時合并為同類。

2.2 點云鄰域應用

為了驗證算法的有效性，對所求點云鄰域進行實例驗證，并且將本文搜索的鄰域和其他方法搜索的鄰域進行比較，如KD樹[8]和柵格[4]鄰域。采用C++語言編程在Microsoft visual studio 2015上實現點云鄰域搜索和其他相關算法。由于點云的鄰域難以直接可視化，本文將點云的鄰域進行實例應用，即將不同鄰域用于點云數據處理中，如點云法矢估計、點云去噪等。比較過程中除了輸入的點云鄰域不同，同一應用中的各個參數均相同。

2.2.1 鄰域在法向量估算中的應用

鄰域擬合法準確估計法向量的前提是用來擬合切平面的鄰域來自同一片連續(xù)的曲面上。將KD樹、柵格法和本文方法搜索得到鄰域采用最小二乘法分別擬合切平面?；趲追N不同鄰域對八面體和經典的Fandisk點云模型估算點云法向量，法向量可視化結果如圖4、圖5所示。為了便于觀察，對點云模型三角化顯示，并且將法向量調整為一致方向，大小歸一化。圖4、圖5中的(b-d)是幾種鄰域應用比較結果。柵格法和KD樹法搜索到的鄰域在平坦區(qū)域可以比較準確地擬合點云對應的切平面，從而估算的法向量比較準確。然而，在特征區(qū)域，特征點的鄰域位于不同的連續(xù)曲面上，擬合的切平面不準確，從而法向量不準確。本文方法搜索得到的鄰域在平坦區(qū)域即為KD樹搜索的鄰域，在特征區(qū)域特征點的各向同性鄰域被分割，得到的是各向異性鄰域，從而擬合的切平面比較準確，估算的法向量幾乎垂直點云所在的局部曲面，如圖4(d)、圖5(d)所示。

(a) 八面體三角化模型(b) KD樹鄰域

(c) 柵格鄰域 (d) 本文方法鄰域圖4 基于不同鄰域八面體點云法向量估計結果比較

(a) Fandisk三角化模型 (b) KD樹鄰域

(c) 柵格鄰域 (d) 本文方法鄰域圖5 基于不同鄰域Fandisk模型法向量估計結果比較

2.2.2 鄰域在點云去噪中的應用

雙邊濾波去噪法在去噪的同時能夠比較有效地保留點云模型的尖銳特征，但是需要比較準確的點云法矢和點云鄰域。雙邊濾波去噪法最早被用于特征保持的二維圖像去噪，Fleishman等將雙邊濾波方法引入到三維網格光順[16]，該算法也同樣適用于離散點云去噪。

雙邊濾波方法定義為：

x′=x+dn

(5)

式中，x為原始點云，x′為濾波后的點云，n為法向量，d為雙邊濾波因子，且:

(6)

基于不同鄰域對鑄件和鋼軌點云雙邊濾波去噪，此時Nb(x)分別表示KD樹鄰域、柵格鄰域和本文方法所求鄰域?；谌N不同鄰域的雙邊濾波去噪結果如圖6、圖7所示。圖6、圖7兩種點云模型都包含了非常明顯的尖銳邊界特征(多個不連續(xù)曲面交界處)，為了突出去噪效果，對無噪聲模型添加不同程度的噪聲，對噪聲點云去噪，并計算去噪產生的處理誤差。圖6、圖7的(e-f)分別是基于三種不同鄰域去噪結果。表1展示了基于三種不同鄰域雙邊濾波器去噪的誤差。由圖6、圖7和表1可知，基于本文方法的鄰域去噪產生的誤差最小，并且特征保留效果更好。

(a) 噪聲點云數據 (b) 無噪聲模型

(c) 加噪模型 (d) 柵格鄰域

(e) KD樹鄰域 (f) 本文方法鄰域圖6 基于不同鄰域鑄件點云模型去噪結果

(a) 噪聲點云數據 (b) 無噪聲模型

(c) 加噪模型 (d) 柵格鄰域

(e) KD樹鄰域 (f) 各向異性鄰域圖7 基于不同鄰域鋼軌點云模型去噪結果

2.3 不同鄰域搜索方法耗時分析

實驗所用的計算機配置為Intel Core i7-6500,2.50 GHz CPU，16 GB內存。對Fandisk，八面體、鑄件和鋼軌點云模型進行鄰域搜索，不同方法搜索鄰域耗時比較如表2所示。當點云模型處處光滑，不包含特征點時本文方法所求鄰域即為kd鄰域。當點云模型包含特征點，需要對KD數構造的鄰域進行分割，相比于柵格法和KD樹方法，本文方法搜索鄰域耗時最長。

表2 點云鄰域計算耗時比較

3 結 語

包含尖銳特征的點云模型鄰域在特征區(qū)域點云鄰域各向同性，本文對特征模型的各向異性搜索方法進行了研究。采用KD樹方法快速搜索點云鄰域，檢測點云特征點尋找各向同性鄰域，估算點云法向量，將各向同性鄰域的法向量映射到高斯球，在高斯球上對各向同性鄰域分割得到各向異性子鄰域。將本文方法搜索的鄰域與KD樹和柵格法搜索的鄰域進行了比較，本文方法搜索的鄰域對點云數據處理(法向量估算和點云去噪)結果更準確，但是算法的復雜度更高，從而更耗時。在對復雜點云曲面重建或者去噪等領域，需要更好地保留原始點云模型的尖銳特征時可以采用本文方法來搜索鄰域。本文算法有多個參數需要用戶設定，今后工作中將在自適應和計算效率方面對點云鄰域深入探討。