Impact of Spatial Dynamic Search With Matching Threshold Strategy on Fractal Image Compression Algorithm Performance: Study

Abstract

Fractal image compression (FIC) is a very popular technique in image compression applications due to its simplicity and superior performance. However, it has a major drawback, which is the long encoding time. This is due to the requirement of performing huge similarity search for encoding each small portion in the image. Thus, reducing the search time of FIC while keeping the quality of reconstructed images at acceptable level is still an active research topic. Therefore, this paper has focused on studying the search problem of the conventional full-search FIC algorithm and the impact of employing a spatial dynamic search technique instead with the matching threshold strategy. Unlike the conventional full-search method that is a spatially static where the search starts from a fixed position (normally from the top-left corner of the image to the bottom-right corner) regardless of the position of the range block being encoding, the idea of the dynamic search method is simple, but effective, and it is based on starting the search from the closest domain block to the range block that needs to be encoded. These two search schemes are tested under different matching threshold values, in which the search is terminated whenever a domain block with an acceptable matching level is found. To make the study comprehensive, the test is performed for different image sizes and types, range block and partitioning step sizes, and quantization levels. The experimental results show the significant impact of using the dynamic search method instead of the conventional search method specifically when the threshold is large. For the best encoding parameters, the improvement amount that can be achieved is near to 90 % in terms of search reduction and 1.6 dB PSNR in terms of image quality.

Keywords

• Fractal image compression
• fast search method
• full search scheme