# Gnral Dveloppement > Algorithme & Mathmatiques > Traitement d'images >  Meilleur algo de dtection d'objet

## Colloc

Bonjour,

J'ai tent de chercher les meilleurs mthodes permettant de retrouver une pice (une forme donne ex : roue dent, axe, autres pices mcanique, came etc...) dans une image (aprs identification de l'original) permettant d'en dterminer le nombre et leur position (X, Y et rotation) prsent  l'image.

J'ai pu trouv des mthodes comme SURF, HAAR TRAINING, etc...

L'ide est de faire  peu prs comme les solutions industrielles COGNEX avec leur algo propritaire Patmax et ne ncessitant pas de ralisation de "base de donnes" comme le haar car les objets sont trs varis.

Pouvez-vous me prconiser les meilleurs algos pour a ou des endroits o trouver ces infos ?

----------


## ToTo13

Bonjour,

il n'y a malheureusement pas de meilleure mthode.
Il y a des bonnes mthodes, mais leur performance dpend de ce qu'elles doivent raliser.
Je crains donc qu'il faille que tu utilises une mthode par type de pice  trouver.

----------


## pseudocode

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

----------


## Colloc

> Patmax fait du "Geometric Pattern Matching". Il faudrait regarder sur internet en utilisant ces mot cls.



J'ai recherch sur le net,  part le matchtemplate d'opencv qui semble peu performant (ne marche pas si la pice est tourne me semble t'il), je n'ai pas trouv d'algo sur le net...

----------


## Flo.

Salut,

j'ai test 2 mthodes principalement :
*
Les Descripteurs de Fourier :* 
tu rcupres le contour d'une imagetu en dduis une signature par tangente (il existe galement une signature par rayon mais on lui prfre la signature par tangente).tu dcomposes cette signature en une srie de Fourier.tu compares les N premires harmoniques du motif appris aux N premires du motif  analyser
La mthode est invariante en translation, niveaux de gris, rotation et en changement d'chelle. Par contre, la mthode ncessite de travailler sur des contours ferms, cela ncessite de travailler sur des objets segmentables au moins localement. En bref, la mthode est intressante, fonctionnelle, robuste, etc mais c'est pas encore le PatMax
*
Image apprise:*

*
Image analyse:*


*La transforme de Hough Gnralise*
tu rcupres le contour d'une imagedans une phase d'apprentissage, tu cres un dictionnaire ou tu associes un couple (rho, thta)  un angle (alpha). (Je ne m'tends pas pour l'instant sur les significations de ces 3 donnes).dans la phase de reconnaissance tu utilises ce dictionnaire pour identifier une forme
La mthode est invariante en translation, niveaux de gris, rotation et en changement d'chelle. Elle est extrmement performante en termes de reconnaissance (similaire  des rsultats PatMax). Elle peut dtecter des formes aux 2/3 cachs (cf. l'exemple). Elle ne ncessite pas de travailler sur des images segmentables ou sur des contours ferms. Par contre elle est trs gourmande en temps de calcul ; a peut aller jusqu' quelques minutes. J'essaie actuellement de l'amliorer en passant par des pyramides d'images.

*Image apprise:*

*
Image analyse:*


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 socit Matrox a dj fait les frais d'un procs intent par Cognex  ce sujet. Le secret est bien protg et peu communiqu ( ce sujet, il semble que le PatMax ramne tous les contours  des primitives (cercles, droites, segments, carr, etc.) et que tout y est ralis en vectoriel. C'est un sujet certes intressant mais qui ncessite d'y consacrer normment de temps.

Flo.

----------


## pseudocode

> Par contre elle est trs gourmande en temps de calcul ; a peut aller jusqu' quelques minutes. J'essaie actuellement de l'amliorer en passant par des pyramides d'images.


Tu peux aussi essayer de faire une premire passe en calculant la GHT seulement aux points d'intrts de l'image/motif. Ca te donne une premire estimation des zones candidates.

----------


## Flo.

Style des points d'intrt rcuprs via un dtecteur 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 mthode.

Je fais dj la GHT uniquement sur les points des contours dtects par le dtecteur de Canny. Cette mthode 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 hystrsis).

En terme de temps CPU, la recherche d'un motif 128x136 dans l'image des billets (824x430) en considrant 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 arrt car a n'est pas la solution mme si au final il faudra le faire).

Maintenant si je ne considre aucune tolrance 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 considrer que les 2.5 secondes ( peu prs incompressibles quelque soit les valeurs de seuil pour Canny) viennent d'un calcul du gradient de Sobel non optimis (sqrt et atan en excs). Pour l'instant a n'est pas mon problme. 

La bonne mthode, je pense, c'est de chercher le motif dans une image de rsolution le 1/4 ou le 1/16 de l'image originale puis effectivement, comme tu dis, revenir  l'image de rsolution suprieure en ne considrant que les zones pr-localises.

Flo.

----------


## pseudocode

> Style des points d'intrt rcuprs via un dtecteur 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 mthode.


Arf, j'ai t un peu extrme dans mon explication. Bien sur, il ne faut pas appliquer la GHT seulement sur LE point d'intrt, mais sur les points du contour (canny) aux environs de ce point.  :;): 

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

Pour une premire passe, cela limite les calculs de GHT sur des petites portions de contour (gnralement celles qui ont une forte courbure).

----------


## Flo.

Oui effectivement, cette formulation est meilleure... J'aurais du interprter la premire avec plus d'imagination aussi je suppose  :;): 

Donc avec ta deuxime 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'intrt serait relativement important.

Par ailleurs on doit pouvoir trouver des formes ne prsentant que trs peu de points d'intrt (un cercle ou toutes formes prsentant un contour sans aucune discontinuit).

De manire gnrale je pense que cette mthode prsume trop de la probabilit que le motif a de prsenter suffisamment de points d'intrt. 

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

Voil le rsultat de la recherche de motif sur l'image rduit au 1/16 (16 fois de pixels) de l'image originale dont est issue l'image de mon prcdent 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 reprsente un champs plus important. Ca pourrait tre un PatQuick  ::D: . 

On peut galement me rtorquer que je prsume trop de la bonne prservation des contours de mon motif aprs une rduction aussi importante.

Flo.

----------


## pseudocode

> Donc avec ta deuxime 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 dbarrasser des points parasites.




> Je ne connais pas bien ces outils l mais je pense que le nombre de points d'intrt serait relativement important.
> 
> Par ailleurs on doit pouvoir trouver des formes ne prsentant que trs peu de points d'intrt (un cercle ou toutes formes prsentant un contour sans aucune discontinuit).


Il faut choisir les points d'intrts en fonction de ton motif. Pour ton exemple, un dtecteur de coins (harris/sift) n'aiderait pas vraiment. Il faut construire un dtecteur qui tienne compte des caractristiques 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 faons une trs bonne pratique. Grer des images de 4000x4000 est toujours un problme quel que soit l'algorithme  ::D: . 

Il faut juste esprer que la miniaturisation ne va pas faire "disparaitre" des motifs lors de la dtection. Grer les faux-positifs est assez facile, mais rcuprer les motifs manqus, c'est plus coton.

----------


## Colloc

J'ai implant le GHT, cependant, je ne trouve pas les rsultats terribles.

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

Aprs 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.

Aprs, je test tous les contours de l'image cible.

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

Comment optimiser ? Comment calculer beta (l je fais btement un atan2 avec les points avant et aprs du point d'intrt du contour (avec une largeur donne entre avant et aprs) ?

----------


## Colloc

Personne pour m'aider ?

----------


## pseudocode

> Comment optimiser ? Comment calculer beta (l je fais btement un atan2 avec les points avant et aprs du point d'intrt du contour (avec une largeur donne entre avant et aprs) ?


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 discrtisation.

----------


## 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 discrtisation.


Je calcul dj avec une largeur de plus d'un pixel de chaque ct, mais sur une largeur paramtrable, cependant, cela n'amliore rien.

Les scores sont trs faibles rapidement sur des pices similaires !

Flo, comment as-tu fait ?

----------


## Flo.

Salut,

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

Sois plus prcis et plus patient. Ton "bta" il reprsente quoi ?




> l je fais btement un atan2 avec les points avant et aprs du point d'intrt du contour (avec une largeur donne entre avant et aprs)


Ca ne veut pas dire grand chose.

Bon comme j'aime pas rpondre par des questions je vais supposer que ton problme 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 gnie de la mthode. Tu as ralis ta R-Table. Tu cherches les motifs dans l'image orients  + ou - 5 degrs 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 rfrence pour l'accumulation d'un vote. Si tu gres plus ou moins 5 degrs il te suffit d'accumuler galement pour les couples (rho, thta) 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 rponse ?

Flo.

----------


## Colloc

> Salut,
> 
> Je comprends pas trs bien la question et ton histoire de largeur de pixel et tout le reste.
> 
> Sois plus prcis et plus patient. Ton "bta" il reprsente quoi ?
> 
> Ca ne veut pas dire grand chose.
> 
> Bon comme j'aime pas rpondre par des questions je vais supposer que ton problme porte sur la gestion de l'angle lors de la recherche du motif.
> ...


Merci de ta rponse !

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 aprs le point du contour que je traite (le contour tant une chaine de pixel). Les pixels prcdents et suivant forme donc la tangente au point (ou 2 pixels avant et aprs ou 3 ou n, etc...). J'en dduis l'angle de la normal (+pi/2).

Cependant, j'ai un pb pour la reconnaissance des autres pdts prsents sur l'image qui sont identique  la forme apprise et qui a permis de gnrer la RTable. En effet, il ne permettent pas un score de vote trs lev car l'angle que forme la normal n'est pas toujours identique au modle ( la rotation prs demand) dans une zone identique du pdt.

Donc, toi, qu'utilise tu comme mthode pour calculer cet angle (que tu nommes chez toi alpha, moi beta  ::D:  )?

----------


## Colloc

Ay, j'ai russi.

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

Je l'avais utilis au dbut mais je 'arrivais pas  rcuprer les donnes de l'image gradient.

J'ai finalement russi (pnible les cast en C !!!).

----------


## Flo.

Oui effectivement. Pour de telles oprations il faut absolument matriser l'criture du gradient d'une image par Sobel. Attention aux fonctions atan et atan2. Il faut souvent se faire sa propre fonction base sur le atan classique.

Par ailleurs il faut galement matriser un algo d'extraction de contours comme celui de Canny.

De mme, 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 trs 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 opration d'amincissement par masque itratif. C'est important sinon tu ne matriseras 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 rsultats.

Flo.

----------


## Colloc

> Oui effectivement. Pour de telles oprations il faut absolument matriser l'criture du gradient d'une image par Sobel. Attention aux fonctions atan et atan2. Il faut souvent se faire sa propre fonction base sur le atan classique.
> 
> Par ailleurs il faut galement matriser un algo d'extraction de contours comme celui de Canny.
> 
> De mme, 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 trs 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 opration d'amincissement par masque itratif. C'est important sinon tu ne matriseras 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.
> ...


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 trs 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 vrifier effectivement car la repre XY d'OpenCV n'est pas direct !

Je posterais qd j'aurais plus test sur d'autres images, une fois que nous aurons rcuprer nos camras !

----------


## nabikov

salut,
Salut,

je suis entraine de faire une tude sur la detection des objet en utilisant la transforme de Hough Gnralise.


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

merci infiniment.




> Salut,
> 
> j'ai test 2 mthodes principalement :
> *
> Les Descripteurs de Fourier :* 
> tu rcupres le contour d'une imagetu en dduis une signature par tangente (il existe galement une signature par rayon mais on lui prfre la signature par tangente).tu dcomposes cette signature en une srie de Fourier.tu compares les N premires harmoniques du motif appris aux N premires du motif  analyser
> La mthode est invariante en translation, niveaux de gris, rotation et en changement d'chelle. Par contre, la mthode ncessite de travailler sur des contours ferms, cela ncessite de travailler sur des objets segmentables au moins localement. En bref, la mthode est intressante, fonctionnelle, robuste, etc mais c'est pas encore le PatMax
> *
> Image apprise:*
> ...

----------


## sannounna

salut, 

je suis entrain d'appliquer le descripteur de Fourier mais il m'a donn des taux de reconnaissance trs faible (25%) daprs la thorie c'est peu.

Voici mon code(matlab) s'ils vout plait j'ai besoin de vos aide . je veux savoir d'ou vient le problme et MERCI. 



```

```

----------

