張良培，張 云，陳震中，肖佩珮，羅 斌

武漢大學(xué)測繪遙感信息工程國家重點實驗室，湖北 武漢 430079

數(shù)字攝影測量三維構(gòu)象采用多個視角拍攝的圖像來實現(xiàn)三維場景模型的恢復(fù)，是構(gòu)建智慧城市[1]的重要基礎(chǔ)技術(shù)之一。通常，由大量大范圍航拍影像或者高分辨率影像所進行多視重構(gòu)獲得的場景三維點云數(shù)據(jù)量較大、結(jié)構(gòu)復(fù)雜，首要解決的關(guān)鍵性問題是需要對點云進行分割處理。

點云經(jīng)過分割處理，復(fù)雜的點云數(shù)據(jù)將會被分割成各個簡單的幾何圖元[2-3]，通過對簡單幾何圖元的識別和組合，逐步構(gòu)建復(fù)雜的三維模型，進而實現(xiàn)精細化的三維構(gòu)象。因此三維點云的分割是實現(xiàn)三維構(gòu)象的重要基礎(chǔ)[4]。

點云數(shù)據(jù)分割方法總體上可以歸類為模型驅(qū)動和數(shù)據(jù)驅(qū)動兩種[5]。其中模型驅(qū)動方法作為一種自頂向下的方法，首先建立圖元庫，再將點云中建筑物與預(yù)先定義的圖元進行匹配，從而獲得圖元分割結(jié)果。而基于數(shù)據(jù)驅(qū)動的點云分割方法，通過點云數(shù)據(jù)的各類特征實現(xiàn)對點云的分割。文獻[6]證實了在點云屋頂面分割情況下，模型驅(qū)動的方法能夠保證拓撲關(guān)系的正確性但在細節(jié)上難以保證?；跀?shù)據(jù)驅(qū)動的點云分割方法又可以大致分為[7]：基于邊緣的分割方法[8-9]、基于區(qū)域生長的分割方法[10-15]、基于特征的分割方法[16-20]、基于圖的分割方法[21-24]、基于模型的分割方法[25-31]及混合方法[32-35]。

通?；谶吘壍姆指钏惴ㄍㄟ^檢測點云數(shù)據(jù)中隱藏的邊緣信息來得到分割區(qū)域，此類方法中點云的邊緣定義點云強度變化或者表面法向量變化較大的區(qū)域。類似于圖像邊緣檢測，文獻[8]提出了利用梯度進行邊緣檢測，通過檢測出的三維直線對點集進行擬合，最后基于點云法向量的方向進行強度變化的檢測；文獻[9]采用了一種基于掃描線的邊緣檢測器算法，該算法給出了最優(yōu)邊緣檢測的定義，提供了保證邊緣強度的方法原理和幾何解釋?；谶吘壍姆指钏惴ǚ指钏俣瓤?，但是點云數(shù)據(jù)在提取邊緣時容易受噪聲和點云密度影響，其抗噪能力差，難以適用于結(jié)構(gòu)較為復(fù)雜的點云分割處理，實際應(yīng)用中并不常見。

基于區(qū)域生長的方法通常是首先選取種子面，以此作為起始點，通過比較鄰域內(nèi)各個點與種子面的相似程度，對各個種子面周圍的離散點云進行分組，不斷向外擴展，最終實現(xiàn)完全劃分。這類算法最早由文獻[10]提出，其關(guān)鍵主要包括種子面的選取及生長規(guī)則。選取種子面通常是采樣測試任意一個未分類的點，判斷該點鄰域內(nèi)能夠擬合為平面的點的數(shù)目是否達到最少標(biāo)準(zhǔn)，如果是，則這些點構(gòu)成種子表面。生長規(guī)則是通過比較坡度、曲率和曲面法向量等相似度來判斷是否進行生長。這類方法對噪聲和離群點不敏感，魯棒性強，適合大規(guī)模復(fù)雜場景的分割處理，但是受初始選取的種子曲面影響較大，種子曲面選取不當(dāng)很容易造成巨大的分割誤差。并且會收到生長規(guī)則的制約，生長規(guī)則直接決定分割結(jié)果，但是很多情況下，生長規(guī)則的選取難以符合數(shù)據(jù)中包含的所有圖元屬性。

基于特征的分割方法主要是采用點云所表現(xiàn)出來的幾何結(jié)構(gòu)特征或者空間分布特征來對點云進行特征聚類，得到分割結(jié)果。其中文獻[16]采用了紋理特征來對點云數(shù)據(jù)進行描述，通過特征聚類來對點云數(shù)據(jù)進行分割；文獻[18—19]則采用法向量和顏色信息作為特征；文獻[20]則利用表面法向量實現(xiàn)對點云的實時平面分割?；谔卣鞯姆指罘椒ㄓ捎趯Ⅻc云分割問題轉(zhuǎn)換到特征空間的聚類問題進行處理，其分割結(jié)果不受點云空間分布影響，但是同時其分割結(jié)果取決于所采用的特征以及聚類方法，特征描述的好壞直接決定最終的分割效果，并且通常隨著點云數(shù)量的增加，時間消耗較大，當(dāng)采用較多維數(shù)的特征時，時間效率很低，所以此類方法難以用于點云規(guī)模較大的分割處理。

基于圖的分割方法是將點云數(shù)據(jù)當(dāng)作頂點，利用點的空間鄰域關(guān)系構(gòu)造邊，利用鄰域點的相似性對連接邊進行加權(quán)，構(gòu)造成圖，利用圖割[22，24]的方法實現(xiàn)點云的分割?；趫D的分割方法通常采用全局優(yōu)化的策略進行求解，能夠獲得全局的優(yōu)化結(jié)果，并且不受數(shù)學(xué)模型和場景復(fù)雜程度的影響，但是由于點云的數(shù)據(jù)量大，構(gòu)造的圖通常異常復(fù)雜，進行優(yōu)化計算時通常時間復(fù)雜度較高。

基于模型的分割方法通常采用簡單幾何圖元的數(shù)學(xué)參數(shù)模型最為先驗信息，通過驗證點云對模型參數(shù)的符合程度，將點云劃分到相應(yīng)的圖元類別之中，實現(xiàn)分割處理。其中最為典型的就是采用隨機抽樣一致性RANSAC[25]的方法進行的點云分割處理。首先對點云數(shù)據(jù)進行采樣，計算每組采樣集的模型參數(shù)(直線、圓和平面等)，然后統(tǒng)計各個點到模型的距離(模型殘差)，通過設(shè)定內(nèi)點閾值將距離小于閾值的點作為其內(nèi)點，在一輪大量采樣之后選擇內(nèi)點數(shù)最多的模型最為提取結(jié)果，其內(nèi)點即為提取模型對應(yīng)的分割結(jié)果。如此完成一次分割過程，通過循環(huán)執(zhí)行RANSAC來不斷在剩余的點集中分割出模型，最終實現(xiàn)整個數(shù)據(jù)集合的分割?；谀Ｐ偷姆指罘椒ɑ旧隙际窃赗ANSAC的基礎(chǔ)上改進而來，其中文獻[26]對比分析了擴展的RANSAC方法和3D Hough變化方法在Lidar點云的屋頂面提取的效果；文獻[27]采用改進的RANSAC分割網(wǎng)格，并實現(xiàn)對符合多種模型的點云進行的同時分割；文獻[28]在提出一種自適應(yīng)的RANSAC方法，通過引入距離、標(biāo)準(zhǔn)差、法向量等信息，來保證最終對屋頂面點云分割效果的拓撲關(guān)系的正確性；文獻[31]將RANSAC融入其提出的基于局部采樣和統(tǒng)計推理的點云分割算法之中來實現(xiàn)點云數(shù)據(jù)中的平面、圓柱體和曲面分割?；谀Ｐ偷姆指罘椒ㄓ捎诓捎脠D元的數(shù)學(xué)參數(shù)模型來對點云進行分割，采用幾何原理及數(shù)學(xué)公式進行參數(shù)解算，能實現(xiàn)更加高效、快捷的計算。采用幾何圖元參數(shù)模型實質(zhì)上是對局部點云的抽象降維處理，能夠?qū)⒋罅康狞c云數(shù)據(jù)表示成簡單的圖元模型參數(shù)，一方面方便點云數(shù)據(jù)的處理，另一方面能夠?qū)崿F(xiàn)點云數(shù)據(jù)的高效壓縮，為后續(xù)的點云存儲管理提供便利。并且將海量的點云數(shù)據(jù)經(jīng)過這類方法處理后，能夠轉(zhuǎn)化成即為規(guī)則的簡單圖元組合，能夠?qū)崿F(xiàn)后續(xù)的拓撲分析。不僅如此，基于模型的分割方法具有較強的抗噪能力和對離群點具有較強的魯棒性，可實現(xiàn)對海量點云數(shù)據(jù)的分割處理。

目前絕大多數(shù)的基于模型的點云分割方法基本上是依據(jù)RANSAC的方法改進而來，RANSAC作為一種經(jīng)典的單模型擬合方法，通過“擬合-剔除”的策略(擬合出一個圖元模型后剔除其內(nèi)點，在剩余點集中再使用RANSAC)來實現(xiàn)對多個模型的提取分割。而基于RANSAC的多模型擬合方法Sequential RANSAC[36-37]和Multi-RANSAC[38]，在模型數(shù)目較多時，偽離群點的數(shù)量急劇增加，多數(shù)情況下難以實現(xiàn)較好的分割結(jié)果。并且基于RANSAC的分割方法很大程度上沒有考慮點云的空間信息，即屬于同一個分割子集的點通常情況下是空間相鄰的，在多數(shù)情況下會導(dǎo)致過分割。不僅如此，采用類似RANSAC的“擬合-剔除”策略進行分割時，如果前一次的分割結(jié)果出現(xiàn)誤差，會影響后續(xù)的分割結(jié)果，一次分割結(jié)果的好壞很大程度上依賴于內(nèi)點的閾值。因此，本文采用了基于分裂合并的多模型擬合方法，首先采用基于鄰域的采樣策略，生成假設(shè)模型，如此利用點云數(shù)據(jù)的較強空間相關(guān)性的特性(空間相鄰的點屬于同一個分割區(qū)域的可能性較大)，獲得較好的模型采樣結(jié)果。然后在生成的假設(shè)模型上統(tǒng)計模型內(nèi)點，接下來在各個假設(shè)模型的模型內(nèi)點集合，分別進行基于鄰域的假設(shè)模型生成，從而實現(xiàn)一個假設(shè)模型分裂成若干個假設(shè)模型，此時采樣獲得的假設(shè)模型不僅包含有空間的先驗，還包含模型空間的先驗(假設(shè)正確的模型內(nèi)點被包含在同一假設(shè)模型的可能性越大)，由此獲得更加準(zhǔn)確的模型采樣。最后采用最小殘差分組的策略來實現(xiàn)屬于不同模型內(nèi)點的分割處理，由此實現(xiàn)多個模型內(nèi)點的同時分割，并且最大限度的排除離群點的干擾，獲得準(zhǔn)確的模型內(nèi)點分割結(jié)果，即作為最終的點云分割結(jié)果。

一般而言，通過擬合平面和柱面基本可以滿足室內(nèi)場景點云分割需求。但在模型擬合過程中，平面和柱面的擬合過程經(jīng)常相互干擾：當(dāng)存在過分割時，一個完整柱面會被擬合為大量平面；而當(dāng)出現(xiàn)欠分割情況時，平面會被擬合為半徑巨大的圓柱。因此，在多模型擬合過程中，往往需要經(jīng)過多次檢驗和判斷，實現(xiàn)對平面和柱面的合理劃分。對此，本文通過先對點云數(shù)據(jù)分割成細部后進行平面擬合，將擬合出過多平面模型的區(qū)域置為問題區(qū)域進行二次判斷，以確定是否有柱面出現(xiàn)。通過這種方法減輕平面和弧面的相互干擾程度。

進一步，本文提出了一套基于模型擬合方法的室內(nèi)點云分割流程。由于點云數(shù)據(jù)通常存在大量的冗余，并且具有較強的空間相關(guān)性，即空間相鄰的點云很可能屬于同一分割區(qū)域。并且在采用基于模型的方法進行分割時，點云的這種分布特性異常顯著。因為簡單幾何圖元的模型參數(shù)計算通常僅需要幾個點即可完成，例如直線需要2個點計算出一組參數(shù)，圓需要3個點，平面需要3個點。因此，在擬合平面闡述時僅需要極少的點即可完成，當(dāng)需要擬合出較為準(zhǔn)確的模型參數(shù)時，其所需點數(shù)相對于點云數(shù)據(jù)而言也是極少的，并且這種較強的空間關(guān)系更有利于擬合出準(zhǔn)確的圖元模型參數(shù)。因此，首先可對原始點云數(shù)進行低采樣率降采樣后，利用基于密度的聚類算法對點云進行預(yù)分割。在預(yù)分割后的子集上，借由分裂合并的多模型擬合方法探測平面。對問題區(qū)域，判斷擬合圓柱面，獲得對降采樣點云的分割結(jié)果。最后將原始點云依照距離判斷和臨近關(guān)系判斷分配到擬合出的模型上，最終實現(xiàn)對室內(nèi)點云的分割。相對于其他對比試驗方法，此流程在時間開銷以及內(nèi)存要求上表現(xiàn)優(yōu)異。同時，擬合效果也遠優(yōu)于目前常用在點云分割上的RANSAC類方法和其他的多模型擬合方法。

以下首先介紹基于分裂合并的多模型擬合方法的基本原理和方法流程，然后采用本方法針對實際的點云分割處理進行試驗，通過傳統(tǒng)MeanShift和MultiRANSAC方法的比較，分析本文提出方法的特點，最后對本文內(nèi)容進行總結(jié)。

1 點云分割方法

本文所采用的基于分裂合并的多模型擬合方法來進行點云分割，首先為了加快點云分割的速度，采用基于密度的聚類方法首先進行點云的預(yù)分割處理，然后采用分裂合并的多模型擬合方法進行精細化的分割，最后當(dāng)需要處理圓柱等典型幾何圖元分割時，采用切片技術(shù)進一步對結(jié)果進行整合處理。以下分別從這三個方面進行詳細的闡述。

1.1 基于密度聚類實現(xiàn)預(yù)分割

點云分布往往具有不均勻性。針對室內(nèi)點云，由于數(shù)據(jù)采集過程中，在不同模型接連處，由于反射、遮擋等往往數(shù)據(jù)密度易受影響，而同一模型的數(shù)據(jù)密度則較為穩(wěn)定。在經(jīng)過較低采樣率采樣過后，這個差異被進一步增強，數(shù)據(jù)點之間密度差異性增大。

DBSCAN(density-based spatial clustering of applications with noise)[39]算法作為一種基于密度的聚類算法，通過考察樣本分布密度，來實現(xiàn)對樣本可連續(xù)性的判斷，并基于可連接樣本，不斷擴展聚類簇，最終獲得聚類結(jié)果。DBSCAN算法可以將附近的點分為一組，并標(biāo)記出分布密度低的，遠離其他數(shù)據(jù)點的噪聲點。

DBSCAN算法流程如下：

(1) 遍歷樣本集D={x1,x2,x3,…,xm}，計算ε-鄰域，若樣本xi的ε-鄰域，內(nèi)至少包括Minpts個樣本，則將xi設(shè)為核心對象，加入核心對象集合Ω，且稱該點ε-鄰域內(nèi)的其他點相對于xi密度直達。

(2) 隨機選取一個核心對象o∈Ω，則該核心對象與該核心對象的所有密度相連點，構(gòu)成聚類簇Ck；將該聚類簇中所有點，從樣本點中和核心對象集合中剔除。

(3) 循環(huán)步驟(2)，直到核心對象集合為空。

(4) 算法結(jié)束，樣本集被劃分為聚類簇。部分密度過小的數(shù)據(jù)點，被劃分為噪聲。

1.2 基于分裂合并的多模型擬合方法

分裂合并的多模型擬合方法主要包括兩部分：假設(shè)模型的生成和模型的分裂組合過程。在模型生成階段，采用較大閾值，獲取初次分割的模型；在模型分裂階段，使用更為嚴(yán)苛的閾值，在初次分割的模型基礎(chǔ)上進行二次分裂，獲得子模型，分割過程可能經(jīng)過多次重復(fù)。最后對所有子模型進行判斷，選擇最優(yōu)模型，作為輸出。

1.2.1 假設(shè)模型的生成

假設(shè)模型的生成是通過選擇足夠多數(shù)目的鄰域點來計算得出模型。通過迭代選擇數(shù)據(jù)中在一定閾值內(nèi)鄰域點數(shù)目最多的點集(密度最大的鄰域點集)計算出模型并統(tǒng)計其內(nèi)點，然后剔除內(nèi)點在剩下的點集中重復(fù)以上步驟，直至沒有模型能夠提取出來。

假設(shè)d為數(shù)據(jù)集X:={xi|xi∈Rd}i=1,…,n，模型計算函數(shù)為F(θ,x)=0，r=RF(θ,x)為模型θ的殘差計算函數(shù)。

定義數(shù)據(jù)集X上的最佳擬合模型

(1)

其內(nèi)點集計算如下

(2)

其中TI為內(nèi)點閾值

(3)

式(3)為離點x距離小于TN的鄰域點集.定義閾值為TN的最密集鄰域點集為

(4)

假設(shè)模型生成算法描述如算法1所示。其中MPF(minimum points needed for fitting)為擬合參數(shù)所需做少數(shù)據(jù)點的個數(shù)。

算法1 假設(shè)模型生成HS=HG(X,TN,TI,MPF):

1. 輸入數(shù)據(jù)X0=X，初始化假設(shè)模型HS=φ，i=0;

2. while card(X0)≥MPF;

3. 按照式(3)，以TN為閾值，找出點集X0中最密集的鄰域點集DX0,TN;

4. if card(DX0,TN)

5. 將DX0,TN代入式(1)、式(2)，計算模型內(nèi)點ISDX0,TN，令MIS=DX0,TN;

6. while MIS≠ISDX0,TN;

7. 將MIS代入式(1)、式(2)，計算模型內(nèi)點ISMIS，令I(lǐng)SDX0,TN=ISMIS;

8. end while;

9. if card(ISDX0,TN)≥MPF;

10.i=i+1，hsi=ISDX0,TN;

11. end if;

12.X0=X0-ISDX0,TN;

13. end while;

14. 輸出假設(shè)模型集合HS={hs1,…,hsi,…,hshn}。

1.2.2 自上而下的分裂與最小殘差分組

自上而下的模型分裂其實就是將模型生成過程迭代用于生成的模型。即在原始的數(shù)據(jù)集中首先采用較大的閾值TN、TI獲得第一次的所生成的模型(模型內(nèi)點組成的集合)。然后分別在所生成的各個模型上采用較小的閾值TN、TI，進行更小粒度層次的模型生成。這個過程即可看作是模型的分裂生成，通過不斷地迭代細分，不斷地將交疊的模型分離開，將模型內(nèi)點與外點盡量分離開，獲得盡可能包含殘差小的內(nèi)點的集合，以便最終采用最小殘差一致的準(zhǔn)則進行模型內(nèi)點的劃分，即最小殘差分組。經(jīng)過反復(fù)的試驗，通常設(shè)定合適TN、TI閾值只需兩步的分裂過程。詳細的算法框架如圖2所示。

算法首先采用模型生成在原始數(shù)據(jù)集hn上獲得假設(shè)模型HS={hs1,hs2,…,hshn}，接下來在每個獲得的假設(shè)模型hsi上分別繼續(xù)使用模型生成算法，對于每個假設(shè)模型hsi都可以獲得生成的假設(shè)模型HSi=P{hsi,1,hsi,2,…,hsi,hni}，對于最初生成的假設(shè)模型HS，兩步分裂后最終獲得THS={hs1,hs2,…,hshn}。兩步模型生成過程中閾值(TN1,TI1)與(TN2,TI2)是不同的，通常(TN2,TI2)要比(TN1,TI1)小。最后最小殘差分組(圖3)利用各個模型計算的殘差向量對各個數(shù)據(jù)點進行最小殘差分組。最終獲得模型內(nèi)點按照模型大小降序排列{mλ(1),…,mλ(t)}。即可選擇所需要求得的前K個模型作為最終的結(jié)果。

圖1 算法流程Fig.1 The workflow of the whole algorithm

最小殘差分組首先計算出由兩步分裂獲得的各個模型對應(yīng)整個數(shù)據(jù)的殘差集合，方法如下

(5)

計算出所有模型的殘差之后即可獲得各個數(shù)據(jù)對應(yīng)不同模型的殘差值，統(tǒng)計如果數(shù)據(jù)對應(yīng)的最小殘差值對應(yīng)模型I，則將該數(shù)據(jù)標(biāo)記為模型I的內(nèi)點。依次如此對所有數(shù)據(jù)進行最小殘差值的分組，將整個數(shù)據(jù)集劃分成不同的內(nèi)點集合。最后按照內(nèi)點集合的大小降序排列，取出前K個模型作為所求模型輸出，K為所需求解模型個數(shù)。

算法的具體描述如算法2所示。

算法2 最小殘差分組{mλ(1),…,mλ(t)}=MRG(X,THS,TI,MPF)：

1. 輸入數(shù)據(jù)X0=X，初始化模型集合M=φ，RS=φ，k=0；

2. fori=0 to hn；

3. forj=0 to hni；

4. hst=hsi,j，將hst代入式(2)和式(4)，計算模型參數(shù)和殘差TmpR；

5.k=k+1，Rk=TmpR；

6. end for；

7. end for；

8. TN=k，RS={R1,…,Rm}；

10. 令m1=φ,…,mTN=φ；

11. fori=0 ton；

13. ifri,tem=∞，xi為外點；

14. elsemtem=mtem∪{xi}為外點；

15. end for；

16. 將集合{m1,…,mTN}按照大小降序排序，并刪除小于MPF的集合，獲得{mλ(1),…,mλ(t)}；

17. 輸出模型內(nèi)點集合M={mλ(1),…,mλ(t)}。

數(shù)據(jù)分布中，模型所屬的數(shù)據(jù)點分布，往往較噪聲的數(shù)據(jù)點分布要更為密集，通過查找數(shù)據(jù)點的最密集分布區(qū)域，進行采樣，可以明顯提高采樣質(zhì)量，進而提升生成的假設(shè)模型質(zhì)量。假設(shè)模型質(zhì)量的提升，不僅意味著對所需生成假設(shè)模型數(shù)量的減少，也意味著后期在正確的模型生成的過程難度降低。對于擬合結(jié)果以及擬合效率都有積極意義。而通過分裂合并的方法，降低了算法的時間復(fù)雜度。

1.3 圓柱模型探測

由于在DBSCAN算法中，已經(jīng)將點云數(shù)據(jù)分成較為細碎的區(qū)域，大多數(shù)區(qū)域內(nèi)的真實模型數(shù)目得到控制。在經(jīng)過多模型擬合后，當(dāng)模型與真實模型一致時，擬合出的模型數(shù)目保持較低。而當(dāng)預(yù)設(shè)的模型與真實模型一致時則可能出現(xiàn)意外。例如當(dāng)用平面，對圓弧面進行擬合，完整的圓弧面會被擬合成大量的平面。對此，本文將擬合出過多平面的子區(qū)域，設(shè)為問題區(qū)域，獲取點集X，進行二次判斷，以探測柱面目標(biāo)。

本文提出點云切片技術(shù)，對柱面模型進行擬合。由于柱面模型更為復(fù)雜，在柱面判斷和擬合過程中直接進行圓柱模型的擬合，往往會帶來較多的時間損耗。通過將點云進行切片，三維的圓柱模型擬合轉(zhuǎn)換為一系列的二維圓形擬合，可以改善這一效率。將興趣區(qū)域進行多層的分割，取薄層，投影到二維方向，進行橢圓檢測。當(dāng)圓柱垂直于投影方向，則可以擬合出多個同心圓，將一系列圓弧組合，圓心的連線方向即為圓柱的軸向，圓弧半徑即為圓柱半徑；而當(dāng)圓柱區(qū)域相對于投影方向有夾角，則會擬合出一系列橢圓，橢圓的短半軸即為圓柱的半徑，橢圓圓心的連線方向即為圓柱軸向，借此可以實現(xiàn)對圓柱的擬合。

通過在xy、yz、xz三個方向上的投影，則問題區(qū)域點云中的圓柱最終可以被擬合出來。

圖2 不同切割方法Fig.2 Different cut methods

2 試驗結(jié)果與分析

2.1 試驗數(shù)據(jù)

試驗選取了加利福尼亞大學(xué)伯克利分校的科里廳的部分走廊數(shù)據(jù)(http:∥www-video.eecs.berkeley.edu/research/indoor/)進行試驗。試驗數(shù)據(jù)如圖3所示,其中區(qū)域A、B、C3個區(qū)域的復(fù)雜性不斷增加。

區(qū)域A是一個I字形狀走廊，走廊一側(cè)分布有子空間，可能是由于臺階入口等導(dǎo)致。區(qū)域B是兩個走廊的連接處，包括兩個走廊的部分點云。其連接部分外側(cè)為直角，內(nèi)側(cè)為平面，且部分區(qū)域的掃描數(shù)據(jù)受到了開關(guān)門的影響。區(qū)域C分布更為復(fù)雜，不僅包括了兩段走廊，同時拐角區(qū)域的內(nèi)側(cè)為圓柱面，且由于圓柱面區(qū)域較大，平面區(qū)域與圓柱面區(qū)域在擬合過程中相互影響，需要加以考慮。

試驗數(shù)據(jù)如圖3所示。

圖3 試驗數(shù)據(jù)Fig.3 Test data

2.2 處理結(jié)果

圖4和5分別為區(qū)域A、B在MeanShift[40]、MultiRANSAC方法和本文所提出方法下的試驗結(jié)果。

可以看出，在區(qū)域A中，MeanShift和MultiRANSAC方法對于較小的面片區(qū)域都出現(xiàn)了丟失。其中MeanShift方法更為明顯，而MultiRANSAC方法主要是對屋頂裝飾面片的丟失，本文方法則較好地保留了這些面片。在區(qū)域B中，MeanShift無法實現(xiàn)對拐角的劃分，MultiRANSAC方法與本文方法試驗效果類似。

圖4 區(qū)域A 3種方法分割結(jié)果Fig.4 Experimental results on area A

圖5 區(qū)域B 3種方法分割結(jié)果Fig.5 Experimental results on area B

同時，對比3種算法的耗時，如表1所示。針對區(qū)域A和區(qū)域B，MeanShift方法由于是對點云數(shù)據(jù)進行的聚類分割，運算量較大，耗時最多。多模型擬合方法MultiRANSAC雖然是對Sequential RANSAC的改進，但是需要采樣計算模型參數(shù)，而且每次采樣獲得若干模型參數(shù)后，需要對模型之間進行相似性比較，其收斂過程較慢，時間消耗雖低于MeanShift方法，但是依然較高。本文提出的方法僅需要經(jīng)過兩次的采樣過程計算模型參數(shù)，統(tǒng)計模型內(nèi)點，最后只需要采用最小殘差進行分組，運算復(fù)雜度低，實際的計算速度也是較快的，時間消耗上明顯優(yōu)于另外兩個經(jīng)典方法。

表1 算法耗時

而當(dāng)在區(qū)域C進行分割時，容易發(fā)現(xiàn)MeanShift和MultiRANSAC算法與本文方法產(chǎn)生了更大的效果差距。受到圓柱區(qū)域的影響，MeanShift方法和MultiRANSAC方法只能夠?qū)γ黠@的兩個大直線區(qū)域進行擬合，而靠近圓柱一側(cè)的平面完全無法擬合。由于MeanShift算法依靠距離最小原則將原始點云分配到各計算模型中后，得到最終的分割結(jié)果。

依據(jù)距離準(zhǔn)則對數(shù)據(jù)進行判斷后，將原始點云分配到各個模型上，獲得最終的試驗結(jié)果如圖6 所示。

圖6 區(qū)域C 3種方法分割結(jié)果Fig.6 Experimental results on area C

表2中展示了3種算法分別在區(qū)域A、區(qū)域B和區(qū)域C上的分割正確率(正確的分割點個數(shù)除以總的點個數(shù))，其中本文方法在3個區(qū)域的分割正確率均高于其他兩種方法，其中由于MeanShift在分割過程中會或多或少的丟失掉一些分割區(qū)域，分割不完整，并且在相近的平面分割時會出現(xiàn)欠分割；而MultiRANSAC方法則相反，在很多區(qū)域存在過分割狀況，分割結(jié)果存在很多破碎的細小分割區(qū)域。該方法在較大區(qū)域上能夠?qū)崿F(xiàn)完整的分割，過分割的現(xiàn)象不嚴(yán)重，即是一些細小的區(qū)域也能實現(xiàn)較好分割。特別是針對曲面也能實現(xiàn)較完整的分割。

表2 區(qū)域分割正確率

3 總 結(jié)

本文根據(jù)點云的分布特點，使用基于密度的聚類對采樣結(jié)果進行預(yù)分割，再使用基于分裂合并的模型擬合方法，在預(yù)分割基礎(chǔ)上進行模型擬合。對問題區(qū)域采用切片方法進行判斷和柱面擬合，最終實現(xiàn)對點云的分割。相對于其他模型擬合方法，本文采用的分割方法在保證時間開銷較小的同時，自動判斷模型數(shù)目，且同時實現(xiàn)對柱面模型和平面模型的擬合。同時，應(yīng)對室內(nèi)點云分割中模型數(shù)量較多，偽噪聲點數(shù)目巨大的情況，本文的方法也能起到良好作用。三維點云分割經(jīng)過本文方法處理后，可以有效分割成簡單的圖元結(jié)構(gòu)，更加有利于實現(xiàn)復(fù)雜的三維場景構(gòu)象。本文所提出的點云分割方法能夠有效地將復(fù)雜場景三維點云分割成常規(guī)的簡單幾何圖元，相較于常規(guī)的點云分割算法本文方法提取圖元更為準(zhǔn)確完整，并且能夠?qū)崿F(xiàn)弧面等較為復(fù)雜圖元的較為完整的分割提取。相較于常規(guī)的點云分割方法，本文方法處理在時間效率上有較大提升，點云分割的正確率要高于常規(guī)的分割方法，較為適用于海量點云數(shù)據(jù)的分割處理。

參考文獻：

[1] 李德仁, 姚遠, 邵振峰. 智慧城市的概念、支撐技術(shù)及應(yīng)用[J]. 工程研究-跨學(xué)科視野中的工程, 2012, 4(4): 313-323.

LI Deren, YAO Yuan, SHAO Zhenfeng. The Concept, Supporting Technologies and Applications of Smart City[J]. Journal of Engineering Studies, 2012, 4(4): 313-323.

[2] SCHNABEL R, WAHL R, WESSEL R, et al. Shape Recognition in 3D Point-clouds[C]∥The 16-th International Conference in Central Europe on Computer Graphics, Visualization and Computer Vision’2008. Czech Republic: UNION Agency-Science Press, 2008: 65-72.

[3] LI Yangyan, WU Xiaokun, CHRYSATHOU Y, et al. GlobFit: Consistently Fitting Primitives by Discovering Global Relations[C]∥Proceeding of ACM SIGGRAPH. Vancouver, British Columbia, Canada: ACM, 2011: 52.

[4] MAHABADI R K, HANE C, POLLEFEYS M. Segment Based 3D Object Shape Priors[C]∥IEEE Computer Vision and Pattern Recognition. Boston, MA: IEEE, 2015: 2838-2846.

[5] 宮鈺嵩. RGBD數(shù)據(jù)驅(qū)動的室內(nèi)景物三維建模方法研究[D]. 南京: 南京大學(xué), 2015.

GONG Yusong. Research on 3D Modeling of Indoor Objects and Scenes Based on RGBD Data[D]. Nanjing: Nanjing University, 2015.

[6] DORNINGER P, PFEIFER N. A Comprehensive Automated 3D Approach for Building Extraction, Reconstruction, and Regularization from Airborne Laser Scanning Point Clouds[J]. Sensors, 2008, 8(11): 7323-7343.

[7] 秦彩杰, 管強. 三維點云數(shù)據(jù)分割研究現(xiàn)狀[J]. 宜賓學(xué)院學(xué)報, 2017, 17(6): 30-35.

QIN Caijie, GUAN Qiang. Research Status of 3D Point Cloud Data Segmentation[J]. Journal of Yibin University, 2017, 17(6): 30-35.

[8] BHANU B, LEE S, HO C C, et al. Range Data Processing: Representation of Surfaces by Edges[C]∥Proceedings of the Eighth International Conference on Pattern Recognition. Paris, France: [s.n.], 1986: 236-238.

[9] JIANG Xiaoyi, BUNKE H. Edge Detection in Range Images Based on Scan Line Approximation[J]. Computer Vision and Image Understanding, 1999, 73(2): 183-199.

[10] BESL P J, JAIN R C. Segmentation through Variable-order Surface Fitting[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2002, 10(2): 167-192.

[11] KOSTER K, SPANN M. MIR: An Approach to Robust Clustering-application to Range Image Segmentation[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2000, 22(5): 430-444.

[12] ROTTENSTEINER F. Automatic Generation of High-quality Building Models from Lidar Data[J]. IEEE Computer Graphics and Applications IEEE, 2003, 23(6): 42-50.

[14] WANG Zhe, LIU Hong, QIAN Yueliang, et al. Real-Time Plane Segmentation and Obstacle Detection of 3D Point Clouds for Indoor Scenes[M]∥FUSIELLO A, MURINO V, CUCCHIARA R. Computer Vision-ECCV 2012. Berlin, Heidelberg: Springer, 2012: 22-31.

[15] PAPON J, ABRAMOV A, SCHOELER M, et al. Voxel Cloud Connectivity Segmentation-Supervoxels for Point Clouds[C]∥IEEE Computer Vision and Pattern Recognition. Portland, OR: IEEE, 2013: 2027-2034.

[16] FILIN S. Surface Clustering from Airborne Laser Scanning Data[J].International Archives of Photogrammetry and Remote Sensing, 2002: XXXII, 3A：119-124.

[17] VOSSELMAN G, DIJKMAN S. 3D Building Model Reconstruction From Point Clouds and Ground Plans[J]. International Archives of Photogrammetry & Remote Sensing, 2001, 34(Part 3/W4): 37-43.

[18] ZHAN Qingming, YU Liang, LIANG Yubing. A Point Cloud Segmentation Method based on Vector Estimation and Color Clustering[C]∥IEEE 2nd International Conference on Information Science and Engineering. Hangzhou, China, China: IEEE, 2011: 3463-3466.

[19] ZHAN Qingming, YU Liang. Segmentation of LiDAR Point Cloud based on Similarity Measures in Multi-Dimension Euclidean Space[M]∥ZENG D. Advances in Computer Science and Engineering. Berlin, Heidelberg: Springer, 2012: 349-357.

[20] HOLZ D, HOLZER S, RUSU R B, et al. Real-Time Plane Segmentation Using RGB-D Cameras[M]∥R?FER T, MAYER N M, SAVAGE J, et al. RoboCup 2011: Robot Soccer World Cup XV. Berlin, Heidelberg: Springer, 2012: 306-317.

[21] SCHOENBERG J R, NATHAN A, CAMPBELL M. Segmentation of Dense Range Information in Complex Urban Scenes[C]∥IEEE/RSJ International Conference on Intelligent Robots and Systems. Taipei, Taiwan: IEEE, 2010: 2033-2038.

[22] SALLEM N K, DEVY M. Extended GrabCut for 3D and RGB-D Point Clouds[M]∥BLANC-TALON J, KASINSKI A, PHILIPS W, et al. Advanced Concepts for Intelligent Vision Systems. Cham: Springer, 2013: 354-365.

[23] GEETHA M, RAKENDU R. An Improved Method for Segmentation of Point Cloud Using Minimum Spanning Tree[C]∥IEEE International Conference on Communications and Signal Processing. Melmaruvathur, India: IEEE, 2014: 833-837.

[24] YANG Jingyu, GAN Ziqiao, LI Kun, et al. Graph-based Segmentation for RGB-D Data Using 3-D Geometry Enhanced Superpixels[J]. IEEE Transactions on Cybernetics, 2017, 45(5): 927-940.

[25] FISCHLER M A, BOLLES R C. Random Sample Consensus: A Paradigm for Model Fitting with Applications to Image Analysis and Automated Cartography[M]∥Readings in Computer Vision. [s.l.]: Elsevier, 1987: 726-740.

[26] TARSHA-KURDI F, LANDES T, GRUSSENMEYER P. Hough-Transform and Extended RANSAC Algorithms for Automatic Detection of 3D Building Roof Planes from LiDAR Data[C]∥Proceedings of the ISPRS Workshop on Laser Scanning, Espoo:ISPRS.2007, 36: 407-412.

[27] SCHNABEL R, WAHL R, KLEIN R. Efficient RANSAC for Point-Cloud Shape Detection[J]. Computer Graphics Forum, 2010, 26(2): 214-226.

[28] CHEN Dong, ZHANG Liqiang, LI J, et al. Urban Building Roof Segmentation From Airborne Lidar Point Clouds[J]. International Journal of Remote Sensing, 2012, 33(20): 6497-6515.

[29] GELFAND N, GUIBAS L J. Shape Segmentation Using Local Slippage Analysis[C]∥Proceedings of Eurographics/

ACM SIGGRAPH Symposium on Geometry Processing. Nice, France: ACM, 2004: 214-223.

[30] AWADALLAH M, ABBOTT L, GHANNAM S. Segmentation of Sparse Noisy Point Clouds Using Active Contour Models[C]∥IEEE International Conference on Image Processing. Paris, France: IEEE, 2015: 6061-6065.

[31] WANG Yanmin, SHI Hongbin. A Segmentation Method for Point Cloud Based on Local Sample and Statistic Inference[M]∥BIAN F, XIE Y. Geo-Informatics in Resource Management and Sustainable Ecosystem. Berlin, Heidelberg: Springer, 2015: 274-282.

[32] MA Teng, WU Zhuangzhi, FENG Lu, et al. Point Cloud Segmentation Through Spectral Clustering[C]∥IEEE 2nd International Conference on Information Science and Engineering. Hangzhou, China: IEEE, 2011: 1-4.

[33] NURUNNABI A, BELTON D, WEST G. Robust Segmentation in Laser Scanning 3D Point Cloud Data[C]∥IEEE International Conference on Digital Image Computing Techniques and Applications. Fremantle, WA, Australia: IEEE, 2013: 1-8.

[34] WOLF D, PRANKL J, VINCZE M. Fast Semantic Segmentation of 3D Point Clouds Using a Dense CRF with Learned Parameters[C]∥IEEE International Conference on Robotics and Automation. Seattle, WA: IEEE, 2015: 4867-4873.

[35] GREEN W R, GROBLER H. Normal Distribution Transform Graph-based Point Cloud Segmentation[C]∥Pattern Recognition Association of South Africa and Robotics and Mechatronics International Conference. Port Elizabeth, South Africa: IEEE, 2015: 54-59.

[37] KANAZAWA Y, KAWAKAMI H. Detection of Planar Regions with Uncalibrated Stereo Using Distributions of Feature Points[C]∥Proceedings of the British Machine Vision Conference. [s.l.]: BMVA Press, 2004: 247-256.

[38] ZULIANI M, KENNEY C S, MANJUNATH B S. The Multiransac Algorithm and Its Application to Detect Planar Homographies[C]∥IEEE International Conference on Image Processing. Genova, Italy: IEEE, 2005: Ⅲ-153.

[39] ESTER M, KRIEGEL H P, SANDER J, et al. A Density-based Algorithm for Discovering Clusters in Large Spatial Databases with Noise[C]∥Proceedings of 2nd International Conference on Knowledge Discovery and Data Mining. [s.l.]: AAAI Press, 1996: 226-231.

[40] COMANICIU D, MEER P. Mean Shift: A Robust Approach Toward Feature Space Analysis[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2002, 24(5): 603-619.