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

f. L'approche proposée par Chen et Lopresti22

Soulignant l'importance de la détection de tableaux dans un document manuscrit non ligné et contenant toutes sortes de bruits, Chen et Lopresti proposent une méthodologie en quatre étapes permettant de résoudre ce problème. Il s'agit de :

· L'étape du prétraitement : Cette étape comprend :

o L'élimination des ombres sur les bordures de la page : marche à suivre :

· Appliquer la transformation en distance à l'image d'entrée ;

²² Op. cit.

·

30

Comme dans l'image transformée les régions ombragées possèdent habituellement des valeurs de distance très élevées, binariser la page en des demis-noyaux résiduels en utilisant un seuil ;

· à partir de ces noyaux, mesurer l'augmentation du nombre de pixels à chaque itération, tout en diminuant le seuil ;

· à partir d'une augmentation soudaine de ce nombre, estimer le seuil qui exclura mieux les ombres de bordure.

o La détection de lignes dominantes (se chevauchant souvent avec l'écriture) : marche à suivre :

· Estimer l'inclinaison de la page en calculant la moyenne des inclinaisons des lignes horizontales si elles sont présentes sur la page ;

· A l'aide de la classique transformation de Hough, projeter chaque point sur un ensemble des points de courbe sinusoïdale dans le plan (ñ,è) (l'espace de Hough) ;

· Dans chaque itération, sélectionner un point au hasard du reste de l'ensemble de points, calculer sa courbe sinusoïdale dans l'espace de Hough et mettre à jour la matrice d'accumulation ;

· Si le seuil est dépassé alors rechercher dans chaque direction, à partir de la position courante, les points d'extrémité du segment de ligne. N.B : comme les lignes dominantes peuvent être dégradées, les petites lacunes (jusqu'à 15 pixels) sont tolérées ;

· Dès que la recherche s'arrête, enregistrer les coordonnées des points d'extrémité du segment de ligne, exclure les points correspondants de la matrice d'accumulation et procéder avec l'itération suivante.

· L'étape de classification de texte : Elle comprend :

o La division de la page en des petits carreaux de même taille ;

o L'extraction des caractéristiques des carreaux en vue de leur classification par la Machine à Vecteur Support (SVM) :

· L'extraction des caractéristiques :

· Utiliser les caractéristiques structurelles comme le Gradient de Concavité Structurel (GSC) pour capturer les caractéristiques

31

de forme telles que les boucles, les points de ramification, les

points de terminaison et les points.

N.B : Ces caractéristiques de multi résolution combinent trois attributs de forme de texte différents :

- les gradients qui représentent l'orientation locale des traits ;

- l'information structurelle qui étend le gradient à des distances plus élevées et qui fournit l'information à propos des trajectoires de traits ;

- les concavités qui capturent les relations entre traits à des distances plus élevées.

n La classification des textes : utiliser l'outil libSVM²³ pour classifier les carreaux contenant du texte et ceux n'en contenant pas.

n L'étape de détection de tableau : Après avoir identifié les carreaux de texte a travers la classification SVM, procéder comme suit :

o Utiliser les projections horizontales de profils afin de repérer les lignes de texte formant probablement les rangées du tableau.

o Estimer la hauteur H de lignes de texte en examinant la séquence des pics dans la projection horizontale de profils.

o Utiliser H pour fixer les limites de chaque ligne de texte.

o Exclure les lignes candidates insignifiantes contenant moins de 5 carreaux de texte.

o Appliquer l'algorithme de programmation dynamique (proposé par Hu²⁴) adapté²⁵ et décrivant une manière optimale de décomposer une page entière en un certain nombre de tableaux présentant une similarité de mesure entre les rangées individuelles. En langage mathématique, cet algorithme qui permet de détecter les tableaux du document, présente les grandes lignes (équations) suivantes :

merit_pre(i, [i + 1, j]) = ~x eY(xli_,) X Incorr(i, k) ; (1)

²³ LibSVM désigne un package contenant l'implémentation des Machines à Vecteur Support.

²⁴ Hu J. et al., «Medium Independant Table Detection», in Document Recognition and Retrieval VIII(IS&T/SPIE Electronic Imaging, 2001, pp. 44 - 55.

²⁵ Au fait, l'algorithme a été légèrement modifié par Jin Chen et Daniel Lopresti afin de permettre le calcul correct et sans erreur de la corrélation entre les rangées d'un tableau.

32

merit_app([i, j - 1], j) = E k-ti er(ili-k) x Incorr(k,j) ; (2)

merit_pre(i, [i + 1,j]) + tab[i + 1, j]

tab[i, j] = max (3)
tab[i, j - 1] + merit_app([i, j - 1], j)

avec 1 <_ i < j <_ n ;

tab[i,i] = 0 1 <_ i <_ n ; (4)

tab[i, j]

score[i, j] = max = (5)
ma5.>,?+@score[i, k] + score[k + 1, j]A

avec 1 <_ i < j <_ n ;

score[i, i] = tab[i, i] 1 <_ i <_ n ; (6)
Les équations ci-dessus signifient successivement :

(1) : Le mérite de joindre la ligne i au tableau s'étendant de la ligne i+1 à la ligne j. Ce mérite se calcule par la sommation de la décroissance des corrélations internes des espaces entre deux lignes de texte ou deux carreaux de texte (Incorr(i, k)).

(2) : Le mérite d'ajouter la ligne j au tableau s'étendant de la ligne i à la ligne j - 1. Ce mérite se calcule aussi par la sommation de la décroissance des corrélations internes des espaces entre deux lignes de texte ou deux carreaux de texte (Incorr(k, j)).

(3) : Le score obtenu en interprétant les rangées i à j comme faisant partie d'un même tableau. Ce score est calculé soit en joignant la première rangée Row[i] commencement de tab [i +1,j], soit en ajoutant la dernière rangée Row[j] à la fin de tab[i ,j - 1] ;

(4) : La condition de limitation ;

(5) : Le meilleur moyen d'interpréter les lignes i à j comme constituant un certain nombre de tableaux. En fait, cette équation exprime la décomposition de la page en un certain nombre de tableau.

(6) : La condition de limitation.