Discussion :

[AlphaJ]

Salut
Je souhaite obtenir les pixels de contours d'un objet dans une image étiquetée, dans l'ordre suivant un des deux sens (horraire ou trigo).
-Mon image a la forme suivante par exemple :

0 0 0 0 0 0 0 0
0 1 1 1 1 1 1 0
0 1 0 0 0 0 1 0
0 1 0 0 0 0 1 0
0 1 1 1 1 1 1 0
0 0 0 0 0 0 0 0

1-J'ai commencé par deux for afin de balayer l'image
2-Je détecte le premier pixel qui appartient à l'objet.
3-je fais un balyage recursif pour ses voisins de la manière suivant:
***
*1*
***
4-je detecte le voisin qui appartient à l'objet et je continue comme ça.

Le problème c'est ce que j'arrive pas à arrêter la procédure !!!!

Je cherche un code idéal pour ce problème ...

Merci

[nikko34]

Tu peux marquer les pixels que tu as déjà parcouru.

[AlphaJ]

je les ai déjà marké mais le problème c'est quand je traite le pixel qui est au coin en bas droite, je peux pas continuer !

[eomer212]

tu peux résoudre ton probleme de bords de 3 maniéres.
soit tu crée un espace de stockage de tes pixels qui soit 2 lignes et deux colonnes plus grands que l'original, auquel cas ces lignes seront systématiquement remplies avec des 0 et tu n'auras pas à gérer l'effet de bord. de plus ca ne te bloquera plus..
inconvenient, ca fait plus de bytes.. mais bon..
ca élimine toutes les vérifications et les accés necessaires.

deuxieme possibilités, tu vérifies sytématiquement via une fonction genre
pixelpossible(x,y) que le pixel que tu veux tester à coté est testable..
ca t'évitera les débordements.


ou alors tu inclues directement le code de vérification avant le test dans ta boucle de parcours.. un peu caca, mais ca marche aussi.

[ToTo13]

Bonjour,

pour faire ce genre de parcours récursif, il faut au préalable donner des priorités de directions (par exemple haut, gauche, bas, droite) et surtour marquer les pixels déjà parcourus.
Tu essaies donc toujours de commencer par aller en haut, si c'est impossible (pas de pixels plein au dessus, ou pixel n'appartenant pas au bord ou pixel déjà visité), tu essaies d'aller à gauche, ...

Une autre solution peut être plus facile mais moins élégante, c'est de faire comme dans la première étape de la marche de Graham (pour trouver l'enveloppe convexe) :
- tu sélectionnes tous les points du contours.
- tu trouves le barycentre B et le point P le plus en haut à droite.
- tu tries les points "p" en fonction de l'angle PBp.
La complexité est en O(N Log N), qui est la complexité du trie par comparaison (QuickSort ou tri par tas) car les deux premières opérations sont en O(N).

Petite correction (Merci PseudoCode), la deuxième version que j'ai donné marche pour des formes convexes ou étoilées, mais par pour des formes fortement non convexes.

[screetch]

je n'ai pas compris si tu cherchais a avoir le contour ou si tu avais le contour et voulait lister tous les points ?

voila une liste d'etapes a effectuer :

ton image de depart, c'est

0 0 0 0 0 0 0 0 0 0
0 1 1 1 1 0 0 0 0 0
0 1 1 1 1 1 1 1 1 0
0 1 1 1 1 1 1 1 1 0
0 0 0 0 0 1 1 1 1 0
0 0 0 0 0 0 0 0 0 0

(exemple hein)

pour obtenir le contour,tu peux realiser une "erosion" de cet objet par le pattern suivant :
0 1 0
1 1 1
0 1 0

cela signifie que tu vas "creuser" autout de l'objet. je dirai plus tard ce qu'est une erosion. l'image resultante sera :

0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 1 1 1 0 0 0 0 0
0 0 0 0 0 1 1 1 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0

ensuite tu peux soustraire l'image 2 de l'image 1, tu obtiendras :

0 0 0 0 0 0 0 0 0 0
0 1 1 1 1 0 0 0 0 0
0 1 0 0 0 1 1 1 1 0
0 1 1 1 1 0 0 0 1 0
0 0 0 0 0 1 1 1 1 0
0 0 0 0 0 0 0 0 0 0

tu vois que tu as pu obtenir le contour de l'objet en retirant l'interieur.

ensuite si tu souhaites obtenir l'interieur, part du premier point que tu trouves (donc ici le point de coordonnees 1,1)
et applique l'algo suivant :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
 
construireContour(first)
{
  Point next = first
  repeat
  {
    liste <- [next]
    dejavu <- [next]
    si (point au dessus de next fait partie du contour et pas encore vu)
      next <- point au dessus de next
    sinon si point au dessus a droite de next  fait partie du contour et pas encore vu)
      next <- ce point
    sinon si ... (parcours les points autour de next dans le sens des aiguilles d'une montre)
    sinon si point au dessus a gauche de next  fait partie du contour et pas encore vu)
      next <- ce point
    sinon c'est une ile de 1 point
  } tant que (next != first)

j'ai ete volontairement vite car je ne suis pas sur d'avoir cerné ton probleme.

[ToTo13]

Bonjour,

il y a plus simple qu'une érosion pour obtenir le contour.
Il suffit de vérifier pour chaque pixel plein de régarder s'il a au moins un voisin vide.

[screetch]

je ne sais pas si il faut obtenir le contour ou bien lister les points du contour d'un objet, l'algorithme que je presente n'a pas besoin de travailler sur une image qui represente uniquement le contour (ca peut etre l'objet entier).

pour l'erosion, je ne vois pas la difference entre faire l'erosion et la soustraction en une passe et ta methode, c'est la meme chose. j'ai mis des noms sur une methode, a priori, rien de plus.

[ToTo13]

Bonjour,

pour l'erosion, je ne vois pas la difference entre faire l'erosion et la soustraction en une passe et ta methode, c'est la meme chose. j'ai mis des noms sur une methode, a priori, rien de plus.

Pour l'érosion tu dois regarder tout l'élement structurant, soit un huit voisinage, dans la mienne tu t'intéresses directement aux pixels souhaités, mais la différence n'est pas énorme.
Ce qui change surtout c'est de ne pas avoir à faire la soustraction.

[screetch]

oui je vois ce que tu veux dire. mais je prefere souvent implementer des operations avec des operateurs standards au lieu de coder un nouveau balayage de l'image.

[grob1212]

peut-être le codage de freeman pourra vous aider ?

[AlphaJ]

Je vous remercie