基于Otsu的建筑物點云分割改進算法

秦家鑫，萬幼川，王 迪，何培培，陳茂霖

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

基于Otsu的建筑物點云分割改進算法

秦家鑫1，萬幼川1，王 迪2，何培培1，陳茂霖1

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

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

點云分割；投影點密度；Otsu；分塊求解；區域增長

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

1 原理與方法

1.1 傳統Otsu算法

地面LiDAR點云隱含分布密度信息，由于每個掃描物體的結構差異，會導致不同物體的點云具有不同的密度信息。將掃描區域的點云進行某一方向的投影后，這種隱含的信息就會顯現出來，便可利用密度信息分割點云。

將三維坐標點垂直投影到水平面上，建立水平格網[11]，根據掃描區域范圍，確定每個格網的大小，統計每個格網的投影點個數，記為投影點密度（DoPP）。把所有格網的DoPP值線性拉伸到0～255區間，模擬每個格網的灰度，即可生成二維灰度圖像，此時一個格網即為灰度圖像的一個像素。不同物體的DoPP值會表現為不同的特征，根據不同物體的DoPP特征，設置相應的閾值就可分割出不同的物體。

Otsu根據圖像的灰度特性，將圖像分成背景和目標2部分。背景和目標之間的類間方差越大，說明構成圖像的2部分的差別越大、錯分概率越小。設圖像的目標和背景的分割閾值為T，屬于目標的像素點個數占整幅圖像的比例為ω0，其平均灰度為μ0；屬于背景像素點個數占整幅圖像的比例為ω1，其平均灰度為μ1；圖像的總平均灰度為μ，類間方差為g：

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

采用遍歷的方法得到使類間方差g最大的灰度閾值T，再遍歷灰度圖像的每個像素，灰度大于等于T的像素視為目標，保留該格網的所有數據點；灰度小于T的像素視為背景，濾除該格網的所有數據點；最后再把分割后的灰度圖像恢復為三維點云，得到分割結果。

1.2 改進算法

在實際應用中，建筑物邊界的DoPP值的分布特點一般不會嚴格符合“DoPP值遠大于其他區域，并形成可連續的帶”。建筑物的某些部分的點云的DoPP值會很小，因此利用傳統Otsu算法簡單地把圖像分為目標和背景2類很可能會造成錯誤分割，在濾掉除建筑物以外的其他地物數據的同時，也濾掉了一部分建筑物數據，導致分割正確率降低。對此，本文提出了2點修改意見。

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

2）區域增長補償錯分區域。根據建筑物的點云分布在垂直投影后是連續的這一特性，在Otsu分塊求解的分割結果上，利用區域增長算法補償建筑物錯分區域。算法原理如下：

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

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

③進行區域增長：將標記為1的點視為新的種子點，重復步驟②。

④結束條件：直到所有點的標記均為0，算法結束。

2 實驗與分析

2.1 實驗流程

本實驗在VC6．0的編程環境下完成，如圖1所示。

圖1 實驗流程圖

2.2 實驗結果及分析

本次實驗采用Riegl公司VZ-400激光掃描儀采集的武漢大學信息學部第一教學樓及其周圍環境的點云，原始LiDAR點云和坐標軸如圖2所示。

圖2 武漢大學信息學部第一教學樓原始點云圖

原始LiDAR點云共有181 860個測量點數據，遍歷所有點，得到X方向坐標最大值為103．665 m、最小值為39．334 m，Y方向坐標最大值為90．328 m、最小值為-83．288 m。結合點云特點，采用100×100格網對點云進行Z軸投影。如圖2所示，X方向為建筑物立面厚度方向，Y方向為建筑物立面延展方向，以厚度方向0．643 31 m、延展方向1．736 16 m的格網間隔投影，符合數據的實際情況，相較于樹木等其他地物的空間分布，基本能夠保證建筑物立面DoPP值遠大于其他地物，有利于其后的Otsu算法應用。垂直投影到水平面上效果如圖3所示，紅色框內就是需要分割出的建筑物邊界點云，投影后線性拉伸生成的二維灰度圖像（見圖4）。

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

圖3 原始數據垂直投影到水平面上效果圖

圖4 灰度圖像

圖5 改進前后效果對比圖

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

圖6 Otsu分塊求解效果圖

傳統的Otsu算法分割效果存在一定的錯誤分割，如圖5 a中藍色框內所示部分。改進后的Otsu算法先利用分塊求解算法較為完整地分割出建筑物點云，補償了兩側低層建筑物點云和主建筑物中DoPP值較小部分的點云，再利用區域增長算法進行優化，如區域增長補償了圖5b中黃色框內所示部分點云，最終分割效果有了明顯的提升，基本上全部分割出建筑物點云。

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

表1 分割結果統計/個

3 結 語

目前，地面LiDAR已成為建筑物三維重建的一種重要數據源，但地面LiDAR建筑物點云的精確分割還處于研究階段。本文在分析地面LiDAR建筑物點云精確分割現狀的基礎上，針對傳統Otsu算法分割結果中的不足，從錯誤分割的區域中尋找分布特點，由此提出了Otsu分塊求解算法，分割效果得到明顯的改進；再利用區域增長算法對分割結果進行優化，使分割精度進一步提高，為后續的建筑物結構面幾何重建提供了良好的分割結果。

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

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

[3] 成曉倩,馬洪超,趙紅強，等．一種基于區域增長的機載LiDAR濾波[J]．測繪科學,2010,35(1):61-63

[4] 熊娜,程新文．LiDAR數據特點及其濾波分類方法[J]．中國水運,2008,8(1):151-154

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

[6] 賈永紅．數字圖像處理[M]．武漢:武漢大學出版社,2003

[7] 吳芬芳,李清泉,熊卿．基于車載激光掃描數據的目標分類方法[J]．測繪科學,2007,32(4):75-77

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

[9] 黃磊,盧秀山,梁勇．基于激光掃描回光強度的建筑物立面信息提取與分類[J]．武漢大學學報：信息科學版,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] 盧秀山,黃磊．基于激光掃描數據的建筑物信息格網化提取方法[J]．武漢大學學報：信息科學版,2007,32(10):852-855

P237.3

B

1672-4623（2014）01-0110-04

10.11709/j.issn.1672-4623.2014.01.038

秦家鑫，碩士，研究方向為地面激光點云數據處理。

2013-06-20。

項目來源：國家科技支撐計劃項目（2012BAH34B02、2012BAJ15B04）。