張 蕊，李廣云，王 力，李明磊

(1． 信息工程大學，河南 鄭州 450052； 2． 華北水利水電大學，河南 鄭州 450045)

一、引 言

海量激光點云數據的存儲和處理技術是目前地理信息系統(tǒng)和測量系統(tǒng)的一個重要研究方向。由車載系統(tǒng)所獲取的建筑物坐標數據或三維激光掃描系統(tǒng)所獲取的實測場景數據一般為全離散矢量距離點構成的“點云”數據[1]，為給后期點云數據的高效處理做準備，目前傳統(tǒng)的技術是預先基于內存對點云構建索引以實現數據的有效存儲[2-3]，當每個數據文件只有KB或MB時，該技術效果顯著。

然而對于海量離散點云數據，數量級達到了GB或甚至為TB，并由于單機內存的限制，無法再根據傳統(tǒng)的基于全內存的方法對數據進行處理。文獻[4—7]中提出了幾種基于外存或數據庫的數據存儲方法，無法滿足點云數據后期處理過程中的交互需求[8]。為達到在現有計算機硬件水平下進行海量點云數據快速處理的效果，近年來計算機領域延伸和發(fā)展了許多新技術，其中以Google的GFS和Hadoop的HDFS(hadoop distributed file system)最為著名，本文基于HDFS對海量點云數據文件的分塊策略提出了新的方法。

二、基于Hadoop的HDFS存儲系統(tǒng)

大數據技術包括大數據的存儲、計算、管理到恢復等多個方面。其中大數據的存儲策略是大數據高效處理過程中需要解決的首要關鍵問題。Hadoop/MapReduce在大數據存儲與數據處理方面扮演著重要的角色。Hadoop是一個基于云計算平臺的分布式系統(tǒng)基礎架構，是一個用來處理大規(guī)模數據的軟件平臺，能可靠地存儲和處理PB級數據，且可通過普通機器組成的服務集群來存儲和處理數據，服務集群可達數千個節(jié)點[8]。

Hadoop是一種典型的主從式結構，主要由HDFS和MapReduce組成，其結構如圖1所示。其中HDFS負責對海量數據進行分布式存儲，具有可靠性高、擴展性強、成本低等優(yōu)勢，它的開源性、高容錯性及可以部署在廉價的硬件設備上的特點是其成為云存儲研究的熱點之一[9]。

圖1 Hadoop基礎架構

文件系統(tǒng)是支持上層應用的基礎。Hadoop由于有HDFS在底層作支撐，可以方便地實現“計算向存儲的遷移”，這與傳統(tǒng)的并行處理技術MPI(message passing interface)有本質區(qū)別，處理TB或PB級的海量數據具有很大的優(yōu)勢。HDFS分布式文件系統(tǒng)體系結構如圖2所示，HDFS由一個名字節(jié)點(Namenode)和多個數據節(jié)點(Datanode)組成。Namenode是集群中的中心服務器，負責管理文件系統(tǒng)的命名空間(Namespace)以及客戶端對文件的訪問。數據節(jié)點通常是多個，一個節(jié)點運行一個數據節(jié)點進程，負責管理它所在節(jié)點上的數據存儲[10]。

圖2 HDFS體系結構

三、海量激光點云數據的數據結構

為描述由激光掃描儀所測量的各個掃描點的詳細信息，本文把點云數據的數據結構設計為

(ID,ρ,θ,α,x,y,z,I,nx,ny,nz,R,G,B)

如圖3所示，由此可獲得掃描點極坐標(ρ,θ,α)，根據極坐標原理即可得掃描點P的三維坐標

(1)

I表示回光強度；nx、ny、nz表示由點P的KNN擬合出曲面獲取的法向三分量，如圖4所示；R、G、B表示相機采集照片貼圖后每點的色彩信息。

圖3 激光掃描儀三維坐標系

圖4 法向三分量示意圖

基于激光點云數據的特點，并結合海量數據的存儲技術，本文提出底層采用基于Hadoop的分布式文件系統(tǒng)HDFS存儲數據，在存儲文件之前需要對文件進行分塊處理，采用的分塊方法直接影響對數據的處理和檢索效率。

四、文件分塊策略

在文件分布式存儲過程中，文件分割是其中一個關鍵步驟。HDFS采用了 64 MB的固定文件分塊大小，這個尺寸遠遠大于傳統(tǒng)文件系統(tǒng)的分塊甚至是文件的大小，每個塊及其副本都以普通Linux文件的形式保存在塊服務器上。如何在文件分布式存儲時對文件進行分割，將文件以最優(yōu)分塊大小進行存儲，是海量數據存儲的一項核心技術，本文對此提出了3種解決方案。

1. 定長分塊(fixed-size partition，FSP)

FSP是通過HDFS配置好的塊大小對文件進行切分，對文件中的激光點云數據進行順序掃描，將點云數據按水平方向均勻分割為若干個大小的數據塊，然后將每個數據塊分別存儲在HDFS系統(tǒng)中的各個數據節(jié)點上，把對一個文件的訪問請求轉變?yōu)閷Χ鄠€文件分塊的訪問請求，從而達到系統(tǒng)負載均衡，提高數據的高吞吐率。

FSP算法的優(yōu)點是簡單、性能高，但它對數據插入和刪除非常敏感，處理十分低效，不能根據內容變化作調整和優(yōu)化。

2. 變長分塊(content-defined partition，CDP)

CDP是將文件分割成長度大小不等的分塊策略。文獻[11]提出制定一個分組因子向量，當需要存儲文件時，先得到該文件的大小，通過將文件大小與分組因子進行比較，得到最優(yōu)分塊大小。

本文考慮基于文件內容對文件進行數據切分，對不同物體掃描的數據存放在不同的數據塊中。CDP最大的好處為對同一物體掃描得到的數據被分割到一個數據塊中，對數據進行讀取時只需訪問當前塊，無需訪問多個數據塊。但此方法有可能會引起有的數據塊過大，而有的數據塊過小。

春天就要來臨了，這群地球上有名的長途旅行家也要開始為每年的春季大遷徙做準備了。每年春季的3—4月，夏季的7—8月，是馴鹿家族的遷徙時間。那時候，家族中的老老少少齊動身，憑著驚人的耐受力開始路途遙遠的大遷徙。

3. 混合分塊法

如果變長分塊方法可行，能否把定長分塊和變長分塊結合起來，充分發(fā)揮二者的優(yōu)勢，彌補各自的缺陷，是需要研究的另一個難點。

五、試驗結果與分析

本文采用的測試環(huán)境為具有6個節(jié)點的服務集群，其中一臺為NameNode，五臺為DataNode，硬件環(huán)境CPU為Intel core i5-3230M 2.6 GHz，3級緩存，內存8 GB，網絡100 Mbps LAN。數據文件大小375.274 MB，存儲了4個模型的三維點云數據，點數為9 854 757。然后，先后采用傳統(tǒng)方法(即不分塊)、定長分塊和變長分塊方法分別對測試數據進行處理，試驗結果如下所述。

1．傳統(tǒng)方法試驗

4個模型的三維點云放在一個文件中，不分塊，處理過程為：

1) 讀取第一個模型的數據；

2) 按八叉樹進行劃分；

3) 每個點在八叉樹中尋找KNN，按最小二乘平面擬合計算點法向；

4) 按步驟1)—3)依次處理其余三部分數據，處理結果見表1。

表1 用傳統(tǒng)方法對點云數據進行處理

2． FSP試驗

4個模型的三維點云按每塊64 MB進行切分，共分為6塊，最后一塊大小為54.849 MB，處理過程為：

1) 6個數據塊存儲在一組DataNode中；

2) 每個節(jié)點進程需要判斷是否從相鄰數據塊中讀取數據(本塊中的當前塊數據是否完全)，然后將完整的數據塊按八叉樹進行劃分；

3) 各個進程中數據塊中的各點在相應八叉樹中尋找KNN，計算點法向；

4) 一個節(jié)點可能包含多個塊的部分數據，依次執(zhí)行步驟1)—3)，處理結果見表2。

3． CDP試驗

4個模型的三維點云按內容進行切分，共分為4個數據塊，對點云數據進行讀取時只需訪問當前塊，處理過程為：

1) 4個數據塊分別存儲在一組DataNode中；

2) 每個節(jié)點進程都將所處理數據按八叉樹進行劃分；

3) 各個數據塊中各點在相應八叉樹中尋找KNN，計算點法向，處理結果見表3。

表2 用FSP法對點云數據進行處理

表3 用CDP法對點云數據進行處理

由試驗結果可以看出，對點云數據進行分塊存儲的效果明顯優(yōu)于傳統(tǒng)方法。

六、后續(xù)工作

對海量數據的存儲是大數據處理的第一步，存儲策略的選擇直接影響到對海量數據的計算和處理效率。對其他數據存儲技術，如數據復制、數據壓縮、重復數據刪除及存儲虛擬化技術等是后續(xù)需要研究的工作。

其次，原始的數據存放在HDFS分布式文件系統(tǒng)中，而用戶習慣通過某種DBMS(database management system)來存取數據。因為這樣能夠隱藏文件系統(tǒng)底層技術，方便對數據的管理和用戶操作，可采用分布式數據庫系統(tǒng)HBase存取數據，對數據表中數據進行分區(qū)處理的海量數據管理技術是后續(xù)需要研究的一個重點。

七、結束語

HDFS文件系統(tǒng)對海量數據進行分布式存儲，具有可靠性高、擴展性強、成本低等優(yōu)勢，正好滿足當前海量激光點云數據的存儲需求。本文首先構建了海量激光點云數據的數據結構，在此基礎上提出了3種海量點云數據文件的分塊方法，并通過仿真試驗驗證了定長分塊和按內容分塊的有效性，對于混合分塊方法的有效性需進一步研究和驗證。

參考文獻：

[1] 李婕,鐘若飛,趙文吉. 車載激光點云海量數據的管理與快速顯示[J].系統(tǒng)仿真學報，2008,20(S1):33-39.

[2] 謝洪.基于地面三維激光掃描技術的海量點云模型重建關鍵算法研究[D].鄭州：信息工程大學，2013.

[3] 黃先鋒,陶闖,江萬壽，等.機載激光雷達點云數據的實時渲染[J]. 武漢大學學報：信息科學版，2005，30(11)：975-978.

[4] KlEIN J, KROKOWSKI J, FISCHER M. The Randomized Sample Tree： a Data Structure for Interactive Walkthroughs in Externally Stored Virtual Environments[C]∥Proceedings of the ACM Symposium on Virtual Reality Software and Technology.[S.l.]:VRST,2002:137-146.

[5] 王晏民,郭明.大規(guī)模點云數據的二維與三維混合索引方法[J]. 測繪學報，2012，41(4):605-612.

[6] BOUBEKEUR T, SCHLICK C. Interactive Out-of-core Texturing with Point-sampled Textures[C]∥Proceedings of the 3rd Eurographics.[S.l.]:IEEE,2006:67-73.

[7] PAJAROLA R. Stream-processing Points[C]∥Proc. VIS’05.[S.l.]:IEEE,2005:239-246.

[8] 邰建華. Hadoop平臺下的海量數據存儲技術研究[D]. 大慶：東北石油大學，2012:1-8.

[9] 王永洲.基于HDFS的存儲技術的研究[D]. 南京：南京郵電大學， 2013:13-44.

[10] 張為民,唐劍鋒,羅治國,等. 云計算深刻改變未來[M]. 北京：科學出版社，2009.

[11] 李暉, 樊凱, 王康,等. 云存儲系統(tǒng)中可變分塊大小的塊數據分塊方法:中國,201110350575 [P]. 2012-06-20.