Fast Local Search for Fractal Image Compression

Wednesday, January 17, 2001 - 2:45pm - 3:45pm
Keller 3-180
Raouf Hamzaoui (Universität Leipzig)
In fractal image compression, the code for a digital image is a representation of a contractive affine mapping whose fixed point is an approximation to the image. The decoding consists of iterating the contractive mapping until convergence to the fixed point. Fractal image compression was introduced by Barnsley and Jacquin in the late eighties. Since then, many researchers have improved the original approach in various ways. Unfortunately, the rate-distortion results of the best fractal coders are still inferior to those of the state-of-the-art in image compression. However, the potential of fractal image compression has not been fully exploited because current fractal schemes do not find optimal codes. Optimal fractal image compression is an NP-hard combinatorial minimization problem where the set of feasible solutions is a large finite set of contractive affine mappings, and the cost function is the error between the original image and the fixed point of one such mapping. Current fractal image schemes are based on a greedy suboptimal algorithm known as collage coding. In this talk, I will present a local search technique that can significantly improve an initial solution found by collage coding. The complexity of local search, which requires successive computations of the fixed point of an affine mapping of a high-dimensional space, is drastically reduced by combining a graph algorithm and a Gauss-Seidel like iterative method.