AA2024


Jean-Jacques BOURDIN

E-mail :
jj NOSPAM @ up8.edu
(enlever le NO Spam)


Algorithmique Avancée 2024


Compression d'Images



  1. Présentation
  2. Constantes et complexité
    1. Calculs et mesures de complexité
    2. Constantes
    3. Exemple
  3. De la Droite Discrète
    1. Algorithme trivial
    2. DDA et accélération
    3. Mots de trace
    4. Algorithme rapide
  4. Graphes
    1. Codages
    2. Algorithmes
  5. Compression
    1. Rappels, champs de bits
    2. Bases
    3. Compression sans perte
    4. Compression avec perte
    5. Compression d'images
  6. Modélisation, Illumination, Rendus
    1. 2D/3D
    2. Modélisation
    3. Illumination
    4. Lumière
    5. Rendus, quelques effets
    6. Rendus Expressifs
    7. IA et jeux
      1. Principes
      2. Algorithmes
    8. Projets


    Compression d'Images


  7. Compression d’images

    1. Rappels

      Rappels : champs de bits

      Nous nommons champ de bits une structure où tous les champs sont des entiers non signées et sont accompagnés du nombre de bits qu’ils utilisent.

      Nous montrons également l’effet lié aux décalages. Voici un exemple avec des effets de dépassement :
      #include <stdio.h>
      
      struct champs {
        unsigned int a: 1;
        unsigned int b: 1;
        unsigned int c: 1;
      } ;
      typedef struct champs champs;
      typedef  unsigned int uint;
      struct champ2 {
        uint x: 1;
      } ;
      typedef struct champ2 champ2;
      
      void fct () {
        champs c;
        champ2 f;
      
        c.a = 1;
        c.b = 2;
        c.c = 3;
        f.x = 1;
        printf("%2u %2u %2u %2d\n\n\n", c.a, c.b, c.c, f.x);
      }
      int oups (int a, int b) {
        int c;
        c = 0;
        while (a) {
              if (a & 0x01)
                c += b;
              b <<= 1;
              a >>= 1;
        }
        return c;
      }
      int main () {
        int i, j;
        fct ();
        printf("      1    2    3    4    5    6    7    8    9\n");
        for (i = 2; i < 10; i++) {
              printf(" %2d ", i);
              for (j = 1; j < 10; j++)
                printf("%3d  ", oups(i,j));
              printf("\n");
        }
      }
      
      white.home: gcc champs.c
      champs.c:21:7: warning: implicit truncation from ’int’ to bit-field changes value from 2 to 0 [-Wbitfield-constant-conversion]
        c.b = 2;
            ^ ~
      champs.c:22:7: warning: implicit truncation from ’int’ to bit-field changes value from 3 to 1 [-Wbitfield-constant-conversion]
        c.c = 3;
            ^ ~
      2 warnings generated.
      white.home: a.out
      1  0  1  1
      
      			
            1    2    3    4    5    6    7    8    9
        2   2    4    6    8   10   12   14   16   18  
        3   3    6    9   12   15   18   21   24   27  
        4   4    8   12   16   20   24   28   32   36  
        5   5   10   15   20   25   30   35   40   45  
        6   6   12   18   24   30   36   42   48   54  
        7   7   14   21   28   35   42   49   56   63  
        8   8   16   24   32   40   48   56   64   72  
        9   9   18   27   36   45   54   63   72   81  
      white.home: 
      

    2. Perception

      Lois de Grassmann et CIE 1930

      Vision et définition visible

    3. Bases
      Pour compresser des images, il faut, au départ, disposer d’une image, au moins. Nous vous donnons ci-dessous des fonctions permettant, sous OpenGL de lire, afficher et modifier une image de format ppm.
      À un moment, vous disposez donc d’une structure Image avec la taille en x et en y et le paquet de données, un octet pour le rouge, un octet pour le vert et un octet pour le bleu, pour chaque pixel de l’image. C’est à partir de cette structure qu’il convient de travailler.

      1. Matériel nécessaire

        Sous OpenGL, on doit utiliser des pointeurs de fonctions. Par exemple la fonction définie par :
        void Mouse(int button, int state, int x, int y){
        
          switch(button){
          case GLUT_LEFT_BUTTON:
            break;
          case GLUT_MIDDLE_BUTTON:
            break;
          case GLUT_RIGHT_BUTTON:
            break;    
          }
          glutPostRedisplay();
        }
        

        sera mémorisée dans le main comme fonction de gestion de souris. D’un côté c’est logique, de l’autre cette affectation n’est possible que parce que la fonction est correctement définie dans glut.
        int main(int argc, char **argv) 
        {  
        
          if (argc<2) {
            fprintf(stderr, "Usage : palette nom_de_fichier\n");
            exit(0);
          }
        
          
          glutInit(&argc, argv); 
          glutInitDisplayMode(GLUT_RGB | GLUT_SINGLE);
          glutInitWindowSize(640,480);  
          glutInitWindowPosition(0, 0);  
          glutCreateWindow("VPUP8");  
        
          Init(argv[1]);
        
          glutCreateMenu(menuFunc);
          glutAddMenuEntry("Informations", 0);
          glutAddMenuEntry("Ouvrir", 3);
          glutAddMenuEntry("Sauver", 4);
          glutAddMenuEntry("Noir et Blanc", 6);
          glutAddMenuEntry("Quit", 5);
          glutAttachMenu(GLUT_LEFT_BUTTON);
        
          glutDisplayFunc(Display);  
          glutReshapeFunc(Reshape);
          glutKeyboardFunc(Keyboard);
          
          glutMouseFunc(Mouse);
        
        
          glutMainLoop();  
        
          return 1;
        }
        
        

        Voici des fichiers utiles pour travailler :

        Récupérer ces fichiers et les installer, objectif : être en mesure de lire un fichier image et l‘afficher.

        Faire une fonction qui modifie l‘image en remplaçant la couleur de chaque pixel par le gris moyen correspondant.

        Vous trouvez plus détails sur la page du TP

      2. Méthodes de compression sans perte

        Nous ne détaillerons pas ici les méthodes les plus classiques vues en cours.
        • Shannon-Fano
        • Huffman
        • LZW
        • RLE (Run length encoding)
          Il s’agit de coder non seulement la valeur mais aussi, sur un octet, le nombre de fois qu’elle apparaît consécutivement.
          Exemple
          a a a b c a a b b r t a c
          devient :
          3 a 1 b 1 c 2 a 2 b 1 r 1 t 1 a 1 c
          Cette méthode ne fonctionne donc, a priori, que lorsque les répétitions sont nombreuses (il faut que chaque lettre soit recopiée au moins deux fois pour que conserver la lettre et son nombre d’occrurences consécutives soit moins lourd que stocker chaque lettre).
          On voit sur l’exemple ci-dessus que nous avons écrit plus de symbôles dans la version RLE que dans la version initiale.
          Cette méthode a été grandement améliorée chez SGI, la valeur donnée correspond, si elle est positive, au nombre d’occurences de la lettre qui suit (5 a pour cinq ’a) et, si elle est négative pour le nombre de lettres différentes qui suivent (-3 a b c signifie a b c). On peut, dans le cas de lettres presque toutes différentes sur la séquence, préférer (-15 a b c d e e f g h a b c d e f) à (-4 a b c d 2 e -9 f g h a b c d e f) (un peu plus long)

          En Informatique Graphique il faut commencer par séparer les composantes bleue rouge et verte (il y a des chances que les rouges de deux pixels voisins soient proches, par exemple).

      3. Color LUT

        Au lieu de mémoriser les trois composantes de chaque pixel, on place dans un grand vecteur toutes les couleurs utilisées. Puis pour chaque pixel on mémorise le numéro de sa couleur dans le vecteur.
        Exemple, la couleur 0 est (0,0,0) le noir, la couleur 1, (255, 255, 255). Pour chaque pixel noir, la valeur mémorisée sera 0, pour chaque pixel blanc ce sera 1.
        La compression la plus simple est de choisir arbitrairement quelques couleurs et, pour chaque pixel, de trouver celle qui en est le plus proche.

        Avec un tel système, si on réduit à, par exemple, 64 couleurs, il suffit de 6 bits pour coder un nombre entre 0 et 63. Donc pour chaque pixel on n'a plus 24 mais 6 bits à coder, donc on divise la taille de l'image par quatre, à peu près (il faut mémoriser aussi la table).

        On commencera par parcourir l‘image et créer la CLUT de toutes les couleurs présentes.

      4. Comment réduire la CLUT ?

        Nous proposons quelques pistes pour réduire le nombre de couleurs utilisées :
        • choisir des couleurs arbitraires, toute couleur de pixel sera remplacée par la plus proche dans la CLUT arbitraire.
        • choisir des couleurs arbitraires, toute couleur cp d‘un pixel sera remplacée par ca, la plus proche couleur dans la CLUT arbitraire. La couleur ca sera mise à jour, selon la formule suivante, où nbp est le nombre de pixels de l‘image et nbclut le nombre de couleurs de la CLUT :

          ca = ca + (cp - ca) * nbclut / nbp
          	    

        • parcourir l‘espace des couleurs chercher les nbclut couleurs les plus intéressantes et s‘en servir comme une clut arbitraire (voir les deux options ci-dessus).
        • considérer les couleurs présentes comme un cluster et utiliser des méthodes de clustering.
    4. SPLINES

      Quelques références, comme :

      Ici, un cours de P13.

      La présentation que je vais expliquer le 20/11/24.

      Un programme d’affichage de surface NURBS, qui tourne sur ma machine
      là,

      la version originale de programme de surface NURBS.
      On remarque en particulier ces trois lignes :
         GLfloat knots[8] = {0.0, 0.0, 0.0, 0.0, 1.0, 1.0, 1.0, 1.0};
         gluBeginSurface(theNurb);
         gluNurbsSurface(theNurb, 
                         8, knots, 8, knots,
                         4 * 3, 3, &ctlpoints[0][0][0], 
                         4, 4, GL_MAP2_VERTEX_3);
         gluEndSurface(theNurb);
      
      Ce sont elles qui permettent de définir la surface à afficher une fois que les points de contrôle ont été définis par la fonction init-surface.

    5. Illumination et calcul matriciel

      Pour vous parler d’Illumination, nous allons partir d’une série de diapositives faites par Venceslas Biri et que vous pouvez trouver sur cette page.

      Puis nous regarderons quelques diapositives sur la résolution d’équations linéaires, tirées de ce cours de HEC Montréal.

      Mieux, venus de l’INSA de Rouen ces deux cours :

      qui donne des bases d‘analyse numérique

      et un cours sur les méthodes comme choleski



    Dernière mise à jour : 21/10/2024 (13h)