張建偉，權(quán)慶樂

(河南牧業(yè)經(jīng)濟(jì)學(xué)院 信息工程學(xué)院，河南 鄭州 450004)

0 引 言

近年來，隨著三維激光掃描技術(shù)的快速發(fā)展，高精度、數(shù)據(jù)海量的稠密點(diǎn)云已廣泛應(yīng)用于逆向工程[1]、文物修復(fù)[2]、3D打印[3]、自動駕駛[4]等領(lǐng)域。如何從點(diǎn)云中快速、準(zhǔn)確地提取出真實(shí)場景目標(biāo)信息，已逐漸成為國內(nèi)外眾多學(xué)者的研究熱點(diǎn)。平面結(jié)構(gòu)由于具有良好的幾何特性，廣泛地存在于室內(nèi)外各場景中。魯棒的平面結(jié)構(gòu)可為場景結(jié)構(gòu)建模[5]、機(jī)器人導(dǎo)航定位[6]等提供穩(wěn)定的特征信息。稠密點(diǎn)云由于其數(shù)據(jù)細(xì)節(jié)豐富，可以較為魯棒地反映真實(shí)地物信息，但由于其數(shù)據(jù)海量，如何高效準(zhǔn)確處理成為難題。因此稠密點(diǎn)云中快速準(zhǔn)確地提取平面結(jié)構(gòu)已成為計算機(jī)領(lǐng)域中重要的研究內(nèi)容[7-8]。

國內(nèi)外眾多學(xué)者針對平面提取已做了部分研究，而目前的平面分割方法可總體分為模型擬合類方法、深度學(xué)習(xí)類方法和區(qū)域生長類方法。

1)模型擬合類方法。主要包括隨機(jī)采樣一致性算法(RANSAC)[9-10]和霍夫變換算法(Hough transformation)[11]。RANSAC算法首先預(yù)先設(shè)定平面參數(shù)，依據(jù)點(diǎn)到平面的距離，在全局范圍內(nèi)將三維點(diǎn)分為外點(diǎn)與內(nèi)點(diǎn)，并將內(nèi)點(diǎn)數(shù)最多的點(diǎn)集作為最終平面分割結(jié)果。部分學(xué)者對RANSAC方法進(jìn)行改進(jìn)，SCHNABEL等提出采用八叉樹優(yōu)化RANSAC算法，以提高平面提取效率[12]。熊風(fēng)光等提出將K均值聚類與RANSAC相結(jié)合，以提高算法中的粗差點(diǎn)剔除率，在一定程度上提高了RANSAC算法的準(zhǔn)確度[13]。RAGURAM等采用附加法向矢量的方式提取數(shù)據(jù)中的三角面片。以上方法雖然有較好的抗噪性，但計算效率較低，同時未考慮空間連通性，易在稠密點(diǎn)云數(shù)據(jù)中產(chǎn)生偽平面[14]。

霍夫變換算法將原始空間中平面檢測問題轉(zhuǎn)化為尋找參數(shù)空間峰值問題。目前主要模型有球體、直線、柱體和平面等。田朋舉等提出一種基于2DHough變換和八叉樹相結(jié)合的方法，實(shí)現(xiàn)建筑平面的有效分割[15]。HULIK等采用矢量約束來提高Hough變換算法檢測平面的準(zhǔn)確度。但該類方法存在一定的平面誤識別現(xiàn)象[16]。

2)深度學(xué)習(xí)類方法。通過構(gòu)建卷積神經(jīng)網(wǎng)絡(luò)，對點(diǎn)云數(shù)據(jù)進(jìn)行語義信息分割。以PointNet[17]、PointNet++[18]、PointCNN[19]等深度神經(jīng)網(wǎng)絡(luò)為代表，可有效實(shí)現(xiàn)在真實(shí)場景下，提取點(diǎn)云數(shù)據(jù)中平面結(jié)構(gòu)。YU等針對稀疏點(diǎn)云特性，提出網(wǎng)絡(luò)模型，提高平面擬合精度，但在稠密點(diǎn)云數(shù)據(jù)中的計算效率仍有待提高[20]。該類方法需大量樣本清洗及模型訓(xùn)練等工作，當(dāng)處理大規(guī)模稠密點(diǎn)云時，與傳統(tǒng)方法相比并無顯著優(yōu)勢。

3)區(qū)域生長類方法[21-22]。通常是利用法線、曲率等幾何屬性，分析點(diǎn)云局部空間的鄰接關(guān)系，進(jìn)而實(shí)現(xiàn)平面點(diǎn)云的生長。薛婧雅等提出基于超體素與區(qū)域生長相結(jié)合的方式提高屋頂平面的分割精度[23]。王沖等采用動態(tài)分配權(quán)重的方法來提高法線解算精度，進(jìn)一步提高區(qū)域生長算法的準(zhǔn)確性[24]。FOTSING等采用ICP算法選取可靠的候選種子點(diǎn)，并在生長過程中采用體素表達(dá)點(diǎn)云，改善平面分割質(zhì)量[25]。ZHANG等提出一種基于2D和3D相互投影的區(qū)域生長方法，通過點(diǎn)云以及投影平面的幾何信息選取初始種子點(diǎn)，并通過區(qū)域生長條件判斷每個點(diǎn)的通視性，改善分割效果[26]。該類方法提取平面精度較高，但受到區(qū)域生長條件限制，平面結(jié)構(gòu)的完整度有待提高。同時該方法更關(guān)注于點(diǎn)云局部空間變化，對于平面結(jié)構(gòu)的整體考慮不足。

近年來一些學(xué)者也提出一些新方法，ZHU等將平面分解為多個平面段合并的結(jié)果，采用準(zhǔn)逆理論(quasi-a-contrario theory)利用誤警值(false alarms)評估每個平面段的分割效果[27]。WANG等用L0梯度最小化算法的區(qū)域生長以及圖分割(graph cut)提取物體表面[28]。FATEMEH等提出多平面算法用于區(qū)分多平面立面的結(jié)構(gòu)和非結(jié)構(gòu)元素，從統(tǒng)計上考慮點(diǎn)組相對于其鄰居的位置，以進(jìn)行識別的隔離多平面建筑的主立面[29]。

目前眾多研究方法多集中于某一類平面分割方法，并在此基礎(chǔ)上進(jìn)行優(yōu)化，而忽略各類方法之間的關(guān)聯(lián)性。模型擬合類方法具有嚴(yán)格的數(shù)學(xué)模型，但是忽略了局部空間結(jié)構(gòu)的連續(xù)性。區(qū)域生長類方法強(qiáng)調(diào)局部空間中連續(xù)，而未對數(shù)據(jù)進(jìn)行整體限制考慮，而過于嚴(yán)格的曲率閾值則會導(dǎo)致平面結(jié)構(gòu)的不完整。因此，綜合以上各類平面分割方法的特點(diǎn)，提出一種區(qū)域生長和RANSAC相結(jié)合的稠密點(diǎn)云平面分割方法。融合2類平面分割方法中數(shù)學(xué)模型以及局部空間約束的優(yōu)點(diǎn)，克服空間不連續(xù)及平面完整度不高的缺點(diǎn)。首先采用3種濾波方法實(shí)現(xiàn)點(diǎn)云初步的預(yù)處理，然后采用混合區(qū)域生長算法實(shí)現(xiàn)平面結(jié)構(gòu)的初分割，其次利用平面彎曲度約束對平面結(jié)構(gòu)的幾何狀態(tài)進(jìn)行判斷，最后采用RANSAC算法剔除異常平面的粗差點(diǎn)，從整體提高平面分割的準(zhǔn)確度。該方法綜合RANSAC和區(qū)域生長平面分割方法的優(yōu)點(diǎn)，在一定程度上提高平面分割的準(zhǔn)確度與完整度。

1 平面分割方法

1.1 技術(shù)路線

平面分割技術(shù)路線如圖1所示。首先對原始稠密點(diǎn)云進(jìn)行預(yù)處理，利用無效點(diǎn)剔除、統(tǒng)計濾波、體素濾波，顯著降低點(diǎn)云數(shù)據(jù)量，濾除大量離群噪聲點(diǎn)。然后提出一種混合區(qū)域生長分割方法實(shí)現(xiàn)場景中平面點(diǎn)云的初分割。其次以整個平面為基礎(chǔ)對平面進(jìn)行彎曲度約束分析，檢測出彎曲度異常平面。最后采用RANSAC算法剔除平面粗差點(diǎn)，提高平面分割準(zhǔn)確度和完整度。

圖1 稠密點(diǎn)云平面分割技術(shù)路線Fig.1 Pipeline of plane segmentation for dense point cloud

1.2 數(shù)據(jù)預(yù)處理

由于稠密點(diǎn)云數(shù)據(jù)海量，對其直接處理，嚴(yán)重影響處理效率，因此在平面分割前對其進(jìn)行預(yù)處理，為后續(xù)平面特征提取做準(zhǔn)備。

首先對稠密點(diǎn)云數(shù)據(jù)P進(jìn)行數(shù)據(jù)格式檢查，尋找數(shù)據(jù)中存在的“非法”格式，如點(diǎn)云中常見的“NAN”，并對其進(jìn)行剔除。然后采用統(tǒng)計濾波濾除噪聲點(diǎn)，其原理如公式(1)所示。最后采用體素濾波，在保證點(diǎn)云數(shù)據(jù)整體輪廓的前提下，降低點(diǎn)云數(shù)據(jù)量，其中體素濾波采用邊長為l(0.02 m)的三維網(wǎng)格。在預(yù)處理后得到點(diǎn)云數(shù)據(jù)PV。

(1)

1.3 點(diǎn)域區(qū)域生長

在預(yù)處理后，以三維點(diǎn)為基礎(chǔ)，結(jié)合局部鄰域空間分析，制定鄰域生長條件，進(jìn)行點(diǎn)域內(nèi)的區(qū)域生長。主要包括以下步驟。

1)采用Kd-tree在PV中為所有三維點(diǎn)確定鄰域點(diǎn)集Gi={pk}。

2)構(gòu)建鄰域協(xié)方差矩陣，采用特征值分解，計算其特征值λ1,λ2,λ3和對應(yīng)特征向量ξ1,ξ2,ξ3(λ1>λ2>λ3)，ξ3作為該點(diǎn)法線，計算曲率V如下

(2)

3)根據(jù)曲率值V，對所有點(diǎn)升序排序。按曲率順序，依次遍歷每一點(diǎn)，并初始化種子隊列seeds，計算每一個種子點(diǎn)與各自鄰域點(diǎn)法線夾角。

4)若種子點(diǎn)法線與種子點(diǎn)法線夾角小于閾值?(3°)，則將當(dāng)前鄰域點(diǎn)加入種子點(diǎn)seeds，若夾角大于?，繼續(xù)其他鄰域點(diǎn)計算。

5)若當(dāng)前種子隊列均判斷完畢，則輸出當(dāng)前平面點(diǎn)云plj。

6)遍歷PV所有點(diǎn)，直到所有點(diǎn)均已判斷完畢，見式(3)將PV分為剩余點(diǎn)云Ple、平面點(diǎn)云集{plj}。

(3)

式中n為平面數(shù)量。

1.4 面域區(qū)域生長

由于區(qū)域生長條件的限制，點(diǎn)域區(qū)域生長后的剩余點(diǎn)云Ple中仍包含部分屬于但未被歸類到相應(yīng)平面結(jié)構(gòu)的三維點(diǎn)。文中進(jìn)一步采用面域區(qū)域生長進(jìn)一步處理未分類的平面點(diǎn)。圖2為面域區(qū)域生長的示意，主要包括以下步驟。

1)平面篩選?，嵥榈钠矫纥c(diǎn)云，通常并非真正的實(shí)體結(jié)構(gòu)，或?qū)鼍敖Y(jié)構(gòu)的表達(dá)的意義不大。因此如圖3所示，對于提取的平面點(diǎn)云，通過外接矩形面積近似作為平面點(diǎn)云面積，并經(jīng)驗性地設(shè)置面積閾值s(0.02 m2)，剔除面積較小的平面，將其放回至剩余點(diǎn)云Ple中。

圖2 平面區(qū)域生長Fig.2 Planar region growing

圖3 外接矩形Fig.3 Bounding rectangle

2)建立鄰域結(jié)構(gòu)。以平面為基礎(chǔ)，再次采用KD-tree在剩余點(diǎn)云中，對平面點(diǎn)云建立鄰域結(jié)構(gòu)，并去除重復(fù)的鄰域點(diǎn)(圖2中黃色點(diǎn))。

3)平面生長。在每一個平面鄰域中，計算其到平面的距離，若小于距離閾值d1(0.03 m)，則將其歸類為當(dāng)前平面點(diǎn)云。

1.5 平面彎曲度約束

平面分割后，以每一平面點(diǎn)云為基礎(chǔ)，計算平面的整體平均曲率，將其作為整個平面的彎曲度評價指標(biāo)，主要包括以下步驟。

1)在公式(4)中，采用最小二乘法擬合平面方程，并計算整個平面點(diǎn)云重心點(diǎn)pc。

(4)

式中a1,…,a6為擬合的平面方程參數(shù)。

2)在公式(5)中，基于參數(shù)方程的一階、二階偏導(dǎo)、獲得pc處擬合曲面的第1基本量(E,F,G)和第2基本量(L,M,N)。

(5)

式中n為法向量。

3)在公式(6)中，結(jié)合參數(shù)方程計算出主曲率ρ1ρ2、平均曲率H。若重心點(diǎn)的平均曲率絕對值小于曲率閾值ε(0.4)，為正常平面，否則將其標(biāo)注為彎曲度異常平面。

(6)

1.6 RANSAC檢核平面

平面彎曲度約束分析后，平面點(diǎn)云分為正常平面和彎曲度異常平面。如圖4在異常平面中采用RANSAC擬合平面點(diǎn)云方程，并計算整體平面的點(diǎn)云的誤差，將點(diǎn)到平面距離大于閾值d2(0.02 m)的點(diǎn)，作為粗差值點(diǎn)，進(jìn)行剔除，提高平面分割準(zhǔn)確度。而彎曲度正常平面則無需進(jìn)行RANSAC檢測，可認(rèn)為其已基本滿足幾何一致性原則，直接保存為最后的平面分割點(diǎn)云。最后輸出所有平面點(diǎn)云。

圖4 RANSAC檢核平面Fig.4 Check plane with RANSAC

2 實(shí)驗結(jié)果與分析

2.1 實(shí)驗數(shù)據(jù)與環(huán)境

實(shí)驗環(huán)境為Intel Core i7-5500U CPU@2.40 GHz 2.39 GHz，8.0 GB RAM，采用Ubuntu 16.04系統(tǒng)，C++編程實(shí)現(xiàn)。實(shí)驗采用4組數(shù)據(jù)，其中前2組數(shù)據(jù)來自PARK學(xué)者公布的公寓及閣樓場景點(diǎn)云數(shù)據(jù)[30]，后2組數(shù)據(jù)來自蘇黎世大學(xué)(UZH)的可視化與多媒體實(shí)驗室提供的辦公室掃描數(shù)據(jù)(https：//www.ifi.uzh.ch/en/vmml/research/datasets.html)。

圖5是采用文中預(yù)處理方法后的點(diǎn)云結(jié)果，體素濾波采用邊長為0.02m的三維體素網(wǎng)格進(jìn)行體素化處理。從圖中預(yù)處理效果可以看出，在保持整體場景特征信息的前提下，點(diǎn)云數(shù)據(jù)量在一定程度上有所降低、大部分離群噪聲點(diǎn)得到有效剔除。

圖5 實(shí)驗數(shù)據(jù)Fig.5 Experimental data

2.2 平面分割對比實(shí)驗

在平面分割實(shí)驗中，選取傳統(tǒng)的區(qū)域生長和RANSAC方法作為對比實(shí)驗。各方法的分割效果如圖6所示，其中不同顏色表示不同平面點(diǎn)云。從圖中分割效果可以看出，RANSAC方法僅使用數(shù)學(xué)模型對點(diǎn)云進(jìn)行分割，未能保證平面點(diǎn)云的連通性，致使多處不鄰的平面段誤識別為同一個平面點(diǎn)云。區(qū)域生長方法的分割效果總體較為良好，但平面分割受到生長條件的限制，未能保證平面的完整度，位于平面邊緣附近的點(diǎn)云未能很好進(jìn)行歸類。目視效果上可見，文中方法可提取處場景中的大部分平面，同時平面之間的邊緣點(diǎn)云也得到良好歸類，平面結(jié)構(gòu)的區(qū)分度較高，在保證準(zhǔn)確度的同時也保證了平面結(jié)構(gòu)的完整度。

圖6 平面分割對比Fig.6 Comparison of plane segmentation

2.3 未分類點(diǎn)分布

為進(jìn)一步對比分析平面分割方法性能，如圖7提取出各方法分割后未歸類到具體平面的剩余點(diǎn)云。在剩余點(diǎn)分布方面，RANSAC方法由于僅采用空間數(shù)學(xué)模型，保留剩余點(diǎn)數(shù)量最少。其次是文中方法，最后是傳統(tǒng)區(qū)域生長方法。相比于區(qū)域生長方法，文中方法可以更好地處理平面邊緣點(diǎn)，減少剩余點(diǎn)數(shù)量，提高平面完整度。

圖7 未分類點(diǎn)分布Fig.7 Distribution of unclassified points

2.4 精度評估

進(jìn)一步量化分析分割方法的性能，采用式(7)和式(8)中準(zhǔn)確度(Corrrectness，Cr)、完整度(Completeness，Cm)[31]指標(biāo)評估各算法。實(shí)驗中采用CloudCompare軟件的標(biāo)記功能，勾選數(shù)據(jù)中的平面點(diǎn)并添加Label作為評估的真值。

(7)

(8)

式中TP為正確分割平面點(diǎn);FP為錯誤識別的平面點(diǎn);FN為漏檢的平面點(diǎn)。

表1記錄了實(shí)驗中3種分割方法在4個數(shù)據(jù)的分割結(jié)果的平面數(shù)量、剩余點(diǎn)數(shù)、準(zhǔn)確度和完整度。其中RANSAC方法由于空間幾何模型在全局范圍提取平面，可提取出場景中的絕大部分平面點(diǎn)。但由于實(shí)驗數(shù)據(jù)中存在大量的平面，致使RANSAC方法所提取的大部分平面點(diǎn)是空間非連續(xù)的，這與空間平面的幾何屬性相矛盾。區(qū)域生長方法和文中方法所分割平面均由空間連續(xù)三維點(diǎn)構(gòu)成，符合空間平面的幾何特性。同時相比于區(qū)域生長方法，文中方法在準(zhǔn)確度與完整度方面均所有提升，4個場景中準(zhǔn)確度均提升2%左右，均達(dá)到95%以上。完整度提高效果為：公寓場景提升約20%；閣樓場景提升約27%；辦公室1場景提升約12%；辦公室2場景提升約11%。文中方法更加魯棒地提取稠密點(diǎn)云中的平面結(jié)構(gòu)，并提高平面特征的完整度。為后續(xù)場景建模以及機(jī)器人定位導(dǎo)航提高更加魯棒的特征結(jié)構(gòu)。

表1 平面分割量化統(tǒng)計Table 1 Quantitative statistics of plane segmentation

3 結(jié) 論

1)利用點(diǎn)域內(nèi)區(qū)域生長和面域內(nèi)區(qū)域生長相結(jié)合，可以有效克服傳統(tǒng)區(qū)域生長在平面邊緣分割時的欠分割現(xiàn)象，平面分割的完整度提高約17%。

2)采用曲率值近似表達(dá)平面彎曲度，并對所分割的平面點(diǎn)云進(jìn)行檢核，可以有效檢測出異常彎曲的平面，有利于檢測平面中的粗差點(diǎn)。

3)利用RANSAC檢核平面，可以在保證平面分割的連通性的基礎(chǔ)上，進(jìn)一步提高平面分割的準(zhǔn)確度，在典型的室內(nèi)場景中，分割的準(zhǔn)確度可達(dá)到95%。

4)基于稠密點(diǎn)云數(shù)據(jù)的平面分割方法可為基于平面結(jié)構(gòu)的特征建模以及室內(nèi)機(jī)器人導(dǎo)航定位提供可靠的特征基礎(chǔ)。