第十一章 空間域上的壓縮與應用

11.1 前言 11.2 四角片式的漸近圖形傳輸 11.3 灰階影像的S樹表示法 11.4 區塊的統計量計算 11.5 植基於S樹的區域分割 11.1 前言 11.2 四角片式的漸近圖形傳輸 11.3 灰階影像的S樹表示法 11.4 區塊的統計量計算 11.5 植基於S樹的區域分割 11.7 作業

11.2 四角片式的漸近圖形傳輸 轉換MRPCA(Multiresolution Representation Polygonal Curve Approximation)問題成解一個NTTLS(Near-Toeplitz Tridiagonal Linear Systems)的問題 二層之間維持固定比例：給一　　　 個控制點的多邊形曲線 　， 上的個控制點可表示為 。　上的控制點表示為 　　　　　　　　　　　。 為 線段的中點所在。 和 彼此之間的點數比例為 。 圖11.1　 和 的關係

最小平均方差(Minimum Mean Square Error)： PCA問題相當於如何決定 使得下式有最小值 (11.1) 式(11.1)中的 、 和 定義如下 式(11.1)的最小化原理相當於 的最小化。

令 當 ； 當 (11.2) (11.3)   此處 令  (11.4) 則我們得到NTTLS的式子，如式(11.4)。

將PCA問題所對應的式(11.4)擴充到QSA的問題上 　的控制點個數為　的控制點個數之4倍：給一四角片構成的曲面　，曲面上的　　　　　　　個控制點表示為 　　　　　　　　　　　　　　　　　　　　。 　可表示為　　　　　　　　　　　　　　　　　 。 令 為線段 的中點，而 為線段 的中點。又令 為線段 的中點。 圖11.2　　和　 的關係

最小平均方差(Minimum Mean Square Error)： QSA問題相當於如何決定 使得下式有最小值 (11.5) 式(11.5)中的 f1和 x 軸有關；f2和 y 軸有關，f3而和 z 軸有關，其中 f 的最小化等同於 f1 的最小化。

令 ，我們得到 (11.6) 式(11.6)的 可由下式求得 補助定理11.1　所有的 係數， 和 ，可在 個浮點計算量之下完成。

將式(11.6)中的左式重新整理後，可得 令 (11.7) 則式(11.6)可改寫為 (11.8) l 的範圍介於1到n之間，所以式(11.8)共有n個NTTLS待解。 補助定理11.2　一個NTTLS可在 個浮點運算花費下完成 的 求解。 補助定理11.3　式(11.8)可在 個浮點計算量下完成所有 的 求解。

我們可利用求解出來的 ，進一步求得 的解集合。式(11.7)可表示為下式 (11.9) 由於k的範圍介於1到m之間，故式(11.9)共有m組NTTLS待解。 補助定理11.4　式(11.9)可在 個浮點計算花費下完成 的 求解。 定理11.5　我們花費 個浮點計算量可完成QSA問題的求解。 已知任兩相鄰的四角片曲面之間的控制點數量之比例為 ，所以求解MRQSA需花費 個浮點計算量。

定理11.6 MRQSA問題可在花費 個浮點計算量下完成求解。 (b) (c) (d) 圖11.3　第一個四層的MRQSA之模懝

11.3 灰階影像的S樹表示法 給一 大小的區塊如圖11.5所示。若該區被稱為同質(Homogeneous)區塊，則需滿足下式 (11.10) 和 ，上式中的 可依下列三個線性內插式求得 這裡 圖11.5　一個同質的區塊

圖11.7　四分樹表示法 圖11.6　區塊分割圖 線性樹表：00110111101111010111101111011110011111110011110111111 顏色表： 圖11.8　S樹表示法

11.4 區塊的統計量計算 頂端線段 代表從點 到點 之間。底端線段 代表從點 11.4 區塊的統計量計算 頂端線段 代表從點 到點 之間。底端線段 代表從點 到點 之間。左邊線段 代表從點 到點 之間。 代表從點 到點 之間的線段。 在這四個線段上，兩相鄰的像素間之灰階異動可表示如下 (11.11) 圖11.5　一個同質的區塊

位於 的估計灰階值表示為 。從 到 的灰階異動可表示如下 (11.12) 從 到 的灰階異動可表示如下 (11.14)

補助定理11.7　位於 的像素，其估計灰階值為 。 證明：位於 的估計灰階值為 (11.15) 根據式(11.15)，位於 的估計灰階值等於 從式(11.14)，可得到 證明完畢。

補助定理11.8　區塊 的平均值為 。 證明：根據平均值的定義， 的平均值可計算如下 因此，我們得到 證明完畢。

補助定理11.9　 的估計灰階值之平方和等於 ，這裡 。 證明：

從  令 ，則上式可改寫成 證明完畢。

補助定理11.10　 區塊的變異數等於 證明：區塊 的變異數可計算如下 利用補助定理11.9，我們得到 證明完畢。

給定兩個待合併的區域A和B，若A和B可以合併的話，則需滿足下列二個條件：(1) 。(2)合併後的區域C，其　　　 。這裡 和　為二個設定的門檻。 證明完畢。

補助定理11.12　 合併後的區域C，其變異數 。 證明： 證明完畢。

綜合上述推演出來的結果，我們得到下列第一個主要結果。 定理11.13　任一區塊的平均值灰階值和變異數可在 時間內完 成；合併後的區域，其平均灰階值和變異數亦可在 的時間內完成。

11.5 植基於S樹的區域分割 定義11.1 活躍區域(Active Region) 指的是由某些區塊集合而成的區 域，且該區域仍有可能和其鄰近 的區域合併為一更大的區域。反 之，不活躍(Inactive)區域指的是 該區域不會再和其它鄰近區域有 合併的可能。 定義11.2　一個區域不管是活躍或 不活躍，我們用該區域的邊來表 示之。每段邊可能為活躍邊或不 活躍邊。對一個活躍的邊而言， 它可能和相鄰的不活躍邊合併而 消失掉；也可能因為和相鄰的邊 不能合併而轉為不活躍的邊。 圖11.9　圖11.6的區域分割圖

定義11.3 在S樹的表示方式中，已被拜訪及處理過的區域集和未 被拜訪過的區塊存在有接攘的線段集，這接攘的線段 集就叫波形(Waveform)。 圖11.10　一個波形的例子 圖11.11　線段(Segment)的資料結構

圖11.12　一個活躍區域的資料結構

圖11.13 Leaf_Operation程序對區塊28的模擬例子 (b)　合併區塊28和區域B 圖11.13　Leaf_Operation程序對區塊28的模擬例子

圖11.13 Leaf_Operation程序對區塊28的模擬例子 (c)　檢查和區域A的合併可能 (d)　區域A不能合併後 圖11.13　Leaf_Operation程序對區塊28的模擬例子

圖11.13 Leaf_Operation程序對區塊28的模擬例子 (e)　合併區域B和區塊10 (f)　修正波形的線段 圖11.13　Leaf_Operation程序對區塊28的模擬例子

定理11.14 令B為S樹表示法中位元1的個數，植基於S樹表示法的 區域分割演算法可在 的時間內完成，這裡 為接近常數的複雜度。 證明：在我們以上所介紹的區域分割演算法中，一旦在線性樹表中讀到位元0，就執行Region_Segm，故總共需呼叫 次Region_Segm程序，這裡A代表線性樹表中位元0的出現個數。一旦在線性樹表中讀入位元1，則呼叫Leaf_Operation。假設線性樹表中的位元1之總個數為B，那麼共需呼叫 次Leaf_Operation程序。針對一個位元1，會產生一個新的區塊。在波形上，至多有四個線段會和這新產生的區塊之邊相接攘，因此最多有4B次的合併動作需被執行。由前面的敍述已知，合併任兩個活躍區域只需 的時間，卻需 的花費來完成全部Union-Find的運算。因為 ，所以植基在S樹的表示法之區域分割法可在 的時間內完成。證明完畢。

(a)　原始影像 (b)　 之下的分割區塊 圖11.15　 區域分割結果的比較 (c)　 和 條件下， 我們的方法之區域分割結果 (d)　每一區域用其平均值圖示

11.7 作業 習題一： 　　分析11.2節中MRQSA方法的數值穩定度。 習題二： 　　利用C語言，寫一程式將灰階影像轉換成S樹表示法。