A Fast-speed Fractal Image Compression Algorithm Based on Eigenvalue Pre-searching

植基於特徵量預搜尋之快速碎型影像壓縮演算法

林俊宏(Chun-Hong Lin) ； 陳飛欽(Fei-Chin Chen)

《中華技術學院學報》 35期 (2006/12) Pp. 153-161

https://doi.org/10.7095/JCIT.200612.0153

摘要

碎型編碼技術對影像壓縮效果令人矚目，然而花費在值域區塊和定義域區塊間的匹配計算量一直是它的最大弱點。本文提出的碎型影像壓縮演算法乃植基於特徵量預搜尋法則：本方法將值域特徵量與事先建立的定義域區塊特徵量比對，挑選特徵量較接近的定義域進行碎型匹配後，決定最佳匹配結果。實驗結果顯示：本文提出的方法較諸傳統碎型影像編碼，在特徵量預搜尋階段選取15個候選者的情況下，節省84.4%的編碼時間，大大節省計算量，並得到30.1dB的優異影像品質。不論候選者個數多寡，影像壓縮率均為12.2。

關鍵字

碎型編碼 ； 特徵量預搜尋 ； 計算量

並列摘要

Fractal coding is a very promising technique for image compression. However, its major drawback is the high encoding complexity to find the best match between a range block and a large pool of domain blocks. This paper presents a fractal-encoding algorithm based on eigenvalue pre-searching. The number of domain blocks searched to find the best match for each range block is safely reduced by eliminating the domain blocks whose eigenvalues are not similar with those of the range block. Simulation results show that the proposed algorithm can produce an almost completely identical fractal code to that of the exhaustive search in reduced time. The proposed scheme promotes an 84.4% reduction in encoding time comparing to the baseline fractal-coding scheme with a little PSNR reduction from 32.8dB to 30.1dB in case of 15 candidates after pre-searching. For single candidate case, the proposed scheme can reduce the complexity up to 85.3%. The compression rate is 12.2 in spite of the number of candidates.

並列關鍵字

fractal coding ； eigenvalue pre-searching ； complexity