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

d. La méthodologie de Shin et Guerette16

Focalisant leur attention sur des tableaux au contenu textuel, Shin et Guerette pensent que la localisation des blocs de texte contenus dans les cellules, le regroupement de ces blocs dans des colonnes ainsi que l'examen des relations spatiales entre ces colonnes permettrait la reconnaissance facile des tableaux. Ils proposent ainsi une approche consistant en deux étapes successives, à savoir : la recherche des zones (ou blocs) de texte et l'identification du tableau.

· La recherche des zones de texte :

Pour trouver les boîtes délimitant les textes du tableau en zones, ces deux auteurs proposent l'utilisation de la méthode de « croissance de région », dont les grandes lignes de l'algorithme s'énoncent comme suit :

· Lire l'image d'entrée en niveau de gris ;

· Déterminer un seuil d'intensité en utilisant une adaptation de l'algorithme de regroupement ISODATA¹⁷ ;

· Utiliser le seuil ainsi obtenu pour binariser l'image (une intensité pour le fond et un autre pour le texte) ;

· Créer un histogramme des longueurs de bandes horizontales de pixels d'arrière-plan entre des pixels de texte ;

· Trouver la longueur la plus commune ;

· Examiner et compter les longueurs de plus en plus longues de l'histogramme, au-delà de la longueur la plus commune ;

· Si le nombre de la première longueur d'espaces blancs est inférieure à la moitié du nombre de la longueur d'espace blanc la plus commune ;

· Alors choisir ce nombre comme montant de dilatation ;

· Dilater horizontalement toutes les lettres afin que tous les caractères soient connectés dans la plupart de mots ; c'est à dire, marquer les nombreux pixels à

¹⁶ Op. cit.

¹⁷ Voir le pseudo code de l'algorithme ISODATA en Annexe.

26

droite de chaque pixel de texte de l'image original comme étant aussi des pixels de texte ;

· Appliquer l'algorithme de croissance de région¹⁸ pour placer des boîtes limitatrices autour de chaque région de pixels de texte liée (le bord le plus à droite de la boîte limitatrice étant ajustée à gauche par le montant avec lequel les pixels de texte ont été dilatés plus tôt, de sorte que les boîtes limitatrices soient autour du texte original et non le texte dilaté) ;

N.B : Lorsque l'image contient un tableau avec un contour, il en résulte une zone de délimitation qui entoure le tableau en plus d'un cadre de délimitation pour chaque mot dans le tableau.

· Détecter cette boîte extérieure en marquant tous les cadres de délimitation dont la hauteur est supérieure à la hauteur moyenne de toutes les boîtes limitatrices, et en les testant afin de déterminer si oui ou non elles contiennent des petites boîtes limitatrices ;

· Garder une trace de toutes ces "grandes" boîtes limitatrices et les petites boîtes limitatrices qu'ils contiennent, car ils sont susceptibles de former un tableau.

· L'identification de tableaux

Après l'avoir implémenté pour l'identification de tableaux, Shin et Guerette remarquent que l'algorithme de Kieninger¹⁹ présente quelques insuffisances. Ils en proposent ainsi une version modifiée dont les grandes lignes sont les suivantes :

· Lire la liste des boîtes limitatrices qui ne sont pas de « grandes » boîtes limitatrices ;

· Prendre la première boîte de la liste comme boîte-échantillon et la bouger de haut en bas selon sa hauteur pour vérifier si aucune boîte de la liste dépasse la région définie par la boîte - échantillon ;

· Si la hauteur de la boîte - échantillons est inférieure à la moyenne des hauteurs des boîtes limitatrices, alors égaliser les deux auteurs ;

¹⁸ Voir l'Algorithme de croissance de région en Annexe

¹⁹ Kieninger T. V., «Table Structure Recognition Based on Robust Block Segmentation» in Proceedings of Document Recognition, volume V., San Jose, CA, 1998, pp 22-32.

·

27

Si la boîte - échantillon possède au maximum une boîte limitatrice qui le dépasse en haut et une autre qui le dépasse en bas, et que les boîtes du dessus et celles d'en bas ne sont pas alignées horizontalement, alors

· Placer ces boîtes dans le même groupe que la boîte - échantillon et augmenter la taille verticale de cette dernière afin de trouver d'autres boîtes susceptibles d'être liées ;

· Répéter l'étape précédente jusqu'à ce que le programme ne trouve plus de boîtes à ajouter au groupe (ici, la boîte - échantillon dont la taille a été augmentée) ;

· Répéter la procédure ci - dessus sur d'autres boîtes limitatrices considérées comme non encore examinées jusqu'à ce que toutes les boîtes limitatrices soient groupées ou trouvées comme n'appartenant à aucun groupe ;

N.B : Les groupes ainsi constituées représenteront les colonnes du tableau.

· Marquer les boîtes ainsi groupées comme étant de Type1 et les autres comme étant de Type2.

· Pour chaque boîte limitatrice de Type2, calculer la distance entre elle et ses voisines horizontales ;

· Calculer le seuil pour la distance horizontale entre les boîtes limitatrices en utilisant le même algorithme utilisé plus tôt pour calculer le montant à partir duquel il fallait dilater les pixels de texte, à la seule exception qu'ici on examine la distance entre les boîtes limitatrices au lieu des barres horizontales ;

· Si la distance est inférieure au seuil, la boîte - échantillon et ses voisines concernées sont réunies en une seule boîte, et la distance entre la nouvelle grande boîte et ses voisines concernées est calculée pour déterminer si d'autres boîtes peuvent être unies à elle ou non ;

· Répéter la procédure précédente jusqu'à ce que toutes les boîtes limitatrices soient examinées réunies si nécessaire ;

· Après avoir terminé la jointure horizontale, appliquer le même algorithme utilisé pour trouver les groupes de Type1 sur le nouvel ensemble de boîtes limitatrices.

· Comparer tous les groupes de Type1 finalement trouvés ;

· Marquer tout groupe contenant des boîtes limitatrices alignées verticalement comme appartenant à un tableau.

28

e. Les méthodes proposées par Kawanaka ²⁰

Consacrant leurs recherches à la résolution d'un cas concret observé à l'hôpital de l'Université de Mie²¹, Kawanaka et son équipe se sont posés la question de savoir « comment automatiser la recherche des cas analogues de traitement de maladies à partir des fiches des patients ayant déjà été soignés dans cet hôpital ? )) La réponse à cette question a amené les auteurs à décomposer le problème général en trois sous - problèmes, à savoir :

· La reconnaissance des documents (ici, les fiches - formulaires des patients ayant déjà subi un traitement quelconque) ;

· L'extraction des mots-clés et

· La génération automatique des résultats au format XML

Pour résoudre ces problèmes, Kawanaka et son équipe proposent ainsi une méthodologie basée sur une connaissance à priori du document principal que le système prendra pour « modèle de document à reconnaître)). L'essentiel de cette méthodologie s'articule sur les étapes suivantes :

· Obtention des images des documents (les fiches - formulaires des patients) via un capteur (scanneur) avec une résolution de 300 dpi ;

· Réduction des bruits et inclinaisons de l'image par prétraitement ;

· Identification des structures du tableau ;

· Reconnaissance et conversion des caractères du tableau en données textuelles par le moteur OCR ;

· Génération des documents XML à partir des résultats obtenus.

Ci-après, la schématisation du système implémentant la méthodologie proposée :

²⁰ Op. cit.

²¹ Une ville du Japon.

29

Fig. 2. Schéma du système de recherche des cas analogues selon Kawanaka