影像碎形壓縮

簡介 “碎形（factal)”很難下定義。 然而，如果我們考慮一個集合F為碎形，則它包含下列的特性： 它通常可以用一個簡單的演算法產生。 例如樹：樹幹分成樹枝，樹枝又分成較小的樹枝， …，直到最小的樹枝，它們都是相似的。

簡介 其他的例子包含：雲、森林、 星雲、 樹葉，羽毛、 花、 岩石、 山、 地毯、 磚等等 人眼看起來覺得很複雜，但實際上包含的資訊量郤是非常的低，因為它們可以用一個簡單的演算法來描述。 它們可以經由重複地自我拷貝或部份的自我拷貝而產生。 因此，其累贅度相當高。 碎形的應用有：影像切割、 影像分析、 影像合成、 以及影像壓縮等

簡介 Barsley是第一個使用碎形技術做影像壓縮的人。 他的演算法一直沒有公諸於世，倒是開了間公司賣他的碎形影像壓縮程式。 A. Jcquin是Barsley’s的博士班學生，它發表了一個植基於規則分割(regular partitioning) 而類似於Barsley方法的碎形壓縮演算法。 Fisher在1991年提出了改良版.

什麼是影像碎形壓縮? 我們使用Fisher 提出的一個有名的例子作為開始。 想像我們有一台特製的影印機能將輸入影像縮小一半並且拷貝成三份。

什麼是影像碎形壓縮? 如果我們將這台機器的輸出再當成輸入，會發生什麼情況？ 我們發現，不管輸入影像為何，它最後的結果都收斂到同一張影像。 我們稱這張收斂影像為這部影印機的歸結圖 (attractor)。 只要重複地使用這部影印機夠多次，任何起始影像都不會影響到這部影印機的歸結圖的樣子。

什麼是影像碎形壓縮?

什麼是影像碎形壓縮? 事實上，決定最後影像的樣子的是拷貝的位置與方向。 由於決定這部影印機歸結圖最後樣子的是轉換的方式，因此我們只需描述這些轉換便足夠了。

什麼是影像碎形壓縮? 不同的轉換會導致不同的歸結圖，而這些轉換則必須滿足收縮性 (contractive)。 換句話說，在輸入影像上面的任何兩點經過轉換之後，在拷貝版的這兩點必須變得比原來還靠近。 縮放性的條件是非常的自然，因為如果拷貝版上的距離反而增大，那麼歸結圖將會變成無限大。

什麼是影像碎形壓縮? 除了收縮性條件外，轉換可以是任何一種形式。 實際上，仿射轉換(affine transformations) 可以產生相豐富又有趣的歸結圖。 仿射轉換可以將原輸入影像弄斜、展開、旋轉、 平移及放大縮小，特別是，它一定將正方形對應成平行四邊形。

什麼是影像碎形壓縮? 仿射轉換的例子

什麼是影像碎形壓縮? 利用一些轉換的集合來儲存，可以達到影像壓縮的目的。. 考慮Barsley展示的第三種例子：羊齒植物，它包含了四個仿射轉換。 每一個仿射轉換 ti 可以用ai，bi，ci，di，ei 及 fi六個數目定義出. 假設我們用32個位元來表示每一個數目，則這四個轉換可以存放在4  6 32 = 768 bits。

什麼是影像碎形壓縮? 碎形壓縮４倍的解碼影像（左）及原影像（右）之部份放大比較（碎形放大後仍細緻平滑）。

d(t(p1),t(p2)) < sd(p1,p2), 理論基礎 收縮性(contractive)轉換及疊代函數系統。 定義: A transformation t is said to be contractive if for any two points p1, p2, the distance d(t(p1),t(p2)) < sd(p1,p2), for some s < 1.

理論基礎 這個定義非常的廣泛，可以用在我們有先定義距離公式d(p1,p2)的任何地方。 以常用的歐基里得距離為例，若 p1=(x1,y1) 且 p2=(x2,y2), 則

理論基礎 依照以上的定義，轉換 t = 滿足收縮性，並且兩點的距離會縮短一半。 任意選擇一個點，並應用這個轉換　　　　　　多次，最後將發現 p 被送往(1,1) 這個點。 上例的(1,1)點，稱之為定點。

理論基礎 收斂性轉換可以送任何輸入點到特定定點的特性，我們稱之為此收縮轉換之定點性質。 令 pf 表示收縮轉換 t 之定點，則對任何一個輸入點 p，下列的式子成立：

理論基礎 轉換 t會送任何點到 pf 。 t(pf )=pf pf 具備唯一性。

疊代函數系統 在數學的領域，我們前面所引用的重複拷貝之影印機可以用疊代函數系統(iterative function system；IFS )來描述。 一個IFS包含一些由 R2對映至R2 的收縮轉換所成的集合。 這個轉換集合定義了一個(巨)轉換 而這個轉換的對象則是一個二元影像， f0。

疊代函數系統 舉例而言，假設在第３個例子的╘ 圖是我們的初始二元影像 f0。 這個例子使用了在巨轉換T 的4個收縮性轉換，T 將初始二元影像對映成第二格的二元影像。 其中四個轉換各自產生自己的結果，ti(f0) ，而它們的聯集便是T(f0)，也就是第二格的二元影像。 其中 f0={pj |pj 為構成f0圖案╘ 的黑色像素位置}。

疊代函數系統 如果在T 的所有 ti 為收縮性，則 T 也具收縮性。即T也有一個 “定點”。 Ｔ的定點便是最後的收斂二元影像，如第三例的第三格之羊齒植物的葉子。

疊代函數系統 以此類推, fn=T(fn-1)=T(T(fn-2))=…=Tn(f0). 令T為 T的定點， 則 T為唯一。

疊代函數系統 如果考慮灰階影像，則將會比二元影像多一個維度。 也就是， {(xi,yi,zi)zi=f(xi,yi)為在位置(xi,yi)的灰階值}。 距離及灰階值必須同時滿足收縮性特性。 位置的收縮性需求可以由演算法的設計自然滿足。 所以編碼方法會著重在灰階值的接近。

疊代函數系統 轉換的定點為解碼所得到影像。 第三例的羊齒植物葉，它的自我相似性是全面的。 然而，灰階影像的自我相似性只是局部性，而不存在一些仿射轉換可以轉換它們。 但灰階影像還是具有另一類的自我相似性。 即解碼影像不是由整張原影像的拷貝所形成，而是由原影像的部份拷貝而成。

疊代函數系統 解碼影像與原影像之間允許一些誤差，即將影像表示成一組轉換所得到的不是原影像，而是一張和它差不多的一張影像。

分割版疊代函數系統 特製影印機 : 分割版的影印機 額外的兩個能力: 這些額外的特性可以用來編碼灰階影像 原始影像的數個拷貝會合起來形成輸出影像 每個拷貝會經過位置、尺寸、歪斜，伸展及旋轉等因子的調整 分割版的影印機 額外的兩個能力: 每一個拷貝有調整灰階值之明亮度及對比度的能力 對每一個拷貝，有一個遮罩可以選擇原始影像的部份來拷貝 這些額外的特性可以用來編碼灰階影像 partitioned iterated function system (PIFS).

分割版疊代函數系統 令定義域方塊 Dj (domain blocks;) 為所有重疊、 固定大小的1616像素子區塊的集合，而值域方塊 Ri (range block)為影像中的88像素的非重疊子區塊 歸結圖可以分割成N=512512/(8 8)的值域方塊， 而且每一個值域方塊Ri只決定於一個轉換ti 。 換句話說，Ri 是ti歸結圖。 為了讓灰階值可以收斂到一個固定值，ti 可以調整，一個值域方塊的對比及明亮度。

分割版疊代函數系統 對一個值域方塊Ri， ti固定只取某一特定的定義域方塊Dj 做轉換，而不是整張影像 令Dj初始影像的定義域方塊，則 因為值域方塊的尺寸很小，將它表示成一個碎形影像也不至於有太大的誤差。 Dj 和 Ri 都是取自同一張灰階影像：先從f0 (原始影像)取得Dj，求得Ri；這些 Ri聯合起來形成f1，然後來由f1取得新的Dj，並計算新的Ri，這些新的Ri再一起形成f2，以下類推。

分割版疊代函數系統 一個PIFS的仿射轉換可以表示為 : 其中 si 控制轉換的對比度，oi 控制轉換的明亮度。 上式座標轉換的部份可以表示成：

分割版疊代函數系統 轉換vi決定了定義域方塊Dj 被對應至值域方塊Ri的方式（可能是旋轉、鏡射、 平移或者更複雜的仿射轉換），而si 及oi 決定了轉換的對比及明亮度。 T=t1t2t3…tN，其中 v1v2v3…vN 為座標轉換。 如果所有的vi具備收縮性，則T 在座標轉換上也具備收縮性。

分割版疊代函數系統 仿射轉換vi的收縮性隱含在下列兩個事實： 灰階值的轉換可以表示成gi(z)=siz+oi vi(Dj)= Ri Dj is of size 2Ri2Ri 灰階值的轉換可以表示成gi(z)=siz+oi 很明顯地，只要 si<1，則所有的gi對灰階階具有收縮性。 實驗結果顯示，取si<1.2就可以，而且這樣的編碼結果還會稍微好一點。

分割版疊代函數系統 我們能夠取si >1是因為我們所要的是 Tm具收縮性而非T ，其中m>1。 T 或 gi 可以不具備收縮性，前提是存在一個整數m>1，使得Tm 具備收縮性。 Tm 具備收縮性可以推得Tn 具備收縮性，對n>m。 也即定點特性是滿足的。

影像碎形壓縮- 編碼 假設有一個大小512512的256灰階影像 則此影像有4096 (不重疊)的值域區塊, R1, R2,…, R4096 (8 ×8) 它也有497497＝247,009 (重疊) 定義域區塊(16 ×16) 對每一個值域區塊 Ri，在所有的定義域區塊D，去尋一個DjD ，並且在所有可能的轉換，去尋找一個tk ，使得 d(tk(Dj’), Ri)為最小，其中 Dj’ 為 Dj 的子取樣版本(from 1616 to 88)且tk=vk+gk.

影像碎形壓縮- 編碼 為了降低計算負擔，vi 可以限制在下列八個簡單的轉換之一： Rotate by 0 Rotate by 90 Flip over the vertical middle line Flip over the horizontal middle line Flip over the 45 line Flip over the 135 line

影像碎形壓縮- 編碼 令a1, a2, a3, …, an 為從轉換後區塊Dj的子取樣Dj’的影像點，且 b1, b2, b3, …, bn 為值域區塊Ri的影像點，則可以選擇在 gi 的si 及 oi 如下：

影像碎形壓縮- 編碼 可以證明，如此的 si 及 oi 可以最小化下列的錯誤度量:

影像碎形壓縮- 編碼 步驟１：對原始影像每一個值域區塊 Ri ，進行下列步驟２及３的編碼。 步驟２：計算Ri的變異數V 步驟３：如 V<Vt 則 傳送 Ri的平均值 否則 尋找tk, Dj ，使得 d(tk(Dj’), Ri)為最小。 傳送 tk 及Dj的位置

影像碎形壓縮- 編碼 計算量: 247,009 定義域區塊 ８個可能的轉換 4096 值域區塊

影像碎形壓縮- 解碼 步驟１：對每一個值域區塊Ri，進行步驟２。 步驟２：如果是平均值，則 設定給Ri 否則 設定Ri為tk(Dj’)

影像碎形壓縮- 解碼

影像碎形壓縮- 解碼

影像碎形壓縮- 實驗結果 128128 Cr 大約為 17 用8個bits在 x及y方向來決定Dj的位置。 vi ： 3個bit si： 5個bit oi： 7個bit It takes about two hour CPU time on Sun Ultra 2.