空间资料结构设计

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

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

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

4、性四分樹SSSSSSSSSSSSSSSSSSSSS123456789nwne swse層3210圖四分樹表示法7另外，線性四分樹的表示法雖然只記載黑色節點的資訊，但其編碼是代表該節點的走訪路徑，因此只要在編解碼時，確定每個碼代表的方位彼此都一致（例如：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法中，四分樹的節點被分為四種類型：nCBLQ法白色外部節點 輸出0某內部節點的四個孩子皆為外部節點 輸出3黑色外部節點 輸出1某內部節點的四個孩子非全為外部節點 輸出2利用廣先搜尋的方式，圖的表示式為221020003003110100011。層3210221020003003101000111圖CBLQ樹9圖256 256颱風影像圖 的 256 256 颱風地圖，若照原圖儲存共需65536位元。我們實驗的結果顯示：n深先表示法需花19024位元nCBLQ法需花1

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

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

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

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

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

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