基于多結(jié)構(gòu)估計的建筑物激光雷達點云特征線提取算法

江 靜,蔡國榕,陳水利,李紹滋,吳云東*

(1.集美大學理學院,福建廈門361021;2.廈門市無人機遙感應(yīng)用工程技術(shù)研究中心,福建廈門361021; 3.廈門大學信息科學與技術(shù)學院,福建省仿腦智能系統(tǒng)重點實驗室,福建廈門361005)

基于多結(jié)構(gòu)估計的建筑物激光雷達點云特征線提取算法

江 靜1,2,蔡國榕1,2,陳水利1,2,李紹滋3,吳云東1,2*

(1.集美大學理學院,福建廈門361021;2.廈門市無人機遙感應(yīng)用工程技術(shù)研究中心,福建廈門361021; 3.廈門大學信息科學與技術(shù)學院,福建省仿腦智能系統(tǒng)重點實驗室,福建廈門361005)

建筑物激光雷達(light detection and ranging,LiDAR)點云特征線對于多視角點云配準、建筑物對稱性檢測、建筑物三維重建等應(yīng)用具有十分重要的意義.由于LiDAR點云具有數(shù)據(jù)量龐大的特點,傳統(tǒng)的算法難以實現(xiàn)建筑物特征線的快速提取.針對這個問題,提出一種基于多結(jié)構(gòu)魯棒估計的建筑物特征線提取算法,該算法利用歷史模型信息進行條件采樣,并通過迭代搜索符合所有特征線性質(zhì)的模型.根據(jù)建筑物LiDAR數(shù)據(jù)的實驗結(jié)果表明,該方法與傳統(tǒng)的RANSAC(random sample consensus)、MLESAC(maximum likelihood estimation sample consensus)等算法相比,避免了無效、重復的特征線采樣過程,在相同時間內(nèi)可獲取更多的直線內(nèi)點,從而有效提高了建筑物特征線的提取效率.

激光雷達點云;特征線提取;多結(jié)構(gòu);相似函數(shù)

激光雷達(light detection and ranging,LiDAR)獲取的三維數(shù)據(jù)不僅具有精度好、密度高、處理成本低的優(yōu)點,且其數(shù)據(jù)獲取過程中不受光照變化、陰影和天氣因素的影響.因此,相關(guān)數(shù)據(jù)處理技術(shù)已逐漸成為遙感、測繪、計算機視覺等領(lǐng)域新的研究熱點.由于LiDAR掃描得到的點云數(shù)據(jù)量很大,為了加快處理速度,一般需要對點云進行抽稀或特征提取,以減少點云數(shù)量.其中,點云特征線提取是提高建筑物配準、重建效率的有效工具.

點云特征線是由掃描物體上尖銳特征,或高曲率部分采樣特征點組成的線段或曲線.目前,三維模型特征線提取技術(shù)已被廣泛用于增強建筑物點云的幾何特征[1]、對稱性檢測[2]、表面重建[3]、點云分割[4]、曲線匹配、模型簡化以及點云與圖像的配準等[5].點云數(shù)據(jù)特征線提取方法主要包括:1)基于三角網(wǎng)格在對曲率信息估計的基礎(chǔ)上提取特征線[6-7];2)最小生成樹法:Gumhold等[8]在對所有點構(gòu)建鄰域關(guān)系的黎曼圖基礎(chǔ)上,計算每個點的特征權(quán)重將點進行分類,最后由黎曼圖的最小生成樹來生成特征線.Pauly等[9]通過在多尺度上對特征進行分析拓展了此方法;3)李寶等[10]用RANSAC提取特征點,然后用主成分分析的方法計算線段參數(shù)來提取特征線;4)折線生長算法:在提取已有特征點基礎(chǔ)上,由用戶輸入一個半徑值來控制特征折線的精度,然后用主成分分析方法完成特征折線的生成.這些方法在處理噪聲數(shù)據(jù)和缺失數(shù)據(jù)方面存在局限性,特別是處理LiDAR數(shù)據(jù)的時間代價偏高,難以滿足特征線快速提取的需求.

目前在LiDAR數(shù)據(jù)上提取建筑物特征線一般是將LiDAR點云數(shù)據(jù)轉(zhuǎn)化為深度圖像,再利用圖像的分割算法及邊界線提取算法提取特征線[11-12].梁欣廉[13]使用分裂的最小均方差線段逼近法,從離散的LiDAR數(shù)據(jù)中提取建筑物特征線.尤紅建等[14]用方位角分離出靠近建筑物輪廓邊緣上的激光點,對分離出的激光點進行規(guī)則化處理,同時依據(jù)邊緣點連線方向角度的變化進行邊界點的分組,計算建筑物的主方向,然后對邊界點進行邊緣規(guī)則化,最后得到建筑物最外側(cè)邊緣的輪廓.分析目前基于LiDAR點云數(shù)據(jù)提取建筑物特征線的研究工作,主要集中在處理凸多邊形數(shù)據(jù),針對凹多邊形輪廓特征線的處理方法有限且效果不理想.現(xiàn)有方法需要用到迭代逼近,本身運算量較大,又因為LiDAR數(shù)據(jù)具有海量的特點,因此處理效率有待提高.

針對以上算法存在的效率問題,本文首先根據(jù)文獻[15]方法,提取建筑物LiDAR點云數(shù)據(jù)的特征點.在此基礎(chǔ)上,計算特征點對假設(shè)模型的殘差,利用殘差排序構(gòu)造兩點屬于同一模型的相似函數(shù).采樣過程中利用相似函數(shù)構(gòu)造的條件概率進行采樣,使采樣朝著同一直線上的點進行.當采樣到一定模型集后放入原模型集重新計算殘差,更新模型集使之向最優(yōu)的模型方向迭代.算法利用相似性函數(shù)指導采樣,降低了RANSAC、MLESAC等隨機采樣在LiDAR海量數(shù)據(jù)中重復計算的風險,提高了采樣速度.通過點對模型的殘差排序情況來確定點屬于某個模型的可能,有效減少了LiDAR數(shù)據(jù)噪聲點和非均勻點對模型產(chǎn)生的影響.與以往算法借助三角網(wǎng)格和圖像提取點云特征線的主要區(qū)別在于,本文直接對LiDAR掃描的數(shù)據(jù)進行處理,降低了算法的復雜度,有效提高了處理效率.實驗結(jié)果表明由Chin等[16]提出的多結(jié)構(gòu)模型快速生成算法在采樣速度、局內(nèi)點總數(shù)以及魯棒性方面比隨機采樣RANSAC[17]、MLESAC[18-19]算法有較大提高.

1 多結(jié)構(gòu)算法提取建筑物LiDAR點云特征線

本文利用多結(jié)構(gòu)算法直接對LiDAR建筑物點云數(shù)據(jù)進行處理,通過點對模型的殘差構(gòu)造相似函數(shù)來指導模型采樣,降低了噪聲和數(shù)據(jù)的不均勻因素對模型產(chǎn)生的影響.指導性采樣的過程為海量LiDAR數(shù)據(jù)節(jié)省了采樣時間,增加了模型獲得內(nèi)點數(shù)目,提高了模型提取的準確率和速度.

1.1 多結(jié)構(gòu)模型算法的基本原理

多結(jié)構(gòu)模型快速生成算法是一種魯棒性估計方法,該算法通過計算數(shù)據(jù)點對假設(shè)模型的殘差,對殘差進行排序,然后構(gòu)造數(shù)據(jù)點之間的相似函數(shù),用來度量數(shù)據(jù)點之間屬于同一結(jié)構(gòu)的相似程度,以此來指導采樣,當產(chǎn)生一定數(shù)量的新模型后,將其融入原模型集,再利用條件概率有指導地采樣,使其向最優(yōu)的模型方向迭代.

在有序殘差的基礎(chǔ)上,定義xi和xj的相似函數(shù):表示xi和xj殘差升序排序后前h個模型中相同模型的個數(shù).由于的取值范圍為[0,1]且是對稱的,對于所有的i,有f(xi,xi)=1.h為點按照模型殘差值排序的前n(n=1,2,…,M)個模型,在文獻[16]中知h的取值范圍為1≤h≤M.

利用殘差排序和相似函數(shù),在規(guī)定時間范圍內(nèi)來指導模型取樣,主要采用條件概率的方法選取特征點,構(gòu)造優(yōu)化模型.隨機選擇第一個數(shù)據(jù)點s1,在此基礎(chǔ)上,通過條件概率

選擇第2個數(shù)據(jù)點s2,a1是歸一化因子,a1=保證P1(i)為有效的離散條件概率分布,則s2的選取概率依賴于P1,即s2～P1.同理,假設(shè)選擇每個點都是獨立的,根據(jù)貝葉斯原則,后續(xù)點的選取依賴于與被選中點之間的相似度.即

其中ak也是歸一化因子,則第s+1個數(shù)據(jù)點的選擇概率依賴于Pk,即sk+1～Pk.

輸入 點云數(shù)據(jù)集X,需要的總模型個數(shù)T,最小子集p,改變窗口大小的模型個數(shù)b,采樣模型集Θ1,控制相似函數(shù)大小的h,殘差閾值ζ

輸出 模型Θ

第1步:如果模型個數(shù)M≤b,則隨機取樣p個數(shù)據(jù)點并存儲在矩陣S中;

第2步:隨機采樣模型,使得模型個數(shù)M＞b,放入模型集Θ1中,點集X中隨機選擇第一個點s1,存儲矩陣S中;

第3步:根據(jù)采樣的第1個點s1,利用a(i),h構(gòu)造公式P1(i),來采樣模型需要的第2個點s2,并放入矩陣S中,利用已采樣的點構(gòu)造概率矩陣Pk(i)來采樣下一個點,直到采樣p個點為止.本文中直線模型只需采樣兩個點;

第4步:將第3步采樣得到的由p個點構(gòu)成的模型放入模型集Θ1中.循環(huán)第2步到第4步直到采樣到T個模型;

第5步:如果模型個數(shù)M≥b并且mod(M,b)= 0,將采樣的模型Θ1加入到模型Θ中,重新計算點對所有模型的殘差,并進行排序得到a(i).統(tǒng)計每個模型對數(shù)據(jù)點的殘差值小于閾值ζ的個數(shù),個數(shù)最多的模型為最優(yōu)的直線模型Θ,改變h的大小,h=[0.1M].

1.2 線段檢測

多結(jié)構(gòu)模型算法用于檢測直線模型,直線生成算法如下:

輸入 三維點云數(shù)據(jù)點集P={pi},模型個數(shù)M,距離閾值,得分閾值

輸出 三維直線Imo的參數(shù)a,b,c,x0,y0,z0

第1步:在P中隨機選擇一點Pm1,根據(jù)多結(jié)構(gòu)中條件概率選擇另外一點Pm2;

第3步:計算P中其余點Pj到Im的距離dj,存入矩陣dt中;

第4步:重復步驟1～3共M次,選擇出M個模型;

第5步:統(tǒng)計P中其余點Pj到每個模型的距離dj小于閾值ζ的點作為直線Im的內(nèi)點,并統(tǒng)計它的個數(shù),作為Im的得分FIm;

第8步:重復步驟1～7直到無法從剩余點中選擇一個得分至少為閾值F′0的直線.

檢測出直線后,需要將位于同一條直線上不同的目標線段找出來,實現(xiàn)窗戶邊緣特征,算法過程如下:

輸入 通過算法1檢測出的屬于同一直線上的點集Q={qi},距離閾值α和點數(shù)閾值γ

第1步:如果輸入點集Q={qi}的max Xˉmin X絕對值小于閾值α,則輸入的點屬于豎直直線上的點;

第2步:按照z值對這些點排序,并計算相鄰的兩點之間的距離;

第3步:如果相鄰兩點之間的距離小于閾值β,則保存這相鄰的兩點到矩陣inx,繼續(xù)下一個兩點之間距離的檢測;

如果相鄰兩點之間距離大于閾值β,檢測矩陣inx是否為空,如果inx為空或者inx點的數(shù)量小于閾值γ,則將inx中的點的索引全設(shè)為0,繼續(xù)步驟3,檢測下面的點;

否則畫出檢測出來的線段,將inx中的點的索引重新設(shè)為0,繼續(xù)步驟3;

第4步:檢測剩下的點,如果inx是空或者inx中點的索引小于閾值γ,則返回;

否則畫出直線段;

水平方向檢測max Zˉmin Z的絕對值是否小于閾值α,其他步驟和豎直方向一樣.

取ζ=0.065,F′0=15,α=0.25,β=0.4,γ=15實驗效果為最佳.

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

本文采用vs2010平臺對LiDAR點云數(shù)據(jù)構(gòu)建kd_tree,提取特征點,然后利用MATLAB 2011a作為仿真平臺,對本文提出的算法進行實現(xiàn).實驗中改變窗口大小的模型個數(shù)b=10.

圖1(a)為RIGEL固定站式激光掃描儀掃描的建筑物立面墻點云數(shù)據(jù),總點數(shù)X=89 498,圖1(b)為采用切割最小二乘平面算法提取的特征點,提取的特征點數(shù)為9 605個,圖1(c)為多結(jié)構(gòu)算法在有限時間lim=1時提取的標準特征線,為下面在不同時間限制內(nèi)的實驗結(jié)果提供參考,模型個數(shù)上限T=2 000,點數(shù)閾值γ=15,圖2 lim=0.5,T=20,γ=100;圖3 lim =0.6,T=100,γ=15.圖2和3分別為不同限制時間內(nèi)RANSAC、MLESAC和多結(jié)構(gòu)算法提取的特征線圖,可以看出在有限時間內(nèi),當模型個數(shù)上限分別為20和100的情況下,RANSAC和MLESAC算法尋找最優(yōu)直線的能力均不及多結(jié)構(gòu)算法,而且隨著模型個數(shù)和時間的增多,多結(jié)構(gòu)算法檢測的特征線圖更趨于標準特征線圖.

圖4中(a)是與圖1(a)在不同站點下掃描的點云數(shù)據(jù).圖4(a)中總點數(shù)X=3 215,圖4(b)中用切割最小二乘平面算法提取的特征點,個數(shù)為945個,圖4 (c)為用多結(jié)構(gòu)算法提取的標準特征線圖,T=200, lim=2,γ=15.圖5和6中時間限制分別為0.006和0.01,模型上限T均為10,γ=15.圖5和圖6為在點數(shù)較少情況下所做實驗,可以看出,相同較短時間下,多結(jié)構(gòu)算法能有效利用歷史模型信息提取較多特征線,且提取的特征線較完整,而RANSAC和MLESAC算法提取的特征線較破碎.

圖1 標準特征點、特征線,有限時間lim=1Fig.1 Standard feature points,feature lines with limit time of 1

圖2 不同算法下提取的特征線對比,有限時間lim=0.5Fig.2 Feature lines comparison of different algorithms with limit time of 0.5

圖3 不同算法下提取的特征線對比,有限時間lim=0.6Fig.3 Feature lines comparison of different algorithms with limit time of 0.6

圖7 為最優(yōu)直線所包含的內(nèi)點個數(shù).從圖中可以看出檢測同一條直線,多結(jié)構(gòu)算法包含內(nèi)點能力優(yōu)于其他2種算法.隨著提取直線個數(shù)的增多,直線包含內(nèi)點個數(shù)逐漸減少.表1為多結(jié)構(gòu)算法和其他2種算法實驗參數(shù)的對比,由于多結(jié)構(gòu)算法利用殘差排序構(gòu)造兩點之間相似函數(shù),利用相似函數(shù)建立已采樣點的聯(lián)合概率模型,估計下一個采樣點的概率,不斷更新采樣模型使其向最優(yōu)的模型方向迭代.在相同時間內(nèi)多結(jié)構(gòu)算法利用指導采樣比RANSAC和MLESAC等隨機采樣算法提取的特征線條數(shù)更多,更接近標準特征線,迭代次數(shù)更少,尋找到最優(yōu)直線所用時間更短.

圖4 標準特征點、特征線,有限時間lim=2Fig.4 Standard feature points,feature lines with limit time of 2

圖5 不同算法下提取的特征線對比,有限時間lim=0.006Fig.5 Feature lines comparison of different algorithms with limit time of 0.006

圖6 不同算法下提取的特征線對比,有限時間lim=0.01Fig.6 Feature lines comparison of different algorithms with limit time of 0.01

圖7 最優(yōu)模型內(nèi)點個數(shù)Fig.7 Number of optimal model inlier

表1 兩算法參數(shù)對比,其中T=10,γ=5Tab.1 Comparison parameter of two algorithm,T=10,γ=5

3 結(jié) 論

本文針對建筑物立面墻LiDAR點云數(shù)據(jù)的特征線提取問題,在建立點云數(shù)據(jù)kd_tree的基礎(chǔ)上,引用文獻[15]中的方法提取立面墻邊界特征點,然后提出基于多結(jié)構(gòu)魯棒估計的建筑物LiDAR點云特征線提取算法.算法直接作用于建筑物點云數(shù)據(jù),在有限時間內(nèi),該算法能有效利用歷史模型信息,建立已采樣點的聯(lián)合概率,來對下一個采樣點進行估計,如此進行指導采樣,不斷更新采樣模型使其向最優(yōu)的方向迭代.實驗結(jié)果表明:本算法能根據(jù)模型殘差排序進行指導采樣,有效增強了算法找出最優(yōu)直線模型的能力,提高了尋找最優(yōu)直線的速度和效率,尋找最優(yōu)直線所包含內(nèi)點的能力比其它兩種算法有優(yōu)勢.在處理特征點采樣問題時,其采樣性能優(yōu)于RANSAC、MLESAC算法.

[1] Merigot Q,Qvsjanikov M,Guibas L.Voronoi-based curvature and feature estimation from point cloud[J].IEEE Transactions on Visualization and Computer Graphics, 2011,17(6):743-756.

[2] Bokeloh M,Berner A,Wand M,et al.Symmetry detection using feature lines[J].Computer Graphics Forum,2009, 28(2):697-706.

[3] Xue T,Liu J,Tang X.Example-based 3D object reconstruction from line drawings[C]∥Computer Vision and Pattern Recognition.Providence,RI:IEEE,2012: 302-309.

[4] Weber C,Hahmann S,Hagen H.Sharp feature detection in point clouds[C]∥Shape modeling international conference(SMI).Aix-en-Provence:IEEE,2010:175-186.

[5] Liu L,Ioannis S.A systematic approach for 2D-image to 3D-range registration in urban environments[J].Computer Vision and Image Understanding,2012,116(1):25-37.

[6] Hilderandt K,Polthier K,Wardetzky M.Smooth feature lines on surface meshes[C]∥Symposium on Geometry Processing.Switzerland:ACM Press,2005:85-90.

[7] Ohtake Y,Belyaev A,Seidel H P.Ridge-valley lines on meshes via implicit surface fitting[J].SIGGRAPH,2004, 23(3):609-612.

[8] Gumhold S,Wang X,Mcleod R.Feature extraction from point clouds[C]∥Proceedings of the 10th International Meshing Roundtable.Berlin:Springer Press,2001: 293-305.

[9] Pauly M,Gross M.Multi-scale feature extraction on point-sampled surfaces[J].Computer Graphics Forum, 2003,22(3):281-289.

[10] 李寶,程志全,黨崗,等.一種基于RANSAC的點云特征線提取算法[J].計算機工程與科學,2013,35(2): 147-153.

[11] Li S K,Xue Y Q.Efficiently 3D remote sensing integration system[M].Beijing:Science Press,2000.

[12] Brian B J,Hanson A R,Riseman E M.Extracting straight lines[J].IEEE Pattern Analysis and Machine Intelligence,1986,8(4):425-455.

[13] 梁欣廉.機載激光雷達數(shù)據(jù)濾波與建筑三維模型重建[D].北京:中國測繪科學研究院,2005.

[14] 尤紅建,李樹凱.基于稀疏激光采樣點的建筑物提取[J].中國科學院研究生院學報,2001,18(2):154-158.

[15] 錢錦鋒,陳志楊,張三元,等.點云數(shù)據(jù)壓縮中的邊界特征檢測[J].中國圖像圖形學報,2005,10(2):164-169.

[16] Chin T,Jin Y,David S.Accelerated hypothesis generation for multi-structure data via preference analysis[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence,2011,34(4):625-638.

[17] Martin A,Robert C.A paradigm for model fitting withapplications to image analysis and automated cartography[J].Comm of the ACM,1981,24(6):381-395.

[18] Torr P H S,Zisserman A.MLESAC:a new robust estimator with application to estimating image geometry [J].Computer Vision and Image Understanding,2000, 78(1):138-156.

[19] Rastgar H,Liang Z,Demin W,et al.Validation of correspondences in MLESAC robust estimation[C]∥IEEE International Conference Computer Vision and Pattern Recognition.Tampa,FL:IEEE,2008:1-4.

Extract Feature Lines from Building LiDAR Point Cloud Based on Multi-structure Estimators

JIANG Jing1,2,CAI Guo-rong1,2,CHEN Shui-li1,2,LI Shao-zi3,WU Yun-dong1,2*
(1.College of Science,Jimei University,Xiamen 361021,China;2.Engineering Technology Research Center of UAV Remote Sensing Application,Xiamen 361021,China;3.Fujian Key Laboratory of the Brain-like Intelligent Systems,School of Information Science and Engineering,Xiamen University,Xiamen 361005,China)

:Feature lines extracted from building LiDAR(Light Detection and Ranging)point cloud data are of great significance in multiple views registration,building symmetry detection,3D surface reconstruction,among others.Since the LiDAR data are generally associated with a huge amounts of 3D points,traditional algorithms suffer from the time complexity of rapidly extracting feature lines from building point cloud.In order to solve this problem,we present a feature lines extracted algorithm based on multi-structure robust estimation.In the proposed method,historical models generated by random strategy have been used for conditional sampling new models.Consequently,the searching process aims at extracting all feature lines from the model set.In the section of experiments, the multi-structure algorithm has been compared with the RANSAC(random sample consensus)and MLESAC(maximum likelihood estimation sample consensus).Results acquired from our LiDAR dataset indicate that the proposed method improves the efficiency of building feature lines extraction,since the multi-structure algorithm avoids many invalid and repeated sampling processes.Therefore, we can generate more feature lines at the same time.

LiDAR point clouds;feature lines extraction;multi-structure;similar function

O 29;P 231

A

0438-0479(2015)03-0390-07

10.6043/j.issn.0438-0479.2015.03.018

2014-07-31 錄用日期:2014-10-27

國家自然科學基金(61103052);國家科技支撐計劃(201309110001);國家高技術(shù)研究發(fā)展計劃(863計劃)(2012AA12A208-06);福建省產(chǎn)學重大科技項目(2011H6020);福建省自然科學基金(2012J01013,2013J01245);福建省教育廳專項課題(JK2012025);廈門市科技計劃項目(3502Z20110010)

*通信作者:yundongwu@jmu.edu.cn

江靜,蔡國榕,陳水利,等.基于多結(jié)構(gòu)估計的建筑物激光雷達點云特征線提取算法[J].廈門大學學報:自然科學版, 2015,54(3):390-396.

:Jiang Jing,Cai Guorong,Chen Shuili,et al.Extract feature lines from building LiDAR point cloud based on multi-structure estimator[J].Journal of Xiamen University:Natural Science,2015,54(3):390-396.(in Chinese)