第八章 空間資料結構設計.

Presentation on theme: "第八章 空間資料結構設計."— Presentation transcript:

1 第八章 空間資料結構設計

2 內容 8.1 前言 8.2 黑白影像表示法 8.3 影像加密 8.4 灰階影像表示法 8.5 作業

3 8.1 前言 將影像切割成許多的規律區塊，可用較省記憶體的空間資料結構(Spatial Data Structures)來表示這些區塊。
空間資料結構除了省記憶體的優點外，他還保有不需解壓的影像運算等方面的有效應用。

4 8.2 黑白影像表示法 四分樹切割 圖8.2.1黑白影像 圖8.2.2 四分樹表示法

5 四分樹的正規化 (a) 移動後的結果 (b) 移動後的四分樹表示法 圖 ×4黑白影像 圖8.2.4 移位後的效果

6 圖8.2.2的四分樹可表示成GGWWWGBWBWBWGWWGWWBBB。
深先表示法 內部節點  輸出G 白色外部節點  輸出W 黑色外部節點  輸出B 圖8.2.2的四分樹可表示成GGWWWGBWBWBWGWWGWWBBB。 圖8.2.2四分樹表示法

7 利用深先搜尋方式，圖8.2.2的可表示為 030，032，1XX， 322，323，33X。
線性四分樹 利用深先搜尋方式，圖8.2.2的可表示為 030，032，1XX， 322，323，33X。 圖8.2.2 四分樹表示法

8 解碼 10X, 130, 132, 21X, 22X, 231, 232, 3XX

9 8.3 影像加密 圖8.3.1 影像加密系統 (a) 8×8黑白影像 (b) 四分樹結構 圖8.3.2影像加密的例子

10 掃瞄語言 圖 個掃瞄圖案

11 模擬例子 給定一組產生規則: 圖8.3.4 加密後的結果 則圖8.3.2(a)的黑白影像被加密成圖8.3.4。將圖8.3.4予以壓縮。利用列掃瞄的方式，圖8.3.4可表示成 ，進而用 來表示圖8.3.4。

12 8.4 灰階影像表示法 一維線性內插 圖8.4.1中的O點被表示為(1,5)，此處1表示x軸的位置而5表示灰階值；C點被表示為(11,13)。假設A點的位置為4，則 由 得知 A點的灰階值約為7=(5+2)。 圖8.4.1 一維的線性內插

13 二分樹切割的條件 圖8.4.2 同質的區塊分割圖 圖8.4.3 二分樹的表示法

14 求算 假設一個區塊的四個角點分別如下: 利用線性內插可以得到 ， 此處 和 。 廣先搜尋 圖8.4.3的二分樹用S樹表示如下:
利用線性內插可以得到 ， 此處 和 。 廣先搜尋 圖8.4.3的二分樹用S樹表示如下: 位置 灰階值 左上 右上 左下 右下 線性樹表： 顏色表：(eul , eur , ebl , ebr) , (hul , hur , hbl , hbr) , … , (jul , jur , jbl , jbr)

15 重疊策略 採用重疊策略來降低區塊效應的影響。將原影像的最右邊一行和最底下一列重複一次，這使得原先 大小的影像放大成 的大小。這個重疊策略(Overlapping Strategy)會使影像經二分樹分割後，鄰近的兩區塊會重疊一個像素的寬度，解壓出來後確可大幅降低區塊效應的影響。

16 實驗 在ε=21時，圖8.4.4對應樹所需的bpp(Bit Per Pixel)約為1.35 bits，這與原始影像一個像素需8個bits相比，壓縮改良率為83%。 圖8.4.4 ε=21得到的還原影像圖 圖8.4.5 二元分割後的區塊示意圖

17 8.5 作業 作業一：寫一C程式以完成將黑白影像轉成線性 四分樹的實作。 作業二：寫一C程式以完成影像加密的實作。