Projet image 2016 : Reconnaissance de documents : Différence entre versions

De Ensiwiki
Aller à : navigation, rechercher
(Filtrage et binarisation)
(Prétraitement)
Ligne 61 : Ligne 61 :
  
 
<center>[[Fichier:Transformation.png|800px]]</center>
 
<center>[[Fichier:Transformation.png|800px]]</center>
 +
 +
 +
==== Squélétisation ====
 +
L'extraction des squelettes aurait dû permettre une meilleure reconnaissance, toutefois celle-ci était trop sensible au bruit présent après les deux étapes précédentes. Aussi à partir d'une image parfaite, nous obtenons le premier squelette, tandis qu'avec le caractère imparfait, nous observons le second. Cette piste a été combinée avec le calcul de la [https://www.cs.cornell.edu/courses/cs664/2008sp/handouts/cs664-8-binary-matching.pdf distance de Chamfer], cependant celle-ci s'est révélée moins efficace.
 +
 +
[[Fichier:Squelette.png]]
 +
 +
==== Rotation ====
 +
Enfin, l'image peut présentée une rotation (que nous avons limitée à plus ou moins 45°).
 +
 +
[[Fichier:Alice_rotation.png|800px|thumb|center|upright=3| Image avant traitement]]
 +
 +
Afin de corriger cette erreur, nous procédons à une [https://en.wikipedia.org/wiki/Hough_transform transformée de Hough] puis nous recherchons l'angle pour lequel le nombre de droite parallèle est le plus important.
 +
 +
[[Fichier:Hough.png|400px|thumb|center|upright=3| Projection dans l'espace de Hough]]
 +
 +
Enfin nous effectuons la rotation de l'angle obtenu, nous permettant de redresser l'image.
 +
 +
[[Fichier:Droit.png|800px|thumb|center|upright=3| Image après rotation]]
  
 
=== Segmentation ===
 
=== Segmentation ===

Version du 9 juin 2016 à 09:18

Project schedule.png
Titre du projet Reconnaissance de documents
Cadre Projets de spécialité
Page principale Projets de spécialité image

Étudiants

Qu'est ce qu'un OCR ?

La reconnaissance optique de caractères est un domaine qui consiste à extraire les données d’une image pour être manipulées par l’ordinateur. Bien que le support papier soit un moyen de communication naturel pour les humains, il n’est pas compréhensible par un ordinateur et de ce fait il ne peut pas les traiter. L’une des premières utilisations de cette reconnaissance fut dans le domaine postale. La reconnaissance automatique des informations sur les lettres ont permis d’automatiser le transfert dans les bonnes zones postales. L’une des autres applications qui nous touchent particulièrement est l’extraction des données des formulaires que nous remplissons avec des lettres majuscules insérées dans de petites cases. Ces documents sont ensuite traités par un OCR (Optical Character Recognition).

Objectifs du projet

L’objectif de ce projet de spécialité que nous avons réalisé du 24 mai au 10 juin 2016 est de reproduire les différentes étapes nécessaires à la reconnaissance des documents. Les méthodes de résolution de ce problème sont diverses et variées. Nous nous sommes donc fixés des limites concernant les méthodes étudiées. D’une part nous essayerons d’implémenter différents algorithmes de difficulté croissante en nous basant sur les techniques développées durant l’âge d’or des publications (années 90 au début années 2000) en excluant les solutions appliquant les réseaux neuronaux. En effet, nous avons pris le parti d’implémenter les techniques algorithmiques nous permettant de comprendre les enjeux et la complexité du problème. En effet, ce problème reste irrésolu malgré l’apport des réseaux neuronaux.

Dans cette optique nous avons donc fixé un certain nombre de contraintes permettant de nous concentrer sur une partie du problème : - Texte en anglais ne contenant donc pas de lettres accentuées - Le texte sera écrit dans une couleur sombre (le plus proche possible du noir) sur un fond de couleur claire (le plus proche possible du blanc) ceci afin de simplifier les prétraitements - La qualité des scans devra être d’au moins 400DPI (qualité moyenne des scanners) - Enfin le texte devra être parfaitement lisible par un être humain et sans ambiguïté. Le texte scanné ne sera donc pas froissé, déchiré, tâché…

Ces contraintes seront maintenues durant toute la durée du projet. Nous avons une autre partie de contraintes qui nous permettront de gérer notre avancement et d'évaluer notre progression : - Tout d’abord nous travaillerons sur un document parfaitement droit, avec une qualité parfaite. Le document contiendra uniquement du texte sans aucune mise en forme quelconque dans une police standard monospace et une taille importante ( > 14) - Mêmes contraintes que précédemment mais la police pourra contenir des lettres qui se chevauchent (les lettres peuvent ne plus être séparable par une règle se déplaçant verticalement mais ne devront pas se toucher) - Le texte pourra contenir des défauts (bruit) dû au scan et comporter une légère rotation du texte. Nous tenterons également de séparer les caractères qui se toucherait (police donnant l’effet d’une écriture manuscrite en liant les lettres)

Organisation

Suite aux contraintes que nous nous sommes fixés et aux solutions envisagées lors de nos lectures, nous avons décider de procéder comme suit :

Organisation.png

Chaque ligne correspond à une étape de notre projet. Les colonnes correspondent aux différentes partie d’un OCR. Le prétraitement concerne la qualité de l’image, le but est d’améliorer la forme générale du texte. Enlever les rotations, les imperfections et passer en noir & blanc. La segmentation consiste à découper les lignes puis les caractères. La reconnaissance permet d’associer une liste de possibles caractères à une image (petite partie du document découpée par la partie précédente et supposé contenir un caractère). Le post-traitement permet de corriger les erreurs dues à la reconnaissance (majuscule, minuscule, mot anglais). Enfin le formatage permet de rendre forme au document.

Travail réalisé

Nous avons effectuer une ou plusieurs implémentations pour chaque partie. Nous allons décrire plus en détails les différentes implémentations que nous avons réalisées :

Prétraitement

Les scans présentant des défauts, il est nécessaire de les corriger en supprimant le bruit et en repositionnant le texte pour qu'il soit droit.

Filtrage et binarisation

Notre premier défi a été de choisir un filtre qui supprime le bruit sans déstructurer les lettres, cependant les filtres bilatérales et médians, usuellement utilisés en image, sont peu adaptés aux textes. Nous avons donc appliquer un filtre linéaire de masque :

1 2 1
2 4 2
1 2 1

Cela correspond à un filtrage gaussien qui permet de lisser le bruit.

Il est alors nécessaire de calculer le seuil des pixels correspondant aux caractères, nous avons utilisé la méthode d'Otsu.

Ainsi, à partir de la première image, nous obtenons la seconde par lissage et la troisième par binarisation.

Transformation.png


Squélétisation

L'extraction des squelettes aurait dû permettre une meilleure reconnaissance, toutefois celle-ci était trop sensible au bruit présent après les deux étapes précédentes. Aussi à partir d'une image parfaite, nous obtenons le premier squelette, tandis qu'avec le caractère imparfait, nous observons le second. Cette piste a été combinée avec le calcul de la distance de Chamfer, cependant celle-ci s'est révélée moins efficace.

Squelette.png

Rotation

Enfin, l'image peut présentée une rotation (que nous avons limitée à plus ou moins 45°).

Image avant traitement

Afin de corriger cette erreur, nous procédons à une transformée de Hough puis nous recherchons l'angle pour lequel le nombre de droite parallèle est le plus important.

Projection dans l'espace de Hough

Enfin nous effectuons la rotation de l'angle obtenu, nous permettant de redresser l'image.

Image après rotation

Segmentation

La partie segmentation a été un bloc majeur lors de ce projet. Il est en effet indispensable de découper correctement les caractères afin de les reconnaître correctement. Une mauvaise découpe entraînement inévitablement une mauvaise reconnaissance. Nous avons implémenté trois algorithmes différents :

Fenêtre glissante

La fenêtre glissante ou “sliding window” dans la littérature consiste à chercher une ligne verticale entièrement blanche et considérer cette comme une séparation de caractère. Cette méthode, bien que simple, permet d’implémenter une reconnaissance de mot et de paragraphes (voir partie formatage). Cependant elle est très sensible à la densité de pixel (DPI) du document. Une densité trop faible risque de rendre les espaces indétectables ou encore de désolidariser les lettres (pixels manquant dans un ‘d’ le coupant en ‘c’ + ‘l’ si la jonction petite de base, disparaît lors du scann). Le bruit sera également considéré comme un élément important et donc découpé au même titre qu’une ligne ou qu’un caractère.

Segmentation de lettre se chevauchant

L’ “overlapping segmentation” est la seconde méthode implémentée. Cette méthode, bien plus complexe que la première (plus que 400 lignes de code contre 30 pour la première) permet de découper deux caractères qui se chevauchent mais qui ne se touchent pas (au moins un pixel blanc entre les deux). L’avantage de cet algorithme est qu’il préserve les accents ou encore les points sur les ‘i’ et ‘j’. C’est donc une implémentation qui pourrait être utiliser sur des langues utilisant des accents comme le français. L’inconvénient majeur de cette solution est encore une fois liée au DPI. Les caractères doivent en effet être connexe (c’est à dire qu’il n’y a pas de pixels manquant pour que la lettre soit entière).

Sur segmentation

L’ “oversegmentation” est la dernière méthode implémentée mais pour laquelle nous n’avons pas eu le temps de développer tout son potentiel. Elle s’applique pour les caractères qui sont accolés. La première étape consiste donc à déterminer un ensemble de coupure qui pourrait s’avérer intéressant ( = correspondre à des lettres) puis d’y associer un graphe des possibles. A partir de là, en s’appuyant sur l’étape de reconnaissance, on cherche le chemin dont la probabilité de reconnaissance est la plus élevée (et qui correspond donc à un ensemble de lettre correct).

La limitation de cet implémentation est dûe au taux de reconnaissance des caractères. Au vu de nos implémentations, un caractère coupé en deux (même des lettres sans ambiguïté telles que le ‘c’ ou encore le ‘l’ dans les polices ayant une boucle) est très souvent mieux reconnu que le caractère entier.

Cet algorithme a une tendance a découper de trop. Un ‘d’ deviendra un ‘c’ + ‘l’ ou encore un ‘m’ -> ‘r’ + ‘n’. La prochaine étape que nous n’avons pas eu le temps d’implémenter (dû entre autre au point précédent) est la correction de cette coupure. Le principe est d’apprendre les “mauvaises” coupures que fait l’algorithme afin de les corriger si nécessaire.


Reconnaissance

Clusters

La base de données comprenant plus de 1000 images par caractères, il était nécessaire de réduire le nombre d’images afin que la reconnaissance s’effectue en temps raisonnable. L’algorithme utilisé est celui du Kmeans, cependant celui-ci considère chacun des pixels indépendants. Chaque caractère subit un clustering afin de résuire le nombre d’images le représentant, toutefois le cluster ne mélange pas les labels afin de conserver cette information essentielle à la reconnaissance.

Améliorations envisagées : - Utilisation d’autres informations sur l’image, ce qui permetterait de réduire la dimension de celle-ci et d’affiner les clusters. - Considérer la variance de chaque pixel.


Reconnaissance

Chaque image est comparée à l’ensemble des clusters obtenus lors de l’étape précedente suivant la distance des moindres carrés. Les k voisins les plus proches de labels identiques définissent le label du caractère testé ( Algorithme KNN).

D’autres distances ont cependant étét testé mais celles-ci ont présenté de moins bon résultat : - Avec prétraitement, squeletisation et distance de Chamfer (PSK) - Avec prétraitement et squeletisation (PS)

Reconnaissance.png

Afin d’améliorer la reconnaissance de caractères nous avons aussi utilisé la position du caractère dans la ligne. Ainsi, en ajoutant cette information, un "0" n'est plus confondu avec un "o".

Position.png

Un texte qui était précedemment reconnu comme : “A1ice waS beginning tO get Very tired” est maintenant interprété comme “Alice was beginning to get very tired”

Post-traitement

Modèle de Markov caché

La chaine de caractères obtenus présente des défauts rendant le texte incompréhensible, il est alors nécessaire d’adapter la reconnaissance pour corriger certains successions de lettres. Cependant chaque langue possède ces propres particularités, c’est pourquoi nous avons choisi de nous concentrer sur des textes anglais et de considérer les successions de lettres dans cette langue.

HMM.png

Les états cachés sont les lettres réelles constituant les mots, les états observés sont les lettres obtenues à la fin de la reconnaissance. L’algorithme de Viterbi permet de calculer le mot le plus probable en prenant en compte la succession des lettres en anglais mais aussi les erreurs habituelles du classifier. Ces erreurs sont calculées en prédisant les labels de la base de données et en notant quels sont les caractères reconnus. Ainsi, nous obtenons sur la phrase : “A1ice has got a book.” -> “Alice has got a book.”

Distance de Levenshtein

Certains mots peuvent toutefois présentés des erreurs, même si ils ont une consonance anglaise, ils peuvent ne pas exister dans la langue, il est alors nécessaire de vérifier dans le dictionnaire anglais leur bonne écriture. Pour se faire, nous calculons les distances entre les mots du dictionnaire et le mot obtenu via la distance de Levenshtein qui autorise des délétions et des insertions.


Formatage

La partie formatage est la partie la plus légère. En effet, nous avions conscience de la difficulté et du temps que nous prendrais les autres parties. Nous avons donc implémenter qu’une première solution simple pour permettre le découpage en paragraphes et en mots. Pour cela nous avons effectué une moyenne sur tous les espacements trouvés sur une image, verticalement pour la recherche de mots et horizontalement pour la recherche de paragraphes. Nous supposons ensuite qu’un mot ou un paragraphe est caractérisé par un espacement plus grand que la moyenne (non pondérée par le nombre d’espace trouvé ayant X pixels de large). Cette implémentation est cependant très limité. En effet, elle est très sensible au changement de taille de police (une plus grande taille de police implique une plus grande hauteur d’interligne ce qui peut fausser les résultats si deux paragraphes contiennent deux polices/tailles différentes). Le découpage en mot est également sensible aux polices qui sont cursives et rend la détection d’espaces plus complexe (la barre d’un ‘y’ en début de mot de décalant suffisamment vers la gauche pour diminuer l’espace entre les mots)

Conclusion

Problèmes rencontrés

Perspectives

Références