基于幾何特征的點(diǎn)云分割算法研究進(jìn)展

鞏育江，龐亞軍*，王 汞，白振旭

(1.河北工業(yè)大學(xué) 電子信息工程學(xué)院 先進(jìn)激光技術(shù)研究中心，天津 300401；2.河北工業(yè)大學(xué) 河北省先進(jìn)激光技術(shù)與裝備重點(diǎn)實(shí)驗(yàn)室，天津 300401)

引 言

3維圖像是一種特殊的信息表達(dá)形式，包含了所觀測(cè)場(chǎng)景的完整幾何信息。相較于平面2維圖像，深度信息的獲取使得3維圖像可以輕易地實(shí)現(xiàn)不同距離場(chǎng)景的分離，并對(duì)不同測(cè)量設(shè)備和不同視角保持良好的統(tǒng)一性。近些年來，隨著3維成像技術(shù)的快速發(fā)展，出現(xiàn)了越來越多高精度、低成本的3維圖像傳感器，如激光雷達(dá)(light detection and ranging,LiDAR)[1]、深度相機(jī)[2]等，大幅降低了3維信息獲取的難度與成本。作為一種特殊格式的3維數(shù)據(jù)，點(diǎn)云[3]已經(jīng)成為當(dāng)前3維圖像的主要信息表達(dá)方式。相較于其它的3維數(shù)據(jù)格式，點(diǎn)云數(shù)據(jù)無需存儲(chǔ)各離散點(diǎn)之間的拓?fù)浣Y(jié)構(gòu)，有著更為簡(jiǎn)單、靈活和強(qiáng)大的表示能力，在處理時(shí)可以表現(xiàn)出更好的性能。因此，點(diǎn)云成為了機(jī)器視覺、遙感測(cè)繪等領(lǐng)域的首選數(shù)據(jù)格式，在目標(biāo)識(shí)別[4]、模型構(gòu)建[5]等場(chǎng)景中得到了廣泛的應(yīng)用。

點(diǎn)云分割是點(diǎn)云數(shù)據(jù)處理過程中的重要步驟，其目的在于將初始點(diǎn)云劃分成若干具有相似屬性的子集[6]，為后續(xù)進(jìn)一步應(yīng)用做準(zhǔn)備。由傳感器所獲得的原始點(diǎn)云數(shù)據(jù)往往較為復(fù)雜，包含著大量冗余信息，難以直接獲取所需信息,故需要先對(duì)初始點(diǎn)云進(jìn)行分割，再從中分離出感興趣的部分。在點(diǎn)云處理過程中，點(diǎn)云分割的結(jié)果將作為后續(xù)步驟的輸入數(shù)據(jù)，對(duì)算法的運(yùn)行結(jié)果產(chǎn)生直接影響，因此，點(diǎn)云分割算法一直受到3維信息處理領(lǐng)域的廣泛關(guān)注。近年來，深度學(xué)習(xí)給點(diǎn)云數(shù)據(jù)處理提供了新的思路[7]，但相關(guān)算法結(jié)構(gòu)復(fù)雜、運(yùn)行速度慢、結(jié)果穩(wěn)定性差，距離廣泛的實(shí)際應(yīng)用還有一定距離。與之相比，基于3維圖像幾何特征的點(diǎn)云分割算法結(jié)構(gòu)更加簡(jiǎn)潔、響應(yīng)速度快、結(jié)果穩(wěn)定性好，并且易于針對(duì)不同場(chǎng)景進(jìn)行快速調(diào)整，在實(shí)際應(yīng)用中仍占有主要地位。

盡管基本理論框架已經(jīng)基本完善，但隨著硬件設(shè)備的不斷更新，3維圖像特征的獲取方式更加多樣化，許多優(yōu)秀的分割算法仍舊不斷涌現(xiàn)。本文中對(duì)近年來出現(xiàn)的點(diǎn)云分割算法進(jìn)行了梳理，并依照其所應(yīng)用的特征進(jìn)行了分類，分析了其優(yōu)缺點(diǎn)。期望為相關(guān)研究和應(yīng)用提供一定參考。

1 點(diǎn)云分割的數(shù)學(xué)定義

2 基于邊緣檢測(cè)的分割方法

邊緣描述了物體的形狀特征，在圖像中常常表現(xiàn)為方向不連續(xù)、或者某屬性發(fā)生突變的點(diǎn)。根據(jù)RABBANI等人[8]的定義，此類分割算法主要分為兩步：(1)邊緣的檢測(cè)與提?。?2)對(duì)邊緣內(nèi)的點(diǎn)云進(jìn)行聚類。邊緣檢測(cè)算法大體上可分為直接檢測(cè)與間接檢測(cè)兩類[9]：直接檢測(cè)即利用邊緣的特殊性質(zhì)對(duì)其進(jìn)行檢測(cè)，間接檢測(cè)則通過將3維點(diǎn)云與2維圖像建立對(duì)應(yīng)關(guān)系來進(jìn)行，通過對(duì)2維圖像進(jìn)行邊緣檢測(cè)將所得邊緣投影至3維點(diǎn)云。由于3維點(diǎn)云轉(zhuǎn)換到2維圖像的過程中有可能會(huì)丟失部分特征，在實(shí)踐中有諸多困難難以克服，應(yīng)用較少，本文中只對(duì)直接檢測(cè)方法進(jìn)行討論。

2017年，美國俄勒岡州立大學(xué)的CHE等人[10-11]提出了法向量變化分析(normal variation analysis，NORVANA)算法。該算法利用地面激光掃描(terrestrial laser scan，TLS)的網(wǎng)格掃描模式構(gòu)建局部三角網(wǎng)絡(luò)，并由每條共享邊的法向梯度確定共享邊是否位于邊緣上。2019年，CHE等人將NORVANA算法拓展至車載激光雷達(dá)點(diǎn)云數(shù)據(jù)(mobile laser scan，MLS)處理中，稱作Mo-NORVANA[12]，其流程圖如圖1所示。車載激光雷達(dá)點(diǎn)云無法利用網(wǎng)格模式確定近鄰，故基于車載激光雷達(dá)點(diǎn)云由線性掃描所得這一事實(shí)，選取相鄰兩條掃描線上的點(diǎn)作為最近鄰以構(gòu)建網(wǎng)格，分析其法向差異，并應(yīng)用NORVANA算法實(shí)現(xiàn)邊緣檢測(cè)。

圖1 Mo-NORVAMNA算法流程圖[12]

2018年，英國斯特拉斯克萊德大學(xué)的SUMMAN等人提出了利用鄰域點(diǎn)特征來提取邊界點(diǎn)的方法[13],該算法依據(jù)鄰域點(diǎn)的分布將點(diǎn)云劃分為內(nèi)點(diǎn)、凸面邊界點(diǎn)和凹面邊界點(diǎn)3類，并利用“3點(diǎn)定圓”的思想來標(biāo)記邊緣點(diǎn)，其示意圖如圖2所示。其中點(diǎn)C為內(nèi)點(diǎn)，點(diǎn)A和點(diǎn)B為凹面邊界點(diǎn)，點(diǎn)D和點(diǎn)E為凸面邊界點(diǎn)。對(duì)于未分類的點(diǎn)，步驟一：計(jì)算該點(diǎn)及任意兩個(gè)鄰域點(diǎn)所確定的所有圓的半徑;若有任意一個(gè)圓的半徑大于其局部分辨率，且所求圓的對(duì)應(yīng)球體中不包含任一其它點(diǎn)，則此點(diǎn)標(biāo)記為邊界點(diǎn)；否則進(jìn)行步驟二：將點(diǎn)P及其鄰域投影至最佳擬合平面上，并以P為原點(diǎn)建立極坐標(biāo)系，嘗試建立一個(gè)可以包圍原點(diǎn)并通過所有鄰域點(diǎn)的路徑，若此路徑不存在則將P標(biāo)記為邊界點(diǎn)。

圖2 a—初始點(diǎn)云及探測(cè)結(jié)果[13] b—步驟一示意圖[13] c—步驟二示意圖[13]

對(duì)點(diǎn)云而言，是否為邊界點(diǎn)是一個(gè)由其鄰域所確定的固有屬性[14]，故邊緣檢測(cè)算法很容易受到離群點(diǎn)和噪聲的影響，在應(yīng)用此類方法之前應(yīng)先對(duì)點(diǎn)云做降噪處理。同樣，若點(diǎn)云密度過低或分布不均勻，則無法明確點(diǎn)云的局部特征，導(dǎo)致邊緣缺失，影響算法運(yùn)行的結(jié)果。

3 基于表面特征的分割方法

3.1 區(qū)域生長算法

區(qū)域生長算法(region growing，RG)[15]是在2維圖像分割領(lǐng)域中得到廣泛應(yīng)用的經(jīng)典算法，因其出色的分割效果被拓展至3維點(diǎn)云數(shù)據(jù)中。算法流程為：首先指定種子點(diǎn)，隨后對(duì)鄰域點(diǎn)的某些特征進(jìn)行比對(duì)，若小于預(yù)定閾值則將鄰域點(diǎn)作為新的種子點(diǎn)繼續(xù)生長，若周邊鄰域點(diǎn)沒有符合條件的點(diǎn)則跳出算法。

種子點(diǎn)的選取策略與生長與否的判斷依據(jù)是對(duì)區(qū)域生長算法效果影響最大的兩個(gè)因素。1988年，美國密歇根大學(xué)安娜堡分校的BESL等人提出選擇曲率最小的點(diǎn)作為種子點(diǎn)[16]。此準(zhǔn)則簡(jiǎn)單有效，是目前采用最多的方法[17-18]。此外，將點(diǎn)云預(yù)分割以提升種子點(diǎn)選擇質(zhì)量也是常見的方法[19]。在生長判斷準(zhǔn)則方面，閾值分類思想仍舊占據(jù)主流，平滑度[8]、RGB顏色[20]、法向量[18]、平面擬合殘差[21]等點(diǎn)特征作為生長判據(jù)被廣泛應(yīng)用于區(qū)域生長算法之中。

2019年，華中師范大學(xué)的WU等人將多尺度張量投票算法(multiscale tensor voting method,MSTVM)引入?yún)^(qū)域生長算法以確定種子點(diǎn)[22]，其流程圖如圖3所示。張量投票算法最早由德國波恩大學(xué)攝影測(cè)量研究所的SCHUSTER引入點(diǎn)云數(shù)據(jù)之中[23]，通過點(diǎn)云協(xié)方差矩陣的特征值和特征向量表述該點(diǎn)的局部幾何特征。對(duì)于張量投票算法而言，投票的數(shù)目，即尺度，對(duì)算法的效果有著至關(guān)重要的影響。因此，作者提出了MSTVM, 通過指數(shù)化半變異函數(shù)確定合適的尺度區(qū)間，在區(qū)間內(nèi)多次計(jì)算投票值以求得相對(duì)投票值，選擇相對(duì)投票值較高的點(diǎn)作為種子點(diǎn)。相較于應(yīng)用主成分分析(principle component analysis，PCA)和張量投票算法的區(qū)域生長算法，MSTVM有著更高的分割精度，對(duì)噪聲有著更高的魯棒性。

圖3 MSTVM算法流程框圖[22]

2020年，巴西坎皮納斯大學(xué)的PAIVA等人結(jié)合了分水嶺算法與區(qū)域生長算法，實(shí)現(xiàn)了對(duì)RGB點(diǎn)云建筑模型的分割[24],算法流程圖如圖4所示。對(duì)于所得初始點(diǎn)云，該算法首先通過灰度變換將其轉(zhuǎn)化為灰度圖，并利用八叉樹明確點(diǎn)云各點(diǎn)之間的連接關(guān)系。連接圖構(gòu)建完成后，平滑點(diǎn)云灰度值，以此獲取梯度作為分水嶺算法的輸入。隨后選定各區(qū)域內(nèi)的曲率最小點(diǎn)作為種子點(diǎn)應(yīng)用區(qū)域生長算法。

圖4 區(qū)域生長與分水嶺混合算法流程圖[24]

盡管區(qū)域生長算法已經(jīng)在點(diǎn)云分割領(lǐng)域得到廣泛應(yīng)用，但它的缺點(diǎn)仍舊不容忽視。種子點(diǎn)可以大幅影響算法效率，但是其選擇的依據(jù)并沒有一個(gè)統(tǒng)一的最優(yōu)解，目前應(yīng)用最為廣泛的方法是選擇曲率最小的點(diǎn)作為種子點(diǎn)，但在小部分情況下這依然無法取得較好的效果，這使得算法的穩(wěn)定性大打折扣。此外，區(qū)域生長算法要求點(diǎn)云集有足夠的連續(xù)性，若點(diǎn)云密度不均勻則難以獲得精確的結(jié)果。與基于邊緣的分割算法類似，區(qū)域生長同樣基于局部特征，故對(duì)噪聲、離群點(diǎn)十分敏感，在分割之前需要對(duì)點(diǎn)云進(jìn)行去噪、平順等預(yù)處理。

3.2 聚類算法

除區(qū)域生長算法以外，各種聚類算法也被用于進(jìn)行點(diǎn)云分割，如經(jīng)典的k均值算法[25-26]、均值漂移算法[27-28]、高斯混合模型[29]等。對(duì)于聚類算法而言，其選用特征的可靠性和質(zhì)量對(duì)算法的分割效果有著較大的影響。常用于點(diǎn)云分割的特征有點(diǎn)的空間位置信息[30-31]、法向量、點(diǎn)的局部密度等。以點(diǎn)特征構(gòu)建特征向量[32]可以提高算法的魯棒性，也是常見的特征構(gòu)建方法。也有少部分算法采用局部算子作為特征，如快速點(diǎn)特征直方圖(fast point feature histogram,FPFH)[33]、視點(diǎn)特征直方圖(viewpoint feature histogram，VFH)[34]等。

2018年，美國德克薩斯大學(xué)奧斯汀分校的CZERNIAWSKI等人[35]將基于密度的噪聲應(yīng)用空間聚類(density-based spatial clustering of applications with noise,DBSCAN)算法[36]應(yīng)用于點(diǎn)云分割。算法將點(diǎn)云映射至高斯球上以提取法向信息，并與3維坐標(biāo)相結(jié)合，構(gòu)建6維特征空間{x,y,z,nx,ny,nz}以進(jìn)行DBSCAN聚類。分割結(jié)果如圖5所示。

圖5 DBSCAN算法運(yùn)行結(jié)果[36]

2019年，浙江工業(yè)大學(xué)的HUANG等人提出了基于密度的聚類算法(density-based clustering，DBCS)[37]。該算法由DBSCAN算法發(fā)展而來，并通過將點(diǎn)云劃分為不同子集平行處理提高算法效率，其流程圖如圖6所示。對(duì)于大規(guī)模點(diǎn)云場(chǎng)景，算法先求其邊界盒，若其中子集數(shù)量大于預(yù)設(shè)值，則對(duì)矩形邊界盒進(jìn)一步進(jìn)行劃分，直至邊界盒內(nèi)點(diǎn)云數(shù)量達(dá)到閾值。

圖6 DBSC算法流程圖[37]

2020年，韓國首爾國立大學(xué)的PARK等人提出了彎曲體素的概念，并以此為基礎(chǔ)利用聚類算法完成了對(duì)點(diǎn)云數(shù)據(jù)的分割,稱作彎曲體素聚類算法[38]，流程圖如圖7所示。彎曲體素是體素在球坐標(biāo)系下的拓展，與體素類似，定義為球坐標(biāo)系內(nèi)的獨(dú)立單元，以確定的分辨率劃分整個(gè)球坐標(biāo)系。算法首先將初始點(diǎn)云自3維笛卡爾坐標(biāo)系轉(zhuǎn)換至球坐標(biāo)系中，隨后創(chuàng)建哈希表，將各點(diǎn)映射至包含其的彎曲體素中，并濾除其中的無用彎曲體素，保留含有點(diǎn)的體素。最后在哈希表中搜尋相鄰的體素，將其劃分為同一個(gè)聚類，完成分割。

圖7 彎曲體素聚類算法流程圖[38]

與區(qū)域生長算法類似，利用聚類算法來完成點(diǎn)云分割同樣也是基于點(diǎn)云及其相鄰點(diǎn)的局部特征來對(duì)散亂點(diǎn)進(jìn)行分類的。此類算法與區(qū)域生長算法最大的區(qū)別就在于聚類算法無需定義種子點(diǎn)，這使得聚類算法的適用性比區(qū)域生長算法略高，但其判斷準(zhǔn)則仍舊對(duì)算法效果有較大影響。

3.3 圖論法

圖是一種強(qiáng)大的數(shù)學(xué)工具，已在計(jì)算機(jī)視覺、目標(biāo)探測(cè)等方面得到廣泛的應(yīng)用。點(diǎn)云離散的特性也使得其與圖有著良好的相性，圖論中眾多的分割方法在點(diǎn)云數(shù)據(jù)處理中都有著廣泛的應(yīng)用潛力。圖論分割的主要思想即是確保不同片段之間的相似度最小，而相同片段中各點(diǎn)的相似性最大，點(diǎn)云中各點(diǎn)可天然視作圖中的頂點(diǎn)，因此，如何確定構(gòu)建連接圖，確定邊的權(quán)重，成為了此類方法的研究重點(diǎn)。

2017年，慕尼黑工業(yè)大學(xué)的XU等人[39]提出了基于體素與圖論方法的點(diǎn)云分割(voxel-graph based segmentation,VGS)方法。算法首先將點(diǎn)云體素化，以所得體素作為圖的頂點(diǎn)，并利用八叉樹構(gòu)建全連接圖。圖中各邊的權(quán)重則由頂點(diǎn)的空間相似度、幾何相似度與曲率變化確認(rèn)。2020年，XU等人對(duì)VGS算法進(jìn)行了進(jìn)一步的優(yōu)化[40]，其算法流程圖如圖8所示。新的算法利用幾何中心與內(nèi)部各點(diǎn)的法向量對(duì)體素進(jìn)行表示，以此為基準(zhǔn)，僅保留內(nèi)部點(diǎn)分布平面化的體素，濾除內(nèi)部點(diǎn)云呈不規(guī)則分布或曲面分布的冗余體素，提升了平面擬合效果；各邊的權(quán)重則由相鄰節(jié)點(diǎn)Vn,Vm之間的法向量角度差Dnmα和空間距離Dnmp得到：

圖8 VGS算法流程圖[40]

(1)

式中,δα和δp為權(quán)重參數(shù)。分割完成后，應(yīng)用RANSAC算法進(jìn)行平面提取。

以圖論作為理論基礎(chǔ)有著較好的可解釋性，在復(fù)雜場(chǎng)景下基于圖論的點(diǎn)云分割可以取得很好的效果，但此類算法仍舊有著很高的時(shí)間復(fù)雜度，難以實(shí)現(xiàn)實(shí)時(shí)應(yīng)用。

4 基于模型擬合的點(diǎn)云分割

此類算法通過將所得點(diǎn)云與預(yù)設(shè)模型進(jìn)行擬合來實(shí)現(xiàn)點(diǎn)云分割，其所使用的形狀基元在參考文獻(xiàn)[41]中有著詳細(xì)的介紹，在此不多贅述；而其中使用最為廣泛、效果最為出色的算法是3-D霍夫變換(3-D Hough transform，3DHT)[42]、隨機(jī)采樣一致(random sample consensus，RANSAC)[43]，以及它們的一系列衍生算法。

4.1 霍夫變換算法

霍夫變換是一種純數(shù)學(xué)的參數(shù)空間轉(zhuǎn)換方法，由HOUGH在1960年提出[44]。通過改變點(diǎn)的數(shù)學(xué)表現(xiàn)形式，將點(diǎn)從3維空間映射至參數(shù)空間完成投票，對(duì)各種可參數(shù)化的形狀有良好的探測(cè)效果。霍夫變換由3步構(gòu)成[45]：(1)構(gòu)建參數(shù)空間；(2)由輸入數(shù)據(jù)累計(jì)投票；(3)在參數(shù)空間中識(shí)別模型。對(duì)于3維笛卡爾空間中的平面，其方程為：

a·x+b·y+c·z+d=0

(2)

可寫為：

z=sxx+syy+D

(3)

式中,sx和sy為平面對(duì)z軸的斜率，D為平面在z軸的截距。由此可定義一個(gè)三變量空間，即霍夫空間?；舴蚩臻g中的點(diǎn)與3維坐標(biāo)系中的平面一一對(duì)應(yīng)，利用這樣的對(duì)應(yīng)關(guān)系即可以通過投票算法完成擬合。

2019年，荷蘭代爾夫特大學(xué)的WIDYANINGRUM等人提出了基于有序點(diǎn)表(ordered points lists，OPL)輔助的霍夫變換算法，并實(shí)現(xiàn)了對(duì)空載激光雷達(dá)建筑物點(diǎn)云邊界線的提取[46]，算法流程圖及分割結(jié)果如圖9所示。OPL由霍夫矩陣變換而來，與霍夫矩陣有著相同的維度與參數(shù)。兩者的區(qū)別在于：霍夫矩陣僅保存行內(nèi)直線的投票點(diǎn)的數(shù)量，而OPL保存了這些點(diǎn)的有序表。通過設(shè)定間隔空隙，算法對(duì)包含點(diǎn)不連續(xù)的直線進(jìn)行了分割，解決了傳統(tǒng)霍夫變換對(duì)方向相同但屬于不同分割片段的直線誤判斷問題，大幅提高了建筑物邊界提取的質(zhì)量。

圖9 OPL輔助霍夫變換算法流程圖[46]

同年，北方工業(yè)大學(xué)的SONG等人與澳門大學(xué)的TIAN利用3DHT實(shí)現(xiàn)了大規(guī)模MLS云的地面提取[47]。算法同時(shí)利用了中央處理器(central processing unit,CPU)與圖形處理器(graphics processing unit,GPU)，并將3-D霍夫空間體素化，實(shí)現(xiàn)了利用GPU的并行計(jì)算，大幅提升了算法效率。GPU-CPU混合地面提取算法框架如圖10所示。

圖10 GPU-CPU混合地面提取系統(tǒng)框架[47]

2020年，TIAN等人通過構(gòu)建標(biāo)志圖對(duì)算法進(jìn)行了進(jìn)一步優(yōu)化[48]。

標(biāo)志圖與霍夫空間維度相同，主要用于實(shí)現(xiàn)對(duì)3-D霍夫空間內(nèi)體素的一對(duì)一標(biāo)記，對(duì)有效體素則通過霍夫空間內(nèi)的坐標(biāo)計(jì)算標(biāo)志值：

l(i,j,k)=

(4)

式中,i,j,k分別為標(biāo)志圖的3維坐標(biāo)，h(i,j,k)為霍夫空間內(nèi)相應(yīng)坐標(biāo)的投票值，IH，JH和KH分別為霍夫空間內(nèi)各3維方向上的體素?cái)?shù)量。

在此基礎(chǔ)上，算法將相連的體素聚類為同一集團(tuán)，并取集團(tuán)內(nèi)的最小標(biāo)志值代表集團(tuán)。此時(shí)，同一集團(tuán)內(nèi)標(biāo)志值相同，不同集團(tuán)之間標(biāo)志值相異，遍歷所有集團(tuán)即可完成峰值搜索。算法流程如圖11所示。

圖11 地面探測(cè)系統(tǒng)流程框圖[48]

4.2 隨機(jī)采樣一致(RANSAC)算法

RANSAC算法基于對(duì)模型的假設(shè)與選擇，通過隨機(jī)選取點(diǎn)云中的若干子集對(duì)模型進(jìn)行多次擬合，從中選取擬合效果最佳的模型作為擬合結(jié)果。RANSAC算法簡(jiǎn)單且強(qiáng)大，2007年，法國國立應(yīng)用科學(xué)學(xué)院的TARSHA-KURDI等人[49]將3-D霍夫變換與RANSAC算法進(jìn)行了比較，實(shí)驗(yàn)證明，RANSAC算法有著更高的效率與精準(zhǔn)度。

2017年，武漢大學(xué)LI等人將RANSAC算法與正態(tài)分布變換單元(normal distribution transformation cells，NDT Cells)相結(jié)合，用于點(diǎn)云數(shù)據(jù)的平面分割[50]。NDT與體素類似，為小尺寸立方體，包含若干點(diǎn)云，其內(nèi)部點(diǎn)云視為正態(tài)分布。在完成對(duì)初始點(diǎn)云的劃分后，求各單元內(nèi)點(diǎn)云的協(xié)方差矩陣，其特征值與特征向量作為單元特征表述各單元的幾何特性，并以此為依據(jù)提取平面分布的正態(tài)分布單元。最終，對(duì)平面分布的正態(tài)分布單元內(nèi)應(yīng)用RANSAC算法，實(shí)現(xiàn)平面分割，并以迭代加權(quán)最小二乘法計(jì)算法向量，進(jìn)行平面擬合，完成平面融合。其算法運(yùn)行結(jié)果如圖12所示。

圖12 NDT-based RANSAC算法運(yùn)行結(jié)果[50]

最大似然估計(jì)采樣一致算法(maximum likelihood estimation sample consensus，MLESAC)由微軟研究院的TORR與牛津大學(xué)的ZISSERMAN[51]提出，以模型的似然度代替內(nèi)點(diǎn)數(shù)量對(duì)模型擬合效果進(jìn)行評(píng)估。2020年，武漢大學(xué)ZHAO等人[52]將MLESAC算法進(jìn)行優(yōu)化，提出Prior-MLESAC算法，并應(yīng)用于室內(nèi)點(diǎn)云數(shù)據(jù)分割，其示意圖如圖13所示。Prior-MLESAC算法在進(jìn)行模型擬合值前，先基于迭代高斯映射對(duì)點(diǎn)云進(jìn)行粗分割。理論上，所有位于平行平面上的點(diǎn)映射至高斯球上后應(yīng)為同一個(gè)點(diǎn)，由此可通過對(duì)點(diǎn)云進(jìn)行高斯映射，并對(duì)所得高斯球進(jìn)行DBSCAN算法完成平行平面提取。在此基礎(chǔ)上，以剩余的點(diǎn)云作為輸入，逐漸調(diào)整DBSCAN算法的參數(shù)，迭代地對(duì)點(diǎn)云進(jìn)行提取，實(shí)現(xiàn)對(duì)點(diǎn)云的粗分割。粗分割完成后，由PCA算法定義曲率特征：

圖13 a—Prior-MLESAC算法流程框圖[52] b—迭代高斯映射分割示意圖[52] c—分割結(jié)果[52]

(5)

式中,λi(i=1,2,3)為PCA所得張量的特征值，描述局部區(qū)域彎曲度的概率：

ω=(1-Pc)2

(6)

作為各點(diǎn)的先驗(yàn)特征，以此引導(dǎo)點(diǎn)云的采樣，對(duì)屬于不同模型的點(diǎn)應(yīng)用不同的采樣策略。

同年，南方科技大學(xué)的WU等人利用RANSAC算法實(shí)現(xiàn)了點(diǎn)云數(shù)據(jù)中成對(duì)正交平面(pairwise orthogonal planes，POP)的提取[53]。對(duì)于成對(duì)正交平面，作者將其視為一個(gè)由4個(gè)兩面角構(gòu)成的整體模型，由平面的法向量與相交線定義兩面角，實(shí)現(xiàn)了對(duì)成對(duì)正交平面模型的表述。在此基礎(chǔ)上，算法基于八叉樹結(jié)構(gòu)將點(diǎn)云結(jié)構(gòu)化，先在位于同一節(jié)點(diǎn)內(nèi)的子集中生成候補(bǔ)模型，隨后將其擴(kuò)張至整個(gè)點(diǎn)云，實(shí)現(xiàn)RANSAC算法,其算法結(jié)果如圖14所示。實(shí)驗(yàn)證明，相較于傳統(tǒng)的平面擬合，成對(duì)平面擬合有著更高的效率，對(duì)正交的微小平面也有足夠的處理能力。

圖14 POP-RANSAC算法對(duì)單個(gè)房間的分割結(jié)果[53]

相較于3-D霍夫變換算法，RANSAC算法有著更快的運(yùn)行速度，對(duì)噪聲有更強(qiáng)的魯棒性，有著更廣泛的應(yīng)用場(chǎng)景，但其仍舊有著較高的時(shí)間復(fù)雜度，難以投入到大型場(chǎng)景的實(shí)際應(yīng)用中；此外，算法自定義參數(shù)較少，對(duì)參數(shù)的選擇十分敏感，這對(duì)算法在不同場(chǎng)景下的適配程度有所影響；最后，此類算法對(duì)點(diǎn)云的質(zhì)量有著較高的要求，處理低精度、大場(chǎng)景的點(diǎn)云需要額外的措施對(duì)點(diǎn)云進(jìn)行優(yōu)化。因此，此類算法現(xiàn)多用于對(duì)其它算法所得的粗分割結(jié)果進(jìn)行優(yōu)化。

5 部分算法性能比較

表1中總結(jié)了各算法的性能參數(shù)，并統(tǒng)計(jì)了其主要應(yīng)用場(chǎng)景。由于面向不同場(chǎng)景的算法側(cè)重點(diǎn)有所不同，其評(píng)估方法也有所差異，故部分參數(shù)缺省。由表1可見，對(duì)于MLS和TLS點(diǎn)云而言，若應(yīng)用于大場(chǎng)景戶外點(diǎn)云，基于邊緣探測(cè)的NORVANA與Mo-NORVANA算法在保證高精準(zhǔn)度的同時(shí)有著最高的算法效率，相較于其它算法有著3～4個(gè)數(shù)量級(jí)上的提升；而對(duì)于室內(nèi)場(chǎng)景，其點(diǎn)云密度較高且分布更為均勻，模型也更加規(guī)則，因此模型擬合類算法可以獲得優(yōu)秀的分割結(jié)果?；诒砻嫣卣鞯乃惴ㄔ砗?jiǎn)單、容易實(shí)現(xiàn)、效率良好、準(zhǔn)確度也較高，但其精確度與召回率較低，因此易產(chǎn)生過分割與欠分割問題。由MSTVM算法可見，種子點(diǎn)的選取質(zhì)量對(duì)區(qū)域生長算法的分割效果有著較大影響，但若選擇算法過于復(fù)雜，則算法效率大打折扣，故需要針對(duì)不同需求分別應(yīng)用；對(duì)于機(jī)載激光掃描(airborne laser scanning,ALS)點(diǎn)云而言，由于其點(diǎn)云密度較低且不穩(wěn)定，對(duì)算法性能提出了較大挑戰(zhàn)，僅有模型擬合類算法有著較好的運(yùn)行結(jié)果，其余算法則不甚理想。

表1 部分算法性能參數(shù)

6 影響點(diǎn)云分割算法效率的主要因素

在過去幾年中，研究者們?cè)邳c(diǎn)云分割領(lǐng)域中完成了大量的工作，許多不同的算法被開發(fā)，但由于點(diǎn)云數(shù)據(jù)仍存在一些限制，導(dǎo)致目前在實(shí)際工程中難以實(shí)現(xiàn)實(shí)時(shí)應(yīng)用。本節(jié)中總結(jié)了對(duì)算法效率產(chǎn)生影響的主要因素，對(duì)其進(jìn)行了簡(jiǎn)要的分析。

6.1 特征的獲取

基于局部特征的算法中，相似度的表征與所選用的特征直接相關(guān)，在模型擬合類算法中，其所選擇的擬合基元也可視作特征。點(diǎn)云分割算法中所使用的特征對(duì)算法的效率與精確度有著至關(guān)重要的影響，現(xiàn)今，大多數(shù)算法所使用的特征為點(diǎn)特征，如法向量、RGB顏色、返回激光的強(qiáng)度、空間位置，以及在法向量的基礎(chǔ)上進(jìn)一步計(jì)算得到的若干高階特征，如曲率、梯度等。除點(diǎn)特征外也有部分諸如FPFH、半徑表面描述子(radius-based surface descriptor，RSD)等高階算子被應(yīng)用于點(diǎn)云分割算法之中，此類高階算子可以提供更高的精度，但其計(jì)算需要較高算力，對(duì)算法效率有所影響，故尚未得到廣泛應(yīng)用。在點(diǎn)云的法向量估計(jì)方法中，占據(jù)主要的是以PCA為代表的局部平面擬合類算法，此類算法簡(jiǎn)單有效，因此應(yīng)用得最為廣泛，但其對(duì)鄰域大小和點(diǎn)云噪聲較為敏感，且對(duì)尖銳特征的表述有所欠缺，容易影響特征估算的精度。

6.2 鄰域大小的確定

鄰域的大小對(duì)算法有著較大影響，鄰域范圍過大會(huì)導(dǎo)致算法復(fù)雜度較高，過小則會(huì)影響特征估算的精度。最為常用的鄰域確定方法有k最近鄰(k-nearest neighbor，KNN)和固定半徑鄰域(fixed distance neighbor,FDN)兩種。在實(shí)踐中，F(xiàn)DN需要根據(jù)算法的應(yīng)用場(chǎng)景來調(diào)整截?cái)嗑嚯x，這對(duì)使用者的經(jīng)驗(yàn)提出了要求，限制了FDN的應(yīng)用范圍。與此相對(duì)，KNN對(duì)點(diǎn)云密度自適應(yīng)，有著更為廣泛的應(yīng)用場(chǎng)景，但是對(duì)噪聲和離群點(diǎn)敏感，對(duì)點(diǎn)云數(shù)據(jù)的質(zhì)量有較高要求。除此之外，將點(diǎn)云結(jié)構(gòu)化以確定鄰域也是比較常見的做法，如將點(diǎn)云數(shù)據(jù)體素化[54]、網(wǎng)格化[55]，利用掃描線確定鄰域等[54]。由表1可見，此類方法可大幅提升算法的運(yùn)行效率，但其增加了算法的步驟，并對(duì)使用場(chǎng)景和數(shù)據(jù)獲取方式提出了要求，因此只有在特定場(chǎng)景下得到應(yīng)用。

6.3 算法的自動(dòng)化程度

點(diǎn)云分割的對(duì)象是復(fù)雜多變的，同一個(gè)算法在不同的場(chǎng)景下難以得出相同的結(jié)果，因此在算法實(shí)現(xiàn)過程中仍舊需要人工調(diào)整參數(shù)，以改善算法的運(yùn)行結(jié)果。但人工干預(yù)增加了算法的不可控變量，往往需要多次實(shí)驗(yàn)才能得到良好的參數(shù)，這增加了算法設(shè)計(jì)的成本，降低了算法的適應(yīng)性。

6.4 應(yīng)用場(chǎng)景的限制

遙感測(cè)繪與計(jì)算機(jī)視覺是點(diǎn)云數(shù)據(jù)的兩大主要應(yīng)用領(lǐng)域，但是兩者有著不同的注重點(diǎn)，導(dǎo)致領(lǐng)域之間算法難以互通，需要根據(jù)應(yīng)用場(chǎng)景對(duì)算法進(jìn)行調(diào)整。兩者的區(qū)別主要有以下幾點(diǎn)：

(1)算法的評(píng)估方式。在計(jì)算機(jī)視覺應(yīng)用中，點(diǎn)云分割算法的側(cè)重點(diǎn)在于整體的精度，而在遙感測(cè)繪領(lǐng)域中，算法往往更為關(guān)注對(duì)建筑物等特定目標(biāo)的提取。因此在算法效果的評(píng)估方面，兩者需要不同的評(píng)估方式來選擇與實(shí)際情況更加契合的算法。

(2)點(diǎn)云的獲取方式。點(diǎn)云數(shù)據(jù)的主要獲取方式有攝影測(cè)量、深度相機(jī)、激光雷達(dá)、逆向工程等。遙感測(cè)繪應(yīng)用需要復(fù)雜且具體的大面積點(diǎn)云數(shù)據(jù)，因此大多是通過激光雷達(dá)與攝影測(cè)量得到點(diǎn)云。這種方法所獲點(diǎn)云密度不恒定，數(shù)據(jù)量較大，分布不均勻且充滿著噪聲和離群點(diǎn)，在進(jìn)行點(diǎn)云分割時(shí)有著更多的限制。而計(jì)算機(jī)視覺更加關(guān)注具體的3維細(xì)節(jié)，因此需要較高的密度和均勻的分布。其主要的獲取方式是深度相機(jī)與模型逆向工程。由此方法獲取的點(diǎn)云密度高，故處理時(shí)算法有著更高的時(shí)間花費(fèi)。

(3)數(shù)據(jù)格式。點(diǎn)云數(shù)據(jù)包含著物體表面的3維坐標(biāo)信息，除此之外，由激光雷達(dá)所得的數(shù)據(jù)還包含著返回激光的強(qiáng)度，由攝影測(cè)量與深度相機(jī)所得的數(shù)據(jù)包含著該點(diǎn)的顏色信息。此類信息可以作為特征來提高算法的效果，但也導(dǎo)致算法難以在不同設(shè)備獲取的數(shù)據(jù)之間通用。

(4)對(duì)數(shù)據(jù)的預(yù)處理。在計(jì)算機(jī)視覺領(lǐng)域中，數(shù)據(jù)的噪點(diǎn)與離群點(diǎn)并不會(huì)對(duì)算法的效果造成過多影響，這是由其獲取方式和算法側(cè)重點(diǎn)所決定的。在高密度的點(diǎn)云中可以較為容易的濾除離群點(diǎn)，且增強(qiáng)了對(duì)噪聲的魯棒性。但在遙感測(cè)繪領(lǐng)域，傳感器帶來的噪聲難以避免，在點(diǎn)云密度不均勻的情況下加重了對(duì)算法的影響。因此，算法需要針對(duì)濾波去噪平順等方面進(jìn)行大量的預(yù)處理，以盡量提高點(diǎn)云質(zhì)量。

7 結(jié)束語

點(diǎn)云相較于其它3維數(shù)據(jù)，在處理時(shí)耗費(fèi)資源較少，因此成為了計(jì)算機(jī)視覺、遙感測(cè)繪等領(lǐng)域的首選信息表示形式和處理對(duì)象。點(diǎn)云分割作為點(diǎn)云數(shù)據(jù)處理過程中的重要步驟，是實(shí)現(xiàn)相關(guān)應(yīng)用的關(guān)鍵技術(shù)，其分割結(jié)果直接關(guān)系到后續(xù)算法的效果，故一直以來受到廣泛關(guān)注，研究熱度居高不下。針對(duì)本領(lǐng)域中仍舊存在的問題，如特征估計(jì)難、自動(dòng)化程度低等，研究人員正在不斷探索，對(duì)算法不斷進(jìn)行優(yōu)化，取得了相當(dāng)卓越的成績(jī)。3維信息獲取設(shè)備的不斷發(fā)展也給點(diǎn)云分割提供了更多的硬件支持和處理路徑，隨著獲取點(diǎn)云的不斷豐富，在多傳感器協(xié)同工作下的特征提取更加便捷。在自動(dòng)駕駛、智能機(jī)器人等需求的牽引下，點(diǎn)云數(shù)據(jù)處理方法必將迎來新一波的發(fā)展熱潮。