Distortion Minimization with Fast Local Search for Fractal Image Compression |
| |
Authors: | Raouf Hamzaoui Dietmar Saupe Michael Hiller |
| |
Affiliation: | Institut für Informatik, Universität Leipzig, Augustusplatz 10-11, Leipzig, 04109, Germanyf1 |
| |
Abstract: | Optimal fractal image coding is an NP-hard combinatorial optimization problem, which consists of finding in a finite set of contractive affine mappings one whose unique fixed point is closest to the original image. Current fractal image schemes are based on a greedy suboptimal algorithm known as collage coding. In a previous paper, Hamzaoui, Hartenstein, and Saupe proposed a local search algorithm that iteratively improves an initial solution found by collage coding. For a standard fractal scheme based on quadtree image partitions, peak-signal-to-noise ratio (PSNR) gains are up to 0.8 dB. However, the algorithm is time-consuming because it involves many iteration steps, each of which requires the computation of the fixed point of an affine mapping. In this paper, we provide techniques that drastically reduce the complexity of the algorithm. Moreover, we show that the algorithm is also successful with a state-of-the-art fractal scheme based on highly adaptive image partitions. |
| |
Keywords: | Abbreviations: fractal image compressionAbbreviations: combinatorial optimizationAbbreviations: NP-hard problemsAbbreviations: local searchAbbreviations: graph algorithms |
本文献已被 ScienceDirect 等数据库收录! |
|