Discussion :

[KirbX]

Bonjour tout le monde!
Je suis actuellement bloqué. Je suis en train d'implémenter l'algorithme SIFT (detection de points clefs dans une image afin de pouvoir faire du mtaching, de la reconstruction, ...) et j'ai fini la première étape qui est de créer les descripteurs (un descripteur est un point (x,y) de l'espace avec comme caracteristique particulière un vecteur de 128 élements (16*8, on se base sur le voisinage pour faire un descripteur précis).
J'en suis donc à l'étape de faire un arbre KD (comme Lowe conseil de le faire) pour trier les descripteurs et faire une recherche grâce à l'algorithme Best Bin First.
J'ai fais pas mal de recherche sur le net, mais je n'arrive pas à trouver de réponse à mes questions.
Un arbre KD en dimension 2, ça ressemble à un arbre binaire. En dimension 3, on sépare l'espace en X,Y et Z. Mais en dimension 128, ça se passe comment?
Quelqu'un l'à déjà fait et pourrait m'aider?
Merci d'avance pour votre aide!
Et bonne fin de journée!!

[velkouby]

Bonjour,

c'est bien de vouloir reprogrammer depuis le début des techniques déjà éprouvées, mais ne vas tu pas un peu loin en essayant de reprogrammer toi-même ton KDTree? Il en existe des très bien optimisés dans tous les langages. Sinon, que ce soit en 3D ou en nD, c'est le même algo avec le même fonctionnement : Tu divises ton espace en deux en bouclant sur chacune de tes dimentions

Regarde cette discussion : ici

Mais bon, je ne saurai que trop d'encourager à ne pas le faire toi-même et à utiliser une lib. Moi,j'utilise celui de Boost qui fonctionne bien (avec une réduction dimensionnelle de mes descripteurs en préalable(PCA, SVD, etc...): 20D suffisent généralement.

Bon courage.

[KirbX]

Merci de ta réponse, je vais jeter un coup d'oeil à la discussion!
Je suis d'accord sur le fait qu'il en existe déjà plein (et effectivement, j'ai pu en voir des tonnes, openCV, openSIFT, boost (comme tu l'as dis) et patati et patata)). Mais personnelement j'utilise openCV, et tout ce que j'ai déjà fait est déjà implémenté, mais ça marche moins bien que ce que j'ai fais (peut-être que justement, c'est parceque ça marche trop bien que ça marche moins bien, je sais pas vraiment), mais j'ai pas envie de changer ma façon de faire pour pouvoir utiliser le KD-tree d'openCV (on a pas la même structure de donnée à la base, et ducoup, modifier le tout m'attire pas vraiment ). Mais si jamais je n'y arrive vraiment pas, je vais peut-être devoir changer ma façon de penser !

Je pense avoir réussi à faire quelque chose de correct (ou dumoins, c'est en construction).
Si j'ai bien compris Lowe :
il faut couper a chaque fois en 2 selon la dimension qui a le plus de variance, puis on prends le médian, et on refait a gauche et à droite. C'est pas si compliqué que ça. Le problème qu'il me reste à résoudre c'est l'algorithme du Best Bin First, qui est plus ou moins expliqué nul part (Sur les 3 premieres pages gogoles, il n'y a rien en tout cas )

En tout cas, merci pour ta réponse
Bonne journée!