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

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

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

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

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

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

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

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

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

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

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

1 多結(jié)構(gòu)算法提取建筑物L(fēng)iDAR點(diǎn)云特征線

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

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

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

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

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

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

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

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

輸出 模型Θ

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

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

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

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

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

1.2 線段檢測

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

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

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

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

第3步:計(jì)算P中其余點(diǎn)Pj到Im的距離dj,存入矩陣dt中;

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

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

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

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

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

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

第2步:按照z值對這些點(diǎn)排序,并計(jì)算相鄰的兩點(diǎn)之間的距離;

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

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

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

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

否則畫出直線段;

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

取ζ=0.065,F′0=15,α=0.25,β=0.4,γ=15實(shí)驗(yàn)效果為最佳.

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

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

圖1(a)為RIGEL固定站式激光掃描儀掃描的建筑物立面墻點(diǎn)云數(shù)據(jù),總點(diǎn)數(shù)X=89 498,圖1(b)為采用切割最小二乘平面算法提取的特征點(diǎn),提取的特征點(diǎn)數(shù)為9 605個,圖1(c)為多結(jié)構(gòu)算法在有限時間lim=1時提取的標(biāo)準(zhǔn)特征線,為下面在不同時間限制內(nèi)的實(shí)驗(yàn)結(jié)果提供參考,模型個數(shù)上限T=2 000,點(diǎn)數(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),當(dāng)模型個數(shù)上限分別為20和100的情況下,RANSAC和MLESAC算法尋找最優(yōu)直線的能力均不及多結(jié)構(gòu)算法,而且隨著模型個數(shù)和時間的增多,多結(jié)構(gòu)算法檢測的特征線圖更趨于標(biāo)準(zhǔn)特征線圖.

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

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

圖4 標(biāo)準(zhǔn)特征點(diǎn)、特征線,有限時間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)點(diǎn)個數(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點(diǎn)云數(shù)據(jù)的特征線提取問題,在建立點(diǎn)云數(shù)據(jù)kd_tree的基礎(chǔ)上,引用文獻(xiàn)[15]中的方法提取立面墻邊界特征點(diǎn),然后提出基于多結(jié)構(gòu)魯棒估計(jì)的建筑物L(fēng)iDAR點(diǎn)云特征線提取算法.算法直接作用于建筑物點(diǎn)云數(shù)據(jù),在有限時間內(nèi),該算法能有效利用歷史模型信息,建立已采樣點(diǎn)的聯(lián)合概率,來對下一個采樣點(diǎn)進(jìn)行估計(jì),如此進(jìn)行指導(dǎo)采樣,不斷更新采樣模型使其向最優(yōu)的方向迭代.實(shí)驗(yàn)結(jié)果表明:本算法能根據(jù)模型殘差排序進(jìn)行指導(dǎo)采樣,有效增強(qiáng)了算法找出最優(yōu)直線模型的能力,提高了尋找最優(yōu)直線的速度和效率,尋找最優(yōu)直線所包含內(nèi)點(diǎn)的能力比其它兩種算法有優(yōu)勢.在處理特征點(diǎn)采樣問題時,其采樣性能優(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的點(diǎn)云特征線提取算法[J].計(jì)算機(jī)工程與科學(xué),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] 梁欣廉.機(jī)載激光雷達(dá)數(shù)據(jù)濾波與建筑三維模型重建[D].北京:中國測繪科學(xué)研究院,2005.

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

[15] 錢錦鋒,陳志楊,張三元,等.點(diǎn)云數(shù)據(jù)壓縮中的邊界特征檢測[J].中國圖像圖形學(xué)報(bào),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

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

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

江靜,蔡國榕,陳水利,等.基于多結(jié)構(gòu)估計(jì)的建筑物激光雷達(dá)點(diǎn)云特征線提取算法[J].廈門大學(xué)學(xué)報(bào):自然科學(xué)版, 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)