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