第九章 空間資料結構設計與應用.

Presentation on theme: "第九章 空間資料結構設計與應用."— Presentation transcript:

1 第九章 空間資料結構設計與應用

2 內容 9.1 前言 9.2 黑白影像的空間資料結構表示法 9.3 高灰階影像的空間資料結構表示法 9.4 基本影像運算之應用 9.5 結論
四分樹表示法 線性四分樹表示法 深先表示法 S 樹表示法 影像加密 動差計算

3 9.2 黑白影像的空間資料結構表示法9.2.1 四分樹表示法
四分樹切割 圖 黑白影像 圖 四分樹表示法

4 四分樹的正規化 圖9.2.1.3需16個葉子點。往東南方向移動一格，只需七個葉子點。
(a) 移動後的結果 圖 移位後的效果 (b) 移動後的四分樹表示法 圖 ×4黑白影像 適當的移位可以減少葉子數量來達到節省記憶體的功效。

5 9.2.2 深先表示法 圖9.2.1.2的四分樹，用深先搜尋法 內部節點  輸出G 白色外部節點  輸出W 黑色外部節點  輸出B
得到GGWWWGBWBWBWGWWGWWBBB。 可改成((000 (101010(00(00111。 圖 四分樹表示法

6 9.2.3 線性四分樹表示法 線性四分樹 圖9.2.1.2的可表示為 030，032，1XX ， 322，323，33X。
圖 四分樹表示法

7 兩組不同的線性四分樹編碼，還原出一樣的四分樹。
10X, 130, 132, 21X, 22X, 231, 232, 3XX 3XX, 10X, 21X, 22X, 130, 132, 231, 232

8 某內部節點的四個孩子非全為外部節點  輸出2
在CBLQ法中： CBLQ法 白色外部節點  輸出0 某內部節點的四個孩子皆為外部節點  輸出3 黑色外部節點  輸出1 某內部節點的四個孩子非全為外部節點  輸出2 利用廣先搜尋的方式，圖 的表示式為 。 圖 CBLQ樹

9 實驗 照原圖儲存共需65536個位元。實驗結果： 深先表示法需花19024位元 CBLQ法需花17148位元 緊緻四分樹需花13957位元
圖 × 256颱風影像 照原圖儲存共需65536個位元。實驗結果： 深先表示法需花19024位元 CBLQ法需花17148位元 緊緻四分樹需花13957位元 JBIG來壓縮圖需花10976位元 (難運算) 實驗

10 9.2.4 S 樹表示法 以深先搜尋表示 線性樹表 內部節點  輸出0 外部節點  輸出1
圖 圖 的二分樹表示法 線性樹表 顏色表 內部節點  輸出0 外部節點  輸出1 線性樹表可表示為 。 白色葉子  輸出0 黑色葉子  輸出1 顏色表可表示為 。

11 9.3 高灰階影像的空間資料結構表示法 一維線性內插
O點=(1,5)，此處1表示 x 軸的位置而5表示灰階值；C點=(11,13)。A點=(4,?)，則 由 得 A點的灰階值約為7=(5+2)。 圖9.3.1 一維的線性內插 C(11,13) O(1,5)

12 gest(x, y): 線性內插得到的估計灰階值 ε:誤差容忍度
二分樹切割的條件 此處 g(x, y): 原始灰階值 gest(x, y): 線性內插得到的估計灰階值 ε:誤差容忍度 圖 同質的區塊分割圖 圖 二分樹表示法

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

14 重疊策略(Overlapping Strategy)
由於區塊與區塊之間是分開的，會造成區塊效應(Blocking Effect)，採用重疊策略來降低區塊效應的影響。 原先2n×2n大小的影像放大成(2n+1)×(2n+1)的大小。像素分享的特色配合線性內插的平滑性，解壓出來後可降低區塊效應。

15 實驗 在ε=21時，圖9.3.4的 S 樹所需的bpp(Bit Per Pixel)約為1.35位元，這與原始影像一個像素需8個位元相比，壓縮改良率為83%。 圖 ε=21得到的還原影像圖 圖 二元分割後的區塊示意圖 在壓縮比上不如JPEG (Joint Photographic Experts Group)來的好，但在解碼的時間(Decoding Time)上快3~4倍。

16 9.4 基本影像運算之應用 9.4.1 影像加密 網路傳輸前，將資料加密(Encrypt)，使攔截者無法有效的解密(Decrypt)。
圖 影像加密系統

17 (a) 8×8黑白影像 (b) 四分樹結構 圖 影像加密的例子

18 假設影像的大小為 ，掃瞄語言可被定義為文法
定義掃瞄語言 假設影像的大小為 ，掃瞄語言可被定義為文法 代表非終結符號集 代表四分樹中第i層的掃瞄圖案 終結符號集 圖 中定義的24個掃瞄圖案中的一個 代表起始符號 代表文法 G 中的產生規則 為24個掃瞄圖案中的第 i 個掃瞄圖案 圖 個掃瞄圖案

19 模擬例子 給定一組產生規則如下 則圖9.4.1.2(a)的黑白影像被加密成圖9.4.1.4。 利用列掃瞄的方式，
圖 加密後的結果 則圖 (a)的黑白影像被加密成圖 。 利用列掃瞄的方式， 圖 可表示成 ，進而用 來表示。

20 9.4.2 動差計算 動差 動差(Moment)在影像處理的特徵表達上有蠻多的應用。 (p+q)階的動差可表示為 離散型式可改寫為
質心 質心(Centroid) 表示為 ， ( ) ( ) :把灰階值加總起來。

21 一個小例子 所以質心為 。 在連續影像中，質心的變動有時可用來 追蹤物體。 圖 一個小例子

22 中心動差 另外有一種中心動差(Central Moment)也很常用到，其定義為 ( ) 此處 和 。 範例1: 給一3×3的影像如右圖， (1) 請求出 、 、 和此影像的質心。 (2) 請求出 、 、 。

23 解答： (1) 可得質心 。 (2) 解答完畢

24 主軸L的計算 上式亦可改成 圖 物體上求主軸

25 f (x, y)視為加權，如此一來，圖9.4.2.2中物體上所有點累積的慣量可 表示為
似乎地可視為一種偏離軸的慣量而 f (x, y)視為加權，如此一來，圖 中物體上所有點累積的慣量可 表示為 ( ) 最佳的主軸所在會使得式子( )有最小值，也就是相當於在解 下式 ( ) 首先式子( )對α和β分別微分且令為零，可得 ( )  

26 定理9.4.1 物體的主軸會通過質心。 定理9.4.2 物體的主軸與x軸的夾角為 。 和
   和 定理9.4.1 物體的主軸會通過質心。 將 和 代入式子( )中，解 θ 的問題變成了這樣的一個最小化問題 ( ) 式子( )對 θ 微分後令為零，可得  定理9.4.2 物體的主軸與x軸的夾角為 。

27 基於 S 樹的動差計算方法 (參見課本pp.380-386):optional