Enlever des points sans perdre d'information

Salut à tous !

J’ai voulu tester de créer un programme simple de reconnaissance de caractère. Basiquement je trace avec la souris un caractère sur ma fenêtre, et je récupère un tableau (ordonné) de points.

Pour faire la reconnaissance des caractères, je me suis dit que représenter chaque caractère par un sous-espace vectoriel pourrait peut-être passer, et ainsi chaque tableau de point à identifier serait un vecteur, et il "suffirait" de calculer des projetés orthogonaux pour déterminer le caractère le plus probable.

Mon problème est le suivant : je dois pouvoir reconnaître un caractère quelque soit sa taille, et le nombre de point obtenu lors de l’acquisition à la souris. Et pour ça, la magie de l’algèbre linéaire ne doit pas pouvoir m’aider . Pour la taille un simple changement de repère devrait suffire, mais je bloque sur le problème du nombre de points. Pour que tous mes vecteurs représentant les caractères soient dans un espace de même dimension, il me faut un nombre constant de points : je doit trouver un moyen de réduire leur nombre (comme avec la souris on capture un point à chaque frame on ne devrait jamais avoir à en rajouter).

J’ai testé la solution suivante :

• pour chaque point $p_i$, on calcule l’angle $(\overrightarrow{p_{i-1}p_{i+1}}, \overrightarrow{p_{i-1}p_i})$ (en non orienté)
• On enlève alors les points avec l’angle le plus faible, donc ceux qui sont le plus aligné avec les points suivant et précédent, donc possédant le moins d’information.

Mais cette solution ne me satisfait pas : il va falloir trier un nombre énorme de points selon l’angle :(.

Je suis sûr qu’enlever des points d’un ensemble de point en minimisant l’information perdue est quelque chose de relativement courant, mais pas moyen de trouver des trucs sur internet faute de mots clés clairs …

Vous auriez une idée ?

(j’ai un peu hésité entre le poster ici ou dans Sciences pour les maths)

Merci ! J’ai pas encore regardé l’article en détail, mais ça ressemble fort à une espèce de diagonalisation / décomposition SVD ? C’est pas trop coûteux en temps / ressources ?

Je n’ai jamais fait de décomposition SVD. Mais une phrase permet de bien cerner l’ACP :

Finalement, la question de l’ACP se ramène à un problème de diagonalisation de la matrice de corrélation.

Mais étant donné que ACP est la première lien "Voir aussi" de la page wikipédia de la décomposition SVD alors oui ça doit beaucoup ressembler.

Après, l’ACP n’est pas la seule méthode d’analyse de donnée mais je suis loin d’être un expert dans le domaine.

Merci ! Mais alors du coup on doit stocker différemment nos vecteurs … je pensait ne stocker que les coordonnées des points, donc avec un nombre de points fixe. Du coup si on raisonne avec une image fixe, comme du 8 x 8, il faut un vecteur dans $\mathbb{R}^{8\times 8}$, où pour chaque pixel de l’image, on met 1 ou 0 dans la composante du vecteur qui correspond selon si le pixel est colorié ou non, c’est bien ça ?

C’est vrai que finalement ça semble plus simple, mais on perd de l’info sur l’ordre de tracé des points. Ça ne va pas trop nous déranger pour la suite ?

Les techniques classiques d’OCR ne sont pas "dynamique" dans le sens où on te donne une image, tu dois la reconnaître et c’est tout… Tu ne sais pas comment elle a été tracé, tu n’as aucune information sur l’ordre des points. Tu peux regarder une base connue de chiffres comme la base MNIST pour t’en convaincre. Après, il existe peut être (sûrement même) des articles de recherche qui prenne en compte/analyse la manière dont une lettre fût écrite mais je n’y connais rien.

Sinon l’encodage que tu proposes est bien celui employé pour de l’OCR à base réseau de neurones.

Edit: totalement grillé

Ah, je n’avais pas saisi que la problématique originale est la version de reconnaissance manuscrite en mode online. C’est sensiblement différent, tu peux jeter un coup d’œil ici pour un très bref aperçu.

En soit c’est même pas vraiment de la reconnaissance online puisque je ne stockais pas le moment où chaque point était placé, juste l’ordre. En tout cas merci je vais regarder tout ça.

Et c’est vrai qu’avec des nuances de gris on doit perdre moins d’info qu’avec du noir et blanc je vais partir là dessus.