Algorithme séquentiel de construction des zones d'influence

Christian RONSE © (22/11/2007)
LSIIT UMR 7005 CNRS-ULP, Département d'Informatique de l'ULP



Supposons l'espace discret à deux dimensions (E = Z2), avec une distance d de chanfrein satisfaisant les conditions de Montanari. Soit S un masque rectangulaire dans E, et n marqueurs X1, ..., Xn inclus dans S. On peut construire dans le masque S les zones d'influence et le SKIZ des marqueurs, grâce à une variante de l'algorithme de transformée de distance. Celui-ci calculait pour tout pixel p de S une valeur f(p) égale à la distance de p à un marqueur R. Ici f(p) sera la distance de p au plus proche des marqueurs X1, ..., Xn (en d'autres termes, la distance de p à la réunion de ces marqueurs), mais l'algorithme associera aussi à p un entier m(p) entre 1 et n, qui est le numéro du marqueur le plus proche de p (donc m(p) = i pour d(p,Xi) = f(p)).

Approche Meyer-1 sans SKIZ

S'il y avait deux numéros distincts i et j tels que d(p,Xi) = d(p,Xj) =f(p), alors p appartiendrait au SKIZ, et il faudrait normalement attribuer à m(p) une valeur spéciale (par exemple 0 ou n + 1) correspondant au SKIZ. Les problèmes mentionnés précédemment (SKIZ passant entre les pixels, ou épais), font qu'il est plus simple d'adopter la démarche suivante, provenant du premier algorithme de Meyer pour la ligne de partage des eaux, que nous appellerons Meyer-1 :

  1. Pour chaque pixel p, la valeur de m(p) sera un entier entre 1 et n, c.-à-d. le numéro d'un marqueur ; donc le masque S sera partitionné en n zones d'influence, et on ne construit pas de SKIZ.
  2. Dans le cas où pour plusieurs numéros distincts i1, ..., is on a d(p,Xi1) = ... = d(p,Xis) = f(p), en d'autres termes si p appartient au SKIZ, alors on posera m(p) égal au plus petit des numéros i1, ..., is.
  3. Si on veut construire un SKIZ, soit on marquera comme points du SKIZ tous les interpixels situés entre deux pixels 8-adjacents appartenant à deux zones d'influence distinctes, soit on constituera le SKIZ de tous les pixels ayant un voisin (au choix : en 4- ou en 8-adjacence) appartenant à une zone d'influence ayant un numéro supérieur.

Si on considère uniquement les points 1 et 2 ci-dessus, c.-à-d. qu'on partitionne le masque en zones d'influence sans SKIZ, alors ces zones d'influence seront intermédiaires entre les zones d'influence au sens strict ZI(Xi) et les zones d'influence au sens large ZIL(Xi). Nous les appelons zones d'influence ordonnées et les notons ZIO(Xi). Elles sont définies comme suit : la zone d'influence ordonnée d'un marqueur est formée de tous les pixels strictement plus proches de ce marqueur que de tout autre marqueur de numéro inférieur, et plus proches ou à même distance de ce marqueur que de tout autre marqueur de numéro supérieur. Formellement :

On a ainsi :

Si on construit le SKIZ avec tous les pixels ayant un voisin appartenant à une zone d'influence ayant un numéro supérieur (cfr. le point 3 ci-dessus), alors les problèmes du SKIZ non-euclidien se résolvent de la façon suivante. Premièrement, le SKIZ ne pourra plus passer entre deux pixels, dans ce cas il sera dévié du côté de celui appartenant à la zone d'influence ayant le plus petit numéro (voir ci-contre). Deuxièmement, on n'aura plus de SKIZ épais ; une zone épaisse du SKIZ sera affectée à la zone d'influence de plus petit numéro, sauf son bord (non épais) avec l'autre zone. Ceci est illustré ci-dessous, où la zone épaisse du SKIZ (au sens originel) est hachurée, tandis que le SKIZ des zones d'influence ordonnées forme une ligne :

L'algorithme de transformée de distance s'adapte alors au calcul des zones d'influence ordonnées :

m et f sont deux fonctions définies sur S.
H est un nombre considéré comme "infini".

(0) Initialisation 

Pour chaque p dans S on pose

f(p) := 0   et   m(p) := i           si p appartient au marqueur Xi (i = 1, ..., n),
f(p) := H   et   m(p) := n+1     si p n'appartient à aucun de ces marqueurs.

(1) Balayage dans l'ordre direct :

Pour le pixel p allant du premier au dernier, faire

x := min { f(q) + M¯p(q) | q dans V¯(p) } ;
m(p) := min { m(q) | q dans V¯(p), f(q) + M¯p(q) = x } ;
f(p) := x .

(2) Balayage dans l'ordre inverse :

Pour le pixel p allant du dernier au premier, faire

x := min { f(q) + M+p(q) | q dans V+(p) } ;
m(p) := min { m(q) | q dans V+(p), f(q) + M+p(q) = x } ;
f(p) := x .

A la fin de l'algorithme, pour chaque pixel p du masque S, m(p) donnera le numéro i de la zone d'influence ordonnée ZIO(Xi) à laquelle il appartient, et f(p) donnera la distance de p à ZIO(Xi).

Les remarques que nous avons données concernant l'algorithme de transformée de distance restent valables ici.

Problèmes des approches avec SKIZ

Nous décrivons brièment deux autres approches qui construisent à des zones d'influence et un SKIZ. Nous les déconseillons, car leur comportement effectif cause des problèmes. Ici, pour un pixel p, la valeur de m(p) sera un entier m(p) entre 0 et n, où m(p) = 0 signifie que p fait partie du SKIZ, tandis que pour m(p) = i > 0, p fait partie de la zone d'influence du marqueur Xi.

Dans l'approche issue du second algorithme de Meyer pour la ligne de partage des eaux, que nous appellerons Meyer-2 :

  1. L'information de distance au plus proche marqueur ne peut être propagée que par les pixels qui n'appartiennent pas au SKIZ. En d'autres termes, pour un pixel p, le calcul de f(p) n'utilise les valeurs f(q) que pour les pixels q du voisinage de p vérifiant m(q) > 0.
  2. Un pixel p ayant deux plus proches marqueurs distincts sera marqué du SKIZ, c.-à-d. m(p) = 0.

L'algorithme décrit plus haut doit alors être modifié dans les étapes (1) et (2) de balayages dans l'ordre direct et dans l'ordre inverse. Nous ne décrivons ici que l'étape (1), l'autre est semblable :

(1) Balayage dans l'ordre direct :

Pour le pixel p allant du premier au dernier, faire
    S'il existe au moins un q dans V¯(p) tel que m(q) > 0 Alors :

x := min { f(q) + M¯p(q) | q dans V¯(p), m(q) > 0 } ;
A := { m(q) | q dans V¯(p), m(q) > 0, f(q) + M¯p(q) = x } ;
Si |A| = 1 Alors m(p) := élément de A Sinon m(p) := 0 ;
f(p) := x .

Le problème est que si tous les chemins les plus courts d'un pixel p à son marqueur le plus proche passent par des portions du SKIZ, alors les valeurs de f(p) et m(p) ne seront pas correctement mises à jour. Dans certains cas, f(p) et m(p) garderont les valeurs de l'initialisation.

Il y a une dernière approche construisant le SKIZ. Contrairement à celle de Meyer-2, il n'y a pas de restriction sur les pixels propageant l'information de distance. Elle a été utilisée dans l'algorithme de Soille et Vincent pour la ligne de partage des eaux (quoique leur algorithme suive un schéma différent). Nous donnons ici la modification de l'étape (1) de l'algorithme (balayage dans l'ordre direct), celle de l'étape (2) (balayage dans l'ordre inverse) est semblable :

(1) Balayage dans l'ordre direct :

Pour le pixel p allant du premier au dernier, faire

x := min { f(q) + M¯p(q) | q dans V¯(p) } ;
A := { m(q) | q dans V¯(p), f(q) + M¯p(q) = x } ;
Si |A| = 1 Alors m(p) := élément de A Sinon m(p) := 0 ;
f(p) := x .

Cette approche construira des SKIZ épais, et elle a tendance à propager le SKIZ à l'intérieur des zones d'influence.

Lorsque le SKIZ passe entre deux pixels (voir plus haut), les deux approches avec SKIZ ne marqueront aucun de ces deux pixels comme membre du SKIZ. Il faudra donc compléter le SKIZ de la même manière que pour l'approche Meyer-1. En conclusion, ces deux approches n'ont aucun avantage, mais uniquement des inconvénients, par rapport à l'approche Meyer-1 sans SKIZ.



Retour à l'index