【正文】 能適應(yīng)所有的情況，這也使得測(cè)量儀器的不斷推陳出新。由于這些原因，必須做出一套能全天候主動(dòng)去獲取高精度空間數(shù)據(jù)的系統(tǒng)，LiDAR測(cè)量系統(tǒng)便出現(xiàn)了。展望未來，LiDAR系統(tǒng)必定會(huì)成為獲取三維空間數(shù)據(jù)的重要設(shè)備，它會(huì)同其他數(shù)據(jù)獲取技術(shù)，例如全球衛(wèi)星定位、控制測(cè)量、近景攝影測(cè)量等技術(shù)一起促進(jìn)空間信息技術(shù)向前發(fā)展。隨著應(yīng)用需求的發(fā)展以及研究的深入，索引的維度也開始從傳統(tǒng)的一維、二維索引向多維發(fā)展，出現(xiàn)了一些三維空間數(shù)據(jù)庫的索引方法，比如R樹索引、KD樹索引、四叉樹索引等，索引的空間對(duì)象也由“點(diǎn)、線、面”發(fā)展到“點(diǎn)、線、面、體”。下表是前人對(duì)常用的索引方式研究的基礎(chǔ)上得出的綜合性能表Error! Reference source not found.：表1 常用索引方式基礎(chǔ)性能表索引名稱劃分區(qū)域方法適合對(duì)象優(yōu)點(diǎn)缺點(diǎn)KD樹根據(jù)點(diǎn)二分點(diǎn)對(duì)象查詢效率高，存儲(chǔ)要求低對(duì)于海量數(shù)據(jù)管理困難，主要對(duì)點(diǎn)對(duì)象索引八叉樹對(duì)空間八分空間對(duì)象算法簡單，比較適應(yīng)空間對(duì)象深度較大，可能對(duì)各種操作有不利影響R樹矩形或其他不規(guī)則多邊形空間對(duì)象比較適應(yīng)空間對(duì)象算法復(fù)雜，區(qū)域重疊KDB樹根據(jù)點(diǎn)二分點(diǎn)對(duì)象查詢效率高，動(dòng)態(tài)索引刪除困難，主要用于點(diǎn)對(duì)象索引BSP樹對(duì)空間二分空間對(duì)象容易控制切割面以及樹的深度，檢索速度也快算法較為復(fù)雜，要預(yù)先生成，動(dòng)態(tài)維護(hù)性能較差規(guī)則網(wǎng)格等分面域或不等分空間對(duì)象查詢效率高，算法簡單，跟編碼相結(jié)合分辨率單一，難以維護(hù)，數(shù)據(jù)冗余實(shí)際上，現(xiàn)在出現(xiàn)的多種索引方式都是針對(duì)于不斷出現(xiàn)的新需求而出現(xiàn)的，對(duì)于在實(shí)際應(yīng)用中選擇哪種索引方式作為空間數(shù)據(jù)庫的索引，要從實(shí)際出發(fā)。主要的研究內(nèi)容有：1）點(diǎn)云數(shù)據(jù)獲取的理論研究，對(duì)機(jī)載LiDAR和車載LiDAR的系統(tǒng)組成、原理和特點(diǎn)進(jìn)行分析；2）研究基于KD樹和八叉樹的LiDAR點(diǎn)云數(shù)據(jù)的組織與管理，通過C++語言進(jìn)行實(shí)現(xiàn)，完成了算法測(cè)試，規(guī)律分析和對(duì)比。此章節(jié)介紹了本文的研究背景和空間數(shù)據(jù)索引在國內(nèi)外的發(fā)展現(xiàn)狀，分析了在現(xiàn)在點(diǎn)云數(shù)據(jù)組織管理中存在的問題，提出了本文所研究的內(nèi)容。此章節(jié)主要介紹了KD樹索引的概念原理、建立算法以及查詢算法，進(jìn)行算法測(cè)試得出結(jié)果及分析。此章節(jié)主要介紹了兩種索引混合的方式原理及建立方式，進(jìn)行算法測(cè)試，得出了結(jié)果和對(duì)比分析第六章，結(jié)論與展望。圖1 機(jī)載LiDAR系統(tǒng)的組成單元[2]（1）對(duì)地定位原理假設(shè)在空間有一個(gè)向量，它的模為R，方向?yàn)椋ǎ?，如果可以測(cè)出向量R的起點(diǎn)的坐標(biāo)（），便可以通過計(jì)算得出向量R的另一端點(diǎn)P的坐標(biāo)（X，Y，Z）。圖2 對(duì)地定位示意圖線掃描方式是一種最常用的掃描方式，以線掃描方式為例子，對(duì)于地面上的點(diǎn)P，如果它和掃描儀之間距離為S，掃描儀的位置坐標(biāo)為（），P點(diǎn)與掃描中心線的角度大小為，地面點(diǎn)P的坐標(biāo)就可以通過以下方式計(jì)算出來。由于光在空氣中的傳播速度一定，通過測(cè)定光波在發(fā)射點(diǎn)到被測(cè)目標(biāo)之間來回傳播的時(shí)間能夠求出距離值，這是激光測(cè)距的基本原理。相位法是利用連續(xù)波信號(hào)的相位差，間接地去確定傳播的時(shí)間；脈沖法是對(duì)傳播時(shí)間直接量測(cè)[10]。處理不規(guī)則的回波信號(hào)，由此估計(jì)出目標(biāo)測(cè)距的可能產(chǎn)生的延時(shí)，給出回波脈沖信號(hào)，目標(biāo)回波的延時(shí)就是脈沖信號(hào)的延時(shí)；第四步，測(cè)量時(shí)間延遲?，F(xiàn)在常用的有三種掃描方式：圓錐掃描、線掃描、纖維光學(xué)陣列掃描。掃描鏡的鏡面傾斜出一個(gè)傾角，它的旋轉(zhuǎn)軸和發(fā)射裝置的激光束之間成45度夾角?！癦”字模型是將掃描儀擺動(dòng)來實(shí)現(xiàn)的，一定程度上彌補(bǔ)了掃描線之間距離大的問題。第二，機(jī)載LiDAR的激光脈沖信號(hào)的穿透力非常強(qiáng)，能部分的穿透植被，能夠快速地獲得精度較高和空間分辨率較高的森林或山區(qū)的數(shù)字地面模型。地面LiDAR技術(shù)是通過激光進(jìn)行高速的、實(shí)時(shí)的、自動(dòng)的獲取區(qū)域目標(biāo)表面的三維坐標(biāo)的測(cè)量技術(shù)，是一種能夠獲取大面積高密度的三維空間信息的非接觸式主動(dòng)測(cè)量技術(shù)。附件設(shè)備還有腳架，配準(zhǔn)靶標(biāo)等等。即獲得的原始數(shù)據(jù)有：兩個(gè)反射鏡的角度值，在下圖中為水平角值和垂直角值；通過計(jì)算得到的儀器到掃描點(diǎn)之間的斜距S，掃描點(diǎn)反射強(qiáng)度。 (23)地面LiDAR技術(shù)跟全站儀測(cè)量技術(shù)的定位原理是相同的，都是將儀器自身中心作為坐標(biāo)原點(diǎn)，測(cè)出距離值和角度值，進(jìn)行解算得出目標(biāo)的三維坐標(biāo)。將激光掃描技術(shù)用于目標(biāo)空間數(shù)據(jù)信息采集，能夠及時(shí)地測(cè)定出目標(biāo)表面的三維信息，所以能夠在自動(dòng)監(jiān)控行業(yè)內(nèi)應(yīng)用。（4）實(shí)時(shí)、動(dòng)態(tài)與主動(dòng)性：地面LiDAR系統(tǒng)是一個(gè)主動(dòng)式的掃描系統(tǒng)，利用的是探測(cè)自身發(fā)射的激光脈沖，由回射的信號(hào)通過處理來描述目標(biāo)信息，這給予了系統(tǒng)測(cè)量不會(huì)因時(shí)間和空間而受到影響的特點(diǎn)。有精密的傳感工藝支持，能自動(dòng)立體地采集目標(biāo)的立體結(jié)構(gòu)和表面結(jié)構(gòu)的數(shù)據(jù)。在進(jìn)行數(shù)據(jù)采集時(shí)，掃描系統(tǒng)采集和管理數(shù)據(jù)的軟件通過TCP/PI或平行連線接口及相應(yīng)的驅(qū)動(dòng)程序來控制掃描儀，處理軟件會(huì)對(duì)自動(dòng)選擇目標(biāo)的始點(diǎn)和終點(diǎn)，具有很好的建模處理、點(diǎn)云處理能力，其它的專業(yè)軟件還可以通過軟件開放的接口格式調(diào)用掃描的三維信息，與其它軟件也能兼容和互相操作。除此之外，軟件還能夠?qū)?shù)碼相機(jī)進(jìn)行定向、參數(shù)校準(zhǔn)和控制照片的采集等功能。系統(tǒng)提供了不同分辨率的掃描方式，可以重復(fù)地對(duì)物體進(jìn)行掃描，用戶也就能夠自己選在掃描的精度。激光掃描儀掃描獲取的數(shù)據(jù)經(jīng)過格式轉(zhuǎn)換后，得到的點(diǎn)云數(shù)據(jù)格式如下：X（m）Y(m)H(m)………………………………這是最基礎(chǔ)的三維空間坐標(biāo)數(shù)據(jù)，即點(diǎn)云數(shù)據(jù)。第一，點(diǎn)云數(shù)據(jù)的內(nèi)容是分布在目標(biāo)表面的大量三維點(diǎn)的坐標(biāo)。第三，點(diǎn)云數(shù)據(jù)能夠直接獲取測(cè)量數(shù)據(jù)，比如三維坐標(biāo)、距離等，還可以通過計(jì)算得到目標(biāo)的表面積、體積等。地面LiDAR也會(huì)由于目標(biāo)的不同出現(xiàn)數(shù)據(jù)分布不均勻的情況。KD樹的每一層都需要一個(gè)分辨器，根據(jù)這個(gè)分辨器作出該層的分支決策，對(duì)于一棵KD樹，它的第i層的分辨器就是i mod k（根節(jié)點(diǎn)為0層，接下來依次遞增）。接下來的其它層都依次類推。分割方式采用的是取最長軸中位數(shù)方法進(jìn)行分割。在根據(jù)算法進(jìn)行編程實(shí)現(xiàn)的過程中，考慮到數(shù)據(jù)量非常大的情況，避免出現(xiàn)內(nèi)存不夠?qū)е碌某绦蜻\(yùn)行失敗，建立索引的過程中并不移動(dòng)數(shù)據(jù)，僅僅依據(jù)數(shù)據(jù)建立索引，在完成索引建立后，才將對(duì)應(yīng)的數(shù)據(jù)存儲(chǔ)到相應(yīng)的也葉子結(jié)點(diǎn)中。 算法測(cè)試算法測(cè)試的將數(shù)據(jù)按照數(shù)據(jù)量進(jìn)行等級(jí)劃分，在沒給數(shù)量等級(jí)對(duì)若干個(gè)不同的點(diǎn)進(jìn)行K鄰近查找，查找同一個(gè)點(diǎn)的時(shí)候，改變K值得出各種查詢方式的效率。在后面的集中算法的測(cè)試中也是在相同的環(huán)境下按同樣的測(cè)試方式進(jìn)行算法測(cè)試。進(jìn)行了算法測(cè)試，得出了一些規(guī)律，也發(fā)現(xiàn)了KD樹索引在組織管理海量的數(shù)據(jù)時(shí)消耗的時(shí)間會(huì)大大增加，影響到查詢的效率。在八叉樹索引中，若是一棵非空的八叉樹，它必定包含八個(gè)子樹，而且每個(gè)子樹都是八叉樹。與KD樹索引建立相似，八叉樹索引建立時(shí)，同樣不在建立過程中移動(dòng)數(shù)據(jù)，只在最后完成索引建立后，才將數(shù)據(jù)存儲(chǔ)進(jìn)相應(yīng)的也葉子節(jié)點(diǎn)中。完成查找。使用C++語言實(shí)現(xiàn)了算法，并進(jìn)行了算法測(cè)試，找到了八叉樹索引的一些規(guī)律，也得出了八叉樹更不適合于組織和管理海量數(shù)據(jù)的結(jié)論。接下來用點(diǎn)云數(shù)據(jù)查找過程來解釋如何將兩種索引結(jié)合。可以將一次查找操作進(jìn)行分步處理，首先進(jìn)行粗略查找，也就是區(qū)域查找，然后再對(duì)查找到的區(qū)域進(jìn)行精確查找。索引的建立都是先建立粗略查找的索引，然后對(duì)粗略查找索引的葉子節(jié)點(diǎn)所代表的子空間建立精確查找索引。 兩種方法的查找方式相似，先進(jìn)行粗略查找，再進(jìn)行精確查找。與KD樹索引相比，在KDO索引的KD部分閾值設(shè)定跟KD樹索引相等，數(shù)據(jù)量相等，查找數(shù)據(jù)量相等且大于設(shè)定的閾值的情況下，KDO索引和KD索引的查詢效率相差不大，查找數(shù)據(jù)量小于設(shè)定閾值時(shí)，KDO索引查找效率不如KD索引。在數(shù)據(jù)量增大很多厚，OKD的查找效率相對(duì)于KDO索引和KD索引來說有明顯的提高，更適應(yīng)于海量的數(shù)據(jù)處理。與KDO索引相比，根據(jù)測(cè)試的數(shù)據(jù)，OKD索引是很成功的將KD樹索引和八叉樹索引結(jié)合起來了，在小數(shù)據(jù)量時(shí)，雖然在一定條件下，OKD索引的查詢效率低于KD樹索引，但是差距并不是很大，沒有明顯的區(qū)別，但是在數(shù)據(jù)量大增之后，OKD索引的查找效率明顯地比KD樹索引的效率高，隨著數(shù)據(jù)量的繼續(xù)增加，之間的差別還會(huì)繼續(xù)增加，主要原因是由于OKD索引充分利用了兩種索引的優(yōu)勢(shì)，先使用八叉樹索引實(shí)現(xiàn)粗略查找，更為迅速的確定目標(biāo)區(qū)域，再通過KD樹索引實(shí)施精確查找，發(fā)揮出KD樹索引精確查找效率高的優(yōu)勢(shì)，這樣就提高了整體的工作效率。經(jīng)過努力，本文在對(duì)于點(diǎn)云數(shù)據(jù)的組織與管理方面取得了一定的研究成果，但是由于本人的水平有限，本文還有一些不足之處值得注意以及更加進(jìn)一步的研究。參考文獻(xiàn)[1] :[D].武漢:武漢大學(xué),2011.[2] :[D].長沙:中南大學(xué),2009.[3] :[D].北京:首都師范大學(xué),2007.[4] :[D].武漢:武漢大學(xué),2008.[5] 程義民,孫啟彬,[J].自動(dòng)化學(xué)報(bào),1991,17(4):447454.[6] 寧津生,[J],第31卷第1期,2006年2月.[7] 張愛武,胡少興,蔡廣杰,王雷章,[C]. ,.[8] 劉少創(chuàng),尤紅建,1999,24(2):124~128.[9] :武漢大學(xué)出版社,~75.[10] :[D].北京:中國測(cè)繪科學(xué)研究院,2006.[11] :[D].武漢:武漢大學(xué),2002.[12] :[D].武漢:武漢大學(xué),2005.[13] and . Multidimentional Access Methods[J]. Computing :~ 231.[14] Dmitry 3D Building Model Generation from 2D Floor Plans[D]. The Dissertation of Master of Engineering in Electrical Engineering and Computer Science at the MASSACHUSETTS INSTITUTE OF TECHNOLOGY .September 2008.[15] Guting , .: An introduction to spatial database systems[J].VLDB Journal 3 (1994).[16] Hanan Samet. Review of Spatial Databases and Geographic Information Systems[C]. SEBD39。 MyPoint operator ( MyPoint )。 float distance (MyPoint)。}。c[2]=z。}MyPoint MyPoint::operator*(float d){ return MyPoint(c[0]*d,c[1]*d,c[2]*d)。amp。 else return false。typedef struct { MyPoint min。 ~Kdtree(void)。 CalcCubicBounds ( MyPoint * points,unsigned int count )。 BuildKdtree ( MyPoint * points, unsigned int count, unsigned int threshold, unsigned int maximumDepth, Kdtree * t, unsigned int currentDepth=0)。 void CleanK ( )。 bool _maker。}。 Kdtree * t。 =MyPoint(0,0,0)。 float sum[3]={,}。jcount。 } for(int j=0。jcount。 } if(varianc[0]varianc[1]) this_shaft=1。}Kdtreeamp。 i count。 if ([2] this[2]) this[2] = [2]。 } this=this+(10)。 Kdtree::SerchMiddle ( MyPoint * points, unsigned int count){ float *a=new float[_count]。i++) { if( ((points+i)c[0][0]amp。 ((points+i)c[1][1]amp。 ((points+i)c[2][2]amp。 } if(j==_count)break。 return *this。 p = new MyPoint *[t_count]。icount。amp。amp。 j++。 tSerchMiddle(points,count)。amp。amp。amp。 if([t_shaft]t_place) =1。i++) { if(!childCounts[i]) { std::cout分164。std::endl。 t_child[i]_count=childCounts[i]。 t_child[i]_shaft=(_shaft+1)%3。 Kdtree *t=this。 headnext=NULL。 node *s=new node。 while(qnext!=NULLamp。 qnext=s。 } DistP(t,p,points,i,k)。 delete q。ik。 endl。 cou