Clustering de points dans une image

Bonjour à tous,

Dans le cadre de mon projet de diplome, je dois fais de la détection d'obstacles à partir d'images filmées depuis une caméra placée sur une chaise roulante a moteur en environnement intérieur et immobile.

Pour ce faire, j'utilise opencv et le flux optique. Puis je clusterise les points détectés pour en faire des objets potentiels. Maintenant, je ne sais le faire qu'avec un nombre de clusters fixé en dur, vu que je ne sais pas à l'avance combien il devrait y avoir d'objets dans mes images...

J'aurais donc aimé savoir comment décider de manière dynamique le nombre de clusters à former, même si je ne sais pas si c'est possible...

Par ailleurs pour faire en sorte que les clusters formés soient cohérents d'une image à l'autre, est il possible de définir les graines (seeds) des clusters de la prochaine image à partir du centre des clusters détectés dans l'image précedente?

Merci pour votre aide

je bosse aussi sur quelque chose d'equivalent , mais dans mon cadre d'etude sa concerne la mise en correspendance et la carte de disparité

il est prévu ds mon projet de faire du clusuring a l'aide des reseaux de neurones , mais j'en ss au tout début ds cette partie dc......

je vais chercher plus ds ça et je posterai du nouveau la prochaines fois , sinon si quelqu'un a de la bonne Doc ds ça sa m'interesse tjr

merci

En cherchant un peu, j'ai fini par tomber sur un algorithme de clustering qui s'appelle le mean shift. Cet algo a l'avantage de n'avoir pas besoin de connaitre le nombre de clusters à former et n'est pas "contraignant sur leur forme" (même si je ne suis pas sur d'avoir compris ce que ca signifie... :? ).

Bien sur, ca serait pas marrant si c'était aussi simple :D Le problème est que j'ai essentiellement trouvé des papiers très "mathématiques", mais apperement il correspond assez bien à ce que je cherche. Ses défauts (par rapport à ce que j'ai compris bien entendu) sont qu'il devient vite lourd au delà d'un certain nombre de dimensions et le pire de tout, il ne se trouve apperement déjà codé, pré-maché et optimisé dans OpenCV :P

Pour ceux que ca interesse, il y a là un article plutot bien expliqué et une implementation en Java (c'est mieux que le reste que j'ai trouvé, tjrs en Matlab ^^).

Enfin bref, je vais tenter ca, selon le résultat et si ca interesse qqun, je vous tient au courrant

2 remarques. Pour débuter dans le clustering, regarde peut être du côté des k-means ; tu obtiendra facilement un premier set de résultats

Ensuite, poru implémenter le meanshift (j'avais cru le voir implémenté quelque part dans opencv mais j'ai du rever) tu peux suivre ce papier relativement bien expliqué et réecrire ton implémentation. Sinon le choix de meanshift est sans doute adapté a tes objectifs, après les résultats vont beaucoup dépendre du type de scènes observées.

Salut et merci pour ta réponse,

Alors pour ce qui est du k-mean, c'est par ca que j'ai commencé (étant donné que c'est celui que j'avais appris en cours de proba :D ), mais le résultat n'est pas vraiment satisfaisant, vu que je ne peux pas définir par avance combien de clusters je souhaite avoir d'avance...

Sinon, pour ce qui est du document sur le mean shift, le code est clair, son fonctionnement aussi, c'est au sujet des données en entrée que j'ai de la peine. L'exemple parle ici de débruitage d'une image et se base donc sur un histogramme RVB (tableau 3D) de l'image et lance le mean shift sur chacun des points pour récuperer le centre du cluster auquel il appartient, ce qui donne la nouvelle couleur du point.

Mais dans mon cas, c'est différent et je ne comprends pas comment l'adapter. J'ai un tableau uni dimensionnel contenant les coordonnées des points que je veux clusteriser. Donc si j'ai plus ou moins compris, voila ce que je dois faire :
- Créer un tableau bi-dimensionnel de la taille de mon image et y disposer mes points détectés, de manière à ce que la valeur d'un élément [x][y] soit de 1 si il y a un point dessus et de 0 dans le cas contraire
- Pour chacun de mes points, appliquer le mean shift, ce qui va me donner un nouveau centroid, qui représente le centre du cluster dans lequel il va aller

Est-ce que je suis un peu juste ou alors je patauge méchamment?

Extrait de la doc open cv
Pas le temps de em pencher sur la question tout de suite ;)

Citation:

---

MeanShift
Iterates to find object center.
int cvMeanShift( IplImage* imgProb, CvRect windowIn, CvTermCriteria
criteria, CvConnectedComp* out );
2D object probability distribution.
imgProb
Initial search window.
windowIn
Criteria applied to determine when the window search should be
criteria
finished.
Resultant structure that contains converged search window
out
coordinates (rect field) and sum of all pixels inside the window
(area field).
Discussion
The function MeanShift iterates to find the object center given its 2D color
probability distribution image. The iterations are made until the search window center
moves by less than the given value and/or until the function has done the maximum
number of iterations. The function returns the number of iterations made.

---

Gné? J'étais sur d'avoir cherché de fond en comble sans rien trouver >_<

Ben euh... Merci, je vais voir ca :D

Hello,

Comme les méchants dans les films, les problèmes ne meurent jamais du premier coup... Mais je ne m'avoue pas vaincu pour autant. :aie:

Alors j'ai regardé cette méthode cvMeanShift et je n'ai pas vraiment trouvé comment je pourrais l'utiliser dans le but que je recherche. Il est dit qu'elle permet, à partir de la back projection d'une image (l'image à laquelle ont ré-applique son histogramme après l'avoir equalisé) d'appliquer le mean shift sur une zone de recherche, afin récuperer les nouvelles coordonées de la fenêtre de recherche après convergence. (Je n'ai pas vraiment compris l'interet...)

Mais voila, je n'ai pas une image equalisée à lui donner en pature, mais une série de points, du coup je ne sais pas comment l'adapter à mes besoins...

Donc au final, j'ai codé ma propre version du mean shift, en me basant sur l'exemple donné plus haut... Et je crois que j'ai bien réussi à fournir son implémentation la plus approximative et la moins efficace qu'on ai vue depuis longtemps... Ce qui me donne un temps de traitement près de 4 fois superieur à ce que j'avais en utilisant le k mean d'open cv (150ms par image contre 40ms). Je vais donc déjà essayer d'optimiser tout ca, mais si qqun comprends comment utiliser la version d'open cv du mean shift pour du clustering de points, je suis preneur...

En fait, il m'a suffit de quelques minutes de réflexion (et de 2-3h de débogage après, cela va de soi :D ) pour optimiser la chose. Dans la mesure où j'ai atteint des perfs tout à fait raisonnable, je vais m'en tenir la.

Si jamais qqun est interessé par le code, il suffit de me le demander.