孔德明，張 娜，王書(shū)濤，史慧超

(1. 燕山大學(xué) 電氣工程學(xué)院，河北 秦皇島 066004；2. 北京化工大學(xué) 信息科學(xué)與技術(shù)學(xué)院，北京 100029)

1 引 言

點(diǎn)云模型分割是醫(yī)學(xué)研究、模式識(shí)別、機(jī)器人環(huán)境認(rèn)知、逆向工程等領(lǐng)域中一項(xiàng)關(guān)鍵且繁瑣的技術(shù)。作為目標(biāo)識(shí)別的基礎(chǔ)，其實(shí)質(zhì)是將具有相似特征屬性的點(diǎn)劃分入同一區(qū)域，不同特征的點(diǎn)歸入相互獨(dú)立的集合，從而依據(jù)各區(qū)域內(nèi)點(diǎn)集的特性選取相應(yīng)處理方式對(duì)其分而治之，使得后續(xù)有針對(duì)性地處理更加精準(zhǔn)高效。然而，現(xiàn)實(shí)場(chǎng)景中物體逐漸趨于復(fù)雜化，應(yīng)用現(xiàn)有的點(diǎn)云分割技術(shù)已不能滿(mǎn)足快速、高精度的要求。因此，如何在高冗余度且無(wú)序不均的數(shù)據(jù)點(diǎn)中，迅速提取關(guān)鍵點(diǎn)并進(jìn)行有效處理是當(dāng)前重點(diǎn)研究的內(nèi)容。

區(qū)域生長(zhǎng)作為點(diǎn)云分割領(lǐng)域中的經(jīng)典分割算法，因其算法原理簡(jiǎn)單且易于實(shí)現(xiàn)，廣泛應(yīng)用于各種場(chǎng)景中。Yi B等[1]通過(guò)區(qū)域生長(zhǎng)算法獲取點(diǎn)的恰當(dāng)局部區(qū)域，同時(shí)利用基本基元的中層參數(shù)，指導(dǎo)各點(diǎn)法線參數(shù)的修改和曲面類(lèi)型的迭代檢測(cè)；Rabbani T等[2]提出一種加入平滑條件約束的區(qū)域生長(zhǎng)算法對(duì)密集管道場(chǎng)景進(jìn)行分割，但應(yīng)用于復(fù)雜場(chǎng)景時(shí)分割效果欠佳；李仁忠等[3]將曲率最小的點(diǎn)設(shè)置為種子點(diǎn)，以擬合曲面與種子面法向量夾角是否超出閾值作為生長(zhǎng)準(zhǔn)則實(shí)現(xiàn)點(diǎn)云分割，但該算法的閾值需要測(cè)試選取，故分割的穩(wěn)定性不足；郭保青等[4]利用基于法線一致性原則的區(qū)域生長(zhǎng)算法對(duì)鐵路場(chǎng)景中不同類(lèi)物體進(jìn)行分割，并利用VFH獲取單個(gè)物體特征信息；盧維欣等[5]借助主成分分析法提取建筑物點(diǎn)云的最優(yōu)特征，依據(jù)有效區(qū)域內(nèi)點(diǎn)的特征屬性確定生長(zhǎng)規(guī)則實(shí)現(xiàn)建筑物平面的精確分割。

現(xiàn)有的區(qū)域生長(zhǎng)分割算法雖能實(shí)現(xiàn)點(diǎn)云場(chǎng)景的完整分割，但種子點(diǎn)選取的高隨機(jī)性、局部特征變化平緩區(qū)域點(diǎn)云特征模糊導(dǎo)致的生長(zhǎng)規(guī)則難確定性使得分割效果有一定的局限。本文在傳統(tǒng)區(qū)域生長(zhǎng)算法的基礎(chǔ)上，提出了一種基于多視角區(qū)域生長(zhǎng)的復(fù)雜曲面結(jié)構(gòu)模型分割方法，通過(guò)在多視角下建立點(diǎn)云與距離圖像的一一映射關(guān)系，獲取各個(gè)待分割區(qū)域內(nèi)的種子點(diǎn)并將其作為生長(zhǎng)中心；以網(wǎng)格法向量偏移角度和各點(diǎn)之間的距離度量作為生長(zhǎng)判別標(biāo)準(zhǔn)，同時(shí)利用KNN算法剔除分割過(guò)程中的異常點(diǎn)，實(shí)現(xiàn)復(fù)雜點(diǎn)云模型的合理分割。

2 算 法

本文的算法實(shí)施流程如圖1所示。輸入點(diǎn)云數(shù)據(jù)采用構(gòu)網(wǎng)的方式生成連續(xù)規(guī)則的網(wǎng)格結(jié)構(gòu)，計(jì)算網(wǎng)格結(jié)構(gòu)中各三角面片的法向量，從而基于網(wǎng)格法向量方向相異性原則將復(fù)雜點(diǎn)云模型進(jìn)行初分類(lèi)；依據(jù)目標(biāo)分割面的特征多次選取恰當(dāng)視角建立點(diǎn)云與距離圖像的映射關(guān)系；采用Canny算子獲取各個(gè)面的邊緣信息并生成獨(dú)立連通域，進(jìn)而根據(jù)映射關(guān)系,計(jì)算各連通域內(nèi)重心坐標(biāo)在三維空間中的對(duì)應(yīng)點(diǎn)，將此點(diǎn)作為種子點(diǎn)；以種子點(diǎn)為生長(zhǎng)中心，利用區(qū)域生長(zhǎng)算法實(shí)現(xiàn)模型的完整分割。

圖1 算法流程圖Fig.1 Flow chart of algorithm

2.1 基于網(wǎng)格法向量的點(diǎn)云初次分類(lèi)

為了更好地描述非結(jié)構(gòu)化點(diǎn)云數(shù)據(jù)的特征，構(gòu)建點(diǎn)云模型的網(wǎng)格結(jié)構(gòu)并計(jì)算生成三角面片的法向量[6,7]，依據(jù)三角面片各頂點(diǎn)的坐標(biāo)數(shù)據(jù)，計(jì)算由任意1個(gè)頂點(diǎn)指向其余2頂點(diǎn)的兩相異法向量，得到向量V1和向量V2，兩向量間的夾角用γ表示,解算兩向量的向量積得到該三角面片的法向量D0(d01,d02,d03):

|D0|=|V1×V2|=|V1|·|V2|sinγ

(1)

對(duì)所得法向量進(jìn)行歸一化處理，使不同維度之間的特征在數(shù)值上具有一定的可比性，標(biāo)準(zhǔn)化處理后的法向量用D(d1,d2,d3)表示：

(2)

式中：norm為法向量D0的模；d01，d02，d03與d1，d2，d3分別為歸一化處理前后的法向量D0和D在模型長(zhǎng)、寬、高3個(gè)方向上的分量。

(3)

Fandisk為經(jīng)典的復(fù)雜曲面結(jié)構(gòu)模型，選取其作為實(shí)驗(yàn)對(duì)象介紹模型的分割過(guò)程不失一般性?；诰W(wǎng)格法向量方向性原則可將Fandisk模型分為4組。圖2(a)為網(wǎng)格法向量符合d2<0且d3>0的對(duì)應(yīng)點(diǎn)云，頂面與4個(gè)相互獨(dú)立且曲率變化一致的曲面連接為一個(gè)整體；圖2(b)和圖2(d)分別為側(cè)視視角下網(wǎng)格法向量符合d2>0且d3>0、d2<0且d3<0的對(duì)應(yīng)點(diǎn)云，前者包含的分割面彼此連接緊密且大部分區(qū)域未有明顯的邊界劃分，而后者包含的4個(gè)分割面彼此獨(dú)立；圖2(c)包含模型中的底面與所有立面結(jié)構(gòu)，網(wǎng)格法向量符合d1=1或d1=-1或d3=-1。

圖2 Fandisk模型的4類(lèi)分割面Fig.2 Four types of divided surfaces of the Fandisk model

2.2 多視角距離圖像的生成

為了獲取更完整的三維結(jié)構(gòu)特征信息，引入六視圖繪圖概念，分別在主視、后視、左視、右視、俯視、仰視6個(gè)方向上將初次劃分得到的各類(lèi)點(diǎn)云轉(zhuǎn)化為距離圖像[9,10]。

以俯視方向?yàn)槔?，沿高度軸將此視角下包含的點(diǎn)豎直投影到長(zhǎng)度軸與寬度軸所在的二維平面上，計(jì)算投影后各點(diǎn)之間的平均間距和點(diǎn)云掃描線之間的平均間距，將二者中的較大值作為網(wǎng)格邊長(zhǎng)。這樣操作的目的是盡量保證劃分后的格網(wǎng)中只包含1個(gè)激光腳點(diǎn)。利用格網(wǎng)化方法將映射到平面上的點(diǎn)進(jìn)行劃分，根據(jù)劃分到網(wǎng)格內(nèi)點(diǎn)沿映射方向的高程值對(duì)所在網(wǎng)格進(jìn)行賦值。映射關(guān)系如圖3(a)所示。當(dāng)網(wǎng)格中僅包含1個(gè)點(diǎn)時(shí)，將該點(diǎn)的高程值賦值給該網(wǎng)格；當(dāng)多個(gè)點(diǎn)同時(shí)被劃入同一網(wǎng)格內(nèi)時(shí)，該網(wǎng)格的高程值被指定為網(wǎng)格內(nèi)所有映射點(diǎn)的距離均值；若未將點(diǎn)劃入網(wǎng)格中，將所有映射點(diǎn)的最小值作為網(wǎng)格高程值。經(jīng)過(guò)對(duì)所有網(wǎng)格進(jìn)行賦值處理，生成俯視視角下的距離圖像，如圖3(b)所示，隨著高程值的增加圖像中灰度由深到淺變化。同理，按照上述規(guī)則可對(duì)其余5個(gè)視角下的點(diǎn)云數(shù)據(jù)進(jìn)行相應(yīng)處理生成六視角下的距離圖像，此時(shí)圖像中包含模型的全部特征信息。

圖3 俯視視角下的距離圖像Fig.3 Distance image in vertical view

2.3 基于距離圖像的種子點(diǎn)獲取

距離圖像以灰度的深淺變化來(lái)表征其高程變化，隨著高度值的增加灰度由深及淺，且相鄰面相較于同一面的灰度變化程度更為劇烈。利用Canny算子對(duì)灰度突變的敏銳性檢測(cè)不同面的邊緣信息。

由于原始模型中存在過(guò)渡邊界變化不明顯的部分區(qū)域，因此Canny算子檢測(cè)得到各個(gè)區(qū)域的邊緣信息可能存在斷點(diǎn)和噪聲。如圖4(a)所示，在俯視視角下檢測(cè)獲取到第1組點(diǎn)云的原始邊緣信息并不完整，在圓圈標(biāo)注區(qū)域內(nèi)均存在斷裂情況。利用式(6)中閉運(yùn)算算法填補(bǔ)圖像中的空洞區(qū)域[11,12]：

[f⊕g](u,v)=max{f(u+x,v+y)+g(x,y)}

(4)

[fΘg](u,v)=min{f(u+x,v+y)-g(x,y)}

(5)

f·g=[(f⊕g)Θg]

(6)

式中：⊕為膨脹符號(hào)；Θ為腐蝕符號(hào)；·代表閉運(yùn)算。

具體可分為兩步進(jìn)行：首先由式(4)對(duì)原始圖像f(u,v)進(jìn)行膨脹處理，運(yùn)算過(guò)程可描述為在選定局部區(qū)域內(nèi)計(jì)算原始圖像與結(jié)構(gòu)元素g(x,y)灰度值總和，將最大值替換原始灰度值；其次，利用式(5)對(duì)膨脹后的圖像做腐蝕處理，使處理后的圖像縮減細(xì)化。圖4(b)為經(jīng)過(guò)閉運(yùn)算處理得到的各分割面邊緣信息。此時(shí)斷裂區(qū)域內(nèi)各分割面邊緣已經(jīng)按照原始增長(zhǎng)趨勢(shì)緊密連接成為5個(gè)獨(dú)立連通域；針對(duì)每一獨(dú)立連通域，計(jì)算其重心坐標(biāo)，依據(jù)距離圖像與點(diǎn)云數(shù)據(jù)之間的映射關(guān)系，提取對(duì)應(yīng)三維空間中的點(diǎn)，此點(diǎn)即為種子點(diǎn)。圖5為依據(jù)上述步驟獲取到頂面的種子點(diǎn)，此點(diǎn)位于該面的中心位置，用圓點(diǎn)表示；頂面邊緣點(diǎn)用米字符號(hào)表示。

圖4 待分割面邊緣提取Fig.4 Edge extraction of awaiting surfaces

圖5 種子點(diǎn)獲取Fig.5 Acquisition of seed point

2.4 基于區(qū)域生長(zhǎng)算法的面分割

基于上述處理獲取待分割區(qū)域內(nèi)的種子點(diǎn)，以種子點(diǎn)為生長(zhǎng)中心，利用區(qū)域生長(zhǎng)算法對(duì)各個(gè)面進(jìn)行分割[13]。步驟為：搜索距離種子點(diǎn)最近的法向量，定義其為種子法向量；依據(jù)法向量是否平滑生長(zhǎng)對(duì)鄰接面進(jìn)行分離，并在多個(gè)視角下進(jìn)行細(xì)化分割，從而獲取彼此獨(dú)立的分割面；針對(duì)各獨(dú)立面，以種子點(diǎn)為生長(zhǎng)中心按照迭代搜索最近點(diǎn)的原則提取各點(diǎn)，并利用KNN算法的距離度量剔除離群點(diǎn)完成模型的優(yōu)化分割。流程見(jiàn)圖6所示。

圖6 區(qū)域生長(zhǎng)算法流程圖Fig.6 Flow chart of region growing algorithm

2.4.1 鄰接面分離

引入網(wǎng)格法向量的偏移角度作為鄰接面之間的差異性度量，將每組點(diǎn)云均分割成獨(dú)立面結(jié)構(gòu)。以第1組點(diǎn)云為例，構(gòu)建此類(lèi)點(diǎn)云的網(wǎng)格結(jié)構(gòu)并求解各三角面片的重心坐標(biāo)，將距離種子點(diǎn)最近的網(wǎng)格重心點(diǎn)定義為網(wǎng)格種子點(diǎn)[14]，其所在三角面片的法向量定義為種子法向量Vs(vcx,vcy,vcz)，網(wǎng)格法向量用Vg(vxi,vyi,vzi)(i=1,2,3，…，k)表示，k為此類(lèi)待分割區(qū)域中所有參與運(yùn)算的網(wǎng)格法向量數(shù)量；在種子法向量的鄰域內(nèi)搜索距離最近的法向量并利用式(7)計(jì)算其與種子法向量的偏移量cosβ，依據(jù)式(8)將所得偏移量數(shù)值轉(zhuǎn)化為弧度制表征的角度Ang。

(7)

Ang=acos(cosβ)

(8)

若最近鄰域法向量與種子法向量的偏移角度Ang變化微小，其表征相鄰法向量生長(zhǎng)平滑，即對(duì)應(yīng)的點(diǎn)云未生長(zhǎng)到鄰接面上，此時(shí)更新此法向量為種子法向量，將其在原始法向量點(diǎn)集中剔除；若偏移角度Ang變化數(shù)倍以上，則判定該法向量與原始法向量處于異面，即點(diǎn)云已生長(zhǎng)到鄰接面上[15]，此時(shí)原種子法向量維持不變，并將此法向量視為噪點(diǎn)予以剔除。

按照上述判定規(guī)則循環(huán)遍歷集合中的所有法向量獲取歸屬于同一分割面的全部法向量，進(jìn)而提取組建對(duì)應(yīng)網(wǎng)格的點(diǎn)得到目標(biāo)區(qū)域的分割結(jié)果，如圖7所示，即為頂面與其余獨(dú)立面的分離結(jié)果。在多個(gè)視角重復(fù)上述操作，可將鄰接區(qū)域細(xì)化分割成多個(gè)獨(dú)立的分割面。

圖7 鄰接面分離Fig.7 Separation of adjacent surfaces

2.4.2 獨(dú)立面提取

將點(diǎn)的距離度量作為各個(gè)獨(dú)立面的生長(zhǎng)準(zhǔn)則實(shí)現(xiàn)各面的劃分[16]。計(jì)算待分割區(qū)域內(nèi)各點(diǎn)之間的距離均值，將此數(shù)值作為距離閾值K。以種子點(diǎn)作為生長(zhǎng)中心，搜索距離此點(diǎn)的最近點(diǎn)，計(jì)算兩點(diǎn)之間的距離值并與距離閾值相比較，若此距離值與距離閾值數(shù)值相近，則此點(diǎn)包含在目標(biāo)分割區(qū)域內(nèi)，更新此點(diǎn)為新的種子點(diǎn)并重復(fù)上述操作；反之，若兩點(diǎn)間的距離值相較于距離閾值有一個(gè)突變，則此點(diǎn)已超出目標(biāo)分割面區(qū)域，停止生長(zhǎng)。提取結(jié)果如圖8(a)所示，在4個(gè)曲率變化一致且相互獨(dú)立的點(diǎn)云集中，將其中1個(gè)面完整地提取出來(lái)。

2.4.3 基于KNN的離群點(diǎn)去除

如圖8(a)所示，經(jīng)過(guò)上述處理獲取到的目標(biāo)分割面可能存在異常點(diǎn)，因此需要對(duì)其進(jìn)行離群點(diǎn)檢測(cè)。對(duì)于1個(gè)完整的分割面，面內(nèi)任意一點(diǎn)均包含完整的四鄰域和八鄰域[17]，在邊界處也至少保證周?chē)?個(gè)點(diǎn)?；贙NN算法搜索目標(biāo)分割面中各點(diǎn)鄰域內(nèi)的最近3個(gè)點(diǎn)，并按距離值升序排序；若最遠(yuǎn)距離值遠(yuǎn)大于面中各點(diǎn)的平均距離閾值K，則此點(diǎn)視為離群點(diǎn)，將其在分割面數(shù)據(jù)集中剔除；剔除后的離群點(diǎn)歸入剩余待分割面的數(shù)據(jù)集中，繼續(xù)按照區(qū)域生長(zhǎng)規(guī)則完成其余各面的分割。如圖8(b)所示，經(jīng)過(guò)上述處理后目標(biāo)分割面中已經(jīng)基本不存在具有明顯特征差異的異常點(diǎn)。

圖8 離群點(diǎn)去除Fig.8 Deletion of off-group points

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

電腦配置為：CPU Intel Core i5 3.20 GHz，內(nèi)存12 G。開(kāi)發(fā)環(huán)境為Matlab，選取Fandisk、Block、Candle 3個(gè)復(fù)雜點(diǎn)云模型，在同一實(shí)驗(yàn)環(huán)境下，分別應(yīng)用混合流形譜聚類(lèi)算法[18]、頂點(diǎn)聚類(lèi)算法[19]和本文算法進(jìn)行分割實(shí)驗(yàn)。分割結(jié)果見(jiàn)圖9。

圖9 分割結(jié)果對(duì)比Fig.9 Comparison of segmentation results

混合流形譜聚類(lèi)算法采用混合概率主成份分析(MPPCA)法獲取點(diǎn)的幾何特征并構(gòu)建鄰接矩陣，在譜聚類(lèi)空間中利用N-cut將點(diǎn)云特征信息融入低維向量，借助類(lèi)間類(lèi)內(nèi)劃分(BWP)算法實(shí)現(xiàn)模型無(wú)監(jiān)督分割。如圖9(a)所示，采用此類(lèi)方法可對(duì)模型各部分進(jìn)行有效分割，但對(duì)邊界特征模糊和鄰接面區(qū)域分割效果欠佳，易將多個(gè)區(qū)域劃分為同一自由曲面。如Fandisk模型的兩側(cè)區(qū)域、Block模型的中空區(qū)域及Candle模型中間部分均有較大面積出現(xiàn)過(guò)分割與欠分割現(xiàn)象。

頂點(diǎn)聚類(lèi)算法依據(jù)曲率、法向量以及頂點(diǎn)位置構(gòu)造多維空間描述模型的局部表面特征，并將student-t混合模型(SMM)應(yīng)用于模型三維網(wǎng)格結(jié)構(gòu)進(jìn)行頂點(diǎn)聚類(lèi)，從而實(shí)現(xiàn)模型各部分的合理分割。由于輸入的特征約束較多，因此該類(lèi)算法對(duì)模型劃分過(guò)于精細(xì)，可能將歸屬于同一面的區(qū)域多次劃分。如圖9(b)所示，Block模型的頂面和Candle模型上半部分中近似圓柱的區(qū)域在各自模型中本應(yīng)屬于同一區(qū)域，但均被分割成兩部分。

結(jié)合圖9(c)中本文算法的分割結(jié)果可知，相較于前兩種算法，本文所提出算法對(duì)3種模型分割效果更為完整，無(wú)明顯區(qū)域的錯(cuò)誤分割。不僅對(duì)立面與曲面有良好的分割效果，對(duì)于特征模糊區(qū)域同樣可以準(zhǔn)確識(shí)別。

3種算法的分割精度Rac[20]為：

(9)

式中：Sp為理論上標(biāo)準(zhǔn)分割區(qū)域所包含點(diǎn)的個(gè)數(shù)；Tp為實(shí)際的分割數(shù)據(jù)點(diǎn)個(gè)數(shù)；|Sp-Tp|為錯(cuò)誤分割的數(shù)據(jù)點(diǎn)個(gè)數(shù)。

表1為各算法的分割精度對(duì)比?；旌狭餍巫V聚類(lèi)算法對(duì)結(jié)構(gòu)較為復(fù)雜且特征模糊區(qū)域的模型分割效果欠佳，整體分割精度較低，分割精度在55.84%～83.38%之間；頂點(diǎn)聚類(lèi)算法在所選取的模型上分割效果較穩(wěn)定，分割精度不低于80%；本文算法對(duì)Fandisk和Candle的分割精度均高于90%，由于Block模型整體點(diǎn)云數(shù)據(jù)過(guò)于稀疏，應(yīng)用3種算法得到的分割精度均偏低，但應(yīng)用本文算法的分割精度仍高于其余2種方法。

表1 各算法分割精度Tab.1 Segmentation accuracy of algorithms (%)

4 結(jié) 論

根據(jù)復(fù)雜點(diǎn)云模型的特征，提出了一種基于多視角區(qū)域生長(zhǎng)的復(fù)雜點(diǎn)云模型分割方法。借助多視角距離圖像對(duì)傳統(tǒng)區(qū)域生長(zhǎng)算法加以改進(jìn)，以距離圖像所對(duì)應(yīng)點(diǎn)云區(qū)域內(nèi)的重心作為種子點(diǎn)，保證種子點(diǎn)選取的穩(wěn)定性；以網(wǎng)格法向量偏移角度和各點(diǎn)之間的距離度量作為生長(zhǎng)約束條件改善生長(zhǎng)過(guò)程中的過(guò)分割與欠分割現(xiàn)象。在選取的數(shù)據(jù)集上與其余2種分割方法進(jìn)行測(cè)試比較，實(shí)驗(yàn)結(jié)果表明，本文算法相較于其余2種分割方法對(duì)特征模糊區(qū)域識(shí)別效果更佳，可獲得不低于80%的合理分割結(jié)果。