Discussion :

[pipo44]

Bonjour,
J'ai une idée d'algorithme en tête cependant j'aimerais bien avoir votre avis quand à sa fonctionnalité (ça marchera ou pas?)
Je souhaite reconnaître des cartes (images de 20*80 pixels) qui s'affiche sur mon écran à une position donnée.
Tout d'abord je constituerais une base de données des 52 cartes du jeu en relevant tous les 20*80 pixels de l'image grâce un GetPixel.
Ensuite une fois mis en fonctionnement mon programme relèvera 20*80 pixels de l'endroit ou sont les cartes (sur l'écran, on les prendra une par une (les cartes)) et les comparera à tour de rôles avec ceux de ma base de donnée (on compare d'abord avec l'as de pic puis l'as de coeur ...).
Par comparer j'entends : faire un GetPixel sur un point de l'image de l'écran, si sa valeur est identique au point de même coordonnées de la base de donnée alors j'incrémente un compteur de 1. Ensuite pour chaque carte je calcule le rapport point identique divisé par nombre point de l'image et je dis que ma carte de l'écran est celle ayant ce rapport le plus grand.

Mes questions sont :
Est ce que mes résultats seront cohérents sachant qu'il sera impossible de comparer exactement la même image que celle de la base de donnée (décalage de 1 ou 2 pixels possibles...)?
Ce décalage ne changera t il pas grand chose étant donné que mes cartes ne sont que de deux couleurs (rouge/noir et blanc)?
Comparer 20*80 pixels 104 (103, on ne peut pas avoir deux fois la même carte...) fois d'afillés (52*2), combien de temps cela va t il prendre?

Merci d'avance de votre attention

[Jeromnimo]

Bonjour,

en ce qui concerne les cartes que tu dois reconnaitre, elles sont identiques à celles que tu vas mettre dans ta base de données, ou bien est-ce seulement des cartes très ressemblantes ???
Vaste sujet que la reconnaissance de forme dans une base de données, il existe de nombreuses méthodes, plus ou moins complexe, mais cela dépend surtout du contexte d'utilisation...

[pipo44]

C'est exactement les mêmes, j'aurais fais des relevés au préalable pour constituer ma bdd

[Jeromnimo]

Dans ce cas, une méthode de parcours de tous les pixels t'assurera un résultat correct !
Tu travailles sur des pixels, donc peu importe où sont placées les cartes dans l'espace, il suffit d'itérer sur les pixels, en incrémentant sur les deux images...
Maintenant, pour accélérer la chose, tu peux introduire quelques "descripteurs" pour faire un tri préalable...
Par exemple, dans une zone définie en pixels, qui correspond à la zone ou se trouve le symbole (coeur, trefle...etc), si tu trouves du rouge, tu élimines toutes les cartes pique et trèfle, et si tu trouves du noir, tu élimines les coeur et les carreau, ca te permettra de diviser par 2 ton espace de recherche tout en explorant seulement quelques pixels...

[pipo44]

Le fait que mes cartes seront relevées "manuellement" et que du coup deux cartes identiques comparées ne donneront pas 100% de similarité ne pose pas de problème?

[Jeromnimo]

heuuuu j'ai du mal à saisir.. les cartes à comparer seront identiques ou non ? (pour chaque pixel, pixel_bdd(x,y) = pixel_carte(x,y) ???)
Un coup, tu dis oui

C'est exactement les mêmes, j'aurais fais des relevés au préalable pour constituer ma bdd

et un coup tu dis non

Le fait que mes cartes seront relevées "manuellement" et que du coup deux cartes identiques comparées ne donneront pas 100% de similarité ne pose pas de problème?

[Invité]

Ca marchera surement, vu que c'est l'algorithme classique de reconnaissance de formes
Je l'avais utilisé dans un projet de lectures de plaques minéralogiques. C'est vraiment pas la partie la plus compliquée, si tes images ont toutes la même taille et on été acquises bien à plat.
Quelques conseils :
- tu peux mettre plusieurs exemplaires (légèrement différents bien sûr) de chaque carte dans ta base de données. Surtout si tu veux être capable de reconnaître plusieurs des graphismes les plus utilisés :
http://his.nicolas.free.fr/Images/Je...xandre_WEB.jpg
http://trictrac.aquitain.free.fr/IMA.../pique_roi.gif
- Tu parlais de deux couleurs, rouge et noir, mais qu'est ce que tu fais des figures qui sont de plusieurs couleurs ? De toutes façons, passe tes images en niveau de gris, voire carrément en binaire avant de faire la comparaison, avec un seuil très bas, pour que seul le fond blanc de la carte soit à zéro. Il n'y a pas deux cartes qui ont la même forme et des couleurs différentes, donc l'info de la couleur est inutile. Tu peux t'en servir à la rigueur pour accélérer le traitement comme te l'as conseillé Jeronimo.

Comparer 20*80 pixels 104 (103, on ne peut pas avoir deux fois la même carte...) fois d'afillés (52*2), combien de temps cela va t il prendre ?

C'est pas 52*2, mais 52*52 ! Tu compares chaque carte avec toutes les autres possibles. Ca fait plus de 4 millions de comparaisons c'est pas la mort.
Je sais pas comment tu vois le truc, mais tu peux faire la récupération de tes pixels en C++, puis tu les mets dans une matrice de 20*80 booléens (puisque tu as une image binaire) et tu fais ton algo de comparaison en C pur. C'est pas la peine de travailler sur des objets image et de faire des GetPixel à chaque fois. GetPixel ne doit te servir qu'à remplir tes matrices au début.
Pareil pour ta base de données. Tu fais la binarisation de tes images échantillon une fois pour toute, et après tu sauves juste des fichiers de 0 et de 1.

[pipo44]

let me explain:
Les cartes qui s'affichent sur mon écran seront exactement les même que celles qui seront dans ma bdd.
Cependant lorsque tu prends deux photos d'une même scène tu auras deux résultats différents : il est impossible de centrer exactement pareil (il y aura toujours un décalage (à gauche à droite en haut ou en bas) ).
De la même façon que ce brave photographe j'ai essayé de faire de mon mieux pour avoir exactement les mêmes images et que le relevé à l'écran soit également identique mais je ne suis pas à l'abri d'un petit décalage de quelques pixel du fait que je placerais ma fenêtre à la main ... En gros je pense avoir une précision de 2 ou 3 pixels (grâce à la loupe Paint ...).
D'ou ma question précédente.

Merci de prêter attention à mon problème, n'hésite pas à me dire si mon explication n'est pas claire (j'essaierais d'improviser un autre exemple ;D)

[Jeromnimo]

Tu parlais de deux couleurs, rouge et noir, mais qu'est ce que tu fais des figures qui sont de plusieurs couleurs ?

heuuuu, on doit pas avoir les mêmes jeux de cartes !
Chez moi, les coeur et les carreau sont rouges, et les trefles et pique noirs, d'ou ma suggestion d'eliminer la moitié des cartes en fonction de cette couleur...

Je comprends un peu mieux ton explication pipo44, mais il y a encore une chose que j'ai du mal à comprendre... ta carte va s'afficher à l'écran, et en supposant que tu connaisses ou se situe le pixel(0,0), les pixels seront identiques si tu parcours tes deux images en parallèle, c'est bien ca ???
Maintenant, pourquoi est-ce que tu dois selectionner ton image "à la main" ?? il y a plusieurs cartes qui s'affichent en meme temps ??? ou bien est-ce une seule carte sur un fond uni ?

[ToTo13]

Bonjour,

la comparaison pixel à pixel est très rarement la meilleure solution. Comme tu l'as dit toi même, il peut y avoir un décalage, l'égère rotation, du bruit, une luminosité différentes, ...

En reconnaissance de formes, on utilise plutôt une représentation de l'objet par ses caractéristiques : surface, périmètre, ... et dans ton cas couleur, numéros, ...
La méthode la plus simple et peut être même la plus efficace pour ce problème est une recherche par K plus proches voisins (K Nearest Neighbors). C'est une méthode couramment utilisée dans le OCR qui a fait ses preuves.

[pipo44]

- tu peux mettre plusieurs exemplaires (légèrement différents bien sûr) de chaque carte dans ta base de données. Surtout si tu veux être capable de reconnaître plusieurs des graphismes les plus utilisés :
http://his.nicolas.free.fr/Images/Je...xandre_WEB.jpg
http://trictrac.aquitain.free.fr/IMA.../pique_roi.gif
- Tu parlais de deux couleurs, rouge et noir, mais qu'est ce que tu fais des figures qui sont de plusieurs couleurs ?

En fait ça sera pour reconnaître des cartes s'affichant sur mon écran donc pas de problème pour que ce soit à plat.

Merci pour ta réponse je vais étudier le coup des niveaux de gris

[pipo44]

"la comparaison pixel à pixel est très rarement la meilleure solution. Comme tu l'as dit toi même, il peut y avoir un décalage, l'égère rotation, du bruit, une luminosité différentes, ...

En reconnaissance de formes, on utilise plutôt une représentation de l'objet par ses caractéristiques : surface, périmètre, ... et dans ton cas couleur, numéros, ...
La méthode la plus simple et peut être même la plus efficace pour ce problème est une recherche par K plus proches voisins (K Nearest Neighbors). C'est une méthode couramment utilisée dans le OCR qui a fait ses preuves."

Ouooooooow rassure moi si je reconnais des éléments de mon écran je n'aurais pas tous ces problémes??

ta carte va s'afficher à l'écran, et en supposant que tu connaisses ou se situe le pixel(0,0), les pixels seront identiques si tu parcours tes deux images en parallèle, c'est bien ca ???

Et bien non ils ne seront pas TOUS identiques étant donné que mon centrage pour faire les relevé pour ma base de donné et mon centrage pour savoir ou est mon pixel(0,0) lors de l'utilisation de mon programme ne seront pas exactement les même (coup du photographe). Mais la plupart des pixels seront les même étant donné que les cartes sont "uniforme" (grosse partie blanche puis grosse partie colorées). Il y aura juste une différence de pixels aux endroits ou la carte passera de la couleur au blanc.

Maintenant, pourquoi est-ce que tu dois selectionner ton image "à la main" ?? il y a plusieurs cartes qui s'affichent en meme temps ??? ou bien est-ce une seule carte sur un fond uni ?

Je voulais sous entendre par "sélectionner à la main" : déterminer le pixel 0,0 . Comme pour notre photographe (il a bon dos celui la ) le point 0,0 de notre BDD et le point 0,0 déterminé sur notre écran ne sera pas forcément exactement le même mais il sera géographiquement très proche.
Pour l'affichage des cartes, il y en aura deux , je compte tout simplement faire deux fois la même manipulation en changeant de pixel d'origine.

[Jeromnimo]

oki, je commence à comprendre un peu mieux
Tes cartes seront sur un fond uni je suppose (genre du blanc) ?
Et est-ce que tu es sûr d'échantillonner tes images de la même manière (tu parles du décalage de 2/3 pixels, mais est-ce qu'il peut y avoir une rotation aussi ) ?
Il est clair que la reconnaissance des pixels n'est jamais la meilleure solution dans un cadre général, mais dans un contexte particulier, où les conditions sont maîtrisées, elle peut être très efficace

[Invité]

heuuuu, on doit pas avoir les mêmes jeux de cartes !

Je parle des couleurs au sens image. Sur un roi, y a du bleu, du jaune...

[pipo44]

Tes cartes seront sur un fond uni je suppose (genre du blanc) ?

mmmmmmmh, il y a un piège? Je compte faire une reconnaissance de pixel que sur ma carte, peut importe le fond. (PS : je déterminerais manuellement le point d'origine de ma carte...)

Et est-ce que tu es sûr d'échantillonner tes images de la même manière (tu parles du décalage de 2/3 pixels, mais est-ce qu'il peut y avoir une rotation aussi ) ?

L'échantillonage sera identique, il n'y aura pas de rotation, juste mon petit décalage (de photographe ).
Mon décalage se fait sur l'axe des abscisses et des ordonnées de plus ou moins deux pixel je pense.

[Invité]

Merci pour ta réponse je vais étudier le coup des niveaux de gris

Le coup des niveaux de gris ne sera pas bon s'il y a de légères différences entre l'éclairage des cartes. Ou alors il ne faut pas que tu fasse une comparaison stricte des valeurs des pixels. Mais à ce moment là autant faire un seuillage et utiliser des images binaires.

[Jeromnimo]

Si il n'y a aucune rotation, tu peux prendre comme origine le premier pixel différent du fond comme origine, ce qui te permettra de retrouver tes pixels à l'identique...
Dans ce cas tu sélectionne une zone un peu plus large que ta carte à la main, et tu parcours les pixels en ligne jusqu'à trouver un pixel différent du fond. tu es sûr d'être sur le pixel(x,y) de ton image de la BDD qui correspond au premier pixel différent du fond, et à partir de là, ta comparasion de pixels se fera dans des conditions parfaitement identiques...
J'espère que c'était clair

[pipo44]

ta comparasion de pixels se fera dans des conditions parfaitement identiques...
J'espère que c'était clair

Très clair clair merci, je n'y avais pas pensé donc merci beaucoup!!!

Pour les niveaux de gris mes connaissances sont à 0 donc c'est du chinois ce que tu me dis cependant je regarderais ça de plus près .

[Invité]

Pour les niveaux de gris mes connaissances sont à 0 donc c'est du chinois ce que tu me dis cependant je regarderais ça de plus près .

Ok, rapide explication. Parmi les formats d'image possibles, tu as :
- RGB (red green blue) : l'image est en couleurs. Pour faire une couleur, il faut un peu de rouge, de vert et de bleu. Un pixel sera donc représenté par 3 valeurs (de 0 à 255), une pour chacune de ces couleurs.
- Image en niveaux de gris : l'image est en "noir et blanc". C'est une façon de parler, puisque en fait l'image est en noir et blanc... et de toutes les teintes de gris possibles, comprises entre le noir et le blanc. Un pixel est représenté par une valeur comprise entre 0 et 255 (0= noir, 255=blanc).
- Image binaire. Là c'est du "vrai" noir et blanc. Un pixel est soit noir, soit blanc, et est donc représenté par une valeur qui est soit 0, soit 1.

Les images binaires sont très utiles pour faire des opérations élémentaires en traitement d'image, notamment grâce aux masques.
C'est quoi un masque ? C'est une image binaire, obtenue par seuillage d'une image RBG ou en niveau de gris.
C'est quoi un seuillage ? C'est une opération qui consiste à mettre à 1 tous les pixels qui répondent à des critères que tu fixes, et à 0 les autres.
Exemple : tu ne veux garder que les pixels rouges d'une image. Tu fais tout d'abord un masque. Si R, G et B sont les valeurs des composantes rouge, vert et bleu de tes pixels. Tu vas mettre à 1 les pixels qui satisfont les conditions suivantes (je mets des valeurs au pif, je ne sais pas quelle tronche aura mon rouge avec ces valeurs) :
R > 150
G < 50
B < 50
Tu obtiens ainsi un masque. Tu multiplies ton masque par l'image de départ, et ainsi tu as isolé les parties rouges de l'image, le reste étant à 0.

Pourquoi c'est intéressant pour toi de travailler en binaire ? Si tu compares tes images en niveaux de gris, tu va chercher à comparer des pixels tous vaguement gris, et comme tes images n'ont pas été acquises dans les mêmes conditions, deux pixels supposés identiques n'auront pas exactement la même valeur. Tu peux dire que tu compares les pixels à x près (genre 120 et 130 c'est kifkif), mais tu vas passer du temps à ajuster ce x pour que ça marche le mieux possible, alors que toute ce que tu veux, c'est savoir si ce truc à une forme de pique ou de trèfle.
Tu vas donc passer tout d'abord en niveaux de gris. Si je me souviens bien, il suffit de remplacer chaque pixel par la moyenne de ses composantes RGB.
Ensuite, tu vas faire un masque pour mettre à 1 le dessin a proprement parlé, donc tout ce qui ne fait pas partie du fond blanc de la carte (grosso modo, les pixels < 240 par exemple).
La suite reste comme tu l'avais pensé : tu compares ton image avec chacun de tes échantillons pixel par pixel. Si les deux sont à 1, tu incrémentes un truc, et à la fin tu divises ce truc par le nombre de pixels à 1 de l'image de référence. Le but étant que ce rapport soit le plus proche de 1.

Avant de passer en niveau de gris, tu peux appliquer l'idée de Jeromnimo : tu regardes si l'image est majoritairement noire ou rouge, et en fonction tu t'évites la moitié des comparaisons.

Edit : si tu peux, procure toi le logiciel Aphelion. Il permet de faire toutes les opérations que je t'ai décrit sans une goutte de programmation.

[pipo44]

Tout d'abord Gastiflex, merci beaucoup pour ta réponse très complète!!!

RGB (red green blue) : l'image est en couleurs. Pour faire une couleur, il faut un peu de rouge, de vert et de bleu. Un pixel sera donc représenté par 3 valeurs (de 0 à 255), une pour chacune de ces couleurs.

Tu vas donc passer tout d'abord en niveaux de gris. Si je me souviens bien, il suffit de remplacer chaque pixel par la moyenne de ses composantes RGB.

Sur le net j'ai trouvé que GETRValue, GETGValue,GETBValue servait à trouver les niveaux de couleurs rouge,vert et bleu.
Est ce que du coup pour passer de RGD à niveau de gris l'opération suivante serait elle valable :
pour chaque pixel :
nveaupixel=[ GETRValue(pixel)+ GETGValue(pixel)+GETBValue(pixel) ]/3

Est ce que pour faire la technique de Jeromnimo je peut faire un : GETRValue et dire que si la valeur est supérieur à une certaine valeur alors c'est bon? (le noir est composé d'aucune couleur ça va etre quoi sa GETRValue??)

Ensuite pour passer de niveau de gris à booléen je dis quand "valeur du nouveau pixel"<une certaine valeur => 0 ? (ton explication semble dire ça mais je préfère être sur).


Deux dernières petites questions bonus :
Hier soir J'ai fait une différence d'un entier avec une couleur et ça m'a donné un résultat cohérent (algo qui marche) alors qu'un peut plus tard j'ai vu que GetPixel renvoyé un hexadécimal (couleur).Comment ça ce fait que mon algorithme tourne?
Dans un printf, on met %d pour un entier %f pour un flottan t(rien d'exceptionnel jusque la ) mais que met t on pour voir une couleur sous sa forme hexadécimale?

merci de vos réponses