pen icon Colloque
quote

Codage d'images avec automates à états finis

Charles Quenneville
Gefia Hahn
Jean Meunier
CQ

Membre a labase

Charles Quenneville

Résumé du colloque

La représentation d'images par tétrarèbres est bien connue, mais peut nécessiter beaucoup d'espace mémoire. Il a été observé qu'en liant les tétrarèbres sont équivalents aux langages rationnels (i.e. reconnaissables par des automates à états finis); ces derniers étant moins encombrants, plus simples et plus flexibles. Notre objectif est d'étudier cette correspondance tétrarèbre-automate dans le but de coder et de manipuler des images binaires (deux niveaux de gris), à plusieurs niveaux de gris ou en couleurs. Pour encoder une image sous forme d'automate, il faut suivre les grandes étapes suivantes: (1) construire l'automate de l'image en se basant sur le principe de construction des tétrarèbres, (2) minimiser le nombre d'état à l'aide d'un algorithme basé sur le théorème de Myhill-Nerode, (3) sauvegarder la table de transition de l'automate minimal sur disque et (4) réafficher l'image à partir du fichier résultant, en reconstruisant l'automate minimal décrit dans le fichier et en régénérant l'image correspondante. Les mêmes étapes sont appliquées pour les images à plusieurs niveaux de gris et à plusieurs couleurs en minimisant en augmentant le nombre d'états finaux pour tenir compte du nombre de niveaux de gris ou de couleurs dans l'image. Les résultats obtenus montrent que notre méthode est efficace pour les images contenant un pattern redondant; le nombre d'états de l'automate après minimisation dans ces cas est de loin moindre au nombre de noeuds du tétrarèbre équivalent. Cette méthode est aussi avantageuse pour les images ayant de grandes sections de même couleur, comme pour les tétrarèbres. Les opérations habituelles sur les tétrarèbres sont applicables sur les automates et sont plus simples et flexibles d'utilisation. Les automates gardent donc tous les avantages des tétrarèbres tout en étant plus simples à manipuler et moins encombrants.

Contexte

Section :
Informatique et recherche opérationnelle
news icon Thème du colloque :
Informatique et recherche opérationnelle
host icon Hôte : Université de Montréal

Découvrez d'autres communications scientifiques

news icon

Titre du colloque :

Informatique et recherche opérationnelle
Évaluation de la contraction cardiaque tridimensionnelle en ventriculographie monoplan par détermin…
Zohra Sehbouh
Codage d'images avec automates à états finis
Charles Quenneville
Les systèmes intelligents embarqués appliqués au transport routier: promesses et réalités
Jean-François Martin
Voir tous les contenus de ce colloque

Autres communications du même congressiste :

news icon

Thème du colloque :

Informatique et recherche opérationnelle
Codage d'images avec automates à états finis
Charles Quenneville
Codage d'images avec automates à états finis
Charles Quenneville