Discussion :

[Colloc]

Bonjour,

J'ai tenté de chercher les meilleurs méthodes permettant de retrouver une pièce (une forme donnée ex : roue denté, axe, autres pièces mécanique, came etc...) dans une image (après identification de l'original) permettant d'en déterminer le nombre et leur position (X, Y et rotation) présent à l'image.

J'ai pu trouvé des méthodes comme SURF, HAAR TRAINING, etc...

L'idée est de faire à peu près comme les solutions industrielles COGNEX avec leur algo propriétaire Patmax et ne nécessitant pas de réalisation de "base de données" comme le haar car les objets sont très variés.

Pouvez-vous me préconiser les meilleurs algos pour ça ou des endroits où trouver ces infos ?

[ToTo13]

Bonjour,

il n'y a malheureusement pas de meilleure méthode.
Il y a des bonnes méthodes, mais leur performance dépend de ce qu'elles doivent réaliser.
Je crains donc qu'il faille que tu utilises une méthode par type de pièce à trouver.

[pseudocode]

Patmax fait du "Geometric Pattern Matching". Il faudrait regarder sur internet en utilisant ces mot clés.

[Colloc]

Patmax fait du "Geometric Pattern Matching". Il faudrait regarder sur internet en utilisant ces mot clés.

J'ai recherché sur le net, à part le matchtemplate d'opencv qui semble peu performant (ne marche pas si la pièce est tournée me semble t'il), je n'ai pas trouvé d'algo sur le net...

[Flo.]

Salut,

j'ai testé 2 méthodes principalement :

Les Descripteurs de Fourier :

• tu récupères le contour d'une image
• tu en déduis une signature par tangente (il existe également une signature par rayon mais on lui préfère la signature par tangente).
• tu décomposes cette signature en une série de Fourier.
• tu compares les N premières harmoniques du motif appris aux N premières du motif à analyser

La méthode est invariante en translation, niveaux de gris, rotation et en changement d'échelle. Par contre, la méthode nécessite de travailler sur des contours fermés, cela nécessite de travailler sur des objets segmentables au moins localement. En bref, la méthode est intéressante, fonctionnelle, robuste, etc mais c'est pas encore le PatMax

Image apprise:


Image analysée:


La transformée de Hough Généralisée

• tu récupères le contour d'une image
• dans une phase d'apprentissage, tu crées un dictionnaire ou tu associes un couple (rho, thêta) à un angle (alpha). (Je ne m'étends pas pour l'instant sur les significations de ces 3 données).
• dans la phase de reconnaissance tu utilises ce dictionnaire pour identifier une forme

La méthode est invariante en translation, niveaux de gris, rotation et en changement d'échelle. Elle est extrêmement performante en termes de reconnaissance (similaire à des résultats PatMax). Elle peut détecter des formes aux 2/3 cachés (cf. l'exemple). Elle ne nécessite pas de travailler sur des images segmentables ou sur des contours fermés. Par contre elle est très gourmande en temps de calcul ; ça peut aller jusqu'à quelques minutes. J'essaie actuellement de l'améliorer en passant par des pyramides d'images.

Image apprise:


Image analysée:


Dans tous les cas, faut se dire que le PatMax de Bill Silver (co-fondateur de Cognex je crois) est breveté dans tous les sens. La société Matrox a déjà fait les frais d'un procès intenté par Cognex à ce sujet. Le secret est bien protégé et peu communiqué (à ce sujet, il semble que le PatMax ramène tous les contours à des primitives (cercles, droites, segments, carré, etc.) et que tout y est réalisé en vectoriel. C'est un sujet certes intéressant mais qui nécessite d'y consacrer énormément de temps.

Flo.

[pseudocode]

Par contre elle est très gourmande en temps de calcul ; ça peut aller jusqu'à quelques minutes. J'essaie actuellement de l'améliorer en passant par des pyramides d'images.

Tu peux aussi essayer de faire une première passe en calculant la GHT seulement aux points d'intérêts de l'image/motif. Ca te donne une première estimation des zones candidates.

[Flo.]

Style des points d'intérêt récupérés via un détecteur de coins de Harry ou des descripteurs SIFT ? Non je ne pense pas. Je vois bien que tu penses à diminuer le nombre de points sur lesquels on applique la GHT mais ça n'est pas la bonne méthode.

Je fais déjà la GHT uniquement sur les points des contours détectés par le détecteur de Canny. Cette méthode me permet de faire un apprentissage et une reconnaissance sur un nombre de points restreint ou au contraire important (en jouant sur le seuillage par hystérésis).

En terme de temps CPU, la recherche d'un motif 128x136 dans l'image des billets (824x430) en considérant aucune variation en échelle et une variation angulaire de + ou - 140° me prend approximativement 80 secondes (Intel Core2Duo T5270 - 1.4GHz - 3Gb DDR2). (A noter que j'avais commencé à coder certaines parties en XMMX mais j'ai arrêté car ça n'est pas la solution même si au final il faudra le faire).

Maintenant si je ne considère aucune tolérance angulaire, je tombe à environs 2.5 secondes. Bien sur je ne trouve plus que 2 motifs dans l'image (le motif caché le plus haut et le motif le plus bas et le plus complet orienté 0°).

On peut considérer que les 2.5 secondes (à peu près incompressibles quelque soit les valeurs de seuil pour Canny) viennent d'un calcul du gradient de Sobel non optimisé (sqrt et atan en excès). Pour l'instant ça n'est pas mon problème.

La bonne méthode, je pense, c'est de chercher le motif dans une image de résolution le 1/4 ou le 1/16 de l'image originale puis effectivement, comme tu dis, revenir à l'image de résolution supérieure en ne considérant que les zones pré-localisées.

Flo.

[pseudocode]

Style des points d'intérêt récupérés via un détecteur de coins de Harry ou des descripteurs SIFT ? Non je ne pense pas. Je vois bien que tu penses à diminuer le nombre de points sur lesquels on applique la GHT mais ça n'est pas la bonne méthode.

Arf, j'ai été un peu extrême dans mon explication. Bien sur, il ne faut pas appliquer la GHT seulement sur LE point d'intérêt, mais sur les points du contour (canny) aux environs de ce point.

1. calcul du contour
2. calcul des points d'intérêts (proches du contour)
3. calcul des zones d'intérêts = box autour des points d'intérêts
4. calcul de la GHT sur les points du contour qui sont dans les zones d'intérêts

Pour une première passe, cela limite les calculs de GHT sur des petites portions de contour (généralement celles qui ont une forte courbure).

[Flo.]

Oui effectivement, cette formulation est meilleure... J'aurais du interpréter la première avec plus d'imagination aussi je suppose

Donc avec ta deuxième formulation et un peu plus d'imagination, je pense que effectivement ça devrait optimiser les calculs. Mais peut-être pas autant que ça.

Si on regarde l'image des contours, on voit qu'elle est relativement complexe



Je ne connais pas bien ces outils là mais je pense que le nombre de points d'intérêt serait relativement important.

Par ailleurs on doit pouvoir trouver des formes ne présentant que très peu de points d'intérêt (un cercle ou toutes formes présentant un contour sans aucune discontinuité).

De manière générale je pense que cette méthode présume trop de la probabilité que le motif a de présenter suffisamment de points d'intérêt.

Je reste sur ma position. Passer par une pyramide d'image :

Voilà le résultat de la recherche de motif sur l'image réduit au 1/16 (16 fois de pixels) de l'image originale dont est issue l'image de mon précédent message. Le temps de calcul est de 4 secondes pour une variation angulaire de + ou - 140°.



On voit qu'on a trouvé pas mal de motifs plus quelques faux motifs. On est passé de 4 secondes à 80 secondes alors que la petite image représente un champs plus important. Ca pourrait être un PatQuick .

On peut également me rétorquer que je présume trop de la bonne préservation des contours de mon motif après une réduction aussi importante.

Flo.

[pseudocode]

Donc avec ta deuxième formulation et un peu plus d'imagination, je pense que effectivement ça devrait optimiser les calculs. Mais peut-être pas autant que ça.

Si on regarde l'image des contours, on voit qu'elle est relativement complexe

bof... pas si complexe que cela. Peut-être un peu de pré/post filtrage permettrait de se débarrasser des points parasites.

Je ne connais pas bien ces outils là mais je pense que le nombre de points d'intérêt serait relativement important.

Par ailleurs on doit pouvoir trouver des formes ne présentant que très peu de points d'intérêt (un cercle ou toutes formes présentant un contour sans aucune discontinuité).

Il faut choisir les points d'intérêts en fonction de ton motif. Pour ton exemple, un détecteur de coins (harris/sift) n'aiderait pas vraiment. Il faut construire un détecteur qui tienne compte des caractéristiques de ton motif, ce qui n'est pas toujours évident/simple.

Je reste sur ma position. Passer par une pyramide d'image :

C'est de toutes façons une très bonne pratique. Gérer des images de 4000x4000 est toujours un problème quel que soit l'algorithme .

Il faut juste espérer que la miniaturisation ne va pas faire "disparaitre" des motifs lors de la détection. Gérer les faux-positifs est assez facile, mais récupérer les motifs manqués, c'est plus coton.

[Colloc]

J'ai implanté le GHT, cependant, je ne trouve pas les résultats terribles.

Je vais donc décrire ce que j'ai fait, si vous pouvze faire vos commentaires...

Après binarisation de l'image, je cherche les contours (avec la fonction cvFindContours....).
Puis je calcule l'angle de la normale à la tangente sur ces contours et enfin les alpha et d et construit ma R-Table.

Après, je test tous les contours de l'image cible.

Cela fonctionne bien sur des objets sans rotation. Dès que je les tourne, le "score" qu'elles obtiennent est faible.

Comment optimiser ? Comment calculer beta (là je fais bêtement un atan2 avec les points avant et après du point d'intérêt du contour (avec une largeur donnée entre avant et après) ?

[Colloc]

Personne pour m'aider ?

[pseudocode]

Comment optimiser ? Comment calculer beta (là je fais bêtement un atan2 avec les points avant et après du point d'intérêt du contour (avec une largeur donnée entre avant et après) ?

Il faut avoir une meilleure estimation de l'angle. Avec seulement 2 points, il va y avoir une marge d'erreur énorme due a la discrétisation.

[Colloc]

Il faut avoir une meilleure estimation de l'angle. Avec seulement 2 points, il va y avoir une marge d'erreur énorme due a la discrétisation.

Je calcul déjà avec une largeur de plus d'un pixel de chaque côté, mais sur une largeur paramétrable, cependant, cela n'améliore rien.

Les scores sont très faibles rapidement sur des pièces similaires !

Flo, comment as-tu fait ?

[Flo.]

Salut,

Je comprends pas très bien la question et ton histoire de largeur de pixel et tout le reste.

Sois plus précis et plus patient. Ton "béta" il représente quoi ?

là je fais bêtement un atan2 avec les points avant et après du point d'intérêt du contour (avec une largeur donnée entre avant et après)

Ca ne veut pas dire grand chose.

Bon comme j'aime pas répondre par des questions je vais supposer que ton problème porte sur la gestion de l'angle lors de la recherche du motif.

Et bien c'est relativement simple et c'est là de tout le génie de la méthode. Tu as réalisé ta R-Table. Tu cherches les motifs dans l'image orientés à + ou - 5 degrés par exemple.

Lors de la recherche de motifs, lorsque tu es sur un point contour, tu obtiens l'angle alpha formé par la normale au contour en ce point (ou la tangente au contour en ce point) et l'horizontale (axe Ox). Cet alpha est la clé qui te permet de trouver dans la R-Table le couple (rho, theta) qui te donne le point de référence pour l'accumulation d'un vote. Si tu gères plus ou moins 5 degrés il te suffit d'accumuler également pour les couples (rho, théta) correspondant à la clé (alpha - 5), (alpha - 4), (alpha - 3) et ainsi de suite jusqu'à (alpha + 4) et (alpha + 5).

Et c'est tout.

Ca te convient comme réponse ?

Flo.

[Colloc]

Salut,

Je comprends pas très bien la question et ton histoire de largeur de pixel et tout le reste.

Sois plus précis et plus patient. Ton "béta" il représente quoi ?

Ca ne veut pas dire grand chose.

Bon comme j'aime pas répondre par des questions je vais supposer que ton problème porte sur la gestion de l'angle lors de la recherche du motif.

Et bien c'est relativement simple et c'est là de tout le génie de la méthode. Tu as réalisé ta R-Table. Tu cherches les motifs dans l'image orientés à + ou - 5 degrés par exemple.

Lors de la recherche de motifs, lorsque tu es sur un point contour, tu obtiens l'angle alpha formé par la normale au contour en ce point (ou la tangente au contour en ce point) et l'horizontale (axe Ox). Cet alpha est la clé qui te permet de trouver dans la R-Table le couple (rho, theta) qui te donne le point de référence pour l'accumulation d'un vote. Si tu gères plus ou moins 5 degrés il te suffit d'accumuler également pour les couples (rho, théta) correspondant à la clé (alpha - 5), (alpha - 4), (alpha - 3) et ainsi de suite jusqu'à (alpha + 4) et (alpha + 5).

Et c'est tout.

Ca te convient comme réponse ?

Flo.

Merci de ta réponse !

Alors j'ai bien compris l'algo et j'ai construit la RTable.

Mais pour moi, le pb est le calcul de l'angle de la normal au contour avec l'axe X. Pour le calcul, j'utilise les pixels du contour identifié situé avant et après le point du contour que je traite (le contour étant une chaine de pixel). Les pixels précédents et suivant forme donc la tangente au point (ou 2 pixels avant et après ou 3 ou n, etc...). J'en déduis l'angle de la normal (+pi/2).

Cependant, j'ai un pb pour la reconnaissance des autres pdts présents sur l'image qui sont identique à la forme apprise et qui a permis de générer la RTable. En effet, il ne permettent pas un score de vote très élevé car l'angle que forme la normal n'est pas toujours identique au modèle (à la rotation près demandé) dans une zone identique du pdt.

Donc, toi, qu'utilise tu comme méthode pour calculer cet angle (que tu nommes chez toi alpha, moi beta )?

[Colloc]

Ayé, j'ai réussi.

Pour le calcul de l'angle, j'utilise les gradients.

Je l'avais utilisé au début mais je 'arrivais pas à récupérer les données de l'image gradient.

J'ai finalement réussi (pénible les cast en C !!!).

[Flo.]

Oui effectivement. Pour de telles opérations il faut absolument maîtriser l'écriture du gradient d'une image par Sobel. Attention aux fonctions atan et atan2. Il faut souvent se faire sa propre fonction basée sur le atan classique.

Par ailleurs il faut également maîtriser un algo d'extraction de contours comme celui de Canny.

De même, je te conseille, pour l'extraction des maximas dans l'espace de Hough, de ne pas utiliser des segmentations classiques. Tu peux aller faire un tour sur ImageJ et sa fonction "recherche de maximas locaux" (ou truc du style).

Ce sont des fonctions qui ont l'air très facile mais qui demandent beaucoup de rigueur pour être efficaces et robustes. Par exemple, obtenir un contour d'épaisseur 1 pixel par Canny n'est pas possible. Il faut rajouter une opération d'amincissement par masque itératif. C'est important sinon tu ne maîtriseras pas l'amplitude de tes accumulations.

Enfin bref de la rigueur, beaucoup de rigueur pour que les algos ne soient pas des trucs écris vite fait mal fait.

Au passage, ça serait sympa de pouvoir voir tes résultats.

Flo.

[Colloc]

Oui effectivement. Pour de telles opérations il faut absolument maîtriser l'écriture du gradient d'une image par Sobel. Attention aux fonctions atan et atan2. Il faut souvent se faire sa propre fonction basée sur le atan classique.

Par ailleurs il faut également maîtriser un algo d'extraction de contours comme celui de Canny.

De même, je te conseille, pour l'extraction des maximas dans l'espace de Hough, de ne pas utiliser des segmentations classiques. Tu peux aller faire un tour sur ImageJ et sa fonction "recherche de maximas locaux" (ou truc du style).

Ce sont des fonctions qui ont l'air très facile mais qui demandent beaucoup de rigueur pour être efficaces et robustes. Par exemple, obtenir un contour d'épaisseur 1 pixel par Canny n'est pas possible. Il faut rajouter une opération d'amincissement par masque itératif. C'est important sinon tu ne maîtriseras pas l'amplitude de tes accumulations.

Enfin bref de la rigueur, beaucoup de rigueur pour que les algos ne soient pas des trucs écris vite fait mal fait.

Au passage, ça serait sympa de pouvoir voir tes résultats.

Flo.

Pour la recherche de contour, j'utilise les fonctions toutes faites de OpenCV qui ont l'avantage d'être efficace et de respecter Freeman (pas de pb d'épaisseur).

Pour le max local, j'utilise aussi les fonctions d'OpenCV qui fonctionnent ttes très bien et sont rapides !

Pour faire une recherche sur une amplitude 90° par pas de 1°, je mets 1 à 2 s sur une image de 1600*1200. (Il faut aussi dire que les images sont propres !).

Pour les pb d'atan, il faut bien vérifier effectivement car la repère XY d'OpenCV n'est pas direct !

Je posterais qd j'aurais plus testé sur d'autres images, une fois que nous aurons récupérer nos caméras !

[nabikov]

salut,
Salut,

je suis entraine de faire une étude sur la detection des objet en utilisant la transformée de Hough Généralisée.


je cherche une implementation de cette algo sous matlabe ou sous c++ (biblioteque open cv).

merci infiniment.

Salut,

j'ai testé 2 méthodes principalement :

Les Descripteurs de Fourier :

• tu récupères le contour d'une image
• tu en déduis une signature par tangente (il existe également une signature par rayon mais on lui préfère la signature par tangente).
• tu décomposes cette signature en une série de Fourier.
• tu compares les N premières harmoniques du motif appris aux N premières du motif à analyser

La méthode est invariante en translation, niveaux de gris, rotation et en changement d'échelle. Par contre, la méthode nécessite de travailler sur des contours fermés, cela nécessite de travailler sur des objets segmentables au moins localement. En bref, la méthode est intéressante, fonctionnelle, robuste, etc mais c'est pas encore le PatMax

Image apprise:


Image analysée:


La transformée de Hough Généralisée

• tu récupères le contour d'une image
• dans une phase d'apprentissage, tu crées un dictionnaire ou tu associes un couple (rho, thêta) à un angle (alpha). (Je ne m'étends pas pour l'instant sur les significations de ces 3 données).
• dans la phase de reconnaissance tu utilises ce dictionnaire pour identifier une forme

La méthode est invariante en translation, niveaux de gris, rotation et en changement d'échelle. Elle est extrêmement performante en termes de reconnaissance (similaire à des résultats PatMax). Elle peut détecter des formes aux 2/3 cachés (cf. l'exemple). Elle ne nécessite pas de travailler sur des images segmentables ou sur des contours fermés. Par contre elle est très gourmande en temps de calcul ; ça peut aller jusqu'à quelques minutes. J'essaie actuellement de l'améliorer en passant par des pyramides d'images.

Image apprise:


Image analysée:


Dans tous les cas, faut se dire que le PatMax de Bill Silver (co-fondateur de Cognex je crois) est breveté dans tous les sens. La société Matrox a déjà fait les frais d'un procès intenté par Cognex à ce sujet. Le secret est bien protégé et peu communiqué (à ce sujet, il semble que le PatMax ramène tous les contours à des primitives (cercles, droites, segments, carré, etc.) et que tout y est réalisé en vectoriel. C'est un sujet certes intéressant mais qui nécessite d'y consacrer énormément de temps.

Flo.