【正文】 能適應(yīng)所有的情況，這也使得測量儀器的不斷推陳出新。由于這些原因，必須做出一套能全天候主動去獲取高精度空間數(shù)據(jù)的系統(tǒng)，LiDAR測量系統(tǒng)便出現(xiàn)了。展望未來，LiDAR系統(tǒng)必定會成為獲取三維空間數(shù)據(jù)的重要設(shè)備，它會同其他數(shù)據(jù)獲取技術(shù)，例如全球衛(wèi)星定位、控制測量、近景攝影測量等技術(shù)一起促進空間信息技術(shù)向前發(fā)展。隨著應(yīng)用需求的發(fā)展以及研究的深入，索引的維度也開始從傳統(tǒng)的一維、二維索引向多維發(fā)展，出現(xiàn)了一些三維空間數(shù)據(jù)庫的索引方法，比如R樹索引、KD樹索引、四叉樹索引等，索引的空間對象也由“點、線、面”發(fā)展到“點、線、面、體”。下表是前人對常用的索引方式研究的基礎(chǔ)上得出的綜合性能表Error! Reference source not found.：表1 常用索引方式基礎(chǔ)性能表索引名稱劃分區(qū)域方法適合對象優(yōu)點缺點KD樹根據(jù)點二分點對象查詢效率高，存儲要求低對于海量數(shù)據(jù)管理困難，主要對點對象索引八叉樹對空間八分空間對象算法簡單，比較適應(yīng)空間對象深度較大，可能對各種操作有不利影響R樹矩形或其他不規(guī)則多邊形空間對象比較適應(yīng)空間對象算法復(fù)雜，區(qū)域重疊KDB樹根據(jù)點二分點對象查詢效率高，動態(tài)索引刪除困難，主要用于點對象索引BSP樹對空間二分空間對象容易控制切割面以及樹的深度，檢索速度也快算法較為復(fù)雜，要預(yù)先生成，動態(tài)維護性能較差規(guī)則網(wǎng)格等分面域或不等分空間對象查詢效率高，算法簡單，跟編碼相結(jié)合分辨率單一，難以維護，數(shù)據(jù)冗余實際上，現(xiàn)在出現(xiàn)的多種索引方式都是針對于不斷出現(xiàn)的新需求而出現(xiàn)的，對于在實際應(yīng)用中選擇哪種索引方式作為空間數(shù)據(jù)庫的索引，要從實際出發(fā)。主要的研究內(nèi)容有：1）點云數(shù)據(jù)獲取的理論研究，對機載LiDAR和車載LiDAR的系統(tǒng)組成、原理和特點進行分析；2）研究基于KD樹和八叉樹的LiDAR點云數(shù)據(jù)的組織與管理，通過C++語言進行實現(xiàn)，完成了算法測試，規(guī)律分析和對比。此章節(jié)介紹了本文的研究背景和空間數(shù)據(jù)索引在國內(nèi)外的發(fā)展現(xiàn)狀，分析了在現(xiàn)在點云數(shù)據(jù)組織管理中存在的問題，提出了本文所研究的內(nèi)容。此章節(jié)主要介紹了KD樹索引的概念原理、建立算法以及查詢算法，進行算法測試得出結(jié)果及分析。此章節(jié)主要介紹了兩種索引混合的方式原理及建立方式，進行算法測試，得出了結(jié)果和對比分析第六章，結(jié)論與展望。圖1 機載LiDAR系統(tǒng)的組成單元[2]（1）對地定位原理假設(shè)在空間有一個向量，它的模為R，方向為（），如果可以測出向量R的起點的坐標(biāo)（），便可以通過計算得出向量R的另一端點P的坐標(biāo)（X，Y，Z）。圖2 對地定位示意圖線掃描方式是一種最常用的掃描方式，以線掃描方式為例子，對于地面上的點P，如果它和掃描儀之間距離為S，掃描儀的位置坐標(biāo)為（），P點與掃描中心線的角度大小為，地面點P的坐標(biāo)就可以通過以下方式計算出來。由于光在空氣中的傳播速度一定，通過測定光波在發(fā)射點到被測目標(biāo)之間來回傳播的時間能夠求出距離值，這是激光測距的基本原理。相位法是利用連續(xù)波信號的相位差，間接地去確定傳播的時間；脈沖法是對傳播時間直接量測[10]。處理不規(guī)則的回波信號，由此估計出目標(biāo)測距的可能產(chǎn)生的延時，給出回波脈沖信號，目標(biāo)回波的延時就是脈沖信號的延時；第四步，測量時間延遲。現(xiàn)在常用的有三種掃描方式：圓錐掃描、線掃描、纖維光學(xué)陣列掃描。掃描鏡的鏡面傾斜出一個傾角，它的旋轉(zhuǎn)軸和發(fā)射裝置的激光束之間成45度夾角?！癦”字模型是將掃描儀擺動來實現(xiàn)的，一定程度上彌補了掃描線之間距離大的問題。第二，機載LiDAR的激光脈沖信號的穿透力非常強，能部分的穿透植被，能夠快速地獲得精度較高和空間分辨率較高的森林或山區(qū)的數(shù)字地面模型。地面LiDAR技術(shù)是通過激光進行高速的、實時的、自動的獲取區(qū)域目標(biāo)表面的三維坐標(biāo)的測量技術(shù)，是一種能夠獲取大面積高密度的三維空間信息的非接觸式主動測量技術(shù)。附件設(shè)備還有腳架，配準(zhǔn)靶標(biāo)等等。即獲得的原始數(shù)據(jù)有：兩個反射鏡的角度值，在下圖中為水平角值和垂直角值；通過計算得到的儀器到掃描點之間的斜距S，掃描點反射強度。 (23)地面LiDAR技術(shù)跟全站儀測量技術(shù)的定位原理是相同的，都是將儀器自身中心作為坐標(biāo)原點，測出距離值和角度值，進行解算得出目標(biāo)的三維坐標(biāo)。將激光掃描技術(shù)用于目標(biāo)空間數(shù)據(jù)信息采集，能夠及時地測定出目標(biāo)表面的三維信息，所以能夠在自動監(jiān)控行業(yè)內(nèi)應(yīng)用。（4）實時、動態(tài)與主動性：地面LiDAR系統(tǒng)是一個主動式的掃描系統(tǒng)，利用的是探測自身發(fā)射的激光脈沖，由回射的信號通過處理來描述目標(biāo)信息，這給予了系統(tǒng)測量不會因時間和空間而受到影響的特點。有精密的傳感工藝支持，能自動立體地采集目標(biāo)的立體結(jié)構(gòu)和表面結(jié)構(gòu)的數(shù)據(jù)。在進行數(shù)據(jù)采集時，掃描系統(tǒng)采集和管理數(shù)據(jù)的軟件通過TCP/PI或平行連線接口及相應(yīng)的驅(qū)動程序來控制掃描儀，處理軟件會對自動選擇目標(biāo)的始點和終點，具有很好的建模處理、點云處理能力，其它的專業(yè)軟件還可以通過軟件開放的接口格式調(diào)用掃描的三維信息，與其它軟件也能兼容和互相操作。除此之外，軟件還能夠?qū)?shù)碼相機進行定向、參數(shù)校準(zhǔn)和控制照片的采集等功能。系統(tǒng)提供了不同分辨率的掃描方式，可以重復(fù)地對物體進行掃描，用戶也就能夠自己選在掃描的精度。激光掃描儀掃描獲取的數(shù)據(jù)經(jīng)過格式轉(zhuǎn)換后，得到的點云數(shù)據(jù)格式如下：X（m）Y(m)H(m)………………………………這是最基礎(chǔ)的三維空間坐標(biāo)數(shù)據(jù)，即點云數(shù)據(jù)。第一，點云數(shù)據(jù)的內(nèi)容是分布在目標(biāo)表面的大量三維點的坐標(biāo)。第三，點云數(shù)據(jù)能夠直接獲取測量數(shù)據(jù)，比如三維坐標(biāo)、距離等，還可以通過計算得到目標(biāo)的表面積、體積等。地面LiDAR也會由于目標(biāo)的不同出現(xiàn)數(shù)據(jù)分布不均勻的情況。KD樹的每一層都需要一個分辨器，根據(jù)這個分辨器作出該層的分支決策，對于一棵KD樹，它的第i層的分辨器就是i mod k（根節(jié)點為0層，接下來依次遞增）。接下來的其它層都依次類推。分割方式采用的是取最長軸中位數(shù)方法進行分割。在根據(jù)算法進行編程實現(xiàn)的過程中，考慮到數(shù)據(jù)量非常大的情況，避免出現(xiàn)內(nèi)存不夠?qū)е碌某绦蜻\行失敗，建立索引的過程中并不移動數(shù)據(jù)，僅僅依據(jù)數(shù)據(jù)建立索引，在完成索引建立后，才將對應(yīng)的數(shù)據(jù)存儲到相應(yīng)的也葉子結(jié)點中。 算法測試算法測試的將數(shù)據(jù)按照數(shù)據(jù)量進行等級劃分，在沒給數(shù)量等級對若干個不同的點進行K鄰近查找，查找同一個點的時候，改變K值得出各種查詢方式的效率。在后面的集中算法的測試中也是在相同的環(huán)境下按同樣的測試方式進行算法測試。進行了算法測試，得出了一些規(guī)律，也發(fā)現(xiàn)了KD樹索引在組織管理海量的數(shù)據(jù)時消耗的時間會大大增加，影響到查詢的效率。在八叉樹索引中，若是一棵非空的八叉樹，它必定包含八個子樹，而且每個子樹都是八叉樹。與KD樹索引建立相似，八叉樹索引建立時，同樣不在建立過程中移動數(shù)據(jù)，只在最后完成索引建立后，才將數(shù)據(jù)存儲進相應(yīng)的也葉子節(jié)點中。完成查找。使用C++語言實現(xiàn)了算法，并進行了算法測試，找到了八叉樹索引的一些規(guī)律，也得出了八叉樹更不適合于組織和管理海量數(shù)據(jù)的結(jié)論。接下來用點云數(shù)據(jù)查找過程來解釋如何將兩種索引結(jié)合。可以將一次查找操作進行分步處理，首先進行粗略查找，也就是區(qū)域查找，然后再對查找到的區(qū)域進行精確查找。索引的建立都是先建立粗略查找的索引，然后對粗略查找索引的葉子節(jié)點所代表的子空間建立精確查找索引。 兩種方法的查找方式相似，先進行粗略查找，再進行精確查找。與KD樹索引相比，在KDO索引的KD部分閾值設(shè)定跟KD樹索引相等，數(shù)據(jù)量相等，查找數(shù)據(jù)量相等且大于設(shè)定的閾值的情況下，KDO索引和KD索引的查詢效率相差不大，查找數(shù)據(jù)量小于設(shè)定閾值時，KDO索引查找效率不如KD索引。在數(shù)據(jù)量增大很多厚，OKD的查找效率相對于KDO索引和KD索引來說有明顯的提高，更適應(yīng)于海量的數(shù)據(jù)處理。與KDO索引相比，根據(jù)測試的數(shù)據(jù)，OKD索引是很成功的將KD樹索引和八叉樹索引結(jié)合起來了，在小數(shù)據(jù)量時，雖然在一定條件下，OKD索引的查詢效率低于KD樹索引，但是差距并不是很大，沒有明顯的區(qū)別，但是在數(shù)據(jù)量大增之后，OKD索引的查找效率明顯地比KD樹索引的效率高，隨著數(shù)據(jù)量的繼續(xù)增加，之間的差別還會繼續(xù)增加，主要原因是由于OKD索引充分利用了兩種索引的優(yōu)勢，先使用八叉樹索引實現(xiàn)粗略查找，更為迅速的確定目標(biāo)區(qū)域，再通過KD樹索引實施精確查找，發(fā)揮出KD樹索引精確查找效率高的優(yōu)勢，這樣就提高了整體的工作效率。經(jīng)過努力，本文在對于點云數(shù)據(jù)的組織與管理方面取得了一定的研究成果，但是由于本人的水平有限，本文還有一些不足之處值得注意以及更加進一步的研究。參考文獻[1] :[D].武漢:武漢大學(xué),2011.[2] :[D].長沙:中南大學(xué),2009.[3] :[D].北京:首都師范大學(xué),2007.[4] :[D].武漢:武漢大學(xué),2008.[5] 程義民,孫啟彬,[J].自動化學(xué)報,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].北京:中國測繪科學(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