復(fù)雜型面點(diǎn)云的法向特征聚類分級(jí)估計(jì)方法

孫殿柱,沈江華,汪思騰,李延瑞,林 偉

(1.山東理工大學(xué) 機(jī)械工程學(xué)院,山東 淄博 255049；2.西安交通大學(xué) 機(jī)械工程學(xué)院，陜西 西安 710049)

0 引言

點(diǎn)云的法向信息是三維模型不可或缺的屬性，法向估計(jì)的準(zhǔn)確性和一致性直接影響點(diǎn)云配準(zhǔn)[1-2]、精簡[3-4]和曲面重建[5-6]等后期處理的準(zhǔn)確性。隨著點(diǎn)云數(shù)據(jù)在逆向工程、工業(yè)制造及醫(yī)學(xué)可視化等領(lǐng)域的應(yīng)用，復(fù)雜型面采樣點(diǎn)云，特別是含棱邊特征點(diǎn)云法向估計(jì)的精確度問題一直倍受關(guān)注[7-8]。

目前，應(yīng)用最廣泛的法向估計(jì)算法為Hoppe等[9]提出的點(diǎn)云微切平面估計(jì)法，其主要思想是用樣點(diǎn)的k-鄰域計(jì)算其最小二乘意義上的局部擬合平面，將擬合平面的法向作為點(diǎn)云的法向。為進(jìn)一步提高法向估計(jì)的準(zhǔn)確性，Pauly等[10]在其提出的散亂點(diǎn)云曲面建模中，采用移動(dòng)最小二乘表面定義中的局部參考平面估計(jì)樣點(diǎn)的法向；Gross等[11]為樣點(diǎn)的鄰域點(diǎn)集賦予高斯權(quán)重，使距離樣點(diǎn)越近的鄰域點(diǎn)對(duì)法向估計(jì)的影響越大，距離越遠(yuǎn)的鄰域點(diǎn)影響越??；Yoon等[12]對(duì)樣本進(jìn)行多次隨機(jī)采樣得到若干個(gè)相互覆蓋的子集，將基于各子集估算的樣點(diǎn)法向均值作為樣點(diǎn)的最終法向。然而，因?yàn)辄c(diǎn)云微切平面估計(jì)法及其改進(jìn)算法均將歐氏距離搜索的樣本作為平面擬合數(shù)據(jù)，所以在后期處理的曲面重建過程會(huì)將尖銳特征平滑掉，為提高棱邊尖銳特征區(qū)域點(diǎn)云法向估計(jì)的準(zhǔn)確性，王醒策等[13]通過Hoppe算法獲取初始法向，然后改進(jìn)移動(dòng)最小二乘曲面重建算法實(shí)現(xiàn)局部曲面擬合，以重建的網(wǎng)格面片作為樣點(diǎn)法向；孫殿柱等[14]提出一種以有界泊松曲面逼近局部樣本作為約束的樣點(diǎn)法向加權(quán)估計(jì)算法，通過泊松曲面逼近樣本點(diǎn)，用有界泊松曲面離散網(wǎng)格中距樣點(diǎn)最近的網(wǎng)格面片作為樣點(diǎn)的參考面片，并基于頂點(diǎn)鄰域面的正則度及鄰域面到該頂點(diǎn)的測地距離估計(jì)參考面片頂點(diǎn)法向，將參考面片各頂點(diǎn)法向的加權(quán)求和結(jié)果作為樣點(diǎn)最終法向；Mura等[15]對(duì)樣點(diǎn)局部鄰域進(jìn)行離散化，選擇距鄰域中心最近的樣點(diǎn)，以其法向修正初始經(jīng)由Hoppe算法估計(jì)的法向；Cao等[16]通過最大化鄰域結(jié)構(gòu)一致性對(duì)局部樣本進(jìn)行漂移獲取樣點(diǎn)的各向同性鄰域，可提高棱邊樣點(diǎn)鄰域樣本搜索的準(zhǔn)確性，避免棱邊區(qū)域樣點(diǎn)法向被平滑處理。

現(xiàn)有的點(diǎn)云法向估計(jì)算法對(duì)實(shí)物表面采樣數(shù)據(jù)所作的主要假設(shè)是數(shù)據(jù)來自光滑曲面，即任一樣點(diǎn)的歐氏近鄰點(diǎn)集構(gòu)成的曲面樣本所呈現(xiàn)的形貌近似平面，這一假設(shè)對(duì)含有棱邊(或小半徑圓角)和尖角等特征的曲面樣本無效。在工業(yè)設(shè)計(jì)領(lǐng)域，有許多產(chǎn)品的數(shù)字模型是基于曲面求交、裁剪、倒角等建模過程構(gòu)造的復(fù)合曲面模型，對(duì)于該類產(chǎn)品的實(shí)物表面采樣數(shù)據(jù)，在特征區(qū)域，若將曲面局部樣本所體現(xiàn)的形貌視為平面，則將導(dǎo)致樣點(diǎn)的法向和曲率等微分幾何量的估計(jì)結(jié)果與真實(shí)情況存在較大偏差。

針對(duì)上述問題，本文提出一種基于曲面形貌聚類優(yōu)化的點(diǎn)云法向估計(jì)方法。首先，基于曲面局部平坦性和貝葉斯信息準(zhǔn)則對(duì)每個(gè)樣點(diǎn)鄰域構(gòu)成的曲面局部樣本進(jìn)行聚類分析，將曲面采樣點(diǎn)云劃分為平坦區(qū)域、特征邊緣、棱邊區(qū)域和尖角區(qū)域等類別；然后，估計(jì)平坦區(qū)域樣點(diǎn)的法向，以該類樣點(diǎn)的法向作為確定性最高的初始法向；最后，將平坦區(qū)域樣點(diǎn)法向向鄰近特征區(qū)域樣點(diǎn)分級(jí)傳播，實(shí)現(xiàn)特征樣點(diǎn)的法向估計(jì)。本文方法對(duì)復(fù)雜型面樣點(diǎn)的分類與曲面形貌一致，可有效提高特征邊緣樣點(diǎn)法向估計(jì)結(jié)果的準(zhǔn)確性，并能保證棱邊和尖角區(qū)域樣點(diǎn)法向具有多義性。

1 曲面樣本分類

設(shè)S為曲面采樣點(diǎn)云，對(duì)于任一樣點(diǎn)p∈S，可基于S的空間索引(kd樹、空間八叉樹或R樹皆可)[17]從S中搜索距離p最近的k個(gè)樣點(diǎn)，并將其與p所構(gòu)成的點(diǎn)集作為以p為中心的曲面局部樣本λ(p)。

若S來自光滑曲面，則可采用平面逼近λ(p)的方法估計(jì)p的法向，然而對(duì)于形貌復(fù)雜的曲面采樣點(diǎn)云，如圖1所示的渦輪發(fā)動(dòng)機(jī)輪盤點(diǎn)云，在棱邊特征區(qū)域，λ(p)包含來自兩張曲面的樣點(diǎn)，亦即在理論上p有兩個(gè)法向，僅以單張平面逼近λ(p)來估計(jì)p的法向會(huì)導(dǎo)致錯(cuò)誤的結(jié)果。含有小圓角特征的曲面局部樣本也存在類似問題。因此，為提高復(fù)雜型面采樣點(diǎn)云法向估計(jì)結(jié)果的準(zhǔn)確性，必須對(duì)樣點(diǎn)所處區(qū)域?qū)?yīng)的曲面特征進(jìn)行識(shí)別和分類，然后針對(duì)特定類別對(duì)樣點(diǎn)的法向估計(jì)結(jié)果進(jìn)行優(yōu)化。

復(fù)雜型面的形貌復(fù)雜性可基于曲面上任意一點(diǎn)的曲率作量化分析，然而對(duì)曲面采樣點(diǎn)云而言，其中任一樣點(diǎn)與其周圍樣點(diǎn)不存在任何拓?fù)浜蛶缀我饬x上的鄰接關(guān)系。對(duì)曲面采樣點(diǎn)云S中的任一樣點(diǎn)p所處區(qū)域?qū)?yīng)的曲面特征進(jìn)行識(shí)別和分類的前提是，為λ(p)的形貌復(fù)雜性構(gòu)造與曲面形貌一致的量化模型。

復(fù)雜型面上的棱邊和尖角等特征區(qū)域有別于平坦區(qū)域，對(duì)于后者，可基于λ(p)擬合平面γ(p)，用λ(p)中的樣點(diǎn)到γ(p)的殘差衡量λ(p)形貌的平坦程度。設(shè)λ(p)中所有樣點(diǎn)到γ(p)的殘差平方和為χ(p)，用閾值ε區(qū)分λ(p)的形貌是否平坦，若χ(p)≤ε，則λ(p)形貌為平坦；若χ(p)>ε，則為不平坦，將λ(p)視為處于小圓角、棱邊或尖角等特征區(qū)域。因此，基于ε可實(shí)現(xiàn)對(duì)曲面采樣點(diǎn)云S中平坦區(qū)域樣點(diǎn)與非平坦區(qū)域樣點(diǎn)的分離，設(shè)結(jié)果分別為S1和S2。為便于描述，將χ(p)稱為λ(p)的形貌特征值。

對(duì)于p∈S2，可繼續(xù)基于ε對(duì)其所處特征區(qū)進(jìn)行細(xì)化識(shí)別。假設(shè)p處于棱邊區(qū)域，若將λ(p)中所有形貌特征值大于ε的樣點(diǎn)全部剔除，則可得點(diǎn)集λ′(p)。若λ′(p)非空，則因λ(p)中被剔除的樣點(diǎn)集中于曲面的棱邊區(qū)域，而且λ′(p)中的樣點(diǎn)主要分布于棱邊區(qū)域兩側(cè)的平坦區(qū)域，所以在歐氏空間中只需對(duì)λ′(p)進(jìn)行聚類劃分，便可分離不同平坦區(qū)域的樣點(diǎn)，如圖2所示。若λ′(p)被劃分為兩類，則認(rèn)為p處于棱邊區(qū)域；同理，若劃分結(jié)果多于兩類，則可認(rèn)為p處于尖角區(qū)域。關(guān)鍵問題在于，如何確定λ′(p)聚類劃分結(jié)果的數(shù)量。

假設(shè)λ′(p)的聚類結(jié)果為C={C1,C2,…,Cm}，m值取決于C的聚類最優(yōu)性。若采用k均值聚類算法[18]對(duì)λ′(p)進(jìn)行劃分，則可基于貝葉斯信息準(zhǔn)則(Bayesian Information Criterion，BIC)[19]估計(jì)C的聚類優(yōu)性。對(duì)于λ′(p)任一候選的聚類劃分結(jié)果Ci={Ci1,Ci2,…,Cim}，其聚類優(yōu)性可量化為

B(Ci)=2logL(mi|Ci)-dlog|λ′(p)|。

(1)

式中：L(mi|Ci)為似然函數(shù)；d為樣點(diǎn)數(shù)據(jù)維度(文中d=3)；|λ′(p)|為λ′(p)包含樣點(diǎn)的個(gè)數(shù)。定義

(2)

2 特征樣點(diǎn)法向估計(jì)

若樣點(diǎn)p處于曲面平坦區(qū)域，即χ(p)≤ε，則γ(p)的法向便可作為p的法向估計(jì)結(jié)果。值得探討的是，當(dāng)p處于曲面上的特征區(qū)域時(shí)，其法向如何確定。

基于上述分析，設(shè)曲面采樣點(diǎn)云S中法向確定的樣點(diǎn)所構(gòu)成的集合為P={p1,p2,…,pn}，將特征邊緣樣點(diǎn)、棱邊區(qū)域樣點(diǎn)、尖角區(qū)域樣點(diǎn)分別賦以級(jí)別編號(hào)1，2，3，則樣點(diǎn)法向確定性的傳播過程如下：

(1)h←1。

(4)從P中剔除pi。

(5)重復(fù)(2)～(4)，直到P中不存在級(jí)別為h的樣點(diǎn)。

(6)h←h+1。

(7)重復(fù)上述步驟，直到P為空集。

對(duì)于棱邊區(qū)域或尖角區(qū)域的任一樣點(diǎn)，上述過程為其估計(jì)的法向并不唯一，每個(gè)棱邊區(qū)域樣點(diǎn)有兩個(gè)法向，每個(gè)尖角區(qū)域樣點(diǎn)有3個(gè)甚至更多法向，這種結(jié)果與曲面棱邊和尖角特征相符，即棱邊為兩張光滑曲面的交線，而尖角為多張光滑曲面的交點(diǎn)，因此棱邊樣點(diǎn)和尖角樣點(diǎn)的法向必定具有多義性?，F(xiàn)有的曲面采樣點(diǎn)云法向估計(jì)算法通常忽視了該性質(zhì)，為棱邊區(qū)域和尖角區(qū)域樣點(diǎn)所估計(jì)的法向通常近似為多義性法向的合向量，這種單一的法向并不合理。

3 算例

為驗(yàn)證本文法向估計(jì)結(jié)果的準(zhǔn)確性，在硬件配置為Inter(R)Xeon(R)CPU 5120，1.86 GHz，2.0 GB內(nèi)存，GNU/Linux操作系統(tǒng)環(huán)境下，采用Mura算法、Cao算法和本文算法對(duì)不同點(diǎn)云模型進(jìn)行實(shí)驗(yàn)。如圖4所示，輪盤、顯微鏡、鋼琴模型均含有棱邊和尖角等復(fù)雜特征。

如圖5所示，對(duì)輪盤模型的三維點(diǎn)云數(shù)據(jù)進(jìn)行法向估計(jì)實(shí)驗(yàn)，由于點(diǎn)云分布較均勻，實(shí)驗(yàn)中設(shè)置k=10，從點(diǎn)云中隨機(jī)抽取1 000個(gè)采樣點(diǎn)并搜索每個(gè)采樣點(diǎn)的k近鄰，對(duì)于每一采樣點(diǎn)，計(jì)算其與鄰域中最遠(yuǎn)點(diǎn)的距離，然后將1 000個(gè)采樣點(diǎn)的距離平方和求平均，用該平均值區(qū)分平坦與非平坦區(qū)域的閾值，即ε=0.03。計(jì)算樣點(diǎn)的鄰域到其局部擬合平面的殘差平方和，并將大于ε的樣點(diǎn)歸為非平坦區(qū)域，非平坦區(qū)域的識(shí)別結(jié)果如圖5a所示；對(duì)于非平坦區(qū)域中的任一樣點(diǎn)，剔除其鄰域中的非平坦區(qū)域點(diǎn)，并將剩余點(diǎn)進(jìn)行聚類分析，基于分類數(shù)量將其劃分為尖角、棱邊、特征邊緣區(qū)域，分別如圖5b～圖5d所示，圖5e是去除尖角、棱邊、特征邊緣等特征的平坦區(qū)域。在計(jì)算法向過程中，首先采用主元分析算法計(jì)算平坦區(qū)域樣點(diǎn)的法向，然后以平坦區(qū)域樣點(diǎn)為初始法向，逐級(jí)向特征邊緣、棱邊、尖角區(qū)域樣點(diǎn)傳播，各區(qū)域的法向估計(jì)結(jié)果如圖5f～圖5i所示，特征區(qū)域樣點(diǎn)的法向估計(jì)結(jié)果與其鄰近平坦區(qū)域樣點(diǎn)的法向保持一致，圖5j所示為輪盤模型全部樣點(diǎn)的法向。

采用Mura算法、Cao算法和本文算法對(duì)圖4c所示含有棱邊、圓角且采樣不均勻的鋼琴模型進(jìn)行法向估計(jì)，結(jié)果如圖6所示。3種算法在圓角特征區(qū)域的法向無明顯區(qū)別，但是在棱邊區(qū)域，本文算法樣點(diǎn)的法向估計(jì)結(jié)果準(zhǔn)確，棱邊上的樣點(diǎn)存在多義性法向，且多義性法向的夾角近似為鄰接面的夾角；Mura算法出現(xiàn)法向光滑過渡現(xiàn)象；Cao算法棱邊區(qū)域法向雖未被完全平滑處理，但法向準(zhǔn)確性明顯低于本文算法。

為進(jìn)一步展示本文算法在棱邊和尖角區(qū)域樣點(diǎn)法向計(jì)算的準(zhǔn)確性，將圖4b中含有大量棱邊和尖角特征的顯微鏡模型作為實(shí)驗(yàn)對(duì)象進(jìn)行實(shí)驗(yàn)。圖7所示為不同算法在其中一特征區(qū)域的法向計(jì)算局部放大圖，圖中的特征區(qū)域由3個(gè)平面相交產(chǎn)生，Mura算法和Cao算法棱邊區(qū)域樣點(diǎn)的法向在一定程度上被平滑處理，本文算法則能準(zhǔn)確識(shí)別特征區(qū)域樣點(diǎn)所屬的平面，其法向估計(jì)結(jié)果與鄰近平坦區(qū)域樣點(diǎn)的法向保持一致，從圖中可見，鄰接面上相近的兩點(diǎn)法向夾角近乎為兩平面夾角，而且尖角點(diǎn)存在3個(gè)方向的法向。

為測試法向估計(jì)的穩(wěn)健性，需對(duì)法向估計(jì)結(jié)果進(jìn)行定量分析，故基于法向偏差均方根(Root Mean Square，RMS)統(tǒng)計(jì)棱邊和尖角區(qū)域樣點(diǎn)法向估計(jì)誤差，其中RMS的計(jì)算公式為

(3)

f(〈nref,nest〉)=

(4)

式中：nref和nest分別為單位標(biāo)準(zhǔn)法向和估計(jì)法向；|S|為曲面采樣點(diǎn)的總數(shù)量；τ為角度閾值，根據(jù)文獻(xiàn)[20]取τ=π/18。

圖4a中輪盤模型的點(diǎn)數(shù)為53 720，將其分別添加0，15%，25%，35%的高斯噪聲，其中高斯噪聲的標(biāo)準(zhǔn)差為0.01，利用Mura算法、Cao算法和本文算法對(duì)該點(diǎn)云在不同噪聲下進(jìn)行樣點(diǎn)法向計(jì)算，統(tǒng)計(jì)3種算法所得結(jié)果的RMS值和法向出錯(cuò)樣點(diǎn)數(shù)量Nbad-point，結(jié)果如表1所示，可見Cao算法和Mura算法所得法向出錯(cuò)樣點(diǎn)數(shù)量隨噪聲含量的增大而明顯增大。對(duì)于噪聲含量為25%的數(shù)據(jù)，3種算法所得結(jié)果及法向出錯(cuò)樣點(diǎn)如圖8所示，Cao算法和Mura算法估計(jì)結(jié)果中的法向出錯(cuò)樣點(diǎn)數(shù)量較多，主要分布于棱邊和尖角區(qū)域，而本文算法估計(jì)結(jié)果僅存在少量法向出錯(cuò)樣點(diǎn)。

表1 3種算法在不同噪聲下的法向出錯(cuò)樣點(diǎn)數(shù)和RMS值

為進(jìn)一步測試法向計(jì)算的準(zhǔn)確性，以25%高斯噪聲下計(jì)算的法向?yàn)槔ㄟ^堆積圖統(tǒng)計(jì)3種算法計(jì)算結(jié)果中法向出錯(cuò)樣點(diǎn)的法向與其標(biāo)準(zhǔn)法向的角度偏差，結(jié)果如圖9所示?？梢姡?種算法的法向出錯(cuò)樣點(diǎn)主要集中在10°～18°角度偏差范圍內(nèi)，所占比例均超過50%，Mura算法、Cao算法和本文算法的比例分別為76.04%，81.76%，83.56%，本文算法角度偏差超過34°的法向出錯(cuò)樣點(diǎn)的數(shù)量可以忽略不計(jì)。

4 結(jié)束語

本文提出一種針對(duì)含有棱邊和尖角等特征的曲面采樣點(diǎn)云法向估計(jì)方法，基于平坦區(qū)域樣點(diǎn)法向的估計(jì)結(jié)果，逐級(jí)確定特征邊緣、棱邊區(qū)域和尖角區(qū)域樣點(diǎn)的法向，該方法具有以下特點(diǎn)：

(1)基于樣點(diǎn)對(duì)應(yīng)曲面局部樣本平面擬合結(jié)果的殘差值，從點(diǎn)云中任一樣點(diǎn)對(duì)應(yīng)的曲面局部樣本中剔除非平坦區(qū)域樣點(diǎn)，從而使剩余的曲面局部樣本數(shù)據(jù)具有可聚類性，可將曲面局部樣本所屬特征區(qū)域的識(shí)別問題轉(zhuǎn)化為更加簡單的k均值聚類分析問題。

(2)采用貝葉斯信息準(zhǔn)則對(duì)特征區(qū)域的聚類優(yōu)性進(jìn)行量化，基于最優(yōu)聚類劃分結(jié)果的分類數(shù)量可準(zhǔn)確推斷樣點(diǎn)所屬特征區(qū)域的類型。

(3)基于平坦區(qū)域樣點(diǎn)的法向估計(jì)結(jié)果，逐級(jí)確定特征邊緣、棱邊區(qū)域和尖角區(qū)域樣點(diǎn)的法向，可提高特征區(qū)域樣點(diǎn)法向估計(jì)結(jié)果的正確性，能保證棱邊區(qū)域和尖角區(qū)域樣點(diǎn)法向具有多義性，且對(duì)數(shù)據(jù)噪聲具有抑制作用。

對(duì)于復(fù)雜型面采樣點(diǎn)云，特征區(qū)域樣點(diǎn)法向的多義性通常會(huì)破壞以曲面光滑為前提的法向一致性傳播過程，導(dǎo)致各塊平坦區(qū)域樣點(diǎn)法向難以獲得統(tǒng)一，擬對(duì)該問題進(jìn)行進(jìn)一步研究。