點(diǎn)云數(shù)據(jù)的凹陷體判定算法

楊作威 車 明

(天津大學(xué)智能與計(jì)算學(xué)部 天津 300350)

0 引 言

物體具有長(zhǎng)、寬、高的三維物理尺寸。然而，大多數(shù)顯示技術(shù)仍然屬于二維顯示技術(shù)，包含一些深度線索，但缺乏深度信息，這將導(dǎo)致人眼的深度、動(dòng)態(tài)和視差功能的退化[1]。因此人類的大腦需要獲取完全符合三維真實(shí)物體的信息，也就是三維信息。體三維顯示是三維顯示領(lǐng)域的重要研究方向，為人類視覺系統(tǒng)提供生理和心理深度信息以感知3D對(duì)象，可允許多個(gè)觀察者同時(shí)從不同角度觀察到同一三維場(chǎng)景的不同側(cè)面[2]。但是當(dāng)體三維顯示系統(tǒng)處理帶凹陷體的點(diǎn)云數(shù)據(jù)時(shí)，由于凹陷體區(qū)域無法正確判定，導(dǎo)致對(duì)應(yīng)區(qū)域的顏色缺失，會(huì)影響體三維系統(tǒng)的顯示效果。而現(xiàn)有的相關(guān)點(diǎn)云處理算法主要是對(duì)點(diǎn)云邊界的判定與處理。3D點(diǎn)云中邊界的提取方法可分為兩類，分別是基于網(wǎng)格的方法和直接基于點(diǎn)的方法。基于網(wǎng)格的方法可以通過網(wǎng)格之間的拓?fù)潢P(guān)系來識(shí)別邊界[3-8]。Jun[5]利用邊界三角網(wǎng)格的相鄰三個(gè)網(wǎng)格中至少一個(gè)為空的原理確定種子邊界點(diǎn)，再通過跟蹤獲得閉環(huán)邊界邊，但是無法區(qū)分模型外邊界和內(nèi)部空洞邊界。Huang等[6]首先對(duì)點(diǎn)云構(gòu)建tin網(wǎng)格，初始化一個(gè)最大邊界，再通過設(shè)立網(wǎng)格邊長(zhǎng)閾值逐步縮小邊界邊，最終得到精確的點(diǎn)云邊界，該算法適合于處理復(fù)雜形狀的點(diǎn)云數(shù)據(jù)。直接基于點(diǎn)的方法首先找到每個(gè)點(diǎn)的鄰居，然后通過計(jì)算點(diǎn)的幾何屬性如法向量、密度等以確定邊界[9-14]。丁承君等[10]首先構(gòu)造點(diǎn)云kd樹拓?fù)浣Y(jié)構(gòu)，通過RANSAC算法尋找種子點(diǎn)確定平面，并找出感興趣區(qū)域，最后通過k鄰域點(diǎn)的法線夾角與閾值對(duì)比確定邊界點(diǎn)。Gai等[11]使用二維相位圖和每個(gè)點(diǎn)的相鄰區(qū)域來確定邊界，然后使用邊界點(diǎn)的行和列坐標(biāo)刪除輪廓點(diǎn)。陸帆等[12]首先將每個(gè)目標(biāo)點(diǎn)及其相鄰點(diǎn)投影到平面上，然后計(jì)算反距離權(quán)重和點(diǎn)云密度來確定其是否為邊界特征點(diǎn)，但是算法依賴加權(quán)權(quán)重的選取。除此之外，Bao等[15]借助3D laser scanner將三維點(diǎn)云映射到二維range圖像中，利用圖像處理中的canny算子得到點(diǎn)云邊界，但是算法無法區(qū)分內(nèi)外邊界。

現(xiàn)有的點(diǎn)云邊界算法只能識(shí)別孔洞或點(diǎn)云的邊界，缺乏對(duì)凹陷體判定的研究，因此，本文工作如下：(1)提出了凹陷體的定義，并為之做出了形象化的描述；(2)根據(jù)凹陷體的空間特性，提出了基于空間連通性原理的凹陷體判定算法，為點(diǎn)云中凹陷體的判定提出了一種解決方案；(3)通過實(shí)驗(yàn)驗(yàn)證了算法的可行性并對(duì)未來的應(yīng)用前景做出了展望。

1 凹陷體判定算法

1.1 凹陷體定義

本文將凹陷體定義以y軸作為高度軸，凹陷體是指處于點(diǎn)云模型中，或不含點(diǎn)的空間，凹陷體與點(diǎn)云外界區(qū)域相被點(diǎn)所包圍，且高度值低于點(diǎn)云中周圍點(diǎn)的高度變化趨勢(shì)，含少量點(diǎn)連通。如圖1所示，圖1(a)為點(diǎn)云數(shù)據(jù)，圖1(b)三部分點(diǎn)云分別包裹的區(qū)域即為凹陷體，而點(diǎn)云內(nèi)部的空洞由于不與外界連通，不屬于凹陷體。本文針對(duì)該問題提出了PCDD算法以求出點(diǎn)云中的各個(gè)凹陷體，為后續(xù)的應(yīng)用打下基礎(chǔ)。

(a)點(diǎn)云數(shù)據(jù) (b)凹陷體邊界圖1 點(diǎn)云凹陷體示意圖

1.2 凹陷體判定算法原理

凹陷體判定算法流程如圖2所示。

圖2 凹陷體判定算法流程

1.2.1點(diǎn)云體素化

1)確定點(diǎn)云體素化分割大小。計(jì)算出點(diǎn)云數(shù)據(jù)在x、y、z軸上的范圍，分別記作range_x、range_y、range_z。取三者其中的最小值記作min并將其k等分，其他兩個(gè)方向上按照相同比例進(jìn)行分割，其中k取決于實(shí)驗(yàn)經(jīng)驗(yàn)值。

2)構(gòu)建外表面層作為凹陷體正確性判定依據(jù)。由于在點(diǎn)云數(shù)據(jù)中，點(diǎn)只分布于實(shí)體邊界周圍而實(shí)體內(nèi)部通常是沒有點(diǎn)的，因此在本文的算法處理過程中模型內(nèi)部的空洞也會(huì)被判定為凹陷體。對(duì)于這種模型本身的空洞及模型所包含的真實(shí)凹陷體如果不加以區(qū)分的話會(huì)造成判定錯(cuò)誤。因此，本文考慮到真實(shí)的凹陷體是與點(diǎn)云外界區(qū)域相連通的原理，通過在點(diǎn)云的外表面附加一層體素來作為連通性判定的依據(jù)。將y軸作為點(diǎn)云數(shù)據(jù)的高度軸，點(diǎn)云體素化示意圖如圖3所示。

圖3 點(diǎn)云體素化示意圖

3)定義體素及平面區(qū)域結(jié)構(gòu)體。對(duì)于每一個(gè)體素，本文定義其結(jié)構(gòu)體如下：

struct VOXEL

{

introw,col,height;

//體素所處的空間位置坐標(biāo)：行，列，高度

intsize；

//體素包含的點(diǎn)個(gè)數(shù)

intlabel；

//label為-2表示體素內(nèi)包含點(diǎn)數(shù)大于閾值，label為-1表示

//體素為判別連通性的附加表面層，label為0表示體素包含點(diǎn)

//數(shù)小于閾值，label為大于0的自然數(shù)表示屬于各個(gè)不同凹陷

//體。初始狀態(tài)下體素label只有0、-1、-2三種

}

同時(shí)在xz平面方向上定義結(jié)構(gòu)體：

struct grid

{

intmax_height;

//該區(qū)域的最大高度

VOXEL *voxel;

//存儲(chǔ)該區(qū)域在高度方向上的體素，

//數(shù)組大小為round(range_y×k/min)+1

}

4)定義點(diǎn)云中點(diǎn)的空間位置。計(jì)算每個(gè)點(diǎn)所處的體素位置，記第i個(gè)點(diǎn)的三維坐標(biāo)為(xi,yi,zi),記整個(gè)點(diǎn)云文件的x、y、z最小值分別為x_min、y_min、z_min,第i點(diǎn)所處矩陣的行：

round((zi-z_min)/(range_z/round(range_z×k/min)))+1

點(diǎn)所處矩陣的列：

round((xi-x_min)/(range_x/round(range_x×k/min)))+1

點(diǎn)所處每個(gè)矩陣的體素?cái)?shù)組下標(biāo)即高度。

round((yi-y_min)/(range_y/round(range_y×k/min)))+1

為了防止計(jì)算結(jié)果越界，當(dāng)三個(gè)參數(shù)大于約束的范圍時(shí)，將對(duì)應(yīng)值減一即可。

1.2.2確定點(diǎn)云凹陷體素集合

本文確定一個(gè)體素是否可能屬于凹陷體的判斷原理主要有以下兩點(diǎn)：

(1)以y軸作為點(diǎn)云的高度軸，該體素包含點(diǎn)數(shù)少于閾值且低于所處對(duì)應(yīng)xz平面grid區(qū)域上的最高點(diǎn)。

(2)該體素包含點(diǎn)數(shù)少于閾值并對(duì)于該體素做xz平面上的切面，在如圖4所示的8個(gè)方向上向外延伸，存在4個(gè)及以上方向被非空體素所阻隔。

圖4 體素判定原理圖

圖4為xz平面上的切面圖，帶*的方塊表示label為-2即包含點(diǎn)數(shù)大于閾值的體素，不含任何標(biāo)記的方塊表示包含點(diǎn)數(shù)小于閾值的體素。

因此在遍歷體素過程中，首先判斷體素的label值，如果label值為0，判斷其是否低于該平面區(qū)域上的最高點(diǎn)，若結(jié)果為true，放入凹陷判定集合Q；否則，對(duì)該體素在xz切面的8個(gè)方向上依次延伸，設(shè)當(dāng)前正在進(jìn)行處理的體素為I，如圖4中帶I標(biāo)記的方塊所示。以斜右上方方向?yàn)槔O(shè)體素I所處的空間中的行、列、高為I.row、I.col、I.height,依次判斷(I.row+i,I.col+i,I.height)處的體素label值是否為-2即判斷在延伸的過程中是否會(huì)碰到label為-2的體素，其中i為自然數(shù)。其他7個(gè)方向同理，若在4個(gè)及以上方向均滿足條件，則放入集合Q。

按照上述判斷原理進(jìn)行判斷，形成凹陷體判定集合Q進(jìn)行下一步判定。

1.2.3凹陷體素集合分割與判定

對(duì)集合Q采取基于連通性原理的區(qū)域增長(zhǎng)思想進(jìn)行處理，設(shè)初始組數(shù)s=1，定義集合LK來存儲(chǔ)各個(gè)凹陷體的體素。

(1)取出Q中未處理的體素，如果label為0，更改其label值為s并放入LK中。

(2)判斷Q中是否存在與當(dāng)前LK內(nèi)體素相鄰的元素，即在行、列、高三個(gè)方向上存在兩者相等，另一個(gè)相差為1。若存在則將label修改為s，加入到LK中。

(3)按照第二步中規(guī)則繼續(xù)處理新加入LK的體素直至找不到相鄰的體素，清空LK，s++并重復(fù)第一步直到Q中所有體素均遍歷完畢。

1.2.4凹陷體正確性判定

對(duì)于分割出的各個(gè)凹陷體，按照如下兩種方式進(jìn)行正確性判定：

1)凹陷體大小。有些判別結(jié)果所包含體素個(gè)數(shù)較小，表示這部分區(qū)域占模型的比例較小或者屬于噪聲區(qū)域，對(duì)結(jié)果的影響不大，因此本文通過定義組成凹陷體的體素個(gè)數(shù)與組成點(diǎn)云模型體積的體素個(gè)數(shù)的比值的一定比例作為閾值來篩選掉此類結(jié)果。

2)凹陷體連通性。經(jīng)過該方法計(jì)算出的凹陷體中包含有模型內(nèi)部的空洞，這是通過三維重建等方法獲取點(diǎn)云的必然結(jié)果，因?yàn)辄c(diǎn)云中的點(diǎn)只分布于實(shí)體邊界周圍而實(shí)體內(nèi)部沒有點(diǎn)，因此按照本文算法，實(shí)體內(nèi)部的區(qū)域也會(huì)被計(jì)算為凹陷體即假凹陷體。本文建立模型的外部附加層，以各個(gè)凹陷體與附加層的體素相鄰的個(gè)數(shù)作為閾值進(jìn)行判定。

1.2.5計(jì)算凹陷體邊界

對(duì)于計(jì)算出的各個(gè)正確凹陷體，本文通過判斷組成凹陷體的各個(gè)相鄰體素判定其邊界點(diǎn)。

對(duì)于組成凹陷體I的體素q，如果q在空間上的6個(gè)直接相鄰體素中存在label為-2的體素，則該體素內(nèi)的點(diǎn)即屬于該凹陷的邊界，通過遍歷凹陷體的組成體素可以得到完整的邊界點(diǎn)。依次對(duì)各個(gè)凹陷體進(jìn)行同樣處理可以得到對(duì)應(yīng)的邊界點(diǎn)集合。

2 實(shí) 驗(yàn)

本文應(yīng)用C++語(yǔ)言，借助visual studio 2013實(shí)現(xiàn)了上述算法。由于現(xiàn)有的研究中均是對(duì)點(diǎn)云數(shù)據(jù)邊界或是孔洞邊界的提取，缺乏對(duì)點(diǎn)云中凹陷體的判定研究，缺少相關(guān)的實(shí)驗(yàn)結(jié)果，無法進(jìn)行對(duì)比。因此本文自行構(gòu)建了兩個(gè)帶凹陷體的點(diǎn)云對(duì)算法進(jìn)行測(cè)試。通過將點(diǎn)云文件分割成近60 000個(gè)體素得到的實(shí)驗(yàn)數(shù)據(jù)結(jié)果如圖5、圖6所示，本文借助Meshlab軟件對(duì)處理的結(jié)果進(jìn)行顯示。圖5(a)所示的實(shí)驗(yàn)數(shù)據(jù)中共包含三個(gè)凹陷體，圖6(a)所示的實(shí)驗(yàn)數(shù)據(jù)中包含六個(gè)凹陷體，在圖5(b)、圖6(b)中均被正確地識(shí)別出來，實(shí)驗(yàn)結(jié)果中的點(diǎn)表示各個(gè)凹陷體的邊界。點(diǎn)云數(shù)據(jù)內(nèi)部的空洞由于不符合與外界連通的原則，則被排除。實(shí)驗(yàn)結(jié)果證明了本文算法的可行性，其可以穩(wěn)定地判定出點(diǎn)云數(shù)據(jù)中的凹陷體。

(a)實(shí)驗(yàn)數(shù)據(jù) (b)實(shí)驗(yàn)結(jié)果圖5 實(shí)驗(yàn)1

(a)實(shí)驗(yàn)數(shù)據(jù)

3 結(jié) 語(yǔ)

本文考慮到體三維顯示系統(tǒng)無法正確顯示帶凹陷的點(diǎn)云數(shù)據(jù)問題，首先對(duì)凹陷體概念作了規(guī)范化定義，并根據(jù)凹陷體的屬性特征提出了點(diǎn)云凹陷體判定算法PCDD，實(shí)驗(yàn)結(jié)果證明了算法的可行性。點(diǎn)云凹陷體能夠應(yīng)用于三維顯示領(lǐng)域及CAD領(lǐng)域，體三維顯示系統(tǒng)可以通過模擬透過凹陷體觀察到的顏色來實(shí)現(xiàn)更真實(shí)的三維顯示效果，CAD領(lǐng)域可以通過對(duì)凹陷體的精確把握實(shí)現(xiàn)高精度的模型設(shè)計(jì)，有很好的應(yīng)用價(jià)值與發(fā)展前景。