分形壓縮

分形壓縮（en:Fractal compression），特別適合壓縮自然景觀的圖片，依賴於特定的圖像及同一副圖像的一部分與其他部分的相似程度。Michael Barnsley在1987年提出分形壓縮技術，最廣為人知的具有實際用處的分形壓縮算法是由Barnsley和Alan Sloan提出的。所有的這些算法都是基於使用疊函數系統的分形變換。 ^[1] 

分形壓縮沒有被廣泛的使用，這是因為分形壓縮的壓縮和解壓速度遠比JPEG慢，此外，它的專利也不允許被廣泛使用。

對於低質量的圖象，分形壓縮比JPEG優越，另一個優於JPEG的方面是當圖像被放大時，採用分形壓縮的圖像比JPEG圖像質量要高。

分形壓縮最大能達到10000:1的壓縮率，但是還不夠成熟。

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

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

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

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

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

T的定點便是最後的收斂二元影像

。

因此，

，以此類推可求得

。

令|T|表T的定點，則T的定點（集）可以表示成：

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

總結來説，給定一張輸入二元影像f₀，應用迭代函數系統T一次，則可得到

，應用兩次則得到

。他的定點是

，與起始二元影像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)點的灰階值}。

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

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

1987年, Michael Barnsley 創建了分形壓縮的概念和方法, 他因此而持有多個技術專利. Barnsley 和 Alan Sloan 發明了可用於實踐的分形壓縮算法. 1992年, Barnsley的研究生Arnaud Jacquin 開發了第一個應用於圖形壓縮的分形壓縮軟件. 所有這些方法都是基於使用迭代函數系統(Iterated function systems)的分形變換(fractal transform). Michael Barnsley 和 Alan Sloan 1987年發明的迭代函數系統已經被授予了與分形壓縮相關的20多個專利。

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

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