空間資料結(jié)構(gòu)設(shè)計

1、1第九章第九章空間資料結(jié)構(gòu)設(shè)計空間資料結(jié)構(gòu)設(shè)計29.1 前言n9.2 黑白影像的空間資料結(jié)構(gòu)表示法n9.3 視窗查詢的四分樹分割n9.5 高灰階影像的空間資料結(jié)構(gòu)表示法 n9.8 作業(yè)n9.2.1 四分樹表示法n9.2.3 線性四分樹表示法 n9.2.5 內(nèi)插二分碼n9.2.2 深先表示法n9.2.4 S樹搜尋39.2 黑白影像的空間資料結(jié)構(gòu)表示法9.2.1 四分樹表示法圖所示的黑白影像。利用四分樹的切割方式， 其樹狀表示法如圖所示。 SSSSSSSSSSSSSSSSSSSSS123456789nwne swse層3210圖黑白影像圖 四

2、分樹表示法n四分樹切割4n四分樹的正規(guī)化圖9.2.3 44黑白影像(a) 移動後的結(jié)果圖9.2.4移位後的效果(b) 移動後的四分樹表示法圖9.2.3所示的黑白影像，其四分樹表示法共需16個葉子點。假如將黑色區(qū)域，往東南方向移動一格如圖9.2.4(a)，則其四分樹表示法如圖9.2.4(b)所示，就只需七個葉子點。 因此適當?shù)囊莆唬梢詼p少葉子數(shù)量來達到節(jié)省記憶體的功效。59.2.2 深先表示法只使用B(Black)、W(White)和G(Gray)三個符號。 SSSSSSSSSSSSSSSSSSSSS123456789nwne swse層3210圖四分樹表示法內(nèi)部節(jié)點 輸出G圖9

3、.2.1.2的四分樹可表示成GGWWWGBWBWBWGWWGWWBBB。 黑色外部節(jié)點 輸出B白色外部節(jié)點 輸出W為了更節(jié)省的記憶體需求，圖的深先表示法可改成 (000 (101010(00(00111。 69.2.3 線性四分樹表示法只記錄黑色節(jié)點且其儲存方式為(第i層,路徑)。如圖中的S20可表示為(0,322)，這裡的0代表S20位於第0層；3代表東南方向；2代表西南方向。另外，還有一種拿掉第i層欄位修改路徑的表示法，如節(jié)點S13可表示為33X，這裡X是補上去的額外符號。利用深先搜尋方式，圖的可表示為 030，032，322，323，33X。n線

4、性四分樹SSSSSSSSSSSSSSSSSSSSS123456789nwne swse層3210圖四分樹表示法7另外，線性四分樹的表示法雖然只記載黑色節(jié)點的資訊，但其編碼是代表該節(jié)點的走訪路徑，因此只要在編解碼時，確定每個碼代表的方位彼此都一致（例如：0代表NW, 1代表NE, 2代表SW, 3代表SE）就算沒有使用特定的走訪順序，同一群但不同順序的編碼也能還原出一樣的四分樹。 如下列兩組不同的線性四分樹編碼，依然可以還原出一樣的四分樹。10X, 130, 132, 21X, 22X, 231, 232, 3XX3XX, 10X, 21X, 22X, 130, 132, 231,

5、 23201231301322312323XX10X21X22X8在CBLQ法中，四分樹的節(jié)點被分為四種類型：nCBLQ法白色外部節(jié)點 輸出0某內(nèi)部節(jié)點的四個孩子皆為外部節(jié)點 輸出3黑色外部節(jié)點 輸出1某內(nèi)部節(jié)點的四個孩子非全為外部節(jié)點 輸出2利用廣先搜尋的方式，圖的表示式為221020003003110100011。層3210221020003003101000111圖CBLQ樹9圖256 256颱風影像圖 的 256 256 颱風地圖，若照原圖儲存共需65536位元。我們實驗的結(jié)果顯示：n深先表示法需花19024位元nCBLQ法需花1

6、7148位元n緊緻四分樹需花13957位元nJBIG來壓縮圖需花10967位元n實驗109.2.4 S樹表示法在S樹表示法中，必須先得到圖的二分樹結(jié)構(gòu)，如圖所示。 LTDLRTDLRRTDLRTDTDLRTDRD圖圖的二分樹表示法n線性樹表n顏色表內(nèi)部節(jié)點 輸出0外部節(jié)點 輸出1圖的線性樹表可表示為 0001010111010010011011011。 白色葉子 輸出0黑色葉子 輸出1圖的線性樹表對應(yīng)顏色表可表示為0010010010101。119.2.5 內(nèi)插二分碼給一張 的黑白影像，如圖(a)

7、所示。利用二分樹的分割方式得到圖(b)的五個區(qū)塊。區(qū)塊位於(0,1)的位置和第四層。令 01231230ijADFIHABCDEFGHLIJ87117124208253層01234(a) 44 黑白影像(b) 二分樹分割後的區(qū)塊(c) 內(nèi)插二分碼NN22442201)01()(1jjj22012344422)1111(),(152222ssssslNN2201)00()(0i ii這裡l代表層數(shù)。內(nèi)插二分碼將i、j和s的二位元字串交錯內(nèi)插成碼 14241664000000087)01010111()(2200102131sjsisjsiQA圖一個內(nèi)插二分碼的例子12

8、9.3 視窗查詢的四分樹分割006614115162993121051311884. . . . .xyBBB123n最大四分樹區(qū)塊給一大小98的視窗如圖9.3.1所示，該粗體線圍住的視窗其左下角位於影像的(1,15)位置。在圖9.3.1中，影像的大小為 。依照四分樹結(jié)構(gòu)將影像分割，則該視窗被分解成八個22的區(qū)塊、一個44的區(qū)塊和24個11的區(qū)塊。 4422 為方便起見，1B2B3B表示為(4,12,4,4)這裏，前兩欄代表位置而後兩欄代表區(qū)塊大小。 圖9.3.1 98視窗的四分樹區(qū)塊分割表示為(2,12,2,2)表示為(2,10,2,2)給一nn的視窗，則四分樹的區(qū)塊數(shù)不會超過 。)(5)l

9、og2(3nOnn139.5 高灰階影像的空間資料結(jié)構(gòu)表示法n一維線性內(nèi)插圖9.5.1中的O點被表示為(1,5)，此處1表示x軸的位置而5表示灰階值；C點被表示為(11,13)。假設(shè)A點的位置為4，則OABCD3108圖9.5.1 一維的線性內(nèi)插CDABOCOA由得知4 . 21083OCCDOAABA點的灰階值約為7=(5+2)。14假設(shè)有一高灰階影像被切割成圖9.5.2，其二分樹表示法如圖9.5.3所示。在圖9.5.3中每一個區(qū)塊皆需滿足xyaeldfbcighjkabcdefghijkl圖9.5.2同質(zhì)的區(qū)塊分割圖 圖9.5.3二分樹的表示法 n二分樹切割的條件),(yxgest此處 g

10、(x,y)為區(qū)塊內(nèi)位於(x,y)的像素之原始灰階值； | ),(),(|yxgyxgest 代表同樣位於(x,y)的像素依據(jù)區(qū)塊四個角點的灰階值經(jīng)過三次的一維線性內(nèi)插得到的估計灰階值。 代表誤差容忍度；15n求算),(yxgest假設(shè)一個區(qū)塊的四個角點分別如下),(12yx),(21yx),(22yx位置灰階值左上右上左下右下),(11yx1g4g3g2g利用一維線性內(nèi)插可以得到)(),(112565yyyygggyxgest)(1121215xxxxgggg)(1123436xxxxgggg此處 和 。n廣先搜尋不同於9.2.4節(jié)的S樹在空間資料結(jié)構(gòu)所採取的深先搜尋法，我們利用廣先搜尋法，將

11、圖9.18的二分樹用S樹表示如下線性樹表：00000000010101111111111 顏色表：(eul , eur , ebl , ebr) , (hul , hur , hbl , hbr) , , (jul , jur , jbl , jbr) 16n重疊策略由於區(qū)塊與區(qū)塊之間是分開的，我們擔心上述樹表示法經(jīng)解壓後會造成區(qū)塊效應(yīng)(Blocking Effect)。這種區(qū)塊效應(yīng)，會讓解壓後的影像有一些不太平滑。我們採用一種重疊策略來降低區(qū)塊效應(yīng)的影響 。我們的做法是將原影像的最右邊一行和最底下一列重複一次，這使得原先2n2n大小的影像放大成(2n+1)(2n+1)的大小。這個重疊策略(Overlapping Strategy)會使影像經(jīng)二分樹分割後，鄰近的兩區(qū)塊會重疊一個像素的寬度，這種像素分享的特色配合上線性內(nèi)插的平滑性，解壓出來後確可大幅降低區(qū)塊效應(yīng)的影響。 17在=21時，圖9.5.4對應(yīng)的樹所需的bpp(Bit Per Pixel)約為1.35 bits，這與原始影像一個像素需8個bits相比，壓縮改良率為83%。本節(jié)介紹的空間資料結(jié)構(gòu)表示法，雖然在壓縮比上不如JPEG(Joint Photographic Expe