第八章 空間資料結構設計
內容 8.1 前言 8.2 黑白影像表示法 8.3 影像加密 8.4 灰階影像表示法 8.5 作業
8.1 前言 將影像切割成許多的規律區塊,可用較省記憶體的空間資料結構(Spatial Data Structures)來表示這些區塊。 空間資料結構除了省記憶體的優點外,他還保有不需解壓的影像運算等方面的有效應用。
8.2 黑白影像表示法 四分樹切割 圖8.2.1黑白影像 圖8.2.2 四分樹表示法
四分樹的正規化 (a) 移動後的結果 (b) 移動後的四分樹表示法 圖8.2.3 4×4黑白影像 圖8.2.4 移位後的效果
圖8.2.2的四分樹可表示成GGWWWGBWBWBWGWWGWWBBB。 深先表示法 內部節點 輸出G 白色外部節點 輸出W 黑色外部節點 輸出B 圖8.2.2的四分樹可表示成GGWWWGBWBWBWGWWGWWBBB。 圖8.2.2四分樹表示法
利用深先搜尋方式,圖8.2.2的可表示為 030,032,1XX, 322,323,33X。 線性四分樹 利用深先搜尋方式,圖8.2.2的可表示為 030,032,1XX, 322,323,33X。 圖8.2.2 四分樹表示法
解碼 10X, 130, 132, 21X, 22X, 231, 232, 3XX
8.3 影像加密 圖8.3.1 影像加密系統 (a) 8×8黑白影像 (b) 四分樹結構 圖8.3.2影像加密的例子
掃瞄語言 圖8.2.3 24個掃瞄圖案
模擬例子 給定一組產生規則: 圖8.3.4 加密後的結果 則圖8.3.2(a)的黑白影像被加密成圖8.3.4。將圖8.3.4予以壓縮。利用列掃瞄的方式,圖8.3.4可表示成00000000000111110000000000000000111110000000 11110000000011110000,進而用011516574844來表示圖8.3.4。
8.4 灰階影像表示法 一維線性內插 圖8.4.1中的O點被表示為(1,5),此處1表示x軸的位置而5表示灰階值;C點被表示為(11,13)。假設A點的位置為4,則 由 得知 A點的灰階值約為7=(5+2)。 圖8.4.1 一維的線性內插
二分樹切割的條件 圖8.4.2 同質的區塊分割圖 圖8.4.3 二分樹的表示法
求算 假設一個區塊的四個角點分別如下: 利用線性內插可以得到 , 此處 和 。 廣先搜尋 圖8.4.3的二分樹用S樹表示如下: 利用線性內插可以得到 , 此處 和 。 廣先搜尋 圖8.4.3的二分樹用S樹表示如下: 位置 灰階值 左上 右上 左下 右下 線性樹表:00000000010101111111111 顏色表:(eul , eur , ebl , ebr) , (hul , hur , hbl , hbr) , … , (jul , jur , jbl , jbr)
重疊策略 採用重疊策略來降低區塊效應的影響。將原影像的最右邊一行和最底下一列重複一次,這使得原先 大小的影像放大成 的大小。這個重疊策略(Overlapping Strategy)會使影像經二分樹分割後,鄰近的兩區塊會重疊一個像素的寬度,解壓出來後確可大幅降低區塊效應的影響。
實驗 在ε=21時,圖8.4.4對應樹所需的bpp(Bit Per Pixel)約為1.35 bits,這與原始影像一個像素需8個bits相比,壓縮改良率為83%。 圖8.4.4 ε=21得到的還原影像圖 圖8.4.5 二元分割後的區塊示意圖
8.5 作業 作業一:寫一C程式以完成將黑白影像轉成線性 四分樹的實作。 作業二:寫一C程式以完成影像加密的實作。