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

(1 中國科學院 長春光學精密機械與物理研究所激光與物質相互作用國家重點實驗室，吉林 長春 130033;2中國科學院大學，北京 100049)

基于改進的局部表面凸性算法三維點云分割

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

(1中國科學院 長春光學精密機械與物理研究所激光與物質相互作用國家重點實驗室，吉林 長春 130033;2中國科學院大學，北京 100049)

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

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

1 引 言

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

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

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

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

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

2 局部表面凸性

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

用局部凸性衡量兩個相鄰測量點周圍局部表面的特性。如圖1所示，任意兩個點pi和pj，其位移向量di, j=-dj,i，如果兩個法向量ni和nj方向相同或者任一表面上的所有點都處于另一個表面之下，那這兩個點就滿足局部凸性(local convexity)，通常用凸度值ci, j來表示。若兩個點滿足局部凸性，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 局部表面凸性的點云分割算法

算法的主要步驟是：

(1)鄰近點關系分析

為減少鄰近點搜索耗費的時間，對點云數(shù)據(jù)進行預處理，通過三角剖分，建立各數(shù)據(jù)點之間的直接相鄰關系，構建局部連通點集，為分割判斷提供局部子點集。

(2)邊界判定

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

(3)

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

(3)確定邊界量bi,j

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

(4)

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

(4)確定點云數(shù)據(jù)分割標準

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

(5)

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

4 鄰近點關系分析改進

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

圖2 兩種連通點集 Fig.2 Two connected point sets

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

5 實驗結果及分析

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

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

為了獲得最優(yōu)的分割結果，避免過分分割和不充分分割，通過多次數(shù)據(jù)測試和分割效果分析，對實驗參數(shù)進行優(yōu)化，將各個參數(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ù)閾值的設定值對任意場景均可適用。分割標準閾值vst的取值范圍為0.2～0.5，分割某一場景時，只需調整優(yōu)化vst的大小，即可獲得最優(yōu)分割結果。經(jīng)過驗證，分割場景A和B的數(shù)據(jù)時，vst取0.38分割效果最優(yōu)。

圖3 3種算法對場景A進行分割的結果 Fig.3 Segmentation results of three algorithms for scene A

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

圖4 3種算法對場景B進行分割的結果 Fig.4 Segmentation results of three algorithms for scene B

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

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

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

表1 分割結果統(tǒng)計

6 結 論

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

[1] 王飛,湯偉,王挺峰,等.8×8APD 陣列激光三維成像接收機研制[J].中國光學,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ù)嚴,周凌,等.機載激光 3D 探測成像系統(tǒng)的關鍵技術[J].中國光學,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] 周森,郭永彩,高潮,等.基于三維激光掃描的移動大尺寸圓柱體工件長度快速檢測系統(tǒng)[J].光學 精密工程,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] 呂恒毅,李祥之,韓誠山,等.遙感相機靜態(tài)調制傳遞函數(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)小目標成像自動調光方法[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相機側擺成像及定位精度優(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].液晶與顯示,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] 王田,劉偉寧,孫海江,等.基于復雜度和方向梯度的紅外弱小目標檢測方法[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ū)域選擇的紅外弱小目標超分辨率復原算法[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

國家高技術研究發(fā)展計劃(863計劃)資助項目 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è)大學獲得學士學位，主要從事激光主動探測方面的研究。E-mail:arianwang@outlook.com

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

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