Memoire Online - La reconnaissance optique de tableaux numerises : listes des étudiants inscrits de l'ISP/Bukavu

« Notre peur vient, non pas de ne pas être à la hauteur; notre peur vient, du fait que notre pouvoir est presque sans bornes.

On se dit souvent ` qui suis-je moi pour être brillant, talentueux, fantastique ? '

Nous sommes sur terre pour témoigner de la gloire de Jéhovah Dieu qui se trouve en nous, en nous autorisant à rayonner permettant aux autres de faire autant.»

DEDICACE

Julienne MAWAZO Chakupewa, pour nous avoir tendrement aimé depuis notre conception et à notre naissance; de nous avoir éduqué et acheminé à l'école.

REMERCIEMENTS

A notre Directeur, L'assistant Dieudonné KYENDA Sulika, pour nous avoir encadré en ces recherches et nous avoir temoigné son amour; puisse Jéhovah Dieu lui donner une longue vie, et avec lui nous remercions tous les enseignats de l'ISP/Bukavu et plus en clair les chefs de travaux BULABULA, KASELE, aux assistants TASHO Issa, KAMPEMPE Damien, Tony SAMAMBA, Marcelline SIKITU, Manix LUNANGA ;

A notre grand frère Hector MUKAMBA Byemba pour nous avoir témoigné sa grande générosité. Qu'il reçoive par cet oeuvre le talent de son frère cadet ;

A nos soeurs : SANGANYI, Isabel BASUBI, Furaha TAKUBUSOKA BITONDO et Zawadi BASUBI;

A Jessicca ZAWADI, Dorianne MISANZILA, Kennedy, Ndambi et Jean-Jacques MWENE MAHAMBA, Riziki KABILONGO, Ange LUNANGA, notre oncle Barthélemy LUNANGA, Janvier LUNANGA ;

A notre bien aimée Eunice CIZA Byazire pour nous avoir suffisamment soutenu en des moments critiques comme en des temps paisibles et de guetté ;

A Prosper CHIRUZA, Nadine MASOKA, Saidi BUSOLE, Elysée KASIKILA, Jean-Marie ZIHALIRWA, Pascaline MWANGAZA, Christian KADIYA, Prince KALALIZI, Alain, Bernard et Bitho NGOY, Isaac MAKUVUNINA, Matthieu KALEKO, Ahadi KILOKOTE, Christian BATACHOKA, Edith KAMUNGU,Neema BYAMUNGU, Benjamin MUSIKAMI, Etienne MUKUMO, Jacques ALIMASI, Léon MASHAURI, McMillan JONATHAN,AMANI BYAMUNGU,Josué ZIHINDULA et Mamy KANIKI;

Aux familles Jules MATABARO, Emmanuel KAHARA, Isidore BASUBI, Modeste BYAZIRE, Idesbalde-SOLANGE BYAZIRE, KAMUKALANGA WASSO, LUNGERE, flory MUBANDILWA et Moïse BASHEKE;

A nos camarades : Jean-Marie MUNGUAKONKWA, Mutumay et Teddy KABAMBA, Didier MUTIKI, Kossi DJAKE, Matongo KAWAYA, Nsimire CIRHABA, Lucien MUBALAMA, Alain NAMUJIMBO, Olivier MULONGESHA, Oswald MATTHIEU, Wivine BIKUBUSHO,Douglas MUPENDA et Sauda KILUHUKIRO.

SIGLES ET ABREVIATIONS

RESUME

La reconnaissance optique des données numériques trouvées dans des tableaux pose d'énormes problèmes de distinction des tracés du tableau et les données contenues dans les cellules de celui-ci.

Le présent travail examine les possibilités de séparer les tracés du tableau et le contenu qui peut être des chaines de caractères, et renvoie les éléments au programme de reconnaissance optique des caractères en des petites images.

Le programme ainsi conçu utilisera les méthodes de projection horizontale et verticale du tableau des pixels, la reconnaissance hors ligne et les astuces de voisinage des pixels.

Le résultat obtenu nous permet de confirmer avoir atteint nos objectifs, car, les images remises en retour peuvent être traitées par un logiciel de reconnaissance optique des caractères et le résultat peut être stocké dans un classeur usuel ou les bases des données.

ABSTRACT

Optical recognition of numeric datas founds in arrays has got problems of making distinction between arrays and their datas.

This research parper aims at examining possibilities of separating arrays and their conteint which can be strings of caracteres. It sends elements like images to the programm's optical recognition of caracteres.

There for, this programme will be using the horizontal and vertaical's projections, out of lines recognition's method and pixels which are in neighbourood amoung themselves.

Thus, as far as the images found in return which can be treated by optical recognition program of caracteres and its result can be stocked in the file or in the data base are concerned, we can confirm that we have attended the objective.

Key word: Recognition, Optical, T ables.

1. I. INTRODUCTION

2. I.1. PROBLEMATIQUE

Dans les pays qui envisagent le développement, l'histoire a une nécessité pour l'appréhension du présent et la préparation du futur.

En effet, Pour que l'on soit informé du passé, il faut apprendre l'histoire et cela à travers beaucoup de sources entre autres les documents écrits.

Parce que présent système aura besoin d'une information harchivée nécessaire du passé, il est important de coder les informations que nous avons en possession. Néanmoins avec l'évolution de la technologie, le moyen le plus fiable et rapide pour protéger les informations s'avère être leur stockage dans des procédés informatiques.

L'informatique étant jeune par rapport à l'époque des machines mécaniques et améliorée du jour le jour, les informations se trouvant sur des documents tapées à la machine mécanique ou sur des documents imprimés longtemps plus tôt, et dont le format numériques est perdu sont appelées à être codées de nouveau et stockées dans des ordinateurs pour qu'elles soient, soit traitées ou soit consultées en vue d'une prise de décision ultérieure quelconque.

Il se pose alors un problème de temps, d'efforts et d'énergie pour la ressaisie de ces documents, car leur nombre est devenu de plus en plus croissant.

C'est pour ces raisons que des informaticiens se sont mis à mettre sur pieds des astuces qui servent non seulement à scanner des documents texte mais aussi de reconnaitre les caractères se trouvant sur les images optenues après scanning.

Pourtant, certains documents ont des données complexes, par exemple celles contenues dans des tableaux; alors que les programmes de ROC peinent à traiter les tableaux. De plus, leur vérification est difficile: ils contiennent de nombreux chiffres, souvent avec des espaces, points ou virgules, et il n'est pas aisé de décaler des cellules d'une ligne ou d'une colonne. Il leur faut un effort particulier de concentration et une rélecture obstinée et intense, une vérification soigneuse, et un bon contrôle de qualité^1(*).

Le traitement de ces données par les programmes de reconnaissance optique des caractères dévient plus difficile en raison des traits, des lignes et des colonnes; mais quelques fois, la séparation des données qui se trouvent dans deux cellules consécutives.

- La détérmination de la forme de tableau et la reconnaissance des lignes, des colonnes ainsi que des limites de cellules obtenues de ces dernières posant des difficultés importantes, la reconnaissance des lignes et des colonnes permettra-t-elle la reconnaissance du tableau tout entier ?

- les cellules du tableau numérisé et reconnues doivent être retournées individuellement dans des images bitmap propres ; quels sont les moyens qui seront mis sur base pour écrire les octets réprésentant ces cellules peuvent elles être utilisés ?

- pourquoi les images retournées en sortie, doivent-elles avoir des caractéristiques qui permettront la susceptibilité d'être reconnues sans difficulté par des logiciels de ROC ?

Telles sont les genres des questions auxquelles nous donnerons des réponses dans ce mémoire.

3. I.2. HYPOTHESES

Etant donné que les logiciels de reconnaissance optique des caractères traitent sans difficultés les données se trouvant non pas dans des tableaux, le logiciel que nous allons concevoir pourra, sans failles reconnaitre et différentier le tableau et les caractères représentant les données, et remettre uniquement les données d'une même cellule dans une petites images. A cet état, ces logiciels peuvent les traiter séparément sans des difficultés épaisses.

En effet, la reconnaissance des lignes et des colonnes permettra par conséquent la reconnaissance des limites des cellules ainsi que celle du tableau proprement dit ;

Nous montrerons et développerons dans ce mémoire les méthodes qui pemettront d'écrire les octets des cellules dans des images bitmap propres ;

Les images bitmap reconnues doivent être dépourvues des lignes du tracé pour permettre aux logiciels de ROC, de reconnaître sans problèmes les caractères qui les contiennent.

4. I.3. METHODES ET TECHNIQUES

En vue de bien comprendre des notions à généralisser, nous avons utilisé la méthode inductive qui nous a aidé à partir du particulier au général, partant d'un élément de l'image à son ensemble.

Pour y arriver, il faudra tout d'abord reconnaître les lignes et les colonnes constituant l'image du tableau et en détérminer les limites et traits séparateurs.

Lorsque les limites seront trouvées, la question ne restera qu'à indéxer les cellules elles-mêmes et les tirer de l'image globale,pour les remettre dans des images bitmap respectives.

Ainsi, les images remises pourront permettre la reconnaissance des caractères car elles seront dépourvues des barres, séparateurs des cellules.

La bibliothèque présentement riche en documentation et renseignements à savoir l'internet, nous a permis de renforcer la théorie sur les les fichiers, la reconnaissance des formes et d'enrichir nos connaissances en vue de l'élaboration de ce travail.

De toute évidence, nous avons recouru à la technique documentaire afin d'accéder aux différents ouvrages et articles traités par nos prédécesseurs et ayant un marquage au problème auquel nous voulons porter solution.

5. I.4. DELIMITATION DU TRAVAIL

Nous avons réalisé nos investigantions en traitant les données des tableaux du bureau des inscriptions et de scolarité de l'ISP/Bukavu, dans la ville de Bukavu, dans la province du sud-kivu, en république démocratique du Congo.

Notre travail va se limiter sur la détérmination et le renvoie dans des images, des zones de l'images bitmap à savoir, le contenu des cellules d'un tableau à deux dimensions.

Nous utiliserons pour la reconnaissance des formes aux images bitmap, les images scindées seront transformées en fichers ps. Une transformation des fichiers ps sera faite grace au langage postscript ; tandis que nous afficherons sur une page html que les image jpeg converties. Il est donc bien évident que les images Jpeg ne feront l'object que de l'état de sortie.

6. I.5. CHOIX ET INTERET DU SUJET

Sachant que nous allons répondre tant soit peu à une question qui tracasse les hommes de la sciences quant ils veulent faciliter la réedition de leurs documents imprimés ou tapés à la machine, nous avons voulu de plus approfindir nos connaissances sur le traitement des images.

Nous savons tout de même que la reconnaissance des formes est un domaine qui se forge la place dans le monde technologique actuelle, il nous a été d'une grande importance d'apprentissage des notions nécéssaires pour le développement de la reconnaissance des formes.

Nous savons que l'imagerie est un domaine de l'informatique qui est très fréquentée et qui intéresse énormément des chercheurs, notre dessein pour l'aspect scientifique est de faciliter les institutions à pouvoir traiter avec plus d'efficacité et de rapidité les informations qui peuvent leur prendre plus de temps et de l'argent de traitement.

7. I.6. ETAT DE LA QUESTION

1. YANG CAO, HENG LI et SHUHUA WANG : les deux premiers du Département de Bâtiment et Propriété Vraie à l'université de Polytechnique de Hong-Kong et le troisième de l'université laboratoire Clé de Nouvelle Technologie des Logiciels, Université Nanjing de CHINE. Ils ont traité le travail intitulé : AUTOMATIC RECOGNITION OF TABLES IN CONSTRUCTION TENDER DOCUMENTS.

Le système qu'ils ont conçu en 2002, consiste en deux modules principaux pour la reconnaissance des documents( tender document) suivants:

Le modérateur du tableau aide des utilisateurs pour construire des modèles de formulaire, et le lecteur du tableau reconnaît les entrée des tableaux provenant du modèle de base des données et régénère des tableaux électroniques.

2. RAHGOZAR M. A. aux etats-unis a présenté en 2000 en collaboration avec firmes suivantes : Xerox Architecture Center, Xerox Corporation, Webster New York, 800 Phillips Rd., 0128-30E, Webster et NY 14580; une Approche qui est Basée sur Le « DOCUMENT TABLE RECOGNITION BY GRAPH REWRITING » (PARADIGME DE RECRIRE DES GRAPHIQUES).

En premier lieu, l'image du document est transformée dans une disposition graphique dont les noeuds et les bords représentent respectivement des entités du document et leurs corrélations. Ce graphique est réecrit par la suite et utilise un ensemble de règles conçues et basées sur la connaissance à priori du document ainsi que les conventions générales de formatage. Le graphique résultant fournit à la fois la logique et la disposition envisagées du contenu du document.

3. Serges SHABANI lusamaki dans son travail de fin ce cycle à l'ISP/Bukavu intitulé LA RECONNAISSANCE DES FORMES DANS LA CORRECTION DES QUESTIONS A CHOIX MULTIPLES en 2004 et MUGARUKA Ntabaza dans CORRECTION DES QUESTIONS A CHOIX MULTIPLE PAR RECONNAISSANCE DES FORMES de la même année traitent de la reconnaissance du doicument. Il est à noter que les assertions qu'ils ont considérées, pour être reconnues devaient être rangées ligne par lignes comme dans un tableau, dont la première colonne est celle des numéros ou les lettres des réponses et la deuxième, celle des réponses elles-mêmes. Ils ont consideré le rapport entre le nombre des pixels entre l'assertion choisie et la première assertion. Le resultat de ce rapport et la première assertion donne des éléments sur la prise de décision de l'assertion qui a été choisie ou cohée.

4. B. Gatos, D. Danatsas, I. Pratikakis et S. J. Perantonis, des chercheurs d'Athènes en Grèce, ont devéloppé en 2005, AUTOMATIC TABLE DETECTION IN DOCUMENT IMAGES

ils ont d'abord recherché les courses du tracé noir horizontal et vertical pour détérminer les lignes et les ont estimé les lignes horizontale et verticale et l'amélioration de l'estimation de ces ligne en utilisant le déménagement des régions de l'image/text. Ces chercheurs sont alors partis à la détéction du tableau proprement par la détermination des intersections des lignes et la détection de la reconstruction du tableau.

5. Luiz Antonio Pereira Neves , Joao Marques de Carvalho et Jacques Facon ont travaillé sur la RECOGNITION OF DETERIORATED TABLE-FORM DOCUMENTS: A NEW APPROACH : dans cette approche, ils essaient de réprésenter dans la matrice des réels les différents coins du tableau. Une analyse du tableau des réels devrait être faite. Chaque intersection des voisins est comparée à la référence du voisinage du tableau de réjection, puis du tableau des réfus. Avec cette méthode on détérmine les segments et par conséquent les cellules du tableau par la connaissance facile des coins sxtrêmes du tableau.

FOR TABLE-FORM DOCUMENTS approche des japonais Lin Yu Tseng et Rung-Ching Chent du département de Mathématique appliqué de l'université national de Chung Hsing Taichung en Taiwan en 1996. selon eux, Il faut d'abord extraire tous les segments des lignes horizontales, les segments des lignes verticales ainsi que et les segments des lignes penchées ou obliques de l'image du document ; ensuite, l'assemblage et la reconstruction du document.

il y a trois types des champs à savoir : le champs de nom, le champs des données et le champs mixte. Un champ mixte est une combinaison des champs de nom et de champs des données.

L'inconvénient de cette méthode est que l'on parcours deux fois la même image pour extraire le tableau.

8. I.7. PLAN SOMMAIRE DU TRAVAIL

L'introduction et la conclusion non incluses, ce travail est subdivisé en quatre chapitres intitulés et détaillés comme suit :

Chapitre premier, LES FICHIERS INFORMATIQUES. Dans ce chapitre nous allons parler des fichiers que nous avons utilisés, à savoir les fichiers .ps, jpeg, bitmap, et les .bat. Après le dévéloppement de ces notions, nous allons dans ce même chapitre,faire un aperçu sur les termes constituant le sujet de ce travail à savoir la reconnaissance, optique, données et numériques.

Chapitre deuxième, LES MODELES DE RECONNAISSANCE DES DOCUMENTS :TABLEAUX. Dans ce chapitre, nous allons considérer les méthodes déjà utilisées pour la reconnaissance des documents en général et des documents tableaux en particulier.

Chapitre trosième, LA RECONNAISSANCE OPTIQUE DES TABLEAUX. Dans ce chaptre, nous éssayerons de proposer un algorithme permettant la reconnaissance optique d'un tableau des données.

Chapitre quatrième, LA SIMULATION DE L'ALGORITHME DE RECONNAISSANCE OPTIQUE DES TABLEAUX PAR UN LOGICIEL INFORMATIQUE. Dans ce dernier chapitre, nous allons illustrer par un programme informatique l'algorithme que nous aurons proposé dans le chapitre précédent. Un état de sortie fait en html sera présenté pour afficher le résultat, les images sur la page du html. CHAPITRE I. LES FICHIERS INFORMATIQUES

Dans ce travail, nous allons traiter différents types des fichiers ; il est donc important de jetter un coup d'oeil sur les caractéristiques de ces fichiers avant de développer leurs notions individuellement.

Nous allons parler des fichiers textes, des fichiers images jpeg et bitmap ; nous terminerons par les fichiers « .bat ». ces types des fichiers nous seront très util dans la suite de ce travail.

D'une manière général, nous pouvons admettre qu'un fichier est est un ensemble structuré des données stockées en général sur un support externe(disquette, disque dur, disque optique, bande magnetique, etc.). cette déficition s'adapte facilement selon les différentes applications. Pour la gestion des bases des données par exemple, les fichiers les plus utilisés sont conçus sous forme des tables. Dans ce cas, un fichier est composé d'une suite d'enregistrement homogène,etc.

9. I.1. LES FICHIERS « .ps »

En informatique, un fichier texte( ou fichier texte brut ou fichier texte simple ou encore fichier ASCII), est un fichier dont le contenu représente uniquement une suite de caractères imprimables, d' espaces et de retours à la ligne( pas de formattage).

Un fichier « non texte » est appelé « fichier binaire », dans le sens où les bits contenus dans le fichier ne peuvent pas être représentés par une simple suite de caractères imprimables, d'espaces et de retours à la ligne.

La dénomination « fichier ASCII » est souvent abusivement utilisée à propos de fichiers texte n'utilisant pas le codage de caractères ASCII.

Les fichiers d'extention « .ps » sont des fichiers textes. Ces fichiers sont interprétés par des récents logiciels capables de lire les fichiers pdf ; par exemple le PDF Creator, à condition de le configurer lors de l'installation du produit, le Ghostview ou encore le Ghostscriptview, lequel peut aussi convertir les fichiers .ps en pdf. par contre, acrobat reader n'est pas en mesure de lire les fichiers .ps. le contenu du fichier .ps représente une image vectorielle prêtte pour être imprimée par des imprimantes Postscript.

Les images des fichiers .ps se structurent de la manière à ce que les coordonnées des points sur la pages du fichier ont comme unité le pixel ( picture element ) qui représente une soixante douzième de pouce dans le langage PostScript.

Il est à noter que les pixels du fichier ps sont repertoriés dans la grille de la page di fichier, le point en bas et à gauche de la page du fichier ps a pour coordonées (0,0) et la taille de la page est horizontalement 612 , et verticalement 792. Ces tailles sont valides pour le type :"letter type". Il y a plusieurs possibilités de définition de la taille des pages.

Ces fichiers ps qui nous faciliteront la conversion des images bitmap en images jpeg sont productibles par le langage PostScript duquel proviennent les deux lettres donnant l'extension des fichiers « *.ps ». Nous développerons beaucoup plus les détails sur ce langage au dernier chapitre de ce mémoire ; mais à présent, les images qui seront converties.

10. I.2. LES FICHIERS IMAGES

1) les images JPEG

(Image de http://fr.wikipedia.org/wiki/JPEG)
JPEG vient de l'acronyme: Joint Photographic Experts Group. C'est un comité d'experts qui édite des normes de compression pour l'image fixe. La norme communément appelée JPEG, de son vrai nom ISO/IEC IS 10918-1 | ITU-T Recommendation T.81, est le résultat de l'évolution des travaux qui ont débuté dans les années 1978 à 1980 avec les premiers essais en laboratoire de compression d'images^1(*).

Le groupe JPEG qui a réuni une trentaine d'experts internationaux, a spécifié la norme en 1991. Mais la norme officielle et définitive n'a été adoptée qu'en 1992. Pratiquement, seule la partie concernant le codage arithmétique est brevetée, et par conséquent protégée par IBM, son concepteur.

JPEG normalise uniquement l'algorithme et le format de décodage. Le processus d'encodage est laissé libre à la compétition des industriels et universitaires, du moment que l'image produite est décodable par un décodeur standard. La norme propose un jeu de fichiers de tests appelés fichiers de conformance qui permettent de vérifier qu'un décodeur respecte bien la norme. Un décodeur est alors dit conforme s'il est capable de décoder tous les fichiers de conformance.

Le brevet de la norme JPEG a été déposé par l'entreprise Forgent 1, mais il a été remis en cause par le bureau américain des brevets (USPTO), qui l'a invalidé le 24 mai 2006 pour antériorité existante à la suite d'une plainte de la Public Patent Foundation qui considère ce brevet invalide 2. Mais depuis le 27 septembre 2007, la société Global Patent Holdings, filiale d'Acacia Research Corporation, a à son tour revendiqué la paternité de ce format.

· avec pertes ou compression irréversible. C'est le JPEG « classique ». Il permet des taux de compression de 3 à 100 ;

· sans pertes ou compression réversible. Il n'y a pas de pertes d'information et il est donc possible de revenir aux valeurs originales de l'image. Les gains en termes de compression sont alors plus modestes, avec un taux de compression de l'ordre de 2. Cette partie fait l'objet d'une norme spécifique JPEG-LS.

Comme nous venons de le voir dans les phrases précédentes, les fichiers JPEG permettent une compression facile que les images Bitmap et ont bien entendue une taille extremement inférieure aux mêmes fichiers Bitmap, raisons pour lesquelles elles sont beaucoup plus utilisées pour les pages web ; mais pourtant, elles occasionnent quoi que minime, une perte d'informations liée aux multiples compressions et decompressions.

11. I.3. APERCU SUR LES IMAGES BITMAP

Il est difficile de séparer la reconnaissance des formes percues sur les images et les images bitmap. Parlant de la reconnaissance des formes perçues sur les images, nous ne cesserons pas de jetter un projecteur sur les images matricielles. Ce type d'images correspond le mieux pour la reconnaissance des formes vue sa facilité d'accès aux pixels.

Les images matricielles, appellées aussi les images bitmap, sont les images représentées par une matrice des pixels. Une matrice est en quelques sorte un tableau des pixels(élément d'image). Le pixel à son tour est le plus petit élement constituant une image bitmap,ces pixels ont une forme rectangulaire, et chacun d'entre eux possède une quelconque couleur, et le rassemblement de ces pixels donne l'image matricielle globale. Les limites entre les pixels ne sont pas visibles à l'oeil nu sauf si l'image est agrandie jusqu'o laisser voir l'effet d'escalier.

Les images matricielles peuvent être directement capturée par des périphériques comme les scanners, les appareils photo numériques, des tablèttes digitales, les radars, etc, ou tout simplement synthétisées sur des ordinateurs par des logiciels spéciaux comme le photoshop, paint,etc.

La figure suivante montre comment des chiffres sont vicualisés en images matricielles :

La lourdeur de ces images par rapport aux JPEG fait qu'elles ne soient pas beaucoup plus utilisées pour d'autres fins délicats ; bien qu'elles soient utilisées pour d'autres comme la reconnaissance des formes du fait qu' elles occasionnent moins de perte d'information ;

La résolution d'une image numérique est le nombre de pixels par pouce, une pouce étant égal à 2.54 centimetres. Elle définit le degré de détail de l'image. Ainsi, plus la résolution est élévée, meilleure est la restitution, grande est la taille et très longue est l'impression.Tant que la résolution d'une image est grande autant l'image est nette et bonne. Autrement dit, plus la hauteur et la largeur de l'image sont longues, plus l'image détient plus de pixels et plus la taille en octet augmente.

La définition d'une image est à peu près la même chose que la résolution sauf que la définition correspond au nombre de pixels la composant, c'est-à-dire le nombre de points en hauteur et en largeur, par exemple une image de 200 pixels par 450 pixels, abregé en « 200x450 ».

Alors que la résolution est exprimée par unité de surface, généralement le ppp, ainsi une résolution de 300ppp signifie 300 colonnes et 300 rangées de pixels sur une pouce carré ce qui donne 90 000 pixels sur une pouce carré.

Nous avons utilisé les images bitmap de 24 bits pour collorer un pixel ; pour ces images, les octets de l'entête et du corps ne peuvent déppasser la valeur 255. Il dévient alors difficile de créer des images bitmap lorsqu'on a qu'une matrice des chiffres du corps. D'où, il faut chercher à savoir les nombres à écrire dans les octets de l'entête : si nous savons le nombre des lignes et le nombre des colonnes de la matrice.

Dans la mésure où ce nombre dépasse 255, il faut alors renvoyer à des divisions par 256 jusqu'à ce que le reste inférieur à 256.

Illustrons ça par un exemple concret : si nous détenons d'une matrice 600x600, dans l'entete de l'image, nous n'écrirons pas :

· Ni largeur :600, il faudra aux octets de la hauteur écrire d'abord 88 qui est le modulo de la division euclidienne et dans l'octet suivant écire 2.

La fonction nous a aidé de faire cette tâche et nous renvoie quatre valeurs de quatre octets inférieur à 256 correspondants au nombre entré en argument:

Ces images sont composées d'entités géométriques telles qu'un cercle, une ligne, un rectangle, une courbe, un segment,etc. Ces entités géométriques sont réprésentées par des formules mathématiques( par exemple, le rectangle est définit par deux points, le cercle par un centre et un rayon, une courbe par un plusieurs points et une équation.) c'est le processeur qui se chargera de traduire ces formules en informations interprétables par la carte graphique.

L'interêt avec ces types d'images ce qu'on peut les agrandir sans perte de qualité c'est-à-dire sans aucun effet d'éscalier car un dessin vectoriel est dessiné à nouveau à chaque visualisation, ce qui engendre des calculs sur la machine. On se sert de ce type d'images pour représenter des formes simples et non pas pour dessiner un home ou un animal, même si dans certains cas, on peut y arriver après beaucoup des tournures souvent trop lourdes.

Nous allons nous limiter pour ce mémoire aux images matricielles étant donné que nous allons effectuer des extractions des parties d'images et en produire d'autres. Le langage postscript crééra alors un pont entre les images bmp et les images JPEG pour produire facilement nos états de sortie en html.

12. I.4. LES FICHIERS .bat2(*)

Il est vrai que les fichiets d'extention.bat sont des fichiers de commandes MS-DOS. Réaliser un tel fichier permet de concevoir des scripts qui seront interprétés par le " shell" ou interpréteur de commandes ( command.com ou cmd.exe) pour notamment exécuter des fichiers .EXE ou .COM. Cette extension est principalement utilisée sur les systèmes d'exploitation de Microsoft (DOS et Windows). Elle peut être assimilée (dans une certaine mesure) à l'extension .sh des scripts shell Unix (ceux du Bourne shell plus exactement).

Si le fichier est inconnu, il est préféreable de ne pas le lancer (à l'aide d'un double clic), mais au contraire il faut l'éditer (à l'aide d'un clic droit puis éditer) pour voir ce qu'il contient. En effet, il peut s'agir d'un script malveillant tel qu'un cheval de Troie ou autre virus de son type.

Il existe quelques commandes spécifiques aux fichiers de traitements par lots. Nous énumérons ici un échantillon:

13. I.5. LES TERMES DU SUJET

Nous rappelons que le sujet de ce mémoire est : «La reconnaissance optique des tableaux numérisés». Bien que le reste du présent mémoire explique en général ces notions, nous ne cesserons pas de considérer certains de ces termes individuellement.

1) Reconnaissance:

Reconnaître quelque chose c'est l'identifier après une observation systématique, différemment d'autres observées.

2) Optique:

L'optique est la branche de la physique qui traite de la lumière, du rayonnement électromagnétique et de ses relations avec la vision^3(*). L'optique dans ce travail trouvera son utilité, pas seulement que les scanners et les appareils de numérisation utilisent des procédés de l'optique mais surtout que les méthodes de reconnaissance vont planner sur les aspects dont le tableau est apparu et apprecié optiquement par le logiciel que nous mettrons sur pieds : la reconnaissance structurale de l'image par exemple.

3) Numérisation 4(*) :

La transformation d'un signal analogique en signal numérique est appelée numérisation. La numérisation comporte deux activités parallèles : l'échantillonnage (en anglais sampling) et la quantification. L'échantillonnage consiste à prélever périodiquement des échantillons d'un signal analogique. La quantification consiste à affecter une valeur numérique à chaque échantillon prélevé.

· La fréquence d'échantillonnage (appelé taux d'échantillonnage) : plus celle-ci est grande (c'est-à-dire que les échantillons sont relevés à de petits intervalles de temps) plus le signal numérique sera fidèle à l'original;

· La profondeur des images bitmap : la profondeur des couleurs est le nombre des bits associé à chaque pixel pour en coder la couleur. Ainsi, les images BMP peuvent être de 2 couleurs(1 bit), 16 couleurs( 4 bits) 256 couleurs(8 bit), 65 536 couleurs (16 bits) ou 16,8 millions des couleurs(24 bit) ;

· Le nombre de bits sur lequel on code les valeurs (appelé résolution) : il s'agit en fait du nombre de valeurs différentes qu'un échantillon peut prendre. Plus celui-ci est grand, meilleure est la qualité.

Ainsi, grâce à la numérisation on peut garantir la qualité d'un signal, ou bien la réduire volontairement pour :

Les phénomènes qui nous entourent sont quasiment tous continus. Ces phénomènes sont quantifiables et passent d'une valeur à une autre sans discontinuité.

Ainsi, lorsque l'on désire reproduire les valeurs du phénomène, il s'agit de l'enregistrer sur un support, afin de pouvoir l'interpréter pour reproduire le phénomène original de la façon la plus exacte possible. Lorsque le support physique peut prendre des valeurs continues, on parle d'enregistrement analogique. Par exemple une cassette vidéo, une cassette audio sont des supports analogiques. Par contre, lorsque le signal ne peut prendre que des valeurs bien définies, en nombre limité, on parle alors de signal numérique.

La représentation d'un signal analogique est donc une courbe, tandis qu'un signal numérique pourra être visualisé par un histogramme.

De cette façon, il est évident qu'un signal numérique est beaucoup plus facile à reproduire qu'un signal analogique (la copie d'une cassette audio provoque des pertes...).

4) Le tableau

Un tableau est un ensemble des données structurées et rangées en lignes et en colonnes. L'intersection d'une ligne et d'une colonne donne une cellule.

Dans un tableau, deux données de même type se trouve dans une même colonne tandis que deux enregistrements similaires se trouvent sur deux lignes différentes.

Ayant parlé des fichiers qui nous facilitéront la reconnaissance à savoir les fichiers bitmap et autre fichiers qui nous permettront l'affichage du résultat, parlons des modeles envisagés déjà pour la reconnaissance des tableaux.

CHAPITRE II. LES MODELES DE RECONNAISSANCE DES

DOCUMENTS : TABLEAUX

Malgré sa création et sa découverte ancienne (La première machine de ROC fut créée par Gustav Tauschek, un ingénieur allemand, en 1929. Elle contenait un détecteur photosensible qui pointait une lumière sur un mot quand il correspondait à un gabarit contenu dans sa mémoire^5(*)), la reconnaissance optique des caractères intéresse les chercheurs dans les différents coins de la planète. Ce domaine de recherche reste toujours en actualité en science.

Ainsi les documents traités à nos jours sont-ils complexes et détiennent-ils souvent des tableaux. Dans les points développés dans ce chapitre, nous allons illustrer les différents moyens utilisés par les chercheurs pour l'appréhension de la reconnaissance des tableaux dans un document scanné.

II.1. DETECTION AUTOMATIQUE DU TABLEAU DANS L' IMAGE

DU DOCUMENT( en anglais : Automatic table detection in document images)6(*)

Ces recherches s'efforcent vers une méthodologie pour la détection automatique des tableaux dans des documents images. La méthodologie proposée ne présente ni les phases de la formation ni usages heuristiques du domaine spécifique, donc, il résulte à une approche qui consiste à appliquer à une variété des documents types. Il se construit sur plusieurs étapes consécutives qui peuvent être principalement identifiées aux suivantes:

La méthode de détection et analyse d'un tableau dans un document que nous présentons ici a été développée dans le laboratoire « Computational Intelligence Laboratory » par B. Gatos, D. Danatsas, I. Pratikakis et S. J. Perantonis, des chercheurs d'Athènes en Grèce( 2005) semble être efficace.

Après le prétraitement de l'image, ils sont partis par la détermination de la morphologie de celle-ci et la structuration de ses éléments. Ce qui nous intéresse dans cette partie c'est plutôt la deuxième étape qui concerne bien les lignes, les colonnes que le tableau lui-même dans une image d'un document scanné.

a) La détection des lignes :

La technique est basée sur le traitement des principales courses noir horizontal et vertical (pour le cas des colonnes) aussi bien que sur estimation des régions de l'image/text pour exclure des segments de la ligne qui appartiennent à ces régions.

Initialement, un ensemble d'opérations morphologiques avec structuration convenable des éléments sont exécutés pour connecter la ligne possible en vue de casser et rehausser les segments de la ligne. Les étapes distinctes de la technique de la découverte de la ligne proposée sont les suivantes:

- L'amélioration de l'estimation de la ligne en utilisant le déménagement des régions de l'image/text.

b) Détection du tableau

La détection du tableau par la découverte de la ligne horizontale et verticale facilite la présentation du tableau. La technique de la découverte de Notre tableau implique en son sein deux étapes distinctes :

Toutes les intersections des lignes possibles sont progressivement détectées d'après l'algorithme suivant :

En premier lieu, on détecte toutes les intersections comme le montre les illustrations IDs 1-4 suivantes :

Dans ce cas, un point de la fin de ligne horizontale et une autre fin de point d'une ligne verticale définissent une intersection de la ligne de ce type si elles ont le minimum distance parmi les autres autour d'un voisinage.

Par la suite, ils ont tracé pour les intersections avec IDs 5-8. Dans ce cas, un point de la fin de, non plus une ligne horizontale ou une ligne verticale est testée contre un autre point de la ligne qui n'est pas un point de la fin et correspond à une ligne verticale ou une ligne horizontale respectivement.

L'intersection de la ligne de ce genre est définie pour des tels points qui ont la distance minimum parmi autres autour d'un voisinage. Finalement, nous détectons des intersections avec ID5-9. Cela correspond aux croisements des lignes horizontales et verticales.

La découverte du tableau et sa reconstruction impliquent le les étapes suivantes:

En premier lieu, tous les pixels qui appartiennent aux lignes détectées sont déplacés (voir Le fig. 5(c)). Alors, toutes les intersections des lignes détectées sont groupées en premier lieu horizontalement et alors verticalement. Chaque groupe est aligné plus loin d'après la valeur moyenne des positions verticales ou horizontales pour des groupements respectivement horizontales et verticales.

Finalement, on accomplit une table de reconstruction en traçant des lignes horizontales et verticales correspondantes qui connectent toutes les paires d'intersection de la ligne. La découverte du tableau et sa reconstruction sont illustrées ci-après :

c) Les Résultats expérimentaux

Le corpus pour l'évaluation de la méthodologie proposée a été préparé en sélectionnant 102 images avec un total de 2813 Ground-truthed (terre-verité) des lignes horizontales et verticales. Il consiste en scannant de formulaires, journaux, des magazines, des travaux scientifiques, billets de banque, chèques, des certificats et documents manuscrits.

La plupart des images ont des problèmes sévères tel que la qualité qui peut être pauvre, des lignes cassées ou des texte recouverts par des régions des lignes. Les chercheurs qui ont développé ces recherches ont utilisé un tableau de « MatchScore » pour les lignes horizontales et verticales dont les valeurs sont calculées d'après l'intersection des résultant des pixels des lignes et les gound thruth. Une performance globale métrique peut être détectée si l'on combine le taux de la découverte et les résultes l'exactitude de la reconnaissance selon à la formule suivante:

(a) image Initiale; (b) la détection des intersections des lignes; (c) Image sans lignes horizontales et verticales; (d) Reconstruction du tableau.

Exemple : si le taux de reconnaissance est de 93% et l'exactitude de reconnaissance de 99%, la performance globale métrique sera de :

Nous avons apprécié cette méthode, c'est pour quoi nous l'avons mise entre vos mains via ce travail, mais aussi parce que la reconnaissance globale métrique est améliorée que le taux de reconnaissance est croissant.

Cette méthode n'étant pas la seule pour appréhender les tableaux, voyons la suite.

II.2. RECONNAISSANCE DE DOCUMENTS A TABLEAU-FOMULAIRE

DETERIORE: NOUVELLE APPROCHE( En anglais:RECOGNITION OF

Cette deuxième méthode de reconnaissance d'un tableau duquel nous voulons parler a été réalisée par Luiz Antonio Pereira Neves et Joao Marques de Carvalho et Jacques Facon7(*). Le premier et le deuxième sont de l'université UFCG :Universidade Federal de Campina Grande - Campina Grande, PB, et le troisième de l'université 2PUCPR :Pontifcia Universidade Catolica do Parana - Curitiba, PR, tous du Brésil

Ces chercheurs ont développé une approche qui tient compte des tableaux qu'ils appellent détériorés. Ce sont des tableaux inclinés légèrement lors du scanning ou ceux qui présentent des coins vides ou traits qui ne sont pas finis (intersection des traits qui ne se touchent pas).

la méthodologie concerne la découverte ou la détection des formes taleau-formulaire. Pour l'extraction réussie de la forme des cellules, on utilise les étapes suivantes :

L'EXTRACTION DE LA STRUCTURE PHYSIQUE Cette structure a trois phases qui sont détaillées comme suit :

-La correction de l'angle d'inclinaison de l'angle : rotation de laisser passer avec interpolation bilinéaire

-l'opération de l'érosion produit des images contenant uniquement des racines des coins correspondant aux éléments structurels utilisés

Tous les coins types reconnus sont stockés dans un tableau des réels suivant :

Remarquez que tous les coins qui ne se touchent pas sont représentés par des zéros dans la matrice Tableau des réels. Si l'on construit une autre matrice constituée par les éléments de l'image et que l'on représente les traits par des chiffres différents de zéro et les zones vides par des zéros, on aura construit la matrice appelée tableau des réjections ou encore tableau des refus.

L'EXTRACTION DE LA STRUCTURE LOGIQUE Elle peut être détaillée par trois phases suivantes:

- Chaque intersection des voisins est comparée à la référence du voisinage du tableau de réjection

En comparant le voisinage du tableau des réels au voisinage des éléments du tableau de rejection on détecte des fausses intersections car, celles-ci seront représentées dans la matrice de réjection par une succession des zéros dans tous les coins.

Il y a erreur d'intersection si le tableau d'erreurs donne un résultat suivant :

Si une mauvaise intersection est trouvée dans le tableau des réels suivant une ligne, cette ligne est prolongée jusqu'à l'intersection. Cette erreur est corrigée de nord, sud, est et ouest de l'erreur. Ces opérations sont représentées par les étapes suivantes :

Les erreurs corrigées, on a en fin un tableau interprétable facilement et dont les paramettres à savoir les lignes et les colonnes sont bien reconnues.

Les parties hierarchiques du document étant connues et l'extraction des cellules atant faite par l'analyse de sa forme grâce à l'interprétation de ses points des coins dans la structure hierarchique, il ne restera qu'à traiter les cellules individuellement et reconstruire le tableau après reconnaissance.

II.3. LA RECONNAISSANCE EFFECTIVE ET LA METHODE D'EXTRACTION DES DONNEES POUR LES DOCUMENTS TABLEAU-FORMULAIRE( En anglais : AN EFFICIENT RECOGNITION AND DATA

EXTRACTION METHOD FOR TABLE-FORM DOCUMENTS)8(*)

Cette méthode est developpée depuis dans le laboratoire « Workshop on Machine Vision Applications »1996 par les japonais Lin Yu Tseng et Rung-Ching Chent du département de Mathématique appliqué de l'université national de Chung Hsing Taichung en Taiwan.

5) 1. Etude

Dans cette méthodologie de la reconnaissance optique des documents, le système doit d'abord étudier le document pour le reconnaître par après et extraire les données de ses champs.

Il faut extraire tous les segments des lignes horizontales, les segments des lignes verticales ainsi que et les segments des lignes penchées ou obliques du document.

Chaque segment de la ligne est représenté par ses deux points terminaux P1(x1, y1) et P2(x2, y2) sachant que les segments sont droits possibles. Pour le segment de la ligne horizontale, le P1 représente le point terminal gauche et p2 le point terminal droit, pour le segment de la ligne vertical P1 représente le point terminal inférieur et P2 le point terminal supérieur ; pour les segments de la ligne penchée, Le P1 représente le point terminal bas et P2 le point terminal supérieur.

Quand les segments des lignes auront été extraits, la question ne rentrera qu'à former le tableau. Ainsi, faudra-t-il vérifier si le tableau formulaire est oblique. Apre que tous les segments de la ligne seraient extraits, l'échelle du document est normalisée à LxH. Alors toutes les coordonnées des points finaux des segments ligne sont normalisées en conséquence.

Tous les segments des lignes horizontales sont assortis par leur mouvement du sommet à le fin de P1 et pour ceux là avec le même mouvement de gauche à droite de y1. Tous les segments de la ligne vertical sont assortis par leur mouvement de gauche à droite de leur P1, et pour ceux ve horizontale, le même mouvement du sommet vers la fin pour X1. Tous les segments de la ligne penchée sont aussi assortis dans le même sens par leur P1, comme c'est le cas des segments des lignes qui seraient horizontales et verticales.

Un document est alors représenté par le nombre des segments de la ligne horizontal, le segment de la ligne verticale, le segment de la ligne penchée et les trois séquences assorties mentionnées ci haut.

Un document de tableau formulaire est scanné et desobliqué par le processus si c'est nécessaire, trois types des segments de la ligne sont extraits et une représentation de ce document est obtenue. Dans un document la reconnaissance du tableau, il y a trois types des champs à savoir : le champs de nom, le champs des données et le champs mixte. Un champ mixte est une combinaison des champs de nom et de champs des données

Le segment de la ligne penchée, les points limites de tous les champs peuvent être déterminés.

Avec une analyse de l'intérieur d'un champ, ce champ peut être déterminé pour être un champ de donnée ou de nom/champs mixte.

Les utilisateurs sont aussi demandés à fournir si possible quelques attributs pour chaque champ des données à travers l'interaction de l'interface utilisateur. Cette information peut plus tard aider le logiciel de reconnaissance optique des caractères à reconnaître plus facilement les blocs des textes extraits dans les champs des données.

Nous avons remarqué dans les méthodes devéloppées dans les phrases précédentes que, le reconnaissance des tableaux peut être faite de différentes manières et avons montré quelques unes. Dans le chapitre qui va suivre, nous allons parler d'une autre façon de le faire. Nous allons la présenter et en proposer un algorithme.

CHAPITRE III. RECONNAISSANCE OPTIQUE DES

TABLEAUX

La reconnaissance optique des tableaux est une partie de la reconnaissance des formes. Avant d'éxaminer les méthodes et les manières avec lesquelles nous avons apprécié les étapes de la reconnaissance des tableaux, envisagons d'abors la reconnaisance des forme elle-même.

III.1. LA RECONNAISSANCE DES FORMES

On désigne par reconnaissance de formes (appelée parfois reconnaissance de motifs) un ensemble de techniques et méthodes visant à identifier des motifs à partir de données brutes afin de prendre une décision dépendant de la catégorie attribuée à ce motif. On considère donc la reconnaissandce des formes comme une branche de l' intelligence artificielle qui fait largement appel aux techniques d' apprentissage automatique et aux statistiques.

Les motifs à reconnaitre peuvent être de diverses natures; il peut s'agir de contenu visuel (code barre, visage, empreinte digitale...) ou sonore (reconnaissance de parole), d'images médicales ou multispectrales (images satellitaires) et bien d'autres.

Dans le cas de ce trvail par exemple il s'agira comme nous l'avons signalé de reconnaitre un tableau trouvé sur une image en deux dimensions.

Rappellons ensuite que la reconnaissance de motifs peut être effectuée au moyen de divers algorithmes d' apprentissage automatique tels:

a) Application de la reconnaissance des formes9(*):

Un algorithme bien connu pour la détection de formes, la transformée de Hough, est une méthode d'estimation paramétrique.

Cette méthode caractérise une forme et extrait des paramètres caractéristiques de l'objet et les comparent par une méthode de classification ou de mise en correspondance à une base d'apprentissage. Par cette méthode, il est impossible d'extraire plusieurs formes de la même image sans pré-traitement.

Dans cette approche, on extrait des points caractéristiques d'objets comme les coins via les détecteurs de Harris puis on extrait des caractéristiques aux voisinage de ce point. Avec ces caractéristiques, il est possible d'extraire plusieurs objets et de faire la reconnaissance de ceux-ci via un classifieur.

III.2. LA RECONNAISSANCE EN LIGNE

Ce mode de reconnaissance des caractères généralement maniscrite s'opère en temps réel (pendant l'écriture). Les symboles sont reconnus au fur et à mesure qu'ils sont écrits à la main.

C'est une approche «signal» où la reconnaissance est effectuée sur des données à une dimension. L'écriture est représentée comme un ensemble de points dont les coordonnées sont en fonction du temps

Dans le cadre de la reconnaissance en-ligne, l'échantillon d'encre est constitué d'un ensemble de coordonnées ordonnées dans le temps. Il est ainsi possible de suivre le tracé, de connaître les posés et levés de stylo et éventuellement l'inclinaison et la vitesse. Il faut évidemment un matériel spécifique pour saisir un tel échantillon, c'est le cas notamment des stylos numériques ou des stylets sur agendas électroniques ou sur les Tablets PC.

La reconnaissance en-ligne est généralement beaucoup plus efficace que la reconnaissance hors-ligne dont nous allons parler plus tard car ses échantillons sont beaucoup plus informatifs. En revanche, elle nécessite un matériel beaucoup plus coûteux et impose de fortes contraintes au scripteur puisque la capture de l'encre doit se faire au moment de la saisie (capture synchrone) et non a posteriori (capture asynchrone).

Les techniques usitées peuvent avoir un champ applicatif plus vaste permettant la reconnaissance de toute forme abstraite simple. Les systèmes actuels procèdent majoritairement par une comparaison de l'échantillon à reconnaître avec ceux contenus dans une base de données. Cette base de données peut être créée de toutes pièces ou être l'objet d'une phase d'apprentissage.

Les techniques de comparaison reposent généralement sur des méthodes statistiques simples pour gagner en vitesse de traitement. La conséquence est que le nombre de formes reconnaissables doit être limité, sans quoi les résultats risquent d'être souvent erronés. En effet, toute la difficulté de la reconnaissance est d'évaluer la similarité entre une forme étudiée et chaque forme de la base de données (il est presque impossible qu'il y ait une correspondance exacte). Il suffit alors de choisir la forme la plus similaire. La reconnaissance idéale doit avoir la même évaluation de similarité que le cerveau, ce dont on se rapproche avec les réseaux de neurones. Mais les méthodes plus rapides (moins complexes) évalueront une similarité entachée d'erreur. Lorsqu'il y a peu de formes dans la base de données, bien séparées, la forme la plus similaire restera la même, et donc le résultat final sera juste. En augmentant la taille de la base des données, on « rapproche » nécessairement les formes modèles entre elles, et l'erreur sur la similarité peut plus facilement faire pencher la balance vers une mauvaise forme.

III.3. LA RECONNAISSANCE HORS LIGNE

La reconnaissance hors-ligne travaille sur un instantané d'encre numérique (sur une image). C'est le cas notamment de la reconnaissance optique de caractères mais égalemant de la reconnaissance des données scannées. Dans ce contexte, il est impossible de savoir comment ont été tracés les différents motifs. Il est seulement possible d'extraire des formes à partir de l'image, en s'appuyant sur les technologies de reconnaissance de forme.

C'est le type de reconnaissance privilégié pour les traitements asynchrones, tels que la lecture de chèques bancaires ou le tri postal, la lecture des bordereaux... Cette reconnaissance en est beaucoup utilisé.

Le présent travail ne fera pas la reconnaissance en temps réél, ne suivra pas le posé et le lèvé du stylet pour en savoir les coordonnées des pixels en fonction du temps,... il est alors utile d'éclairer que cette reconnaissance hors ligne être serait appliquée aux images qui proviendraient du logiciel du présent travail une fois la séparation des cellules effectuée.

III.4. LA REEDITION DES DOCUMENTS

Comme nous l'avons signalé dans les chapitres précédents, il est vrai que lorsqu'on veut assurer des modifications sur les informations se trouvant sur des papiers, il est important de bien les rééditer à base d'un ordinateurs, afin soit de les diffuser ou de les utiliser ultérieurement.

Si le doccument est disponible, on peut recourir à sa version éléctronique( si elle existe) pour pouvoir l'améliorer davantage. En l'absence de la version éléctronique, on peut reprendre la réedition au format éléctrnique, ce qui causera une perte de temps unitile surtout quand des rectifications nécessaires sont minimes.

Un système de reconnaissance de document sera facile et on aura la facilité de conserver une copie d'archive en version éléctronique pour un usage ultérieur^10(*). Bien avant de reconaitre un document il faut tout d'abord le scanner ; cépendant, au moment du scanning, des éventuels problèmes peuvent se poser. Voyons en quelques sorte comment les éviter.

III.5. SCANNING NON INCLINE DES DONNEES

Le moment crucial et déterminatif pour la reconnaissance des tableaux commence par le processus du scaning du document à reconnaitre grâce à un scanner(plus rarement appelé numériseur de document). C'est un périphérique informatique qui permet de transformer un document en une image numérique. Le document est soumis au balayage d'un rayon lumineux.. Pour cette tâche beaucoup de scanners existent et peuvent être de type diversifié. Nous allons illustrer deux de ces types pour bien viser le problème lié au scanning incliné des documents à reconnaitre optiquement. Le scanner peut être à plat,à défilement, à main, à diapositive, etc.

Pour que l'humain reconnaisse une image percue par son oeil, il lui faut l'identifier soit par sa forme, sa couleur ou encore sa longeur ou sa surface. Il faut donc des détails structurels de la chose percue.

Il faudra développer un algorithme consistant à identier les valeurs représentant ses couleurs, rendre l'image en noir et blan, retrouver le tableau proprement dit sur l'image et l'extraire, identifier le nombre de linges et de colonnes du tableau, détérminer et tirer les cellules. Bien anvant d'entammer ces étapes, il faut tout d'abord veiller à bien scanner le document.

Il est dificile voire impossoble de scanner avec un scanner plat sans que le vent de glisse la feuille pour qu'elle s'incline meme si elle était bien droite horizontale, le scanner à defilement est le mieux adapté pour éviter tant peu que soit cette objection. En effet, Ce procédé est principalement utilisé dans le monde bureautique car il ne s'applique qu'aux documents sur feuille volante de grammage et de format standard. De ce fait le document passera horizontalement posible dans les machoires du scanner

Ces scanners évitent l'inclinaison de l'image qui serait due à la force de vent bascule de manière négligeable le document pour le type précédent.

Beaucoup d'autres actuces pour rendre droite un objet sur une image sont possibles grâce aux disposotifs de la reconnaissance des formes.

Ainsi, par l'alalyse discriminante linéaire(LDA)11(*) utilisant la transformation linéaire de Ficher et la projection des données d'une dimension d sur une ligne de dimension 1 (passant par l'origine), on peut parvenir à tourner une image selon un modèle.

Nous devons garder à l'esprit qu'un algorithme est un langage de description des étapes de la résolution d'un problème. Il doit en son sein :

Un algorithme concerne la fourniture de la solution à un problème, sa première étape consiste donc à analyser le problème, c'est-à-dire en cerner les limites et le mettre en forme dans un langage descriptif, on parle généralement d'analyse pour décrire le processus par lequel le problème est formalisé. Le langage de description utilisé pour écrire le résultat de l'analyse est appelé algorithme. L'étape suivante consiste à traduire l'algorithme dans un langage de programmation spécifique, il s'agit de la phase de programmation^13(*).

Le problème que nous avons à résoudre dans ce cadre de ce trvail, nous allons suivre les étapes suivantes :

1° TRANSFORMATION DE L'IMAGE EN NIVEAU DE GRIS

Le traitement d'images en couleurs codées sur 24 bits donne à peu près 16,7 millions des différentes couleurs dont certaines se rapprochent du noir et d'autres du blanc.

Les pixels d'une image en couleur étant colorés de différentes manières, les nombres écris dans ces pixels sont différents. Pour faciliter l'analyse et pour prêter l'image à une opération qui ne consistera à ne traiter que peu de valeurs et ainsi améliorer l' éfficacité dans les test des pixels, il faut tout d'abord rendre l'image en niveau de gris en trouvant pour chaque pixel la somme de ses trois valeurs et écrire la moyenne trouvée trois fois dans le même pixel. Cela a traduit l'image de couleur en noir et blanc.

2°DETERMINATION DES LIGNES ET DES COLONNES DU

TABLEAU

En reconnaissance des données retrouvées dans des tableaux ou dans des documents simillaires ,l'étape préalable et qui facilite la suite est la détérmination des lignes et des colonnes du tableau ; la détermination des limites des cellules en est une autre. Mais néanmoins, nous ne devons pas oublier que les cellules se trouvant sur une meme ligne ont la même hauteur et celles se trouvant sur une même colonne ont le même largeur.

dans les parties introductives de ce travail, nous avons signifié que nous allons utiliser des tableaux qui sont verticalement possibles sur les images bitmap. C'est-à-dire, les tableaux non inclinés ou non obliques, par conséquent les cellules et les données ne les seront pas aussi.

Pour détérminser les lignes nous avons projété horizontalement les valeurs des pixels comme le montre le cas du tableau sans données suivant en gris :

Projection horizontale
	1	2	3	4	5	6	7	8	9	10	11	12	13	14
1
12
12
1
12
12
12
12
12
1
12
1
14

Avec les valeurs projettées du tableau précédent nous pouvons tracer un graphique et placer à l'axe des abscisses les valeurs de la projection horizontale et à l'axe des ordonnées les numéros des colonnes. Nous obtenons le graphique qui suit : y=f(x) : projection horizontale en fonction des lignes de l'image su tableau.

Deux cas sont possibles après cettte première projection ( voir l'histogramme)

· les noirs sont très longs que les blancs : cas d'un tableau à lignes pleines ;

· les blancs sont très longs que les noirs : cas d'un tableau à lignes vides.

La courbe représentée sur le graphique précédent est y=f(x) a généralement le forme sinizoïdale ; elle décroit que les tracés des lignes hozontales croissent et croit quand les zones intérieures des cellules augmentent.

Vue que les valeurs projetées sont les moyennes des pixels rangés horizontalement, et vue que la zone en nuance de gris du tableau réprésente le tracé du tableau sur l'image, nous remrquerons que les projections des tracés séparant les lignes ont des valeurs inférieurs(indice de 1 pour le cas d'espece).

La distance a représente les valeurs intérieures d'une ligne du tableau à reconnaître ou ensemble des lignes de l'image qui font la ligne du tableau.

Nous pouvons alors compter les lignes du tableau en parcourant uniquement les projections horizontales sachant que partout où nous trouvons une valeur inférieur à un indice calculé, nous conclurons que c'est un tracé horizontal.

Quand nous parcourons les projections et que nous trouvons les valeurs réprésentant les tracées des séparateurs des lignes vue leur infériorité, nous pouvons à ceniveau indéxer les limites des lignes. Ce sont ces limites qui nous interesseront plus tard.

Par ce que les projections horizontales nous ont permis de détérminer les lignes et leurs limites, les projections verticales quant à elles nous permettrons de déterminer les colonnes et les limites y afférentes.

Comme pour la projections horontales, la projection verticale facilitera la détérmination des colonnes et de ses limites.

Si nous représentons sur des l'axe des ordonnée les projections verticales et sur l'axe des abscisses les colonnes, nous aurons le graphique suivant :

La courbe représentée sur le graphique précédent est y=f(x) a généralement le forme sinizoïdale ; elle décroit que les tracés des colonnes verticales croissent et croit quand les zones intérieures des cellules augmentent.

Les parties élevées du graphique projettées sur l'axe des colonnes donne les intérieurs des colonnes séparateurs. C'est le cas de la distance b Ainsi, les trois parties de la courbe qui touchent par l'indice deux donnent les colonnes du tracé.

Sachant les limites des lignes et celles des colonnes par les lignes qui ont précédées, il ne nous restera que de déterminer les cellulles qui ne seront que des intersections intérieurs des limites des lignes et des coloinnes.

3° ACCES AUX CELLULES GRACES AUX LIMITES

Nous savons que les tableaux que nous parcourons n'ont pas des cellulles fusionnées par lignes ou par colonnes, c'est-à-dire que toutes les cellules d'une ligne ont une même huteur, et celles trouvées sur une même colonne ont une meme largeur. c'est pour cette raison que, quand nous avons déjà les limites des cellules par ligne et ceux séparant les colonnes, nous ne pouvons que parcourrir le tableau pour en fin de trouver les cellules correspondates.

Voici dans la méthode ci-bas :si nous entrons en ergument, deux limites de la ligne et de la colonne, nous pouvons avoir accès à toutes les cellules du tableau.

Dans la méthode suivante, l'image entière se trouvant dans le tableau « r »,la fonction ne demande en argument que les limites des lignes et celles des colonnes pour rétourner un petit tableau correspondant à une cellule.

Le tableau contenant une cellule suffit pour retourner une image bitmap ayant sa largeur, sa hauteur et son contenu décimal qui en retournera le corps.

Nous avons affiné les notions spacieuses sur l'algorithme de reconnaissance des tableaux. Nous avons aussi joint à ce travail un programme capable dematérialiser nos phrases. Le chapitre suivant donne succintement et le fonctionnalités du logiciel proposé.

CHAPITRE IV. SIMULATION DE LA RECONNAISSANCE DE

TABLEAU PAR UN LOGICIEL INFORMATIQUE

Au chapitre précédent nous avions donné un algorithme qui nous a permis de reconnaitre un tableau contenant ou pas des données; ce tableau doit être sur une image bitmap, pour que le programme le reconnaisse et retourne les cellules et les données correspondantes dans des différentes images facilement traitables par des logiciles de ROC. Remarquez que les quelques instructions contenus dans les méthodes présentées sont en langage Java. Nous avons ensuite affiché les images retournées et converties en .jpeg dans des pages web grâce au Html.

Il est vrai que les pages du HTML n'acceptent pas des images Bitmap, les formats autorisés sont GIF (256 couleurs) JPEG (16 millions couleurs) (les autres sont fortement déconseillés)^14(*), mais à nos jours, HTML accepte les images PNG et XBM .

Pour passer les Images du format BITMAP au format JPEG, nous avons utilisé le langage Postscript qui nous a fourni pour chaque transmission un fichier texte sous l'estention « .ps» que nous avons supprimé automatiquement après utilisation.

Nous avions choisi le langage java pour la reconnaissance des formes vues sa facilité dans le traitement des images et sa portabilité, sa tenacité par l'utilisation d'objets, sa propriété d'être non payant et plus encore, en raison de sa documentation qui reste abondante.

Même si nous avons utilisé comme éditeur JCreator 3.50 LE, nous vous laissons libre de faire le choix de l'éditeur.

Il est vérifiable que tous les programmeurs ou groupe des programeurs veuillent à ce que leur produit remplisse certains critères notamment :

1. L'exactitude : aptitude d'un logiciel à fournir le résultats voulus, dans des conditions normales d'utilisation (par exemple, des données correspondant aux spécifications) ;

2. La robustesse : aptitude à bien réagir lorsque l'on s'écarte des conditions normales d'utilisation ;

3. L'extensibilité : facilité avec laquelle un programme pourra être adapté pour satisfaire à

4. La réutisabilité : possibilité d'utiliser certaines parties du logiciel pour résoudre un autre

5. La portabilité : facilité avec laquelle on peut exploiter un même logiciel dans différentes implémentations ;

Signalons que le langage postscript est un langage interpreté ; le java est quant à lui, un langage compilé. Le langage qui nous a permis de transformer les images BITMAP en image JPEG est bel et bien le postscript. Il se caractérise de diverse manières.

1) Caractéristique du Postscript

Le PostScript est un langage informatique spécialisé dans la description de pages, mis au point par Adobe. Il repose sur des formulations vectorielles de la plupart de ses éléments. Il sait aussi traiter les images matricielles (en mode point). Ce langage inter-plateformes permet d'obtenir un fichier unique comportant tous les éléments décrivant la page (textes, images, polices, couleurs, etc.).

Postscript est un langage complet, qui permet le codage de tout algorithme d'impression, raison pour laquelle il est standartisé.

Bien qu'il soit tout à fait possible d'écrire directement de tels programmes, ils sont en général fabriqués par d'autres programmes, des pilotes d'impression par exemple.

Le Postscript est indissociable de l'environnement dans lequel il sera exécuté. Étant donné le caractère totalement dynamique de ce langage, il est alors un langage tout à fait interprété.

Un interprète, ou interpréteur, est un outil informatique ayant pour tâche d'analyser, de traduire et d'exécuter un programme écrit dans un langage informatique.

2) Le document à reconnaitre

Dans les phrases introductives de ce travail, nous avons signalé que pour la reconnaissance, nous avons consideré les tableaux utilisés dans pour l'enregistrement d'étudiants et avons consideré les années allant de 2000 à 2010.

Au cours de cette période, la forme du document constituant les listes des étudiants inscrits a changé des années à d'autres. C'est pourquoi nous n'allons pas les illustrer tous mais, avons choisit certrains parmi eux que nous avons testé par notre logiciel qui les a reconnus sans problème.

Ainsi, nous présentons ci-bas un des documents que nous avons scanné et avons testé sa reconnaissance avec notre logiciel :

3) Guide de l'utilisateur

A l'exécution du programme de ce travail écrit en java, vous serez sans doute à votre écran, la page d'accueil suivante qui ne vous demandera que des informations sur ce dont il est question

: Sur cette page, vous avez l'amabilité soit de quitter ou de continuer en cliquant respectivement sur Quitter le programme ou sur Démarrer le programme.

Si vous quittez, vous retournez au mode console, sinon vous continuez avec la page suivante à laquelle vous pouvez immédiatement effectuer les opérations suivantes :

- Reconnaissance des lignes et les colonnes par la détérmination des limites des cellules;

Ces opérations citées vous pouvez les effectuer en cliquant dans l'illustration suivante sur les commandes du menu Fichier suivantes : Synchroniser avec gris :reconnaître le tableau en transformant d'abord l'image en niveau de gris ou Synchroniser sans gris : reconnaître sans passer l'image en nivreau de gris.

Les images retournées auront comme noms de fichiers la première le nombre de leur ligne et leur colonne dans l'image. Par exemple « 1-1.bmp » pour l'image de la première ligne et la prémière colonne.

Il est imératif de taper le nom de fichier image d'entré à reconnaitre dans la boite de dialogue comparable à celle truvée sur l'image sivante:

Lorsque l'écriture des images de sortie sera faite avec succès, cela va vous être signalé dans la boite de dialogue suivante:

Le HTML est un langage dit de « marquage » (de « structuration » ou de « balisage ») dont le rôle est de formaliser l'écriture d'un document avec des balises de formatage. Les balises permettent d'indiquer la façon dont doit être présenté, le document et les liens qu'il établit avec d'autres documents.

Le langage HTML permet notamment la lecture de documents sur Internet à partir des machines différentes, grâce au protocole HTTP, permettant d'accèder via le réseau à des documents repérés par une adresse unique, appelée URL.

On appelle WWW ou tout simplement Web (mot anglais signifiant toile) la "toile virtuelle" formée par les différents documents (appelés « pages web ») liés entre-eux par des hyperliens.

Les pages web sont généralement organisées autour d'une page d'accueil, jouant un point central dans la navigation à l'aide des liens hypertextes. Cet ensemble cohérent de pages web liées par des liens hypertextes et articulées autour d'une page d'accueil commune est appelée site web.

Le Web est ainsi une énorme archive vivante composée d'une myriade de sites web proposant des pages web pouvant contenir du texte mis en forme, des images, des sons, des vidéo, etc.

Dans notre travail, nous allons utiliser les pages de html comme des états de sorties pouvant restructurer sur elles les images scendées.

Il sera abérant de ne pas avoir un navigateur et vouloir visualiser les images de sortie. Il est alors important d'installer un navigateur. Parmi les principaux navigateurs utilisés sur Internet, citons :

La page html est optenue en executant la commande page html du menu Edition comme cela est montré dans l'illustration suivante :

C''est après cette commande que vous ouvez à consulter la page html se logeant dans le même repertoire que le prgramme.

CONCLUSION

Nous voici à la fin de notre travail qui a porté sur la reconnaissance optique des données numériques, et ayant consideré les documents tableau scanné sur une image de type bitmap.

Sachant que les logiciels de reconnaissance optiques des caractères sont déjà disponibles, ceux-ci rencontrent des problèmes énormes pour des données se trouvant dans des tableaux. Le présent travail a examiné les possibilités de reconnaitre optiquement les différentes zones sémentiques d'un tableau des données et a remis dans les images separées les cellules particulières pouvant être traitées sans failles par les logiciels de reconnaissance des caractères.

Le résultat offert par l'application que nous avons réalisé en nous servant de l'algorithmique de la détermination des pixels des limites du tableau et la l'identification des limites des cellules confirme bien notre hypothèse ; les cellules du tableau et leurs données retournées dans des petites images sont traitées par ces logiciels de reconnaissance comme des simples pages sans des tableaux. Nous avons convertie automatiquement les images bitmap scindées en des images jpeg via les fichiers postscrip et avons affiché sur une page de html un échantillon comme état de sortie.

Toutefois, un vaste champ de recherche reste ouvert aux futurs chercheurs, qui pourront reconnaitre de manière optique les graphiques, les schémas et leurs interprétations. Tout travail humain étant sujet à des imperfections et coquilles, nous disons bienvenues aux suggestions et remarques d'autres chercheurs qui pourront élargir de plus les fronitières de la science.

BIBLIOGRAPHIE

· Lin Yu Tseng et Rung-Ching Chent, an efficient recognition and data extraction method for table-form documents , Département de Mathématique appliqué,L'université national de Chung Hsing Taichung en Taiwan,1996.

· Luiz Antonio Pereira Neves , Joao Marques de Carvalho et Jacques Facon, la Recognition of deteriorated table-form documents: a new approach, brazil,2009.

· Dieudonné KYENDA SULIKA, cours de LOGIQUE ET CONCEPTION DES PROGRAMMES G1 I.G. /ISP BUKAVU, inédit, 2006.

· Olivier MOTOMOKE MONGA, Cours d'Algorithmique et Programmation, inédit, science et école polytechnique, université libre de Bruxelles,2005.

TABLE DES MATIERES

BIIOGRAPHIE...............................................................................................................................................61

BIOGRAPHIE

Richard ISHARA Kibasomba, né le 27 Juillet 1985 à Bukavu, est un Gestionnaire, Informaticien, concepteur programmeur, Electricien Congolais, il fit ses études matérnelles, primaires et secondaire a l'institut d'Ibanda de Bukavu, ses études humanitaires techniques a l'Institut technique avenir et recu son diplôme d'Etat en Eléctricite Industrielle en RDCongo.

Il fut ses études superieurs a l'ISP/Bukavu et optenu son diplôme de licencie en informatique de Gestion dans l'année académique 2009-2010.

* ⁷Luiz Antonio Pereira Neves , Joao Marques de Carvalho et Jacques Facon, Recognition of deteriorated table-form documents: a new approach, Brazil,2009.

* ¹⁰ KYENDA SULIKA, reconnaissance dynamique des formules mathématiques, Mémoire DEA, 2005.

La reconnaissance optique de tableaux numerises : listes des étudiants inscrits de l'ISP/Bukavu

PRELUDE

EPIGRAPHE