 |
 |
Pour obtenir des contours en 4 (respectivement en 8) connexité il suffit d'éroder la composante de l'image dont on recherche les contours par un élément structurant de taille 1 construit sur les bases de la 8 (respectivement la 4) connexité puis de soustraire l'image obtenue à l'image initiale. Cette opération est facilement obtenue grâce à des fonctions déjà existantes sur khoros, notamment les fonctions de morphologie binaire et d'algèbre (érosion binaire et soustraction). On obtient alors des contours dont la 4 (respectivement la 8) connexité est assurée par construction.
Il est á noter qu'une érosion en 4 connexité donnera finalement un contour en 8 connexité (cf Théorème de Jordan).
 |
 |
 |
Le modèle utilisé pour obtenir les contours présentés dans cette page peut-être visualisé en cliquant sur le lien ci-dessous.
voir la fenêtre khoros
Dans les résultats présentés dans la partie suivante, l'image originale est l'image à niveaux de gris initiale. Celle-ci n'est donc pas encore seuillée.
Pour chacune des trois images, l'image originale est placée au dessus des images des contours obtenues en 4 (à gauche) et en 8 (à droite) connexité.
Les images sont :
- hommes.gif (l'église (/ima/images/don_images_1/architec/) )
- vlsi.gif (le circuit électronique (/ima/images/general/))
- corail.gif (le corail (/ima/images/general/))
 |
 |
 |
 |
 |
 |
 |
 |
 |
Commentaires
Dès que les contours présentent des parties obliques la 8 connexité se révèle supérieure à la 4 connexité. En effet, en 4 connexité, les contours apparaissent visuellement plus épais ou en marche d'escalier.
Cela se voit par exemple sur l'image du circuit vlsi. Dans cette image, le circuit présente une partie oblique à peu près orientée à 45°. Les contours en 8 connexité parviennent à bien coller à la courbe du contour tandis que les contours en 4 connexité, où les directions multiple-impaires de 45° sont absentes, doivent utiliser les directions verticales et horizontales pour suivre le tracé. Il y a donc deux fois plus de points d'où l'aspect visuel d'épaisseur du tracé. C'est aussi pourquoi les contours de l'image de corail apparaissent beaucoup plus épais. Les branches de corail partant dans toutes les directions, il est plus facile de coller au tracé avec les directions de la 8 connexité qu'avec celles de la 4 connexité.
La deuxième grande influence de la représentation en 4 ou en 8 connexité est la mémoire utilisée pour coder les contours. En effet la 4 connexité peut être codée sur 2 bits tandis que la 8 connexité requiert 3 bits. On pourrait donc penser que le coût de stockage est plus élevé pour la 8 connexité. Ceci n'est pas toujours vrai comme l'illustre l'image du corail. Lorsque les directions diagonales prédominent dans le tracé du contour, la 4 connexité utilise deux directions la où la 8 connexité n'en utilise qu'une seule. La taille mémoire n'est plus alors à l'avantage de la 4 connexité.
En général la 8 connexité est plus utilisée que la 4 connexité, comme par exemple pour les prédicteurs dans les algorithmes de codage.
Les problèmes rencontrés dans la représentation des contours peuvent être de l'ordre de l'analyse, par exemple mettre en évidence certaines propriétés de la courbe comme son aire ou ses axes de symétrie, ou de l'ordre de la synthèse, où une courbe doit être construite pour vérifier certaines propriétés spécifiques. La partie ci-dessous décrit quelques unes des techniques simples de manipulation des contours représentés en codage de Freeman et qui répondent aux problèmes cités précédemment.
Un exemple de dilatation peut être donné pour la chaîne codant le cercle minimal: 01234567. Une dilatation de facteur 4 donnera comme chaîne 00001111222233334444555566667777. Les contours correspondant sont représentés dans le tableau suivant. L'exemple proposé fait appel à la 8 connexité mais le procédé de dilatation est identique en 4 connexité.
 |
 |
L'exemple suivant se propose d'illustrer la distorsion engendrée par la contraction pour la chaîne 22101076. Si les directions pouvaient être regroupées par paires la contraction serait immédiate: en effet il suffirait de garder une direction sur deux pour obtenir la chaîne contractée. A l'évidence, ce n'est pas possible pour cette chaîne. On peut remarquer cependant que les deux premières directions satisfont à cette condition. De plus les quatre directions suivantes peuvent être réarrangées pour donner deux paires "11" et "00". Les deux dernières directions diffèrent d'une unité et leur moyenne ne parle en faveur d'aucune des deux directions. Dans un tel cas, la direction précédente est alors prise en considération et la moyenne de ces trois directions indique laquelle des deux directions est privilégiée. Dans cet exemple la moyenne de 0 (c'est à dire 8), 7 et 6 est la direction 7. La contraction est donc en résumé.
22101076
22110076
22110077
2107
La distorsion entraînée par cette contraction apparaît clairement dans la représentation du tracé originale et du tracé contracté visibles ci-dessous. Il est aussi ŕ noter que cet exemple est donné en 8 connexité mais que la procédure serait la même en 4 connexité.
 |
 |
A ce propos la figure suivante explicite certaines chaînes caractéristiques de certains angles.
 |
En 8-connexité, les voisins n'étant pas tous à la même distance du centre, il convient de distinguer les directions paires et impaires. Le périmètre est donc donné par le nombre de composants pairs additionné au nombre de composants impairs multiplié par racine de 2.
Le chemin inverse est le fait de parcourir le même tracé mais en sens inverse.
Le chemin inverse est obtenu en remplaçant chaque direction du tracé par sa direction inverse puis en inversant la chaîne de directions.
Par exemple, le tracé 1232076 a pour chemin inverse le tracé 2346765.
Pour exemple, la méthode va être appliquée sur le tracé 7107542 afin de trouver le plus court chemin joignant les deux extrémités de ce tracé. La longueur de cette courbe est 3+4.sqr(2). La courbe a deux paires de directions inverses, "15" et "04". On aboutit alors à la courbe réduite 772. Le remplacement de "72" par "0" amène finalement à une courbe composée uniquement de deux directions: 70. La distance entre les deux extrémités est donc 1+sqr(2). On peut le vérifier sur le schéma suivant.
 |
Si une courbe présente plus d'une série de directions pour lesquelles la réduction de chemin conduit au chemin nul et si ces séries ne se chevauchent pas et sont séparées par un nombre de paires qui s'annulent entre elles, alors la courbe est constituée de plusieurs boucles connectées entre elles. La série de paires qui s'annulent représente en fait la branche de connexion entre les différentes boucles. La courbe 0112334556772321076546 est un exemple d'un tel chemin composé de boucles reliées entre elles par une branche de connexion.
Dans les figures suivantes les tracés ont été dilatés d'un facteur 4 pour une meilleure lisibilité.
 |
 |
Pour trouver le point d'intersection entre deux courbes, il faut tout d'abord spécifier une branche de connexion entre les deux courbes qui servira à placer deux points de départ en deux positions. La branche de connexion peut-etre n'importe quelle courbe simple formant une branche entre un point de départ sur une courbe et un point d'arrivée sur la seconde. Mais elle ne doit malgré tout ne toucher les courbes qu'uniquement en ses deux points extrémités. En parcourant la première courbe puis la seconde (avec pour point de départ les extrémités de la branche de connexion) une réduction de chemin est effectuée pas à pas en considérant une direction supplémentaire à chaque fois.
Chaque courbe réduite est réorganisée pour positionner ses directions dans un ordre numérique croissant. Les longueurs des chemins réduits sont aussi calculées à chaque étape. Les deux chemins réduits sont ensuite comparés. Pour une séquence de réduction de chemin qui est commune aux deux courbes, les deux courbes s'intersectent sur un point de la grille orthogonale. Si les chemins réduits des deux courbes ne diffèrent d'un seul élément (soit par une différence de valeur pour une direction, soit par l'absence d'un élément) deux fois successivement, et si simultanément les longueurs des courbes de la séquence échangent leur rôle, il existe une intersection entre points de la grille.
On peut appliquer cette méthode pour étudier l'intersection de deux courbes A et B: A=01066112 et B=020117. Ces deux courbes sont connectées par une branche 66 en leur premier point. Les réductions de chemin successives et les longueurs associées sont reprises ci-dessous.
| Séquence | Longueur | |
| Pour A: | 1) 0
2) 01 3) 010=001 4) 0016=000 5) 0006=007 6) 0071=0000 7) 000001 8) 000012=00011 |
1
1+sqr(2) 2+sqr(2) 3 2+sqr(2) 4 4+sqr(2) 3+2.sqr(2) |
| Pour B: | 1) 6
2) 66 3) 660=67 4) 672=7 5) 70=07 6) 071=000 7) 0001 8) 00017=00000 |
1
2 1+sqr(2) sqr(2) 1+sqr(2) 3 3+sqr(2) 5 |
En étudiant les deux séries de réduction de chemin, il apparait que A(4) correspond à B(6), indiquant la présence d'une intersection sur un point de la grille orthogonale. De plus, A(6) et B(7) ne diffèrent que d'une seule direction et la même chose se reproduit pour A(7) et B(8). Simultanément la longueur de A passe de 4 à 5.414 et celle de B passe de 4.414 à 5 rendant ainsi A plus long que B. De là on déduit que les courbes ont une intersection entre les points de la grille orthogonale définie par les points extrémités des 4 séquences A(6), A(7), B(7) et B(8). On peut vérifier la justesse des résultats de cette méthode sur la figure suivante.
 |
De là découle la méthode suivante pour déterminer l'aire incluse dans un contour. Il faut d'abord définir un "modifier" qui représente la distance courante de la courbe à l'axe des x. Ainsi dans la figure suivante l'aire A est initialement à 0 et le modifier B est égal à "2". La première direction est "1" (c'est à dire 45°) et entraîne donc un accroissement de l'aire courante de la valeur de la premier colonne (soit 2.5) et du modifier d'une valeur de 3. La direction suivante, "0", n'entraîne aucune modification du modifier puisque le tracé progresse parallèlement à l'axe des x, mais entraine par contre une modification de l'aire de la valeur du modifier (c'est à dire 3). L'aire courante est donc maintenant de 5.5. Il est à noter que le modifier donne la valeur du bord principal de la colonne verticale considérée. Lors de l'étape suivante, la direction "1" accroît l'aire de la valeur du modifier plus 0.5 (ce qui donne une aire de 9) et porte la valeur du modifier à 4. La direction 2 ne change pas l'aire mais donne au modifier la valeur 5. La direction suivante "7" accroît l'aire de la valeur du modifier minorée de 0.5 soit une valeur finale de 4.
La méthode précédente peut être généralisée pour donner un ensemble de règles à appliquer pour chacune des 8 directions. Le tableau ci-dessous indique, suivant la direction appliquée, les changements à opérer sur les valeurs de l'aire courante et du modifier.
Si le point de départ coincide avec l'origine, le modifier est initialement à 0, sinon il est nécessaire de prendre les bonnes conditions initiales.
| Directions | Modification de l'aire | Modifications du modifier |
| 0
1 2 3 4 5 6 7 |
+B
+B+0.5 +0 -B-0.5 -B -B+0.5 +0 +B-0.5 |
+0
+1 +1 +1 +0 -1 -1 -1 |
Soit la courbe fermée 1013532107765544 représentée dans la figure ci-dessous. La courbe est parcourue dans le sens des aiguilles d'une montre et possède une aire de 11 unités carré. La valeur initiale de B est prise à 0.
| N | A | B |
| 1
0 1 3 5 3 2 1 0 7 7 6 5 5 4 4 |
0.5
1.5 3 0.5 -2 -4.5 -4.5 0 5 9.5 13 13 11.5 11 11 11 |
1
1 2 3 2 3 4 5 5 4 3 2 1 0 0 0 |
 |
 |
03.97 page maintenue par:
ndehais@email.enst.fr
vmoreau@email.enst.fr