激光掃描系統(tǒng)能夠直接獲取被測目標(biāo)表面的三維空間坐標(biāo)，具有采樣密度高、點(diǎn)云分布密集等特點(diǎn)，正逐漸成為三維空間信息快速獲取的主要手段之一，被廣泛應(yīng)用于文物保護(hù)、三維重建、數(shù)字地面模型生產(chǎn)、城市規(guī)劃等領(lǐng)域^[1]?，F(xiàn)代車載激光掃描系統(tǒng)，通常安裝多個激光掃描頭采集三維點(diǎn)云數(shù)據(jù)，如Optech公司的LYNX系統(tǒng)，Riegl公司的VMX-450系統(tǒng)。車載激光掃描系統(tǒng)沿著某一軌跡采集數(shù)據(jù)，多個高頻采樣激光頭數(shù)據(jù)相互疊加，產(chǎn)生海量三維點(diǎn)云數(shù)據(jù)，其數(shù)據(jù)量隨著軌跡的延長而線性增加。例如，VMX-450系統(tǒng)在約一個小時內(nèi)，可獲取40 km左右長度的點(diǎn)云數(shù)據(jù)，數(shù)據(jù)量高達(dá)1 TB。對于車載激光掃描系統(tǒng)采集的海量三維點(diǎn)云數(shù)據(jù)，單在數(shù)據(jù)量方面即對后續(xù)數(shù)據(jù)處理(如點(diǎn)云濾波、分割，目標(biāo)識別，三維重建和可視化等)帶來巨大的挑戰(zhàn)。為實(shí)現(xiàn)海量點(diǎn)云數(shù)據(jù)的空間分析及可視化，需要實(shí)時、高效地完成點(diǎn)云數(shù)據(jù)的調(diào)度和查詢工作?？臻g數(shù)據(jù)的調(diào)度，關(guān)鍵在于數(shù)據(jù)的索引與檢索，索引的性能優(yōu)劣直接影響到系統(tǒng)的效率和分析能力。因此，如何建立合理的空間索引機(jī)制，是解決海量空間數(shù)據(jù)組織和快速調(diào)度的關(guān)鍵問題。許多標(biāo)志性索引方法已被廣泛應(yīng)用于空間數(shù)據(jù)的檢索、查詢、存儲以及管理，如四叉樹^[2]、R樹^[3, 4]、R*樹^[5]和八叉樹^[6]等。

在地理信息系統(tǒng)中，支持二維空間數(shù)據(jù)的索引方法已非常成熟。但是，隨著三維點(diǎn)云數(shù)據(jù)的廣泛應(yīng)用，迫切需要在虛擬地理環(huán)境下可視化全部三維點(diǎn)云數(shù)據(jù)。在三維點(diǎn)云數(shù)據(jù)可用性不斷增強(qiáng)的驅(qū)動下，出現(xiàn)了一些具有可視化和三維點(diǎn)云數(shù)據(jù)管理功能的商業(yè)軟件^[7, 8]。然而，Quick Terrain Reader、Point Tools等商業(yè)點(diǎn)云處理軟件對載入點(diǎn)云數(shù)據(jù)量有嚴(yán)格限制，不支持車載海量激光點(diǎn)云數(shù)據(jù)的實(shí)時三維可視化，從而引發(fā)了完善三維激光點(diǎn)云數(shù)據(jù)空間索引方法的熱潮。

R樹或R*樹的每個子塊包含一個對象，這些子塊可以彼此重疊。文獻(xiàn)^[9]提出利用三維 R 樹結(jié)構(gòu)管理虛擬環(huán)境下的三維建筑物。文獻(xiàn)^[10]提出使用三維 R 樹結(jié)構(gòu)快速索引激光點(diǎn)云數(shù)據(jù)。但是，如何有效解決R 樹子塊重疊是三維點(diǎn)云數(shù)據(jù)管理尚未解決的問題。四叉樹索引是一種基于樹的空間索引，它按照一定的規(guī)則，將已知范圍的空間遞歸地均分成4個部分，直到每個子塊滿足條件為止^[11]。文獻(xiàn)^[12]提出了一種基于四叉樹的三維點(diǎn)云渲染方法，此方法在假設(shè)連續(xù)點(diǎn)屬于同一條掃描線的前提下，只存儲每個葉子節(jié)點(diǎn)內(nèi)的點(diǎn)的位置以節(jié)省存儲空間。但是，這種方法無法對多掃描儀獲取的無序點(diǎn)云建立索引。八叉樹作為四叉樹的3D擴(kuò)展亦被廣泛應(yīng)用于三維數(shù)據(jù)索引。 文獻(xiàn)^[13]提出了基于八叉樹的三維點(diǎn)云數(shù)據(jù)的多尺度可視化方法。文獻(xiàn)^[14]提出了一種開源的八叉樹點(diǎn)云數(shù)據(jù)索引標(biāo)準(zhǔn)數(shù)據(jù)格式，并測試其在海量點(diǎn)云特征提取算法方面的適用性。文獻(xiàn)^[15]通過哈希表數(shù)據(jù)結(jié)構(gòu)優(yōu)化八叉樹結(jié)構(gòu)，實(shí)現(xiàn)三維點(diǎn)云數(shù)據(jù)的快速檢索。文獻(xiàn)^[16]設(shè)計(jì)了一種基于外存的多分辨率數(shù)據(jù)結(jié)構(gòu)，實(shí)現(xiàn)了海量點(diǎn)云數(shù)據(jù)的實(shí)時可視化與交互編輯 。一般情況下，基于八叉樹的樹結(jié)構(gòu)比較適合處理三維點(diǎn)云數(shù)據(jù)，并且該方法有現(xiàn)行開源標(biāo)準(zhǔn)數(shù)據(jù)格式^[14]。但是，對車載激光掃描系統(tǒng)采集的三維數(shù)據(jù)使用八叉樹索引具有分布不均等缺點(diǎn)，會出現(xiàn)大量空的葉節(jié)點(diǎn)。這直接造成了點(diǎn)云存儲空間的低利用率，并且增加了空間數(shù)據(jù)查詢的復(fù)雜度。相比四叉樹結(jié)構(gòu)，八叉樹結(jié)構(gòu)需要更多的存儲空間，更難實(shí)現(xiàn)?？焖贆z索算法通常需要耗費(fèi)較大的存儲空間，在時間和空間之間不能保持一個合理的平衡。KD樹索引在鄰域查找效率方面優(yōu)于八叉樹、四叉樹以及R 樹、R*樹索引結(jié)構(gòu)，常被用于單個激光點(diǎn)相鄰區(qū)域點(diǎn)云數(shù)據(jù)查找，但對于海量點(diǎn)云數(shù)據(jù)存儲管理與實(shí)時可視化，其鄰域關(guān)系的重建將耗費(fèi)大量的計(jì)算資源，整體效率低于八叉樹索引結(jié)構(gòu)^[14, 17]。

本文提出了一種基于內(nèi)外存調(diào)度的海量三維點(diǎn)云數(shù)據(jù)管理與實(shí)時可視化方法，用戶在臺式計(jì)算機(jī)或網(wǎng)絡(luò)環(huán)境下可以流暢地檢索和可視化三維點(diǎn)云。由于區(qū)域四叉樹是最重要、應(yīng)用最廣泛的四叉樹表示法^[18]，對幾何空間的劃分沒有重疊，通過特定的編碼可以快速查找?guī)缀螀^(qū)域所在的行列，同時還可以根據(jù)空間對象的稠密程度來確定空間數(shù)據(jù)的分辨率。因此，本文在解決海量三維激光點(diǎn)云數(shù)據(jù)的可視化時，采用雙層區(qū)域四叉樹方法對數(shù)據(jù)建立索引，實(shí)現(xiàn)海量激光點(diǎn)云數(shù)據(jù)的管理與動態(tài)調(diào)度。

區(qū)域四叉樹是將有邊界的幾何空間劃分為連續(xù)的4個相同大小的區(qū)域，遞歸劃分該區(qū)域?yàn)?個相同大小的較小的區(qū)域，直到得到的區(qū)域僅包含一個幾何對象(見圖 1)。若被劃分區(qū)域根據(jù)相應(yīng)的判別條件被判別為最小劃分單元，那么該區(qū)域?qū)⒉辉倮^續(xù)劃分。

圖 1 四叉樹平面分割及其結(jié)構(gòu)圖Fig. 1 Quad-Tree Plane Segmentation and its Structure Diagram

圖選項(xiàng)

激光掃描點(diǎn)云數(shù)據(jù)處理的首要步驟就是三維點(diǎn)云數(shù)據(jù)的檢索和可視化。海量點(diǎn)云數(shù)據(jù)處理的一個難點(diǎn)是如何克服臺式計(jì)算機(jī)有限的內(nèi)存存儲空間。為實(shí)現(xiàn)三維點(diǎn)云數(shù)據(jù)的快速可視化，本文提出的方案滿足以下條件：

1) 利用高效的數(shù)據(jù)索引快速檢索點(diǎn)云數(shù)據(jù)；

2) 將點(diǎn)云數(shù)據(jù)從外部磁盤動態(tài)加載到計(jì)算機(jī)的主存儲器中；

3) 多細(xì)節(jié)層次(levels of detail,LoD)可視化三維點(diǎn)云。

車載激光掃描系統(tǒng)采集的三維點(diǎn)云一般存儲在LAS文件中^[19]，該文件記錄每個激光點(diǎn)的坐標(biāo)和強(qiáng)度。存儲千萬點(diǎn)級別的LAS文件可能達(dá)到GB級。車載激光掃描系統(tǒng)通常沿著某一軌跡(街道、高速公路等)采集三維點(diǎn)云。獲得的三維點(diǎn)云可能覆蓋了一個較大的范圍區(qū)域，而其中僅有一小部分區(qū)域包含點(diǎn)云數(shù)據(jù)(見圖 2)。

圖 2 車載激光掃描系統(tǒng)采集的激光點(diǎn)云Fig. 2 A Snapshot of MMS Collecting Point Clouds

圖選項(xiàng)

激光掃描的目的不僅僅是進(jìn)行可視化，為了使獲取的三維激光掃描數(shù)據(jù)具有較好的查詢性能，應(yīng)該對點(diǎn)云數(shù)據(jù)進(jìn)行有效的管理和檢索。但是，如果建立四叉樹、R樹或者八叉樹來索引LAS文件中的點(diǎn)云數(shù)據(jù)，將會導(dǎo)致大量空的葉節(jié)點(diǎn)和無效的存儲空間。為了解決這一難題，首先將三維點(diǎn)云沿著掃描路徑分成一系列連續(xù)區(qū)域塊，每塊僅包含一部分?jǐn)?shù)據(jù)。這樣可以通過減少空的葉節(jié)點(diǎn)來節(jié)約索引文件的存儲空間，并有效減少索引樹高度，可提高檢索性能以及點(diǎn)云加載的速度。

本文提出的方法首先將采集到的三維點(diǎn)云分割成連續(xù)的矩形塊，對每個矩形內(nèi)的點(diǎn)用區(qū)域四叉樹進(jìn)行索引，然后對全部矩形塊進(jìn)行四叉樹索引。利用雙層四叉樹結(jié)構(gòu)組織三維點(diǎn)云的關(guān)鍵步驟為：

1) 設(shè)置最小矩形塊的大小(比如300 m×200 m)。當(dāng)前車載激光掃描儀的最大掃描范圍約為150 m。

2) 采用內(nèi)存映射文件技術(shù)訪問磁盤上的LAS數(shù)據(jù)文件，實(shí)現(xiàn)LAS數(shù)據(jù)的分塊讀入，分塊建立四叉樹并記錄每塊的空間范圍<x_min,y_min,x_max,y_max >，不對LAS文件執(zhí)行直接I/O操作或內(nèi)容緩存，降低應(yīng)用程序?qū)?a title="操作系統(tǒng)知識庫" target="_blank" style="color:#df3434; font-weight:bold;">操作系統(tǒng)的內(nèi)存需求。

3) 構(gòu)建四叉樹文件索引所有的矩形塊，建立樹的集群，并按照樹之間的相互關(guān)系建立統(tǒng)一的數(shù)據(jù)檢索入口(見圖 3)。

圖 3 三維點(diǎn)云的雙層四叉樹結(jié)構(gòu)Fig. 3 A Two-Level Quad-Tree Data Structure for 3D Point Clouds

圖選項(xiàng)

4) 存儲每塊數(shù)據(jù)文件和相關(guān)聯(lián)的四叉樹索引文件。

雙層四叉樹結(jié)構(gòu)由上述4個步驟完成(見圖 3)。第一層四叉樹管理所有的矩形塊，第二層四叉樹管理每個矩形塊內(nèi)的數(shù)據(jù)點(diǎn)。與LAS文件相比較，每個數(shù)據(jù)塊只包含一小部分點(diǎn)云數(shù)據(jù)，存儲體積小，能夠快速地從硬盤加載到計(jì)算機(jī)主存儲器中。數(shù)據(jù)塊之間無塊間數(shù)據(jù)內(nèi)容關(guān)聯(lián)，搭建索引服務(wù)器亦可實(shí)現(xiàn)海量點(diǎn)云文件的分布式存儲管理。

由于計(jì)算機(jī)內(nèi)存的限制，無法一次性將所有矩形塊內(nèi)的點(diǎn)云數(shù)據(jù)加載到計(jì)算機(jī)主存儲器中。可視化的首要步驟是判別可見或近可見的矩形塊，然后，判斷當(dāng)前視景體中的激光點(diǎn)集。矩形塊的可見性與用戶在三維場景中的視景體范圍相關(guān)，一旦確定了視景體的覆蓋范圍，依據(jù)構(gòu)建的第一級四叉樹結(jié)構(gòu)，就可判斷出可見矩形塊。最后加載可見矩形塊中的激光點(diǎn)到計(jì)算機(jī)主存儲器，以便進(jìn)一步的可視化。

當(dāng)用戶以漫游方式瀏覽三維點(diǎn)云時，矩形塊的可見性發(fā)生快速變化，近可見的矩形塊從磁盤加載到主存儲器中，不可見的矩形塊從主存儲器內(nèi)刪除。不同矩形塊之間的平滑過渡至關(guān)重要，否則，很難實(shí)現(xiàn)海量點(diǎn)云數(shù)據(jù)的快速可視化。為了滿足這一要求，設(shè)計(jì)鄰近矩形塊緩存機(jī)制，通過快速檢索并加載可視和近可視點(diǎn)到可視化緩存區(qū)完成視點(diǎn)移動中的場景平滑過渡。在加載過程中，分配B₁和B₂兩個緩存區(qū)。緩存區(qū)B₁存儲可見矩形塊中的點(diǎn)云，緩存區(qū)B₂存儲近可見矩形塊中的點(diǎn)云。當(dāng)可見矩形塊變?yōu)椴豢梢姇r，緩存區(qū)B₂與內(nèi)存交換以實(shí)現(xiàn)可視化；緩存區(qū)B₁和緩存區(qū)B₂內(nèi)的點(diǎn)云輪流交換到視頻內(nèi)存，從而進(jìn)行不同矩形塊之間的平滑過渡。

與地形LoD可視化相比，三維點(diǎn)云的LoD可視化要簡單得多。由于每個矩形塊都有限定范圍<x_min,y_min,x_max,y_max >，以計(jì)算得到的可見矩形塊到視點(diǎn)的距離以及可視葉節(jié)點(diǎn)到視點(diǎn)的距離作為選擇三維點(diǎn)云LoD層次的依據(jù)。本文方法將計(jì)算得到的距離分成6個區(qū)間，分別為[0 m,100 m]、[100 m,300 m]、[300 m,700 m]、[700 m,1 500 m]、[1 500 m,2 500 m]、[2 500 m,+∞]。對可視葉節(jié)點(diǎn)內(nèi)的點(diǎn)云數(shù)據(jù)根據(jù)距離間隔進(jìn)行采樣。設(shè)計(jì)位于6個間隔區(qū)間內(nèi)的激光點(diǎn)分別按原始點(diǎn)的100%、90%、80%、70%、50%和40%進(jìn)行采樣，從而在保證運(yùn)行效率的前提下實(shí)現(xiàn)無明顯變化的動態(tài)渲染。該方法實(shí)現(xiàn)動態(tài)LoD是空間點(diǎn)云密度自適應(yīng)的，用較高的密度渲染較近的點(diǎn)，用較低的密度渲染較遠(yuǎn)的點(diǎn)，從而形成對場景的分層表達(dá)。

本文利用C++語言實(shí)現(xiàn)海量車載激光掃描點(diǎn)云數(shù)據(jù)的快速索引、動態(tài)調(diào)度以及LoD場景表達(dá)，利用OpenGL渲染機(jī)對場景進(jìn)行繪制。實(shí)驗(yàn)數(shù)據(jù)為海南某高速公路3.7千萬個車載激光掃描點(diǎn)。實(shí)驗(yàn)環(huán)境為Intel Core i7 870(2.93 GHz)處理器、3 GB內(nèi)存、GT220顯卡。為驗(yàn)證算法性能，將本文算法與海量激光點(diǎn)云索引管理與八叉樹索引方法^[14]進(jìn)行對比。八叉樹索引方法的實(shí)現(xiàn)使用其提供的開源軟件包3DTK^[20]。

索引建立階段，對原始點(diǎn)云文件創(chuàng)建雙層四叉樹索引并存儲為文件，用于管理三維點(diǎn)云數(shù)據(jù)。本文四叉樹索引方法與八叉樹索引方法在建立文件索引耗時、耗內(nèi)存方面進(jìn)行比較的結(jié)果如圖 4所示。八叉樹索引方法^[14]耗費(fèi)最大內(nèi)存2.1 GB，消耗時間為559 s。雙層四叉樹索引耗費(fèi)最大內(nèi)存為1.3 GB，消耗時間只需337 s。雙層四叉樹結(jié)構(gòu)較八叉樹結(jié)構(gòu)簡單，計(jì)算復(fù)雜度小，在同等代碼實(shí)現(xiàn)效率下，四叉樹索引在構(gòu)建速度方面明顯優(yōu)于八叉樹。在計(jì)算資源消耗方面，八叉樹索引方法需要把全部點(diǎn)讀入內(nèi)存后才能建立八叉樹，數(shù)據(jù)大小與消耗內(nèi)存呈線性關(guān)系，構(gòu)建索引內(nèi)存消耗隨數(shù)據(jù)量的增加而升高。本文提出的雙層四叉樹方法在內(nèi)存消耗上呈連續(xù)馬鞍狀，內(nèi)存消耗峰值穩(wěn)定，不隨數(shù)據(jù)量的增加而不斷上升，優(yōu)于八叉樹索引方法。本文方法建立索引內(nèi)存消耗可控，使用雙層四叉樹方法結(jié)構(gòu)建立索引需要消耗的內(nèi)存與點(diǎn)云數(shù)據(jù)大小無關(guān)，具有對超內(nèi)存存儲量點(diǎn)云數(shù)據(jù)建立數(shù)據(jù)索引的能力。

圖 4 建立數(shù)據(jù)索引消耗的資源與時間比較Fig. 4 Comparison of Time and Ram Consumptionat Building Index Stage

圖選項(xiàng)

在數(shù)據(jù)瀏覽階段，本文方法與Elseberg八叉樹索引方法內(nèi)存消耗比較如圖 5所示?；诎瞬鏄渌饕姆椒ㄏ牡膬?nèi)存為492 MB，使用本文方法消耗的內(nèi)存約為50 MB。本文方法不用把數(shù)據(jù)一次性讀入內(nèi)存，內(nèi)存消耗較少。由于八叉樹索引為整體索引結(jié)構(gòu)，需要一次性讀入全部數(shù)據(jù)，數(shù)據(jù)大小與消耗內(nèi)存以及讀入時間成線性關(guān)系。當(dāng)輸入數(shù)據(jù)過于龐大時，基于八叉樹的方法無法載入數(shù)據(jù)或載入速率非常緩慢。圖 6為利用本文方法與基于八叉樹的方法在瀏覽幀率方面的比較。雙層四叉樹索引結(jié)構(gòu)、多線程動態(tài)數(shù)據(jù)調(diào)度以及LoD技術(shù)的綜合使用降低了海量激光點(diǎn)云數(shù)據(jù)可視化對硬件帶來的壓力，瀏覽幀速度大幅度優(yōu)于八叉樹索引方法。

圖 5 數(shù)據(jù)漫游內(nèi)存消耗比較Fig. 5 Comparison of Data Roaming Ram Consumption

圖選項(xiàng)

圖 6 數(shù)據(jù)漫游幀率比較Fig. 6 Comparison of Rendering Performance

圖選項(xiàng)

圖 7為三維點(diǎn)云動態(tài)可視化例圖。實(shí)驗(yàn)證明，本文提出的方法在內(nèi)存消耗和可視化速度方面有較好的性能，更有利于海量點(diǎn)云數(shù)據(jù)的實(shí)時可視化。與八叉樹索引方法相比，本文的雙層四叉樹結(jié)構(gòu)具有更簡單的數(shù)據(jù)結(jié)構(gòu)，更容易實(shí)現(xiàn)和維護(hù)。本文方法首先將三維點(diǎn)云分成連續(xù)的矩形塊，利用四叉樹管理所有的矩形塊，然后構(gòu)建每個矩形塊的四叉樹數(shù)據(jù)結(jié)構(gòu)。這種分而治之的策略使點(diǎn)云數(shù)據(jù)動態(tài)加載更加簡單而有效。此外，每個矩形塊的四叉樹數(shù)據(jù)結(jié)構(gòu)較容易保持良好的平衡，并具有相對較低的樹高度，有效減少了構(gòu)建索引的內(nèi)存與時間消耗，并提高了查詢速度。實(shí)驗(yàn)結(jié)果表明，本文方法實(shí)現(xiàn)了高效率的海量三維點(diǎn)云管理與實(shí)時可視化。

圖 7 三維點(diǎn)云動態(tài)可視化Fig. 7 Dynamic Visualization of 3D Point Clouds