Discussion :

[salihovic]

bonjour
j'ai un nuage de points résultant d'une analyse d'une image par le filtre de canny et une extraction des corners.
je veux découper mon ensemble de point selon un critère qui est la distance maximale entre les différents point qui peuvent appartir à un objet
par exemple je fixe une distance de 10pixel comme max pour les distances
je veux regrouper mes points selon des ensemble.y a t il quelcun ayant une idée ?

peut etre j'ai besoin d'un algorithme recursif qui a chaque point de départ cherche les proches vérifiant la condition de distance et on répète les itérations a chaque successeurs du premier jusqu'a arriver a terminer tous les points ou que la condition de distance n'est pas rempli pour tous les fils...
mais ici il y a un problème de complexité qui est trops grande:
on doit parcourire n*(n-1)*(n-2)... peut etre tout ça exposant n!!!

[pseudocode]

bonjour
j'ai un nuage de points résultant d'une analyse d'une image par le filtre de canny et une extraction des corners.
je veux découper mon ensemble de point selon un critère qui est la distance maximale entre les différents point qui peuvent appartir à un objet
par exemple je fixe une distance de 10pixel comme max pour les distances
je veux regrouper mes points selon des ensemble.y a t il quelcun ayant une idée ?

Un graph-cut sur la carte des distances.

Mais comme je suppose que ca a un rapport avec ton post sur la segmentation des cellules, je dirais que ce n'est pas la meilleur approche possible.

[souviron34]

j'ai déjà expliqué plusieurs fois l'algo nécessaire, qui est en 5*N+N*log(N) (en moyenne)..

• faire un tri (qsort) des points par X croissant, et à même X par Y croissant.
  
  
• partir du premier. Pour chaque point, explorer les autres (routine récursive).
  
  • si distance > dist max, alors on le marque comme appartenant à un autre cluster
  • si distance < dist max, on le marque comme appartenant à ce cluster, et on part de lui.
  
  

Normalement, la phase 2 devrait être en N*N, mais le faire d'avoir classer les points avec le qsort ramène en moyenne à 5*N..

[salihovic]

oui ce post a une relation avec l'autre mais c'est une piste que j'essaie d'explorer je vai essayer de détecter les ellipses ou les nuages de points à partir d'un ensemble de points déja extrait avec la bibliothèque Aforge.net avec la détection des corners en utilisant susan.j'obtient un ensemble de point je dois l'analysé et extraire les objets possibles.je vai rechercher en tt cas sur ce graph-cut peut etre j'aurais un résultat.
merci bien pour tes réponses

j'ai déjà expliqué plusieurs fois l'algo nécessaire, qui est en 5*N+N*log(N) (en moyenne)..

• faire un tri (qsort) des points par X croissant, et à même X par Y croissant.
  
  
• partir du premier. Pour chaque point, explorer les autres (routine récursive).
  
  • si distance > dist max, alors on le marque comme appartenant à un autre cluster
  • si distance < dist max, on le marque comme appartenant à ce cluster, et on part de lui.
  
  

Normalement, la phase 2 devrait être en N*N, mais le faire d'avoir classer les points avec le qsort ramène en moyenne à 5*N..

cette méthode est bonne je pense .
si la complexité n'est pas trops grande ça me convient.
deja ma liste est trié en Y et puis en X. je dois inverser???
j'ai a l'instant même pensé de déviser mes points en un ensemble de région selon la distance chaque distance représenté par un carré. mais peut etre cette methode que tu as dis est plus efficace.




j'ai réussi a détecter les objets avec la methode de corners et l'algorithme que m'a proposé souviron34
les resultats a partir d'un fichier sont si jointes...
je dois maitenant accumuler les points et reconstituer les ellipses...
j'ai lu qu'il y a des methodes pour présenter les ellipses le plus proche des points comme le moindre carré ...si quelcun peut me donner l'algorithme ou un lien pour une implémentation
RQ:j'ai testé plusieurs méthodes avant peut etre il faut réctifier l'entré des algorithme pour optimiser les résultats...
j'ai après cette étape une collection contenant des collections des points presentants les objets...(hashtable)
merci bien pour votres aides

[souviron34]

je dois maitenant accumuler les points et reconstituer les ellipses...
j'ai lu qu'il y a des methodes pour présenter les ellipses le plus proche des points comme le moindre carré ...si quelcun peut me donner l'algorithme ou un lien pour une implémentation

oui, la méthode est les moindres carrés.

je t'ai donné le lien sur le code dans l'autre post..

C'est très simple..

Une fois les points clusterisés, tu prends les clusters un par un, et tu appliques l'algo.

Cet algo est hyper-simple : développement de l'équation de l'ellipse

• Application pour chacun des pixels du cluster, avec stockage des X2, Y2, XY, etc
• Moindre carré général
• Déduction en sens inverse du centre, du petit et gand axe, et de l'orientation

Note : au vu de ton image, il faudrait néanmoins re-faire une analyse par cluster pour séparer les différentes ellipses..

[salihovic]

Note : au vu de ton image, il faudrait néanmoins re-faire une analyse par cluster pour séparer les différentes ellipses..

et comment on fait ça???
pour le code existant dans la page c'est en fortrant et je le comprend pas et j'ai pas une manière de le tester
si tu peut plus décrire l'algorithme pour que je l'implémente seul

[souviron34]

pour le code existant dans la page c'est en fortrant et je le comprend pas et j'ai pas une manière de le tester
si tu peut plus décrire l'algorithme pour que je l'implémente seul

je viens de te la donner, l'explication...

[ToTo13]

Bonjour,

regarde dans les articles présentés dans WSCG 2008. Il y en a un qui traite de la reconnaissances de formes (des primitives) dans un nuages de points 3D.
C'est ce que tu veux...

[pseudocode]

j'ai réussi a détecter les objets avec la methode de corners et l'algorithme que m'a proposé souviron34
les resultats a partir d'un fichier sont si jointes...

Hum... A la vue de l'image, je me demande si l'étape de detection des corners était vraiment indispensable.

[salihovic]

Hum... A la vue de l'image, je me demande si l'étape de detection des corners était vraiment indispensable.

bon je fait la détection des corners pour ensuite pouvoir répérer les objet et dessnier moi même j'ai pas précisé que ces points sont des objets que j'ai créé moi même et qui servent a identifier chaque cellule plus tard...

Bonjour,

regarde dans les articles présentés dans WSCG 2008. Il y en a un qui traite de la reconnaissances de formes (des primitives) dans un nuages de points 3D.
C'est ce que tu veux...

j'ai pas trouvé le lien si c'est possible merci de me le donner

[pseudocode]

bon je fait la détection des corners pour ensuite pouvoir répérer les objet et dessnier moi même j'ai pas précisé que ces points sont des objets que j'ai créé moi même et qui servent a identifier chaque cellule plus tard...

Je voulais juste dire que j'ai l'impression que tu as pratiquement 1 corner par pixel du contour. Donc tu aurais pu utiliser directement les pixels du contour.

[salihovic]

Je voulais juste dire que j'ai l'impression que tu as pratiquement 1 corner par pixel du contour. Donc tu aurais pu utiliser directement les pixels du contour.

oui mais le problème c'est de relire tous les pixels de l'image.en plus les corners ne sont pas trops rapproché il y a une distance...
peut etre l'exemple que j'ai pris n'est pas excellent je peut réduire le nombre de corners c'est paramétrable...
mon vrai problème maintenant c'est comment reconstituer des ellipses...
car j'ai mal a comprendre pourtant j'ai compris que la méthode de moindre carré sert a résoudre des equations compliqués et dans mon cas l'équation est ax^2+by^2+cxy+dx+ey+f=0...
le reste je le connais pas... pourtant j'ai une serie de points qui doivent vérifier cette eauation.
de toute façon je suis a la recherche du bon algorithme à implémenter .

[pseudocode]

mon vrai problème maintenant c'est comment reconstituer des ellipses...
car j'ai mal a comprendre pourtant j'ai compris que la méthode de moindre carré sert a résoudre des equations compliqués et dans mon cas l'équation est ax^2+by^2+cxy+dx+ey+f=0...
le reste je le connais pas... pourtant j'ai une serie de points qui doivent vérifier cette eauation.
de toute façon je suis a la recherche du bon algorithme à implémenter .

J'avais posté une implémentation Java il y a quelques temps (il y a meme un exemple d'utilisation pour une ellipse) :

http://www.developpez.net/forums/d37...emes-lineaires

Le problème c'est que ca ne marche que pour trouver UNE ellipse. Tes clusters contiennent plusieurs ellipses, donc ca ne va pas marcher. (a moins d'utiliser des techniques additionnelles comme RANSAC)

Il faut au préalable redécouper tes clusters pour n'avoir que des points qui appartiennent a une seule ellipse. Je réitère donc ma remarque de l'autre discussion : rechercher sur google "Ellipse Detection Based on Edge Grouping".

[salihovic]

j'ai pas pu trouvé une méthode pour détecter les ellipses en groupe
je vai premièrement éliminer les points internes dans les ellipses pour éclaircir l'image de plus,je pense que cette opération va couter trops car je parcourrais tous les points de la liste pour un abject et éliminé tous les points ayant a la foi des uppers et des lowers ...
pour la détection multiple des ellipse peut être après éclaircir mon image je vai découper en petite images contenant les objet et appliquer la méthode de pseudopode pour chercher dans chaque petite image l'ellipse la plus convenable.pour le reste je dois chercher plus pour améliorer mon traitement.
[EDIT]
peut etre je vai appliquer un algorithme de détection d'enveloppe convexe pour déterminer les points externes déjà j'ai une implémentation de la marche de jarvis

[salihovic]

j'ai fait le quickhull sur l'image
il me reste maintenant que bien détecter les ellipses...
peut être on doit rectifier l'image si on veut que la détection soit bien propre.
[EDIT]
j'ai ajouté la détermination du box dans le quel les objets existes(en rouge dans l'image)
je vai tester la détection des ellipses espérons bien que ça marche.mais peut etre j'ai besoin d'une aide concernant la détection des objets chevauchés

[salihovic]

j'ai un problème dans le dessin de l'ellipse après avoir déduit les points caractéristiques depuis la méthode de pseucode...
si j'ai le centre et le petit axe et le grand axe et l'angle comment je peut la dessiner???
je travaille en c# même s'il y a un code java c bien je peut le convertir
j'ai pas saisie comment le faire car donner le demi grand axe et le demi petit axe et le centre avec un angle ne fourni pas les argument nécessaires pour drawEllipse ... elle demande un rectangle ou une position et une size...
mon problème c'est si l'ellipse n'est pas symétrique... sa causerait des problèmes sinon je peut directement dessiner une ellipse dans le box que j'ai dessiné en rouge ...si quelqu'un a une idée merci de la passer..

[souviron34]

j'ai un problème dans le dessin de l'ellipse après avoir déduit les points caractéristiques depuis la méthode de pseucode...
si j'ai le centre et le petit axe et le grand axe et l'angle comment je peut la dessiner???

Euh...

x2/a2 + y2/b2 = 1

x = xpt - xc
y = ypt - yc

Donc pour i = 0 jusqu'à i = 2*PI (par exemple par pas de 1 degré (180/PI en radian))
petit calcul à effectuer

j'ai pas saisie comment le faire car donner le demi grand axe et le demi petit axe et le centre avec un angle ne fourni pas les argument nécessaires pour drawEllipse ... elle demande un rectangle ou une position et une size...

C'est normal, c'est comme ça que font tous les softs..

Une position et une size = 1 cercle (cas particulier d'une ellipse)
un rectangle : calcule le centre, et en fonction des rapprts d'axes trace.. l'angle et donc 1/2 grand-axe et 1/2 petit sont automatiquement déduits (avec un algo ressemblant à celui que j'ai utilsé pour le fit en Fortran indiqué).

mon problème c'est si l'ellipse n'est pas symétrique...

Une ellipse est forcément symétrique ... sinon ce n'est pas une ellipse...

[salihovic]

j'ai pu maintenant dessiner les ellipses mais c pas bien précis

est ce qu'il y a des algorithmes pour détecter les ellipses en groupes??
j'ai cherché "Ellipse Detection Based on Edge Grouping" mais j'ai pas réellement trouvé un algorithme...peut etre c'est compliqué.
aussi par la méthode de RANSAC proposé par pseudocode j'ai pas eu un exemple car il me faut un modèle et des paramètres..
est ce que le modèle dans mon cas est l'équation d'une ellipse???
si quelqu'un peut m'expliquer car j'ai pas compris et merci.

[pseudocode]

est ce qu'il y a des algorithmes pour détecter les ellipses en groupes??
j'ai cherché "Ellipse Detection Based on Edge Grouping" mais j'ai pas réellement trouvé un algorithme...peut etre c'est compliqué.
aussi par la méthode de RANSAC proposé par pseudocode j'ai pas eu un exemple car il me faut un modèle et des paramètres..
est ce que le modèle dans mon cas est l'équation d'une ellipse???
si quelqu'un peut m'expliquer car j'ai pas compris et merci.

Commençons simplement par un système de vote comme pour Hough.

- Pour chaque Cluster (supposons le composé de N points):

1. prendre K points au hasard dans le cluster (genre K ~ 10)
2. calculer les parametres de l'ellipse passant par ces K points
3. augmenter l'accumulateur de vote pour cette ellipse
4. Recommencer au point #1, plusieurs fois (genre N/10)
5. sélectionner les ellipses dont les accumulateur de vote dépasse un certain seuil.

[salihovic]

bonjour
la methode de detection d'ellipse que j'ai utulisé (elle est une conversion du code de l'exemple de pseudocode) ne marche pas dans tous les cas...
en plus le nombre de points nécessaire n'est pas fixe...
les résultats données ne sont pas toujours satisfaisant
[EDIT
il paret qu'il faut refaire la procédure de détection d'ellipse pour etre plus propre
en plus il faut trouver une autre approche pour minimiser les points de la frontière car avec la methode utilisé (quickhull) il y a perte de données à cause de la forme elliptique et le chevauchement des formes...il faut aussi minimiser le seuil pour savoir si un point appartient a l'iobjet ou pas.