Reconnaissance de symboles tracés via la souris

Un article de Teto.


Sommaire

[modifier] Reconnaissance de symboles (Description algorithmique)

[modifier] Introduction

La reconnaissance de caractères tracés à la souris peut augmenter l'immersivité du jeu en se substituant à des menus de jeu ou bien parce qu'elle imite mieux la réalité. Intégrée au navigateur Opéra, elle permet aussi d'augmenter la vitesse de surf.

Ce tutorial ne prétend pas à l'exhaustivité loin de là. Il présente la technique utilisée dans le cadre d'un jeu développé en C à 4 en temps limité (Anteus) et est largement inspiré du code de Tribal Wars (merci à Kick pour sa coopération).

Et parce qu'une image vaut 1000 mots, voici une image créée pour le gamedocument du projet Anteus. Image:ObjectifReconnaissanceDeSymbole.jpg

[modifier] Cahier des charges

On va essayer de préciser un peu les fonctionnalités du système de manière plus formelle. Grosso modo, on vise un système proche de celui d'Opéra (le navigateur web), c'est-à-dire :

  1. distinguant le sens dans lequel le symbole est tracé. Ainsi un segment tracé de gauche à droite doit être considéré comme différent d'un autre segment tracé depuis la droite vers la gauche <ref> Le premier correspondant dans Opéra à l'action "Page suivante" et le second à l'action "Page précédente" par exemple</ref>
  2. le symbole peut être tracé à différentes échelles ( on peut tracer un grand "L" aussi bien qu'un petit "L" tant que les proportions entre différents segments sont respectées ). Ca permet d'éviter un apprentissage trop contraignant, de se retrouver déboussolé quand on change de résolution etc...
  3. on doit pouvoir commencer à tracer le symbole n'importe où sur l'écran pour la même raison et aussi parce qu'on ne peut pas définir de point de départ commun à tous les symboles sans restreindre la possibilité des symboles.
  4. La création des symboles devait être simple car pas le temps de créer un éditeur de symbole.


Un premier problème est de faire la distinction entre mouvements de souris anodins et une volonté de la part de l'utilisateur de tracer un symbole. Pour notre part, nous avons décidé de délimiter début et fin du dessin d'un symbole par l'appui continu sur un bouton de la souris.

<ref>On peut imaginer de ne délimiter que le début, de vérifier à chaque frame si ce n'est pas un symbole en utilisant un timer pour limiter dans le temps les comparaisons.</ref>


Le point 3 n'est pas vraiment un problème, il s'agit juste de convertir des coordonnées absolues (coords de la souris vis-à-vis de la fenêtre) en coordonnées relative (coords de la souris lors du premier clic de souris).

Le point critique reste le point 2. Petite étude de différents systèmes envisagés.


  1. Une première idée peut être d'enregistrer une image bicolore (noir/blanc par exemple) du symbole dessinée avec une certaine épaisseur (équivalente à la tolérance) et de vérifier que le curseur ne sort pas de la zone blanche (un peu à la manière du jeu Forward/Reward).Ce systeme n'empêche pas l'utilisateur de faire des allers/retours dans la zone autorisée ce qui permet de ne pas suivre tout à fait le symbole mais le joueur n'a pas d'intérêt à zigzagger plutôt que de suivre le symbole.
  2. On peut utiliser des fonctions paramétrées, des splines puis calculer la distance entre le curseur et la tangente à la spline etc... La solution n'a pas été explorée plus loin car elle n'était pas en adéquation avec le point 4 (on s'imaginait mal trouver les points de contrôle sans éditeur de spline ^^ ).

[modifier] Description de la solution choisie

Il est important d'enregistrer les positions absolues du curseur (ça foire en relatif: pour peu qu'on soulève la souris par exemple,le curseur est décalé par rapport à l'endroit où on trace). Si vous enregistrez les coordonnées à chaque frame, vous vous retrouvez avec approximativement 400 points ( Soit 400 x 2 entiers puisque qu'on parle de coordonnées écran 2D). La mémoire n'est pas un problème, le vrai souci est qu'on va devoir effectuer des opérations sur ces 400 points pour chaque symbole de la liste avec lequel il faudra le comparer. Une bonne idée peut être d'enregistrer les points éloignés avec un minimum de X pixels. Pour cela on calcule la distance (au carré pour éviterr d'utiliser la coûteuse fonction racine carrée) entre le dernier point enregistré et la position actuelle de la souris. Dès que la distance curseur/dernier point enregistré dépasse X pixels, on ajoute le point à la liste des points définissant la commande utilisateu. Ca évite également d'enregistrer tous les tremblements du joueur (à moins de jouer sur sa machine à laver, ca devrait aller).

En pseudo code

//Boucle traitant les événements
...
// Si la souris bouge
case SDL_MOUSEMOTION:
...
                // Si on est en train de dessiner un pouvoir
                if(gContexteProgramme.traceSymbole){
 
                    // on recupere le dernier point enregistré lors 
                    SVecteur dernierPoint = recupererDernierPointTraceEnregistre();
 
                    SVecteur positionSourisActuelle(event.motion.x, event.motion.y);
 
                    // SVecteur <=> point
                    float normeCarree = calculerNormeCarreEntreLes2Points(dernierPoint,positionSourisActuelle);
 
 
                    // si suffisamment loin du point precedent, on l'ajoute a la liste des 
                    // points qui comptent
                    if(normeCarree > _DISTANCE_MINIMALE_ENTRE_POINTS_SYBOLE_AU_CARRE) {
                           ajouterPointAuSymboleTraceParLutilisateur(positionSourisActuelle);
                    }
                }
                break;
...


Pour le format de stockage des symboles, on hésitait entre 2 solutions :

  • enregistrer les coordonnées des points du symbole
  • enregistrer les vecteurs déplacements d'un point à son successeur


Exemple plus précis:

0,0		// Point(0,0)
0,20		// Point(0,20)
30,200		// Point(30,200)

=> Points:

0,0		// Point(0,0)
0,20		// Point(0,0) + (0,20) = (0,20)
-30,220		// Point(0,20) + (-30,220) = (-30,240);

On voulait éviter de se retrouver avec des points négatifs (car le repère SDL utilise des coordonnées positives uniquement) donc on a choisi la première solution moins sujette à erreur à priori.

Au final un symbole n'est qu'un tableau de points. On peut décider de créer une classe/structure et d'y sauver des informations complémentaires calculées à chaque chargement. Cela permet d'éviter de tout recalculer à chaque comparaison avec un autre symbole.

Par exemple dans le cadre d'anteus :

typedef struct  {
// Indispensable
STableau* points;   //!< Tous les points échantillonés
 
// Optionnel
int nbPoints;       //!< Nombre total de points échantillonés
STableau* dist;     //!< Distances cumulatives du premier point jusqu'au x-ième
int largeur;        //!< Largeur du symbole ( utile pour l'affichage )
int hauteur;        //!< Hauteur du symbole ( utile pour l'affichage )
} SSymbole;

Une fois que l'utilisateur relâche le bouton de la souris (<=> j'ai fini de tracer mon symbole), on a tous les points nécessaires pour effectuer la comparaison. Dès lors comment procéder ? Le comparer à tous les symboles enregistrés jusqu'à ce que l'un d'entre eux corresponde ou bien qu'il n'y ait plus de symbole avec lequel comparer.

....
    //listeSymboles est le tableau contenant tous les symboles
    int noSymbole = 0;
    // Pour chaque pouvoir chargé en mémoire
    while(noSymbole <=  taille(listeSymboles) ){
 
            // On calcule la difference du symbole trace par l'utilisateur avec le symbole de reference
            float dist = comparerAvecSymbole(listeSymboles[noSymbole],symboleAcomparer,bufferDist,bufferPointsCorriges);
 
            // si jamais on est inferieur au seuil defini dans la configuration
            if(dist < limiteAcceptable){
                // alors il s'agit du bon pouvoir et on recupere son numéro
                return noSymbole;
            }
            ++noSymbole;
        }
    }

Cela présuppose qu'on a déja chargé les autres symboles <=> blabla....

[modifier] Algorithme

Pour chaque symbole enregistré, tant que le symbole n'est pas reconnu, on va effectuer les opérations suivantes: Image:AlgoReconnaissanceSymbole.jpg [Faudrait intégrer du code ici]


  • On calcule la longueur totale du symbole tracé, et on multiplie chaque coordonnée par le ratio (longueur du symbole référence)/(longueur du symbole tracé) pour avoir 2 symboles de même longueur (problème 3 de la mise à échelle résolue).
  • On fait en sorte d'avoir le même nombre de points dans le symbole tracé que dans le symbole enregistré pour pouvoir ensuite....
  • ...calculer les distances point à point des coordonnées des 2 symboles. On somme toutes ces distances au final qui représentent un écart au symbole référence.


Plus les 2 symboles sont proches, plus la distance totale est proche. En dessous d'une valeur seuil, on admet que le symbole tracé est reconnu.

Ici la fonction d'Anteus permettant de faire ceci (saucissonnée par quelques explications):

/**
*
* \param pointsCorriges est juste la liste des points tracés par l'utilisateur
**/
float
comparerAvecSymbole(SSymbole* pouvoir,SSymbole* symbole,float* dist ,SVecteur* pointsCorriges){
 
 
    SVecteur* points = symbole->points->donnees;
 
    int i = 0,j = 0;
 
    // si moins de vecteurs tracés que dans le pouvoir
    // les 2 symboles ne sont pas identiques
    if(symbole->nbPoints < pouvoir->nbPoints){
        return -1.0f;
    }
 
 
    float distanceCumulative = 0.0f;
    //calculate the distance betwen each point of incoming shape
    dist[0] = 0.0f;
    SVecteur v;
    for(i = 1; i < symbole->nbPoints ;i++){
 
        //Bug ne retourne que des v bizarres
        calculerVecteur(&v,&points[i-1],&points[i]);
 
        distanceCumulative += normeVecteur(&v);
        dist[i] = distanceCumulative;// Met a jour la distance jusqu'a ce point
 
    }
 
    //scale the incoming shape to the loaded one
    // rapport entre les 2 distances totales
    float* distancePouvoir = accesElementTableau(pouvoir->dist,pouvoir->nbPoints-1);
    float delta_size = (*distancePouvoir) / distanceCumulative;
 
    //offsets <=> a l'endroit ou on a commencé a tracer le signe
    //il faut retirer les coords de ce point à tous les points
    //car le symbole est defini par rapport a 0
    //offset = points[0];
 
    // reparametre le symbole dessiné pr qu'il soit redefini par rapport à (0,0)
    // et reajuste sa taille pr qu'elle soit identique a celle du pouvoir charge.
 
    for(i=0; i < symbole->nbPoints ;i++){
 
        pointsCorriges[i].x = (points[i].x - points[0].x) * delta_size ;
        pointsCorriges[i].y = (points[i].y - points[0].y) * delta_size ;
 
        dist[i] *= delta_size;
    }
 
 
 
 
//int k = 0;
    //get the same number of points, with the nearest points
	//need to improve with interpolation of 2 nearest points
	// Side-effect : inverse l'ordre des points
	// prend le point de la distance tout juste supérieure
	// au point du pouvoir
 
    STableau* t3 = nouveauTableau(pouvoir->nbPoints,sizeof(SVecteur));
    SVecteur* pointsFinaux = t3->donnees;
    float* distance = NULL;
	for( i=0; i < pouvoir->nbPoints ;i++ ){
 
		for(j = symbole->nbPoints-1; j >= 0 ; j--){
 
            pointsFinaux[i].x = pointsCorriges[j].x;
			pointsFinaux[i].y = pointsCorriges[j].y;
 
            distance = accesElementTableau(pouvoir->dist,i);
			if(dist[j] < *distance){
                break;
			}
		}
 
	}
 
	distanceCumulative = 0.0f;
	//Calcule la longueur entre 2 points de mm rang des symboles
	for(i=0; i < pouvoir->nbPoints;i++){
 
	    calculerVecteur(&v,PVR(i),&pointsFinaux[i]);
        distanceCumulative += normeVecteur(&v);
 
	}
 
 
    // Difference de longeur par point
	distanceCumulative /= pouvoir->nbPoints;
 
    return distanceCumulative;

[modifier] Conclusion

Je ne mets pas de code "out of the box" mais vous pouvez jeter un coup d'oeil à celui du projet en question: Anteus ( C/SDL/Fmodex/une petite partie lua facile à enlever).

Si jamais vous avez un exemple de code fonctionnel orienté objet ou si vous avez découvert un framework remplissant le cachier des charges, il serait très intéressant de le partager.

[modifier] Notes

<references/>

[page de dscussion]Discuter:Reconnaissance de symboles tracés via la souris

[modifier] reseau neuronal type perceptron

Un code que j'ai fait il y a quelques année en darkBasicPro Sers-toi...

ici : [1]

L'avantage de cette méthode, c'est qu'elle est généraliste et simple à coder. Tu peux lui faire apprendre plein de chose. Et il sera capable de reconnaitre un v pas exactement comme dessiné etc... Essayes J'ai tous détaillé dans le message. Le code n'est bien sûre pas orienté objet... Si d'aventure, tu le codée en c++ ou c, je suis preneur.

Il n'est pas optimisé dans cet exemple, mais une piste qui change tous (pour l'avoir essayé) entree=cherche_entree(ordre(reso,NC,NN),ordre(reso,couche,N)) Cette appel rend l'apprentissage long.

En utilisant les pointeurs, tu peux gagner un facteur ... 1000 ... sur la vitesse d'apprentissage.

Un dernier avantage, la consultation d'un réseau est très rapide.



Les commentaires ci-dessus ont été laissés par des visiteurs.
Le gestionnaire du site n’est pas responsable de leur contenu. This site's operators can not take responsibility for the content of such comments.