【正文】 任意空間對(duì)象進(jìn)行索引。這種分步查找的方式也就延伸出兩種索引結(jié)合的方式：KDO索引：粗略查找使用KD樹索引，精確查找使用八叉樹索引，這種方式雖然是進(jìn)行了結(jié)合，但是并沒有發(fā)揮出兩種索引各自的優(yōu)點(diǎn)，比如KD樹索引的精確查找，八叉樹索引的面向任意空間對(duì)象的查找；OKD：粗略查找使用八叉樹索引，精確查找使用KD樹索引，這種方式能夠使得兩種索引的優(yōu)點(diǎn)充分的發(fā)揮出來，有助于提高組織管理效率。在對(duì)于某一些情況下，查找的步驟會(huì)出現(xiàn)不同，具體的查找步驟如下：KDO索引查找步驟：1）進(jìn)行粗略檢查找，找到目標(biāo)區(qū)域，目標(biāo)區(qū)域包含的點(diǎn)數(shù)據(jù)量若大于查找的點(diǎn)數(shù)據(jù)量，則對(duì)這個(gè)空間進(jìn)行精確查找，若小于查找的點(diǎn)數(shù)據(jù)量，則先將目標(biāo)區(qū)域的所有點(diǎn)暫時(shí)列為查找結(jié)果的一部分，然后按照KD樹查找時(shí)的處理機(jī)制對(duì)其他區(qū)域進(jìn)行查找，根據(jù)查找路徑記錄空間進(jìn)行相似的判斷；2）精確查找后判斷最遠(yuǎn)鄰近點(diǎn)的距離是否大于被查找點(diǎn)到目標(biāo)區(qū)域邊界的最短距離，若是判斷后小于最短距離，則數(shù)據(jù)查找到的點(diǎn)數(shù)據(jù)，否則按照KD樹查找時(shí)的處理機(jī)制進(jìn)行其他區(qū)域的查找。在將KD樹索引同八叉樹索引結(jié)合后，得出兩種索引OKD索引和KDO索引。首先，本文作者寫出的代碼并沒有進(jìn)行足夠的優(yōu)化，可能會(huì)影響到算法效率對(duì)比的結(jié)果。 MyPoint operator + ( MyPoint )。include includeiostreamMyPoint::MyPoint(void) :code(0){ memset(c,0,sizeof(c))。}MyPoint MyPoint::operator+(float d){ return MyPoint(c[0]+d,c[1]+d,c[2]+d)。}Kdtree代碼：pragma onceincludetypedef struct{ MyPoint *point。 Kdtreeamp。 void SerchK ( MyPoint p,unsigned int k )。 Bounds _bounds。}node。 float average[3]={,}。j3。 if(varianc[this_shaft]varianc[2]) this_shaft=2。 i++) { MyPoint p = *(points+i)。 this=this+10。amp。amp。}Kdtreeamp。i++) { if( ((points+i)c[0]t[0]amp。 ((points+i)c[2]t[2]amp。 for(unsigned int i=0。(points+i)c[1]=t[1])amp。 childCounts[]++。 system(pause)。 t_child[i]BuildKdtree(points,count,threshold,maximumDepth,t_child[i],currentDepth+1)。 headt=NULL。amp。 while(ik||points[i].dheadnextd) { DistP(headnextt,p,points,i,k)。i++) { std::coutstd::setprecision(3)std::setiosflags(std::ios::fixed) 坐標(biāo)：X(points+i)pointc[0]Y:(points+i)pointc[1]Z:(points+i)pointc[2]距離：(points+i)dstd::endl。 endl。 for(int i=0。 t=t_child[]。 sd=fabs(t[t_shaft])。 headd=。 else t_child[i][t_shaft]=_place。170。 =0。 ((points+i)c[1]t[1]amp。 } unsigned int childCounts[2]={0,0}。(points+i)c[1]=t[1])amp。 for(unsigned int i=0。 delete [] a。amp。icount。 if ([2] this[2]) this[2] = [2]。 for (unsigned int i = 1。 varianc[2]+=((points+j)c[2]average[2])*((points+j)c[2]average[2])。 sum[2]+=(points+j)c[2]。 Kdtree::Shaft ( MyPoint *points,unsigned int count){ float max=。 node * next。 float _place。 Kdtreeamp。class Kdtree{public: Kdtree(void)。c[2]==[2]) return true。}MyPoint MyPoint::operator+(MyPoint p){ return MyPoint(c[0]+[0],c[1]+[1],c[2]+[2])。 unsigned int code。 ~MyPoint( void )。在效率對(duì)比中，可以看出隨著數(shù)據(jù)量小時(shí)，集中索引方式并沒有太大的差別，選擇哪種索引方式不會(huì)太過于影響到數(shù)據(jù)處理的效率，隨著數(shù)據(jù)量的增加，由八叉樹進(jìn)行粗略索引，由KD樹進(jìn)行精確查找的這種方法的效率會(huì)比其他的方式明顯高出許多，顯然由此而引出的OKD索引更適合于海量數(shù)據(jù)的情況下的檢索，對(duì)于現(xiàn)在的LiDAR技術(shù)的發(fā)展有著實(shí)際的意義。在數(shù)據(jù)量小時(shí)，OKD索引查找效率會(huì)同KDO索引和KD索引相差不大，但是小數(shù)據(jù)量下的情況并適應(yīng)數(shù)據(jù)量增大后的情況，而且數(shù)據(jù)量小的時(shí)候效率相差也不會(huì)太大，比較沒有意義。OKD索引建立步驟：1）先建立八叉樹索引；2）在建立八叉樹索引時(shí)，如果新建的結(jié)點(diǎn)為葉結(jié)點(diǎn)，且所代表的空間所包含的點(diǎn)數(shù)量大于KD樹索引設(shè)定的閾值，則對(duì)八叉樹的葉子結(jié)點(diǎn)所代表的子空間建立KD樹索引；3）完成整個(gè)索引的建立。八叉樹索引在精確查找方面并不具優(yōu)勢，若是為了進(jìn)行更精確的查找而減小閾值，會(huì)使得樹的深度加深，對(duì)于其他操作會(huì)有不良的影響。此章節(jié)介紹介紹了八叉樹的基本概念原理和八叉樹的點(diǎn)云數(shù)據(jù)組織方式，詳述了建立八叉樹索引以及檢查效率的K鄰近查找的算法。索引建立的算法步驟如下：1）設(shè)定索引的閾值，確定葉結(jié)點(diǎn)所代表的空間中允許存在的點(diǎn)數(shù)量的最大值；2）建立根結(jié)點(diǎn)R，計(jì)算原始點(diǎn)云的外包六面體邊長、中心點(diǎn)和包含的點(diǎn)云點(diǎn)數(shù)據(jù)數(shù)量并存儲(chǔ)在根結(jié)點(diǎn)中；3）若結(jié)點(diǎn)R代表的六面體空間包含的點(diǎn)數(shù)據(jù)數(shù)量小于閾值，則將該部分點(diǎn)云數(shù)據(jù)存儲(chǔ)在該結(jié)點(diǎn)中，否則進(jìn)行4）；4）建立結(jié)點(diǎn)R的八個(gè)子結(jié)點(diǎn)，根據(jù)點(diǎn)云數(shù)據(jù)點(diǎn)相對(duì)于結(jié)點(diǎn)R中心點(diǎn)位置，將點(diǎn)云數(shù)據(jù)分配到八個(gè)子結(jié)點(diǎn)中，并存儲(chǔ)每個(gè)結(jié)點(diǎn)所代表的子空間的變長、中心點(diǎn)和數(shù)據(jù)點(diǎn)數(shù)量等信息，依次對(duì)每個(gè)子結(jié)點(diǎn)執(zhí)行3）；5）在所有點(diǎn)分配完畢后結(jié)束索引建立。本章節(jié)介紹了KD樹索引的原理以及基于KD樹索引對(duì)點(diǎn)云數(shù)據(jù)進(jìn)行組織的方法，還介紹了索引建立和檢驗(yàn)查找效率的K鄰近查找算法。K鄰近查找的步驟：1）確定所查找點(diǎn)的坐標(biāo)及查找的鄰近點(diǎn)個(gè)數(shù)K；2）根據(jù)查找點(diǎn)坐標(biāo)確定點(diǎn)所在的葉子結(jié)點(diǎn)所代表的子空間R，記錄查詢路徑，同時(shí)記錄查詢路徑上中間點(diǎn)所代表子空間的分割面到查找點(diǎn)的距離，并按從小到大排序Z；3）計(jì)算R中包含的點(diǎn)到查找點(diǎn)的距離，同時(shí)進(jìn)行排序，取最近的K個(gè)點(diǎn)，若點(diǎn)的數(shù)量足夠K個(gè)點(diǎn)而且最遠(yuǎn)的點(diǎn)的距離小于查詢路徑上最近的分割面的距離，則完成查詢，否則根據(jù)查詢路徑排序Z對(duì)相應(yīng)的空間進(jìn)行查找，對(duì)查找過的空間標(biāo)號(hào)，若查找到的K個(gè)點(diǎn)滿足要求或者整個(gè)空間都查詢完成，這結(jié)束查詢。為了降低KD樹刪除的代價(jià)，中間點(diǎn)不存儲(chǔ)數(shù)據(jù)點(diǎn)，所有的數(shù)據(jù)點(diǎn)都存放在葉結(jié)點(diǎn)中。KD樹是K（K2）維的二叉索引樹，但與二叉索引樹不同，它的每個(gè)結(jié)點(diǎn)表示的都是一個(gè)K維空間中的一個(gè)點(diǎn)。點(diǎn)的位置和相互之間的間隔并沒有一定的分布規(guī)則，更加容易表達(dá)出目標(biāo)物體的細(xì)節(jié)信息。（10）新型的掃描系統(tǒng)還裝備了GPS接收機(jī)或者其他的高精度定位裝置，在軟件平臺(tái)的內(nèi)部可以進(jìn)行坐標(biāo)轉(zhuǎn)換，將點(diǎn)云數(shù)據(jù)直接轉(zhuǎn)換成為大地坐標(biāo)系下的坐標(biāo)，更加方便使用。在后期數(shù)據(jù)處理階段，利用圖片信息還能夠?qū)?shù)據(jù)進(jìn)行調(diào)整、編輯、貼圖等操作。（5）密度高、精度高：激光掃描能夠獲取目標(biāo)的表面特征密度、精度都很高。該系統(tǒng)具有如下特點(diǎn)[4][12]：（1）快速性：激光掃描測量獲取到大面積目標(biāo)的空間信息的速度很快。圖6 地面LiDAR系統(tǒng)組成Error! Reference source not found.地面LiDAR系統(tǒng)工作的原理如下：首先從激光脈沖二極管中發(fā)射出激光脈沖信號(hào)，在經(jīng)過了旋轉(zhuǎn)棱鏡后射向目標(biāo)，然后探測器接收從目標(biāo)反射的激光脈沖信號(hào)，并且記錄器記錄下來，最后將記錄轉(zhuǎn)換，變成能直接識(shí)別和處理的數(shù)據(jù)信息，在經(jīng)過軟件處理后實(shí)現(xiàn)實(shí)體建模輸出圖7 地面LiDAR工作原理在使用地面LiDAR系統(tǒng)對(duì)目標(biāo)掃描的時(shí)候，掃描儀從左到右、從上到下地進(jìn)行全自動(dòng)的步進(jìn)掃描測量，隨著兩個(gè)同步反射鏡地旋轉(zhuǎn)，窄束激光脈沖從激光脈沖發(fā)射體發(fā)出依次掃過目標(biāo)區(qū)域，測量出從發(fā)出到返回儀器的每個(gè)激光脈沖所經(jīng)過的時(shí)間（或者相位差），由此計(jì)算出距離值，同時(shí)獲取掃描控制模塊的控制，測量出每個(gè)脈沖激光角度值。第四，機(jī)載LiDAR系統(tǒng)作業(yè)時(shí)很安全，能在危險(xiǎn)地區(qū)（例如大型垃圾堆、沼澤地帶等）進(jìn)行測圖的工作；第五，機(jī)載LiDAR不僅可以單獨(dú)作為采集環(huán)境信息、地表資源的重要手段，還可以和其它的一些技術(shù)手段結(jié)合使用，比如可以與紅外遙感、航空攝影測量以及數(shù)字?jǐn)z影測量等相結(jié)合，組成功能更強(qiáng)的系統(tǒng)[11]。平行模式中沿掃描線方向的點(diǎn)距很小，掃描線之間的距離卻相對(duì)大。為了能夠得到具有一定帶寬的激光腳點(diǎn)的距離信息，就需要使用機(jī)械裝置，用某種掃描方式來作業(yè)。測量光波的往返時(shí)間的方法有脈沖法、相位法和變頻法，比較常用脈沖法和相位法。這些參數(shù)還需要通過一定的方法進(jìn)行檢校來確定。第五章，基于KD樹和八叉樹索引混合的點(diǎn)云數(shù)據(jù)組織與管理。 論文結(jié)構(gòu)安排本文共分成六章，相應(yīng)章節(jié)的內(nèi)容安排如下：第一章，緒論。每種索引都有自己的應(yīng)用特點(diǎn)。相對(duì)于傳統(tǒng)攝影測量技術(shù)，LiDAR技術(shù)有許多的更優(yōu)秀的地方，例如：LiDAR獲取的點(diǎn)云數(shù)據(jù)密度非常高，獲取的三維點(diǎn)之間的間距可以從米級(jí)到毫米級(jí)乃至更小的級(jí)別；獲取到的數(shù)據(jù)精度很高，由于激光有很高的方向性，一般很少因環(huán)境而影響；由于光波的一些特性，有部分LiDAR還能夠穿透地物，可透過非常狹小的空隙，探測到那些被遮擋的物體；不僅可以獲取到三維空間的幾何數(shù)據(jù)，還可以獲取到地物反射率等其他信息，某些LiDAR經(jīng)過加裝配準(zhǔn)了得高分辨率相機(jī)，可以完成對(duì)彩色紋理自動(dòng)匹配，而且精度很高，還可以通過加裝感應(yīng)位置與姿態(tài)的裝置，完成多站的點(diǎn)云自動(dòng)配準(zhǔn)，在最后形成整體是彩色的點(diǎn)云模型等等。空間數(shù)據(jù)獲取手段正在向多樣化、自動(dòng)化、高精度化、便捷化發(fā)展，例如研究開發(fā)更高精度的測量儀器，把測量的精度由毫米向納米發(fā)展；通過自動(dòng)化技術(shù)和計(jì)算機(jī)技術(shù)的融合發(fā)展向智能化、一體化的測量設(shè)備及系統(tǒng)，以提高測量的工作效率；把傳統(tǒng)的對(duì)點(diǎn)測量數(shù)據(jù)采集技術(shù)發(fā)展成利用數(shù)字?jǐn)z影或遙感衛(wèi)星等獲得的數(shù)字影像的面測量手段，提高了單點(diǎn)精度、數(shù)量和整體的模型精度。由于通過立體視差法對(duì)圖像進(jìn)行特征匹配在實(shí)際應(yīng)用中有許多困難，于是使用主動(dòng)光源對(duì)真實(shí)物體進(jìn)行照射，通過使用編碼光或者結(jié)構(gòu)光的辦法恢復(fù)三維空間的信息。對(duì)于點(diǎn)云數(shù)據(jù)的組織與管理的目的是能夠更好的、更高效地對(duì)點(diǎn)云數(shù)據(jù)進(jìn)行處理，在所有針對(duì)點(diǎn)云數(shù)據(jù)進(jìn)行的處理操作中，最基礎(chǔ)的操作即是查詢操作，若是對(duì)于點(diǎn)云數(shù)據(jù)的組織管理能在查詢操作上更加高效，相信能極大地提高空間數(shù)據(jù)處理的效率，推動(dòng)LiDAR技術(shù)的發(fā)展。所以，空間數(shù)據(jù)的重要獲取手段也將變成不用近距離接觸而且效率高的測量方法，而如何能夠?qū)Ａ康目臻g數(shù)據(jù)進(jìn)行快速、可靠、自動(dòng)化的處理也就成為了研究的核心問題。2) It summarizes the characteristics of the point cloud data, such as the mass of a little cloud data, discrete, uneven distribution. In addition, It describes the octree index and regular grid index, and analyzes the shortings and deficiencies of their existence in the organization and management of point cloud data。本科生畢業(yè)設(shè)計(jì)（論文） 基于KD樹與八叉樹索引相結(jié)合的 LiDAR點(diǎn)云數(shù)據(jù)索引建立方法題目： 姓名： 學(xué)號(hào)： 班級(jí)： 二〇一五年六月中 國 礦 業(yè) 大 學(xué)本科生畢業(yè)設(shè)計(jì)學(xué) 院： 環(huán)境與測繪學(xué)院 專 業(yè)： 測繪工程 設(shè)計(jì)題目： 基于KD樹與八叉樹索引相結(jié)合的