影像碎形压缩编码.ppt

分割版疊代函數系統 仿射轉換vi的收縮性隱含在下列兩個事實： vi(Dj)= Ri Dj is of size 2?Ri??2?Ri? 灰階值的轉換可以表示成gi(z)=si?z+oi 很明顯地，只要 si1，則所有的gi對灰階階具有收縮性。 實驗結果顯示，取si1.2就可以，而且這樣的編碼結果還會稍微好一點。 分割版疊代函數系統 我們能夠取si 1是因為我們所要的是 Tm具收縮性而非T ，其中m1。 T 或 gi 可以不具備收縮性，前提是存在一個整數m1，使得Tm 具備收縮性。 Tm 具備收縮性可以推得Tn 具備收縮性，對nm。 也即定點特性是滿足的。 影像碎形壓縮- 編碼 假設有一個大小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? Rotate by 180? Rotate 270? 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 步驟３：如 VVt 則 傳送 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. 影像碎形壓縮 簡介 “碎形（factal)”很難下定義。 然而，如果我們考慮一個集合F為碎形，則它包含下列的特性： F是指某種形狀、結構的一個局部或片斷。 F 在實際、近似或統計上是自我相似的。 它通常可以用一個簡單的演算法產生。 例如樹：樹幹分成樹枝，樹枝又分成較小的樹枝， …，直到最小的樹枝，它們都是相似的。 簡介 其他的例子包含：雲、森林、 星雲、 樹葉，羽毛、 花、 岩石、 山、 地毯、 磚等等 人眼看起來覺得很複雜，但實際上包含的資訊量郤是非常的低，因為它們可以用一個簡單的演算法來描述。 它們可以經由重複地自我拷貝或部份的自我拷貝而產生。 因此，其累贅度相當高。 碎形的應用有：影像切割、 影像分析、 影像合成、 以及影像壓縮等 簡介 Barsley是第一個使用碎形技術做影像壓縮的人。 他的演算法一直沒有公諸於世，倒是開了間公司賣他的碎形影像壓縮程式。 A. Jcquin是Barsley’s的博士班學生，它發表了一個植基於規則分割(regular partitioning) 而類似於Barsley方法的碎形壓縮演算法。 Fisher在1991年提出了改良版. 什麼是影像碎形壓縮? 我們使用Fisher 提出的一個有名的例子作為開始。 想像我們有一台特製的影印機能將輸入影像縮小一半並且拷貝成三份。 什麼是影像碎形壓縮? 如果我們將這台機器的輸出再當成輸入，會發生什麼情況？ 我們發現，不管輸入影像為何，它最後的結果都收斂到同一張影像。 我們稱這張收斂影像為這部影印機的歸結圖 (attractor)。 只要重複地使用這部