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

3.3.1. L'étape du prétraitement

Après l'acquisition de l'image via un scanneur, cette étape est d'une importance capitale dans la mesure où elle réduit le nombre d'étapes de l'algorithme principal du système de reconnaissance. Et, dans notre cas, l'algorithme principal est celui d'extraction des caractéristiques du tableau. Ainsi, selon la qualité de l'image d'entrée, plusieurs étapes peuvent être nécessaires avant d'extraire les caractéristiques d'un tableau dans une image. Parmi ces nombreuses étapes, nous avons retenus trois qui nous ont semblé plus importantes, à savoir : la réduction de la taille et la binarisation.

3.3.1.1. Réduction de la taille de l'image:

Cette étape permet de conserver les dimensions de l'image d'entrée dans des proportions imposées par les neurones de la première couche, à savoir 300 X 300 (c'est - à - dire, 300 pixels en hauteur et 300 pixels en largeur).

3.3.1.2. Binarisation de l'image:

Appelé aussi `'seuillage simple», la binarisation est une étape qui consiste à mettre à zéro tous les pixels niveau de gris inférieur à une certaine valeur (appelée seuil, en anglais `'treshold») et à attribuer la valeur maximale aux pixels ayant une valeur supérieure au seuil. Le résultat en est une image binaire contenant des pixels noirs et blancs. Dans le cas des images contenant des tableaux, la binarisation permet d'accentuer les tracés des lignes et des colonnes ainsi que d'autres objets sur l'image, rendant ainsi leur identification moins difficile. Néanmoins, une difficulté demeure au niveau du choix du seuil à utiliser. Pour palier à cette difficulté, nous nous sommes proposé de calculer ce seuil en nous appuyant sur les considérations du chapitre précédent concernant le problème de la reconnaissance des tableaux.

Calcul du seuil:

Nous savons que le seuil dépend de la qualité des couleurs de l'image, c'est - à - dire des niveaux de couleurs contenus dans chaque pixel lu. En outre, le seuil est celui qui nous donne le niveau de couleur qui maximise la probabilité de détecter les pixels appartenant au tracé du tableau. Ce seuil sera donc donné par : S = arg min P(T)

avec P(T) = [0,y]

[0,255] : la probabilité de détecter les pixels appartenant au tracé du tableau.

y : le niveau de couleur permettant de détecter un pixel appartenant à au tracé du tableau.

Soit x le niveau de couleur lu sur l'image. En nous référant à la théorie des 2 clients (cf. Chapitre II), lorsque nous nous plaçons dans la situation du premier client, nous observons que la décision `'tracé de tableau» est soumise à la condition suivante :

p(T|y) = p(T |y)

10

+ p(T) p(y|T)

p(T)p(y|T)

? 10

p(T)p(y|T) + p(T )p(y|T ) p(T)p(y|T)

p(Tf)p(y|Tf)

=

f

59

? 10p(T)p(y|T) = p(Tf) p(y|Tf)

p(T) = p(Tf)p(y|Tf) ?(***)

10p(y|T)

Calculons les termes de (***):

1°) p(T) =

[h,] = /1

[h,2VV] 2V] (a)

2°) p(T^f) = [/1,2VV] = 2VV2 (avec y > 0) (b)

[h,2VV]

V]

3°) p(y|T^f) = 1/4(n3/4) = 3/4

/1/|À22VV| 2VV2

* 256 (c)

4°) p(y|T) = 1/4(n3/4) = |À2| * 256 (d)

3/4 /1

Â.Ä

Ainsi, (***) devient : a = ~****~

h

En substituant a,b,c et d par leurs valeurs dans (****), nous obtenons :

2ÅÅ"Æ * ÆÈ$È|É"~ÅÅ|

2ÅÇ 2ÅÅ"Æ

1h|É"Æ| ÆÈ$

*2V]

* 2V]

/1 = V]

/1 ?=

~

ÆÈ$È|É"2ÅÅ|

$

_1h|É"Æ| ÆÈ$

?10|x - y| - y = 1 + |x - 255| (i *)

Ici, 2 cas peuvent se présenter :

1er cas : x - y > 0 . Dans ce cas, (i *) devient :

1hÀ2|À22VV|21

10x - 11y = 1 + |x - 255| ?Ê = ~~~ *~

~~2ème cas : x - y < 0 . Dans ce cas, (i *) devient :

-10x + 9y = 1 + |x - 255| ? Ê = ~hÀ/|À2~VV|/~ ~~~~ *~

i

En tenant compte du fait que nous sommes à la recherche d'une valeur du seuil S inférieure à y et à ne pas dépasser, nous rejetons donc (iii *) et nous gardons(ii *). Ainsi, le seuil sera donné par la valeur de y qui minimise(ii *), c'est-à-dire :

S = Ê =

10x - |x - 255| - 1

(4i. *)

11

60

3Ëe( x : le niveau de couleur le plus élevé de tous les pixels de l'image.

3.3.2. L'étape d'extraction des caractéristiques du tableau.

Toute cette étape est exécutée par le réseau de neurones et se subdivise en deux phases essentielles, à savoir : la détection du tableau et la compréhension de la structure du tableau. De plus, l'essentiel des procédures de cette étape repose sur le codage du gradient

morphologique des éléments de structuration d'un tableau tel que schématisé dans la figure suivante :

1 2 3

4 5 6

7 8 9

10 11

61

Fig. 9. Codage des éléments de structuration d'un tableau sur 3X3 pixels 1ère phase : Détection du tableau

L'objectif de cette phase est d'arriver à localiser les éléments de structuration du tableau

contenu sur l'image du document. Pour ce faire, le réseau de neurones implémente

l'algorithme suivant :

- Au niveau de la rétine (par neurone) :

Initialiser chacun des poids w. à 1 ;

Fixer le seuil 8 à 0 ;

Recevoir les instances de niveaux de gris x₁ , x₂ et x₃ ;

62

Appliquer la fonction d'activation f(x) = signOEw.x1

M - 8) ; (fonction linéaire à seuil)

.-1

Calculer la valeur de sortie du neurone : sort = sign(w1x1 + _w2x2 + w3x3 - 8) ;

- Au niveau du gradient (par neurone) :

Initialiser chacun des poids w.1 à 1 ;

Recevoir la matrice E [][] contenant les sorties de neuf neurones de la rétine ;

Calculer la valeur de sortie du neurone du gradient selon le cas :

Si ? E[i][j]wÏÐ == 3 (avec i = 0, 1 ou 2 V j

~ ) alors sort=10 ;
+-0

Si ? E[i][j]wÏÐ == 3 (avec j = 0, 1 ou 2 V i

~ ) alors sort=11 ;
.-0

Si ((E[2][1]w21 + E[1][1]w11 + E[1][2]w12 == 3) et (E[0][0]w00 + E[1][0]w10 +
E[2][0]w20 + E[0][1]w01 + E[0][2]w02 + E[2][2]w22 == 0)) alors sort=1 ;

Si ((E[0][0]w00 + E[1][0]w10 + E[2][0]w20 + E[0][1]w01 + E[0][2]w02 == 5) et
(E[2][1]w21 + E[1][1]w11 + E[1][2]w12 + E[2][2]w22 == 0)) alors sort=1 ;

Si ((E[1][0]w10 + E[1][1]w11 + E[2][1]w21 == 3) et (E[0][0]w00 + E[2][0]w20 +
E[0][1]w01 + E[0][2]w02 + E[1][2]w12 + E[2][2]w22 == 0)) alors sort=2 ;

Si ((E[0][0]w00 + E[0][1]w01 + E[0][2]w02 + E[1][2]w12 + E[2][2]w22 == 5) et
(E[1][0]w10 + E[1][1]w11 + E[2][1]w21 + E[2][0]w20 == 0)) alors sort=2 ;

Si ((E[1][0]w10 + E[1][1]w11 + E[0][1]w01 == 3) et (E[0][0]w00 + E[0][2]w02 +
E[1][2]w12 + E[2][0]w20 + E[2][1]w01 + E[2][2]w22 == 0)) alors sort=3 ;

Si ((E[0][2]w02 + E[1][2]w12 + E[2][0]w20 + E[2][1]w01 + E[2][2]w02 == 5) et
(E[0][0]w00 + E[1][0]w10 + E[1][1]w11 + E[0][1]w01 == 0)) alors sort=3 ;

Si ((E[0][1]w01 + E[1][1]w11 + E[1][2]w12 == 3) et (E[0][0]w00 + E[1][0]w10 +
E[2][0]w20 + E[2][1]w21 + E[2][2]w22 + E[0][2]w02 == 0)) alors sort=4 ;

Si ((E[0][0]w00 + E[1][0]w10 + E[2][0]w20 + E[2][1]w21 + E[2][2]w22 == 5) et
(E[0][1]w01 + E[1][1]w11 + E[1][2]w12 + E[0][2]w02 == 0)) alors sort=4 ;

Si ((E[0][1]w01 + E[1][1]w11 + E[1][2]w12 + E[2][1]w21 == 4) et (E[0][0]w00 +
E[1][0]w10 + E[2][0]w20 + E[2][2]w22 + E[0][2]w02 == 0)) alors sort=5 ;

Si ((E[0][0]w00 + E[1][0]w10 + E[2][0]w20 + E[1][1]w11 + E[1][2]w12 == 5) et
(E[0][1]w01 + E[0][2]w02 + E[2][1]w21 + E[2][2]w22 == 0)) alors sort=5 ;

Si ((E[1][0]w10 + E[1][1]w11 + E[1][2]w12 + E[2][1]w21 == 4) et (E[0][0]w00 +
E[0][1]w01 + E[0][2]w02 + E[2][0]w20 + E[2][2]w22 == 0)) alors sort=6 ;

63

Si ((E[0][0]woo + E[0][1]woi + E[0][2]w₀₂ + E[1][1]w_ii + E[2][1]w_2i == 5) et

(E[1][0]w₁₀ + E[2][0]w₂₀ + E[1][2]w₁₂ + E[2][2]w₂₂ == 0)) alors sort=6 ;

Si ((E[0][1]w_o1 + E[1][1]w₁₁ + E[1][0]w₁₀ + E[2][1]w₂₁ == 4) et (E[0][0]w_oo +
E[0][2]w₀₂ + E[1][2]w₁₂ + E[2][2]w₂₂ + E[2][0]w₂₀ == 0)) alors sort=7 ;

Si ((E[1][0]w₁₀ + E[1][1]w₁₁ + E[1][2]w₁₂ + E[0][2]w₀₂ + E[2][2]w₂₂ == 5) et
(E[0][0]w_oo + E[0][1]w₀₁ + E[2][0]w₂₀ + E[2][1]w₂₁ == 0)) alors sort=7 ;

Si ((E[0][1]w_o1 + E[1][0]w₁₀ + E[1][1]w₁₁ + E[1][2]w₁₂ == 4) et (E[0][0]w_oo +
E[0][2]w₀₂ + E[2][0]w₂₀ + E[2][1]w₂₁ + E[2][2]w₂₂ == 0)) alors sort=8 ;

Si ((E[0][1]w_o1 + E[1][1]w₁₁ + E[2][0]w₂₀ + E[2][1]w₂₁ + E[2][2]w₂₂ == 5) et
(E[0][0]w_oo + E[0][2]w₀₂ + E[1][0]w₁₀ + E[1][2]w₁₂ == 0)) alors sort=8 ;

Si ((E[0][1]w_o1 + E[1][1]w₁₁ + E[1][0]w₁₀ + E[1][2]w₁₂ + E[2][1]w₂₁ == 5) et
(E[0][0]w_oo + E[0][2]w₀₂ + E[2][0]w₂₀ + E[2][2]w₂₂ == 0)) alors sort=9 ;

2ème phase : Compréhension de la structure du tableau

Cette phase permet de générer automatiquement la structure du tableau détecté à l'aide de

la phase précédente. Pour y arriver, l'aire de sortie du réseau implémentera l'algorithme

suivant :

Recevoir la matrice M[][] contenant les sorties de tous les neurones du gradient ;

Initialiser l, c, nbrcolonnes et nbrlignes à 0 ;

Pour i allant de 0 à 290 faire

Pour j allant de 0 à 290 faire

Si ((M[j][i]==7) ou ((M[j][i]==5)) alors

l=1 ; j=291 ;

sinon l=0 ;

FinSi

FinPour

nbrlignes= nbrlignes+l ;

FinPour

Pour i allant de 0 à 290 faire

Pour j allant de 0 à 290 faire

Si (M[i][j]==6) alors

64

c=1 ; j=291 ;

sinon c=0 ;

FinSi

FinPour

nbrcolonnes = nbrcolonnes +c ;

FinPour

Créer le fichier `'Tableau.html» ;

Ouvrir "Tableau.html" ;

Ajouter la chaîne suivante au contenu de `'Tableau.html»

"<html> \n <head> <style type=\"text/css\"> <!-- table {border-width: 1px; border-

color:black;} td {border-width: 1px; border-style:solid; border-color:black;} --> </style> \n

<title> STRUCTURE DU TABLEAU</title>\n</head> <body><center> <table border

style=\"solid\" cellspacing=\"0\">";

Pour i allant de 0 à nbrlignes faire

Ajouter la chaîne "<tr>" au contenu de "Tableau.html" ;

Pour j allant de 0 à nbrcolonnes faire

Ajouter la chaîne "<td><font color=\"white\">___</font></td>" au contenu de

"Tableau.html" ;

FinPour

Ajouter la chaîne "</tr>" au contenu de "Tableau.html" ;

FinPour

Ajouter la chaîne "</table></center></body></html>" au contenu de "Tableau.html" ;

Fermer "Tableau.html".

Créer le fichier2 `'Tableau.doc» ;

Ouvrir "Tableau.doc" ;

Ajouter la chaîne suivante au contenu de `'Tableau.doc»

"<html> \n <head> <style type=\"text/css\"> <!-- table {border-width: 1px; border-

color:black;} td {border-width: 1px; border-style:solid; border-color:black;} --> </style> \n

<title> STRUCTURE DU TABLEAU</title>\n</head> <body><center> <table border

style=\"solid\" cellspacing=\"0\">";

Pour i allant de 0 à nbrlignes faire

Ajouter la chaîne "<tr>" au contenu de "Tableau.doc" ;

65

Pour j allant de 0 à nbrcolonnes faire

Ajouter la chaîne "<td><font color=\"white\">___</font></td>" au contenu de

"Tableau.doc" ;

FinPour

Ajouter la chaîne "</tr>" au contenu de "Tableau.doc" ;

FinPour

Ajouter la chaîne "</table></center></body></html>" au contenu de "Tableau.doc" ;

Fermer "Tableau.doc".