基于Alpha Shapes算法的LIDAR數(shù)據(jù)建筑物輪廓線提取

王秋燕，陳犀力

（1.江蘇聯(lián)合職業(yè)技術學院南京分院；2.南京地鐵運營有限責任公司）

1 引言

目前，較普遍的建筑物輪廓線提取方法，一般是采用插值算法，將三維點云的高程值賦給圖像灰度值，進一步處理得到規(guī)則化的nDSM，最后圖像分割，邊緣檢測或結(jié)合高分辨率影像進行建筑物輪廓線的提取[1～3]，如圖1所示。對LIDAR點云插值生成深度影像，如圖1a所示，然后使用具有代表性的圖像邊緣檢測算子，如Canny算子、Sobel算子和Prewitt算子進行檢測的結(jié)果分別如圖1b，1c，1d所示。從實驗結(jié)果分析，檢測的邊緣線會出現(xiàn)斷裂、雜亂及不規(guī)則等問題，這些問題會對后期輪廓線的簡化和規(guī)則化帶來困難，如何連接斷裂的邊緣線以及如何判斷并去除多余的非邊界線等都是急需解決的難題。

圖1 圖像邊緣檢測算法輪廓線提取結(jié)果

2 Alpha Shapes算法

Alpha Shapes算法可從一堆離散的點集中進行幾何形狀的重建，如圖2所示。最早是由H.Edelsbrunner，D.G.Kirckpatrick and R.Seidel[4]在1983年發(fā)表的文章《平面點集的形狀》中正式提出。用一個半徑為a的圓在點集周圍滾動，當遍歷所有的點之后，最終可以得出點集的內(nèi)外輪廓線。當圓的半徑 a較大時，圓在點集S的外部滾動，外部滾動的痕跡就是點集的邊界輪廓線。當半徑a值較小時，圓就滾動到點集S內(nèi)部去，當a值足夠小時，點集中的每個點都是邊界點。圓半徑a的取值與檢測出來的建筑物輪廓線精細程度密切相關，如圖3所示，半徑相對較小時，檢測出來的輪廓線較精細，半徑相對較大時，檢測出來的輪廓線略微粗糙。

圖2 Alpha Shapes算法模型

針對離散的三維點云進行建筑物輪廓線提取及輪廓線的規(guī)則化研究，將Alpha Shapes算法[5]運用到本文的研究中，避免了插值算法帶來的誤差，解決邊緣檢測算法提取的輪廓線存在斷裂，雜亂等問題。

3 Alpha Shapes算法的適用性研究

Alpha Shapes算法的適用范圍較廣，對于矩形、正方形、T形、工字型、環(huán)形、三角形、圓形和不規(guī)則凹凸多邊形等都具有很好的適用性，其算法穩(wěn)健性強，運算速度快。本文對Alpha Shapes算法的適用性進行了實驗研究，其實驗結(jié)果如圖4所示。

4 改進的Alpha Shapes算法提取建筑物輪廓線

圖3 Alpha值的大小與邊緣精細程度的關系

本文針對城區(qū)較平坦地區(qū)的建筑物進行實驗，利用改進的Alpha Shapes算法對機載LIDAR建筑物的輪廓線進行了提取，改進的Alpha Shapes算法對機載LIDAR點云數(shù)據(jù)先構建Delaunay三角網(wǎng)，再對構建的Delaunay三角網(wǎng)進行判斷，從而快速有效地提取建筑物輪廓線。

改進的Alpha Shapes算法對實驗數(shù)據(jù)一機載LIDAR點云數(shù)據(jù)構造的Delaunay三角網(wǎng)如圖5所示，用Alpha Shapes算法提取的建筑物輪廓線如圖6所示。圖6c是算法提取的較為精細的建筑物輪廓線。此實驗驗證了改進的Alpha Shapes算法能夠快速準確地將建筑物輪廓線提取出來。

圖5 實驗數(shù)據(jù)一 Delaunay三角網(wǎng)的生成

5 結(jié)語

綜上所述，Alpha Shapes算法的適用范圍較廣，該算法提取的建筑物輪廓線都是閉合的曲線，不需要進行斷裂線段的連接，算法不需要進行插值，避免了插值帶來的誤差，且在一定程度上解決了圖像處理方法提取邊緣線存在斷裂、雜亂的問題。本文對Alpha Shapes算法進行了一定的改進，在進行建筑物的輪廓線提取前，先對LIDAR點云構造Delaunay三角網(wǎng)，再進行建筑物輪廓線的提取，提高了Alpha Shapes算法的運行效率。由此可知，Alpha Shapes算法較適用于離散點云的建筑物內(nèi)外輪廓線提取，且該算法提取的建筑物輪廓線為后續(xù)輪廓線的簡化和規(guī)則化研究做好了充分的數(shù)據(jù)準備。

圖6 實驗數(shù)據(jù)一 Alpha Shapes算法建筑物輪廓線提取