5.6 Segmentation en r´ egions
133
5.6.4 D´ ecomposition et fusion (Split and merge)
Les algorithmes de type d´ ecomposition/fusion exploitent les caract´ eristiques propres de chaque r´ egion (surface, intensit´ e lumineuse, colorim´ etrie,
texture, etc.). Cette technique enchaˆ ıne les deux phases suivantes :
1. D´ ecomposition (Split) : on d´ ecoupe it´ erativement l’image jusqu’` a avoir
des blocs contenant exclusivement des pixels similaires. Les crit` eres de
similarit´ e ou d’homog´ en´ eit´ e sont analogues ` a ceux qu’on utilise pour la
croissance de r´ egions. La m´ ethode couramment utilis´ ee consiste `
a faire une
dichotomie par blocs de l’image. Pour cela, on commence par d´ efinir un
bloc de la taille de l’image, puis on examine le contenu de ce bloc. Si le bloc
est homog` ene (c’est-` a-dire s’il contient exclusivement des pixels similaires)
alors on arrˆ ete la d´ ecomposition. Sinon, on d´ ecoupe le bloc en 4 sous-blocs
et on examine le contenu de chaque sous-bloc. On continue jusqu’` a ce qu’il
n’y ait plus besoin de d´ ecomposer les blocs. Le r´ esultat obtenu est donc
un ensemble jointif de blocs de diff´ erentes tailles qui recouvre enti` erement
l’image.
L’impl´ ementation la plus simple pour cette m´ ethode consiste `
a d´ efinir une
structure d’arbre appel´ ee QuadTree. C’est un arbre dans lequel chaque
nœud repr´ esente un bloc. Chaque nœud poss` ede donc 0 sous-nœud (bloc
homog` ene) ou 4 sous-nœuds (bloc non-homog` ene).
Fig. 5.25 Quad Tree
La d´ ecomposition finale est d´ efinie par les blocs associ´ es aux feuilles de
l’arbre. On obtient ainsi une liste de blocs de diff´ erentes tailles et positions. Si la structure du QuadTree permet une navigation ais´ ee entre bloc
conteneur (parent) et sous-blocs (enfants), elle ne permet pas de naviguer
facilement entre des blocs voisins. Pour cela, il est pr´ ef´ erable de construire
et d’utiliser un graphe d’adjacence.
133
5.6.4 D´ ecomposition et fusion (Split and merge)
Les algorithmes de type d´ ecomposition/fusion exploitent les caract´ eristiques propres de chaque r´ egion (surface, intensit´ e lumineuse, colorim´ etrie,
texture, etc.). Cette technique enchaˆ ıne les deux phases suivantes :
1. D´ ecomposition (Split) : on d´ ecoupe it´ erativement l’image jusqu’` a avoir
des blocs contenant exclusivement des pixels similaires. Les crit` eres de
similarit´ e ou d’homog´ en´ eit´ e sont analogues ` a ceux qu’on utilise pour la
croissance de r´ egions. La m´ ethode couramment utilis´ ee consiste `
a faire une
dichotomie par blocs de l’image. Pour cela, on commence par d´ efinir un
bloc de la taille de l’image, puis on examine le contenu de ce bloc. Si le bloc
est homog` ene (c’est-` a-dire s’il contient exclusivement des pixels similaires)
alors on arrˆ ete la d´ ecomposition. Sinon, on d´ ecoupe le bloc en 4 sous-blocs
et on examine le contenu de chaque sous-bloc. On continue jusqu’` a ce qu’il
n’y ait plus besoin de d´ ecomposer les blocs. Le r´ esultat obtenu est donc
un ensemble jointif de blocs de diff´ erentes tailles qui recouvre enti` erement
l’image.
L’impl´ ementation la plus simple pour cette m´ ethode consiste `
a d´ efinir une
structure d’arbre appel´ ee QuadTree. C’est un arbre dans lequel chaque
nœud repr´ esente un bloc. Chaque nœud poss` ede donc 0 sous-nœud (bloc
homog` ene) ou 4 sous-nœuds (bloc non-homog` ene).
Fig. 5.25 Quad Tree
La d´ ecomposition finale est d´ efinie par les blocs associ´ es aux feuilles de
l’arbre. On obtient ainsi une liste de blocs de diff´ erentes tailles et positions. Si la structure du QuadTree permet une navigation ais´ ee entre bloc
conteneur (parent) et sous-blocs (enfants), elle ne permet pas de naviguer
facilement entre des blocs voisins. Pour cela, il est pr´ ef´ erable de construire
et d’utiliser un graphe d’adjacence.