Projet de Morphologie Mathémathique (I3M)

Segmentation d'un Texte

Sujet : A partir d'une page de texte scannée, séparer les paragraphes, colonnes, graphiques et équations, en vue d'une description par blocs.
Groupe : THIERRY Jérôme, BEASSE Luc, GRAIL Jean-Sébastien.

I. Préliminaires

Etant donné que les images proposées sont de taille importante, de l'ordre de 1600x2400, nous avons extrait 3 sous-images de ccitt5.ima, contenant des informations de natures différentes :

Pour cette dernière, l'échelle a été divisée par deux pour obtenir des caractéristiques de taille des différentes structures comparables aux images extraites de ccitt5.ima (en particulier, pour les espaces entre mots et entre lignes du texte).
Remarque : les images sont inversées par rapport aux originales pour obtenir les formes du texte en blanc sur fond noir. Toutes les images sont binaires.

II. Analyse des structures

L'analyse des structures consiste à définir des caractéristiques propres afin d'établir des opérations morphologiques (choix et taille des éléments structurants) appropriées au traitement de chaque structures.

1) Segmentation progressive des structures

Dans un premier temps nous cherchons à identifier les structures suivantes : les graphiques encadrés, les paragraphes de texte, les formules mathémathiques (en dehors du texte). Nous obtenons donc, quatre catégories de structures (une étiquette est attribuée au reste) que nous segmentons séquentiellement à l'aide de masques. Nous commençons par les structures les plus remarquables (facilement identifiables) et nous les éliminons au fur et à mesure de la segmentation pour s'attacher aux structures de plus en plus fines.

2) Caractéristiques des structures

  1. Les figures : sachant que dans l'image proposée, les figures sont en majorité encadrées (voir l'image ccitt-s3 pour le traitement particulier), nous nous proposons d'identifier le cadre constitué de long segments verticaux et horizontaux pour définir un masque de la figure. Par ailleurs, cadre excepté, une figure se différencie naturellement du reste des structures (texte) par le fait qu'elle est constituée principalement de traits (dessin schématique). La grande figure non-encadrée de l'image ccitt5-s3 sera extraite d'après cette constatation.
  2. Les paragraphes de texte : sachant qu'un paragraphe est constitué d'au moins deux lignes, le but du traitement consiste à regrouper les lettres, les mots et les lignes afin d'obtenir un bloc compact d'une seule composante connexe, facilement identifiable d'une ligne d'équation par exemple. Ici, ayant préalablement retiré les figures (grâce au masque d'identification), nous tirons parti qu'un inter-ligne est plus petit que l'espace entre une ligne d'équation et le paragraphe afin de ne pas inclure l'équation dans le bloc de texte. Le bloc ainsi obtenu constitue le masque d'identification du paragraphe.
  3. Les équations : les lignes d'équations constituent, désormais, les composantes connexes (fermeture) les plus large horizontalement. Pour les identifier, on utilise donc un élément structurant linéaire horizontal suffisamment large pour ne retenir qu'un morceau de la ligne d'équation. Une reconstruction géodésique nous permet de constituer le masque des équations.
  4. Autres : ce qui reste est regroupé dans une classe non-identifiée. Si la reconnaissance des strucures est bonne, comme dans le cas de la premiére image ccitt5-s, il reste simplement le numéro de la figure (fig. n) ou bien des morceaux de texte appartenant à la figure non-encadrée (ccitt5-s3) que l'on pourra éventuellement joindre au masque des figures. Pour facilement reconnaitre les différentes structures, nous proposons de reconstruire une image des étiquettes de couleurs différentes, à partir des masques d'identification.

III. Principales étapes de l'algorithme

Nous avons tout d'abord inversé l'image pour que le texte soit en blanc et que les opérations morphologiques agissent sur ce dernier.

1-Extraction des figures

On ferme l'image originale par une boule de taille deux pour reconnecter les lignes qui pour des raisons de format auraient perdu leur connexité (image 1). On fait une ouverture linéaire horizontale de taille 80 pour sélectionner les grandes lignes horizontales (image 2). De même on fait une ouverture de l'image 1 par une ligne verticale de taille 30 que l'on dilate avec une boule de taille 1 toujours pour des raisons de connexité (image 3). On fait un "ou binaire" entre 2 et 3. On a alors extrait les cadres et plus généralement les grandes lignes verticales et horizontales (image 4).

On fait une reconstruction géodésique de image 4 dans image1. Ceci sert pour les figures non encadrées : on reconstruit ainsi toute la partie de la figure connexe aux grandes lignes détectées. Maintenant on remplit la composante connexe -- avec holefill. On a le cadre plein ou la figure pleine (image 5).

Un "ou exclusif" entre l'image 5 et une image à 255 inverse l'image 5. Maintenant en faisant un "et" entre l'inverse de 5 et l'image originale, on obtient l'image initiale sans les figures que l'on vient de détecter (image 6).

On remarque que pour obtenir les figures il suffit de soustraire l'image 6 à l'image originale (image 7).

2-Extraction du texte

On ferme l'image 6 par une ligne de taille 10 pour que chaque ligne de texte ne donne qu'une bande sur toute sa longueur. Puis on ferme l'image obtenue par une ligne verticale de taille 5 ce qui réunit toutes les lignes du paragraphe en une seule composante connexe (image 8).

On ouvre l'image 8 par une boule de taille 10 pour ne sélectionner que les grosse composantes connexes (image 9). On élimine ainsi les "fig. n" et les formules. cependant certaines formules sont trop épaisses et pour les faire disparaitre totalement, on ouvre image 9 par une ligne horizontale de taille 30 (image 10). Ce dernier point est illustré dans Résultats/Image ccitt-s2.gif.

On dilate géodésiquement image 10 dans image 8 pour retrouver l'intégralité des composantes connexes correspondant aux paragraphes (image 11).

De même que pour l'extraction des figures, on fait un "ou exclusif" puis un "et" astucieusement choisis pour soustraire à l'image 6 les paragraphes que l'on vient de détecter (image 12). Cette dernière image correspond à l'image originale à laquelle on a retranché les figures et les paragraphes. On construit alors l'image des paragraphes en soustrayant l'image 12 à l'image 6 (image 13).

3-Extraction des formules

On considère qu'il ne reste que les formules et des petits bouts de texte dans l'image 12. On la ferme par une boule de taille 10 (image 14), puis on ouvre par un segment horizontal de taille 30 (image 15). On reconstruit géodésiquement l'image 15 dans l'image 14 pour retrouver tout le cache de chaque formule.

Comme dans les deux paragraphes précédents on enlève à l'image 12 les formules (image 16). On conserve les figures dans image 17.

Alors on reconstruit les zones non détectées en faisant un "et" entre image 16 et l'image originale (image 18). Finalement une simple addition des images 6, 12, 16 et 18 avec des couleurs différentes donne les images séparées que l'on peut observer dans Résultats.

IV. Résultats

Pour évaluer les résultats, étudions l'effet produit par l'algorithme sur les quatre images dont il est question dans les Préliminaires.

1-Image ccitt-s.gif

Nous avons fait tourner l'algorithme sur cette image. Le rouge correspond aux figures, le bleu aux paragraphes, le vert aux formules et le violet à ce qui n'a pas été détecté par les trois grandes étapes de l'algorithme. Le résultat obtenu est le suivant :

2-Image ccitt-s2.gif

L'image de droite est le résultat si on ne fait pas l'ouverture par une ligne horizontale de taille 30 après l'ouverture par une boule de taille 10 lors de l'extraction du texte. Ici, la seconde formule a été identifiée comme un paragraphe car ce qui est en crochet est trop épais pour disparaitre avec une ouverture par une boule de taille 10. Par contre en faisant l'ouverture par le segment -- voir l'image ci-dessous -- la seconde formule est bien identifiée comme telle. On voit cependant que le texte d'une ligne est identifié comme une formule. Mais ceci est inévitable car elle a les mêmes propriétés morphologiques qu'une formule. Nous ne pouvons donc pas corriger cette erreur si ce n'est de manière artificielle et donc non robuste.

3-Image ccitt-s3.gif

L'image de droite représente le résultat de l'algorithme sans la reconstruction géodésique avant le remplissage (holefill) au moment de l'extraction des figures. On voit que l'on perd ainsi une partie de la figure. Par contre avec la méthode complète, on détecte toute la figure sauf des petits bouts de texte non connexes à cette dernière. Ceci se vérifie dans l'image ci-dessous.

Les petits bouts de texte mal identifiés pourront être inclus dans le masque de la figure par des opérateurs non-morphologiques très simples, par exemple par reconstruction du cadre englobant la figure. Les méthodes purement morphologiques semblent donc assez peu intéressants.

4-Image lettre_d2.gif

Voyons maintenant ce que donne notre algorithme sur l'image suivante assez différente de celles à partir desquelles l'algorithme a été élaboré.

Le résultat semble assez bon du point de vue de la segmentation. Les parties de natures différentes ont bien été séparées.

V. Critiques, commentaires et améliorations de la méthode

Cette méthode n'est pas unique pour résoudre le problème posé. Nous avons simplement cherché à reproduire algorithmiquement l'analyse progressive des structures décrite plus haut. D'autre part, nous n'avons pas considéré la contrainte de rapidité de temps de calcul. Il est possible, notamment d'éliminer un certain nombre d'opérations qui semblent communes à chaque étape de reconnaissance de structure en considérant plus précisemment l'influence globale d'une opération de fermeture, par exemple, au lieu de recommencer pour chaque étape avec l'image d'origine (ou presque) moins les structures décelées. Notre approche est donc locale et l'influence des opérations à été étudiée seulement dans le but d'isoler une structure bien particulière. Dans cette optique, l'ordre de segmentation à été choisi dans le sens d'une augmentation des opérations pour identifier une structure de moins en moins bien définie morphologiquement.
Certaines erreurs persistent donc, faute de pouvoir identifier finement des structures proches. Par exemple, dans l'image ccitt5-s2, la première ligne de texte isolée est prise pour une équation car cette ligne est séparer d'un paragraphe (un bloc de texte) et sa longueur est semblable à celle d'une ligne d'équation. Sachant qu'une équation est généralement centrée tandis que le texte commence plutôt à gauche, la position de la composante connexe nous permettrait de poser un doute sur l'attribution de l'étiquette "équation" pour cette ligne de texte isolée. Il resterait donc à pousser plus finement ce genre d'analyse dans la description des structures pour séparer des structures proches en forme.

VI. Conclusion

Bien que la Morphologie Mathématique se prète relativement bien à l'analyse d'un texte standard comme l'image ccitt5.ima, pour que la méthode soit valable dans un cas plus général, il faudrait adapter dynamiquement les tailles des éléments structurants aux caractéristiques globales du texte à segmenter. Aussi, il serait intéressant de faire une étude préalable des espacements entre mots (entre lettres), des inter-lignes, des espaces entre un paragraphe et une figure ou une équation. En voulant appliquer l'algorithme sur l'image de la lettre, nous avons, en effet, remarqué que l'échelle était importante.
Bien sur, il serait stupide de vouloir obtenir une étude complète des structures du texte par des opérations de Morphologie Mathématiques lorsque des opérations simples et plus rapides peuvent s'appliquer. Pour calculer les marges de la page, par exemple, un simple histogramme horizontal nous permet, d'une part, de séparer les colonnes (la ligne verticale forme un pic) et d'autre part, de calculer la marge à gauche et à droite, tandis que l'histogramme verticale nous donne la marge de haut et bas de page, ainsi que des informations sur les espacements entre les differentes structures (trous dans l'histogramme). D'autres méthodes non morphologique peuvent donc rendre ce travail plus précis.
Enfin, il est à noter que l'algorithme à été testé sur des images binaires et sans bruit fort, ce qui définit un champs d'application restreint. Cependant, pour rendre ce type d'algorithme plus robuste au bruit et compatible avec un plus grand nombre de pages de texte (mise en page différente), d'autres opérations (morphologiques) peuvent être rajoutées, de la simple ouverture par un petit élément pour éliminer les pixels bruités à des opérations plus complexes comme la recherche des titres de sections ou des formules situées dans un paragraphe de texte.
Pour conclure, cet algorithme ne constitue, donc, qu'un point de départ et une mise en forme des idées que l'on peut avoir pour aborder le problème de la reconnaissance de structures d'un texte par une approche morphologique.