孔德明，張 娜，王書濤，史慧超

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

1 引 言

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

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

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

2 算 法

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

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

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

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

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

(1)

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

(2)

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

(3)

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

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

2.2 多視角距離圖像的生成

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

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

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

2.3 基于距離圖像的種子點獲取

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

由于原始模型中存在過渡邊界變化不明顯的部分區(qū)域，因此Canny算子檢測得到各個區(qū)域的邊緣信息可能存在斷點和噪聲。如圖4(a)所示，在俯視視角下檢測獲取到第1組點云的原始邊緣信息并不完整，在圓圈標注區(qū)域內(nèi)均存在斷裂情況。利用式(6)中閉運算算法填補圖像中的空洞區(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)

式中：⊕為膨脹符號；Θ為腐蝕符號；·代表閉運算。

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

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

圖5 種子點獲取Fig.5 Acquisition of seed point

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

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

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

2.4.1 鄰接面分離

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

(7)

Ang=acos(cosβ)

(8)

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

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

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

2.4.2 獨立面提取

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

2.4.3 基于KNN的離群點去除

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

圖8 離群點去除Fig.8 Deletion of off-group points

3 實驗結(jié)果與分析

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

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

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

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

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

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

(9)

式中：Sp為理論上標準分割區(qū)域所包含點的個數(shù)；Tp為實際的分割數(shù)據(jù)點個數(shù)；|Sp-Tp|為錯誤分割的數(shù)據(jù)點個數(shù)。

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

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

4 結(jié) 論

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