Caractérisation et extraction informatique de la structure d'un tableau par une méthode implémentant un réseau de neurones

1.2.2. Méthodologies, algorithmes et techniques utilisés

Dans le domaine de la reconnaissance de tableaux, nombreuses méthodes ont été proposées par différents auteurs selon le type de reconnaissance à réaliser. Parmi ces multiples approches, nous avons retenu quelques unes qui nous ont semblés plus pertinents et qui ont produit des résultats plus ou moins fiables.

a. L'approche proposée par Laurentini et Viada12

Cette approche consiste en l'utilisation d'un algorithme s'articulant sur des procédures de compréhension et d'identification d'un tableau en vue de la construction d'un « tableau idéal ». La phase de compréhension de l'algorithme se résume à détecter les blocs de texte arrangés dans des modèles réguliers horizontaux et verticaux. La phase d'identification, elle, consiste à identifier les lignes horizontales et verticales en comparant leurs positions relatives.

Plus concrètement, les grandes lignes de cet algorithme s'énoncent dans les étapes suivantes :

· Lire l'image du document scanné ;

· Calculer les composants connectés de l'image ;

⁹ Shahab A. et al., An open approach towards the benchmarking of table structure recognition systems, Kaiserslautern, 2010, p.1

¹⁰ Chen J. et Lopresti D., «Table Detection in Noisy Off-Line Handwritten Documents» in IEEE, University Bethlehem, 2011, pp 399-403.

¹¹ Support Vector Machine ou `'Machine à Vecteur Support»

¹² Op. cit.

·

17

Calculer l'histogramme de taille des boîtes de contour pour tous les composants noirs de l'image ;

· Trouver la zone la plus peuplée dans cet histogramme, _Amp étant le nombre de composants dans cette zone ;

· Calculer la moyenne de l'histogramme et laisser _Aavg être le nombre de composants ayant cette taille moyenne ;

· Fixer un seuil pour la taille des boîtes de contour (ou boîtes d'encadrement), S1=n X max (Amp, Aavg) ;

· Fixer un seuil pour la longueur maximum des boîtes de contour, S2 ;

· Filtrer les composants noirs connectés, en ajoutant à la zone de texte tous ceux ayant

une surface inférieure à S1, un ratio na gear dans l'intervalle[ , S₂], les autres

largeur

composants étant ajoutés à la zone de graphiques ;

· Trouver les lignes verticales et horizontales :

o Fixer un seuil de densité S3=dimension moyenne des caractères ;

o Initialiser I à 0 ; (avec I : intervalle entre pixels noirs)

o Parcourir l'image horizontalement et verticalement tout en tenant compte de

la condition suivante :

Si I<S3 alors

Lire pixels noirs de l'image ;

Calculer I=intervalle entre pixels noirs du parcours ;

FinSi

o Fusionner les parcours suffisamment proches l'un de l'autre pour obtenir des lignes horizontales et verticales.

· Fusionner en mots tous les caractères colinéaires satisfaisant des conditions géométriques adéquates ;

· Fusionner ensuite les mots en phrases ;

· Identifier une zone rectangulaire contenant des lignes droites susceptibles d'appartenir à un tableau (au moins une ligne horizontale et une ligne verticale sont requises) ;

· Fixer le seuil de connexion S4 ;

· Connecter les lignes trouvées en fonction du seuil S4 ;

·

18

Effectuer quelques ajustements dur les lignes pendantes et celles dont les bouts sont proches d'autres lignes ;

· Eliminer les zones n'appartenant pas au tableau en effectuant un test qui consiste en la comparaison des distances entre deux lignes horizontales adjacents, avec un intervalle de distance interdite relative à la hauteur du caractère ;

· Comparer l'arrangement de lignes précédemment déterminé avec celui des blocs de texte identifiés dans la même zone en vérifiant leur compatibilité ;

· Vérifier le périmètre du tableau et de chaque cellule ;

· Considérer les profils de projections horizontales et verticales des blocs de texte ;

· Si les blocs de texte ne sont pas arrangés suivant un modèle régulier, alors la construction du tableau échoue ;

· Sinon, ajouter des lignes droites horizontales et verticales pour construire le tableau idéal en considérant les profils de projection et les courtes lignes droites possibles dans les interstices de profil ;

· Lire et envoyer au programme OCR, les informations relatives à la dimension et à la position de chaque cellule du tableau pour la reconnaissance du texte.