高永光，胡聞達，何鵬程

（61683部隊，北京100094）

影像Internet服務(wù)中金字塔的高效組織

高永光，胡聞達，何鵬程

（61683部隊，北京100094）

為了提高基于Internet的影像信息服務(wù)的速度，提出了相離式金字塔結(jié)構(gòu)，用以組織和管理海量的影像數(shù)據(jù)；分別討論了相離式金字塔結(jié)構(gòu)數(shù)據(jù)和索引兩部分的組織問題，并給出了適宜的組織方法。同傳統(tǒng)的金字塔結(jié)構(gòu)相比，相離式金字塔結(jié)構(gòu)具有更高的查詢響應(yīng)性能和更好的可擴展性，適于作為影像Internet服務(wù)中服務(wù)器端的數(shù)據(jù)組織。

影像數(shù)據(jù)；瓦片；相離式金字塔；空間鄰近性

影像數(shù)據(jù)作為一種的重要的基礎(chǔ)空間數(shù)據(jù)，在“國家空間數(shù)據(jù)基礎(chǔ)設(shè)施”建設(shè)中起著越來越重要的作用[1]。在 Internet飛速發(fā)展和普及的今天，如何通過 Internet提供影像信息服務(wù)，從而為數(shù)字攝影測量和遙感圖像處理等應(yīng)用領(lǐng)域提供影像數(shù)據(jù)，成為一個既有理論意義又有現(xiàn)實價值的問題[2]。自從谷歌推出GoogleEarth之后，只需一臺能夠連接Internet的PC機，普通用戶即可近距離感知整個地球、居住城市乃至所在街區(qū)，他們同樣需要影像信息服務(wù)，以方便自己的日常生活。為了同慢速且不穩(wěn)定的Internet相適應(yīng)，服務(wù)器端通常將海量影像數(shù)據(jù)組織成瓦片金字塔結(jié)構(gòu)，僅僅發(fā)送用戶請求的瓦片，以減少服務(wù)器處理量和網(wǎng)絡(luò)傳輸量，從而達到快速分發(fā)影像數(shù)據(jù)的目的。顯然，影像金字塔的組織在上述解決方案之中是一個基礎(chǔ)和核心問題，其組織優(yōu)劣將直接影響到該解決方案的效率高低。本文深入研究了影像金字塔的組織問題，提出了一種索引與數(shù)據(jù)相分離的金字塔結(jié)構(gòu)，即相離式金字塔結(jié)構(gòu)，并設(shè)計了組織瓦片索引和瓦片數(shù)據(jù)的有效方法。實驗和分析表明，相離式金字塔結(jié)構(gòu)具有較快的查詢響應(yīng)和較好的可擴展性，完全可以用作服務(wù)器端的數(shù)據(jù)組織。

1 影像金字塔

為了提供各種分辨率的影像數(shù)據(jù)，同時滿足用戶的無級縮放需求，原始影像數(shù)據(jù)一般需要經(jīng)過拼接、抽樣、分塊和金字塔構(gòu)建等環(huán)節(jié)[3]。拼接是指將一個區(qū)域內(nèi)的多幅小的影像圖片無縫地拼接成一幅大的影像圖片；抽樣是指按倍數(shù)關(guān)系（為了實現(xiàn)無級縮放，應(yīng)當(dāng)取2倍）逐級將高分辨率影像圖片抽樣成各種分辨率的影像圖片；分塊是指在每一個分辨率級別中，將影像圖片均勻劃分成多個瓦片；金字塔構(gòu)建是指將所有瓦片構(gòu)建成一個金字塔，相鄰級別之間的瓦片通過父子指針關(guān)聯(lián)?？紤]一幅影像圖片，它被劃分成8× 8=64個瓦片（如圖 1所示），其中，數(shù)字表示瓦片編號。按2倍關(guān)系對圖1進行抽樣，直到最低一級分辨率的影像圖片僅僅包含一個瓦片，結(jié)果見圖2。我們約定：第1級為最低分辨率的影像圖片。據(jù)此，圖1應(yīng)該是第4級影像圖片。圖3指出了第2、3級影像圖片中瓦片之間的對應(yīng)關(guān)系，其他相鄰級別中瓦片之間的對應(yīng)關(guān)系可以依次類推。從圖3中可以看出，第2級的瓦片1是從第3級的瓦片1、2、5和6抽樣而成的。

圖1 示例影像圖片（第4級）

圖2 1-3級影像圖片

圖3 2-3級中瓦片之間的對應(yīng)關(guān)系

基于上述金字塔結(jié)構(gòu)，我們不僅可以為用戶提供各種分辨率的影像數(shù)據(jù)，而且直接支持無級縮放：首先顯示大比例尺（低分辨率）影像，在用戶選擇感興趣區(qū)域之后，依據(jù)父子指針調(diào)出小比例尺（高分辨率）影像。由于無需讀出對于用戶來說無用的瓦片，使得平滑的影像漫游和縮放成為可能。需要指出的是，為了降低存儲開銷和減少網(wǎng)絡(luò)傳輸，瓦片通常以壓縮形式存儲，一般是 jpg格式。因此，由于細節(jié)程度的不同，任意 2個瓦片，即使是來自同一個級別，也不大可能有相同的尺寸。

如何在物理上實現(xiàn)一個金字塔呢？通常的做法是將其表示成一種類似于樹的結(jié)構(gòu)[4]：樹中的一層表示影像一個分辨率級；自根節(jié)點而下，依次表示第1級影像、第 2級影像等；每一個節(jié)點項除了記錄一個瓦片數(shù)據(jù)之外，同時維護4個指向下一層瓦片的指針。上述思想是將索引信息與數(shù)據(jù)信息整合在一個結(jié)構(gòu)之內(nèi)，檢索總是從根節(jié)點開始，依據(jù)索引信息自上而下進行瓦片定位。如果待請求瓦片位于第N層（N是金字塔的級數(shù)），那么至少需要N次I/O操作才能讀出該瓦片，I/O代價較高正是樹結(jié)構(gòu)金字塔實現(xiàn)的一個最大缺點。另外，結(jié)構(gòu)的復(fù)雜性和飽和性使得樹結(jié)構(gòu)金字塔實現(xiàn)的可擴展性很差。

2 索引與數(shù)據(jù)相分離的金字塔結(jié)構(gòu)

為了提高影像金字塔的I/O性能，并使之同時具有較高的可擴展性，我們提出了一種索引與數(shù)據(jù)相分離的金字塔結(jié)構(gòu)（以下簡稱相離式金字塔），其核心思想是將索引信息剝離出來單獨組織：一個金字塔結(jié)構(gòu)包括索引與數(shù)據(jù)2個部分，兩者通過指針關(guān)聯(lián)。在相離式金字塔結(jié)構(gòu)中，每一個瓦片的數(shù)據(jù)被存儲在數(shù)據(jù)部分，它同時在索引部分有一條記錄，指出這個瓦片的級別和編號，以及該瓦片的尺寸及其在數(shù)據(jù)部分中的位置。圖4給出了相離式金字塔的一個例子，其中，箭頭表示指向數(shù)據(jù)部分位置的指針。檢索時，首先掃描索引部分（索引部分較小，通?？梢猿ｑv內(nèi)存，同磁盤I/O代價比較起來，基于內(nèi)存的掃描代價是較小的），在定位出待請求瓦片的位置之后，借助1次I/O操作即可讀出該瓦片。

圖4 相離式金字塔示例

較之傳統(tǒng)的一體式金字塔結(jié)構(gòu)實現(xiàn)，我們提出的相離式金字塔結(jié)構(gòu)實現(xiàn)有3個主要特點：

1）索引部分和數(shù)據(jù)部分各自組織，互不干涉，在索引部分相鄰的 2個瓦片不一定在數(shù)據(jù)部分相鄰，反之亦然；

2）內(nèi)外存結(jié)構(gòu)一致，當(dāng)系統(tǒng)配置足夠內(nèi)存時，無需任何轉(zhuǎn)換即可將相離式金字塔結(jié)構(gòu)從磁盤導(dǎo)入內(nèi)存；

3）數(shù)據(jù)結(jié)構(gòu)簡單，易于實現(xiàn)、操作和擴展。

2.1 數(shù)據(jù)部分組織

數(shù)據(jù)部分通常很大，不大可能裝入內(nèi)存之中，其I/O性能是我們關(guān)注的主要問題。顯然，讀取單個瓦片沒有任何優(yōu)化技巧可言，但是，用戶往往依次請求多個瓦片，并且這些瓦片是語義相關(guān)的，或者在水平方向上有兄弟關(guān)系，或者在垂直方向上有父子關(guān)系。如果相鄰的2個被請求瓦片在物理存儲上也是相鄰的，那么在讀取瓦片時，磁盤中機械磁頭的移動距離將被盡可能地減少，因而能夠降低I/O代價?；谏鲜隹紤]，我們可以對那些有兄弟或父子關(guān)系的瓦片進行聚簇存儲，從而利用瓦片請求的局部性來提高數(shù)據(jù)部分整體的I/O性能。

對于數(shù)據(jù)部分來說，一種直觀的組織方法是逐層、逐行和逐列組織各個瓦片，即首先存儲第1層瓦片，接著存儲第2層瓦片等，而在一層內(nèi)，首先存儲第1行瓦片，接著存儲第 2行瓦片等。這種組織方法雖然簡單，但是幾乎沒有考慮到訪問的局部性，使得其空間鄰近性（包括水平和垂直2個方向）很差。

考慮水平方向上的訪問局部性，我們需要盡可能地提高一個層中瓦片的空間鄰近性。在二維空間中，空間臨近性指按某種編碼方式將二維位置映射成一維碼后，鄰接的二維位置在一維碼中的距離遠近程度。在已出現(xiàn)的多種編碼方式中，Morton碼（也稱Z-order碼）是其中最為簡單有效的一種[5]。Morton碼是對行列號的二進制碼進行位交叉之后的得到的一種編碼，例如，(3，4)M=26，其編碼過程如圖 5所示。據(jù)此，我們可以得到一種數(shù)據(jù)部分的組織方式（以下稱為逐層Morton碼組織），即首先逐層組織，而在一層內(nèi)，按Morton碼大小依次存儲各個瓦片。對于圖 1、圖 2所示的金字塔，數(shù)據(jù)部分的逐層Morton碼組織如下：<1.1，2.1，2.2，2.3，3.1，3.2，3.5，3.6，3.3，3.4，3.7，3.8，…，4.55，4.56，4.63，4.64>，其中，每一項的前一部分是層號，后一部分是圖1和圖2中瓦片的編號。

考慮垂直方向上的訪問局部性，我們應(yīng)該首先存儲父瓦片，接著存儲子瓦片，依次類推下去，即按照深度優(yōu)先順序組織各個瓦片（以下稱為深度優(yōu)先組織）。對于圖1和圖2所示的金字塔，數(shù)據(jù)部分的深度優(yōu)先組織如下：<1.1， 2.1，3.1，4.1，4.2，4.9，4.10，3.2，4.3，4.4，4.11，4.12，…，4.55，4.56，4.63，4.64>。

圖5 (3，4)的Morton編碼

顯然，水平和垂直2個方向上的訪問局部性是相互矛盾的，照顧水平方向上的訪問局部性必然會損害到垂直方向上的訪問局部性，反之亦然。在實際應(yīng)用中，即使是以下鉆操作為主，在下鉆到一個層次之后也會請求該層中在視野范圍之內(nèi)的所有瓦片。因此，較之垂直方向上的訪問局部性，水平方向上的訪問局部性更為重要一些，因此，逐層Morton碼組織比深度優(yōu)先組織更適合用來組織數(shù)據(jù)部分。

2.2 索引部分組織

索引部分較小，一般可以裝入內(nèi)存之中。雖然同I/O操作相比，CPU操作快了很多，但是，通過掃描索引來定位瓦片也是不可取的。為此，我們提出了索引部分的逐層有序組織，即首先逐層組織，而在一層內(nèi)，按編碼大小依次存儲各個瓦片對應(yīng)的索引項。在逐層有序組織中，每一層索引項的起止點被預(yù)先記錄在數(shù)據(jù)字典中。對于索引部分來說，逐層有序組織可以借助二分查找，從而將瓦片定位的時間復(fù)雜度從 O(N)降為O(log2N)。當(dāng)新來一個瓦片請求之后，首先依據(jù)其行列號計算出層內(nèi)編碼，然后在所屬層的索引項范圍之內(nèi)進行二分查找。前面已經(jīng)說過，索引部分組織并不依賴于數(shù)據(jù)部分組織，因此，索引部分可以采用更為簡單的編碼方式，如行優(yōu)先碼（即逐行順序編碼），而不是Morton碼。對于圖1和圖2所示的金字塔，索引部分的逐層有序組織如下：<1.1，2.1，2.2，2.3，2.4，3.1，3.2，…，4.64>。

3 實驗與分析

本節(jié)將通過實驗來驗證相離式金字塔的有效性。實驗采用南昌市DMC航拍數(shù)據(jù)，該數(shù)據(jù)集有7層，共開展了2組實驗：第一組隨機生成1000條瓦片查詢，測試總響應(yīng)時間；第二組采用World Wind客戶端從第1層下鉆到第 7層，測試平均響應(yīng)時間。實驗平臺是一臺配置了 PIV處理器、1 G內(nèi)存和80 G硬盤的戴爾PowerEdge SC430小型服務(wù)器。實驗結(jié)果如表1和表2所示，其中，數(shù)據(jù)部分的無序指瓦片的存儲順序無規(guī)律可循，而索引部分的無序指索引項的存儲順序無規(guī)律可循。

我們從表1和表2可以得出2點：①由于瓦片數(shù)據(jù)的聚簇性存儲，數(shù)據(jù)部分的深度優(yōu)先組織和逐層Morton碼組織大大加快了瓦片查詢的響應(yīng)速度，而后者利用了水平方向上空間臨近性，在響應(yīng)速度方面更勝一籌；②由于避免了時間復(fù)雜度為 O(N)的掃描操作，索引部分的逐層有序組織明顯地提高了查詢響應(yīng)性能。

表1 隨機瓦片查詢的總響應(yīng)時間/s

表2 World W ind查詢的平均響應(yīng)時間/s

4 結(jié)語

本文研究了影像Internet服務(wù)中金字塔的組織問題，在傳統(tǒng)的一體式金字塔結(jié)構(gòu)的基礎(chǔ)上，提出了相離式金字塔結(jié)構(gòu)，其包括數(shù)據(jù)和索引 2個部分，兩部分各自組織，互不影響，具有很好的可擴展性。以此為基礎(chǔ)，研究了數(shù)據(jù)部分和索引部分的組織方法，得出了適合于數(shù)據(jù)部分的逐層Morton碼組織和適合于索引部分的逐層有序組織。實驗和分析表明，相離式金字塔結(jié)構(gòu)具有很高的查詢響應(yīng)性能，能夠勝任服務(wù)器端的數(shù)據(jù)組織。

[1] 王密.大型無縫影像數(shù)據(jù)庫系統(tǒng)(Geo ImageDB)的研制與可量測虛擬現(xiàn)實(MVR)的可行性研究[D].武漢:武漢大學(xué)，2001

[2] 陳靜，龔健雅，朱欣焰，等.海量影像數(shù)據(jù)的Web發(fā)布與實現(xiàn)[J].測繪通報，2004(1):22-25

[3] 李霖，吳凡.空間數(shù)據(jù)多尺度表達模型及其可視化[M].第一版.北京:科學(xué)出版社，2004

[4] 鄧雪清.柵格型空間數(shù)據(jù)服務(wù)體系結(jié)構(gòu)與算法研究[D].鄭州:中國人民解放軍信息工程大學(xué)，2003

[5] 龔健雅.地理信息系統(tǒng)基礎(chǔ)[M].第一版.北京:科學(xué)出版社，2001

[6] Jensen J.R.Introductory Digital Image Processing.A Remote Sensing Perspective[M].Pearson Prentice Hall，Upper Saddle River，NJ，2005

[7] Powell M.W，Rossi R.A，Shams K.A Scalable Image Processing Framework forGigapixel Mars and OtherCelestial Body Images[C].Aerospace Conference，2010:1-11

Efficient Organization of Pyramid in Internet Image Service

by GAO Yongguang

In order to improve image service speed based on Internet, we proposed a new architecture for image pyramid,called Separated Pyramid,for organizing and managing huge image data.Separated Pyramid structure contains two parts:data and index,and so we discussed their organization problem,leading appropriate organization for data part and index part respectively.Compared with traditional pyramid structure,Separated Pyramid provides higher query answering and better scalability,and so it can be used as the data organization of the server side in the Internet image service.

image data，tile，Separated Pyramid，space locality

2011-11-27

P237

B

1672-4623(2012)02-0070-03

高永光，工程師，研究方向為3S集成與應(yīng)用。