Mesurer la similarité entre le tracé de l'utilisateur et un tracé de référence

Bonjour

Je souhaiterais calculer une mesure de la similarité / distance entre deux tracés. Je vous décris la procédure pour que vous compreniez ce que j’entends par « tracé ».

• Je dispose d’un tracé de référence (choix de la représentation libre) : imaginez un tracé fait avec un crayon sans lever le crayon. Ça peut être un simple cercle, un triangle, ce genre de choses.
• Je capture le tracé d’un utilisateur (j’ai un bout de code qui fait ça en écoutant les événements mousemove sur le document, cf. l’annexe en fin de post). J’obtiens une liste de points : les points que les événements mousemove m’ont donné pendant que le bouton de la souris était enfoncé.
• Je veux savoir à quel point la forme du tracé de l’utilisateur ressemble au tracé de référence, sans tenir compte de l’échelle (il peut être plus petit ou plus grand, ce qui compte c’est que la forme soit la même). Par exemple si le tracé de référence était un cercle et que l’utilisateur a dessiné à peu près un cercle (pas forcément de même diamètre), la mesure de distance devrait être proche de zéro. Mais si ce qu’il a tracé ne ressemble pas du tout à un cercle la distance devrait être grande.

Je ne sais pas bien dans quelle direction partir. J’ai fait quelques recherches Google mais je ne parviens ni à trouver quelque chose qui réponde à ce besoin précisément, ni une solution à un problème similaire que je parviendrais à adapter.

Au départ, j’ai imaginé l’algorithme suivant :

• On a besoin d’un tracé de référence (le tracé dont l’utilisateur cherche à imiter la forme).
• Normaliser les tracés (le but est de « coller » les tracés vers l’origine du repère) :
  • Rechercher l’abscisse la plus petite dans la liste des points du tracé.
  • Retirer la valeur trouvée aux abscisses de tous les points du tracé.
  • Faire de même avec les ordonnées.
• On calcule la distance entre chaque point du tracé et le point le plus proche du tracé de référence.
• Le résultat est la somme des distances : plus cette somme est proche de zéro, plus les tracés sont similaires.

Les problèmes que j’ai identifié avec cette approche sont les suivants :

• Cela ne répond pas au besoin d’être insensible à l’échelle : un tracé reproduisant parfaitement la forme mais d’une taille différente à celle du tracé de référence ne permettra pas d’avoir une distance nulle.
• Si un tracé contient peu de points (si on bouge la souris très vite par exemple), le point le plus proche peut être loin d’un point du tracé tout en étant sur le tracé. Par exemple si on a un point de coordonnées (0,5) et que le tracé de référence est constitué des points (0,0) et (0,10), le point est à une distance de 5 de chaque point du tracé, alors qu’il est sur le tracé.

Je suppose que puisque je voudrais être insensible à l’échelle du dessin, j’aurais besoin de travailler avec des vecteurs mais je n’ai aucune idée de comment faire. Vos suggestions sont les bienvenues ! Soyez toutefois conscient⋅es que mon niveau en mathématique est très faible, attendez-vous donc à des questions !

Annexe – l’exemple de code avec lequel je compte capturer le tracé de l’utilisateur :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

let captureEnabled = false;
let shapePoints;

function startCapture() {
    console.log('START CAPTURE');
    captureEnabled = true;
    shapePoints = [];
}

function capture(mouseEvent) {
    if (!captureEnabled) {
        return;
    }

    shapePoints.push(Point.fromMouseEvent(mouseEvent));
}

function endCapture() {
    console.table(shapePoints);
    captureEnabled = false;
}

class Point {
    constructor(x, y) {
        this.x = x;
        this.y = y;
    }

    static fromMouseEvent(event) {
        return new Point(event.offsetX, event.offsetY);
    }
}

window.addEventListener('mousedown', startCapture, false);
window.addEventListener('mousemove', capture, false);
window.addEventListener('mouseup', endCapture, false);

Pour normaliser ton image à la taille ton image de référence, tu peux calculer la bounding box de ton dessin, te restreindre à cette sous-image en croppang et la redimensionner à une taille de référence.

Pour le calcul de similarité, y’a des articles de recherche sur l’utilisation de la distance de Hausdorff. Aucune idée c’est encore la pointe de la recherche ou si on fait mieux et/ou autrement depuis.

Bonjour Davidbrcz et merci pour ta réponse !

Je vais me documenter un peu et je reviendrai ici poster mes questions et / ou le résultat de mes réflexions et expérimentations.

Soyez toutefois conscient⋅es que mon niveau en mathématique est très faible, attendez-vous donc à des questions

Je viens de voir ce passage. Ce que tu souhaites faire n’est pas du tout trivial, surtout pour des dessins arbitraires, ca va demander des choses un peu évoluées.

Si tu as des hypothèses plus fortes (comme par exemple, il n’y a que 3 figures possibles, carré, rond, triangle) alors on peut envisager des méthodes plus simples pour calculer la similarité (nombre de cotés, ratio des surfaces, …).

D’ailleurs, dans le domaine du traitement d’image, OpenCV est une référence. Une contrainte particulière pour faire du dev web (cf le tag).

Merci pour l’avertissement.

Si tu as des hypothèses plus fortes (comme par exemple, il n’y a que 3 figures possibles, carré, rond, triangle) alors on peut envisager des méthodes plus simples pour calculer la similarité (nombre de cotés, ratio des surfaces, …).

Ce que je sais sur les tracés: ce sont uniquement des lignes (pas de formes pleines). Ce sont des tracés assez simples, constitué d’un seul trait. Et si ça simplifie on peut considérer qu’il y a un point de départ et un point d’arrivée.
En gros c’est une suite de point ordonnée qu’il faut considérer comme reliés les uns aux autres.

Le second problème que j’avais relevé n’est en fait pas très pertinent car pour le régler il me suffit de m’assurer que mes modèles sont très précis (c’est-à-dire qu’il contiennent suffisamment de points pour qu’un point qui est sur le tracé soit toujours très proche d’un point du modèle).

Le vrai problème au final c’est la mise à l’échelle. Je ne vois vraiment pas comment faire ça. Peut-être que pour commencer je vais m’affranchir de cette contrainte et compenser avec l’interface utilisateur pour pousser à dessiner à la bonne taille.

Merci pour les retours !