融合圖像邊緣的區(qū)域生長(zhǎng)點(diǎn)云分割算法

施庭雨,黃麗婷,林靖宇,,謝勝利

1(廣西大學(xué) 電氣工程學(xué)院,南寧 530004)2(廣東工業(yè)大學(xué) 自動(dòng)化學(xué)院,廣州 510006) E-mail：tyshi123@sina.cn

1 引 言

點(diǎn)云是無(wú)序的三維點(diǎn)集.點(diǎn)云分割是根據(jù)點(diǎn)云中的局部特征對(duì)三維點(diǎn)進(jìn)行分類(lèi),將具有相似屬性的點(diǎn)歸為一類(lèi),使之劃分為互不相交的集合、同一集合內(nèi)的點(diǎn)具有相似特征,從而得到感興趣的目標(biāo)對(duì)象.點(diǎn)云分割有助于場(chǎng)景分析,如定位和對(duì)象識(shí)別、分類(lèi)和特征提取、物體識(shí)別等,是點(diǎn)云數(shù)據(jù)處理的關(guān)鍵環(huán)節(jié)之一[1].

區(qū)域生長(zhǎng)源于圖像分割算法,后來(lái)擴(kuò)展到點(diǎn)云分割算法.其思想是先選定種子點(diǎn),由種子點(diǎn)開(kāi)始擴(kuò)散,判斷其周?chē)徲螯c(diǎn)是否屬于同一個(gè)曲面,直到擴(kuò)散至鄰域不存在連續(xù)點(diǎn)集為止,最后組合這些鄰域構(gòu)成區(qū)域[2,3].這種算法復(fù)雜度低,容易實(shí)現(xiàn),因此得到了廣泛應(yīng)用.

區(qū)域生長(zhǎng)算法對(duì)種子點(diǎn)的選擇以及相關(guān)生長(zhǎng)策略的設(shè)計(jì)非常依賴(lài).如果種子點(diǎn)選擇不當(dāng)或者生長(zhǎng)策略設(shè)計(jì)不當(dāng),會(huì)出現(xiàn)欠分割或者過(guò)分割現(xiàn)象,從而影響到分割精度[4].對(duì)于種子點(diǎn)的選擇,許多區(qū)域生長(zhǎng)算法都是以平面分割為目標(biāo),Ning等[5]對(duì)于種子點(diǎn)的選擇是先為某個(gè)點(diǎn)及其相鄰點(diǎn)設(shè)計(jì)一個(gè)擬合平面,然后選擇對(duì)擬合平面殘差最小的點(diǎn)作為種子點(diǎn),殘差通常由一個(gè)點(diǎn)與其擬合平面之間的距離或點(diǎn)的曲率來(lái)估計(jì),殘差最小的點(diǎn)作為種子點(diǎn)會(huì)從點(diǎn)云中最平滑的區(qū)域開(kāi)始分割,對(duì)于特征變化顯著的部分通常會(huì)被識(shí)別成噪點(diǎn)而移除.Vo等[6]根據(jù)不同的數(shù)據(jù)集進(jìn)行預(yù)定義和調(diào)整,不同的數(shù)據(jù)集種子點(diǎn)的選擇也會(huì)較大的差異,如果種子點(diǎn)選擇有誤會(huì)使區(qū)域增長(zhǎng)產(chǎn)生非均勻性問(wèn)題.稠密點(diǎn)云數(shù)據(jù)量較大,并具有較多的鄰域點(diǎn),使用常規(guī)的點(diǎn)云分割算法會(huì)使分割效率偏低,Chen等[7]根據(jù)數(shù)據(jù)的特征進(jìn)行相應(yīng)的下采樣,但是下采樣會(huì)使具體的分割結(jié)果需要在精度和效率之間進(jìn)行權(quán)衡.Huang等[8]采用隨機(jī)采樣一致性(Random Sample Consensus,RANSAC)算法獲取種子點(diǎn),但是基于此法進(jìn)行區(qū)域生長(zhǎng)容易出現(xiàn)分割不穩(wěn)定的情況,即分割結(jié)果出現(xiàn)欠分割或者過(guò)分割現(xiàn)象.對(duì)于相關(guān)生長(zhǎng)策略的設(shè)計(jì),需要根據(jù)不同的點(diǎn)云特征設(shè)計(jì)出與之相應(yīng)的相似性判定依據(jù),通常使用幾何特征如歐幾里得距離、法向量或曲率作為相似性的判定依據(jù).Ning等[5]以法向量為法向量作為判定依據(jù),使得共面可以共享共同的法向量,但是在特征變化幅度較大的點(diǎn)云中,會(huì)因共同的法向量較少影響到分割精度.Xu等[9]應(yīng)用法向量、相鄰點(diǎn)到調(diào)整平面的距離以及當(dāng)前點(diǎn)和候選點(diǎn)之間的距離作為將點(diǎn)合并到種子區(qū)域的標(biāo)準(zhǔn),該種子區(qū)域是在手動(dòng)過(guò)濾邊緣附近區(qū)域后從數(shù)據(jù)集中隨機(jī)選取的,對(duì)于分割結(jié)果好壞的影響會(huì)有一定隨機(jī)性.Dong等[10]采用兩點(diǎn)之間的法向量夾角以及當(dāng)前點(diǎn)的曲率作為相似性度量的依據(jù),但是使用該幾何特征作為判定依據(jù)容易因種子點(diǎn)特征造成的閾值設(shè)定不當(dāng)而影響到分割精度,如閾值設(shè)置過(guò)大會(huì)導(dǎo)致分割不完全;閾值設(shè)置過(guò)小會(huì)導(dǎo)致很多點(diǎn)被識(shí)別成噪點(diǎn).

點(diǎn)云中一般將強(qiáng)度變化顯著的三維點(diǎn)定義為邊緣點(diǎn),邊緣主要存在于目標(biāo)與目標(biāo)、目標(biāo)與背景、區(qū)域與區(qū)域之間.點(diǎn)云的邊緣可以描述點(diǎn)云物體形狀的基本特征,可以劃分出目標(biāo)分割的區(qū)域,作為分割的界限[11,12],所以設(shè)定邊緣三維點(diǎn)為種子點(diǎn)向目標(biāo)對(duì)象點(diǎn)云內(nèi)部進(jìn)行分割可以一定程度上避免欠分割和過(guò)分割現(xiàn)象.但是直接使用現(xiàn)有的算法提取目標(biāo)點(diǎn)云邊緣不夠準(zhǔn)確.利用多傳感器融合技術(shù),采用具有互補(bǔ)特性的不同傳感器來(lái)增強(qiáng)感知能力,可以解決邊緣定位問(wèn)題.例如融合激光雷達(dá)與RGB相機(jī),利用二維RGB圖像豐富的顏色信息和紋理信息快速定位目標(biāo)對(duì)象,采用圖像邊緣提取算法提取出目標(biāo)對(duì)象邊緣[13],再通過(guò)標(biāo)定后得到的對(duì)齊關(guān)系提取出與圖像相對(duì)應(yīng)點(diǎn)云中目標(biāo)對(duì)象的邊緣.

綜上,本文提出一種以目標(biāo)點(diǎn)云的邊緣點(diǎn)作為種子點(diǎn)的區(qū)域生長(zhǎng)分割算法,借助圖像提取目標(biāo)點(diǎn)云的邊緣作為種子點(diǎn),并根據(jù)邊緣性質(zhì)設(shè)計(jì)出相應(yīng)的生長(zhǎng)策略進(jìn)行分割,可以以高精度分割出稠密點(diǎn)云中的目標(biāo)點(diǎn)云,并且可以較大程度地避免欠分割與過(guò)分割現(xiàn)象.本文算法的實(shí)驗(yàn)數(shù)據(jù)和MATLAB代碼可以在https：//github.com/SCVision/PointCloud-Image-Segmentation下載.

2 算法描述

2.1 概述

本文的點(diǎn)云分割算法具體可以分為兩個(gè)部分：標(biāo)定部分和分割部分.

標(biāo)定部分建立二維RGB圖像和三維點(diǎn)云之間的對(duì)齊關(guān)系.首先將相機(jī)和激光雷達(dá)組成采集系統(tǒng),并采用該系統(tǒng)采集標(biāo)定板在不同角度和不同位置的二維RGB圖像和三維點(diǎn)云數(shù)據(jù);然后使用張正友標(biāo)定法[14]獲得相機(jī)內(nèi)部參數(shù)矩陣;接著提取棋盤(pán)格內(nèi)角點(diǎn)的像素坐標(biāo)和三維點(diǎn)云坐標(biāo)并使用透視三點(diǎn)(Perspective-three-Point,P3P)算法[15]獲得聯(lián)合外參;最后是將得到的聯(lián)合外參與相機(jī)內(nèi)參結(jié)合建立出相機(jī)像素點(diǎn)和激光雷達(dá)三維點(diǎn)的對(duì)齊關(guān)系.本文所涉及的坐標(biāo)系和相關(guān)參數(shù)定義如表1所示.

表1 坐標(biāo)系和相關(guān)參數(shù)定義Table 1 Coordinate system and related parameters

分割部分通過(guò)融合RGB圖像提取目標(biāo)點(diǎn)云的邊緣并將邊緣點(diǎn)設(shè)定為種子點(diǎn)進(jìn)行區(qū)域生長(zhǎng)分割得到目標(biāo)點(diǎn)云.首先利用已經(jīng)標(biāo)定過(guò)的相機(jī)和激光雷達(dá)分別采集目標(biāo)對(duì)象的RGB圖像和三維點(diǎn)云數(shù)據(jù),并對(duì)圖像中的目標(biāo)對(duì)象邊緣進(jìn)行提取,計(jì)算原始點(diǎn)云中所有點(diǎn)的法線(xiàn)與曲率;然后根據(jù)聯(lián)合標(biāo)定得到的對(duì)齊關(guān)系,對(duì)原始點(diǎn)云建立三維點(diǎn)到像素點(diǎn)的映射關(guān)系,計(jì)算點(diǎn)云三維點(diǎn)對(duì)應(yīng)的像素點(diǎn)到目標(biāo)點(diǎn)云邊緣點(diǎn)的歐氏距離與距離閾值比較來(lái)判斷目標(biāo)點(diǎn)云的邊緣,將小于閾值的三維點(diǎn)確定為邊緣點(diǎn);接著將目標(biāo)點(diǎn)云的邊緣點(diǎn)劃入種子點(diǎn)集中,并通過(guò)目標(biāo)點(diǎn)云邊緣確定分割界限,從種子點(diǎn)集中選擇一個(gè)種子點(diǎn)進(jìn)行區(qū)域生長(zhǎng)分割,通過(guò)搜索種子點(diǎn)的鄰域點(diǎn),對(duì)鄰域點(diǎn)是否在分割界限內(nèi)進(jìn)行判斷,如果在界限內(nèi)則將其曲率與閾值進(jìn)行比較,小于閾值的劃入種子點(diǎn)集中,大于閾值的計(jì)算鄰域點(diǎn)與種子點(diǎn)的法線(xiàn)夾角,如果夾角小于閾值則將種子點(diǎn)與鄰域點(diǎn)放入聚類(lèi)點(diǎn)集中并從種子點(diǎn)集中刪除該種子點(diǎn),大于閾值則繼續(xù)搜索下一個(gè)鄰域點(diǎn);最后當(dāng)種子點(diǎn)集為空時(shí)結(jié)束,將聚類(lèi)點(diǎn)集作為分割結(jié)果.具體分割流程如圖1所示.

圖1 分割流程圖Fig.1 Flowchart of the segmentation

2.2 相機(jī)與激光雷達(dá)標(biāo)定

進(jìn)行相機(jī)與激光雷達(dá)標(biāo)定的目的是為了獲取相機(jī)與激光雷達(dá)的聯(lián)合外參,建立相機(jī)坐標(biāo)與激光雷達(dá)坐標(biāo)的對(duì)齊關(guān)系,實(shí)現(xiàn)激光雷達(dá)坐標(biāo)到像素坐標(biāo)的映射,為后續(xù)的目標(biāo)點(diǎn)云邊緣提取做準(zhǔn)備.

(1)

(2)

在獲得相機(jī)內(nèi)參矩陣后,需要對(duì)相機(jī)與激光雷達(dá)的聯(lián)合外參進(jìn)行求解.P3P算法[15]可以將3D-2D問(wèn)題轉(zhuǎn)換為3D-3D問(wèn)題,即把透視n點(diǎn)(Perspective-n-Point,PnP)問(wèn)題轉(zhuǎn)換為最近點(diǎn)迭代(Iterative Closest Point,ICP)問(wèn)題[17],從而求解出相機(jī)與激光雷達(dá)聯(lián)合外參.

根據(jù)投影原理建立激光雷達(dá)點(diǎn)PL(i)與像素點(diǎn)pP(i)的幾何關(guān)系,具體如圖2所示.

圖2 激光雷達(dá)點(diǎn)與像素點(diǎn)的幾何關(guān)系Fig.2 Geometric relationship between LiDAR points and pixels

根據(jù)圖2的幾何關(guān)系,結(jié)合相似三角形原理可以得到激光雷達(dá)點(diǎn)PL(i)與像素點(diǎn)pP(i)的關(guān)系

(3)

在激光雷達(dá)采集到的含有標(biāo)定板的三維精細(xì)點(diǎn)云中,可以提取出標(biāo)定板的點(diǎn)云.用隨機(jī)采樣一致性(Random Sample Consensus,RANSAC)算法[8]對(duì)提取出的標(biāo)定板點(diǎn)云進(jìn)行平面擬合并提取標(biāo)定板的4個(gè)頂點(diǎn),根據(jù)Z值由高到低進(jìn)行排序,得到標(biāo)定板點(diǎn)云4個(gè)頂點(diǎn)的激光雷達(dá)坐標(biāo)PL-vtx(i)(XL(i),YL(i),ZL(i)),其中i=1,2,3,4,Z1≥Z2>Z3≥Z4.通過(guò)PL-vtx(2)-PL-vtx(1)可以得到x軸向量x,PL-vtx(3)-PL-vtx(1)可以得到y(tǒng)軸向量y.設(shè)根據(jù)Z值從高到低排序后的標(biāo)定板點(diǎn)云內(nèi)角點(diǎn)激光雷達(dá)坐標(biāo)為PL-cnr(i,j)(XL(i,j),YL(i,j),ZL(i,j)),其中i=1,2,…,m-1,j=1,2,…,n-1,可以建立轉(zhuǎn)換關(guān)系：

(4)

由此可以計(jì)算出標(biāo)定板點(diǎn)云內(nèi)角點(diǎn)激光雷達(dá)坐標(biāo)PL-cnr(i,j),其中i=1,2,…,m-1,j=1,2,…,n-1,ZL(i,j)≥ZL(i+1,j+1).

代入根據(jù)v值從高到低排序好的標(biāo)定板棋盤(pán)格內(nèi)角點(diǎn)像素坐標(biāo)pP-cnr(i,j)和激光雷達(dá)坐標(biāo)PL-cnr(i,j)到公式(3)中,經(jīng)過(guò)求解可以得到激光雷達(dá)坐標(biāo)P′L(i,j)(XL(i,j),YL(i,j),ZL(i,j))及其對(duì)應(yīng)的像素坐標(biāo)P′P(i,j)(XP(i,j),YP(i,j),ZP(i,j)).

根據(jù)P3P算法,兩組三維點(diǎn)存在變換關(guān)系：

?i,P′P(i,j)=RP′L(i,j)+t

(5)

代入P′P(i,j)與P′L(i,j)到公式(5)中,計(jì)算出聯(lián)合外參的旋轉(zhuǎn)矩陣R和平移向量t.

最后根據(jù)相機(jī)內(nèi)參矩陣K、聯(lián)合外參的旋轉(zhuǎn)矩陣R,平移向量t,得到像素點(diǎn)pP與激光雷達(dá)點(diǎn)PL之間的對(duì)齊關(guān)系：

pP=K·R·(PL-t)

(6)

標(biāo)定結(jié)果的精度高低會(huì)直接影響到后續(xù)目標(biāo)點(diǎn)云邊緣提取的效果.造成標(biāo)定誤差的因素有很多,其中包含標(biāo)定板制作、相機(jī)分辨率、目標(biāo)對(duì)象距離和使用的特征提取算法精度等.在使用分辨率較低的相機(jī)進(jìn)行圖像采集時(shí),目標(biāo)物體會(huì)因?yàn)榉直媛瘦^低而造成特征不明顯,在進(jìn)行內(nèi)角點(diǎn)提取時(shí)會(huì)有較大的偏差;在世界場(chǎng)景中,當(dāng)激光雷達(dá)距離目標(biāo)物體較遠(yuǎn)時(shí),會(huì)使點(diǎn)云中目標(biāo)物體部分的三維點(diǎn)比較稀疏,從而造成目標(biāo)物體點(diǎn)云的邊緣特征不顯著,在進(jìn)行平面邊緣擬合時(shí)會(huì)有較大的誤差;聯(lián)合外參的旋轉(zhuǎn)矩陣也會(huì)受到目標(biāo)對(duì)象距離的影響,距離越遠(yuǎn),偏移越大,旋轉(zhuǎn)矩陣的誤差也越大.本文無(wú)法對(duì)影響標(biāo)定精度的因素逐一分析,本文假設(shè)在標(biāo)定板制作、特征提取算法精度高的理想情況下,使用高分辨率(5184×3456)相機(jī)與激光雷達(dá)構(gòu)建固定的采集系統(tǒng),設(shè)定采集系統(tǒng)與目標(biāo)物體距離不超過(guò)激光雷達(dá)有效測(cè)量距離1/2的情況下進(jìn)行數(shù)據(jù)采集,以保證標(biāo)定產(chǎn)生的誤差不會(huì)對(duì)后續(xù)的目標(biāo)點(diǎn)云邊緣提取造成影響.

2.3 目標(biāo)點(diǎn)云邊緣提取

確定目標(biāo)點(diǎn)云的邊緣并以邊緣進(jìn)行分割有助于提高分割的效率與精度,但是點(diǎn)云包含的空間信息多于二維圖像,其對(duì)應(yīng)幾何結(jié)構(gòu)更復(fù)雜,無(wú)序點(diǎn)云的鄰域結(jié)構(gòu)非常復(fù)雜,同時(shí)也存在噪聲、密度不均勻、遮擋等問(wèn)題,通常需要對(duì)原始的三維點(diǎn)云數(shù)據(jù)進(jìn)行手動(dòng)分割、目標(biāo)識(shí)別等步驟,再根據(jù)某一特定目標(biāo)檢測(cè)邊緣,所以直接對(duì)點(diǎn)云邊緣進(jìn)行提取與分割的效率與精度都比較低[17].從圖像中進(jìn)行邊緣檢測(cè)與提取的方法效率與精度都比較高,因此可以借助與點(diǎn)云相對(duì)應(yīng)的二維圖像進(jìn)行目標(biāo)點(diǎn)云邊緣的提取.

在對(duì)點(diǎn)云進(jìn)行目標(biāo)對(duì)象邊緣的三維點(diǎn)提取之前,需要先對(duì)圖像中的目標(biāo)對(duì)象進(jìn)行邊緣提取.由于本文的研究重點(diǎn)為點(diǎn)云分割算法,故對(duì)圖像中的目標(biāo)對(duì)象采用手動(dòng)提取.提取出目標(biāo)對(duì)象后,采用Canny算法[18]行邊緣提取,獲得邊緣的所有像素點(diǎn)集合{pP-edge(u,v)}.

根據(jù)公式(6)的對(duì)齊關(guān)系,原始點(diǎn)云中的所有三維點(diǎn){PL(XL,YL,ZL)}轉(zhuǎn)換為對(duì)應(yīng)圖像的像素點(diǎn){pL(u,v)},同時(shí)在轉(zhuǎn)換的過(guò)程中為每一個(gè)從原始點(diǎn)云三維點(diǎn)轉(zhuǎn)換的像素點(diǎn)建立該像素點(diǎn)映射到其對(duì)應(yīng)三維點(diǎn)的索引pL(i)→PL(i),供之后在提取目標(biāo)點(diǎn)云邊緣時(shí)調(diào)用并查詢(xún),即：

(ui,vi)→(XL(i),YL(i),ZL(i))

(7)

在將原始點(diǎn)云中所有的三維點(diǎn)從三維坐標(biāo)PL(XL,YL,ZL)轉(zhuǎn)換為像素坐標(biāo)pL(u,v)并建立好索引表{(pL,PL)}后,取其中一個(gè)像素點(diǎn)pL(i)(ui,vi),計(jì)算該點(diǎn)到圖像中目標(biāo)對(duì)象邊緣像素點(diǎn)任意一點(diǎn)pP-edge(j)(uj,vj)的歐氏距離d(i,j),即：

(8)

在公式(8)中依次代入{pP-edge}和{pL}中所有的像素點(diǎn)進(jìn)行計(jì)算,設(shè)定距離閾值ε,當(dāng)d(i,j)<ε時(shí),將點(diǎn)pL(i)確定為目標(biāo)點(diǎn)云的邊緣點(diǎn),再調(diào)用索引表{(pL,PL)}查詢(xún)pL(i)→PL(i)的映射關(guān)系,將與pL(i)對(duì)應(yīng)的點(diǎn)PL(i)劃入目標(biāo)點(diǎn)云邊緣的候選集{P′L-edge(XL,YL,ZL)}中,最后將候選集中重復(fù)點(diǎn)去除并對(duì)孤立的離群點(diǎn)進(jìn)行濾波,得到目標(biāo)點(diǎn)云的邊緣點(diǎn)集{PL-edge(XL,YL,ZL)}.目標(biāo)點(diǎn)云邊緣的密集程度與ε成正比,點(diǎn)云數(shù)據(jù)中每一個(gè)點(diǎn)表達(dá)一定的信息量,某個(gè)區(qū)域點(diǎn)越密集有用的信息量越大.孤立的離群點(diǎn)信息量較小,其表達(dá)的信息量可以忽略不計(jì).

2.4 種子點(diǎn)和生長(zhǎng)策略的設(shè)定

傳統(tǒng)的基于區(qū)域生長(zhǎng)點(diǎn)云分割算法中因種子點(diǎn)選取不當(dāng)或特征提取不準(zhǔn)確、無(wú)法得到確定的分割邊緣等問(wèn)題,易出現(xiàn)目標(biāo)點(diǎn)云出現(xiàn)欠分割或過(guò)分割現(xiàn)象[4].針對(duì)這些不足,本文通過(guò)目標(biāo)點(diǎn)云邊緣確定分割界限,并將邊緣點(diǎn)劃入種子點(diǎn)集來(lái)進(jìn)行區(qū)域生長(zhǎng)分割.邊緣點(diǎn)具有強(qiáng)度變化顯著的特點(diǎn),因此可以有效確定目標(biāo)分割的區(qū)域,避免出現(xiàn)欠分割以及過(guò)分割現(xiàn)象.最后根據(jù)邊緣的性質(zhì)設(shè)計(jì)出相應(yīng)的生長(zhǎng)策略進(jìn)行分割,從而得到分割結(jié)果.

目標(biāo)點(diǎn)云的分割界限可以通過(guò)目標(biāo)點(diǎn)云的邊緣確定.在目標(biāo)點(diǎn)云邊緣點(diǎn)集合中,從所有邊緣點(diǎn)坐標(biāo)中取最大的X值,Y值和Z值作為分割的上限,記為Xmax,Ymax和Zmax;從所有邊緣點(diǎn)坐標(biāo)中取最小的X值,Y值和Z值作為分割的下限,記為Xmin,Ymin和Zmin.

在進(jìn)行區(qū)域生長(zhǎng)分割點(diǎn)云之前需要求解原始點(diǎn)云的法向量與曲率.由于法向量的特性是垂直于其當(dāng)前點(diǎn)所在的切平面,所以需要先通過(guò)當(dāng)前點(diǎn)的鄰近點(diǎn)擬合出一個(gè)局部平面再進(jìn)行法向量的求解.擬合出的平面應(yīng)當(dāng)具有候選點(diǎn)到這個(gè)平面距離最小的性質(zhì).用主元分析(Principal Component Analysis,PCA)算法[19]可以找到一組新的變換后的正交基,這組正交基是給定點(diǎn)集的最佳表達(dá),使得變換后的數(shù)據(jù)有著最大的方差.具體來(lái)說(shuō),根據(jù)原始點(diǎn)云中的當(dāng)前點(diǎn)選擇k個(gè)近鄰點(diǎn),并建立一個(gè)平面,使得當(dāng)前點(diǎn)與選出的k個(gè)近鄰點(diǎn)到這個(gè)平面的距離最小,計(jì)算得到趨近擬合平面中心點(diǎn)的目標(biāo)點(diǎn),將k個(gè)近鄰點(diǎn)到目標(biāo)點(diǎn)的向量組成矩陣Y,求出協(xié)方差矩陣S=YYΤ的特征值λ1,λ2,λ3,并從中選出最小的特征值λmin,對(duì)應(yīng)的單位特征矢量n就是法線(xiàn)矢量,該點(diǎn)的曲率H為：

(9)

計(jì)算得到{PL}中每個(gè)點(diǎn)的法向量n與曲率H后完成對(duì)原始點(diǎn)云的預(yù)處理.

由于傳統(tǒng)的區(qū)域生長(zhǎng)算法需要根據(jù)選定的種子點(diǎn)的性質(zhì)設(shè)定相應(yīng)的生長(zhǎng)策略進(jìn)行點(diǎn)云分割,不同的種子點(diǎn)性質(zhì)各不相同,故本文根據(jù)邊緣點(diǎn)性質(zhì)設(shè)計(jì)出了相應(yīng)的分割算法.將上一步得到的目標(biāo)點(diǎn)云分割界限Xmax,Ymax,Zmax,Xmin,Ymin,Zmin,近鄰點(diǎn)數(shù)k以及計(jì)算出每個(gè)點(diǎn)法向量n與曲率H后的原始點(diǎn)云{PL};第2.3節(jié)得到的目標(biāo)點(diǎn)云邊緣{PL-edge};設(shè)定的法向量角度閾值θth和點(diǎn)法向量閾值Hth作為輸入,聚類(lèi)三維點(diǎn)集C作為分割結(jié)果并作為輸出.

將{PL-edge}設(shè)置為種子點(diǎn)集合Q={PL-seed}后,對(duì)種子點(diǎn)PL-seed進(jìn)行近鄰點(diǎn)搜索,在分割界限內(nèi)的近鄰點(diǎn)設(shè)為PL-ngb,如果PL-ngb的曲率HL-ngb

(10)

其中nL-seed為PL-seed的法向量,nL-ngb為PL-ngb的法向量.

表2 基于邊緣的區(qū)域生長(zhǎng)分割算法實(shí)現(xiàn)Table 2 Algorithm for region growing segmentation with edge

如果θL-ngb<θth且PL-seed和PL-ngb不屬于C,將PL-seed和PL-ngb劃入C中,并將PL-seed從Q中刪除,直到Q為空停止,輸出C作為分割結(jié)果.

基于邊緣的區(qū)域生長(zhǎng)分割算法的具體偽代碼表述如表2所示.

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

3.1 相機(jī)與激光雷達(dá)標(biāo)定

實(shí)驗(yàn)系統(tǒng)的相機(jī)采用佳能EOS 1300D數(shù)碼單反相機(jī)(分辨率5184×3456);三維激光雷達(dá)采用北陽(yáng)URG-4LX-UG01和旋轉(zhuǎn)云臺(tái)構(gòu)成,可以采集稠密三維點(diǎn)云(垂直684點(diǎn),水平3600點(diǎn)).具體采集裝置如圖3所示.

圖3 數(shù)據(jù)采集裝置Fig.3 Data acquisition device

標(biāo)定中采用7×10的黑白棋盤(pán)格標(biāo)定板,采用數(shù)碼單反相機(jī)和激光雷達(dá)所構(gòu)建的數(shù)據(jù)采集系統(tǒng)同時(shí)采集10組不同位姿下標(biāo)定板的圖像和點(diǎn)云進(jìn)行標(biāo)定.由于激光雷達(dá)的有效測(cè)量距離為5米,故設(shè)定標(biāo)定板擺放的位置與采集系統(tǒng)之間的距離不超過(guò)2米.對(duì)相機(jī)進(jìn)行內(nèi)參標(biāo)定后可以得到相機(jī)內(nèi)參K,對(duì)相機(jī)與激光雷達(dá)進(jìn)行標(biāo)定后采用Levenberg-Marquardt(L-M)算法[20]進(jìn)行非線(xiàn)性?xún)?yōu)化可以得到聯(lián)合外參的旋轉(zhuǎn)矩陣R與平移向量t,其中具體結(jié)果為：

根據(jù)以上參數(shù)可以建立圖像與點(diǎn)云的對(duì)齊關(guān)系(6).

為了驗(yàn)證標(biāo)定精度,使用標(biāo)定后的設(shè)備分別采集10組包含不同矩形目標(biāo)對(duì)象的圖像和點(diǎn)云來(lái)進(jìn)行標(biāo)定誤差分析.通過(guò)包含矩形目標(biāo)對(duì)象的圖像提取出矩形的幾何中心像素坐標(biāo),再手動(dòng)分割出矩形點(diǎn)云并采用對(duì)齊關(guān)系重投影到對(duì)應(yīng)的圖像中,提取出重投影的幾何中心像素坐標(biāo),最后計(jì)算重投影的幾何中心像素坐標(biāo)到幾何中心像素坐標(biāo)的u軸與v軸偏移像素,具體如表3所示.

表3 標(biāo)定中的像素偏移誤差Table 3 Pixel offset error in calibration

根據(jù)表3的結(jié)果,可以看出u軸和v軸的偏移像素最大不超過(guò)10.最后計(jì)算出重投影的幾何中心像素坐標(biāo)到幾何中心像素坐標(biāo)u軸的平均偏移像素為-2.5685,v軸的平均偏移像素為5.1410.由于圖像的分辨率為5184×3456,則u軸的平均相對(duì)誤差為0.0495%,v軸的平均相對(duì)誤差為0.1488%,u軸和v軸的平均相對(duì)誤差均沒(méi)有超過(guò)0.15%,由此可得u軸和v軸像素偏移基本不會(huì)影響到目標(biāo)點(diǎn)云邊緣點(diǎn)提取精度.

3.2 目標(biāo)點(diǎn)云分割

使用已標(biāo)定的設(shè)備進(jìn)行數(shù)據(jù)采集,分別對(duì)含有規(guī)則幾何體、不規(guī)則幾何體以及多個(gè)目標(biāo)物體的場(chǎng)景下進(jìn)行數(shù)據(jù)采集.將采集到的圖像進(jìn)行目標(biāo)對(duì)象邊緣的提取,再根據(jù)公式(6)的對(duì)齊關(guān)系提取出目標(biāo)點(diǎn)云的邊緣三維點(diǎn),最后根據(jù)當(dāng)前原始點(diǎn)云的狀況設(shè)定相關(guān)的閾值并以目標(biāo)點(diǎn)云的邊緣三維點(diǎn)作為種子點(diǎn)對(duì)原始點(diǎn)云進(jìn)行區(qū)域生長(zhǎng)分割,得到目標(biāo)點(diǎn)云.在包含不同目標(biāo)對(duì)象場(chǎng)景下使用本文算法進(jìn)行稠密點(diǎn)云分割的可視化實(shí)驗(yàn)流程具體如圖4所示.

3.3 對(duì)比實(shí)驗(yàn)

從圖4的實(shí)驗(yàn)結(jié)果可以看出,使用本文算法對(duì)原始稠密點(diǎn)云進(jìn)行目標(biāo)點(diǎn)云的分割后,可以比較完整地分割出原始點(diǎn)云中的目標(biāo)點(diǎn)云,但是也存在少量的欠分割以及過(guò)分割問(wèn)題.本文分別對(duì)含有規(guī)則幾何體、不規(guī)則幾何體以及多個(gè)目標(biāo)物體的場(chǎng)景進(jìn)行圖像和點(diǎn)云數(shù)據(jù)的采集,其中每種場(chǎng)景下分別采集包含不同目標(biāo)物體的5組數(shù)據(jù),三種場(chǎng)景下總共采集到15組數(shù)據(jù).再分別采用基于最小曲率值選擇種子點(diǎn)的區(qū)域生長(zhǎng)分割算法[21],基于RANSAC算法選擇種子點(diǎn)的區(qū)域生長(zhǎng)分割算法[22],基于RANSAC算法的歐氏聚類(lèi)算法[23]與本文算法對(duì)原始稠密點(diǎn)云進(jìn)行分割,將不同算法的分割結(jié)果分別與手動(dòng)分割出的目標(biāo)點(diǎn)云進(jìn)行對(duì)比,以此來(lái)驗(yàn)證本文算法的欠分割與過(guò)分割狀況以及分割精度.部分?jǐn)?shù)據(jù)組的實(shí)驗(yàn)結(jié)果如圖5所示.

圖4 在包含不同目標(biāo)對(duì)象場(chǎng)景下使用本文方法分割的可視化實(shí)驗(yàn)流程Fig.4 Visualization experiment procedures of our method in the scene with different objects

圖5 在包含不同目標(biāo)對(duì)象場(chǎng)景下使用不同算法分割的實(shí)驗(yàn)結(jié)果Fig.5 Results of different algorithms in scenes with different objects

從圖5中的實(shí)驗(yàn)直觀(guān)結(jié)果可以看出,在目標(biāo)物體為不規(guī)則物體的實(shí)驗(yàn)場(chǎng)景下,本文算法與基于最小曲率值選擇種子點(diǎn)的區(qū)域生長(zhǎng)分割算法、基于RANSAC算法選擇種子點(diǎn)的區(qū)域生長(zhǎng)分割算法以及基于RANSAC算法的歐氏聚類(lèi)算法相比具有較好的分割結(jié)果.其它算法的分割結(jié)果都有較明顯的欠分割現(xiàn)象和過(guò)分割現(xiàn)象.

為了評(píng)價(jià)本文算法與其它算法的分割性能,本文分別采用欠分割率(Under-Segmentation Rate,UR)、過(guò)分割率(Over-Segmentation Rate,OR)和交并比(Intersection-over-Union,IoU)[24]作為評(píng)價(jià)標(biāo)準(zhǔn)來(lái)評(píng)價(jià)各算法的分割結(jié)果,UR、OR和IoU定義如下：

(11)

(12)

(13)

其中,RS表示手動(dòng)分割出的目標(biāo)點(diǎn)云三維點(diǎn)集合;TS表示算法分割出的目標(biāo)點(diǎn)云三維點(diǎn)集合;RS∩|RS-TS|表示本應(yīng)該包含在分割結(jié)果中,實(shí)際卻不在分割結(jié)果中的三維點(diǎn)集合;TS∩|RS-TS|表示本不應(yīng)該包含在分割結(jié)果中,實(shí)際卻在分割結(jié)果中的三維點(diǎn)集合;RS∩TS表示正確分割的三維點(diǎn)集合.其中UR∈[0,1],UR越大表明欠分割現(xiàn)象越嚴(yán)重;OR∈[0,1],OR越大表明過(guò)分割現(xiàn)象越嚴(yán)重;IoU∈[0,1],IoU越大表明分割精度越高.

具體對(duì)比實(shí)驗(yàn)數(shù)據(jù)如表4所示.其中數(shù)據(jù)集分類(lèi)中原始點(diǎn)云均值表示每種場(chǎng)景下5組原始點(diǎn)云數(shù)據(jù)的平均三維點(diǎn)數(shù),手動(dòng)分割結(jié)果均值表示每種場(chǎng)景下5組原始點(diǎn)云數(shù)據(jù)手動(dòng)分割出的目標(biāo)點(diǎn)云的平均三維點(diǎn)數(shù);算法中curvature+RGS,RANSAC+RGS與RANSAC+ECS分別表示基于最小曲率值選擇種子點(diǎn)的區(qū)域生長(zhǎng)分割算法,基于RANSAC算法選擇種子點(diǎn)的區(qū)域生長(zhǎng)分割算法與基于RANSAC算法的歐氏聚類(lèi)算法;評(píng)價(jià)指標(biāo)中UR、OR、IoU分別表示欠分割率、過(guò)分割率和交并比.

表4 不同場(chǎng)景下的不同區(qū)域生長(zhǎng)分割算法實(shí)驗(yàn)結(jié)果對(duì)比Table 4 Comparison of different region growing segmentation algorithm experimental results in different scenes

根據(jù)表4的結(jié)果,本文算法在對(duì)不同場(chǎng)景下的原始稠密點(diǎn)云進(jìn)行目標(biāo)點(diǎn)云分割時(shí),交并比分別為89.93%,86.28%,85.73%,均達(dá)到了85%以上.在目標(biāo)物體為規(guī)則幾何體的場(chǎng)景中,由于目標(biāo)物體特征變化強(qiáng)度不大,其他算法都可以比較完整地分割出目標(biāo)對(duì)象,本文算法相比其他算法沒(méi)有顯著優(yōu)勢(shì);在目標(biāo)物體為不規(guī)則幾何體的場(chǎng)景中,其他算法會(huì)受到目標(biāo)物體特征變化強(qiáng)度較大的影響而導(dǎo)致分割精度下降,本文算法通過(guò)邊緣確定分割界限可以顯著提高分割精度,相比其他算法有顯著優(yōu)勢(shì);在多個(gè)目標(biāo)物體的場(chǎng)景中,由于目標(biāo)物體包含規(guī)則幾何體與不規(guī)則幾何體,在不規(guī)則幾何體較多的場(chǎng)景中,本文算法相比其他算法有顯著優(yōu)勢(shì).

4 結(jié) 論

為了解決傳統(tǒng)的區(qū)域生長(zhǎng)法因種子點(diǎn)選取不當(dāng)以及生長(zhǎng)策略設(shè)計(jì)不當(dāng)而導(dǎo)致出現(xiàn)欠分割與過(guò)分割現(xiàn)象的問(wèn)題,本文通過(guò)邊緣特征變化顯著的性質(zhì)提出了一種融合圖像提取目標(biāo)點(diǎn)云邊緣并將邊緣點(diǎn)作為種子點(diǎn)的區(qū)域生長(zhǎng)分割算法.實(shí)驗(yàn)結(jié)果表明,該算法在借助圖像提取出目標(biāo)點(diǎn)云邊緣并將邊緣點(diǎn)作為種子點(diǎn)的條件下進(jìn)行分割,可以從數(shù)據(jù)量大的稠密點(diǎn)云中以較高的精度分割出目標(biāo)點(diǎn)云,使得分割結(jié)果在很大程度上避免了欠分割與過(guò)分割現(xiàn)象.

本文沒(méi)有對(duì)算法中的相關(guān)閾值設(shè)置進(jìn)行研究,而是采用人工設(shè)定,用不同閾值進(jìn)行分割與濾波,從中選取最優(yōu)的分割結(jié)果.下一步的研究工作是尋找點(diǎn)云數(shù)據(jù)特征的變化規(guī)律,嘗試自動(dòng)選取合理的閾值參數(shù)的方法,進(jìn)一步提高算法效率.有興趣的讀者可以下載本文算法的實(shí)驗(yàn)數(shù)據(jù)和MATLAB代碼進(jìn)行研究.