分形压缩

分形壓縮 (Fractal Compression)又名碎形壓縮，是一種破壞性資料壓縮（失真壓縮）的方法，是一種以碎形為基礎的图像压缩，適用於紋理及一些自然影像。

當需要壓縮的影像自身存在部分相似性，則適用分型壓縮。這些圖案的共同特性為，雖然人眼會覺得圖片看起來複雜無比，但實際上圖片卻只包含非常低的資訊量，因此可以經過一個簡單的演算法產生。分形演算法將這些圖片轉換為名為「分形編碼」的數據資料，此種密碼用來重新建立加密（壓縮）過的圖檔。

簡而言之，分形壓縮就是利用自我相似縮小來壓縮，解壓縮則反之，是利用自我相似放大來解壓縮。

理論基礎

参见：迭代函数系统

在數學領域中，分形影像的壓縮可以用迭代函数系统來描述。

二元影像

二元圖片可被視為一個R²的子集合，一個疊代函數系統被定義為許多由平面R²對映至R²的收縮（contraction）轉換所成的集合，即t₁,…,t_n。

T={ti: R² → R² | i=1,2,…,n}

此種轉換集定義了一個（巨）轉換，轉換對像則是二元影像f₀，二元影像f₀表示成點所成的集合。

一個重要的事實是：如果所有的t_i都具備收縮性，則T具備收縮性，而且T也有定點。

T的定點便是最後的收斂二元影像$T(f_{0})=t_{1}(f_{0})\cup t_{2}(f_{0})\cup \cdots \cup t_{n}(f_{0})=f_{1}$

因此，$T^{2}(f_{0})=T(f_{1})=t_{1}(f_{1})\cup t_{2}(f_{1})\cup \cdots \cup t_{n}(f_{1})=f_{2}$，以此類推可求得$T^{n}(f_{0})$。

令|T|表T的定點，則T的定點（集）可以表示成： $|T|=f_{\infty }=\lim _{n\to \infty }T^{n}(f_{0})$

T的定點也是唯一的。也就是說，不管起始的二元影像為何，我們可以重複地將T應用在他上面並且在最後收斂到一張固定的二元影像（定點）。因此，T本身就決定了一張二元影像。

總結來說，給定一張輸入二元影像f₀，應用疊代函數系統T一次，則可得到$T(f_{0})$，應用兩次則得到$T^{n}(f_{0})$。他的定點是$\lim _{n\to \infty }T^{n}(f_{0})$，與起始二元影像f₀昰什麼完全無關，只決定於T。

灰階影像

灰階影像與二元影像的最大不同處在於灰階影像比二元影像多了一個維度。我們可以將一張二元影像表示成許多平面上的點所成的集合，每一個點代表它在影像中是黑色，沒在集合內的點則屬於背景的白色。

因此，可以將一張二元影像表示成{(x_i,y_i)|(x_i,y_i)的顏色為黑色}，換句話說，我們可以將一張二元影像表示成許多位置（平面上的x座標語y座標）所成的集合，而收縮性（兩個點的位置愈來愈靠近）與定點（收斂到某一個特定位置的點）等定義也都是針對位置而言。灰階影像則不然，它除了位置之外，還多了一項灰階值，換句話說，它必須表示成{(x_i,y_i,z_i)|z_i=f(x_i,y_i)，為(x_i,y_i)點的灰階值}。

這麼一來，轉換的收縮性既要滿足兩點的位置變靠近也要滿足兩點的灰階值也變接近，這樣子的轉換會使分形壓縮變複雜。

由於自然灰階影像的自我相似性不是全面的，而是局部的，因此所採用的編碼方法實際上允許將轉換的收縮性著重在灰階值的接近，至於位置的變靠近則由於演算法的設計自然滿足。轉換的定點，當然就是解碼所得到的影像。

特色

使用分形壓縮，由於需要搜尋影像自身的相似性，加密過程需經過大量的運算，所需的計算量非常龐大，但解碼則是非常迅速。此種加密和解密的差異性令分形壓縮無法實際廣為應用，尤其當影片需要由影碟或文件上下載時，分形壓縮更顯劣勢。

在普遍的壓縮率下，約莫50:1，分形壓縮提供和離散餘弦轉換（DCT）相似的結果，例如JPEG。在高壓縮率下分形壓縮可提供高品質，對壓縮率高達170:1的衛星圖而言，分形壓縮的結果是可以被接受的。在合理的壓縮時間範圍下，分形視訊影片壓縮率可達到25:1~244:1的壓縮率。

相關條目

• 迭代函数系统
• 图像压缩
• 小波分析