尖銳特征曲面點(diǎn)云模型各向異性鄰域搜索

袁小翠 陳華偉

1(南昌工程學(xué)院江西精密驅(qū)動(dòng)與控制重點(diǎn)實(shí)驗(yàn)室 江西 南昌 330099)2(貴州師范大學(xué)機(jī)械與電氣工程學(xué)院 貴州 貴陽 550025)

0 引 言

三維掃描儀可以快速獲取物體表面的三維信息，對(duì)三維點(diǎn)云數(shù)據(jù)處理可以實(shí)現(xiàn)曲面重建和產(chǎn)品再制造等應(yīng)用。然而，三維掃描儀獲取的數(shù)據(jù)一般只有三維坐標(biāo)信息，無任何拓?fù)浣Y(jié)構(gòu)，點(diǎn)云數(shù)據(jù)處理時(shí)需要以點(diǎn)云的鄰域?yàn)榛A(chǔ)。點(diǎn)云鄰域的準(zhǔn)確性直接影響點(diǎn)云處理結(jié)果，如法向量估計(jì)、去噪和曲面重建等。

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

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

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

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

1 鄰域搜索方法

1.1 法矢估計(jì)及特征點(diǎn)檢測(cè)

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

(1)

C被分解為三個(gè)特征向量：v2、v1、v0。三個(gè)特征向量對(duì)應(yīng)的特征值分別為λ2、λ1、λ0，其中λ2≥λ1≥λ0。λ0對(duì)應(yīng)的特征向量v0即為切平面法向量。

點(diǎn)的曲面變化表示為：

(2)

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

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

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

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

(3)

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

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

(a) PCA方法估計(jì)的法向量 (b) 修正后的法向量圖2 Fandisk點(diǎn)云模型法向量修正結(jié)果

1.2 各向同性鄰域分割

點(diǎn)云高斯映射[15]的目的是將特征點(diǎn)的各向同性鄰域映射到高斯球上形成不同的數(shù)據(jù)簇。

高斯映射的特點(diǎn)：如果點(diǎn)云模型是一連通的平面，則該連通平面上的點(diǎn)云映射為高斯球上的一點(diǎn)；反之，如果點(diǎn)云模型的高斯圖為高斯球上的一點(diǎn)，則該點(diǎn)云模型為一平面[15]。然而，估算的點(diǎn)云法向量與標(biāo)準(zhǔn)法向量總是存在一定的偏差，所以連通平面的點(diǎn)云映射為高斯球上密集的一個(gè)數(shù)據(jù)簇。

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

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

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

假設(shè)特征點(diǎn)xi的Kb鄰域組成的數(shù)據(jù)集合為：Psub={xi,i=1,2,…,Kb}，則高斯球上的數(shù)據(jù)集表示為：

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

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

(4)

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

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

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

2 實(shí)驗(yàn)結(jié)果與分析

2.1 參數(shù)選擇

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

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

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

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

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

2.2 點(diǎn)云鄰域應(yīng)用

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

2.2.1 鄰域在法向量估算中的應(yīng)用

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

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

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

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

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

2.2.2 鄰域在點(diǎn)云去噪中的應(yīng)用

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

雙邊濾波方法定義為：

x′=x+dn

(5)

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

(6)

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

(a) 噪聲點(diǎn)云數(shù)據(jù) (b) 無噪聲模型

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

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

(a) 噪聲點(diǎn)云數(shù)據(jù) (b) 無噪聲模型

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

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

2.3 不同鄰域搜索方法耗時(shí)分析

實(shí)驗(yàn)所用的計(jì)算機(jī)配置為Intel Core i7-6500,2.50 GHz CPU，16 GB內(nèi)存。對(duì)Fandisk，八面體、鑄件和鋼軌點(diǎn)云模型進(jìn)行鄰域搜索，不同方法搜索鄰域耗時(shí)比較如表2所示。當(dāng)點(diǎn)云模型處處光滑，不包含特征點(diǎn)時(shí)本文方法所求鄰域即為kd鄰域。當(dāng)點(diǎn)云模型包含特征點(diǎn)，需要對(duì)KD數(shù)構(gòu)造的鄰域進(jìn)行分割，相比于柵格法和KD樹方法，本文方法搜索鄰域耗時(shí)最長(zhǎng)。

表2 點(diǎn)云鄰域計(jì)算耗時(shí)比較

3 結(jié) 語

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