基于alpha shapes 算法的相鄰航帶點(diǎn)云重疊區(qū)提取

張 凡，奚冰柔，申 鍵，池典賜

（廣東省海洋發(fā)展規(guī)劃研究中心，廣東 廣州）

引言

機(jī)載激光lidar（Light Detection And Ranging）測(cè)量屬于條帶式測(cè)量的一種，具有空中作業(yè)覆蓋面廣、高精度、高密度、高效率、產(chǎn)品豐富等特點(diǎn)。由于掃描角和航高的限制，不能一次性完成整個(gè)測(cè)區(qū)的數(shù)據(jù)采集工作，因此為實(shí)現(xiàn)作業(yè)區(qū)全覆蓋測(cè)量，必須規(guī)劃多條飛行航線，航帶規(guī)劃布設(shè)需保證相鄰航線間保持20%以上重疊度[1-2]。但系統(tǒng)誤差以及測(cè)量隨機(jī)誤差的共同影響，造成相鄰航帶間同名特征存在三維空間偏移，對(duì)后續(xù)獲取高精度地形數(shù)據(jù)產(chǎn)生明顯影響，為了提高點(diǎn)云數(shù)據(jù)質(zhì)量，有必要消除或減少航帶區(qū)域間的差異。因此要得到完整、精確的點(diǎn)云就需要進(jìn)行點(diǎn)云配準(zhǔn)，確定一個(gè)合適的坐標(biāo)變換矩陣，將不同航帶的點(diǎn)云數(shù)據(jù)集中到統(tǒng)一的坐標(biāo)系之下，消除相鄰航帶點(diǎn)云之間的空間偏差。而相鄰航帶間重疊區(qū)同名特征信息較為豐富，能夠獲得相似特征間的一致性對(duì)應(yīng)關(guān)系，經(jīng)過(guò)旋轉(zhuǎn)、平移將不同坐標(biāo)系下的三維數(shù)據(jù)集轉(zhuǎn)換到統(tǒng)一坐標(biāo)系下，有效的消除物體在掃描過(guò)程中產(chǎn)生的空間偏差，提升點(diǎn)云數(shù)據(jù)質(zhì)量，為后續(xù)生成無(wú)縫產(chǎn)品。因此重疊區(qū)提取對(duì)于尋求相鄰數(shù)據(jù)集間重疊區(qū)同名相似特征具有重要作用。

本文根據(jù)點(diǎn)云輪廓線交集原理實(shí)現(xiàn)相鄰航帶充重疊區(qū)提取。首先利用alphashapes 算法完成條帶點(diǎn)云的輪廓邊界提取，通過(guò)設(shè)置alpha 圓半徑參數(shù)，計(jì)算點(diǎn)點(diǎn)之間的距離公式進(jìn)行存儲(chǔ)，然后通過(guò)引入K-D 樹(shù)（K-Dimension tree）結(jié)構(gòu)快速搜索的優(yōu)勢(shì)，加快alpha shapes算法中圓心坐標(biāo)計(jì)算和輪廓線判斷的速率，設(shè)置搜索半徑并判斷點(diǎn)云數(shù)量是否滿足閾值要求，最后根據(jù)PCL（Point cloud Libarary）構(gòu)建多邊形濾波器，分別對(duì)相鄰航帶進(jìn)行濾波，最終完成相鄰航帶重疊區(qū)的提取工作。實(shí)驗(yàn)證明該方法可以完整有效的提取相鄰航帶間重疊區(qū)域，為后續(xù)的點(diǎn)云配準(zhǔn)工作奠定數(shù)據(jù)基礎(chǔ)。

1 alpha shapes 算法原理

alpha shapes 算法是由Edelsbrunner 等[3]提出的一種可以從離散的空間點(diǎn)集中抽象出其直觀形狀的方法，如圖1，該方法主要適用于多種形狀的點(diǎn)云輪廓邊界提取，例如可有效地用于提取多種類(lèi)型建筑物點(diǎn)云邊界[4-6]，同時(shí)王林振[7]將二維alpha shapes 輪廓提取算法提升至三維空間中，通過(guò)地物邊界所包含的三維坐標(biāo)信息，將其劃分水下點(diǎn)云類(lèi)別，實(shí)現(xiàn)水深點(diǎn)云濾波。

圖1 alpha shapes 提取邊界示意圖

綜上所述，alpha shapes 算法主要適用于點(diǎn)密度較為均勻的數(shù)據(jù)集[8]?；驹頌槿粼擖c(diǎn)集有n 個(gè)點(diǎn)構(gòu)成，可以組成n(n-1)條線段，可以在點(diǎn)集A 中，過(guò)任意兩點(diǎn)P,Q繪制半徑為alpha 的圓，其中給定半徑能夠確定兩點(diǎn)的圓會(huì)有兩個(gè)，且圓心O 是關(guān)于弦中心對(duì)稱(chēng)，如果這個(gè)圓內(nèi)沒(méi)有其它的點(diǎn)存在，則認(rèn)為P,Q 為邊界點(diǎn)，其連線PQ為邊界線段。本文alpha shapes 具體算法流程如下：

步驟1：設(shè)定alpha shapes 算法中alpha 圓半徑參數(shù)，遍歷計(jì)算點(diǎn)云數(shù)據(jù)集中每一條線段PQ；

步驟2：如果PQ 線段的長(zhǎng)度大于直徑，則認(rèn)為超出搜索范圍，無(wú)法找到經(jīng)過(guò)這兩個(gè)點(diǎn)的圓；

步驟3：依據(jù)圖2 幾何計(jì)算關(guān)系，分別求出兩個(gè)圓的圓心O1、O2；

圖2 alpha shapes 算法幾何關(guān)系

步驟4：計(jì)算出PQ 的方向向量V，求解PQ 的中點(diǎn)坐標(biāo)M，并計(jì)算V 的垂直向量H；

步驟5：計(jì)算PQ 弦長(zhǎng)L，根據(jù)圓心坐標(biāo)O=M±D*H公式，解算圓心O 到弦長(zhǎng)的距離D；

步驟6：若兩個(gè)圓中存在任一個(gè)圓內(nèi)部不包含點(diǎn)集A 中的點(diǎn)，則認(rèn)為P,Q 為邊界點(diǎn)；

步驟7：最終獲得點(diǎn)云輪廓邊界。

該算法中在初始計(jì)算過(guò)程中，需要遍歷計(jì)算數(shù)據(jù)集中每一個(gè)點(diǎn)到所有點(diǎn)的之間的線段距離，當(dāng)數(shù)據(jù)量龐大時(shí)，程序中的兩次循環(huán)會(huì)消耗很多的時(shí)間，導(dǎo)致算法的計(jì)算效率下降。KD 樹(shù)結(jié)構(gòu)是一種對(duì)k 維空間中數(shù)據(jù)點(diǎn)進(jìn)行存儲(chǔ)以便對(duì)其進(jìn)行快速檢索的樹(shù)形數(shù)據(jù)結(jié)構(gòu)，主要應(yīng)用加速多維空間關(guān)鍵數(shù)據(jù)的搜索，因此利用K-D 樹(shù)結(jié)構(gòu)加快算法的時(shí)間效率問(wèn)題，流程如圖3 所示。

圖3 本文alpha shapes 算法中流程圖

2 航帶重疊區(qū)提取

為了提高計(jì)算機(jī)的運(yùn)行效率，減少算法的迭代量，目前大部分點(diǎn)云配準(zhǔn)算法研究重點(diǎn)是針對(duì)相鄰航帶的重疊區(qū)域進(jìn)行處理，計(jì)算變換矩陣。例如Behan[9]提出的在重疊區(qū)布設(shè)控制網(wǎng)，進(jìn)行地面控制點(diǎn)和機(jī)載航帶點(diǎn)云間的聯(lián)合平差，解算變換參數(shù)；Burman[10]在相鄰航帶重疊區(qū)域利用點(diǎn)云高程、強(qiáng)度信息生成柵格影像進(jìn)行航帶平差；李天爍等[11]根據(jù)兩站（多站）點(diǎn)云重疊區(qū)局部點(diǎn)云的強(qiáng)度信息，生成柵格數(shù)據(jù)輔助完成點(diǎn)云配準(zhǔn)工作。

本文根據(jù)機(jī)載航帶布設(shè)條件，認(rèn)為相鄰航帶點(diǎn)云數(shù)據(jù)必有交叉重疊的特性，符合情況如圖4，在滿足規(guī)范要求情況下，點(diǎn)云數(shù)據(jù)集A 的部分邊界必會(huì)包圍點(diǎn)云數(shù)據(jù)集B 的部分區(qū)域，兩者的邊界交叉的區(qū)域C 則被認(rèn)為是點(diǎn)云的重疊區(qū)域。點(diǎn)云輪廓線提取完成后，可以通過(guò)PCL 中的hull.reconstruct(*多邊形，邊界點(diǎn))重建封閉多邊形，最后利用CropHull 濾波器進(jìn)行多邊形濾波，該模塊可通過(guò)設(shè)置參數(shù)提取封閉多邊形內(nèi)部點(diǎn)或者外部點(diǎn)。

圖4 交叉重疊示意圖

3 試驗(yàn)結(jié)果與分析

3.1 alpha shapes 算法提取邊界

本文中涉及算法是利用VS2022、PCL 配置環(huán)境在windows 平臺(tái)下編寫(xiě)實(shí)現(xiàn)，為進(jìn)一步驗(yàn)證alpha shapes算法提取相鄰航帶點(diǎn)云重疊區(qū)的有效性，首先通過(guò)4 組不同形狀的簡(jiǎn)易點(diǎn)云進(jìn)行試驗(yàn)，試驗(yàn)結(jié)果發(fā)現(xiàn)alpha shapes 算法中alpha 圓半徑設(shè)置越小，在點(diǎn)云內(nèi)部中凹區(qū)域提取輪廓線就會(huì)越細(xì)致，表現(xiàn)出的點(diǎn)云邊界點(diǎn)的連續(xù)性越強(qiáng)，試驗(yàn)結(jié)果如圖5 所示，其中白色代表提取的點(diǎn)云輪廓邊界，結(jié)果表明，該算法能夠有效的對(duì)點(diǎn)云數(shù)據(jù)的邊界做出判斷，準(zhǔn)確的提取點(diǎn)云輪廓，同時(shí)也說(shuō)明該算法在本次試驗(yàn)的4 組樣本中對(duì)于簡(jiǎn)易形狀的點(diǎn)云邊界提取具有可靠性。

圖5 4 組不同形狀點(diǎn)云邊界提取結(jié)果

然而在實(shí)際測(cè)量過(guò)程當(dāng)中，存在航線布設(shè)覆蓋范圍中存在地物的不規(guī)則性，且設(shè)備傳感器性能的影響，導(dǎo)致所掃描的lidar 點(diǎn)云數(shù)據(jù)存在理想狀況不一致，例如由于道路、橋梁或建筑物存在大量的平面結(jié)構(gòu)，激光反射信號(hào)強(qiáng)，點(diǎn)云數(shù)據(jù)密度高，且整體結(jié)構(gòu)表現(xiàn)出明顯的規(guī)則邊界，而對(duì)于植被類(lèi)數(shù)據(jù)，由于激光信號(hào)的穿透性、反射性與樹(shù)木枝干、葉片的密集程度相關(guān)，整體呈現(xiàn)的數(shù)據(jù)較為離散。因此為驗(yàn)證在實(shí)際測(cè)量過(guò)程中，該算法在提取更加復(fù)雜且不規(guī)則點(diǎn)云邊界的有效性，本文采用兩組不同區(qū)域的機(jī)載激光lidar 相鄰航帶間數(shù)據(jù)進(jìn)行點(diǎn)云輪廓邊界提取試驗(yàn)，試驗(yàn)數(shù)據(jù)信息如表1 所示。

表1 試驗(yàn)數(shù)據(jù)信息

該數(shù)據(jù)集的獲取環(huán)境受機(jī)載lidar 掃描數(shù)據(jù)特性影響，背向掃描物體一側(cè)由于遮擋激光信號(hào)，導(dǎo)致無(wú)法穿透物體表面，出現(xiàn)數(shù)據(jù)缺失，無(wú)反射信息，造成數(shù)據(jù)不完整，而且邊緣數(shù)據(jù)受傳感器設(shè)備和探測(cè)環(huán)境的影響，邊緣部分呈現(xiàn)數(shù)據(jù)密度稀少、不規(guī)則的特征，數(shù)據(jù)空洞部分較多。根據(jù)上訴簡(jiǎn)易點(diǎn)云試驗(yàn)過(guò)程總結(jié)，在對(duì)5 條航帶點(diǎn)云數(shù)據(jù)邊界提取過(guò)程中，設(shè)定的K-D 樹(shù)搜索半徑參數(shù)R 為5.0，alpha 圓半徑參數(shù)為2.0，最終兩組試驗(yàn)點(diǎn)云輪廓線提取結(jié)果如圖6、7 所示。試驗(yàn)結(jié)果中，白色代表提取的的點(diǎn)云輪廓邊界，可以發(fā)現(xiàn)在5 條航線數(shù)據(jù)邊緣規(guī)則區(qū)域，alpha shapes 算法提取的點(diǎn)云邊界符合邊界的走向，也呈現(xiàn)出邊界頂點(diǎn)較為連續(xù)，而且對(duì)于數(shù)據(jù)中存在的空洞部分，通過(guò)該算法設(shè)置的參數(shù)也能準(zhǔn)確的進(jìn)行識(shí)別并能夠提取數(shù)據(jù)內(nèi)邊緣的輪廓邊界，同時(shí)在數(shù)據(jù)邊緣呈現(xiàn)數(shù)據(jù)稀少的區(qū)域，雖然提取的邊界點(diǎn)比較密集，但更加說(shuō)明該算法對(duì)于數(shù)據(jù)邊緣離散出表現(xiàn)的更加敏感，即使存在較小的空洞區(qū)域，通過(guò)調(diào)整設(shè)置的alpha 圓半徑參數(shù)，該算法也可以有效提取，也進(jìn)一步證明了該算法在整體提取點(diǎn)云輪廓邊界方面具有可靠性和魯棒性。

圖6 航帶邊界提取結(jié)果

圖7 航帶邊界提取結(jié)果

3.2 航帶重疊區(qū)域提取

根據(jù)點(diǎn)云輪廓線提取結(jié)果，利用PCL 中封裝后的CropHull 模塊進(jìn)行多邊形濾波，提取多邊形內(nèi)部的點(diǎn)云，例如，利用航帶1 點(diǎn)云輪廓作為邊界矢量提取航帶2數(shù)據(jù)，得到航帶1 和航帶2 中航帶2 的重疊區(qū)域，同理提取航帶1 重疊區(qū)域，最后濾波得到的兩組不同區(qū)域相鄰航帶間重疊區(qū)結(jié)果如圖8，圖中白色區(qū)域?yàn)樘崛〉闹丿B區(qū)結(jié)果，結(jié)果表明利用alpha shapes 算法提取的重疊區(qū)結(jié)果符合實(shí)際測(cè)量工作中相鄰航帶間的重疊特征，可以有效的為后續(xù)點(diǎn)云數(shù)據(jù)處理和特征分析提供數(shù)據(jù)基礎(chǔ)。

圖8 相鄰航帶重疊區(qū)

上述重疊區(qū)域提取結(jié)果中并不會(huì)存在重復(fù)的點(diǎn)，免去了刪除重復(fù)值索引，即使提取邊界的時(shí)候會(huì)有重復(fù)值的記錄，但最后濾波構(gòu)建多邊形時(shí)也并不影響濾波的結(jié)果，該方法在距離之上沒(méi)有下功夫，只是單純?cè)O(shè)定K-D樹(shù)半徑域值以及查找圓的半徑（圓的直徑K-D 樹(shù)的鄰域半徑），通過(guò)提取的效果來(lái)確定是否保留結(jié)果。

4 結(jié)論

本文針對(duì)相鄰航帶重疊區(qū)提取，通過(guò)alpha shapes算法遍歷檢測(cè)點(diǎn)云輪廓，為加快算法點(diǎn)云輪廓線目標(biāo)查找和數(shù)值計(jì)算效率檢測(cè)效率，引入K-D 樹(shù)結(jié)構(gòu)計(jì)算原始點(diǎn)云中所有鄰域點(diǎn)的圓心坐標(biāo)，并經(jīng)過(guò)兩組樣本實(shí)驗(yàn)，證明了該方法在實(shí)現(xiàn)點(diǎn)云輪廓線提取的有效性，最后根據(jù)相鄰航帶點(diǎn)云輪廓線創(chuàng)建多邊形，利用PCL 中的多邊形濾波器分別提取相鄰航帶交集處重疊區(qū)域。根據(jù)數(shù)據(jù)處理結(jié)果來(lái)看，提取的相鄰航帶重疊區(qū)符合實(shí)際地區(qū)的重疊區(qū)形狀，而且對(duì)于重疊區(qū)的地勢(shì)特征并沒(méi)有帶來(lái)?yè)p失，為航帶配準(zhǔn)奠定了數(shù)據(jù)基礎(chǔ)。