三維空間格網(wǎng)的多尺度整數(shù)編碼與數(shù)據(jù)索引方法

賴廣陵，童曉沖，丁 璐，秦志遠(yuǎn)

1. 信息工程大學(xué)地理空間信息學(xué)院，河南 鄭州 450001； 2. 河南城建學(xué)院，河南 平頂山 467036

隨著傳感器技術(shù)的發(fā)展，數(shù)據(jù)獲取手段的不斷增加，傳統(tǒng)的二維數(shù)據(jù)已經(jīng)逐漸不能滿足用戶的需求，LiDAR、城市模型、地下管網(wǎng)、空間動(dòng)態(tài)目標(biāo)及氣象海洋等三維空間數(shù)據(jù)的研究和應(yīng)用越來越多。三維空間數(shù)據(jù)具有體量大、種類多、類型復(fù)雜及尺度多樣等特點(diǎn)，導(dǎo)致其組織和管理的難度越來越大，因此，如何圍繞三維空間信息的管理，設(shè)計(jì)一種有效的空間索引計(jì)算方法是亟待解決的難題。

三維空間區(qū)域劃分是建立空間編碼與索引的基礎(chǔ)。一般而言，三維空間索引的研究方法與二維空間索引相似，多數(shù)為二維空間向三維空間的推廣，如二維空間劃分索引中有規(guī)則格網(wǎng)、四叉樹、不規(guī)則R樹等，與之對(duì)應(yīng)，三維空間有三維格網(wǎng)、八叉樹、三維不規(guī)則R樹等?，F(xiàn)階段常用的空間索引按照其對(duì)劃分后空間的實(shí)現(xiàn)方法的不同，大致可以分成兩大類：

(1) 空間樹狀索引。經(jīng)典的空間樹狀索引有KD樹[1-2]、八叉樹[3-6]、R樹及其變種樹[7-12]、R樹相關(guān)改進(jìn)算法[13-14]和K-D-B樹[15]、QR樹[16-17]等組合索引方法?？臻g樹狀索引能夠與對(duì)象的空間分布相適應(yīng)，但是受樹深的影響較大，且動(dòng)態(tài)維護(hù)困難。采用空間樹狀索引管理不同尺度尤其是尺度差異較大的數(shù)據(jù)時(shí)存在較大的局限性，因?yàn)椴煌叨葘?duì)應(yīng)于不同深度的數(shù)據(jù)，容易導(dǎo)致查詢路線變長(zhǎng)，耗時(shí)更多，且查詢不平衡。R樹及其改進(jìn)樹雖然具備比較好的多尺度信息管理能力，但是由于R樹是一種平衡樹，導(dǎo)致其更新和維護(hù)的成本較高，其索引結(jié)構(gòu)本身的復(fù)雜性導(dǎo)致索引所占空間巨大，一定程度上影響了它的有效性，特別是在三維空間中，一些高動(dòng)態(tài)的對(duì)象及其更新的處理，會(huì)直接降低R樹的效率。

(2) 空間編碼索引?？臻g編碼索引是建立在空間格網(wǎng)劃分基礎(chǔ)上的一種順序結(jié)構(gòu)，適用于空間信息組織管理，能夠快速實(shí)現(xiàn)對(duì)象的多尺度編碼，且可以根據(jù)格網(wǎng)與目標(biāo)之間的對(duì)應(yīng)關(guān)系，實(shí)現(xiàn)對(duì)象的快速訪問和關(guān)系計(jì)算[18]。經(jīng)典的空間編碼索引有規(guī)則格網(wǎng)[19-20]、空間填充曲線[21]、多級(jí)格網(wǎng)[22-23]及自適應(yīng)格網(wǎng)[24]等。從編碼的方法來看，空間編碼索引主要分為兩種：一種是采用變長(zhǎng)的字符串/數(shù)組對(duì)格網(wǎng)進(jìn)行編碼。該方法中，不同位上的數(shù)/字符代表不同尺度/層級(jí)的格網(wǎng)，通過字符串/數(shù)組的長(zhǎng)度來確定劃分深度，在操作上需要涉及數(shù)組循環(huán)與下標(biāo)操作，在海量數(shù)據(jù)計(jì)算中，存在局限性，如多級(jí)格網(wǎng)等。另一種是采用定長(zhǎng)的數(shù)對(duì)格網(wǎng)進(jìn)行編碼，再通過增加額外的信息實(shí)現(xiàn)尺度/深度編碼，如空間填充曲線或規(guī)則格網(wǎng)等。該方法利用空間排序確定單尺度格網(wǎng)的編碼，并附加上尺度/深度信息，由于尺度和編碼分離，因此在對(duì)空間區(qū)域進(jìn)行查詢時(shí)，需要同時(shí)考慮編碼和尺度兩個(gè)因素，運(yùn)算復(fù)雜度較高。

問題：能否在現(xiàn)有空間編碼索引的基礎(chǔ)上，設(shè)計(jì)一種同時(shí)顧及尺度與空間的定長(zhǎng)整數(shù)編碼，使其能夠有效地規(guī)避現(xiàn)有方法存在的問題，實(shí)現(xiàn)基于單整數(shù)的計(jì)算而無須多字段或者逐字段的處理。筆者所在團(tuán)隊(duì)于2016年針對(duì)一維的時(shí)間信息，提出了一種新型的多尺度剖分和整數(shù)編碼方法[25]，并提供了完全基于位操作的計(jì)算方法，極大地提升了時(shí)間信息的多尺度計(jì)算的效率。參照上述一維編碼的多尺度整數(shù)化方法，本文針對(duì)三維空間提出了一種多尺度的整數(shù)編碼方法，采用整數(shù)編碼代替?zhèn)鹘y(tǒng)空間坐標(biāo)來對(duì)格網(wǎng)進(jìn)行組織和管理，目的是實(shí)現(xiàn)三維多尺度格網(wǎng)的編碼及高效的空間檢索和計(jì)算。

1 三維多尺度整數(shù)編碼設(shè)計(jì)方案

首先給出幾個(gè)基本概念：

三維單尺度整數(shù)編碼(three dimensions single-scale integer coding，TDSIC)指的是采用整數(shù)統(tǒng)一地對(duì)單一尺寸格網(wǎng)構(gòu)成的空間區(qū)域進(jìn)行編碼，建立整數(shù)與格網(wǎng)坐標(biāo)之間的一一對(duì)應(yīng)關(guān)系。

三維多尺度整數(shù)編碼(three dimensions multi-scale integer coding，TDMIC)指的是采用整數(shù)統(tǒng)一地對(duì)多種尺寸格網(wǎng)構(gòu)成的空間區(qū)域進(jìn)行編碼，建立整數(shù)與格網(wǎng)坐標(biāo)之間的一一對(duì)應(yīng)關(guān)系。

三維空間整數(shù)化編碼設(shè)計(jì)是在利用格網(wǎng)對(duì)空間區(qū)域進(jìn)行剖分的基礎(chǔ)上進(jìn)行的，充分利用計(jì)算機(jī)處理的優(yōu)勢(shì)，采用整數(shù)對(duì)空間區(qū)域中的每一個(gè)格網(wǎng)進(jìn)行編碼，僅通過位域操作和加減運(yùn)算即能實(shí)現(xiàn)空間數(shù)據(jù)編碼與計(jì)算，既考慮了編碼的可行性也兼顧了編碼運(yùn)算的高效性。下面主要從三維單尺度整數(shù)編碼的設(shè)計(jì)和三維多尺度編碼的設(shè)計(jì)兩個(gè)方面進(jìn)行敘述。

1.1 三維單尺度整數(shù)編碼的設(shè)計(jì)

對(duì)整個(gè)三維的研究空間(定義為0級(jí)空間)進(jìn)行八叉劃分，將空間等分成8個(gè)相同的子空間，再將每個(gè)子空間繼續(xù)劃分為8個(gè)相同的更高級(jí)別的子空間，如此遞歸下去，直到達(dá)到規(guī)定的最高層級(jí)N-1級(jí)，共N級(jí)。

常見的三維空間不同的編碼方式有Z序編碼、H序編碼、Gray序編碼等。本文方法理論上支持各種排序編碼方法。在眾多的編碼方式中，Z序編碼和H序編碼的應(yīng)用最為廣泛，由于Z序編碼可以利用Mordon碼[26]的方式，快速形成行列編碼，對(duì)編碼在高維空間的平移計(jì)算具有較大的優(yōu)勢(shì)。除此之外，Z編碼在維數(shù)變化、網(wǎng)格排序及P-賦范距離等方面性能均優(yōu)于H序編碼[27]，這些優(yōu)勢(shì)也被代入多尺度化的Z序編碼計(jì)算中。因此，本文采用三維的Z曲線對(duì)空間區(qū)域進(jìn)行填充，每一級(jí)具體的編碼規(guī)則如圖1所示，具體敘述如下。

從圖1中可以看出該編碼是由一系列整數(shù)構(gòu)成的一維Z形曲線。采用一個(gè)mbit的整數(shù)(在x64的機(jī)器上m=64，可以根據(jù)系統(tǒng)位數(shù)不同進(jìn)行調(diào)整或者利用內(nèi)存拼接進(jìn)行擴(kuò)展，本文以m=64說明編碼方法)來進(jìn)行編碼，為了確定每一個(gè)格網(wǎng)對(duì)應(yīng)整數(shù)的值，需要建立整數(shù)與格網(wǎng)局部坐標(biāo)的對(duì)應(yīng)關(guān)系，設(shè)格網(wǎng)局部坐標(biāo)為(x,y,z)，其中x,y,z均為不小于0的整數(shù)。為了充分使用存儲(chǔ)空間，滿足編碼結(jié)構(gòu)簡(jiǎn)單、高效及多尺度編碼的需求，設(shè)計(jì)了格網(wǎng)坐標(biāo)系，其坐標(biāo)結(jié)構(gòu)體如表1所示。

圖1 單尺度編碼示意圖[26]Fig.1 Illustration of single-scaled coding[26]

表1 格網(wǎng)坐標(biāo)結(jié)構(gòu)體

由于需要將64 bit的整數(shù)平均分配給X、Y、Z3個(gè)坐標(biāo)軸(與編碼交叉取位有關(guān))，則每一個(gè)坐標(biāo)軸的取值范圍為0～221-1即0～2 097 151，如表1所示。

根據(jù)Z形編碼的結(jié)構(gòu)特點(diǎn)，在進(jìn)行編碼時(shí)，可以通過交叉取位的方法來獲取每一個(gè)格網(wǎng)的整數(shù)編碼，即先將十進(jìn)制的X、Y、Z坐標(biāo)轉(zhuǎn)換成二進(jìn)制編碼，均為21位，不足的用0補(bǔ)齊，然后再按照Z、Y、X的順序，依次取位，組成一個(gè)63位的二進(jìn)制編碼，最后將該編碼轉(zhuǎn)換成十進(jìn)制的整數(shù)，即實(shí)現(xiàn)了單尺度整數(shù)編碼。如格網(wǎng)坐標(biāo)為(2,0,2)對(duì)應(yīng)的編碼計(jì)算步驟如下：①對(duì)應(yīng)的二進(jìn)制編碼(10,00,10)；②采用三維Mordon[26]交叉取位得到101000；③得到十進(jìn)制整數(shù)編碼40。

前文所提方法只需通過位操作就能建立三維單尺度編碼，具有高效的特點(diǎn)，但是這種編碼方法只能對(duì)一個(gè)層級(jí)的格網(wǎng)進(jìn)行編碼，格網(wǎng)的尺寸固定，無法同時(shí)對(duì)不同尺度的格網(wǎng)進(jìn)行編碼。而在對(duì)一個(gè)場(chǎng)景進(jìn)行表達(dá)時(shí)，一般都需要用到多個(gè)尺度的格網(wǎng)信息，對(duì)于細(xì)節(jié)層次要求高的地方要采用小尺寸的格網(wǎng)；反之，則需要采用大尺度的格網(wǎng)。因此，在實(shí)際的應(yīng)用過程中，需要有多個(gè)尺度的格網(wǎng)協(xié)同工作，這就要求編碼方法具有多尺度的特性。

1.2 三維多尺度整數(shù)編碼的設(shè)計(jì)

為了解決單尺度整數(shù)編碼存在不能表達(dá)多尺度信息的缺點(diǎn)，在三維單尺度整數(shù)編碼的基礎(chǔ)之上，提出了一種多尺度的編碼方法。其核心思想是用一個(gè)64 bit的整數(shù)將不同尺度下的格網(wǎng)編碼同時(shí)在空間和尺度層上進(jìn)行排序，通過整數(shù)運(yùn)算體現(xiàn)編碼的層級(jí)及格網(wǎng)間的空間關(guān)系。

(1) 不同尺度整數(shù)編碼后的排序應(yīng)該和單一尺度網(wǎng)格編碼排序在空間上前后關(guān)系保持一致。

(2) 不同尺度整數(shù)編碼后應(yīng)該能體現(xiàn)不同尺度網(wǎng)格間的包含層級(jí)關(guān)系。例如：空間中任意一個(gè)三維網(wǎng)格整數(shù)編碼應(yīng)該能夠通過運(yùn)算，快速得到包含該網(wǎng)格內(nèi)所有三維網(wǎng)格編碼的整數(shù)區(qū)間，并且是連續(xù)的。

基于上述目標(biāo)，三維多尺度整數(shù)編碼TDMIC的設(shè)計(jì)采用下面的基本思路：在單尺度整數(shù)編碼基礎(chǔ)上，對(duì)單尺度的編碼的整數(shù)值×2(左移1位)，得到多尺度編碼中最大尺度(層級(jí)最大，分辨率最高)的編碼值。很明顯，在這一個(gè)層級(jí)中的整數(shù)編碼值均為偶數(shù)，空出了所有的奇數(shù)值，后續(xù)層級(jí)的編碼都在此層的基礎(chǔ)之上產(chǎn)生，并且利用的就是空出的奇數(shù)值。具體是將每相鄰的8個(gè)編碼值取平均，就可以得到下一個(gè)層級(jí)中的編碼值，依此類推，便實(shí)現(xiàn)了場(chǎng)景的多尺度整數(shù)編碼，原理如圖2所示。這樣設(shè)計(jì)的目的主要是為了將尺度和空間信息同時(shí)編碼，一方面順序體現(xiàn)了單一尺度格網(wǎng)的排序，另一方面也體現(xiàn)了尺度間的順序，還可以通過編碼值的大小關(guān)系，保證父單元和子單元的包含關(guān)系。其產(chǎn)生方法如下：

第1步：按照1.1節(jié)中方法建立三維單尺度整數(shù)編碼。

第2步：將通過第1步計(jì)算得到的整數(shù)編碼值都乘以2，即左移一位，得到第21層也就是基礎(chǔ)層級(jí)的編碼值。由此可見，這一個(gè)層級(jí)的編碼值均為偶數(shù)，相鄰編碼值之差為2。

第3步：實(shí)現(xiàn)多尺度編碼其他層級(jí)編碼值的計(jì)算。以第21層為基礎(chǔ)，每8個(gè)相鄰的值為一組取平均值，得到第20層的編碼值；然后以第20層為基礎(chǔ)，每8個(gè)編碼值為一組取平均值，得到第19層的編碼。依次類推，便可得到每一個(gè)層級(jí)的編碼值。很明顯，除基礎(chǔ)層以外，其余各層的編碼值均為奇數(shù)。

圖2 多尺度編碼示意圖Fig.2 Illustration of the formation of a multi-scalar code

根據(jù)編碼原理，對(duì)多尺度編碼的性質(zhì)進(jìn)行了歸納，約定符號(hào)如表2所示，具體描述如下：

三維多尺度整數(shù)編碼層級(jí)范圍

0≤N≤21

(1)

三維多尺度整數(shù)編碼第N層編碼間隔

ΔTDMC(N)=264-3·N=1?(64-N?1-N)

(2)

三維多尺度整數(shù)編碼第N層第0個(gè)編碼值

TDMC(N,0)=263-3·N-1=

(1?(63-N?1-N))-1

(3)

三維多尺度整數(shù)編碼第N層第i個(gè)編碼值

TDMC(N.i)=TDMC(N.0)+iΔTDMC(N)

(4)

三維多尺度整數(shù)編碼第N層i的取值范圍

0≤i≤23N-1 (5)

根據(jù)三維多尺度整數(shù)編碼的原理及性質(zhì)可知，三維多尺度整數(shù)編碼方法其本質(zhì)是一顆倒立的八叉樹。對(duì)空間區(qū)域建立三維多尺度整數(shù)編碼，所有的編碼值會(huì)形成一個(gè)整數(shù)集合，將集合中的整數(shù)作為輸入，建立B樹、B+樹索引或其他一維索引，由于整數(shù)本身就包含了空間順序和尺度順序，因此只需對(duì)該集合進(jìn)行一維排序(從大到小或從小到大)，就可以形成多尺度空間信息的存儲(chǔ)與索引方式，將尺度三維+尺度空間的索引問題轉(zhuǎn)換為一維索引進(jìn)行解決，從而達(dá)到提高效率的目的。

2 三維多尺度整數(shù)編碼計(jì)算方法

三維多尺度整數(shù)編碼計(jì)算指的是利用位域操作及加減運(yùn)算實(shí)現(xiàn)編碼的空間關(guān)系計(jì)算。本節(jié)結(jié)合三維多尺度整數(shù)編碼的特點(diǎn)，重點(diǎn)研究了編碼層級(jí)運(yùn)算、編碼與格網(wǎng)坐標(biāo)轉(zhuǎn)化運(yùn)算、父單元查詢及子單元查詢等基礎(chǔ)運(yùn)算。其中，編碼層級(jí)計(jì)算是進(jìn)行編碼運(yùn)算的基礎(chǔ)，編碼與格網(wǎng)坐標(biāo)轉(zhuǎn)換運(yùn)算是建立多尺度整數(shù)編碼與三維空間聯(lián)系的關(guān)鍵，父、子單元查詢可以用于確定編碼間的空間關(guān)系。

2.1 編碼層級(jí)運(yùn)算

多尺度編碼具有多個(gè)層級(jí)，不同的層級(jí)編碼數(shù)值不一樣，相應(yīng)的格網(wǎng)尺寸也不一樣。因此，在進(jìn)行多尺度編碼以后，任意給定一個(gè)編碼，在使用過程中，需要確定的就是編碼層級(jí)。設(shè)多尺度編碼的數(shù)值為Mc，總層級(jí)為N，其算法原理描述如下[25]：

首先需要判斷編碼值Mc的奇偶性，如果為偶數(shù)，則位于基礎(chǔ)層級(jí)，如果為奇數(shù)則需要進(jìn)一步的計(jì)算，主要是計(jì)算Mc-1與Mc+1最近的相同父單元，即數(shù)值Mid=(Mc-1)∧(Mc+1)左邊有多少位為0，從而達(dá)到計(jì)算層級(jí)的目的。

具體實(shí)現(xiàn)步驟敘述如下：

(1) 若Mc為偶數(shù)，則有Mc&1=0，可得層級(jí)N=21。

(2) 若Mc為奇數(shù)，通過異或運(yùn)算計(jì)算整數(shù)Mid=(Mc-1)∧(Mc+1)，其目的是計(jì)算Mc-1和Mc+1前面高位有多少位是相同的，找這兩個(gè)多尺度整數(shù)編碼最近的相同父編碼。

(3) 通過分支方法確定整數(shù)Mid(64 bit)左邊有多少位是0，計(jì)算多尺度整數(shù)編碼Mc的層級(jí)N。首先令N=0：

① 利用0xFFFFFFFF00000000取Mid的高位，然后右移32位得到Mid0，判斷Mid0是否為0。若Mid0≠0，則Mid=Mid0，N不變；否則，Mid=Mid&0x00000000FFFFFFFF，N=32。

② 利用0xFFFF0000取Mid的高位，然后右移16位得到Mid0，判斷Mid0是否為0。若Mid0≠0，則Mid=Mid0，N不變；否則，Mid=Mid&0x0000FFFF，N=N+16。

③ 利用0xFF00取Mid的高位，然后右移8位得到Mid0，判斷Mid0是否為0。若Mid0≠0，則Mid=Mid0，N不變；否則，Mid=Mid&0x00FF，N=N+8。

④ 利用0xF0取Mid的高位，然后右移4位得到Mid0，判斷Mid0是否為0。若Mid0≠0，則Mid=Mid0，N不變；否則，Mid=Mid&0x0F，N=N+4。

⑤ 利用0xC取Mid的高位，然后右移2位得到Mid0，判斷Mid0是否為0。若Mid0≠0，則Mid=Mid0，N不變；否則，Mid=Mid&0x3，N=N+2。

⑥ 利用0x2取Mid的高位，然后右移1位得到Mid0，判斷Mid0是否為0。若Mid0≠0，則Mid=Mid0，N不變；否則，Mid=Mid&0x1，N=N+1。

⑦ 對(duì)按以上步驟計(jì)算得到的N進(jìn)行轉(zhuǎn)換得到層級(jí)n，所用公式如下

n=(N·0xAAAABBBB)?33

(6)

2.2 編碼與格網(wǎng)坐標(biāo)轉(zhuǎn)換運(yùn)算

三維多尺度整數(shù)編碼在格網(wǎng)場(chǎng)景應(yīng)用的過程中，需要快速地進(jìn)行編碼與格網(wǎng)坐標(biāo)之間的轉(zhuǎn)換，即根據(jù)編碼，實(shí)現(xiàn)格網(wǎng)坐標(biāo)的快速計(jì)算。格網(wǎng)坐標(biāo)的計(jì)算首先需要確定該編碼所在的層級(jí)，進(jìn)而確定該編碼對(duì)應(yīng)的基礎(chǔ)層級(jí)子單元編碼對(duì)應(yīng)的體素坐標(biāo)，最終根據(jù)多尺度生成的規(guī)則(8個(gè)相鄰的體合并得到上一層級(jí)的單元)通過移位操作計(jì)算得到格網(wǎng)坐標(biāo)。設(shè)多尺度編碼值為Mc，則有計(jì)算方法和步驟如下：

(1) 計(jì)算編碼的層級(jí)N。編碼所在的層級(jí)決定了相應(yīng)格網(wǎng)的尺寸，也是進(jìn)行編碼轉(zhuǎn)換的基礎(chǔ)，可以采用上述層級(jí)計(jì)算的方法快速得到給定編碼的層級(jí)N。

(2) 將編碼轉(zhuǎn)換到基礎(chǔ)層級(jí)編碼上，并計(jì)算得到編碼范圍，取最小編碼值Mcmin。三維多尺度整數(shù)編碼由三維單尺度整數(shù)編碼發(fā)展而來。因此，要實(shí)現(xiàn)多尺度編碼與格網(wǎng)坐標(biāo)之間的轉(zhuǎn)換，首先需要找到該編碼對(duì)應(yīng)的基礎(chǔ)層級(jí)編碼。

Mcmin=Mc-1?(63-N-N-N)+1

(7)

(3) 將最小編碼值轉(zhuǎn)換為單尺度編碼。通過第二步計(jì)算得到基礎(chǔ)層級(jí)對(duì)應(yīng)的編碼以后，根據(jù)式(8)，可以計(jì)算得到單尺度編碼的值Sc

Sc=Mcmin?1

(8)

(4) 計(jì)算得到單尺度編碼對(duì)應(yīng)的格網(wǎng)坐標(biāo)(i,j,k)。由1.1節(jié)中內(nèi)容可知，根據(jù)格網(wǎng)的坐標(biāo)，通過交叉取位的方式可以計(jì)算得到單尺度編碼值。同樣的，根據(jù)編碼值，可以通過逆向交叉取位的方法計(jì)算得到相應(yīng)的格網(wǎng)坐標(biāo)。

(5) 計(jì)算得到第N層的格網(wǎng)坐標(biāo)(Ni,Nj,Nk)。完成上述步驟，計(jì)算得到單尺度編碼對(duì)應(yīng)的格網(wǎng)坐標(biāo)以后，只需要進(jìn)行移位計(jì)算就可以得到多尺度編碼對(duì)應(yīng)格網(wǎng)的坐標(biāo)，計(jì)算方法如下

(9)

2.3 父單元查詢

利用格網(wǎng)對(duì)空間區(qū)域進(jìn)行多尺度表達(dá)時(shí)，需要找到與小尺寸格網(wǎng)位置關(guān)系相對(duì)應(yīng)的大尺度格網(wǎng)，在不影響表達(dá)效果的前提下，用大尺度格網(wǎng)代替小格網(wǎng)，減少數(shù)據(jù)量，提高效率。

根據(jù)編碼生成規(guī)則可知，父單元查詢的關(guān)鍵在于計(jì)算查詢層級(jí)的起始編碼值與相對(duì)于起始編碼值的編碼間隔，通過這兩個(gè)量即可實(shí)現(xiàn)父單元的查詢。

已知多尺度整數(shù)編碼Mc，需要查詢層級(jí)為N′(N′≤N)的父單元FMc，具體步驟如下：

(1) 計(jì)算第N′層編碼中的第1個(gè)整數(shù)編碼oTN′,根據(jù)式(10)可以得到

oTN′=1?(63-N′?1-N′)-1

(10)

(2) 計(jì)算第N′級(jí)的父單元編碼相對(duì)于第一個(gè)編碼的間隔ΔFMc

ΔFMc=(Mc?(64-N′-N′-N′))?

(64-N′-N′-N′)

(11)

(3) 計(jì)算第N′級(jí)的父單元編碼FMc

FMc=ΔFMc+oTN′

(12)

2.4 子單元查詢

在格網(wǎng)的應(yīng)用過程中，需要根據(jù)編碼對(duì)其子單元進(jìn)行查找，確定編碼間對(duì)應(yīng)的空間關(guān)系；在進(jìn)行三維表達(dá)時(shí)，由于視點(diǎn)的變化，也需要用小尺度的格網(wǎng)，來代替大尺度的格網(wǎng)，使得表達(dá)效果更加的逼真。

給定一個(gè)多尺度整數(shù)編碼值Mc，相應(yīng)的層級(jí)為N，計(jì)算其包含所有第N′的整數(shù)編碼NT,其中N′≥N。

由于多尺度整數(shù)編碼在整數(shù)排序上，滿足包含關(guān)系，進(jìn)行子單元查詢時(shí)，只需要確定多尺度編碼對(duì)應(yīng)的范圍即可。若層級(jí)為N的整數(shù)值，包含最小尺度的范圍[A,B]，則有

A≤NT≤B

(13)

A=Mc-(oTN+1)+1

(14)

B=Mc+(oTN+1)-1

(15)

式中，oTN表示第N層第0個(gè)編碼值，可由式(3)計(jì)算得到。

對(duì)于特定層級(jí)子單元的查詢，只需在計(jì)算A和B在該層級(jí)對(duì)應(yīng)的父單元即能實(shí)現(xiàn)。

3 試驗(yàn)與分析

為了驗(yàn)證三維多尺度編碼多尺度轉(zhuǎn)換及區(qū)域查詢的效率，本文共設(shè)計(jì)了兩組試驗(yàn)。試驗(yàn)1為多尺度轉(zhuǎn)換試驗(yàn)，通過統(tǒng)計(jì)編碼向不同尺度轉(zhuǎn)換消耗的時(shí)間，驗(yàn)證多尺度轉(zhuǎn)換的效率；試驗(yàn)2為與Oracle Spatial的對(duì)比試驗(yàn)，從數(shù)據(jù)導(dǎo)入、索引建立及區(qū)域查詢3個(gè)方面進(jìn)行對(duì)比，驗(yàn)證三維多尺度整數(shù)編碼在這3個(gè)方面的效率。試驗(yàn)環(huán)境如下：

硬件為Intel(R)Core(TM) i5-4590 CPU(3.1 GHz)，8 GB，硬盤為1 TB；操作系統(tǒng)為Windows 7 64 bit；編譯環(huán)境為Visual Studio 2013，Release版本，x64，c++，數(shù)據(jù)庫版本：Oracle 11.2.0.1.0。

3.1 三維單尺度編碼與三維多尺度編碼轉(zhuǎn)換試驗(yàn)

三維多尺度整數(shù)編碼的優(yōu)勢(shì)很大一部分在于其多尺度性，因此需要對(duì)單尺度到多尺度編碼之間的轉(zhuǎn)換效率進(jìn)行測(cè)試。試驗(yàn)1就是為了實(shí)現(xiàn)這個(gè)目的而設(shè)計(jì)。試驗(yàn)數(shù)據(jù)采用的是模擬數(shù)據(jù)，隨機(jī)生成格網(wǎng)坐標(biāo)作為試驗(yàn)數(shù)據(jù)，格網(wǎng)坐標(biāo)范圍與前文設(shè)計(jì)的體素坐標(biāo)范圍一致，具有一般性，其試驗(yàn)流程如下：隨機(jī)生成n個(gè)格網(wǎng)坐標(biāo)(每一個(gè)坐標(biāo)軸坐標(biāo)的取值范圍為0～2 097 151)；對(duì)生成的n個(gè)格網(wǎng)坐標(biāo)進(jìn)行三維單尺度整數(shù)編碼；分別將生成的n個(gè)三維單尺度整數(shù)編碼轉(zhuǎn)換為第21層、第19層、第17層以及第15層的三維多尺度整數(shù)編碼，并分別統(tǒng)計(jì)消耗的時(shí)間；分別將上述轉(zhuǎn)換結(jié)果轉(zhuǎn)換為單尺度編碼，并分別統(tǒng)計(jì)消耗的時(shí)間。

將n分別取8 000 000、27 000 000、64 000 000，分別進(jìn)行10次試驗(yàn)，取平均值，最終統(tǒng)計(jì)信息如表3所示。

表3 三維單尺度整數(shù)編碼與三維多尺度整數(shù)編碼轉(zhuǎn)換效率比較

由試驗(yàn)結(jié)果可知：三維多尺度整數(shù)編碼每一層的轉(zhuǎn)換效率是一樣的，在三維單尺度整數(shù)編碼與三維多尺度整數(shù)編碼相互轉(zhuǎn)換的過程中，與轉(zhuǎn)換的層級(jí)無關(guān)，只與轉(zhuǎn)換編碼個(gè)數(shù)相關(guān)，其時(shí)間復(fù)雜度為O(n)。

3.2 與Oracle Spatial進(jìn)行對(duì)比試驗(yàn)

本文重點(diǎn)強(qiáng)調(diào)多尺度整數(shù)編碼方法對(duì)多尺度數(shù)據(jù)的組織優(yōu)勢(shì)，因此，選擇R樹作為對(duì)比對(duì)象，一是R樹著重解決的就是多種不同尺度對(duì)象的混合索引問題；二是R樹是現(xiàn)階段空間格網(wǎng)數(shù)據(jù)的管理中應(yīng)用最廣泛的索引，便于與其他類型的索引進(jìn)行橫向?qū)Ρ?；三是R樹能夠有效地組織和管理不同尺度的三維空間數(shù)據(jù)[28-32]，也是目前最主要的商業(yè)化三維空間數(shù)據(jù)索引代表。其中Oracle從9i開始通過Oracle Spatial組件提供了對(duì)三維R樹的支持，其實(shí)質(zhì)是將二維R樹拓展到了三維空間，它能夠很好地解決了高維空間區(qū)域查找的問題，擁有較高的查詢效率。

為了驗(yàn)證三維多尺度編碼的可靠性，設(shè)計(jì)了與Oracle Spatial的對(duì)比試驗(yàn)，從數(shù)據(jù)導(dǎo)入、索引建立及區(qū)域查詢3個(gè)方面進(jìn)行比較。其具體原理如下所示：

假設(shè)整個(gè)空間的尺度為0～21層，按照第21層的格網(wǎng)最小粒度為單位1，以此定義坐標(biāo)。

(1) 根據(jù)層級(jí)要求，隨機(jī)生成字符串，字符串的有效數(shù)值為0～7(按照遞歸八分的方式劃分空間，由于每一個(gè)格網(wǎng)都將被劃分為8份，因此只需0～7之間的整數(shù)即能實(shí)現(xiàn)劃分后每一個(gè)格網(wǎng)的標(biāo)識(shí))，每一個(gè)字符串對(duì)應(yīng)一個(gè)格網(wǎng)，其中字符串中的有效數(shù)值個(gè)數(shù)n表示相應(yīng)格網(wǎng)的層級(jí)為第n層，字符串中的第i個(gè)數(shù)j表示第i層的第j個(gè)格網(wǎng)。如字符串431表示的含義為：該字符串對(duì)應(yīng)第3層的格網(wǎng)，表示的是第1層的第4個(gè)格網(wǎng)，第1層的第4個(gè)格網(wǎng)在第2層八分中的第3個(gè)格網(wǎng)，第2層格網(wǎng)基礎(chǔ)上在第3層上八分的第1個(gè)格網(wǎng)，如圖3所示。由此可見，字符串唯一確定了格網(wǎng)的位置。

圖3 數(shù)據(jù)生成原理圖Fig.3 The data generation scheme

(2) 根據(jù)生成的字符，生成格網(wǎng)對(duì)應(yīng)的多尺度整數(shù)編碼值和相應(yīng)的8個(gè)頂點(diǎn)坐標(biāo)分別作為多尺度整數(shù)編碼和Oracle Spatial的試驗(yàn)數(shù)據(jù)。其中生成跨度為3個(gè)尺度(第7層—第9層)、5個(gè)尺度(第7層—第11層)、10個(gè)尺度(第7層—第16層)、15個(gè)尺度(第7層—第21層)的數(shù)據(jù)各1000萬條、15個(gè)尺度(第7層—第21層)的數(shù)據(jù)各1000萬條、2000萬條、5000萬條、7000萬條以及1億條(每條數(shù)據(jù)對(duì)應(yīng)一個(gè)格網(wǎng)信息，對(duì)于多尺度整數(shù)編碼來說是一個(gè)編碼值，對(duì)于Oracle Spatial而言指的是8個(gè)頂點(diǎn)坐標(biāo))。

(3) 將上述數(shù)據(jù)分別導(dǎo)入數(shù)據(jù)庫中，并統(tǒng)計(jì)數(shù)據(jù)導(dǎo)入時(shí)間以及建立索引的時(shí)間。

(4) 任意選擇1000個(gè)第n1—n2層的不同大小的格網(wǎng)范圍作為查詢區(qū)域，分別進(jìn)行查詢，對(duì)比Oracle Spatial和多尺度整數(shù)編碼的效率，統(tǒng)計(jì)總時(shí)間，再求平均。

其中，數(shù)據(jù)導(dǎo)入時(shí)間信息如表4和圖4所示。

表4 數(shù)據(jù)導(dǎo)入時(shí)間對(duì)比

圖4 數(shù)據(jù)導(dǎo)入時(shí)間對(duì)比Fig.4 Comparison of data import times

設(shè)計(jì)對(duì)比試驗(yàn)導(dǎo)入數(shù)據(jù)時(shí)，由于多尺度整數(shù)編碼導(dǎo)入的是一個(gè)64 bit的整數(shù)，而Oracle Spatial導(dǎo)入的數(shù)據(jù)為相應(yīng)的格網(wǎng)范圍，即8個(gè)頂點(diǎn)坐標(biāo)，數(shù)據(jù)量本身就要大于多尺度整數(shù)編碼，因此耗時(shí)較長(zhǎng)，具體如表4和圖4所示。

表4統(tǒng)計(jì)了兩種不同的數(shù)據(jù)導(dǎo)入數(shù)據(jù)庫的時(shí)間信息。圖4是表4中信息的直觀表示，其中圖4(a)表示兩種方式下相同數(shù)據(jù)量不同層級(jí)跨度的數(shù)據(jù)導(dǎo)入時(shí)間對(duì)比，對(duì)應(yīng)表中1—4組試驗(yàn)；圖4(b)表示不同數(shù)據(jù)量，相同層級(jí)跨度的數(shù)據(jù)導(dǎo)入時(shí)間對(duì)比，對(duì)應(yīng)表中4—8組試驗(yàn)。綜合分析圖表可知：

圖4(a)中曲線平穩(wěn)，在導(dǎo)入數(shù)據(jù)量不變的情況下，消耗的時(shí)間基本保持不變，而圖4(b)中曲線均勻變化，在層級(jí)不變的情況下，導(dǎo)入數(shù)據(jù)消耗的時(shí)間隨數(shù)據(jù)量的增加而增加，呈正相關(guān)，而且Oracle Spatial數(shù)據(jù)導(dǎo)入時(shí)間的曲線斜率大于多尺度整數(shù)編碼,約為多尺度整數(shù)編碼的2倍。由此可以得出，兩種方式的數(shù)據(jù)導(dǎo)入時(shí)間與層級(jí)無關(guān)，與數(shù)據(jù)量正相關(guān)，且Oracle Spatial方式數(shù)據(jù)導(dǎo)入時(shí)間長(zhǎng)于多尺度整數(shù)編碼，且隨數(shù)據(jù)量增加變化更加明顯。

按照設(shè)計(jì)的方案進(jìn)行試驗(yàn)，可以得到兩種方式建立oracle索引的時(shí)間對(duì)比信息，如表5和圖5 所示。

表5 建立索引時(shí)間統(tǒng)計(jì)

表5統(tǒng)計(jì)了兩種不同方式建立索引的時(shí)間信息。圖5是表5中信息的直觀表示，其中圖5(a)表示兩種方式下相同數(shù)據(jù)量不同層級(jí)跨度建立索引的時(shí)間對(duì)比，對(duì)應(yīng)表中1—4組試驗(yàn)；圖5(b)表示不同數(shù)據(jù)量，相同層級(jí)跨度建立索引的時(shí)間對(duì)比，對(duì)應(yīng)表中4—8組試驗(yàn)。綜合分析圖表可知：

(1) 圖5(a)中曲線平穩(wěn)，在數(shù)據(jù)量相同的情況下，兩種方式建立索引的時(shí)間基本保持不變，而圖5(b)中兩條曲線均勻變化，在層級(jí)不變的情況下，建立索引消耗的時(shí)間隨數(shù)據(jù)量的增加而增加，呈正相關(guān)，且Oracle Spatial的曲線斜率大于多尺度整數(shù)編碼。由此可以看出，兩種方式建立索引的時(shí)間與層級(jí)無關(guān)，與數(shù)據(jù)量正相關(guān)，且Oracle Spatial隨數(shù)據(jù)量的增加，建立索引消耗的時(shí)間越大，而多尺度編碼建立索引時(shí)間隨數(shù)據(jù)量的變化則比較平穩(wěn)。

圖5 建立索引時(shí)間對(duì)比Fig.5 Comparison between index construction times

(2) 從圖5(a)和圖5(b)中兩種方式建立索引的時(shí)間對(duì)比可以看出，影響多尺度整數(shù)編碼與Oracle Spatial導(dǎo)入數(shù)據(jù)時(shí)間的因素相同，但是多尺度整數(shù)編碼建立索引消耗的時(shí)間明顯少于Oracle Spatial。

綜合分析可以得到，在索引的建立和更新的過程中，多尺度編碼要優(yōu)于R樹，更加適用于三維動(dòng)態(tài)數(shù)據(jù)的索引。

按照上述原理進(jìn)行試驗(yàn)，可以得到兩種方式給定區(qū)域范圍查詢的時(shí)間對(duì)比信息，如表6和圖6 所示。

表6 查詢時(shí)間對(duì)比

圖6 查詢時(shí)間對(duì)比Fig.6 Comparison between query times

表6統(tǒng)計(jì)了兩種不同方式給定相同的區(qū)域進(jìn)行查詢消耗的時(shí)間信息。圖6是表6中信息的直觀表示，其中圖6(a)表示兩種方式下相同數(shù)據(jù)量不同層級(jí)跨度給定區(qū)域查詢消耗的時(shí)間信息對(duì)比，對(duì)應(yīng)表中1—4組試驗(yàn)；圖6(b)表示不同數(shù)據(jù)量，相同層級(jí)跨度給定區(qū)域查詢消耗的時(shí)間對(duì)比，對(duì)應(yīng)表中4—8組試驗(yàn)。綜合分析圖表可知：

(1) 圖6(a)中多尺度整數(shù)編碼曲線平穩(wěn)，在數(shù)據(jù)量不變的情況下，多尺度整數(shù)編碼查詢消耗的時(shí)間基本保持不變，而Oracle Spatial曲線均勻變化，在數(shù)據(jù)量不變的情況下，Oracle Spatial查詢消耗的時(shí)間隨層級(jí)跨度的增大而變長(zhǎng)。圖6(b)中Oracle Spatial對(duì)應(yīng)曲線均勻變化，在層級(jí)不變的情況下，建立索引消耗的時(shí)間隨數(shù)據(jù)量的增加而增加，呈正相關(guān)，而多尺度整數(shù)編碼查詢時(shí)間變化比較平穩(wěn)，對(duì)于大數(shù)據(jù)的適應(yīng)性較好。由此可以看出，多尺度整數(shù)編碼查詢消耗的時(shí)間與層級(jí)無關(guān)，與數(shù)據(jù)量正相關(guān)，而Oracle Spatial查詢消耗的時(shí)間隨層級(jí)跨度的變大而增大，且隨著數(shù)據(jù)量的增加，查詢消耗的時(shí)間增加較快，而多尺度編碼查詢消耗的時(shí)間隨數(shù)據(jù)量的變化比較平穩(wěn)。

(2) 從圖6(a)和圖6(b)中兩種方式區(qū)域查詢消耗的時(shí)間對(duì)比可以看出，多尺度整數(shù)編碼區(qū)域查詢的效率只與數(shù)據(jù)量相關(guān)，而Oracle Spatial區(qū)域查詢的效率與層級(jí)跨度和數(shù)據(jù)量均相關(guān)，且多尺度整數(shù)編碼區(qū)域查詢消耗的時(shí)間明顯少于Oracle Spatial。

綜上所述：多尺度整數(shù)編碼與Oracle Spatial中的R樹索引兩種方式所需要的原始數(shù)據(jù)導(dǎo)入時(shí)間與層級(jí)無關(guān)，與數(shù)據(jù)量正相關(guān)。由于R樹進(jìn)行空間查詢時(shí)需要的數(shù)據(jù)為8個(gè)頂點(diǎn)坐標(biāo)，而多尺度編碼只需要一個(gè)整數(shù)值就能與其8個(gè)頂點(diǎn)坐標(biāo)相對(duì)應(yīng)，因此多尺度整數(shù)編碼的數(shù)據(jù)導(dǎo)入時(shí)間要優(yōu)于Oracle Spatial，相同數(shù)據(jù)量數(shù)據(jù)導(dǎo)入時(shí)間約為Oracle Spatial的1/2。隨著數(shù)據(jù)量的增加，從數(shù)據(jù)導(dǎo)入時(shí)間的角度的來看，多尺度整數(shù)編碼更加具有優(yōu)越性。

將數(shù)據(jù)導(dǎo)入數(shù)據(jù)庫以后，多尺度整數(shù)編碼與R樹兩種方式建立索引所需要的時(shí)間與層級(jí)無關(guān)，與數(shù)據(jù)量正相關(guān)。由于多尺度整數(shù)編碼將三維編碼問題轉(zhuǎn)換為一維編碼來進(jìn)行解決，而且Oracle Spatial為了實(shí)現(xiàn)快速查詢，在建立索引的過程中進(jìn)行了大量的優(yōu)化，因此在建立索引的時(shí)間上多尺度整數(shù)編碼要明顯優(yōu)于Oracle Spatial，約為Oracle Spatial的1/46，且隨著數(shù)據(jù)量的增大，優(yōu)勢(shì)會(huì)更加突出。另外，對(duì)于高速變化的三維對(duì)象，涉及大量的數(shù)據(jù)插入和刪除操作，索引的更新會(huì)非常頻繁，三維多尺度編碼也有著較大的優(yōu)勢(shì)。

給定區(qū)域進(jìn)行查詢，由于多尺度整數(shù)編碼為一維編碼，多尺度整數(shù)編碼將三維數(shù)據(jù)查詢問題轉(zhuǎn)換為了一維數(shù)據(jù)的查詢問題，而且Oracle Spatial建立R樹對(duì)數(shù)據(jù)進(jìn)行查詢時(shí)，當(dāng)層級(jí)跨度變大時(shí)，R樹的深度也會(huì)變大而一維查詢不存在這個(gè)問題，因此多尺度編碼的查詢效率要優(yōu)于Oracle Spatial。在數(shù)據(jù)量為1000萬，層級(jí)跨度為7～9的情況下，多尺度整數(shù)編碼的查詢時(shí)間約為Oracle Spatial的1/4，而且隨著數(shù)據(jù)量和層級(jí)跨度的增大，多尺度編碼的優(yōu)勢(shì)會(huì)更加明顯。當(dāng)數(shù)據(jù)量和層級(jí)跨度增加時(shí)，多尺度整數(shù)編碼查詢時(shí)間的曲線變化比較平緩，其時(shí)間復(fù)雜度為O(1)，但是Oracle Spatial的增長(zhǎng)較快，時(shí)間復(fù)雜度為O(n)。由此可見，相比于Oracle Spatial多尺度整數(shù)編碼能夠更加滿足大數(shù)據(jù)對(duì)編碼查詢的需求。

4 總 結(jié)

本文設(shè)計(jì)了一種三維空間格網(wǎng)的多尺度整數(shù)編碼與數(shù)據(jù)索引方法，并從編碼方案設(shè)計(jì)與編碼計(jì)算兩個(gè)方面對(duì)該方法進(jìn)行了較為詳細(xì)的敘述。設(shè)計(jì)了多尺度編碼轉(zhuǎn)換試驗(yàn)，以及與Oracle Spatial的對(duì)比試驗(yàn)。由試驗(yàn)結(jié)果可以看出：多尺度整數(shù)編碼方法在數(shù)據(jù)量、索引建立，以及區(qū)域查詢等3個(gè)方面均有著獨(dú)到的優(yōu)勢(shì)，相比于經(jīng)典的三維R樹索引，該方法更加滿足空間大數(shù)據(jù)對(duì)編碼與索引的需求。

最后，需要說明的是限于文章的篇幅，關(guān)于更多的改進(jìn)、應(yīng)用與后續(xù)研究成果，如將本文的編碼與索引方法應(yīng)用于空間動(dòng)態(tài)目標(biāo)數(shù)據(jù)的管理、點(diǎn)云數(shù)據(jù)的組織等方面，沒有進(jìn)行詳細(xì)的描述。本文的編碼查詢范圍采用的也是固定框架下的體塊，針對(duì)任意的查詢范圍，可以通過多尺度聚合，即將查詢區(qū)域拆分為固定格網(wǎng)進(jìn)行查詢，具體技術(shù)細(xì)節(jié)另文詳述。