秦家鑫，萬(wàn)幼川，王 迪，何培培，陳茂霖

（1.武漢大學(xué) 遙感信息工程學(xué)院，湖北 武漢 430079；2. Politecnico di Milano DIIAR, Como Italy 22100）

基于Otsu的建筑物點(diǎn)云分割改進(jìn)算法

秦家鑫1，萬(wàn)幼川1，王 迪2，何培培1，陳茂霖1

（1.武漢大學(xué) 遙感信息工程學(xué)院，湖北 武漢 430079；2. Politecnico di Milano DIIAR, Como Italy 22100）

提出了一種基于Otsu的建筑物點(diǎn)云分割改進(jìn)算法，針對(duì)傳統(tǒng)Otsu分割算法在精確性方面的不足提出2點(diǎn)修改意見(jiàn)。首先根據(jù)投影點(diǎn)密度理論將三維點(diǎn)云轉(zhuǎn)換為二維灰度圖像，再利用Otsu算法及其改進(jìn)算法對(duì)圖像進(jìn)行分割。采用Riegl公司VZ-400激光掃描儀采集的武漢大學(xué)信息學(xué)部第一教學(xué)樓的點(diǎn)云進(jìn)行分割處理，并與傳統(tǒng)的Otsu分割算法進(jìn)行對(duì)比。結(jié)果表明，該算法分割正確率可達(dá)96．54%，遠(yuǎn)高于改進(jìn)前的72．82%。

點(diǎn)云分割；投影點(diǎn)密度；Otsu；分塊求解；區(qū)域增長(zhǎng)

基于地面LiDAR點(diǎn)云的建筑物重建通常可分為建筑物點(diǎn)云分割和建筑物結(jié)構(gòu)面幾何重建2個(gè)步驟[1]，分割效果的好壞直接影響最終的重建結(jié)果。目前國(guó)內(nèi)外的研究多數(shù)是運(yùn)用機(jī)載LiDAR數(shù)據(jù)[2-4]，運(yùn)用地面LiDAR數(shù)據(jù)的研究還不是很多。史文中等根據(jù)像點(diǎn)空間相位信息，提出了點(diǎn)投影密度的概念[5]，以此將三維點(diǎn)云轉(zhuǎn)換為二維灰度圖像，再通過(guò)灰度圖像的一些分割方法進(jìn)行圖像分割[6]。吳芬芳等利用激光點(diǎn)云的空間分布特征和城市環(huán)境中各種物體自身的幾何特性，將點(diǎn)云投影到水平格網(wǎng)中，根據(jù)格網(wǎng)中數(shù)據(jù)點(diǎn)的高程最大值進(jìn)行分類(lèi)[7]。魏征等根據(jù)點(diǎn)云特征圖像和特征值分析，提出了一種地面LiDAR點(diǎn)云建筑物立面位置邊界的自動(dòng)提取方法[8]。上述3種方法都是將三維點(diǎn)云轉(zhuǎn)化為二維圖像進(jìn)行處理，避免了大量的計(jì)算，且可以充分借鑒圖像處理的一些方法，提高了數(shù)據(jù)處理的效率。黃磊等對(duì)激光掃描儀的回波強(qiáng)度信息進(jìn)行了一系列的處理和改正，通過(guò)建立距離-能量、角度-能量之間的對(duì)應(yīng)關(guān)系，將距離和角度引起的強(qiáng)度變化進(jìn)行歸一化改正和補(bǔ)償，排除距離、角度等因素的干擾，最后利用強(qiáng)度差別對(duì)目標(biāo)進(jìn)行分類(lèi)處理[9]。研究應(yīng)用中地面LiDAR點(diǎn)云分割依然存在著精確性的問(wèn)題?，F(xiàn)階段，基于回波強(qiáng)度信息分類(lèi)研究雖然已取得一定的進(jìn)展，但是由于一些技術(shù)上的原因（如缺乏有效的定標(biāo)手段），利用反射強(qiáng)度值還不能對(duì)目標(biāo)進(jìn)行精確分割，使得其無(wú)法真正得到應(yīng)用。利用二維灰度圖像的一些分割方法，雖然適用于建筑物的分割，但同樣也面臨精確性的問(wèn)題。本文針對(duì)以上問(wèn)題，提出了一些解決方案和方法，對(duì)Otsu算法[10]做了2處改進(jìn)，并對(duì)改進(jìn)前后的分割結(jié)果進(jìn)行了比較分析，提高了點(diǎn)云分割精度。

1 原理與方法

1.1 傳統(tǒng)Otsu算法

地面LiDAR點(diǎn)云隱含分布密度信息，由于每個(gè)掃描物體的結(jié)構(gòu)差異，會(huì)導(dǎo)致不同物體的點(diǎn)云具有不同的密度信息。將掃描區(qū)域的點(diǎn)云進(jìn)行某一方向的投影后，這種隱含的信息就會(huì)顯現(xiàn)出來(lái)，便可利用密度信息分割點(diǎn)云。

將三維坐標(biāo)點(diǎn)垂直投影到水平面上，建立水平格網(wǎng)[11]，根據(jù)掃描區(qū)域范圍，確定每個(gè)格網(wǎng)的大小，統(tǒng)計(jì)每個(gè)格網(wǎng)的投影點(diǎn)個(gè)數(shù)，記為投影點(diǎn)密度（DoPP）。把所有格網(wǎng)的DoPP值線性拉伸到0～255區(qū)間，模擬每個(gè)格網(wǎng)的灰度，即可生成二維灰度圖像，此時(shí)一個(gè)格網(wǎng)即為灰度圖像的一個(gè)像素。不同物體的DoPP值會(huì)表現(xiàn)為不同的特征，根據(jù)不同物體的DoPP特征，設(shè)置相應(yīng)的閾值就可分割出不同的物體。

Otsu根據(jù)圖像的灰度特性，將圖像分成背景和目標(biāo)2部分。背景和目標(biāo)之間的類(lèi)間方差越大，說(shuō)明構(gòu)成圖像的2部分的差別越大、錯(cuò)分概率越小。設(shè)圖像的目標(biāo)和背景的分割閾值為T(mén)，屬于目標(biāo)的像素點(diǎn)個(gè)數(shù)占整幅圖像的比例為ω0，其平均灰度為μ0；屬于背景像素點(diǎn)個(gè)數(shù)占整幅圖像的比例為ω1，其平均灰度為μ1；圖像的總平均灰度為μ，類(lèi)間方差為g：

將式（1）代入式（2），得到：

采用遍歷的方法得到使類(lèi)間方差g最大的灰度閾值T，再遍歷灰度圖像的每個(gè)像素，灰度大于等于T的像素視為目標(biāo)，保留該格網(wǎng)的所有數(shù)據(jù)點(diǎn)；灰度小于T的像素視為背景，濾除該格網(wǎng)的所有數(shù)據(jù)點(diǎn)；最后再把分割后的灰度圖像恢復(fù)為三維點(diǎn)云，得到分割結(jié)果。

1.2 改進(jìn)算法

在實(shí)際應(yīng)用中，建筑物邊界的DoPP值的分布特點(diǎn)一般不會(huì)嚴(yán)格符合“DoPP值遠(yuǎn)大于其他區(qū)域，并形成可連續(xù)的帶”。建筑物的某些部分的點(diǎn)云的DoPP值會(huì)很小，因此利用傳統(tǒng)Otsu算法簡(jiǎn)單地把圖像分為目標(biāo)和背景2類(lèi)很可能會(huì)造成錯(cuò)誤分割，在濾掉除建筑物以外的其他地物數(shù)據(jù)的同時(shí)，也濾掉了一部分建筑物數(shù)據(jù)，導(dǎo)致分割正確率降低。對(duì)此，本文提出了2點(diǎn)修改意見(jiàn)。

1）分塊求解。根據(jù)圖像中建筑物的分布特征，把圖像分成多個(gè)區(qū)域，在每個(gè)區(qū)域中，盡量保證該區(qū)域建筑物點(diǎn)云的DoPP值遠(yuǎn)大于其他地物，目的是減少錯(cuò)誤分割。將圖像I（x×y）在X和Y方向上分別劃分為m和n等份，將圖像分成xi×yj（i=1,2,…,m; j=1,2,…,n）m×n個(gè)區(qū)域，在每個(gè)xi×yj區(qū)域內(nèi)進(jìn)行一次Otsu算法，最后將每個(gè)區(qū)域分割的目標(biāo)部分進(jìn)行拼接，得到最終的分割結(jié)果。

2）區(qū)域增長(zhǎng)補(bǔ)償錯(cuò)分區(qū)域。根據(jù)建筑物的點(diǎn)云分布在垂直投影后是連續(xù)的這一特性，在Otsu分塊求解的分割結(jié)果上，利用區(qū)域增長(zhǎng)算法補(bǔ)償建筑物錯(cuò)分區(qū)域。算法原理如下：

①選取種子點(diǎn)：設(shè)原始點(diǎn)云垂直投影生成灰度圖像的每個(gè)像素灰度為gray[i]，經(jīng)過(guò)Otsu分塊求解算法處理后每個(gè)像素灰度為GRAY[i]，再為每個(gè)像素設(shè)定一個(gè)標(biāo)記數(shù)組。遍歷每個(gè)像素，若此像素GRAY ＞0且其四鄰域（或八鄰域）有任意一個(gè)像素符合GRAY =0且gray＞0，則將此像素標(biāo)記為1，否則標(biāo)記為0。選取標(biāo)記為1的像素作為種子點(diǎn)。

②設(shè)定合適的閾值：將種子點(diǎn)GRAY 值與其四鄰域（或八鄰域）gray值作比較，若其商小于提前給定的閾值，則將鄰域點(diǎn)gray值賦予鄰域點(diǎn)GRAY ，并將鄰域點(diǎn)標(biāo)記為1；若其商大于提前給定的閾值，則將鄰域點(diǎn)標(biāo)記為0。一個(gè)種子點(diǎn)與其所有鄰域點(diǎn)都作完比較后，將種子點(diǎn)標(biāo)記為0。

③進(jìn)行區(qū)域增長(zhǎng)：將標(biāo)記為1的點(diǎn)視為新的種子點(diǎn)，重復(fù)步驟②。

④結(jié)束條件：直到所有點(diǎn)的標(biāo)記均為0，算法結(jié)束。

2 實(shí)驗(yàn)與分析

2.1 實(shí)驗(yàn)流程

本實(shí)驗(yàn)在VC6．0的編程環(huán)境下完成，如圖1所示。

圖1 實(shí)驗(yàn)流程圖

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

本次實(shí)驗(yàn)采用Riegl公司VZ-400激光掃描儀采集的武漢大學(xué)信息學(xué)部第一教學(xué)樓及其周?chē)h(huán)境的點(diǎn)云，原始LiDAR點(diǎn)云和坐標(biāo)軸如圖2所示。

圖2 武漢大學(xué)信息學(xué)部第一教學(xué)樓原始點(diǎn)云圖

原始LiDAR點(diǎn)云共有181 860個(gè)測(cè)量點(diǎn)數(shù)據(jù)，遍歷所有點(diǎn)，得到X方向坐標(biāo)最大值為103．665 m、最小值為39．334 m，Y方向坐標(biāo)最大值為90．328 m、最小值為-83．288 m。結(jié)合點(diǎn)云特點(diǎn)，采用100×100格網(wǎng)對(duì)點(diǎn)云進(jìn)行Z軸投影。如圖2所示，X方向?yàn)榻ㄖ锪⒚婧穸确较?，Y方向?yàn)榻ㄖ锪⒚嫜诱狗较?，以厚度方?．643 31 m、延展方向1．736 16 m的格網(wǎng)間隔投影，符合數(shù)據(jù)的實(shí)際情況，相較于樹(shù)木等其他地物的空間分布，基本能夠保證建筑物立面DoPP值遠(yuǎn)大于其他地物，有利于其后的Otsu算法應(yīng)用。垂直投影到水平面上效果如圖3所示，紅色框內(nèi)就是需要分割出的建筑物邊界點(diǎn)云，投影后線性拉伸生成的二維灰度圖像（見(jiàn)圖4）。

對(duì)投影后生成的灰度圖像進(jìn)行傳統(tǒng)的Otsu分割，分割效果如圖5 a、圖5d所示。Otsu分割初步實(shí)現(xiàn)了建筑物點(diǎn)云的分割效果，成功剔除了樹(shù)木等一些不需要的目標(biāo)數(shù)據(jù)，但是也存在一些錯(cuò)誤分割。原因主要有3點(diǎn)：①建筑物的結(jié)構(gòu)特點(diǎn)，使某些凹凸區(qū)域或拐角處的點(diǎn)云個(gè)數(shù)較少；②其他物體的遮擋；③數(shù)據(jù)中同時(shí)包含高層建筑物和低層建筑物，造成低層建筑物的點(diǎn)云個(gè)數(shù)相對(duì)較少。因此，建筑物的凹凸區(qū)域或拐角處、遮擋嚴(yán)重的區(qū)域、低層建筑物區(qū)域的DoPP值可能并不是遠(yuǎn)大于其他區(qū)域，甚至是小于其他區(qū)域的，在分割過(guò)程中被當(dāng)作背景點(diǎn)剔除。在本文實(shí)驗(yàn)中，利用傳統(tǒng)的Otsu算法分割后的錯(cuò)分區(qū)域中包含很多建筑物的特征點(diǎn)，對(duì)后續(xù)的建筑物結(jié)構(gòu)面幾何重建有著一定的影響，因此分割結(jié)果并不十分理想，需要改進(jìn)。

圖3 原始數(shù)據(jù)垂直投影到水平面上效果圖

圖4 灰度圖像

圖5 改進(jìn)前后效果對(duì)比圖

從傳統(tǒng)Otsu算法的分割結(jié)果可以看出，錯(cuò)誤分割區(qū)域呈現(xiàn)條帶狀，集中在某幾段Y區(qū)間內(nèi)，說(shuō)明這幾段Y區(qū)間內(nèi)的建筑物點(diǎn)云的DoPP值在整個(gè)數(shù)據(jù)中過(guò)小，故將Otsu分塊求解的每個(gè)區(qū)域也劃分成條帶狀。取100×2的格網(wǎng)作為每個(gè)求解區(qū)域，即厚度方向100個(gè)像素、延展方向2個(gè)像素，每200個(gè)像素進(jìn)行一次Otsu算法，共將原始影像等分為50個(gè)區(qū)域，效果如圖6所示。Otsu分塊求解的分割效果有了明顯改進(jìn)，基本上完全分割出建筑物點(diǎn)云，但也產(chǎn)生了一定的多余數(shù)據(jù)，如小部分樹(shù)木數(shù)據(jù)。其原因是局部建筑物點(diǎn)云的DoPP值過(guò)小，小于部分樹(shù)木點(diǎn)云的DoPP值，為了把這一部分建筑物點(diǎn)云作為目標(biāo)分割出來(lái)，就不可避免地將部分樹(shù)木點(diǎn)云也劃分為目標(biāo)。由于建筑物的大概坐標(biāo)容易確定，故新增加的噪聲可通過(guò)簡(jiǎn)單的坐標(biāo)法分割去除，分割結(jié)果如圖5 b、圖5e所示。之后，運(yùn)用區(qū)域增長(zhǎng)算法，在Otsu分塊求解的分割結(jié)果基礎(chǔ)上補(bǔ)償錯(cuò)分區(qū)域。經(jīng)過(guò)多次實(shí)驗(yàn)，區(qū)域增長(zhǎng)的閾值設(shè)為3．21時(shí)效果最佳，既保證了建筑物的完整性，又不增加新的噪聲，效果如圖5 c、圖5 f所示。

圖6 Otsu分塊求解效果圖

傳統(tǒng)的Otsu算法分割效果存在一定的錯(cuò)誤分割，如圖5 a中藍(lán)色框內(nèi)所示部分。改進(jìn)后的Otsu算法先利用分塊求解算法較為完整地分割出建筑物點(diǎn)云，補(bǔ)償了兩側(cè)低層建筑物點(diǎn)云和主建筑物中DoPP值較小部分的點(diǎn)云，再利用區(qū)域增長(zhǎng)算法進(jìn)行優(yōu)化，如區(qū)域增長(zhǎng)補(bǔ)償了圖5b中黃色框內(nèi)所示部分點(diǎn)云，最終分割效果有了明顯的提升，基本上全部分割出建筑物點(diǎn)云。

為了定量評(píng)價(jià)本文提出的改進(jìn)算法的分割精度，手動(dòng)提取建筑物立面部分的點(diǎn)云作為參考數(shù)據(jù)。表1為比較結(jié)果，其中A為手動(dòng)分割結(jié)果的點(diǎn)云個(gè)數(shù)；B為運(yùn)用本文算法分割結(jié)果的點(diǎn)云個(gè)數(shù)；A∩B為A與B中共同的點(diǎn)云個(gè)數(shù)，即分割結(jié)果中正確點(diǎn)的個(gè)數(shù)；B/A為在集合B但不在集合A的點(diǎn)云個(gè)數(shù)，即實(shí)驗(yàn)結(jié)果中多余的點(diǎn)云個(gè)數(shù)；A/B為在集合A但不在集合B的點(diǎn)云個(gè)數(shù)，即實(shí)驗(yàn)結(jié)果中遺漏的點(diǎn)云個(gè)數(shù)。由表1可知，改進(jìn)后的Otsu算法分割出的正確點(diǎn)個(gè)數(shù)為94 476，遠(yuǎn)高于傳統(tǒng)的Otsu算法分割出的71 264個(gè)點(diǎn)。改進(jìn)后算法的分割正確率也由改進(jìn)前的72．82%提高到96．54%。雖然結(jié)果中有3 949個(gè)多余點(diǎn)，遺漏了3 390個(gè)點(diǎn)，但是從改進(jìn)后的算法分割效果圖來(lái)看，建筑物的特征點(diǎn)幾乎全部被分割出來(lái)，可滿(mǎn)足后續(xù)的建筑物結(jié)構(gòu)面幾何重建的需要。

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

3 結(jié) 語(yǔ)

目前，地面LiDAR已成為建筑物三維重建的一種重要數(shù)據(jù)源，但地面LiDAR建筑物點(diǎn)云的精確分割還處于研究階段。本文在分析地面LiDAR建筑物點(diǎn)云精確分割現(xiàn)狀的基礎(chǔ)上，針對(duì)傳統(tǒng)Otsu算法分割結(jié)果中的不足，從錯(cuò)誤分割的區(qū)域中尋找分布特點(diǎn)，由此提出了Otsu分塊求解算法，分割效果得到明顯的改進(jìn)；再利用區(qū)域增長(zhǎng)算法對(duì)分割結(jié)果進(jìn)行優(yōu)化，使分割精度進(jìn)一步提高，為后續(xù)的建筑物結(jié)構(gòu)面幾何重建提供了良好的分割結(jié)果。

[1] 楊洋．基于車(chē)載LiDAR數(shù)據(jù)的建筑物立面重建技術(shù)研究[D]．鄭州：信息工程大學(xué),2010

[2] 王繼陽(yáng),文貢堅(jiān),呂金建，等．建筑物三維重建方法綜述[J]．遙感技術(shù)與應(yīng)用,2009,24(6):832-839

[3] 成曉倩,馬洪超,趙紅強(qiáng)，等．一種基于區(qū)域增長(zhǎng)的機(jī)載LiDAR濾波[J]．測(cè)繪科學(xué),2010,35(1):61-63

[4] 熊娜,程新文．LiDAR數(shù)據(jù)特點(diǎn)及其濾波分類(lèi)方法[J]．中國(guó)水運(yùn),2008,8(1):151-154

[5] 史文中,李必軍,李清泉．基于投影點(diǎn)密度的車(chē)載激光掃描距離圖像分割方法[J]．測(cè)繪學(xué)報(bào),2005,34(2):95-100

[6] 賈永紅．?dāng)?shù)字圖像處理[M]．武漢:武漢大學(xué)出版社,2003

[7] 吳芬芳,李清泉,熊卿．基于車(chē)載激光掃描數(shù)據(jù)的目標(biāo)分類(lèi)方法[J]．測(cè)繪科學(xué),2007,32(4):75-77

[8] 魏征,董震,李清泉，等．車(chē)載LiDAR點(diǎn)云中建筑物立面位置邊界的自動(dòng)提取[J]． 武漢大學(xué)學(xué)報(bào)：信息科學(xué)版,2012,37(11):1 311-1 315

[9] 黃磊,盧秀山,梁勇．基于激光掃描回光強(qiáng)度的建筑物立面信息提取與分類(lèi)[J]．武漢大學(xué)學(xué)報(bào)：信息科學(xué)版,2009,34(2):195-198

[10] Otsu N． A Threshold Selection Method from Gray-level Histograms [J]．IEEE Transactions on Systems, Man and Cybernetics, 1979, 9(1):62-66

[11] 盧秀山,黃磊．基于激光掃描數(shù)據(jù)的建筑物信息格網(wǎng)化提取方法[J]．武漢大學(xué)學(xué)報(bào)：信息科學(xué)版,2007,32(10):852-855

P237.3

B

1672-4623（2014）01-0110-04

10.11709/j.issn.1672-4623.2014.01.038

秦家鑫，碩士，研究方向?yàn)榈孛婕す恻c(diǎn)云數(shù)據(jù)處理。

2013-06-20。

項(xiàng)目來(lái)源：國(guó)家科技支撐計(jì)劃項(xiàng)目（2012BAH34B02、2012BAJ15B04）。