Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

REPUBLIQUE ALGERIENNE DEMOCRATIQUE ET POPULAIRE MINISTERE D’ENSEIGNEMENT SUPERI

REPUBLIQUE ALGERIENNE DEMOCRATIQUE ET POPULAIRE MINISTERE D’ENSEIGNEMENT SUPERIEUR ET DE LA RECHERCHE SCIENTIFIQUE MEMOIRE présenté à université de BATNA la faculté des sciences de l’ingénieur département d'informatique Pour l’obtention du diplôme Magister en informatique OPTION INFORMATIQUE INDUSTRIELLE Par ZEROUAL Djazia Thème IMPLEMENTATION D’UN ENVIRONNEMENT PARALLELE POUR LA COMPRESSION D’IMAGES A L’AIDE DES FRACTALES Soutenue le : ..… /..… /2006 Devant le jury composé de A. BILLAMI Maître de conférences, Université de Batna Président M. BENMOHAMMED Professeur, Université de C o n s t a n t i n e Rapporteur A. CHAOUI Maître de conférences, Université de C o n s t a n t i n e Examinateur A. ZIDANI Maître de conférences, Université de Batna Examinateur R Re em me er rc ci ie em me en nt ts s Je tiens, avant tout, à exprimer ma profonde gratitude à monsieur Mohamed Benmohammed, professeur à l’université de Constantine, qui a assumé la direction de ce travail. Qu’il veuille bien trouver ici l’expression de ma reconnaissance pour son dévouement, sa patience, sa disponibilité, ses conseils et son aide constante qu’il m’a apporté tout au long de ce travail. Je remercie les membres de jury qui ont accepté de juger ce travail et d’y apporter leur caution : Monsieur Dr. Azzedine Bilami, maître de conférence à l’université de BATNA, qui me fait le grand honneur d’accepter la présidence du jury. Monsieur Dr. Allaoua Chaoui, maître de conférence à l’université de Constantine, pour l’honneur qu’il me fait en acceptant de participer à ce jury. Monsieur, Dr. Abdelmadjid Zidani, maître de conférence à l’université de BATNA, pour l’honneur qu’il me fait en acceptant également de participer à ce jury. J’adresse mes vifs remerciements à tous les enseignants qui, par leur enseignement, leur encouragement et leur aide, ont contribués à ma formation. à tous ceux qui, par leur encouragement ou leur amitié, ont contribué à l’aboutissement de ce travail. Table des matières TABLE DES MATIERES LISTE DES FIGURES LISTE D'ACRONYMES INTRODUCTION GENERALE……………... ......................................................................1 CHAPITRE 1 NOTIONS SUR LE TRAITEMENT D’IMAGES 1 Introduction .................................................................................................................4 2 Définition de l’image ...................................................................................................4 3 Image numérique .........................................................................................................5 4 Les attributs de limage .................................................................................................5 5 Les différents types d’images ......................................................................................9 6 Les formats d’image .................................................................................................. 10 7 Domaines d’application.............................................................................................. 12 8 Qualité de l’image numérique..................................................................................... 12 9 Pourquoi comprimer ?................................................................................................ 13 10 Nature des images à compresser ............................................................................... 14 11 Mesures de performance de la compression d’image ................................................. 15 12 Conclusion ................................................................................................................ 17 CHAPITRE 2 METHODES DE COMPRESSION 1 Introduction ............................................................................................................... 18 2 L’intérêt de compression d’image............................................................................... 18 3 Les différents types de compression .......................................................................... 18 4 Modèle général pour l'analyse des méthodes de compression .................................... 20 5 Classification des méthodes de compression .............................................................. 22 5.1 Méthode avec ou sans perte d’information ................................................................ 22 5.2 Méthodes par pixels, bloc de pixels, ou image entière (scène) .................................... 22 Table des matières 5.3 Méthodes Intra- et Inter-images ................................................................................ 22 5.4 Méthodes spatiales et méthodes par transformation .................................................... 23 5.5 Méthodes Adaptatives, Non Adaptatives ................................................................... 23 6 Présentation des méthodes avec et sans pertes ............................................................ 23 6.1 Les méthodes réversibles ou sans pertes ................................................................... 24 6.2 Les méthodes de compression avec pertes ou irréversible .......................................... 29 7 Étude comparative des différentes méthodes de compression principales.................... 44 8 Conclusion ................................................................................................................ 45 CHAPITRE 3 COMPRESSION DES IMAGES FIXES BASEE SUR UNE TRANSFORMATION FRACTALE 1 Introduction .............................................................................................................. 46 2 Théorie des Systèmes de Fonctions Itérées (IFS) ........................................................ 46 2.1 Les outils mathématiques ...........................................................................................46 2.2 Quelques définitions dans l'espace (rappels sur les espaces métrique)......................... 46 2.3 Transformation des espaces métrique ........................................................................ 48 2.4 Théorie des ifs et compression par fractales................................................................ 49 3 La compression des images par fractales.................................................................... 53 3.1 Qu’est–ce qu’une Fractale ? ....................................................................................... 53 3.2 Pourquoi "la Compression Fractale d'Images" ?.......................................................... 54 3.3 La notion de L’auto-similarite .................................................................................... 55 3.4 Auto-similarite dans les images .................................................................................. 56 3.5 Principe de la compression IFS et PIFS ..................................................................... 56 3.6 Le codage fractale par bloc (transformation fractale) ................................................ 57 3.7 Schéma général d’un codeur - décodeur fractal ..........................................................60 4 Partitionnement de l’image ........................................................................................ 62 4.1 Rôle du partitionnement pour la compression par fractales : ....................................... 62 4.2 Partitionnement rigide (Quadtree) .............................................................................. 63 4.3 Partitionnement Semi_Rigide (Horizontal _ Vertical)................................................. 65 4.4 Partitionnement souple (triangulaire).......................................................................... 66 4.5 Autres types de partitionnements................................................................................ 68 5 Optimisation fractale et transformations hybrides ....................................................... 68 5.1 Codage par TCD et fractales....................................................................................... 68 Table des matières 5.2 QV et compression fractales ....................................................................................... 69 5.3 Ondelettes et compression fractales ............................................................................ 69 5.4 L’avantages et inconvénients du compression fractale ................................................ 70 5.5 Optimisations ............................................................................................................ 70 6 Conclusion ................................................................................................................. 71 CHAPITRE 4 ARCHITECTURES PARALLELES ET TRAITEMENT D’IMAGE 1 Introduction................................................................................................................72 2 Historique................................................................................................................... 72 3 Définition du parallélisme ......................................................................................... 72 4 Contraintes de parallélisme dan le traitement d’image ............................................. 72 5 Les différentes Architectures des machines parallèles................................................. 73 6 Les architectures MIMD .............................................................................................76 6.1 Machine parallèle MIMD à mémoire centralisée......................................................... 76 6.2 Machine parallèle MIMD à mémoire distribuée .......................................................... 77 7 Les formes de parallélisme .........................................................................................79 8 La topologie de communication................................................................................. 80 9 Modes de communication........................................................................................... 82 10 Technologies dédies ................................................................................................. 83 11 Langages parallèles .................................................................................................... 84 12 Conclusion ................................................................................................................. 87 CHAPITRE 5 PARALLELISATION D’UN ALGORITHME DE COMPRESSION FRACTALEET IMPLEMENTATION P A RT IE A Parallélisation d’un algorithme de compression fractale 1 Introduction................................................................................................................88 2 L'approche séquentielle .............................................................................................. 88 3 L'approche parallèle de la compression fractale .......................................................... 91 3.1 Allocation statique de la charge .................................................................................91 Table des matières 3.2 Allocation dynamique de la charge............................................................................. 92 3.3 Allocation dynamique de la charge avec un processus de circulation pipeline.............93 4 Le parallélisme de compression fractale et l’architecture matériel dédiée :................. 94 4.1 Introduction................................................................................................................94 4.2 Architecture parallèle pour Fixed-size partitionnement (FPFIC)................................. 95 4.3 Architecture parallèle pour le partitionnement Quadtree (QPFIC) ............................ 98 P A R T IE B Implémentation parallèle de la compression d’image fractale et résultats 5 Implémentation parallèle du codage fractale .......................................................... 101 6 Architecture matérielle ............................................................................................. 101 7 Les réseaux de stations de travail.............................................................................. 102 8 Principes de base...................................................................................................... 102 9 Configuration du réseau............................................................................................ 102 10 Outils logiciels ......................................................................................................... 103 11 Modèle d’Exécution ................................................................................................. 103 12 Déroulement d’une communication .......................................................................... 104 13 Fonctionnement de l’application............................................................................... 105 14 Expérimentation et discussion .................................................................................. 106 15 Conclusion ............................................................................................................... 112 CONCLUSION GENERALE ........................................................................................... 113 ANNEXE A ANNEXE B BIBLIOGRAPHIE Liste des Figures LISTE DES FIGURES Figure 1.1 : Un point de l'image de coordonnées (x, y) ...........................................................4 Figure 1.2 : Représentation de la lettre A sous la forme d’un groupe de pixels........................5 Figure 1.3 : Représentation de dimension d’une image...........................................................6 Figure 1.4 : Image avec et sans bruit ......................................................................................6 Figure 1.5 : Image et histogramme Associés...........................................................................7 Figure 1.6 : Image avec texture ..............................................................................................8 Figure 1.7 : Image en mode monochrome...............................................................................9 Figure 1.8 : Image en mode niveau de gris .............................................................................9 Figure 1.9 : Image en mode couleur. .................................................................................... 10 Figure 1.10 : La détérioration de l’image en fonction de l’entropie........................................16 Figure 2.1 : Schéma général de la compression ................................................................... 20 Figure 2.2 : Le modèle à quatre niveaux............................................................................... 21 Figure 2.3 : Un exemple de codage par plage RLE ............................................................... 25 Figure 2.4 : Codage de SHANNON-FANO ........................................................................... 26 Figure 2.5 : Algorithme de Huffman..................................................................................... 27 Figure 2.6 : Principe de la quantification .............................................................................. 30 Figure 2.7 : Quantification scalaire uniforme en Escalier...................................................... 31 Figure 2.8 : Le principe du Quantificateur Vectoriel............................................................ 32 Figure 2.9 : Schéma de principe de la compression/décompression par transformation......... 34 Figure 2.10 : Décomposition d’une image en sous-bandes..................................................... 36 Figure 2.11 : Transformation en colonnes et en lignes............................................................ 37 Figure 2.12 : Transformation ondolette «pyramidale» (1-D (a), 2-D (b), 3-D(c)).................... 38 Figure 2.13 : Le principe de Compression / Décompression par ondelettes............................ 38 Figure 2.14 : Schéma de principe de La compression JPEG .................................................. 40 Figure 2.15 : Le parcours d’un bloc DCT en zigzag................................................................ 41 Figure 2.16 : Schéma typique d'un codeur JPEG 2000 ........................................................... 43 Figure 2.17 : Comparaison des méthodes en fonction (d’erreur RMSE, et taux de compression)........................................................... 44 Figure 3.1 : Illustre le point fixe d’une transformation affiné contractive.............................. 50 Figure 3.2 : L’attracteur de l'IFS .......................................................................................... 50 Figure 3.3 : La feuille de Barnsley........................................................................................ 54 Figure 3.4 : Triangle de Sierpinski........................................................................................ 55 Figure 3.5 : Parties auto similaires dans l’image de Lena..................................................... 56 Liste des Figures Figure 3.6 : Principe de la transformation fractale ................................................................ 57 Figure 3.7 : Transformation massique …….......................................................................... 59 Figure 3.8 : Schéma Général d’un Codeur et Décodeur Fractale. ........................................60 Figure 3.9 : Principe de la division récursive dune image binaire.......................................... 64 Figure 3.10 : Représentation arborescente du quadtree .......................................................... 64 Figure 3.11 : Illustration d’un partitionnement quadtree sur l’image Lena .............................. 65 Figure 3.12 : Partitionnement H_V calculé sur l’image Lena .................................................. 65 Figure 3.13 : Partition H_V méthodes de division (1) ............................................................. 66 Figure 3.14 : Partition H_V méthodes de division (2) ............................................................. 66 Figure 3.15 : Triangles de Delaunay, et Polygones de Voronoi............................................... 67 Figure 3.16 : Illustration de construction de l’initialisation de la triangulation de Delaunay à gauche est suivie des division et fusion à droite......................... 67 Figure 3.17 : Les types d’arbres ............................................................................................. 68 Figure 4.1 : Classification des modèles de parallélisme Proposée par Flynn ......................... uploads/Litterature/ sce-zeroual-djazia.pdf