Compression d'une image par Huffman [Résolu/Fermé]

Signaler
Messages postés
12
Date d'inscription
vendredi 9 mai 2008
Statut
Membre
Dernière intervention
29 juin 2010
-
Messages postés
12
Date d'inscription
vendredi 9 mai 2008
Statut
Membre
Dernière intervention
29 juin 2010
-
Bonjour à tous !

Je me suis récemment intéressé à la compression des fichiers par la méthode Huffman.
J'ai lu beaucoup de pages web l'expliquant et j'ai très bien compris comment il fonctionne.

En revanche, beaucoup s'amusent à l'utiliser pour compresser un fichier texte (par exemple créer l'arbre avec "Comment Ca Marche"), ce qui est facile. Mais cet algorithme est aussi utilisé, par exemple, dans le format TIFF en tant qu'algorithme de compression sans perte.
Mais comment utiliser cet algorithme pour une image, comme il a été utilisé pour TIFF ?

Doit-on passer par le code binaire de l'image (ce qui, à mon sens, ne sert à rien, puisque le code binaire serait déjà le plus court possible ?)

J'ai fait une petite recherche sur Google et sur les forums de CCM sans trouver de solution. Si la réponse existe déjà quelque part, n'hésitez pas à me faire un lien !

Je vous remercie pour votre aide ! :)

6 réponses

Messages postés
593
Date d'inscription
mardi 31 juillet 2007
Statut
Membre
Dernière intervention
20 mai 2010
117
salut ,

avec les caractères tu cherche le nombre d'occurrence de chaque caractère (nombre de fois qu'il est utilisé dans ton code).Le but est de donner la plus petite valeur binaire a ton caractère le plus utilisé.
Sur une image , je pense que le choix ce fait au niveau du pixel , le pixel le plus utilisé reçoit la plus petite valeur binaire.

L'histoire est écrite par les vainqueurs ... 
Les logiciels, c'est comme le sexe: c'est pas parceque c'est payant que c'est meilleur
Messages postés
12
Date d'inscription
vendredi 9 mai 2008
Statut
Membre
Dernière intervention
29 juin 2010
3
Merci de ta réponse Luc !

Je vois très bien !
Par contre, cela signifie qu'il faut conserver l'arbre de chaque fichier si l'on veut les décompresser.

Y'a-t-il vraiment moins de poids en bits à enregistrer tous les arbres pour chaque fichier et diminuer leur code binaire ?

Merci
Messages postés
593
Date d'inscription
mardi 31 juillet 2007
Statut
Membre
Dernière intervention
20 mai 2010
117
je n'ai pas vraiment compris ta question : Y'a-t-il vraiment moins de poids en bits à enregistrer tous les arbres pour chaque fichier et diminuer leur code binaire ?
Messages postés
12
Date d'inscription
vendredi 9 mai 2008
Statut
Membre
Dernière intervention
29 juin 2010
3
^^ je m'explique un peu plus

Si par exemple j'ai 3 fichiers (images) à compresser sur un serveur.
Je veux que chaque fichier ait moins de poids.

En utilisant l'arbre de Huffman, je dois, pour chaque fichier, lire l'image, créer l'arbre, puis convertir le code binaire en un nouveau code binaire.
J'aurai donc enregistré 3 arbres (pour pouvoir décompresser mes fichiers), et les 3 nouveaux codes binaires à la place des codes binaires d'origine.

Ma question est donc est-ce que :
3 arbres de Huffman + 3 nouveaux codes binaires < 3 codes binaires d'origine ?

En gros : est-ce que ça compresse efficacement si on enregistre les arbres, et que ça prend forcément de la place...

:) Merci
Messages postés
593
Date d'inscription
mardi 31 juillet 2007
Statut
Membre
Dernière intervention
20 mai 2010
117
Ok c'est donc bien ce que j'avais compris ,

franchement je n'ai jamais appliqué les codages comme huffman ou fano-shannon , mes connaissances ne sont que théorique :s (malheureusement).

<quote>
Cette relation, qui montre que le codage de Huffman s'approche effectivement de l'entropie de la source et donc de l'optimum, peut s'avérer en fait assez peu intéressante dans le cas où l'entropie de la source est faible, et où un surcoût de 1 bit devient important. De plus le codage de Huffman impose d'utiliser un nombre entier de bit pour un symbole source, ce qui peut s'avérer peu efficace. WIKIPEDIA
</quote>

Donc le codage huffman n'est intéressant qu'a partir du moment ou tes fichiers on une certaine taille , en pratique je ne pourrais te dire a partir de qu'elle taille , il est plus intéressant d'avoir les arbres + nouveaux code a la place de l'ancien code .

Néanmoin pour te donner une idée

<quote>
pour coder 'Wikipédia', nous obtenons donc en binaire : 101 11 011 11 100 010 001 11 000, soit 24 bits au lieu de 64 en utilisant les codes ASCII.
</quote>

La compression est donc assez importante , néanmoins si tu veux compresser un monochrome ne t'attend pas a des miracles ^^
Messages postés
12
Date d'inscription
vendredi 9 mai 2008
Statut
Membre
Dernière intervention
29 juin 2010
3
^^
En cas d'image monochrome, j'utiliserai l'algorithme RLE : Run-Length Encoding ^^ ;)

Merci de ton aide Luc

Je ferai des essais :)