1、第九章第九章空間資料結構設計空間資料結構設計9.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樹搜尋9.2 黑白影像的空間資料結構表示法9.2.1 四分樹表示法圖9.2.1.1所示的黑白影像。利用四分樹的切割方式，其樹狀表示法如圖9.2.1.2所示。SSSSSSSSSSSSSSSSSSSSS123456789nwne swse層3210圖9.2.1.1黑白影像圖9.2.1.2 四分樹表示法
2、n四分樹切割n四分樹的正規化圖9.2.3 44黑白影像(a)移動後的結果圖9.2.4移位後的效果(b)移動後的四分樹表示法圖9.2.3所示的黑白影像，其四分樹表示法共需16個葉子點。假如將黑色區域，往東南方向移動一格如圖9.2.4(a)，則其四分樹表示法如圖9.2.4(b)所示，就只需七個葉子點。因此適當的移位，可以減少葉子數量來達到節省記憶體的功效。9.2.2 深先表示法只使用B(Black)、W(White)和G(Gray)三個符號。SSSSSSSSSSSSSSSSSSSSS123456789nwne swse層3210圖9.2.1.2四分樹表示法內部節點 輸出G圖9.2.1.2的四分樹可
3、表示成GGWWWGBWBWBWGWWGWWBBB。黑色外部節點 輸出B白色外部節點 輸出W為了更節省的記憶體需求，圖9.2.1.2的深先表示法可改成 (000(101010(00(00111。9.2.3 線性四分樹表示法只記錄黑色節點且其儲存方式為(第i層,路徑)。如圖9.2.1.2中的S20可表示為(0,322)，這裡的0代表S20位於第0層；3代表東南方向；2代表西南方向。另外，還有一種拿掉第i層欄位修改路徑的表示法，如節點S13可表示為33X，這裡X是補上去的額外符號。利用深先搜尋方式，圖9.2.1.2的可表示為 030，032，322，323，33X。n線性四分樹SSSSSSSSSSS
4、SSSSSSSSSS123456789nwne swse層3210圖9.2.1.2四分樹表示法另外，線性四分樹的表示法雖然只記載黑色節點的資訊，但其編碼是代表該節點的走訪路徑，因此只要在編解碼時，確定每個碼代表的方位彼此都一致（例如：0代表NW,1代表NE,2代表SW,3代表SE）就算沒有使用特定的走訪順序，同一群但不同順序的編碼也能還原出一樣的四分樹。如下列兩組不同的線性四分樹編碼，依然可以還原出一樣的四分樹。10X,130,132,21X,22X,231,232,3XX3XX,10X,21X,22X,130,132,231,23201231301322312323XX10X21X22X在C
5、BLQ法中，四分樹的節點被分為四種類型：nCBLQ法白色外部節點 輸出0某內部節點的四個孩子皆為外部節點 輸出3黑色外部節點 輸出1某內部節點的四個孩子非全為外部節點 輸出2利用廣先搜尋的方式，圖9.2.1.2的表示式為221020003003110100011。層3210221020003003101000111圖9.2.3.1CBLQ樹圖9.2.3.2256 256颱風影像圖 9.2.3.2的 256 256 颱風地圖，若照原圖儲存共需65536位元。我們實驗的結果顯示：n深先表示法需花19024位元nCBLQ法需花17148位元n緊緻四分樹需花13957位元nJBIG來壓縮圖需花1096
6、7位元n實驗9.2.4 S樹表示法在S樹表示法中，必須先得到圖9.2.1.1的二分樹結構，如圖9.2.4.1所示。LTDLRTDLRRTDLRTDTDLRTDRD圖9.2.4.1圖9.2.1.1的二分樹表示法n線性樹表n顏色表內部節點 輸出0外部節點 輸出1圖9.2.4.1的線性樹表可表示為 0001010111010010011011011。白色葉子 輸出0黑色葉子 輸出1圖9.2.4.1的線性樹表對應顏色表可表示為0010010010101。9.2.5 內插二分碼給一張 的黑白影像，如圖9.2.5.1(a)所示。利用二分樹的分割方式得到圖9.2.5.1(b)的五個區塊。區塊位於(0,1)的
7、位置和第四層。令 01231230ijADFIHABCDEFGHLIJ87117124208253層01234(a)44 黑白影像(b)二分樹分割後的區塊(c)內插二分碼NN22442201)01()(1jjj22012344422)1111(),(152222ssssslNN2201)00()(0i ii這裡l代表層數。內插二分碼將i、j和s的二位元字串交錯內插成碼 14241664000000087)01010111()(2200102131sjsisjsiQA圖9.2.5.1一個內插二分碼的例子9.3 視窗查詢的四分樹分割006614115162993121051311884.xyBBB
8、123n最大四分樹區塊給一大小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)log2(3nOnn9.5 高灰階影像的空間資料結構表示法n一維線性內插圖9.5.1中的O點被表示為(1,5)，此處
9、1表示x軸的位置而5表示灰階值；C點被表示為(11,13)。假設A點的位置為4，則OABCD3108圖9.5.1 一維的線性內插CDABOCOA由得知4.21083OCCDOAABA點的灰階值約為7=(5+2)。假設有一高灰階影像被切割成圖9.5.2，其二分樹表示法如圖9.5.3所示。在圖9.5.3中每一個區塊皆需滿足xyaeldfbcighjkabcdefghijkl圖9.5.2同質的區塊分割圖 圖9.5.3二分樹的表示法 n二分樹切割的條件),(yxgest此處 g(x,y)為區塊內位於(x,y)的像素之原始灰階值；|),(),(|yxgyxgest 代表同樣位於(x,y)的像素依據區塊四
10、個角點的灰階值經過三次的一維線性內插得到的估計灰階值。代表誤差容忍度；n求算),(yxgest假設一個區塊的四個角點分別如下),(12yx),(21yx),(22yx位置灰階值左上右上左下右下),(11yx1g4g3g2g利用一維線性內插可以得到)(),(112565yyyygggyxgest)(1121215xxxxgggg)(1123436xxxxgggg此處 和 。n廣先搜尋不同於9.2.4節的S樹在空間資料結構所採取的深先搜尋法，我們利用廣先搜尋法，將圖9.18的二分樹用S樹表示如下線性樹表：00000000010101111111111 顏色表：(eul,eur,ebl,ebr),(
11、hul,hur,hbl,hbr),(jul,jur,jbl,jbr)n重疊策略由於區塊與區塊之間是分開的，我們擔心上述樹表示法經解壓後會造成區塊效應(Blocking Effect)。這種區塊效應，會讓解壓後的影像有一些不太平滑。我們採用一種重疊策略來降低區塊效應的影響。我們的做法是將原影像的最右邊一行和最底下一列重複一次，這使得原先2n2n大小的影像放大成(2n+1)(2n+1)的大小。這個重疊策略(Overlapping Strategy)會使影像經二分樹分割後，鄰近的兩區塊會重疊一個像素的寬度，這種像素分享的特色配合上線性內插的平滑性，解壓出來後確可大幅降低區塊效應的影響。在=21時，圖
12、9.5.4對應的樹所需的bpp(Bit Per Pixel)約為1.35 bits，這與原始影像一個像素需8個bits相比，壓縮改良率為83%。本節介紹的空間資料結構表示法，雖然在壓縮比上不如JPEG(Joint Photographic Experts Group)來的好，但是在解碼的時間(Decoding Time)上較快34倍，在某些的應用上仍有其利基。圖9.5.4=21得到的還原影像圖圖9.5.5二元分割後的區塊示意圖n實驗9.8 作業 習題一：給一張 的黑白影像，試分析建構四分樹所花的 NNnn22時間複雜度。習題二：在黑白影像的不同空間資料結構表示法中，探討任二種表示法彼此之間的轉換。
