TP1

 

Réduction des couleurs d’une image

Optimisation par la programmation dynamique

 

 

 

 

 

But :

 

            A partir d’une image en 256 niveaux (gris,RVB) nous cherchons à diminuer le nombre de couleurs vers une quantité bien inférieure (8,16..). Le but est d’effectuer cette simplification au mieux c’est à dire en préservant la qualité de l’image de départ.

 

 

Notation :

           

            Nous notons h(i), la fonction qui à tout niveau i associe le nombre de pixels ayant ce niveau. L’histogramme d’une image est le diagramme en bâtons qui représente cette fonction. Notons g(i) la fonction qui à un niveau i dans [0,255] fait correspondre le nouveau niveau dans l’image simplifiée. Nous choisissons comme expression arithmétique de l’erreur la fonction :

                       

 

La méthode :

 

            La quantité de niveaux : n dans l’image simplifiée est choisie par l’utilisateur. Nous allons procéder de la manière suivante. Notre méthode de simplification consiste à positionner n marqueurs sur les niveaux 0 à 255. La zone d’influence d’un marqueur correspond à tous les niveaux qui lui sont les plus proches. Ainsi la zone d’influence d’un marqueur mi est définie de la manière suivante : [ (mi-1+mi) / 2 , (mi+mi+1) / 2 ]. Sur cette zone, la valeur de la fonction g est donnée par celle du marqueur.  Nous obtenons donc :

 

 

1-   Réalisation du projet

 

            Téléchargez le projet : ICI

 

2-   L’histogramme

 

            Construisez une fonction calculant la fonction h(i). Affichez l’histogramme correspondant en utilisant les fonctions MoveTo et LineTo.

 

3- Programmation dynamique

 

            Etudiez et concevez une méthode positionnant les n marqueurs afin de minimiser l’erreur. Cette résolution de l’optimalité doit être effectuée par une méthode de programmation dynamique.

 

4- Développement

 

            Programmez votre méthode en tenant compte des initialisations. Modifiez là afin de pouvoir retrouver l’ensemble des marqueurs sélectionnés pour atteindre l’optimum. Vous pouvez maintenant appliquer votre méthode sur une image en niveaux de gris :

 

 

    

Image originale en 256 niveaux                           Simplification en 16 niveaux (Round)           Simplification en 16 niveaux (Prog. Dyn.)

 

La fonction basique de simplification choisie est   int( int(niveau/(256.0/n)) * (256.0/n) )

 

 

5-  Qualité de la méthode

       

En quoi cette méthode peut être considérée comme meilleure ? Pourquoi pour la plupart des images, la qualité de l’image produite par la fonction basique et la qualité de l’image issue de notre simplification seront assez proches ? Quel défaut flagrant pénalise la méthode basique ? Pourquoi n’est-il pas présent dans notre méthode ? Cette méthode teste – t – elle toutes les fonctions g(i) possibles ?

 

 

5- Complexité

 

            Démontrez que l’algorithme obtenu est en O(n3). Expliquez comment réduire cette complexité à O(n²) par un pré calcul.

 

6 – Vérification

 

            Testez sur une image en niveaux de gris en prenant trois marqueurs. Le résultat sera vérifié en programmant une fonction de type brute force qui testera toutes les positions possibles des trois marqueurs.

 

 

7- La couleur

 

            Nous décomposons une image couleur en trois images en niveaux de gris (rouge, vert et bleu). Traitez indépendamment chaque couche et reconstruisez le résultat final :

 

                                    

                           Image originale 24 bits RVB                         Simplification à 6 bits (Round)                     Simplification à 6 bits (Prog. Dyn.)

 

8- Rédaction

 

Un bon TP rendu ® points bonus pour le partiel