【正文】 現時，同樣還是為了避免內存不足的情況，在最后才將數據存儲進入精確查找索引的葉子節(jié)點中。這種分步查找的方式也就延伸出兩種索引結合的方式：KDO索引：粗略查找使用KD樹索引，精確查找使用八叉樹索引，這種方式雖然是進行了結合，但是并沒有發(fā)揮出兩種索引各自的優(yōu)點，比如KD樹索引的精確查找，八叉樹索引的面向任意空間對象的查找；OKD：粗略查找使用八叉樹索引，精確查找使用KD樹索引，這種方式能夠使得兩種索引的優(yōu)點充分的發(fā)揮出來，有助于提高組織管理效率。對于點云數據的查找來說，不論是KD樹索引還是八叉樹索引，都是直接進行精確的點數據查找。5 基于KD樹和八叉樹混合的LiDAR點云數據組織與管理KD樹索引和八叉樹索引都有各自的優(yōu)點，KD樹索引能夠高效地進行精確點的查找，而八叉樹算法簡單，能針對任意空間對象進行索引。 算法測試程序實現后某次查詢運行界面：八叉樹索引測試結果：表3 八叉樹算法測試最佳耗時表點數據量54152710024061531046K鄰近查找最佳耗時（s）10004000800012000就八叉樹索引測試過程中獲得的完整數據來說，有如下的規(guī)律：1）數據數量一定，閾值設定越小，索引建立耗時越長；2）閾值一定，數量級增大，索引建立耗時增長；3）查詢數據量一定，閾值設定越小，查詢耗時相對越少；4）閾值確定，查詢的數據量越大，查詢時間越長。在編程實現八叉樹索引建立的過程中，為了便于進行K鄰近查找，對那些并不存在點數據的子空間也建立了結點去表示，防止因為查找的點在原點云數據中的位置區(qū)域沒有結點表示而阻礙了K鄰近查找。圖10 八叉樹示意圖八叉樹結構是將包含點云數據的外包六面體按照八叉樹劃分的規(guī)則進行劃分（劃分的深度由設定的閾值決定），每次劃分通過點坐標同空間中心坐標的對比，分配到不同的子空間中，隨著遞歸劃分的深入，在子空間中的點數量小于閾值的時候，將被該子空間包含的點的數據存儲到葉結點中，劃分中途的“中間點”并不存儲點云數據。本章節(jié)所有的實現代碼已經附在附錄中。下面是KD樹索引測試結果（最佳查找耗時是在多次測試，設定不同的閾值的情況下得出的耗時最少的情況）。本次驗證的數據選取了3組點云數據，3組數據都是由Riegl VZ1000三維激光掃描儀掃描學校建筑獲取的點云數據。 K鄰近查找K鄰近查找在不同的索引中查找原理也都不相同。KD樹的每個中間結點都需要有將這個結點所代表的子空間分割平面，分割平面會把這個空間分割成兩個字空間，結點的兩個子節(jié)點就代表了這兩個子空間，空間中所有的點也會分配到兩個子空間中。KD樹索引是二叉樹索引在多維空間的擴展，在具備為多維空間進行索引，進行精確點查找的同時，也繼承了二叉樹索引的優(yōu)點，平均查找長度為1+4logn。一棵非空的KD樹的性質如下：（1）如果它的左子樹不是空樹，則左子樹上的所有結點的第d維的值都小于它的父結點第d維的值，右子樹是同理。本章節(jié)介紹了點云數據的結構以及特點，在研究點云數據的索引方式的時候需要考慮到數據的結構和特點，據此來分析各種索引可能從哪些特點提高檢索效率。第四，點云數據分布不均勻。所以點云反映的是目標表面的信息，并沒有內部的信息。除了三維坐標屬性外還能夠加入其它的屬性數據，比如反射強度等等。對全景空間采集的內容的量及后期的處理中數據拼接的次數由掃描的次數來決定，用戶能夠自由控制工作量的大小。這讓系統(tǒng)能夠帶色彩地去顯示云點數據。（7）地面LiDAR掃描系統(tǒng)能夠通過同步變化視距使得激光自動聚焦，改良了實際測量時的精度，在不同測距的散焦效應也提高了，更好地逼近實體原形。獲取的點云數據是由點的位置的三維坐標數據構成，降低了傳統(tǒng)手段中由于人工的計算或推導帶來的不確定性。系統(tǒng)發(fā)射的激光束可以近似看作平行光，不需要去擔心常規(guī)的光學照相測量中存在的光學變形誤差。（2）非接觸性：地面LiDAR系統(tǒng)可以不需要接觸目標而完成掃描測量，獲取真實世界實體的三維坐標數據，能夠一次性完成從目標實體到三維點云數據的轉換，真正地做到了快速重構原型。兩者之間不同的地方是地面LiDAR技術是全自動地獲取面數據，而且密度很高，數據信息也更加豐富。前三個數據是用來計算掃描點的三維坐標值的；掃描點反射強度則可以用于給反射點匹配顏色。配準靶標配合其他定位設備一起使用時，能夠自動完成配準和坐標轉換等步驟。地面LiDAR系統(tǒng)由幾個部分組成，包括三維激光掃描儀、掃描儀旋轉平臺、CCD相機、數據處理平臺、軟件控制平臺及電源和一些其它的附件設備共同組成，是集成了多種技術的空間信息數據獲取技術。第三，機載LiDAR很少需要或者不需要地面控制點就能在同時能采集大面積的目標的空間信息。圖5 三種掃描方式的點整列形式作為一種新的信息獲取的模式， 機載LiDAR系統(tǒng)己經引起了廣泛的關注，成為國際上進行研究開發(fā)的熱點技術。隨平臺的運動，光斑會在地面上畫出一系列有部分重疊的橢圓。線掃描是使用旋轉式或擺動式的掃描鏡來實現的。測量出發(fā)射主脈沖和受到激光回波脈沖之間的時間間隔。如圖： 圖4 激光脈沖時間測量原LiDAR系統(tǒng)進行距離測量可以分為以步驟：第一步，發(fā)射激光。假設t為光波在一段距離上來回傳播的時間，之間的距離可以表示為： （22）在上述式子中，為激光發(fā)射點和反點之間的距離長度；是激光測距距離的分辨率；c是光在真空中的速度，約為300000km/s；是測距時，系統(tǒng)的測時分辨率；t是光波的往返時間。 （21）式中圖3 線掃描方式直接對地定位原理圖Error! Reference source not found.（2）測距系統(tǒng)原理可見光、紅外光、無線電波、X光等都是屬于電磁波。在機載LiDAR系統(tǒng)中，起點就是遙感器的光學系統(tǒng)的投影中心，它的坐標（）可以由動態(tài)差分GPS得到；向量的模R是由投影中心到地面激光落點之間的距離，通過高精度的姿態(tài)測量裝置可以測量出姿態(tài)參數（）[8][9]?？偨Y了本文的研究內容，并指出進一步研究的問題。第四章，基于八叉樹索引的點云數據組織與管理。第二章，點云數據結構和特點。3）研究了KD樹和八叉樹的結合方式，并使用C++語言具體實現了算法，進行了算法測試，將兩種單個索引方式和結合后的索引方式測試結果進行了對比分析。就目前來說，很多相關的軟件都是采用幾種索引方式都使用、取長補短的策略。；，這種索引方式對于精確點查找有很好的性能；在1984年，GUTTMAN提出了R樹，是一種支持擴展對象存取的索引方法，同時也是現階段應用最廣泛的一種空間索引結構。點云數據是一種三維空間坐標數據。LiDAR系統(tǒng)利用極坐標幾何定位的原理，可以直接得到目標地物表面的三維坐標信息，從而實現了真實三維世界到數字化三維世界的轉換。通常來說，接觸式的測量方式大部分應用在工業(yè)生產的領域，受到它的測量原理的限制，測量速度相對較慢，而且可能損傷被測量的物體，基本上不能測量柔軟易變形的物體，測量范圍較窄，測量效率比較低；非接觸式測量應用于各行各業(yè)，測量速度相對較快，而且能夠不接觸物體而進行無損測量，但是它總是存在固有缺陷，即是對物體的邊界或者輪廓經常測不準，從而測量誤差較大，而且有許多的測量方法對與物體的傾斜度比較敏感，特別是光學測量手段，傾斜度過大會造成反射率降低，數據獲取的精度也會降低，非接觸式測量很難解決物體間的遮擋問題，容易使得測量數據缺失。在測繪學科中，如何去獲取三維空間數據是基礎和出發(fā)點，測繪學科的發(fā)展歷史就是三維空間數據處理應用方法的與獲取工具的發(fā)展歷史。又或者是使用人工標記的輪廓線來表達出三維場景中的物體與物體之間的關系，然后恢復相機參數或者求取表面方向的方法來估計出目標對象的深度，獲得了很好的效果[5]。值得一提的是計算機視覺的理論與方法，發(fā)展到現在已經成為了一種獲取三維空間信息的非常重要的方法。 國內外研究現狀三維空間數據的獲取技術主要研究怎樣把真實的空間地物進行數字化變成計算機能夠進行處理和存儲的數據模型，通過獲取的三維空間坐標以及其他的一些屬性進行數字化建模。這其中有三點原因：（1）不同的應用對象，處理數據的方法不一樣；（2）載體不同，數據處理的方法也不同；（3）掃描產生的數據量非常大，也限制了點云數據處理的發(fā)展。它把激光測距、CCD攝像集于一身，根據載體的不同，可以組成車載、機載和星載LiDAR系統(tǒng)，能夠直接獲取大范圍地表及地物三維數據，而且具有快速、高精度、高密集的特點，除此之外，它還能夠全天候地、實時地、而且主動地進行數據獲取。 KD tree目 錄摘 要ABSTRACT目 錄1 緒 論 1 研究背景與意義 1 國內外研究現狀 1 1 4 研究內容 5 論文結構安排 52 點云數據獲取的理論和數據特點 6 6 6 7 10 11 11 11 12 14 14 153 基于KD樹的LiDAR點云數據組織與管理 15 15 16 16 16 K鄰近查找 17 算法測試 17 194 基于八叉樹的LiDAR點云數據組織與管理 19 19 19 20 K鄰近查找 20 算法測試 21 215 基于KD樹和八叉樹混合的LiDAR點云數據組織與管理 22 22 22 22 23 24 266 結論與展望 26 26 26參考文獻 28附錄 29英文原文 49中文翻譯 58致 謝 64中國礦業(yè)大學本科畢業(yè)設計（論文） 第81頁1 緒 論 研究背景與意義在現在的測繪領域研究中，如何更加快速獲取和更加智能化地處理地球空間信息是研究的熱點，也是在比如“數字地球”、“數字城市”等領域中急需要解決的問題。4)Explore the posite index of the KDtree indexes and octree index, and found two method of indexes for point cloud which named KDO index and OKD index. After testing of two new indexes, the results show, OKD index is more suitable for massive point cloud data management.Keywords: LiDAR。demand,基于上述分析，對于研究點云數據的索引機制也就非常重要了，針對與點云索引建立過程中有涉及到的關鍵技術，論文的主要的研究內容和成果有：1）回顧了三維空間信息獲取技術、LiDAR技術和點云數據組織管理方法的發(fā)展和研究現狀；2）總結了點云數據的特點，例如有點云數據海量性、離散性、分布不均勻等特點，除此之外還介紹了八叉樹索引和規(guī)則格網索引，同時分析了它們在組織和管理點云數據時存在的缺點和不足；3）設計并編程實現了基于KD樹與八叉樹的點云索引，并進行了算法測試與比較，由獲得的測試結果得出，在點云數據量相同的情況下，KD樹的查詢效率比八叉樹索引更更高，對于點云數據的管理效率更加優(yōu)秀；4）探索了KD樹索引與八叉樹索引相結合的點云索引建立方法，分別形成了KDO與OKD等兩種索引，利用C++語言對其編程實現，進行了算法測試，結果顯示出OKD索引更適合于海量的點云數據管理。地面LiDAR的發(fā)展改變了傳統(tǒng)的數據獲取模式，拓寬了數據源范圍，實現了快速獲取高分辨率數字表面模型；但是點云數據的海量性成為了制約點云數據處理方法的發(fā)展的重要因素，急需尋找一種高效空間索引的方法來解決這個問題，高效地管理海量點云數據。social3) Design and programming index of point cloud which based on the KD Tree and octree, and tested and pared the two of algorithms. According to the test results, at the same point cloud data, KD tree efficiency is higher than the efficiency of the octree。 octree。LiDAR技術是在攝影測量與遙感領域中的一個巨大的成就?，F在的點云數據獲取技術有很大的發(fā)展，能夠高速、高精度、高密度地獲取點云數據，然而對于點云數據的處理技術并沒有跟上獲取技術的步伐。本文針對LiDAR系統(tǒng)所獲取的點云數據在組織與管理效率的問題，研究工作具有重要的理論和實用意義。在長期的生產實踐中，人們在不同的應用領域發(fā)明了許多三維空間數據獲取的方法，比如接觸式測量技術，它應用于傳統(tǒng)工業(yè)生產領域中，采用機械手段與被測量物體接觸，通過裝在機械臂上的傳感器，確定目標物體表面的相對三維坐標；還有一類非接觸式的測量技術，它們利用到了聲學、光學、電磁學等技術，在不與被測物體進行接觸的前提之下，獲取到物體的表面及內部的三維坐標信息，在如醫(yī)學檢查、水下勘探、文化遺產保護、逆向工程等許多的方面應用得很好。有的研究人員還通過在連續(xù)運動中的物體建立特征基元，從連續(xù)的圖像序列中提取出特征點基元和線基元并進行匹配，最終達到恢復場景深度信息的目的。還有一類來源于人類的設計與測量的三維空間數據，工程人員使用測量的二維坐標和高程數據重建三維場景，在三維模型制作與渲染軟件中建立三維模型，比如3DMax、SketchUp等軟件等都有這種功能；又或者通過對現有的設計資料進行數字化后重建三維模型，例如從XML格式的CAD平面圖中恢復建筑的三維模型[14]。盡管以上的三維空間信息獲取技術正在不斷的完善，但是它們都有與自身相適用的范圍與使用條件，不存在哪一種測量手段