【文章內(nèi)容簡介】 下地進行全自動的步進掃描測量，隨著兩個同步反射鏡地旋轉(zhuǎn)，窄束激光脈沖從激光脈沖發(fā)射體發(fā)出依次掃過目標區(qū)域，測量出從發(fā)出到返回儀器的每個激光脈沖所經(jīng)過的時間（或者相位差），由此計算出距離值，同時獲取掃描控制模塊的控制，測量出每個脈沖激光角度值。即獲得的原始數(shù)據(jù)有：兩個反射鏡的角度值，在下圖中為水平角值和垂直角值；通過計算得到的儀器到掃描點之間的斜距S，掃描點反射強度。前三個數(shù)據(jù)是用來計算掃描點的三維坐標值的；掃描點反射強度則可以用于給反射點匹配顏色。圖8 掃描系統(tǒng)示意圖如圖所示，以地面LiDAR測量的儀器中心為坐標原點，Y軸是儀器的固定方向，是儀器初始化時激光掃描的方向，Z軸為豎直向上方向，X軸通過右手坐標系來確定。由下面公式就可以計算出被掃描的點的三維空間坐標數(shù)據(jù)。 (23)地面LiDAR技術跟全站儀測量技術的定位原理是相同的，都是將儀器自身中心作為坐標原點，測出距離值和角度值，進行解算得出目標的三維坐標。兩者之間不同的地方是地面LiDAR技術是全自動地獲取面數(shù)據(jù)，而且密度很高，數(shù)據(jù)信息也更加豐富。地面LiDAR系統(tǒng),顧名思義,是選擇激光作為能源進行掃描測量的系統(tǒng)。該系統(tǒng)具有如下特點[4][12]：（1）快速性：激光掃描測量獲取到大面積目標的空間信息的速度很快。將激光掃描技術用于目標空間數(shù)據(jù)信息采集，能夠及時地測定出目標表面的三維信息，所以能夠在自動監(jiān)控行業(yè)內(nèi)應用。（2）非接觸性：地面LiDAR系統(tǒng)可以不需要接觸目標而完成掃描測量，獲取真實世界實體的三維坐標數(shù)據(jù)，能夠一次性完成從目標實體到三維點云數(shù)據(jù)的轉(zhuǎn)換，真正地做到了快速重構(gòu)原型。由于非接觸性的特點柔性目標測量、危險領域測量、人員不可到達位置的測量以及需要保護對象的測量的問題也得到了解決。（3）激光具有穿透性：激光具有穿透的特性，這使得獲取到的采樣點能夠描述出目標表面在不同層面上的幾何空間信息。（4）實時、動態(tài)與主動性：地面LiDAR系統(tǒng)是一個主動式的掃描系統(tǒng)，利用的是探測自身發(fā)射的激光脈沖，由回射的信號通過處理來描述目標信息，這給予了系統(tǒng)測量不會因時間和空間而受到影響的特點。系統(tǒng)發(fā)射的激光束可以近似看作平行光，不需要去擔心常規(guī)的光學照相測量中存在的光學變形誤差。這會更加完整地描述真是世界的場景和實體的空間形態(tài)及結(jié)構(gòu)屬性，采集到的三維數(shù)據(jù)也會更加具有實效、準確。（5）密度高、精度高：激光掃描能夠獲取目標的表面特征密度、精度都很高。有精密的傳感工藝支持，能自動立體地采集目標的立體結(jié)構(gòu)和表面結(jié)構(gòu)的數(shù)據(jù)。獲取的點云數(shù)據(jù)是由點的位置的三維坐標數(shù)據(jù)構(gòu)成，降低了傳統(tǒng)手段中由于人工的計算或推導帶來的不確定性?？梢酝ㄟ^點陣和一定密度的格網(wǎng)去描述實體的信息，采樣點之間的點距間隔可以設置。（6）自動化、數(shù)字化：系統(tǒng)掃描獲取的是數(shù)字距離信號，有這個全數(shù)字的特征，便更容易自動化地去顯示和輸出，可靠性也更好。在進行數(shù)據(jù)采集時，掃描系統(tǒng)采集和管理數(shù)據(jù)的軟件通過TCP/PI或平行連線接口及相應的驅(qū)動程序來控制掃描儀，處理軟件會對自動選擇目標的始點和終點，具有很好的建模處理、點云處理能力，其它的專業(yè)軟件還可以通過軟件開放的接口格式調(diào)用掃描的三維信息，與其它軟件也能兼容和互相操作。（7）地面LiDAR掃描系統(tǒng)能夠通過同步變化視距使得激光自動聚焦，改良了實際測量時的精度，在不同測距的散焦效應也提高了，更好地逼近實體原形。（8）系統(tǒng)配置的數(shù)碼相機能夠協(xié)助掃描工作，同步地進行遙控、監(jiān)測、拍照、選位、立體編輯等一系列的操作，易于現(xiàn)場目標的選擇、優(yōu)化，在復雜空間或不友好環(huán)境下也能更好地工作。在后期數(shù)據(jù)處理階段，利用圖片信息還能夠?qū)?shù)據(jù)進行調(diào)整、編輯、貼圖等操作。除此之外，軟件還能夠?qū)?shù)碼相機進行定向、參數(shù)校準和控制照片的采集等功能。這讓系統(tǒng)能夠帶色彩地去顯示云點數(shù)據(jù)。提供現(xiàn)場操作進行過攝像校準的功能，能夠及時解決現(xiàn)場發(fā)現(xiàn)的問題，降低了之后處理工作的不確定性，減少了返工的可能。（9）系統(tǒng)很少依賴目標環(huán)境和工作環(huán)境，具有抵御輻射、震動、潮濕的性質(zhì)，適應各種場景或野外的操作環(huán)境。系統(tǒng)提供了不同分辨率的掃描方式，可以重復地對物體進行掃描，用戶也就能夠自己選在掃描的精度。對全景空間采集的內(nèi)容的量及后期的處理中數(shù)據(jù)拼接的次數(shù)由掃描的次數(shù)來決定，用戶能夠自由控制工作量的大小。根據(jù)需要，用戶控制掃描的次數(shù)，可以改善因為拼接點云次數(shù)過多引起的空間變形以及拼接時差生的接縫誤差。（10）新型的掃描系統(tǒng)還裝備了GPS接收機或者其他的高精度定位裝置，在軟件平臺的內(nèi)部可以進行坐標轉(zhuǎn)換，將點云數(shù)據(jù)直接轉(zhuǎn)換成為大地坐標系下的坐標，更加方便使用。激光掃描儀掃描獲取的數(shù)據(jù)經(jīng)過格式轉(zhuǎn)換后，得到的點云數(shù)據(jù)格式如下：X（m）Y(m)H(m)………………………………這是最基礎的三維空間坐標數(shù)據(jù)，即點云數(shù)據(jù)。除了三維坐標屬性外還能夠加入其它的屬性數(shù)據(jù)，比如反射強度等等。所謂的點云，就是在相同的空間參考系下的一系列的表達目標空間分布和表面光譜特性的點集合。點云數(shù)據(jù)有很多自身的特點。第一，點云數(shù)據(jù)的內(nèi)容是分布在目標表面的大量三維點的坐標。所以點云反映的是目標表面的信息，并沒有內(nèi)部的信息。第二，點云數(shù)據(jù)的點呈現(xiàn)出離散分布的特點。點的位置和相互之間的間隔并沒有一定的分布規(guī)則，更加容易表達出目標物體的細節(jié)信息。第三，點云數(shù)據(jù)能夠直接獲取測量數(shù)據(jù)，比如三維坐標、距離等，還可以通過計算得到目標的表面積、體積等。第四，點云數(shù)據(jù)分布不均勻。不論是機載的LiDAR還是地面LiDAR，掃描出來的數(shù)據(jù)的分布都是不均勻的，原因有很多。機載LiDAR采用圓錐掃描時，掃描帶中間數(shù)據(jù)密度大，兩側(cè)數(shù)據(jù)密度小，對于其它的掃描方式也會不同程度的出現(xiàn)點云數(shù)據(jù)分布不均勻，同時由于地面目標地物的不同，也會造成數(shù)據(jù)分布不均勻。地面LiDAR也會由于目標的不同出現(xiàn)數(shù)據(jù)分布不均勻的情況。本章節(jié)介紹了點云數(shù)據(jù)的結(jié)構(gòu)以及特點，在研究點云數(shù)據(jù)的索引方式的時候需要考慮到數(shù)據(jù)的結(jié)構(gòu)和特點，據(jù)此來分析各種索引可能從哪些特點提高檢索效率。3 基于KD樹的LiDAR點云數(shù)據(jù)組織與管理KD樹索引是由Bentley在1975年提出的，主要用來對多屬性的數(shù)據(jù)或者多維的點數(shù)據(jù)進行檢索。KD樹是K（K2）維的二叉索引樹，但與二叉索引樹不同，它的每個結(jié)點表示的都是一個K維空間中的一個點。KD樹的每一層都需要一個分辨器，根據(jù)這個分辨器作出該層的分支決策，對于一棵KD樹，它的第i層的分辨器就是i mod k（根節(jié)點為0層，接下來依次遞增）。一棵非空的KD樹的性質(zhì)如下：（1）如果它的左子樹不是空樹，則左子樹上的所有結(jié)點的第d維的值都小于它的父結(jié)點第d維的值，右子樹是同理。（2）它的左右子樹也都是KD樹。圖 9 KD樹示意圖上圖是二維KD樹示意圖，根節(jié)點所在點為0層，分辨器是0 mod 2=0，即用x軸的值作為分支根據(jù)，A的左子樹B上所有點的x值都小于A的x值；A的右子樹C上所有點的x值都大于A的x值。接下來的其它層都依次類推。KD樹索引是二叉樹索引在多維空間的擴展，在具備為多維空間進行索引，進行精確點查找的同時，也繼承了二叉樹索引的優(yōu)點，平均查找長度為1+4logn。根據(jù)點云數(shù)據(jù)不規(guī)則分布的特點，KD樹索引是一種非常適合管理點云數(shù)據(jù)的索引方法。為了降低KD樹刪除的代價，中間點不存儲數(shù)據(jù)點，所有的數(shù)據(jù)點都存放在葉結(jié)點中。分割方式采用的是取最長軸中位數(shù)方法進行分割。KD樹的每個中間結(jié)點都需要有將這個結(jié)點所代表的子空間分割平面，分割平面會把這個空間分割成兩個字空間，結(jié)點的兩個子節(jié)點就代表了這兩個子空間，空間中所有的點也會分配到兩個子空間中。每次進行分割時，首先應該選定分割平面的法方向，然后選擇在哪個位置作為分割平面的位置，這會影響到兩個子空間占空間的比例，根據(jù)二叉樹索引的理想情況，分割完畢后應該會建立一個滿二叉樹索引，就是說在每次分割后，兩結(jié)點包含的點云數(shù)據(jù)的數(shù)量應該相等，所以在選取分割位置時，需要根據(jù)該層的分辨器，確定中位數(shù)，取中位數(shù)的位置作為分割面的位置。索引建立算法的步驟如下：1）設定閾值，確定葉結(jié)點所代表的空間中允許存在的點數(shù)量的最大值；2）建立根結(jié)點，存儲原點云點數(shù)量，計算點云數(shù)據(jù)在三個維度方向的方差值，取方差最大的維度方向作為根結(jié)點的分割面的法方向即初始的分辨器，接下來各層的分辨器隨層數(shù)增加而增加；3）判斷結(jié)點所代表的空間中包含的點數(shù)量是否小于閾值，若小于閾值，則將所有點數(shù)據(jù)存儲在結(jié)點中，否則進行4）；4）根據(jù)結(jié)點所在層的分辨器，確定中位數(shù)，即分割面的位置，將空間分割成兩個字空間，建立兩個新的結(jié)點表示對應的兩個子空間，依次對兩個結(jié)點進行3）；5)所有子空間所包含的點數(shù)量小于閾值后，建立索引成功。在根據(jù)算法進行編程實現(xiàn)的過程中，考慮到數(shù)據(jù)量非常大的情況，避免出現(xiàn)內(nèi)存不夠?qū)е碌某绦蜻\行失敗，建立索引的過程中并不移動數(shù)據(jù)，僅僅依據(jù)數(shù)據(jù)建立索引，在完成索引建立后，才將對應的數(shù)據(jù)存儲到相應的也葉子結(jié)點中。 K鄰近查找K鄰近查找在不同的索引中查找原理也都不相同?；贙D樹索引的特點，在進行K鄰近查找時，記錄下查找經(jīng)過的路徑，按路徑上每個結(jié)點所代表的子空間的分割面到查找點的距離進行排序，在找到目標區(qū)域后先對目標區(qū)域所包含的點進行計算，若查找的結(jié)果并不滿足一定的要求，則按排序后的結(jié)點進行查找，指導查找到的所有結(jié)果滿足查找的要求。K鄰近查找的步驟：1）確定所查找點的坐標及查找的鄰近點個數(shù)K；2）根據(jù)查找點坐標確定點所在的葉子結(jié)點所代表的子空間R，記錄查詢路徑，同時記錄查詢路徑上中間點所代表子空間的分割面到查找點的距離，并按從小到大排序Z；3）計算R中包含的點到查找點的距離，同時進行排序，取最近的K個點，若點的數(shù)量足夠K個點而且最遠的點的距離小于查詢路徑上最近的分割面的距離，則完成查詢，否則根據(jù)查詢路徑排序Z對相應的空間進行查找，對查找過的空間標號，若查找到的K個點滿足要求或者整個空間都查詢完成，這結(jié)束查詢。 算法測試算法測試的將數(shù)據(jù)按照數(shù)據(jù)量進行等級劃分，在沒給數(shù)量等級對若干個不同的點進行K鄰近查找，查找同一個點的時候，改變K值得出各種查詢方式的效率。本次驗證的數(shù)據(jù)選取了3組點云數(shù)據(jù)，3組數(shù)據(jù)都是由Riegl VZ1000三維激光掃描儀掃描學校建筑獲取的點云數(shù)據(jù)。測試數(shù)據(jù)1的數(shù)據(jù)量為541527個數(shù)據(jù)點；測試數(shù)據(jù)2的數(shù)據(jù)量為1002406個數(shù)據(jù)點；測試數(shù)據(jù)3的數(shù)據(jù)量為1531046個數(shù)據(jù)點算法測試運行環(huán)境是ASUS K43SV筆記本，處理器為Interl174。 Core? i52430M ，內(nèi)存為4G。在后面的集中算法的測試中也是在相同的環(huán)境下按同樣的測試方式進行算法測試。下面是KD樹索引測試結(jié)果（最佳查找耗時是在多次測試，設定不同的閾值的情況下得出的耗時最少的情況）。程序某次次查詢結(jié)果及耗時運行圖：KD樹索引測試結(jié)果：表2 KD樹算法測試最佳耗時表點數(shù)據(jù)量54152710024061531046K鄰近查找最佳耗時（s）10004000800012000就KD樹索引測試過程中獲得的完整數(shù)據(jù)來說，有以下幾條規(guī)律：1）數(shù)據(jù)量相同的情況下，閾值越大，索引建立時間越少；2）閾值相同的情況下，數(shù)據(jù)量越大，索引建立時間越長；3）閾值相同的情況下，查詢的數(shù)據(jù)量越大，查詢時間越長；4）查詢數(shù)據(jù)相同的情況下，閾值越大，查詢時間越長；5）閾值確定，在查詢數(shù)據(jù)量大于閾值耗時相比查詢數(shù)據(jù)量小于閾值會突然增長很多。本章節(jié)介紹了KD樹索引的原理以及基于KD樹索引對點云數(shù)據(jù)進行組織的方法，還介紹了索引建立和檢驗查找效率的K鄰近查找算法。進行了算法測試，得出了一些規(guī)律，也發(fā)現(xiàn)了KD樹索引在組織管理海量的數(shù)據(jù)時消耗的時間會大大增加，影響到查詢的效率。本章節(jié)所有的實現(xiàn)代碼已經(jīng)附在附錄中。4 基于八叉樹的LiDAR點云數(shù)據(jù)組織與管理Hunter在1978年首次提出了八叉樹索引結(jié)構(gòu)，這是由四叉樹向三維空間發(fā)展而發(fā)展出來的索引結(jié)構(gòu)。通過對三維空間的實體進行分割后，每個分割出來的子空間都具有相同的大小，通過循環(huán)遞歸地去劃分空間，將整個目標三維空間劃分為個相同大小的子空間，n為分割的次數(shù)。在八叉樹索引中，若是一棵非空的八叉樹，它必定包含八個子樹，而且每個子樹都是八叉樹。圖10 八叉樹示意圖八叉樹結(jié)構(gòu)是將包含點云數(shù)據(jù)的外包六面體按照八叉樹劃分的規(guī)則進行劃分（劃分的深度由設定的閾值決定），每次劃分通過點坐標同空間中心坐標的對比，分配到不同的子空間中，隨著遞歸劃分的深入，在子空間中的點數(shù)量小于閾值的時候，將被該子空間包含的點的數(shù)據(jù)存儲到葉結(jié)點中，劃分中途的“中間點”并不存儲點云數(shù)據(jù)。最后點云數(shù)據(jù)被分配到一定數(shù)量的子空間中。索引建立的算法步驟如下：1）設定索引的閾值，確定葉結(jié)點所代表的空間中允許存在的點數(shù)量的最大值；2）建立根結(jié)點R，計算原始點云的外包六面體邊長、中心點和包含的點云點數(shù)據(jù)數(shù)量并存儲在根結(jié)點中；3）若結(jié)點R代表的六面體空間包含的點數(shù)據(jù)數(shù)量小于閾值，則將該部分點云數(shù)據(jù)存儲在該結(jié)點中，否則進行4）；4）建立結(jié)點R的八個子結(jié)點，根據(jù)點云數(shù)據(jù)點相對于結(jié)點R中心點位置，將點云數(shù)據(jù)分配到八個子結(jié)點中，并存儲每個結(jié)點所代表的子空間的變長、中心點和數(shù)據(jù)點數(shù)量等信息，依次對每個子結(jié)點執(zhí)行3）；5）在所有點分配完畢后結(jié)束索引建立。與KD樹索引建立相似，八叉樹索引建立時，同樣不在建立過程中移動數(shù)據(jù)，只在最后完成索引建立后，才將數(shù)據(jù)存儲進相應的也葉子節(jié)點中。在編程實現(xiàn)八叉樹索引建立的過程中，為了便于進行K鄰近查找，對那些并不存在點數(shù)據(jù)的子空間也建立了結(jié)點去表示，防止因為查找的點在原點云數(shù)據(jù)中的位置區(qū)域沒有結(jié)點表示而阻礙了K鄰近查找。 K鄰近查找八叉樹的K鄰近查找與KD樹不同，根據(jù)八叉樹索引的特點，并不需要記錄查找點目標區(qū)域的路徑，只需要在查找