Enlever des points sans perdre d'information

Pour de la reconnaissance de caractères

L'auteur de ce sujet a trouvé une solution à son problème.
Auteur du sujet

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)

+0 -0
Auteur du sujet

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 ?

+0 -0

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.

ache.one                                                            🦊

+0 -0

Cette réponse a aidé l'auteur du sujet

Je vois pas en quoi l’ACP va aider ici. L’ACP sert à faire ressortir les informations pertinentes en projetant dans un espace de dimension moindre. Ca pourrait servir si tu voulais redresser tes images si elles étaient tournées afin de trouver les axes principaux par exemple.

Dans le cadre de l’OCR, en général on va configurer la méthode sur des images de taille fixe (8 x 8,16 x 16,32 x 32) et on se débrouille pour pré-traiter les données afin qu’elles soient dans ce format avec un simple algorithme de redimensionnement d"image.

Édité par Davidbrcz

+1 -0
Auteur du sujet

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 ?

+0 -0

Cette réponse a aidé l'auteur du sujet

C’est généralement parfaitement suffisant, pour peu que tes images soient correctement dimensionnées et centrées. Ensuite, il est nettement préférable de travailler en niveaux de gris plutôt qu’en noir et blanc (i.e. travailler dans $[0..1]^{n}$ et non dans $\{0,1\}^{n}$).

Enfin, pour arriver a quelque chose de potable, il faut un nombre d’exemples assez conséquent. En reconnaissance de chiffres, tu peux essayer la base de données MNIST qui est très connue, mais il en existe bien d’autres.

+0 -0

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é

Édité par Davidbrcz

+0 -0

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.

+0 -0
Auteur du sujet

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.

+0 -0
Vous devez être connecté pour pouvoir poster un message.
Connexion

Pas encore inscrit ?

Créez un compte en une minute pour profiter pleinement de toutes les fonctionnalités de Zeste de Savoir. Ici, tout est gratuit et sans publicité.
Créer un compte