Soutenance mémoire
« Votre temps est limité, ne le gâchez pas en menant une existence qui n’est pas la vôtre ». Steve Jobs .
La taille des images augmente proportionnellement à leur qualité et leur stockage et transmission qui constituent donc les enjeux principaux dans le monde numérique. La compression s’impose comme une étape incontournable pour optimiser l’utilisation de ces grands volumes d’informations dans les réseaux informatiques. L’objectif principal de la compression d’image est de réduire la quantité d’information nécessaire à une représentation visuelle fidèle à l’image originale. En générale on différencie les méthodes de compression selon la perte d’informations. Les méthodes réversibles, utilisent uniquement le principe de la réduction de la redondance et n’engendrent pas de perte. Les méthodes irréversibles, définissent une représentation approximative de l’information.
Toutes ces méthodes présentent des avantages et des inconvénients ; le but et par contre de trouver un compromis entre les différents critères à vérifier après un algorithme de compression (temps de calcul ; taille de l’image ; dégradation totale…etc.), donc de concevoir un système de compression qui permet d’avoir une meilleure qualité de la compression. Pour cela on a utilisé des méthodes d’optimisation connues sous l’appellation de Métaheuristiques. Les métaheuristiques sont une famille d’algorithmes stochastiques. Apparues au début des années quatre vingts, elles sont destinées à résoudre des problèmes d’optimisation difficile. Utilisées dans de nombreux domaines, ces méthodes présentent l’avantage d’être généralement efficaces, sans pour autant que l’utilisateur ait à modifier la structure de base de l’algorithme qu’il utilise. Ces algorithmes stochastiques d’optimisation peuvent être appliqués à tout problème, du moment qu’il est formulé sous la forme de l’optimisation de critère(s). Ces algorithmes sont inspirés par des analogies avec la physique (recuit simulé, recuit micro canonique), avec la biologie (algorithmes évolutionnaires) ou avec l’éthologie (colonies de fourmis, essaims particulaires). Ils se prêtent aussi à toutes sortes d’extensions, notamment en optimisation multiobjective. D’autre part l’utilisation des métaheuristiques d’optimisation dans le domaine de la compression d’image est assez nouvelle. Dans ce contexte d’étude nous nous intéressons à la conception de métaheuristique d’optimisation pour la compression d’image. Le but est donc d’essayer d’appliquer plusieurs métaheuristiques d’optimisation sur un algorithme de compression d’image, afin d’améliorer les critères de ce dernier. Dans cette thèse de doctorat, nous allons, et pour la première fois, procéder à une étude plus détaillée au sujet de l’Algorithme de la Meute de loups pour la compression fractale d’image. L’image entière est considérée comme un espace de recherche où cet espace est divisé en blocs, les loups chercheurs explorent l’espace pour trouver d’autres plus petit blocs qui se ressemblent. Le processus sera arrêté après un nombre fixe d’itérations ou si aucune amélioration dans la solution du loup chef est trouvée. A la fin un mappage est dressé avec les meilleurs solutions trouvées afin de reconstruire l’image en question. Notre méthode est originale dans le sens où elle utilise, et pour la première fois l’algorithme de la meute des loups dans la compression fractale. Les résultats ont montré l’amélioration du taux et du temps de compression tout en offrant une qualité acceptable de l’image reconstruite.
Compression de données : état de l’art
« La théorie, c’est quand on sait tout et que rien ne fonctionne. La pratique, c’est quand tout fonctionne et que personne ne sait pourquoi ». Albert Einstein .
Avec l’utilisation généralisée de l’Internet, avec les coûts décroissants des numériseurs et des disques, l’archivage, la transmission et la manipulation des documents se fait de plus en plus sur ordinateur et de moins en moins sur papier. L’écran de nos ordinateurs est en train de devenir le moyen privilégié de consultation de documents parce qu’il permet un accès immédiat à l’information. La taille des images augmente proportionnellement à leur qualité et leur stockage et transmission constituent donc les enjeux principaux dans le monde numérique. La compression s’impose comme une étape incontournable pour optimiser l’utilisation de ces grands volumes d’informations dans les réseaux informatiques. L’objectif principal de la compression d’image est de réduire la quantité d’information nécessaire à une représentation visuelle fidèle à l’image originale. En générale, on différencie les méthodes de compression selon la perte d’informations. Les méthodes réversibles, utilisent uniquement le principe de la réduction de la redondance et n’engendrent pas de perte. Les méthodes irréversibles, définissent une représentation approximative de l’information.
Compression physique et compression logique
On considère généralement la compression comme un algorithme capable de comprimer énormément de données dans un minimum de place (compression physique), mais on peut également adopter une autre approche et considérer qu’en premier lieu un algorithme de compression a pour but de recoder les données dans une représentation différente plus compacte contenant la même information (compression logique). La distinction entre compression physique et logique est faite sur la base de comment les données sont compressées ou plus précisément comment est-ce que les données sont réarrangées dans une forme plus compacte. La compression physique est exécutée exclusivement sur les informations contenues dans les données. Cette méthode produit typiquement des résultatsincompréhensibles qui apparemment n’ont aucun sens. Le résultat d’un bloc de données compressées est plus petit que l’original car l’algorithme de compression physique a retiré la redondance qui existait entre les données elles-mêmes. Toutes les méthodes de compression dont nous allons traiter sont des méthodes physiques. La compression logique est accomplie à travers le processus de substitution logique qui consiste à remplacer un symbole alphabétique, numérique ou binaire en un autre. Changer « United State of America » en « USA » est un bon exemple de substitution logique car « USA » est dérivé directement de l’information contenue dans la chaîne « United State of America » et garde la même signification. La substitution logique ne fonctionne qu’au niveau du caractère ou plus haut et est basée exclusivement sur l’information contenue à l’intérieur même des données. Un autre exemple, moins heureux, de substitution logique est de remplacer 1999 par 99…
Compression avec et sans pertes
C’est peut-être le critère de comparaison le plus important pour les algorithmes de compression. Une bonne partie des schémas de compression utilisés sont appelés sans pertes (réversibles), cela signifie que lorsque des données sont compressées et ensuite décompressées, l’information originale contenue dans les données a été préservée. Aucune donnée n’a été perdue ou oubliée. Les données n’ont pas été modifiées. La méthode de compression avec pertes (irréversible) quant à elle « jette », de façon sélective, quelques données d’une image dans le but d’effectuer la compression avec un taux de compression meilleur que la plupart des méthodes de compression sans pertes. Les algorithmes avec pertes s’appliquent généralement aux données ayant de forts taux de redondance, comme les images, ou les sons. Certaines méthodes tirent partis d’algorithmes heuristiques élaborés qui s’ajustent eux-mêmes pour trouver le rapport de compression maximum possibleen changeant aussi peu que possible les détails visibles d’une image. Autrement dit, d’autres algorithmes moins élégants suppriment carrément la portion la moins significative de chaque pixel.
Principales méthodes de compression
Ces méthodes se divisent en deux familles; à savoir les méthodes dites sans pertes et celles avec pertes de données.
Méthodes sans pertes
La compression sans perte ou codage entropique ou codage réversible permet de retrouver la valeur exacte du signal comprimé lorsqu’il n’y aucune perte de données sur l’information d’origine. En fait, la même information est réécrite d’une manière plus concise.
Codage d’Huffman
Huffman [Huf 52] a suggéré une méthode statistique qui permet d’attribuer un mot-code binaire aux différents symboles (pixel) à compresser. La probabilité d’occurrence du symbole dans l’image est prise en compte en attribuant aux plus fréquents des codes courts, et aux plus rares des codes longs, VLC – Variable Length Coding. La suite finale de pixels codés à longueurs variables sera plus petite que la taille originale. Le codeur Huffman crée un arbre ordonné à partir de tous les symboles et de leur fréquence d’apparition. Les branches sont construites récursivement en partant des symboles les plus fréquents. Le code de chaque symbole correspond à la suite des codes le long du chemin allant de ce caractère à la racine. Plus le symbole est profond dans l’arbre plus la quantité de bits pour le représenter est importante .
L’algorithme LZW
Lempel et Ziv [Ziv 77] ont présenté un schéma (LZ77) qui est à la base de tous les algorithmes à dictionnaire dynamique utilisés actuellement. Welch a amélioré leur algorithme et a déposé un brevet en créant l’algorithme LZW qui génère un dictionnaire dynamique qui contient des motifs du fichier. L’utilisation d’un dictionnaire dynamique a réglé le problème de le transmettre a priori pour les procédés de compression et décompression. Il est basé sur la multiplicité des occurrences de séquences de symboles. Son principe consiste à substituer des motifs par un code d’affectation en construisant au fur et à mesure un dictionnaire. Celui-ci est initialisé avec les valeurs de la table ASCII. Chaque octet du fichier est comparé au dictionnaire. S’il n’existe pas, il est ajouté au dictionnaire. L’algorithme LZW fait partie du format d’image, aussi breveté, GIF (Graphics Interchange Format).
|
Table des matières
Introduction générale
Chapitre 1 : Compression d’image : état de l’art
1.1 Introduction
1.2 Principales méthodes de compression
1.2.1 Méthodes sans pertes
1.2.1.1 Codage d’Huffman
1.2.1.2 Codage arithmétique
1.2.1.3 L’algorithme LZW
1.2.1.4 Codage par plage
1.2.1.5 Codage par prédiction linéaire
1.2.2 Méthodes avec pertes
1.2.2.1 Quantification
1.2.2.2 Scalaire
1.2.2.3 Vectorielle
1.2.2.4 Codage prédictif avec pertes
1.2.2.5 Codage par transformation
1.2.2.6 Domaine spatial
1.2.2.7 Quadtree
1.2.2.8 Décomposition en plans binaire
1.2.2.9 Fractales
1.2.2.10 Domaine fréquentiel
1.2.2.11 Les standards
1.2.2.11.1 JPEG
1.2.2.11.2 JPEG 2000
1.2.2.12 Compression par Ondelettes
1.2.3 Conclusion
Chapitre 2 : Métaheuristiques d’optimisation : état de l’art
2.1 Introduction
2.2 Optimisation
2.3 Algorithmes d’optimisation
2.3.1 Heuristiques
2.3.2 Métaheuristiques
2.3.2.1 Métaheuristiques pour l’optimisation mono-objectif
2.3.2.1.1 Algorithme de recuit simulé
2.3.2.1.2 Recherche Tabou
2.3.2.1.3 Algorithmes évolutionnaires
2.3.2.1.4 Algorithme de colonies de fourmis
2.3.2.1.5 Optimisation par Essaim Particulaire
2.3.2.2 Optimisation multiobjectif
2.3.2.2.1 Définitions
2.3.2.2.2 Approche agrégative
2.3.2.2.3 Approche non-Pareto
2.3.2.2.4 Approche Pareto
2.3.2.3 Métaheuristiques pour l’optimisation multiobjectif
2.3.2.3.1 Algorithme de recuit simulé
2.3.2.3.2 Algorithmes évolutionnaires
2.3.2.3.3 Algorithme de colonies de fourmis
2.3.2.3.4 Optimisation par Essaim Particulaire
2.4 Conclusion
Chapitre 3 : Métaheuristiques d’optimisation pour la compression d’image : travaux similaires
3.1 Introduction
3.2 Métaheuristiques d’optimisation pour la compression fractale d’images
3.2.1 Compression fractale d’images et Algorithmes génétiques
3.2.1.1 Travaux de Lucia Vences et al
3.2.1.2 Travaux de Suman K. Mitra et al
3.2.1.3 Travaux de Y.Chakrapani et al
3.2.1.4 Travaux de Wang Xing-yuan et al
3.2.1.5 Travaux de Vishvas V. Kalunge et al
3.2.1.6 Travaux de Mahesh G. Huddar
3.2.1.7 Travaux de Ming-Sheng Wu
3.2.1.8 Travaux de AnamikaPandey et al
3.2.2 Compression fractale d’images et les algorithmes bio-inspirés
3.2.2.1 Travaux de Cristian Martinez
3.2.2.2 Travaux de Chun-ChiehTseng et al
3.2.2.3 Travaux de Dervis Karaboga
3.2.2.4 Travaux de Y.Chakrapani et al
3.2.2.5 Travaux de Wang Xing-Yuan et al
3.3 Comparaison des différentes méthodes d’optimisation
3.4 Conclusion
Chapitre 4 : Approche proposée : Wolf Pack Algorithme pour la compression fractale d’image
4.1 Introduction
4.2 Techniques bio-inspirées
4.3 Compression Fractale d’image
4.3.1 Vue générale
4.3.2 Différentes approches pour la compression fractale
4.4 L’algorithme du pacte des loups « Wolf Pack Algorithme »
4.5 Compression Fractale avec le Wolf Pack Algorithm
4.6 Conclusion
Chapitre 5 : Résultats et discussion
5.1 Introduction
5.2 Processus de compression
5.3 Processus de décompression
5.4 Expérimentation et résultats préliminaires
5.5 Résultats et analyse
5.5.1 Résolution
5.4 Conclusion
Conclusion générale
