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

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

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

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

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

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

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

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

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

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

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)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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