An Improved Full-search Fractal Image Compression Method with Dynamic Search Approach

Encoding Image and video can be performed by different techniques. One of the popular technique is known as fractal-image-compression (FIC) method. Although it has several advantages like simplicity, resolution independent, and fast decoding, it has one main disadvantage, i.e. the compression time. This attributes to the requirement of conducting intensive similarity searches in order to map the image’s blocks together. The way of performing the search is a key point in the encoding speed. Therefore, this paper introduces a dynamic full-search approach for FIC method. The dynamic search is based on initiating the search from the nearest domain block to the range block required to be encoded, and the search window is expanded till an desirable matched domain block is detected or the search window covers the entire image. Although the proposed dynamic-search method looks simple, it is more efficient than the standard full search method which generally initiates the search, for each range block, from a static position (i.e. generally the top-left corner of the image and down to the bottom-right corner) regardless of its location. As a compromise between the image quality and the encoding time, a matching threshold equal to 500 has been used. For evaluation, the proposed method is compared with the traditional full-search method in terms of number of searches performed, and the quality of the decompressed image. For a 265 $\times$ 256 grayscale Lena image, the presented method is able to significantly decrease the search amount by 23 % compared to the traditional method, and also improve the image quality by 0.5 dB.