Navigation
Critical probabilities algorithm, a pretext to write an ocr
permalink to this page
Contents/Contenu
- Definitions
- Context(e)
- Disclaimer/Avertissement
- Implementation
- Test it
Definitions
fr - OCR (ROC en français)- signifie «Reconnaissance Optique de Caractères».
en - OCR- stands for « Optical character recognition».
Context(e)
fr
- projet UTBM lors de mon 2nd semestre (TL51 : Théorie de l'information) ;
- Responsable d'UV : Rachid Bouyhekf.
en
- educational UTBM project during my 2nd semester (TL51 : Information theory);
- Rachid Bouyhekf professor.
Disclaimer/Avertissement
fr
- Seulement une preuve de concept : les pixels sont l'unité d'information, et pas les formes.
- Pour simplifier j'ai choisi d'utiliser des widgets de type 'bouton' pour les représenter, ce qui est très mauvais pour les performances.
en
- Not more than a proof of concept : pixels are the basic information unit, not forms.
- For the sake of simplification I chose to use 'button' widgets to represent pixels, which is very suboptimal.
Implementation
Dependances
How the program works
Quick explanation
The program stores a list of grids and, for each grid, a list of forms, each associated with a name (unfortunately there is no serialization of data in this program, so the user has to input all the data everytime).
The form recognition is performed in an iterative manner, each iteration consisting of these steps:
- Identification of the one pixel in the grid whose value is the most discriminating. Optimally this pixel is white for half of the candidate forms (black for the rest). Knowing if that particular pixel is black or white will statistically eliminate up to half of the candidates. Otherwise said: which pixel would bring the most information (and save iterations) ?
- Checking the value of the pixel in the form to be recognized.
- Eliminate the known forms that do not match from the candidates.
- If the candidates list only contains one item, then this is the one we were looking for.
Why this is not a good algorithm for OCR as such
We, human, use forms, not pixels, to write and read. This program only use pixels, eg. is very likely to fail to recognize a 't' letter if the bar is shifted by only one pixel, whereas we, humans, are likely not to even notice the fact. Real OCR engineers might know if an increase in resolution would solve this issue, however I believe that a good OCR program should analyse forms, maybe by mapping them to bezier curves for instance (computer programs are quite good at that now).Still, the algorithm explained above is useful as a base for quickly discriminating information, and works for non binary data (the cardinality of the alphabet is a parameter in Shannon's law).
Dependances
Fonctionnement du programme
Explication rapide
Le programme stocke une liste de grilles, et pour chacune de ces grilles, une liste de formes, chacune associée avec un nom (il n'y a malheureusement pas de sérialisation dans ce programme, par conséquent l'utilisateur est contraint de resaisir toutes les données à chaque fois).
Le processus de reconnaissance de formes est itératif, chaque itération comportant ces étapes :
- Identification du pixel dont la valeur sépare les formes candidates en deux ensembles de cardinalité la plus proche l'une de l'autre. L'optimum est atteint lorsque ce pixel est blanc pour une moitié des formes, noir pour l'autre. Autrement dit : quel est le pixel dont l'analyse fournira le plus d'information sur la forme à reconnaître (et permettra d'économiser des itérations) ?
- Détermination de la couleur du pixel dans la forme à reconnaître.
- Elimination de l'ensemble de formes candidates qui ne correspond pas.
- Si la liste de candidats restants ne contient plus qu'un seul élément, c'est celui qui était recherché.
Pourquoi ceci n'est pas un bon algorithme d'ocr en soi.
Les humains lisent et tracent des formes, des traits, pas des pixels ; ce programme ne prend que les pixels en considération, et a en conséquence une grande probabilité de ne pas reconnaître un 't' si la barre est décalée d'un seul pixel alors que des humains n'auraient même pas forcément remarqué cette différence. Les vrais concepteurs d'OCR savent peut-être si une augmentation de la résolution résoudrait ce problème, cependant je crois qu'un bon programme d'OCR devrait analyser les formes, par exemple en les approchant par des courbes de Bézier (ce que les programmes d'ordinateur réalisent très bien maintenant). Ceci posé l'algorithme décrit ci-dessus est utile en tant que base pour classer rapidement l'information, et il fonctionne parfaitement pour les données non binaires (la cardinalité de l'alphabet n'est qu'un paramètre de la loi de Shannon utilisée ici).
Test it
No waranty. See WTFPL for distribution and usage terms of the source code. Icons are borrowed from free software packages and might follow another free licence (GPL v2 ? ). Sorry , I haven't checked yet.
There is an french HTML manual inside the archive.
Sans garantie. Voir WTFPL pour les termes exacts de redistribution et d'usage du code source. Pour les icônes en revanche, elles sont empruntées à des paquets de logiciels libres et d'autres termes s'appliquent vraisemblablement. Désolé je n'ai pas encore vérifié.
Il y a un manuel en français dans l'archive.
