Le Coin du Traitement d'Image

Hiérarchique ?

=> Tout objet possède sa propre échelle

C'est pourquoi une image des régions n'est pas un résultat suffisant pour être exploitable : il faudrait dans l'idéal une image des régions pour chaque échelle. D'où le terme "hiérarchique".

Présentation de l'algorithme

• A l'initialisation, chaque pixel est considéré comme une région.

• Les régions sont fusionnées avec leur voisines comme suit, jusqu'à ce que toutes les fusions possibles aient été effectuées :

  • Dans l'ordre croissant du gradient de leur frontière commune

  • Sous la condition que la valeur du gradient soit inférieure au niveau de bruit (premier paramètre) ou que l'une des deux régions ait une taille inférieure à la taille requise (second et dernier paramètre).

L'aspect hiérarchique de l'algorithme s'obtient en bouclant sur les tailles minimales croissantes spécifiées et en sauvant les résultats pour chacune. Le processus repartant du résultat de la taille minimale précédente, le traitement d'une échelle supplémentaire est non seulement très rapide, mais il assure aussi que les nouvelles régions seront un assemblage d'une ou plusieurs régions de l'échelle précédente.
Cette propriété est très importante, car elle permet une mise en forme du résultat en pyramide de région.

Les informations de sortie sont différentes de celles d'un algorithme classique :

• Une image de numéros de région (chaque pixel représente un nombre entier). Elle correspond à l'image classique des régions de l'échelle la plus fine (taille de 50 pixels dans l'exemple). Toutefois, la numérotation est spéciale (voir point suivant).

• Une liste de couples {Rmin, Rmax}, pour chaque échelle spécifiée (3 dans l'exemple, 50, 500 et 5000). Chaque couple { Rmin, Rmax } correspond à une région dont le support dans l'image est l'ensemble des pixels de numéro de regions compris entre Rmin et Rmax (pour les régions de l'échelle la plus fine, Rmin=Rmax).
  

Note : Une phase de débruitage de l'image (similaire à un filtre alterné séquentiel mais en plus rapide) a été incorporée avant la phase de fusion pour améliorer la robustesse au bruit.

Note : L'algorithme utilise l'information de couleur quand elle est disponible.

Temps de calcul

L'objection à venir est la suivante : appliquer cet algorithme tel quel entraîne des temps de calcul prohibitifs (O(N²) en nombre de pixels de l'image).
Quelques approximations mineures, notamment celle du recalcul du "gradient entre régions", et une implémentation efficace du tri par ordre croissant de gradient des voisinages de régions en viennent à bout.

Pour donner un ordre d'idée, le résultat précédents sur l'image "maison", de taille 512x512 pixels, a été obtenu en 0.35 secondes (0.31 s pour les deux premières échelles (50 et 500) et 0.28 s pour la première seule (50)).

L'algorithme a été implémenté en C++ (compilé avec GNU g++ 3.2.2 option -O2 sous Linux, sur un processeur AMD 1800+).

Autres exemples de résultats

La première ligne affiche les images avec des couleurs particulière pour faire ressortir les contrastes. La couleur des régions est la couleur moyenne.
La seconde ligne affiche les images avec des couleurs aléatoires par zones.

Paramètres de l'algorithme :

• L'intensité du bruit est fixée à 20 (pour tous les resultats présentés).
• Le paramètre de taille minimale est donnée en légende de chaque résultat.

Image 640x480 de la grue du site Microsoft de Cambridge, traitée en 0.39 s

Image initiale

Image initiale

Taille min=40px (697 régions)

Taille min=300px (172 régions)

Taille min=2000px (31 régions)

Image 768x576 du chateau de Leuven, traitée en 0.63 s

Image initiale

Image initiale

Taille min=100px (969 régions)

Taille min=400px (260 régions)

Taille min=2500px (58 régions)