Obligement - L'Amiga au maximum

Vendredi 17 novembre 2017 - 18:33  

Translate

En De Nl Nl
Es Pt It Nl


Rubriques

 · Accueil
 · A Propos
 · Articles
 · Galeries
 · Glossaire
 · Hit Parade
 · Liens
 · Liste jeux Amiga
 · Quizz
 · Téléchargements
 · Trucs et astuces


Articles

 · Actualité (récente)
 · Actualité (archive)
 · Comparatifs
 · Dossiers
 · Entrevues
 · Matériel (tests)
 · Matériel (bidouilles)
 · Points de vue
 · En pratique
 · Programmation
 · Reportages
 · Tests de jeux
 · Tests de logiciels
 · Tests de compilations
 · Articles divers

 · Articles in english
 · Articles in other languages


Twitter

Suivez-nous sur Twitter




Liens

 · Sites de téléchargements
 · Associations
 · Pages Personnelles
 · Moteurs de recherche
 · Pages de liens
 · Constructeurs matériels
 · Matériel
 · Autres sites de matériel
 · Réparateurs
 · Revendeurs
 · Presse et médias
 · Programmation
 · Développeurs logiciels
 · Logiciels
 · Développeurs de jeux
 · Jeux
 · Autres sites de jeux
 · Scène démo
 · Divers
 · Informatique générale


Jeux Amiga

0, A, B, C, D, E, F,
G, H, I, J, K, L, M,
N, O, P, Q, R, S, T,
U, V, W, X, Y, Z


Trucs et astuces

0, A, B, C, D, E, F,
G, H, I, J, K, L, M,
N, O, P, Q, R, S, T,
U, V, W, X, Y, Z


Glossaire

0, A, B, C, D, E, F,
G, H, I, J, K, L, M,
N, O, P, Q, R, S, T,
U, V, W, X, Y, Z


Partenaires

Annuaire Amiga

Amedia Computer

Relec

Hit Parade


Contact

David Brunet

Courriel

 


Dossier : Le traitement d'images numériques - quadtree et découpages itératifs
(Article écrit par Barrou Diallo et extrait d'Amiga News - janvier 1997)


Après les petites transformations géométriques du mois dernier, nous allons revenir à des propos un peu plus orientés "traitement du signal" et étudier encore quelques méthodes pour torturer ces fameuses images. Suite à de nombreuses remarques de lecteurs qui voulaient obtenir des documentations sur les différentes applications qu'ils font du traitement d'images, je vais essayer de rester assez généraliste dans le sens de mon exposé. Cette matière a la chance d'être utilisée dans des milieux aussi différents que l'industrie lourde, la détection d'objets volants à l'armée, la quantification de tumeurs dans le monde biomédical, la reconnaissance de caractères manuscrits, l'analyse de scène en visionique, l'hydrométrie dans l'imagerie satellite et tant d'autres domaines que j'oublie. Cette variété d'application entraîne automatiquement une variété d'approches dans les problématiques. Images à canal unique versus multicanaux, images paramétriques ou symboliques, images bruitées ou floues. Bref, les problèmes dans la reconnaissance de forme et l'interprétation automatique de scène ne manquent pas.

Le partitionnement des images

Une approche assez classique en logique est de résoudre un problème en essayant de le sous-diviser en plusieurs parties qui sont autant de nouveaux petits problèmes plus faciles à résoudre. Merci à M. Descartes qui a jeté les bases de ce principe que l'on applique aujourd'hui (entre autres) à l'image. Mais comment décomposer une image ? Il existe évidemment plusieurs méthodes : la décomposition spectrale (Transformée de Fourrier) ou des transformations plus "algorithmiques" basées sur la géométrie discrète.

Le quadtree

La première idée qui vient à l'esprit lorsque l'on veut découper une image est de la diviser en deux, puis en quatre, puis en huit et ainsi de suite. Ce découpage par pavages carrés réguliers est appelé quadtree. Ce terme désigne un arbre (au sens structure de données du terme) composé de zones carrées qui composent ses feuilles. Nous avons ici une représentation typiquement récursive : soit une image que l'on découpe en quatre et pour chacun des morceaux on réapplique ce découpage. Ce processus peut être itéré jusqu'à la notion de pixel (qui prend ici tout son sens). Si l'image fait une taille NxN, alors le nombre de découpage (le nombre de niveaux dans l'arbre) est de N+1. La figure 1 présente une image binaire en noir et blanc très simple qui a été découpée selon le principe expliqué ci-dessus. De ce découpage, résulte l'arbre de la figure 2 qui comporte trois type de noeuds : les noeuds x qui représentent les zones non homogènes, les noeuds noirs et les noeuds blancs. Chaque noeud peut être numéroté comme le montre la figure 3. Cette numérotation est importante et attribue en quelque sorte un "label" à une zone, ce qui permettra plus tard de passer de coordonnées 2D à des valeurs uniques.

Traitement images

Traitement images

L'application de ce découpage peut se faire sur une image binaire ou en niveaux de gris. Chaque bloc représente alors une zone dite "homogène". Le critère d'arrêt du découpage est simple sur une image binaire : si la zone contient à la fois des pixels noirs et des pixels blancs, alors, il faut la redécouper de nouveau. Sinon, il faut s'arrêter et considérer que la zone est homogène.

Traitement images

Dans une image en niveaux de gris et, pire encore, sur une image couleur, les critères d'arrêts sont loin d'être évidents. Différentes approches ont été mises en œuvre et nous pouvons citer, entre autres, l'analyse des textures de la scène, les calculs de variances et de moyennes, les approches de la théorie de l'information ainsi que d'autres critères plus "physiques" comme le critère d'hystérésis. La construction d'un quadtree est donc liée à une recherche d'homogénéité (variance minimale, attributs semblables, etc.). Une fois cet arbre construit, seule la première étape est achevée. La seconde consiste à rassembler les zones suivant d'autres critères moins abrupts que le découpage par pavages. On appelle cette étape la fusion de zone. Là encore, de nombreuses méthodes permettent de fusionner ou regrouper des zones arbitrairement séparées. Nous y reviendrons plus tard.

Prenons d'abord le temps d'expliquer l'implémentation de ce type d'arbre qui, il est vrai, soulève des questions intéressantes du point de vue programmation. Le découpage récursif consomme à la fois du temps de calcul et de la mémoire. Même si, de nos jours, ces deux paramètres sont de moins en moins importants, une mauvaise implémentation du quadtree entraîne une perte de temps considérable.

Vision simpliste du découpage récursif :
	Procédure DécoupeZone (StructZone zone)
	Début
		Si zone != Homogène Alors
			DécoupeZone (zone)
		Sinon
			Stocke les paramètres
	Fin
Cette façon de coder une arborescence est intuitive mais, reste inadaptée aux ordinateurs de bureau. Cette fonction récursive (qui se rappelle elle-même) construit via la pile système l'arbre quaternaire de l'image. Mais, comme la pile n'est pas infinie, cette méthode est très dépendante de la taille de l'image. En fait, la représentation mémoire de l'arbre nécessite la mise en oeuvre de pointeurs (ou d'adresses de cases), ce qui alourdit le processus. L'arbre est construit à partir de la racine et donc tous les pixels sont consultés un nombre de fois équivalent au nombre de niveaux dans lequel il apparaît. Le test d'homogénéité d'une zone est effectué pour tous les pixels d'une zone. Cette zone pouvant être découpée, il sera de nouveau effectué sur ces pixels. Bref, le coût en temps de calcul n'est plus à démontrer, il faut donc trouver une astuce d'implémentation.

L'une des implémentations les plus astucieuses est celle utilisant le codage de la courbe de Peano en Z. A la première itération, les zones sont parcourues dans un sens strict (celui de Peano) comme le montre la figure 4. Ce parcours est répété pour toutes les récursions de toutes les zones. La figure 5 montre la courbe de Peano à l'itération 2. Il faut ainsi de suite redécouper les zones et agrandir cette fameuse courbe. Les propriétés de cette courbe sont immenses et vous remarquerez que si l'on pousse le processus jusqu'à son terme, c'est-à-dire le pixel, on remplit le plan grâce à une courbe en une dimension ! Elle permet donc de passer d'une dimension à une autre, et là, la théorie des fractales prend tout son sens.

Traitement images

Traitement images

A une itération i, quelle est la dimension fractale de la courbe de Peano ? Ni 1 ni 2, elle a une dimension non entière, elle est donc fractale. Nous pourrons revenir aux applications des fractales dans le domaine du traitement de l'image lors d'autres articles mais, notez seulement que ce codage permet de coder une position par un nombre en base 4. La figure 6 montre une image (boules noires) codée par cette méthode. On détecte trois objets {02} {13} et {3}. Le fait de coder une image de la sorte entraîne un gain de place et de parcours. Toute l'information de cette image binaire peut donc être comprimée en ces trois nombres grâce à la courbe de Peano. Le nombre de chiffres qui le composent donne automatiquement le niveau d'itération et par une astuce de codage, il est possible d'associer à chaque pixel (x,y) un nombre sur la courbe de Peano. Cette méthode, qui est une bijection de N2 dans N, est appelée clé de Peano. Elle est formée en intercalant les bits des coordonnées pixels (x,y) un à un. La figure 7 montre cet intercalage qui forme la clé pour passer d'un espace à l'autre. A un couple de coordonnées correspond donc une valeur unique donnée par la clé.

Traitement images

Traitement images

Remarques et restrictions

Cette méthode ne peut s'appliquer que sur des images carrées ou centrées dans une grande image carrée. La largeur ou longueur des carrés est une puissance de deux ce qui a permis l'analogie avec le codage binaire. Bref, cette structure est bien adaptée à l'esprit d'un ordinateur et donc d'un informaticien. Ensuite, on remarquera que ce découpage arbitraire en carrés égaux est grossier et inadapté à des images naturelles. Notons tout de même un avantage : cette méthode n'est pas dépendante de la dimension de l'image, on peut l'appliquer à des images 3D, à des séries de coupes conjointes ou même à des séries temporelles dans le but d'une compression d'informations.

Une approche commune

Il existe toutefois un invariant dans cette diversité d'algorithmes : le traiteur d'images en revient souvent à cette notion d'histogramme et de seuillage. Tout commence ou se termine par un seuillage dira-t-on ? Presque, car un seuillage qu'il soit simple ou multiple équivaut, dans la pratique, à créer des zones de pixels isoprobables. Voyons maintenant la méthode proposée par Nakagawa qui consiste comme nous l'avons montré plus haut à découper l'image en zones d'intersection vide dans lesquelles on calcule l'histogramme. Cet histogramme est approximé par deux gaussiennes si l'écart entre les deux modes (Cf. figure 8) est suffisant. Il ne faut pas oublier de lisser cet histogramme en appliquant soit un filtre moyenneur, soit un filtre médian 1D sur trois valeurs consécutives. La figure 9 représente la formule qui permet d'approximer un histogramme bimodal par la somme de deux lois de Gauss. Il y a donc six paramètres à ajuster pour approcher ce modèle. Le critère utilisé par Nakagawa est simple à calculer. Une zone est considérée comme bimodale si et seulement si :
  • 1. u2-u1 > 4
  • 2. 0.1 < sigma1 / sigma2 < 10
  • 3. delta < 0.8
u1 et u2 sont les moyennes des modes de l'histogramme. Sigma1 et sigma2 sont les écarts-types de l'histogramme, delta est le résultat de la formule donnée en figure 10.

Traitement images

Traitement images

Traitement images

Si l'histogramme de la zone en cours est considéré comme bimodal, alors, on applique la formule 11 qui consiste à minimiser l'erreur d'une mauvaise séparation des pixels sachant la distribution observée (f). La valeur "s" est le seuil à appliquer. Ce seuillage donne de bons résultats si les distributions sont à peu près gaussiennes. Il est appelé dynamique et adaptatif car le découpage successif de l'image permet de s'affranchir des hétérogénéités de spatiales.

Traitement images

Conclusion

Nous avons étudié deux grandes méthodes de segmentation qui sont le quadtree et le découpage adaptatif en vue d'un seuillage. Ces méthodes, loin d'être neuves, sont très utilisées de par leur simplicité de programmation, et la qualité des résultats. Elles reposent le problème de la qualité versus la rapidité. Il est encore difficile d'avoir ces deux paramètres complètement décorrélés. Il n'est, par exemple, pas possible d'effectuer ces traitements en temps réel sur une chaîne de montage dans l'industrie... Après cet exposé un peu plus approfondi, nous reviendrons à d'autres méthodes de partitionnement tout aussi efficaces, mais peut-être encore une fois assez lentes à mettre en oeuvre.

Références :

Samet H : The Quadtree and related hierarchical data structures, Computing Surveys, vol 18n p298-303, 1982.
Nakagawa Y., Rosenfeld, A. : Some experiments on variable thresholding, Pattern Recognition, vol 11, p191-204, 1979.
Meagher, D. : Geometric Modeling using octree encoding, Computer graphics and image processing, vol 19., p129-147, 1982.


[Retour en haut] / [Retour aux articles] [Article précédent]