R. Hamzaoui, D. Saupe. Fractal image compression with fast local search. Vol. 132, pp. 107-120, Springer, 2002.
Optimal fractal image compression is an NP-hard combinatirial optimization problem where the domain of feasible solutions is a large finite set $\mathcal{T}$ of contractive affine mappings, and the cost function is $\|f^*-f_T\|^2_2$, where $f^*$ is the original image, and $f_T$ is the fixed point of $T n \mathcal{T}$. In contrast, traditional fractal coders are based on a greedy algorithm known as collage coding, which minimizes $\|f^* - T(f^*)\|^2_2$. We describe a local search algorithm that rapidly improves the solution obtained by collage coding. In particular, we show how the successive computations of the cost function can be efficiently done by combining a Gauss-Seidel like iterative method and a graph algorithm
@InCollection{HaSa02,
Author = {Hamzaoui, R. and Saupe, D.},
Title = {Fractal image compression with fast local search},
Journal = {IMA Volumes in Mathematics and its Applications},
Volume = {132},
Pages = {107--120},
Publisher = {Springer},
Year = {2002}
}