Adaptive image partitioning for fractal coding achieving designated rates under a complexity constraint

Fractal image coding is a relatively new technique for compact image representation. The basic coding scheme exploits self-similarities between parts of the image and other parts in it at a different resolution. The various parts are consequences of a partition grid obtained by applying a splitting criterion to the image. We present an algorithm for adaptive image partitioning, achieving designated rates under a computational complexity constraint. The proposed algorithm results in a reduction of the computational complexity as compared to other known algorithms at the same rate-distortion operating point. Also presented is an efficient procedure for approximating parts in the image by a linear combination of two other parts in it and its combination with the adaptive partitioning algorithm