Fractal image compression based on delaunay triangulation

This thesis deals with fractal compression of still images, based on the theory of iterated function systems (IFS). After an overview of the main lossy and lossless still image compression methods, we introduce the IFS theory. Then, we detail the main fractal compression algorithms proposed in the literature. A coder involves comparisons between two sets of blocks. A block in the partition of the original image must be approximated by a collage block, with a contractive function. We therefore present different partitioning schemes used for the modelisation of the local-similarities in the images. Thereafter, our algorithm based on the Delaunay triangulation is explained, which constitutes the major contribution of our work. This flexible scheme allows to construct different triangulations, in a image content dependant way. In order to improve the coder-decoder, we propose different solutions. The first method allows to reduce the encoding complexity by the use of a scheme for quantizing the blocks. The second method makes use of a mixed partition composed of triangles and quadrilaterals in order to improve the visual decoding quality at low bit rates. To conclude this work, we compare decoding results computed on different partitioning schemes and we do a comparison between the block based fractal methods and recent hybrid methods merging fractal image compression and wavelet, or Fourier transform methods.Ce mémoire traite de la compression des images fixes par fractales, fondée sur la théorie des systèmes de fonctions itérées (IFS). Après quelques rappels sur les principales méthodes de codage entropique et de compression réversible et irréversible des images nous introduisons les notions nécessaires à la compréhension de la théorie des IFS. Nous détaillons ensuite les principaux algorithmes de compression des images naturelles selon l'approche fractale. Ces derniers consistent à approximer chacun des éléments d'une partition à l'aide d'une transformation locale contractante appliquée sur une autre partie de l'image. Ceci nous conduit à présenter les modèles de partitionnement utilisés pour coder les similarités locales des images. La partie suivante constitue la contribution majeure du travail. Nous présentons un algorithme de codage par fractales fondé sur la triangulation de Delaunay. La souplesse de ce modèle nous permet d'utiliser diverses triangulations adaptées au contenu de l'image à compresser. Nous proposons ensuite différentes solutions ayant pour but d'améliorer le schéma de codage-decodage. La premiere vise à réduire la complexité de la phase de codage en diminuant le nombre de comparaisons inter-blocs, par un algorithme de quantification vectorielle de l'espace de recherche. La seconde vise à réduire le nombre de blocs traités tout en améliorant les résultats visuels, pour des taux de compression élevés. Ceci est fait en introduisant des quadrilatères dans la triangulation de l'image. Nous concluons le mémoire en commentant différents résultats de décompression obtenus à partir des partitionnements étudiés, puis comparons ces résultats à ceux obtenus à partir de méthodes hybrides liant le codage par fractales à une décomposition multirésolution de l'image ou à la transformée en cosinus discrète