基于改進(jìn)的局部表面凸性算法三維點(diǎn)云分割

王雅男，王挺峰，田玉珍*，孫 濤

(1 中國科學(xué)院 長春光學(xué)精密機(jī)械與物理研究所激光與物質(zhì)相互作用國家重點(diǎn)實(shí)驗(yàn)室，吉林 長春 130033;2中國科學(xué)院大學(xué)，北京 100049)

基于改進(jìn)的局部表面凸性算法三維點(diǎn)云分割

王雅男1,2，王挺峰1，田玉珍1*，孫 濤1

(1中國科學(xué)院 長春光學(xué)精密機(jī)械與物理研究所激光與物質(zhì)相互作用國家重點(diǎn)實(shí)驗(yàn)室，吉林 長春 130033;2中國科學(xué)院大學(xué)，北京 100049)

點(diǎn)云分割是點(diǎn)云分類、識(shí)別以及三維重建等處理的基礎(chǔ)，分割結(jié)果對后續(xù)應(yīng)用影響巨大。本文提出利用連通點(diǎn)集改進(jìn)局部表面凸性算法中鄰近點(diǎn)關(guān)系的方法，解決目前激光三維成像系統(tǒng)點(diǎn)云分割算法在處理復(fù)雜環(huán)境散亂點(diǎn)云時(shí)存在分割過度及分割不充分的問題，通過主頂點(diǎn)與周圍點(diǎn)構(gòu)成連通集，作為分割判斷局部子點(diǎn)集，形成有效分割區(qū)域。該方法解決了常用點(diǎn)云分割方法無法對形狀不規(guī)則物體進(jìn)行有效分割的問題，提高了分割精度。算法實(shí)驗(yàn)結(jié)果表明，相比于最小切割算法和區(qū)域生長算法，基于連通點(diǎn)集的改進(jìn)局部表面凸性算法對實(shí)際路面環(huán)境信息的分割效果更好，并能在一定程度上避免分割過度和分割不充分的情況，證明該方法適用于復(fù)雜環(huán)境散亂點(diǎn)云數(shù)據(jù)分割。

激光三維成像；點(diǎn)云分割；連通點(diǎn)集；局部表面凸性

1 引 言

近年來，激光三維成像技術(shù)[1-2]不斷發(fā)展，三維成像系統(tǒng)在逆向工程[3]、數(shù)字城市、智能汽車等方面的應(yīng)用越來越廣泛，與此同時(shí)，數(shù)據(jù)的獲取與處理速度[4-9]也越來越快。激光三維成像系統(tǒng)采集的數(shù)據(jù)是大量散亂點(diǎn)云數(shù)據(jù)，將具有不同屬性的物體分開，需進(jìn)行點(diǎn)云分割處理，因此，點(diǎn)云分割是點(diǎn)云數(shù)據(jù)處理的關(guān)鍵部分，同時(shí)為后續(xù)點(diǎn)云的分類和識(shí)別處理提供基礎(chǔ)信息。

早期的點(diǎn)云分割算法主要是基于對象模型[10]和邊緣特性[11-12]實(shí)現(xiàn)數(shù)據(jù)分割，模型分割的計(jì)算復(fù)雜度高，需要大量的對象模型，并且只能通過邊界對特定對象進(jìn)行粗定位。邊緣特性點(diǎn)云分割的處理對象是表面平坦且具有突出邊緣特性的物體數(shù)據(jù)，主要應(yīng)用于工業(yè)生產(chǎn)中。但由于現(xiàn)在所探測的室外環(huán)境噪聲強(qiáng)，物體幾何形狀復(fù)雜，不符合上述算法的應(yīng)用條件，因此這些算法都不適用于分割室外復(fù)雜環(huán)境點(diǎn)云數(shù)據(jù)。

目前，對于室外大量點(diǎn)云數(shù)據(jù)的分割算法主要有兩種[13]:一種是對恒定點(diǎn)分布進(jìn)行分割的算法；另一種是應(yīng)用于室外單掃描數(shù)據(jù)分割的算法。恒定點(diǎn)分布分割算法的處理對象是機(jī)載點(diǎn)云數(shù)據(jù)、室外地面數(shù)據(jù)和室內(nèi)探測數(shù)據(jù)，主要是利用區(qū)域生長算法等快速分割方法，選取具有相同方向的法向量[14]、同樣的曲率特征[15]和平面特性[16]的種子節(jié)點(diǎn)進(jìn)行區(qū)域生長。這種算法通常是以數(shù)據(jù)點(diǎn)之間的幾何關(guān)系作為閾值條件判斷數(shù)據(jù)點(diǎn)是否屬于同一區(qū)域，只局部地考慮單個(gè)點(diǎn)的歸屬，具有很大的局限性，容易受到噪聲的影響。室外單掃描數(shù)據(jù)分割算法主要應(yīng)用于智能汽車，與恒定點(diǎn)分布分割算法相比，針對智能汽車這種特定的應(yīng)用環(huán)境做了改進(jìn)。汽車行駛環(huán)境是地面，而車載掃描設(shè)備探測的數(shù)據(jù)主要是地面物體，由此將分割算法調(diào)整為首先對地面進(jìn)行探測，之后再把地面障礙物進(jìn)行分割，這樣能夠較大程度地提高處理速度。典型方法有郭春朝[17]和Klasing[18]等人在相關(guān)文獻(xiàn)中提到的分割算法，郭春朝提出的算法主要是針對地面障礙物的分割，而Klasing的算法是通過觀察距離不同和法向量的變化進(jìn)行分割，對體積大的物體分割效果比較好，但無法對小體積物體分割。

雖然目前已有的算法，在實(shí)際應(yīng)用方面各有優(yōu)勢，但它們主要適用于一些形狀比較規(guī)則的常見物體，尚無對任意環(huán)境(包括植被覆蓋的山區(qū)環(huán)境在內(nèi))中的任何物體分割都適用的標(biāo)準(zhǔn)準(zhǔn)則，不能很好的用于分割復(fù)雜環(huán)境散亂點(diǎn)云數(shù)據(jù)。因此對于實(shí)際應(yīng)用，需要研究更有效的分割算法。

本論文根據(jù)實(shí)際點(diǎn)云數(shù)據(jù)特點(diǎn)，利用連通點(diǎn)集對局部表面凸性算法[13]中鄰近點(diǎn)關(guān)系進(jìn)行分析并對算法改進(jìn)。改進(jìn)的局部表面凸性分割算法可用于散亂點(diǎn)云分割處理，該算法適用于復(fù)雜環(huán)境的散亂點(diǎn)云分割。

2 局部表面凸性

局部表面凸性點(diǎn)云分割算法的核心就是局部表面凸性的概念。在數(shù)學(xué)理論中，如果一個(gè)幾何體上任意兩點(diǎn)所連的線段都在它的內(nèi)部，那么這個(gè)集合體就被稱為凸面體。凸面可以通過計(jì)算表面曲率來確定，正曲率表示是凸面，負(fù)曲率則表示為凹面，曲率為0則表示為平面。如果把平面結(jié)構(gòu)也歸為凸面結(jié)構(gòu)，那么自然界中大部分物體都是由具有凸面結(jié)構(gòu)的部分組合而成，而不同物體之間的連接處一般為凹面結(jié)構(gòu)，因此可以用表面凸性來將不同的物體分割開。將表面凸性應(yīng)用到三維點(diǎn)云數(shù)據(jù)上，凸面的概念需適當(dāng)調(diào)整。

用局部凸性衡量兩個(gè)相鄰測量點(diǎn)周圍局部表面的特性。如圖1所示，任意兩個(gè)點(diǎn)pi和pj，其位移向量di, j=-dj,i，如果兩個(gè)法向量ni和nj方向相同或者任一表面上的所有點(diǎn)都處于另一個(gè)表面之下，那這兩個(gè)點(diǎn)就滿足局部凸性(local convexity)，通常用凸度值ci, j來表示。若兩個(gè)點(diǎn)滿足局部凸性，ci, j的值就接近于1，反之，則接近于0。ci, j的定義式[13]為：

圖1 局部表面凸性 Fig.1 Local surface convexity

(1)

式中，vnSim、vnSimF、vconv和vconvF都為常數(shù)，vnSim為法向相似軟閾值，vnSimF為vnSim處的切線斜率，vconv為凸度軟閾值，vconvF為vconv處的切線斜率。

S型函數(shù):

(2)

式中，θ為有效閾值，m為影響閾值處切線斜率的范圍參數(shù)。

3 局部表面凸性的點(diǎn)云分割算法

算法的主要步驟是：

(1)鄰近點(diǎn)關(guān)系分析

為減少鄰近點(diǎn)搜索耗費(fèi)的時(shí)間，對點(diǎn)云數(shù)據(jù)進(jìn)行預(yù)處理，通過三角剖分，建立各數(shù)據(jù)點(diǎn)之間的直接相鄰關(guān)系，構(gòu)建局部連通點(diǎn)集，為分割判斷提供局部子點(diǎn)集。

(2)邊界判定

由于三維點(diǎn)云中的鄰近點(diǎn)不一定屬于同一個(gè)物體，需要對局部連通點(diǎn)集中的點(diǎn)進(jìn)行物體邊界判定，判斷獲得的局部連通點(diǎn)集是否屬于同一物體。根據(jù)深度值的不連續(xù)可以判斷物體邊界的存在以及鄰近像素點(diǎn)是否屬于同一部分，對于任意兩個(gè)鄰近像素點(diǎn)i，j，用連接值li,j判斷邊界情況，如果li,j越接近于1，說明這兩個(gè)鄰近像素點(diǎn)越有可能是屬于同一部分的點(diǎn)，反之，越接近于0，則越不可能屬于同一部分。利用模糊邏輯方法[19]定義的li,j的公式為:

(3)

式中，vrDiff和vrNDiff都為常數(shù)，vrDiff為深度值變化的軟閾值，vrNDiff為深度值的鄰近點(diǎn)相對變化軟閾值，vrNF(r)為在vrNDiff處的切線斜率，計(jì)算公式為2·exp(-0.14r)+0.25。如(ri-rj) → 0同時(shí)(rh-ri) → 0或(rj-rk) → 0，會(huì)出現(xiàn)奇點(diǎn)，此時(shí)將連接值li,j設(shè)為1，li,j滿足對稱性，即li,j=lj,i。

(3)確定邊界量bi,j

連接值li,j通常只能判斷距離較近點(diǎn)是否處于邊界處或處于與背面的連接處，而對于距離較遠(yuǎn)點(diǎn)的邊界情況還需要利用邊界量bi, j進(jìn)行判斷，bi, j的定義公式為:

(4)

式中,vrSB和vωOB為常量，vrSB為探測陰影邊界的距離差，vωOB為物體邊界在邊界量中的權(quán)重。

(4)確定點(diǎn)云數(shù)據(jù)分割標(biāo)準(zhǔn)

通過前面的計(jì)算可以得到凸度值ci,j和連接值li,j，利用ci,j與li,j結(jié)合可以獲得分割閾值：

(5)

式中，vst為分割標(biāo)準(zhǔn)閾值。si,j具有對稱性，滿足si,j=sj,i。如果si,j等于true，說明點(diǎn)pi和pj是屬于同一部分的點(diǎn)。遍歷點(diǎn)云數(shù)據(jù)中所有點(diǎn)，進(jìn)行分割標(biāo)準(zhǔn)判斷，將屬于同一部分的點(diǎn)分到同一連通集中，將不同連通集分割開，獲得分割結(jié)果。

4 鄰近點(diǎn)關(guān)系分析改進(jìn)

實(shí)際應(yīng)用中獲取的數(shù)據(jù)為大量散亂點(diǎn)云數(shù)據(jù)，在利用三角剖分進(jìn)行鄰近點(diǎn)關(guān)系分析的過程中，由于獲取的路面信息數(shù)據(jù)點(diǎn)之間關(guān)聯(lián)性較差，點(diǎn)與點(diǎn)之間沒有直接的相鄰關(guān)系，無法建立三角網(wǎng)格，不能得到有效分割，因此，本文采用連通點(diǎn)集代替三角網(wǎng)格確定鄰近點(diǎn)關(guān)系，將獲取的連通點(diǎn)集作為分割所需要的局部子點(diǎn)集進(jìn)行分割。首先將三維散亂點(diǎn)云數(shù)據(jù)轉(zhuǎn)化為虛擬深度圖像，二維深度圖像中的每一個(gè)像素點(diǎn)都帶有相應(yīng)距離值r的信息，相鄰像素點(diǎn)之間具有潛在的鄰域關(guān)系，通過將三維點(diǎn)投影到二維圖像上，三維點(diǎn)的距離信息存儲(chǔ)為二維圖像的像素點(diǎn)。利用深度圖像像素點(diǎn)的有序性，可以在點(diǎn)云投影深度圖像的同時(shí)，建立三維數(shù)據(jù)點(diǎn)與像素序列之間的對應(yīng)關(guān)系。將每一像素點(diǎn)與其周圍像素點(diǎn)構(gòu)成鄰近點(diǎn)關(guān)系，稱之為連通點(diǎn)集，如圖2所示，得到分割所需的局部子點(diǎn)集。連通集內(nèi)鄰近點(diǎn)的數(shù)目可以自由設(shè)定，如可以取4、8、16等。

圖2 兩種連通點(diǎn)集 Fig.2 Two connected point sets

獲取局部連通集之后，對每個(gè)連通集從主頂點(diǎn)開始利用公式計(jì)算li, j、bi, j和分割閾值si, j，進(jìn)行分割標(biāo)準(zhǔn)判斷，確定是否是同一部分的點(diǎn)。若為同一部分的點(diǎn)，則這兩個(gè)點(diǎn)同時(shí)標(biāo)示為1；若不是同一部分的點(diǎn)，則主頂點(diǎn)標(biāo)示為1，另一個(gè)點(diǎn)標(biāo)示為2；之后順時(shí)針依次遍歷所有測量點(diǎn)，若為不同部分的點(diǎn)則標(biāo)示依次加1，若為同一部分的點(diǎn)則用相同的標(biāo)示進(jìn)行標(biāo)記，直到將所有測量點(diǎn)都加上標(biāo)示。通過分割標(biāo)準(zhǔn)判斷把所有屬于同一部分的點(diǎn)都帶上同樣的標(biāo)示，這樣就把同一部分的點(diǎn)歸到一個(gè)集合中作為分割部分。將不同的分割部分分割開，直到將所有散亂點(diǎn)云數(shù)據(jù)都分割完為止，形成有效分割區(qū)域。

5 實(shí)驗(yàn)結(jié)果及分析

三維點(diǎn)云數(shù)據(jù)分割與數(shù)據(jù)本身特點(diǎn)以及應(yīng)用領(lǐng)域密切相關(guān)。目前，對于分割效果的評價(jià)問題仍然尚未解決，沒有一個(gè)定性和定量的指標(biāo)對分割效果進(jìn)行評估，只能利用目視分析的方法對點(diǎn)云數(shù)據(jù)分割效果進(jìn)行定性評價(jià)。本文通過最小剪切分割算法[20]、區(qū)域生長算法[14]與改進(jìn)的八連通局部表面凸性點(diǎn)云分割算法對同一場景數(shù)據(jù)的分割結(jié)果對比，對本文改進(jìn)算法的分割效果進(jìn)行評價(jià)。

為了驗(yàn)證文中算法的有效性，現(xiàn)選取實(shí)驗(yàn)數(shù)據(jù)進(jìn)行算法評估。此處選取的分割實(shí)驗(yàn)數(shù)據(jù)為德國卡爾斯魯厄理工學(xué)院和芝加哥豐田技術(shù)研究所聯(lián)合創(chuàng)辦的自主駕駛平臺(tái)Annieway在卡爾斯魯厄進(jìn)行實(shí)際路面探測所獲得的三維點(diǎn)云數(shù)據(jù)，Annieway裝配有Velodyne HDL-64E激光掃描儀，可以實(shí)時(shí)釆集360°全景的三維信息。在算法評估時(shí)選取了兩個(gè)不同的場景，場景A為十字路口，該區(qū)域路面開闊，但并不平坦，路面上分布著正在行駛的車輛、步行和騎自行車的人，路邊還零星分布著路燈和樹木，路面兩側(cè)還有圍墻遮擋，路面情況復(fù)雜。場景B為拐角路口，路邊有圍墻遮擋，一輛汽車停放在拐角處，拐角另一邊還分布有幾棵樹，旁邊還有一個(gè)長著植物的花壇。兩個(gè)場景的實(shí)際信息十分復(fù)雜，需要處理的數(shù)據(jù)點(diǎn)較多。

為了獲得最優(yōu)的分割結(jié)果，避免過分分割和不充分分割，通過多次數(shù)據(jù)測試和分割效果分析，對實(shí)驗(yàn)參數(shù)進(jìn)行優(yōu)化，將各個(gè)參數(shù)閾值分別設(shè)定為：vnSim=14.806 2°，vconv=-7.67°，vnSimF=10，vconvF=1.165，vrDiff=0.148，vrNDiff=1.907 82，vrSB=0.03 m，vωOB=2，這些參數(shù)閾值的設(shè)定值對任意場景均可適用。分割標(biāo)準(zhǔn)閾值vst的取值范圍為0.2～0.5，分割某一場景時(shí)，只需調(diào)整優(yōu)化vst的大小，即可獲得最優(yōu)分割結(jié)果。經(jīng)過驗(yàn)證，分割場景A和B的數(shù)據(jù)時(shí)，vst取0.38分割效果最優(yōu)。

圖3 3種算法對場景A進(jìn)行分割的結(jié)果 Fig.3 Segmentation results of three algorithms for scene A

圖3和圖4分別為3種分割算法對場景A和場景B的分割結(jié)果，在結(jié)果圖中將分割出的不同物體利用不同顏色標(biāo)示。對比兩種場景的分割結(jié)果圖，圖3和圖4中(a)圖利用最小剪切算法的分割效果最差，只能將數(shù)據(jù)場景中體積較大物體的大概輪廓分割出來，無法分辨場景中具體的物體信息；圖3 圖4中(b)圖和(c)圖利用區(qū)域生長算法和八連通局部表面凸性算法獲得的分割效果明顯，能夠?qū)?shí)驗(yàn)數(shù)據(jù)場景清晰展現(xiàn)出來；圖3和圖4中(b)圖中對于地面、墻面、汽車等具有平面結(jié)構(gòu)且形狀較為規(guī)則的物體都是用不同顏色標(biāo)示的，分割效果較好，而對于形狀不規(guī)則的行人、植物等都不能較好分割。而在本文改進(jìn)的八連通局部表面凸性算法的分割結(jié)果在圖3和圖4的(c)圖中可以看到顏色標(biāo)示分明，對于形狀規(guī)則的地面、墻面、汽車以及形狀不規(guī)則的行人、植物等都取得了較好的分割結(jié)果，不同物體之間對比明顯。

圖4 3種算法對場景B進(jìn)行分割的結(jié)果 Fig.4 Segmentation results of three algorithms for scene B

圖5 兩種算法分割結(jié)果 Fig.5 Segmentation results of two algorithms

在場景A中選取一小塊場景利用區(qū)域生長算法和八連通局部表面凸性算法進(jìn)行分割，結(jié)果如圖5所示。區(qū)域生長算法結(jié)果圖5(a)中騎自行車的人只有頭部附近是用與地面不同的顏色進(jìn)行標(biāo)示的，身體下部、自行車以及旁邊的汽車下部都與地面顏色相同，不能區(qū)分，車后的路燈以及旁邊站著的行人已經(jīng)完全無法分辨。而本文所采用的八連通局部表面凸性算法結(jié)果圖5(b)中汽車與車后的路燈及行人分割比較完整，用與地面不同的顏色標(biāo)示，能夠清楚分辨出來，騎自行車的人與地面顏色對比鮮明，清晰可辨，但自行車下部與地面接觸的部分與地面分割到一起，說明該算法在分割細(xì)節(jié)方面仍有待改進(jìn)。

選取場景A中有代表性的物體數(shù)目進(jìn)行統(tǒng)計(jì)，如表1所示。對統(tǒng)計(jì)結(jié)果進(jìn)行分析，區(qū)域生長算法能提取到83%的有效數(shù)據(jù)點(diǎn)，而八連通局部表面凸性算法能提取到90%的有效數(shù)據(jù)點(diǎn)，在數(shù)據(jù)點(diǎn)提取方面，八連通局部表面凸性算法效果較好。對于車輛等具有平面結(jié)構(gòu)的規(guī)則物體，兩種算法都能進(jìn)行有效分割，分割效果都比較好。對于行人、路燈等形狀不規(guī)則的物體的分割，區(qū)域生長算法的對物體分割的完整度遠(yuǎn)遠(yuǎn)比不上八連通局部表面凸性算法。綜合分析，八連通局部表面凸性算法更適用于復(fù)雜環(huán)境散亂點(diǎn)云數(shù)據(jù)的分割。

表1 分割結(jié)果統(tǒng)計(jì)

6 結(jié) 論

本文采用連通點(diǎn)集的方式對局部表面凸性的點(diǎn)云分割算法進(jìn)行改進(jìn)，用連通點(diǎn)集代替三角網(wǎng)格確定鄰近點(diǎn)關(guān)系，將獲取的連通點(diǎn)集作為分割所需要的局部子點(diǎn)集進(jìn)行分割。根據(jù)實(shí)際城市路面三維點(diǎn)云數(shù)據(jù)分割實(shí)驗(yàn)和3種算法的對比分析，可知本文提出的八連通局部表面凸性點(diǎn)云分割算法，對實(shí)際路面點(diǎn)云數(shù)據(jù)中的物體體積大小、形狀是否規(guī)則都能夠進(jìn)行有效分割。由此可見，八連通局部表面凸性算法對于復(fù)雜環(huán)境散亂點(diǎn)云數(shù)據(jù)具有良好的分割效果，同時(shí)，算法中設(shè)置的分割標(biāo)準(zhǔn)閾值vst可以根據(jù)分割數(shù)據(jù)特點(diǎn)進(jìn)行調(diào)整優(yōu)化，較好的避免了過度分割和不充分分割。實(shí)驗(yàn)表明，本文改進(jìn)的基于連通點(diǎn)集的局部表面凸性點(diǎn)云分割算法在實(shí)際應(yīng)用中能夠同時(shí)分割不平坦路面信息和形狀不規(guī)則的路面物體，有較好的應(yīng)用前景。

[1] 王飛,湯偉,王挺峰,等.8×8APD 陣列激光三維成像接收機(jī)研制[J].中國光學(xué),2015,8(3):422-427. WANG F,TANG W,WANG T F,etal.. Design of 3D laser imaging receiver based on 8×8 APD detector array[J].ChineseOptics,2015,8(3):422-427.(in Chinese)

[2] 孟慶季,張續(xù)嚴(yán),周凌,等.機(jī)載激光 3D 探測成像系統(tǒng)的關(guān)鍵技術(shù)[J].中國光學(xué),2011,4(4):327-339. MENG Q J,ZHANG X Y,ZHOU L,etal.. Key technologies of airborne laser 3D detection imaging system[J].ChineseOptics,2011,4(4):327-339.(in Chinese)

[3] 周森,郭永彩,高潮,等.基于三維激光掃描的移動(dòng)大尺寸圓柱體工件長度快速檢測系統(tǒng)[J].光學(xué) 精密工程,2014,22(6):1524-1530. ZHOU S,GUO Y C,GAO CH,etal.. Rapid length measuring system for mobile and large scale cylinder workpieces based on 3D laser scanning[J].Opt.PrecisionEng.,2014,22(6):1524-1530.(in Chinese)

[4] 呂恒毅,李祥之,韓誠山,等.遙感相機(jī)靜態(tài)調(diào)制傳遞函數(shù)的地面測試原理[J].液晶與顯示,2015,30(5):851-856. LV H Y,LI X ZH,HAN CH SH,etal.. Principle of static modulation transfer function measurement for remote sensing cameras[J].ChineseJ.LiquidCrystalsandDisplays,2015,30(5):851-856.(in Chinese)

[5] 張濤.紅外系統(tǒng)小目標(biāo)成像自動(dòng)調(diào)光方法[J].液晶與顯示,2016,31(4):399-403. ZHANG T. Method of auto light control for small target in infrared system[J].ChineseJ.LiquidCrystalsandDisplays,2016,31(4):399-403.(in Chinese)

[6] 石俊霞,李佩玥,李洪法,等.遙感TDICCD相機(jī)側(cè)擺成像及定位精度優(yōu)化[J].液晶與顯示,2014,29(5):777-784. SHI J X,LI P Y,LI H F,etal.. Scroll imaging of space TDI CCD remote sensing camera and optimazation of image location accuracy[J].ChineseJ.LiquidCrystalsandDisplays,2014,29(5):777-784.(in Chinese)

[7] 靳永亮,王延杰,丁南南,等.改進(jìn)的紅外弱小目標(biāo)檢測方法[J].液晶與顯示,2011,26(4):555-560. JIN Y L,WANG Y J,DING N N,etal.. Improved method for small infrared target detection[J].ChineseJ.LiquidCrystalsandDisplays,2014,29(5):777-784.(in Chinese)

[8] 王田,劉偉寧,孫海江,等.基于復(fù)雜度和方向梯度的紅外弱小目標(biāo)檢測方法[J].液晶與顯示,2012,(5):692-696. WANG T,LIU W N,SUN H J,etal.. Detecting algorithm of infrared small dim targets based on complexity and orientation gradient[J].ChineseJ.LiquidCrystalsandDisplays,2012,(5):692-696.(in Chinese)

[9] 郭萌,趙巖,王世剛,等.基于區(qū)域選擇的紅外弱小目標(biāo)超分辨率復(fù)原算法[J].液晶與顯示,2016,31(4):415-420. GUO M,ZHAO Y,WANG SH G,etal.. Infrared dim-small target super-resolution restoration algorithm based on region selection[J].ChineseJ.LiquidCrystalsandDisplays,2016,31(4):415-420.(in Chinese)

[10] RABBANI T,VAN DEN HEUVEL F,VOSSELMANN G. Segmentation of point clouds using smoothness constraint [J].InternationalArchivesofPhotogrammetry,RemoteSensingandSpatialInformationSciences,2006,36(5):248-253.

[11] JAGANNATHAN A,MILLER E L. Three-dimensional surface mesh segmentation using curvedness-based region growing approach[J].IEEE,2007,29(12):2195-2204.

[12] ZAVODNY A,FLYNN P,CHEN X. Region extraction in large-scale urban lidar data[J].IEEE,2009:1801-1808.

[13] GUO C,SATO W,HAN L,etal.. Graph-based 2D road representation of 3D point clouds for intelligent vehicles[J].IEEE,2011,30(1):715-721.

[14] KLASING K,WOLLHERR D,BUSS M. A clustering method for efficient segmentation of 3D laser data[J].IEEE,2008:4043-4048.

[15] ZADEH L A. Fuzzy sets as a basis for a theory of possibility[J].FuzzySets&Systems,1978,1(1):3-28.

[16] GOLOVINSKIY A,FUNKHOUSER T. Min-cut based segmentation of point clouds[J].IEEE,2009:39-46.

Improved local convexity algorithm of segmentation for 3D point cloud

WANG Ya-nan1,2, WANG Ting-feng1, TIAN Yu-zhen1*, SUN Tao1

(1.StateKeyLaboratoryofLaserInteractionwithMatter,ChangchunInstituteofOptics,FineMechanicsandPhysics,ChineseAcademyofSciences,Changchun130033,China; 2.UniversityofChineseAcademyofScience,Beijing100049,China)

Segmentation for point cloud is the basis of classification, recognition and reconstruction of point cloud datasets and the segmentation result plays an important role in following research. In this paper, we propose a method using connected point sets to analyze and improve the relationship between adjacent points in the local convexity segmentation, to solve problems of oversegmentation and undersegmentation when using the existing algorithms to segment scattered point cloud data in complex environment in 3D laser imaging system. By this method we use the main vertex and neighbors to constitute connected point sets which can be local point subsets of segmentation and form the effective segmented regions. The method solves the problem of the irregular object′s segmentation, which can not be accomplished by common methods, and improves the accuracy of segmentation. Compared with the min-cut based segmentation and region growing segmentation, the improved local convexity segmentation of connected point sets is better for segmentation results of actual road information, and it can avoid oversegmentation and undersegmentation to some extent. It proved that this method is suitable for segmentation of scattered point cloud data in complex environment.

three-dimensional laser imaging;segmentation for point cloud;connected point sets;local convexity

2017-01-23；

2017-03-30

國家高技術(shù)研究發(fā)展計(jì)劃(863計(jì)劃)資助項(xiàng)目 Supported by National High-tech R&D Program of China

2095-1531(2017)03-0348-07

TN958.98

A

10.3788/CO.20171003.0348

王雅男(1992—)，女，山東德州人，碩士研究生，2014年于哈爾濱工業(yè)大學(xué)獲得學(xué)士學(xué)位，主要從事激光主動(dòng)探測方面的研究。E-mail:arianwang@outlook.com

田玉珍(1985—)，男，內(nèi)蒙古呼和浩特人，博士，助理研究員，主要從事激光主動(dòng)照明成像、激光大氣傳輸湍流效應(yīng)等方面的研究。E-mail:tianyz@ciomp.ac.cn

*Correspondingauthor,E-mailtianyz@ciomp.ac.cn