史紅霞 王建民

太原理工大學(xué)礦業(yè)工程學(xué)院，太原，030024

0 引言

隨著三維掃描技術(shù)的飛速發(fā)展，點(diǎn)云模型已成為幾何模型的通用表示形式，并廣泛應(yīng)用于計(jì)算機(jī)可視化、逆向工程、三維重建、文物保護(hù)等領(lǐng)域[1-5]。特征是反映點(diǎn)云模型幾何外觀的最小基元，可精準(zhǔn)地表達(dá)三維模型表面特性和幾何形狀[1]，因此，特征提取已成為點(diǎn)云數(shù)據(jù)處理中的一個(gè)基礎(chǔ)環(huán)節(jié)，如何有效準(zhǔn)確地提取模型特征是當(dāng)前點(diǎn)云數(shù)據(jù)處理的關(guān)鍵。

為解決點(diǎn)云模型特征提取問(wèn)題，部分學(xué)者通過(guò)點(diǎn)云局部鄰域特性及幾何特征提取模型特征。幾何特征主要指點(diǎn)間距離特征、角度特征及點(diǎn)云法矢、曲率等信息。文獻(xiàn)[6]采用空間距離和角度特性提取車(chē)輛行駛道路和礦井道路邊界，具有一定的準(zhǔn)確性，但未考慮道路障礙物的影響。文獻(xiàn)[7-8]利用點(diǎn)云法向量信息識(shí)別特征點(diǎn)，但均未考慮法向量估算的準(zhǔn)確度。文獻(xiàn)[9]通過(guò)對(duì)各點(diǎn)局部鄰域協(xié)方差矩陣特征值的區(qū)域增長(zhǎng)生成分割帶，在各分割區(qū)域內(nèi)根據(jù)主方向提取特征點(diǎn)。文獻(xiàn)[10]引入多尺度分類(lèi)算子分析局部鄰域點(diǎn)，計(jì)算不同尺度下采樣點(diǎn)成為特征點(diǎn)的概率，但多尺度使其計(jì)算效率下降。文獻(xiàn)[11]根據(jù)曲率突變點(diǎn)隱含特征點(diǎn)，設(shè)置突變點(diǎn)比率選取備選特征點(diǎn)，但由于比率具有不確定性，故可能會(huì)造成細(xì)節(jié)特征的缺失。

基于點(diǎn)云局部鄰域特性及幾何特征的方法大多依賴(lài)全局閾值進(jìn)行特征點(diǎn)識(shí)別，全局固定閾值的設(shè)置易造成特征點(diǎn)的誤判或漏判，為此，有些學(xué)者運(yùn)用聚類(lèi)分割或局部曲面網(wǎng)格重建的方法識(shí)別特征點(diǎn)。例如，文獻(xiàn)[12]對(duì)各點(diǎn)局部鄰域三角區(qū)域的單位法向量進(jìn)行高斯映射，對(duì)映射點(diǎn)進(jìn)行聚類(lèi)分析獲取特征點(diǎn)；文獻(xiàn)[13] 通過(guò)對(duì)遺跡碎片表面法向量的聚類(lèi)實(shí)現(xiàn)碎片分割，結(jié)合法向量和碎片表面粗糙度提取邊界線；文獻(xiàn)[14]對(duì)已標(biāo)記的潛在谷脊點(diǎn)構(gòu)建局部幾何特征信息三角網(wǎng)格，然后再進(jìn)行谷脊點(diǎn)識(shí)別，該方法計(jì)算復(fù)雜度較高。

上述兩類(lèi)方法均不易準(zhǔn)確完整地提取所有模型特征點(diǎn)，尤其是模型過(guò)渡特征。為此，有些學(xué)者引入數(shù)學(xué)形態(tài)學(xué)[15]、投影映射[16]、切片技術(shù)[17]、神經(jīng)網(wǎng)絡(luò)[18]、張量投票理論[19]等方法，使某些模型特征提取效果達(dá)到最優(yōu)。

本文針對(duì)現(xiàn)有模型過(guò)渡線及細(xì)節(jié)特征線提取不完整問(wèn)題，基于區(qū)域分割思想進(jìn)行特征線提取，在綜合利用主成分分析(principal component analysis,PCA)法、螢火蟲(chóng)算法[20](firefly algorithm,FA)和模糊C均值(fuzzy C-mean, FCM)聚類(lèi)算法[21]對(duì)點(diǎn)云模型進(jìn)行聚類(lèi)分割的基礎(chǔ)上，將各分割塊邊界點(diǎn)作為備選點(diǎn)集識(shí)別特征點(diǎn)，采用三次B樣條法擬合生成特征線[22]。

1 FCM聚類(lèi)算法

已知n個(gè)l維空間數(shù)據(jù)集S={s1,s2,…,sj,…,sn}?Rl，將數(shù)據(jù)集S劃分為c(2≤c≤n)個(gè)子集，即聚類(lèi)數(shù)為c，各子集聚類(lèi)中心C={C1,C2,…,Ci,…,Cc}。最佳聚類(lèi)準(zhǔn)則是極小化目標(biāo)函數(shù)值，使具有相似特征的數(shù)據(jù)點(diǎn)聚為一類(lèi)。目標(biāo)函數(shù)Jm的一般定義如下：

(1)

dij=‖sj-Ci‖Uij∈[0,1]

式中，dij為空間數(shù)據(jù)集S中第j個(gè)樣本點(diǎn)sj與第i個(gè)聚類(lèi)中心Ci的歐氏距離；m為模糊加權(quán)指數(shù)；Uij為第j個(gè)樣本點(diǎn)屬于第i個(gè)聚類(lèi)中心的隸屬度。

目標(biāo)函數(shù)Jm取極小值的約束條件是

最小化Jm過(guò)程中，可運(yùn)用下式計(jì)算隸屬度和更新聚類(lèi)中心：

(2)

(3)

式中，dgj為空間數(shù)據(jù)集S中第j個(gè)樣本數(shù)據(jù)點(diǎn)sj與第g個(gè)聚類(lèi)中心Cg的歐氏距離。

FCM聚類(lèi)算法的基本思路就是通過(guò)不斷迭代更新隸屬度Uij和聚類(lèi)中心Ci，使目標(biāo)函數(shù)Jm最小，然后依據(jù)Jm最小時(shí)的隸屬度矩陣劃分?jǐn)?shù)據(jù)集S。

運(yùn)用常規(guī)的FCM聚類(lèi)算法對(duì)點(diǎn)云模型進(jìn)行分割進(jìn)而提取特征線時(shí)，需要考慮兩個(gè)問(wèn)題。首先，若直接利用各點(diǎn)空間坐標(biāo)信息進(jìn)行聚類(lèi)劃分，則所得模型分割線將與模型特征線無(wú)直接聯(lián)系，不易于后續(xù)特征線提取，為此，引入自適應(yīng)鄰域的主成分分析(PCA)法[23]求取模型各點(diǎn)法向，以各點(diǎn)法向量方向的接近程度為聚類(lèi)特征實(shí)現(xiàn)點(diǎn)云模型的有效分割。其次，由于初始聚類(lèi)中心選擇的隨機(jī)性以及梯度下降式的最優(yōu)解搜索法，致使算法容易陷入局部最優(yōu)，為解決這一問(wèn)題，在FCM聚類(lèi)算法中引入FA算法，利用具有全局搜索能力的FA算法為FCM聚類(lèi)算法選取最優(yōu)初始聚類(lèi)中心，有效解決其對(duì)初始值敏感及過(guò)早收斂的問(wèn)題。

2 基于法向量估計(jì)的FA-FCM組合聚類(lèi)算法

法向量是散亂點(diǎn)云模型的一個(gè)重要屬性，可用來(lái)描述模型特征信息。點(diǎn)云模型中任意采樣點(diǎn)局部區(qū)域較為平坦時(shí)，鄰域內(nèi)各點(diǎn)法向量變化平緩；相反，采樣點(diǎn)局部區(qū)域起伏變化時(shí)，各點(diǎn)法向量變化較大，因此，可估算模型法向量，進(jìn)而提取模型特征點(diǎn)。

2.1 法向量估計(jì)

目前，在常見(jiàn)的點(diǎn)云法向量估計(jì)算法中，PCA方法因其算法簡(jiǎn)單高效、穩(wěn)定性強(qiáng)而被廣泛使用。PCA算法實(shí)質(zhì)是對(duì)點(diǎn)云數(shù)據(jù)局部鄰域的主成分分析，然而，固定鄰域尺寸的選擇致使其估算結(jié)果不精確。以二維情況(三維類(lèi)似)為例，說(shuō)明因鄰域值選擇不合理而造成的法向量估算偏差問(wèn)題，如圖1所示。

圖1 局部鄰域值大小對(duì)法向量估算的影響Fig.1 Effect of neighborhood size on normal estimation

圖1中圓形區(qū)域代表鄰域范圍，虛直線代表虛線圓形鄰域內(nèi)數(shù)據(jù)擬合形成的直線，虛線箭頭表示根據(jù)虛線圓形鄰域范圍計(jì)算所得的法向量，實(shí)直線代表實(shí)線圓形鄰域內(nèi)數(shù)據(jù)擬合形成的直線，實(shí)線箭頭表示根據(jù)實(shí)線圓形鄰域范圍計(jì)算所得的法向量。圖中點(diǎn)s1為尖銳特征點(diǎn)，應(yīng)選擇較小的鄰域值擬合估算該點(diǎn)法向量，故圖中s1點(diǎn)處虛線法向量因鄰域值過(guò)大而造成偏差，而s2點(diǎn)所在區(qū)域較為平坦，只有局部略微凸起，應(yīng)選擇較大的鄰域值擬合估算該點(diǎn)法向量，故圖中s2點(diǎn)處實(shí)線法向量因鄰域值過(guò)小而造成偏差。為解決這一問(wèn)題，采用點(diǎn)云局部鄰域幾何維度特征最優(yōu)鄰域選擇法[23]查找各點(diǎn)最優(yōu)鄰域值，然后結(jié)合PCA算法估算各點(diǎn)法向。

對(duì)點(diǎn)云樣本數(shù)據(jù)集而言，空間維度l的值為3，此時(shí)，點(diǎn)云樣本數(shù)據(jù)集S={s1,s2,…,sj,…,sn}?R3，j=1,2，…,n,n為樣本總點(diǎn)數(shù)，取數(shù)據(jù)集S中任意樣本點(diǎn)s，其k近鄰域點(diǎn)集Ns={s1,s2,…,sb, …,sk}，b=1,2，…,k，點(diǎn)s的協(xié)方差矩陣可表示為

(4)

由于協(xié)方差矩陣M為對(duì)稱(chēng)正定陣，因此其特征值λ0、λ1、λ2具有非負(fù)性，同時(shí)，可用三個(gè)特征值描述樣本點(diǎn)局部鄰域維度特性，其特性如下：

(1)當(dāng)λ0?λ1,λ2>0時(shí)，局部鄰域呈線性特征分布。

(2)當(dāng)λ0,λ1?λ2>0時(shí)，局部鄰域呈平面特征分布，此時(shí)最小特征值λ2所對(duì)應(yīng)的特征向量即為鄰域點(diǎn)法向量。

(3)當(dāng)λ0≈λ1≈λ2時(shí)，局部鄰域呈三維曲面特征分布。

根據(jù)各樣本點(diǎn)局部鄰域維度特性可定義其特征模型：

(5)

式中,a1、a2、a3分別表示當(dāng)前點(diǎn)局部鄰域?yàn)榫€性(一維)、平面(二維)和曲面(三維)特征。

基于信息熵理論，依據(jù)上述維度特征模型定義點(diǎn)s的近鄰點(diǎn)數(shù)為k時(shí)信息熵函數(shù)：

(6)

結(jié)合上述基于信息熵理論的自適應(yīng)鄰域選擇法，采用PCA方法進(jìn)行法向量估算，步驟如下：

(1)對(duì)于點(diǎn)云樣本數(shù)據(jù)集S中任意采樣點(diǎn)s，設(shè)置鄰域搜索上下限值分別為kmax和kmin(kmax,kmin均表示鄰域點(diǎn)數(shù))，搜索步長(zhǎng)為1，初始化鄰域值k←kmin。

(3)設(shè)置搜索鄰域值k←k+1，當(dāng)k≤kmax時(shí)，返回步驟(2)；否則執(zhí)行下一步。

2.2 FA-FCM組合聚類(lèi)算法

為解決傳統(tǒng)FCM聚類(lèi)算法因隨機(jī)性的初始聚類(lèi)中心選擇法造成的算法過(guò)早局部收斂問(wèn)題，引入FA，將每只螢火蟲(chóng)的位置作為聚類(lèi)中心，通過(guò)比較螢火蟲(chóng)亮度值進(jìn)行算法迭代循環(huán)，從而為FCM聚類(lèi)算法尋找最優(yōu)初始聚類(lèi)中心。在已求解模型法向的基礎(chǔ)上，介紹引入FA算法后FCM聚類(lèi)算法的初始聚類(lèi)中心選擇方法。

通常情況下，模糊加權(quán)指數(shù)m為2，對(duì)點(diǎn)云模型法向量進(jìn)行聚類(lèi)劃分時(shí)，距離d(vj,Ci)和隸屬度Uij的表達(dá)如下：

(7)

(8)

則改進(jìn)后的模糊聚類(lèi)目標(biāo)函數(shù)為

(9)

FA算法是尋找亮度最亮的螢火蟲(chóng)個(gè)體，其中亮度和吸引度是該算法的兩個(gè)重要概念[24]，而FCM聚類(lèi)算法旨在尋找目標(biāo)函數(shù)最小時(shí)的聚類(lèi)中心，因此，螢火蟲(chóng)亮度值可定義為

(10)

螢火蟲(chóng)吸引度為

β=β0exp(-γr2)

(11)

式中，r為兩螢火蟲(chóng)間距離;β0為最大吸引度，即r=0時(shí)的吸引度；γ為介質(zhì)對(duì)光的吸收因子。

兩螢火蟲(chóng)A、B間距離為

(12)

i=1,2，…,c

式中，CAi、CBi分別為螢火蟲(chóng)A和螢火蟲(chóng)B的第i個(gè)聚類(lèi)中心。

螢火蟲(chóng)A受亮度較高的螢火蟲(chóng)B吸引而向B移動(dòng)，A移動(dòng)后的位置由下式?jīng)Q定：

CAi=CAi+β(CBi-CAi)+α(rand-(0.5))

(13)

式中，α為步長(zhǎng)因子，α∈[0,1]；rand是由3個(gè)隨機(jī)因子構(gòu)成的向量，在區(qū)間[0,1]上屬于均勻分布。

FA-FCM組合聚類(lèi)算法實(shí)現(xiàn)步驟如下：

(1)初始化FA算法參數(shù)β0,γ,α,c,T1，N(T1為FA算法最大迭代次數(shù)，N為螢火蟲(chóng)數(shù))及螢火蟲(chóng)位置，設(shè)置FCM算法收斂閾值ε(ε>0)。

(2)將初始化的螢火蟲(chóng)位置作為初始聚類(lèi)中心，聯(lián)合式(7)、式(8)計(jì)算隸屬度矩陣U(N×c)×(n)和距離d(vj,Ci)，聯(lián)合式(9)、(10)計(jì)算N只螢火蟲(chóng)亮度值矩陣Is(N×1)。

(3)比較各螢火蟲(chóng)亮度，聯(lián)合式(11)、式(12)、式(13)更新各螢火蟲(chóng)位置。

(4)判斷算法迭代次數(shù)是否達(dá)到T1，若是，則按式(7)～式(10)計(jì)算各螢火蟲(chóng)亮度，取最亮螢火蟲(chóng)位置為最優(yōu)初始聚類(lèi)中心；否則，返回步驟(2)，繼續(xù)迭代。

(5)確定初始聚類(lèi)中心后，使用FCM聚類(lèi)算法進(jìn)行聚類(lèi)分割，令FCM算法迭代次數(shù)t=0。

(7)按式(3)更新聚類(lèi)中心位置，此時(shí)，t←t+1。

2.3 FA-FCM聚類(lèi)有效性檢驗(yàn)

為驗(yàn)證聚類(lèi)方法的有效性,本文選取的評(píng)價(jià)指標(biāo)為類(lèi)內(nèi)緊致度Var和類(lèi)間離散度Sep[25]。

根據(jù)點(diǎn)云模型隸屬度矩陣及聚類(lèi)中心，類(lèi)內(nèi)緊致度為

式中，U為隸屬度值Uij構(gòu)成的隸屬度矩陣，i=1,2,…,c,j=1,2,…,n；n(i)為第i個(gè)聚類(lèi)中心樣本數(shù)。

Var表示樣本類(lèi)內(nèi)集中程度，Var越小，類(lèi)內(nèi)越緊致。

類(lèi)間離散度為

0≤Sep(c,U)≤1

式中，F(xiàn)X、FY為兩個(gè)模糊集合；vj表示樣本點(diǎn)向量，j=1,2,…,n;min(UXj，UYj)表示該樣本點(diǎn)分別屬于FX和FY隸屬度的最小值；S(FX,FY)表示兩集合間相似度；當(dāng)FX=FY時(shí)，Sep(c,U)=0。

Sep表示兩聚類(lèi)集群離散度，Sep越大，各類(lèi)間越分散。

為綜合評(píng)價(jià)聚類(lèi)結(jié)果，將Var與Sep結(jié)合，定義綜合評(píng)價(jià)指標(biāo)為

VS越小，聚類(lèi)效果越好。

3 特征點(diǎn)提取

3.1 邊界點(diǎn)剔除與合并

應(yīng)用FA-FCM聚類(lèi)算法對(duì)點(diǎn)云模型進(jìn)行分割后，需要對(duì)各分割塊邊界點(diǎn)進(jìn)行特征點(diǎn)提取，在特征點(diǎn)提取過(guò)程中，所得分割塊的邊界點(diǎn)有兩種情況需要處理。首先，過(guò)分割問(wèn)題的存在容易致使模型平坦區(qū)域出現(xiàn)分割線，顯然該分割線為非特征線，該分割線處的點(diǎn)為明顯非特征點(diǎn)，表示該分割線的兩組邊界點(diǎn)相鄰且共面，應(yīng)從邊界點(diǎn)集中剔除；其次，若分割線為特征線，則表示該分割線的兩組邊界點(diǎn)相鄰但不共面，應(yīng)對(duì)其進(jìn)行合并處理。

本文在利用鄰近投影點(diǎn)相鄰向量夾角的方法[26]提取各分割塊邊界點(diǎn)的基礎(chǔ)上，對(duì)邊界點(diǎn)進(jìn)行優(yōu)化處理，剔除相鄰且共面的邊界點(diǎn)，合并相鄰但不共面的邊界點(diǎn)。

為直觀表達(dá)，以圖2所示圓柱體與長(zhǎng)方體的組合模型為例進(jìn)行說(shuō)明。圖2a所示為該組合模型經(jīng)FA-FCM算法聚類(lèi)分割后所得結(jié)果，由該圖可知，為有效分割長(zhǎng)方體四個(gè)側(cè)面，圓柱體側(cè)面也會(huì)被劃分為四組，存在過(guò)分割現(xiàn)象，導(dǎo)致圓柱體側(cè)面邊界點(diǎn)集l1、m1為非特征點(diǎn)集，長(zhǎng)方體相鄰兩側(cè)面邊界點(diǎn)集l2、m2均為兩側(cè)面交線處特征點(diǎn)，如圖2b所示。為此，以各分割塊為處理單元，通過(guò)分析比較兩分割塊邊界點(diǎn)間距離和法向夾角，利用設(shè)置閾值的方法剔除相鄰且共面的邊界點(diǎn)集(如l1、m1)，將相鄰但不共面的邊界點(diǎn)集(如l2、m2)合并，方法如下。

(a)區(qū)域聚類(lèi)分割結(jié)果 (b)邊界點(diǎn)提取結(jié)果圖2 邊界點(diǎn)優(yōu)化準(zhǔn)則Fig.2 Optimization rule of boundary points

模型分割后，定義分割塊邊界點(diǎn)集為

F={fi}i=1,2,…,c

式中，fi為第i個(gè)分割塊邊界點(diǎn)集。

給定任意兩組邊界點(diǎn)集fw1,fw2(w1,w2=1,2，…,c，w2≠w2)，依據(jù)點(diǎn)云密度設(shè)置距離閾值D，以及依據(jù)邊界點(diǎn)集fw1和fw2所對(duì)應(yīng)分割塊的聚類(lèi)中心間夾角設(shè)置法向夾角閾值T，分別取fw1和fw2中任一點(diǎn)su1(u1=1,2，…,n1)和su2(u2=1,2，…,n2)，n1、n2為各點(diǎn)集總點(diǎn)數(shù),求su1、su2兩點(diǎn)間坐標(biāo)距離d、法向夾角φ。判定準(zhǔn)則如下：

(1)若d≥D，則點(diǎn)su1、su2不做任何處理。

(2)若d

(3)若d

3.2 候選特征點(diǎn)平滑

各分割塊邊界點(diǎn)集經(jīng)優(yōu)化處理后所得點(diǎn)集為無(wú)序點(diǎn)，稱(chēng)該無(wú)序狀態(tài)點(diǎn)集為候選特征點(diǎn)集，為便于曲線擬合，需先對(duì)候選特征點(diǎn)進(jìn)行排序，然后再擬合成線。然而，由于點(diǎn)云數(shù)據(jù)在獲取過(guò)程中不可避免地受外界環(huán)境、掃描設(shè)備等因素影響，導(dǎo)致候選特征點(diǎn)集中存在噪點(diǎn)，若直接對(duì)排序后的候選特征點(diǎn)進(jìn)行曲線擬合，則噪點(diǎn)的存在會(huì)嚴(yán)重影響擬合精度，因此，以各點(diǎn)局部鄰域主軸方向[27]為基準(zhǔn)對(duì)排序后的候選特征點(diǎn)進(jìn)行平滑處理。

取排序后候選特征點(diǎn)集中的一點(diǎn)s0，確定點(diǎn)s0的鄰域值k0，對(duì)于鄰域內(nèi)任意點(diǎn)su(u=1,2,…,k0)，記s0與su兩點(diǎn)連線方向s0su與平滑參考方向正向夾角為θu(u=1,2，…,k0)，如圖3b所示。平滑參考方向構(gòu)造法如下：

(1)候選特征點(diǎn)s0為初始點(diǎn)時(shí)，無(wú)參考方向，取局部鄰域點(diǎn)PCA主軸方向D1為平滑參考方向，如圖3a所示。

(a)采樣點(diǎn)局部鄰域點(diǎn)集及主軸方向

(b)相鄰點(diǎn)方向夾角圖3 候選特征點(diǎn)平滑準(zhǔn)則Fig.3 Smoothing rule of candidate feature points

(2)候選特征點(diǎn)s0為非初始點(diǎn)時(shí)，取s0的前一點(diǎn)s00與s0的連線方向s00s0為平滑參考方向。

確定參考方向后，平滑準(zhǔn)則如下：

(1)距離準(zhǔn)則。min(|s0su|)(|s0su|表示點(diǎn)s0與點(diǎn)su的距離，u=1,2，…,k0)，即查找k0鄰域內(nèi)距s0最近的點(diǎn)。

(2)夾角準(zhǔn)則。min(θu)(u=1,2，…,k0)，即查找s0和k0鄰域內(nèi)任意點(diǎn)su(u=1,2，…,k0)的連線方向s0su與平滑參考方向正向間夾角最小的點(diǎn)。

如圖3b所示，取鄰域值k0為5，搜索s0的下一點(diǎn)，min(|s0su|)=|s0s5|，min(θu)=θ3。僅使用距離準(zhǔn)則時(shí)，s5被確定為s0的下一點(diǎn)，此時(shí)s5與平滑參考方向角度偏差太大；僅使用夾角準(zhǔn)則時(shí)，s3被確定為s0的下一點(diǎn)，此時(shí)距離跨度太長(zhǎng)，直線拐點(diǎn)處特征點(diǎn)不易保留，容易出現(xiàn)過(guò)度平滑現(xiàn)象。因此，在對(duì)候選特征點(diǎn)進(jìn)行平滑處理的過(guò)程中，應(yīng)組合使用距離準(zhǔn)則和夾角準(zhǔn)則，設(shè)置夾角閾值T2，對(duì)滿足條件θu

根據(jù)候選特征點(diǎn)分布特性設(shè)置夾角閾值T2，多次調(diào)整閾值以達(dá)到最佳平滑效果，在實(shí)驗(yàn)過(guò)程中，對(duì)直線和曲線類(lèi)特征線設(shè)置不同的角度閾值T2，分別為T(mén)2=5°～10°和T2=20°～30°。

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

4.1 主要參數(shù)設(shè)置

本文將基于法向量的FA-FCM聚類(lèi)算法應(yīng)用于點(diǎn)云模型特征線提取問(wèn)題中，選取AIM@SHAHE Shape Repository公開(kāi)數(shù)據(jù)庫(kù)中的Smooth、Fandisk、Vase模型以及Princeton ModelelNet數(shù)據(jù)庫(kù)中的m932-table模型作為實(shí)驗(yàn)對(duì)象，驗(yàn)證所提算法的可行性和優(yōu)越性。

目前螢火蟲(chóng)算法的參數(shù)設(shè)置還沒(méi)有明確合理的參考值，為此，首先通過(guò)分析比較文獻(xiàn)中的參數(shù)值來(lái)設(shè)置合理的參數(shù)范圍，然后測(cè)試不同的參數(shù)組合，確定該特征線提取算法的初始化參數(shù)值，設(shè)置見(jiàn)表1。

表1 參數(shù)列表Tab.1 The list of parameters

4.2 特征線提取結(jié)果的有效性及精度分析

為驗(yàn)證本文算法的可行性，選取Smooth、Fandisk、Table和Vase模型進(jìn)行特征線提取。首先估算各模型數(shù)據(jù)點(diǎn)法向，由FA-FCM混合算法對(duì)其進(jìn)行聚類(lèi)分割，各模型聚類(lèi)有效性評(píng)價(jià)指標(biāo)見(jiàn)表2。由表2可知，4個(gè)模型的Sep(0≤Sep≤1)值均接近于1，表明各模型整體劃分效果較好，但分析比較Var值與VS值可知，Vase模型所對(duì)應(yīng)的Var和VS值均為最大，表明Vase模型的聚類(lèi)效果較差，還需進(jìn)一步優(yōu)化。

表2 各模型聚類(lèi)有效性指標(biāo)Tab.2 Cluster validity indexes of each model

4個(gè)模型經(jīng)FA-FCM算法聚類(lèi)分割后，基于各分割塊邊界點(diǎn)提取特征點(diǎn)，對(duì)應(yīng)該相交的特征線端點(diǎn)進(jìn)行合并處理，然后擬合生成特征線，各模型特征線提取不同階段效果顯示如圖4～圖7所示。

(a)Smooth模型原始點(diǎn)云 (b)區(qū)域聚類(lèi)結(jié)果

(c)特征點(diǎn)提取結(jié)果 (d)特征線提取結(jié)果圖4 Smooth模型特征線提取Fig.4 Feature line extraction from Smooth model

(a)Fandisk模型原始點(diǎn)云 (b)區(qū)域聚類(lèi)結(jié)果

(c)特征線提取結(jié)果圖5 Fandisk模型特征線提取Fig.5 Feature line extraction from Fandisk model

Smooth模型結(jié)構(gòu)簡(jiǎn)單，主要由平面和曲面構(gòu)成。圖4b是模型經(jīng)FA-FCM區(qū)域聚類(lèi)分割所得結(jié)果，通過(guò)相鄰兩分割塊交線提取該模型特征線，特征線以直線為主，特征信息較為突出，即為尖銳特征，圖4c為Smooth模型特征點(diǎn)識(shí)別結(jié)果，表明模型尖銳特征點(diǎn)能夠得到準(zhǔn)確提取。

(a)Table模型原始點(diǎn)云 (b)區(qū)域聚類(lèi)結(jié)果

(c)特征線提取結(jié)果圖6 Table模型特征線提取Fig.6 Feature line extraction from Table model

(a)Vase模型原始點(diǎn)云 (b)區(qū)域聚類(lèi)結(jié)果

(c)特征線提取結(jié)果圖7 Vase模型特征線提取Fig.7 Feature line extraction from the Vase model

圖5為Fandisk模型特征線提取不同階段效果圖。Fandisk模型為機(jī)械輪盤(pán)模型，相比于Smooth模型結(jié)構(gòu)較為復(fù)雜，既包含明顯棱線(即尖銳特征線)，又包含過(guò)渡特征線(如在模型底部相鄰曲面相交處的特征點(diǎn)曲率變化較小，法向量方向相近，特征信息不明顯，這類(lèi)特征即為過(guò)渡特征)。圖5c為Fandisk模型特征點(diǎn)識(shí)別結(jié)果，表明Fandisk模型的尖銳特征得到了完整提取，同時(shí)也有效保留了過(guò)渡特征。

圖6為T(mén)able模型特征線提取不同階段效果圖。Table模型為餐桌模型，結(jié)構(gòu)相對(duì)復(fù)雜，主要由平面、曲面以及球面構(gòu)成，特征信息豐富，既包含尖銳特征，也包含細(xì)節(jié)特征，如模型桌腳及兩球面相交處均包含有細(xì)節(jié)特征。圖6c所示為T(mén)able模型特征點(diǎn)識(shí)別結(jié)果，表明本文所提方法在完整提取Table模型尖銳特征的同時(shí)也能有效識(shí)別模型細(xì)節(jié)特征。

圖7為Vase模型特征線提取不同階段效果圖。Vase模型為構(gòu)造復(fù)雜的花瓶模型，由內(nèi)外兩層曲面構(gòu)成，特征線呈“之”字形，主要包括尖銳特征和過(guò)渡特征。與Fandisk模型相比，該模型曲面彎曲度較大，過(guò)渡特征的特征強(qiáng)度較弱且分布不均。圖7c所示為Vase模型特征點(diǎn)識(shí)別結(jié)果，表明該算法對(duì)Vase模型中強(qiáng)度較弱的過(guò)渡特征提取效果不佳，部分特征線斷裂。這與由表2得出的Vase模型聚類(lèi)效果較差的結(jié)論相對(duì)應(yīng)。

為對(duì)本文算法的特征線提取結(jié)果進(jìn)行定量評(píng)價(jià)，分別計(jì)算各模型特征線的數(shù)量提取率和長(zhǎng)度提取率。

模型數(shù)量提取率通過(guò)計(jì)算精確率Rpc和召回率Rrc[28]獲得，精確率表示被正確提取的特征線數(shù)目占被提取出特征線總數(shù)的比值，召回率表示被正確提取的特征線數(shù)目占模型特征線總數(shù)的比值。精確率、召回率的計(jì)算公式如下：

式中，Tp為被正確提取的特征線數(shù)目；Fp為被錯(cuò)誤提取的特征線數(shù)目；Tz為模型特征線總數(shù)。

模型長(zhǎng)度提取率通過(guò)計(jì)算模型中各特征線段長(zhǎng)度提取率的平均值獲得，模型中某一特征線的長(zhǎng)度提取率為已提取出的該特征線長(zhǎng)度與其準(zhǔn)確長(zhǎng)度的比值。因?yàn)槿S點(diǎn)云模型中特征曲線的準(zhǔn)確長(zhǎng)度不易求取，故本文利用“化曲為直”的思想，近似估算曲線長(zhǎng)度。模型整體特征線長(zhǎng)度提取率的計(jì)算公式如下：

式中，hq為第q條特征線的長(zhǎng)度提取率(q=1,2,…,Tz)；lq為已提取的該特征線長(zhǎng)度；Lq為該特征線準(zhǔn)確長(zhǎng)度；H為模型整體特征線長(zhǎng)度提取率。

對(duì)4種模型的精確率、召回率和模型長(zhǎng)度提取率H進(jìn)行統(tǒng)計(jì)，結(jié)果如表3所示。分析表3可知，Smooth模型和Fandisk模型的特征線提取結(jié)果更加完整和準(zhǔn)確，所提取特征線不存在誤判和漏判現(xiàn)象，由精確率、召回率及長(zhǎng)度提取率H可判定Smooth和Fandisk的特征線基本得到了準(zhǔn)確完整的提取，經(jīng)細(xì)微調(diào)整后可投入實(shí)際應(yīng)用中。Table模型特征線提取準(zhǔn)確性較好，不存在誤判現(xiàn)象，但由其Rrc值可判定該模型特征線未得到完整提取。此外，4種模型相比之下，Vase模型特征線提取的完整性和準(zhǔn)確性較低，由其Rpc值和Rrc值可判定該模型的特征線提取既存在誤判現(xiàn)象又存在漏判現(xiàn)象。但Table模型和Vase模型的召回率Rrc均達(dá)到90%，兩模型長(zhǎng)度提取率H均可達(dá)85%，表明本文方法在進(jìn)行相對(duì)復(fù)雜模型的特征線提取時(shí)也可取得較好成效，可進(jìn)行局部二次特征提取，從而有效識(shí)別強(qiáng)度信息不明顯的特征點(diǎn)，提高模型特征線提取的完整性和準(zhǔn)確性。

表3 各模型特征線數(shù)量提取率和長(zhǎng)度提取率Tab.3 The extraction rate of the number and the length of feature lines of each model %

4.3 特征線提取方法對(duì)比

為進(jìn)一步驗(yàn)證算法的可行性及優(yōu)越性，選擇Fandisk模型特征線提取結(jié)果與文獻(xiàn)[29]提取結(jié)果進(jìn)行對(duì)比，結(jié)果如圖8所示。選擇Vase模型特征線提取結(jié)果與文獻(xiàn)[29]、[30]和[31]的提取結(jié)果進(jìn)行對(duì)比，結(jié)果如圖9所示。

(a)本文方法特征線提取(b)文獻(xiàn)[29]特征線提取圖8 Fandisk模型特征線提取方法對(duì)比Fig.8 Comparison of the feature extraction methods used in Fandisk model

在圖8中，對(duì)比長(zhǎng)方形框標(biāo)定區(qū)域可以看出，文獻(xiàn)[29]的方法不易識(shí)別特征強(qiáng)度逐漸減弱的平滑過(guò)渡區(qū)特征，從而導(dǎo)致特征線提取不完整，而本文方法所提取特征線的完整度以及線條光滑度相對(duì)較好。

由圖9可知，本文算法能較好地識(shí)別內(nèi)外兩層特征線，兩層線間不存在相互扭曲現(xiàn)象，曲線線條性更好，但不能完整識(shí)別特征強(qiáng)度較弱的特征點(diǎn)，致使曲線出現(xiàn)斷裂和不完整現(xiàn)象。

(a)本文方法特征線提取 (b)文獻(xiàn)[29]方法特征線提取

(c)文獻(xiàn)[30]方法特征線提取 (d)文獻(xiàn)[31]方法特征線提取

5 結(jié)論

本文基于自適應(yīng)鄰域的FA-FCM算法實(shí)現(xiàn)點(diǎn)云模型的有效分割，通過(guò)構(gòu)造邊界點(diǎn)集剔除與合并準(zhǔn)則以及候選特征點(diǎn)集平滑準(zhǔn)則從各分割塊邊界點(diǎn)集中識(shí)別特征點(diǎn)。結(jié)合實(shí)驗(yàn)分析得出以下結(jié)論：

(1)相對(duì)于固定閾值的主成分分析(PCA)法，自適應(yīng)鄰域的PCA法可較為精準(zhǔn)地估計(jì)模型尖銳特征點(diǎn)處法向，再通過(guò)熒火蟲(chóng)算法優(yōu)化后的FCM算法可使模型分割效果達(dá)到最佳，從而提高各分割區(qū)邊界點(diǎn)中特征點(diǎn)比率。

(2)邊界點(diǎn)集剔除與合并準(zhǔn)則可有效去除邊界點(diǎn)集中多數(shù)非特征點(diǎn)，從而提高算法效率；同時(shí)，結(jié)合候選特征點(diǎn)集平滑準(zhǔn)則的應(yīng)用可使所提算法能夠識(shí)別更多準(zhǔn)確的模型特征，提高所擬合特征線的光滑度。

(3)通過(guò)4種實(shí)驗(yàn)?zāi)Ｐ偷奶卣骶€提取精度分析可知，Smooth模型和Fandisk模型的特征線可得到準(zhǔn)確完整的提取，結(jié)構(gòu)相對(duì)復(fù)雜的Table模型和Vase模型特征線的數(shù)量提取率可達(dá)90%，長(zhǎng)度提取率也可達(dá)85%，其中，主要特征線均可得到完整提取。結(jié)果表明，本文算法簡(jiǎn)單有效且具有一定的通用性，在準(zhǔn)確提取點(diǎn)云模型顯著特征和細(xì)節(jié)特征的同時(shí)能盡可能多地保留模型過(guò)渡特征。