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

王秋燕，陳犀力

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

1 引言

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

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

2 Alpha Shapes算法

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

圖2 Alpha Shapes算法模型

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

3 Alpha Shapes算法的適用性研究

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

4 改進(jìn)的Alpha Shapes算法提取建筑物輪廓線

圖3 Alpha值的大小與邊緣精細(xì)程度的關(guān)系

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

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

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

5 結(jié)語(yǔ)

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

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