Algorithme d'approximation polygonales

Version imprimable

16/01/2011, 17h59
amateur87

1 pièce(s) jointe(s)

Algorithme d'approximation polygonales

Bonjour à tous,
Après avoir obtenu avoir une image contours grâce à un filtre passe haut(laplacien), je dois appliquer l'algorithme d'approximation polygonale pour l'extraction des segments de contours.
Mais juste après avoir coder l'algorithme, je me suis rendu compte qu'il ya des problèmes résoudre au préalable:

1-Les contours sont souvent très épais.
Comment les amincir pour qu'il ait la largeur d'un pixel?

2-J'ai utilisé une liste chaînée pour récupérer les points de contours, mais il ya un problème d'ordre. Moi j'ai fait un balayage de l'image par colonne de gauche à droite.
Comment les récupérer en suivant les lignes de contours?

Pour mieux illustrer le second problème j'ai joins une capture d'écran du résultat obtenu. L'image de droite représente l'image de contours et celle de gauche, les segments de contours.

Merci d'avance.
Cordialement.
16/01/2011, 18h37
pseudocode

Bonjour,

Citation:

Envoyé par amateur87

1-Les contours sont souvent très épais.
Comment les amincir pour qu'il ait la largeur d'un pixel?

Il faut utiliser un algorithme d'amincissement (thinning algorithm). On a déjà donné des exemples dans ce forum (squetisation), et il y en a d'autres disponibles sur le net.

Citation:

2-J'ai utilisé une liste chaînée pour récupérer les points de contours, mais il ya un problème d'ordre. Moi j'ai fait un balayage de l'image par colonne de gauche à droite.
Comment les récupérer en suivant les lignes de contours?

J'ai du donner ce lien au moins 10 fois, mais je recommence : contour tracing algorithm

Je te conseille l'algo de Moore, avec un rayon de recherche de 5 pixels (ou +), pour combler les "trous" dans ton image.
16/01/2011, 19h28
amateur87

Merci bcp pour la réponse,
je fonce voir.
Veillez m'excusez de ne pas avoir lu toutes discussions pour retrouver la même question en vous évitant ainsi de vous répéter.
16/01/2011, 22h47
pseudocode

Citation:

Envoyé par amateur87

Merci bcp pour la réponse,
je fonce voir.
Veillez m'excusez de ne pas avoir lu toutes discussions pour retrouver la même question en vous évitant ainsi de vous répéter.

C'est pas bien grave. Ca me permet de répondre plus vite aux questions. :mrgreen:
19/01/2011, 14h35
amateur87

Bonsoir Mr Philippeau,

j'ai un petit problème avec l'algorithme de Moore concernant la condition de terminaison.
Si j'applique le critère de Jacob par exple,
comment puis-je savoir s'il n'ya pas d'autres objets dans l'image ayant un contour fermé?
De combien de pixels dois-je me déplacer dans l'image pour être sûr de ne pas tomber sur le même objet que je viens de traiter?
merci d'avance.
Cordialement.
19/01/2011, 16h37
pseudocode

Citation:

Envoyé par amateur87

Bonsoir Mr Philippeau,

j'ai un petit problème avec l'algorithme de Moore concernant la condition de terminaison.
Si j'applique le critère de Jacob par exple,
comment puis-je savoir s'il n'ya pas d'autres objets dans l'image ayant un contour fermé?
De combien de pixels dois-je me déplacer dans l'image pour être sûr de ne pas tomber sur le même objet que je viens de traiter?
merci d'avance.
Cordialement.

Préalablement à l'étape de tracé de contour, on procède habituellement à l'extraction des composantes connexes. Cette première étape nous permet de savoir combien il y a d'objets dans l'image.
20/01/2011, 00h23
amateur87

Veuillez m'excuser pour ma question si elle est un peu stupide,
il s'agit de la condition de terminaison de Jacob de l'algorithme de Moore.
Je n'ai pas bien saisi le fonctionnement de cette condition au-delà du sens linguistique:

Citation:

Stop after entering the start pixel a second time in the same manner you entered it initially

s'agit-il du fait que le backtrace du pixel de start doit correspondre à celui de sa seconde rencontre?
Qu'est-ce qui caractérise "la même manière dont on l'a inséré initialement"?
Merci d'avance.
Cordialement.
20/01/2011, 11h15
pseudocode
Citation:

Envoyé par amateur87

Qu'est-ce qui caractérise "la même manière dont on l'a inséré initialement"?

Pour commencer l'algorithme de tracé, on doit trouver un premier pixel du contour. Cela se fait en cherchant un pixel de la composante qui a (au moins) un voisin n'appartenant pas a la composante.

Sur une image binaire, on cherche un pixel blanc qui à pour voisin (au moins) un pixel noir.
Code:

1 2 3 4 5 6 7 8 +--+--+--+ |0 |0 | 1| +--+--+--+ |0 | 1| 1| +--+--+--+ |0 |0 | 1| +--+--+--+
La position de ce pixel noir par rapport au pixel blanc central nous donne la direction du "point d'entrée" initial dans la composante.
Code:

1 2 3 4 5 6 7 8 +--+--+--+ |0 |0 | 1| +--+--+--+ |0-->1| 1| +--+--+--+ |0 |0 | 1| +--+--+--+
20/01/2011, 13h19
amateur87

Merci bcp, j'ai pu bien saisir grâce à ce schéma très simple et très explicite.
Vraiment une image vaut 1000 mots!!!

Mais concernant votre avant dernière réponse, y-a-t-il dans la littérature un algo qui me permettra de connaître le nbre d'objets dans l'image?
Merci bcp.
Cordialement.
20/01/2011, 14h43
pseudocode

Citation:

Envoyé par amateur87

Mais concernant votre avant dernière réponse, y-a-t-il dans la littérature un algo qui me permettra de connaître le nbre d'objets dans l'image?

Il y a tout un tas d'exemples dans la rubrique "contribuez" du forum.

Et, hasard du calendrier, Toto13 vient de rassembler tout le code dans une seule archive.

:arrow: Etiqueter les composantes connexes

:ccool: