CIDE (2009) Ouwayed
Une approche générale pour l’extraction de lignes des documents Arabes anciens multi-orientés
|
Sommaire
- Résumé
- Dans cet article, nous présentons une nouvelle approche pour l’extraction de lignes des documents Arabes anciens multi-orientés. En raison de la multi-orientation de lignes et de leur dispersion dans l’image, nous utilisons un maillage automatique de l’image qui nous permet de déterminer progressivement et localement les lignes. Le maillage est initialisé avec une petite fenêtre où sa taille est corrigée par extension jusqu'à ce que suffisamment de lignes et de composantes connexes ont été trouvées. Nous utilisons le Snake pour l’extraction de lignes. Une fois le document est divisé en fenêtres, l’orientation est déterminée en utilisant la distribution de Wigner Ville (DWV) sur l'histogramme de projection. Ensuite, cette orientation locale est élargie pour limiter l'orientation dans les fenêtres voisines. Ensuite, les lignes de texte sont extraites localement dans chaque zone en se basant sur le suivi des lignes de base et la proximité des composantes connexes. Enfin, les composantes connexes qui se chevauchent et se connectent dans les lignes adjacentes sont séparées en considérant la morphologie des lettres terminales des mots Arabes. L'approche proposée a été expérimentée sur 100 documents atteignant une précision d’environ 97.6%.
- Abstract
- This paper presents a novel approach for the multi-oriented text line extraction from historical handwritten Arabic documents. Because of the multi- orientation of lines and their dispersion in the page, we use an image paving allowing us to progressively and locally determine the lines. The paving is initialized with a small window and then its size is corrected by extension until enough lines and connected components were found. We use the Snake for line extraction. Once the paving is established, the orientation is determined using the Wigner-Ville distribution (WVD) on the histogram projection profile. This local orientation is then enlarged to limit the orientation in the neighbourhood. Afterwards, the text lines are extracted locally in each zone basing on the follow- up of the baselines and the proximity of connected components. Finally, the connected components that overlap and touch in adjacent lines are separated. The morphology analysis of the terminal letters of Arabic words is here considered. The proposed approach has been experimented on 100 documents reaching an accuracy of about 97.6%.
Introduction
La segmentation du texte en lignes est vue comme une étape nécessaire dans le domaine d'analyse de document avant la reconnaissance des mots. La difficulté de cette tâche vient des caractéristiques des documents manuscrits et particulièrement lorsqu’ils sont anciens (voir Figure 1).
Ces documents présentent des espacements irréguliers entre les lignes et des fluctuations de la ligne de base de l’écriture par rapport à l’horizontale. Les lignes ont des longueurs différentes et peuvent se chevaucher ou se connecter lorsque leurs hampes et leurs jambages appartiennent à deux lignes consécutives. En outre, les lignes sous forme d'annotations peuvent exister dans les marges. Ces lignes sont en général obliques en raison de la réduction de l'espace qui constitue de nouvelles orientations. Par exemple, la Figure 1.a contient 4 annotations. La présence massive des points diacritiques complique en plus cette tâche. Également, l'écriture manuscrite arabe présente de grandes variations, dans les formes des lettres ou des mots, et dans la mise en page.
L’article est organisé comme indiqué ci-après. Dans la Section 2, nous présentons les techniques existantes pour l’extraction des lignes. Les différentes étapes de notre approche pour l’extraction de lignes multi- orientées dans les documents arabes manuscrits sont détaillées dans la Section 3. Nous présentons dans la Section 4 nos résultats expérimentaux et une conclusion dans Section 5.
État de l’art
Dans la littérature, deux classes d’approches existent pour l’extraction de lignes : descendant et ascendant. Les approches descendantes sont essentiellement basées sur la technique de la projection. Dans [9 , 16 , 23 ], la projection horizontale est appliquée au document entier ou à une bande (horizontale ou verticale) de celui-ci. Ensuite, les maxima et les minima sont déterminés et les composantes connexes entre deux minima consécutifs sont recherchées. Ces composantes connexes forment la ligne.
Les approches ascendantes sont basées sur le bas niveau (pixel ou composante connexe). Dans cette catégorie, nous trouvons la classification par k-ppv (plus proches voisins), la transformée de Hough, la technique du lissage (smearing), et la technique de répulsif-attractif. Dans la classification par k-ppv [12 ], les alignements sont détectés en choisissant les composantes connexes, prolongées dans des directions spécifiques. Puis, les lignes sont extraites en groupant ces alignements selon trois critères : proximité, similitude et continuité de direction. Dans la transformée de Hough [13 , 20], les points votants sont les centres de gravités des composantes connexes. Un ensemble de points alignés dans l'image ayant un pique dans la transformée de Hough, représente une ligne. Dans la technique de lissage [8, 21], RLS (Run-Length Smoothing), les pixels noirs consécutifs sur la direction horizontale sont lissés. Les boîtes qui englobent les composantes connexes dans l’image lissée forment les lignes. Dans la technique de répulsif-attractif [18], les lignes de base qui représentent les forces attrayantes, sont construites une par une à partir du fond de l'image jusqu’au début. Dans l'image les pixels représentent les forces répulsives. Les forces répulsives-attrayantes entre deux lignes de bases consécutives sont étudiées pour déterminer les lignes du document. D’autres méthodes utilisent le principe de regroupement par l'arbre couvrant minimal (MST : Minimum Spanning Tree). Dans [5], Yin et Liu ont proposé une méthode fondée sur le regroupement par MST avec l'apprentissage de distance. Compte tenu de la distance métrique, les composantes connexes de l’image sont regroupées dans une structure arborescente. Les lignes de texte sont extraites de l’arbre en coupant ses bords avec une fonction objective. Pour une description plus détaillée de ces méthodes les lecteurs sont invités à lire [14].
Toutes les approches citées ci-dessus sont soit trop globales, procédant par projection ou par recherche d’alignements, soit trop locales, opérant par suivi de composantes connexes. Elles trouvent ici leurs limites face à la mauvaise qualité et à la multi-orientation des documents. La méthode que nous présentons dans ce papier se base sur le maillage automatique de l’image, la détection des zones multi-inclinées et l’extraction locale des lignes.
Approche proposée
L'écriture dans les documents arabes manuscrits anciens est multi- orientées, tordue et bruitée. Pour cette raison, nous avons décidé de nous concentrer sur une méthode locale qui divise d'abord l'image en plusieurs fenêtres. Puis, elle estime l’orientation dans chaque fenêtre. Ensuite, elle applique des règles de correction et d’extension de l’orientation afin de trouver toutes les zones (une zone est un ensemble des fenêtres qui ont la même orientation) multi-inclinées. Enfin, elle suit les lignes de base pour extraire les lignes du document. Les lignes qui se chevauchent et se connectent sont séparées après dans une étape de post-traitement.
Maillage automatique
Dans cette étape, le document est partitionné en petites fenêtres de taille (w×h). Cette taille est automatiquement généré en se basant sur l'idée qu’une fenêtre doit contenir environ 3 lignes pour être capable de produire un histogramme de projection représentatif de l'orientation. Cela fait suite à plusieurs étapes. Tout d'abord, une première fenêtre de taille arbitraire (15×15 pixels) est placée au milieu de l'image (voir Figure 2.a). Ensuite, l’approche du Snake est appliquée pour calculer les lignes (voir les explications ci-après). La largeur de la fenêtre est agrandie jusqu'à ce que le Snake se donne au moins 3 lignes. Une fois les lignes sont trouvées, la hauteur moyenne⎯h est estimée ainsi que la distance moyenne entre les lignes⎯g. La distance entre les lignes est estimée en utilisant l’enveloppe convexe des lignes [15] (voir Figure 2.b). La fenêtre finale a une taille qui est égale à (w×h), où w = h = 3 ×⎯h + 2 ×⎯g (voir Figure 2.c).
Modèle de contour actif (Snake) : Le Snake est défini comme un contour virtuel qui va être emmené vers un contour réel dans l’image en utilisant un mécanisme de minimization d’énergie avec une méthode itérative qui le déforme [11]. Le Snake est un ensemble de points v(s)=[x(s), y(s)], où s [0,1]. Le contour final peut être obtenir en minimisant la fonction d’énergie suivante :
1 1 1
Esnake 0 Eint (v(s))ds 0 Eext (v(s))ds 0 Econt (v(s))ds
(1)
où Eint est l’énergie interne du Snake qui sert à la régularization du Snake (forme, convexe, etc..), Eext est l’énergie externe de l’image qui pousse le Snake vers les lignes, les contours des objets qui se trouvent dans l’image et Econt est l’énergie de contexte qui exprime certaines contraintes supplémentaires qui peuvent être imposées par l'utilisateur vu le Snake qu'il veut obtenir.
L’énergie externe traditionnelle est située sur les contours externes. Cela oblige à initialiser le Snake à proximité du contour cible. En outre, les valeurs du gradient ont des sens inverse sur les deux côtés du même contour, qui empêche le Snake d’entrer dans les concavités. Pour cette raison, Xu et al. [22] ont développé un nouveau type d'énergie externe qui permet d’initialiser le Snake loin du contour cible et d’aller vers les concavités. Cette énergie est nommé GVF (Gradient Vector Flow). GVF est défini comme un vecteur V(x, y) = (u(x, y), v(x, y)) qui minimise la fonction d’énergie suivante :
2 2 2 2 2 2 (ux uy vx vy ) f V f dxdy (2)
V peut être trouvé par les deux équations d’Euler :
u (u f
v (v f )( f 2 f 2 ) 0
)( f 2 f 2 ) 0 y x y
où est un paramètre de réglage de bruit. Pour trouver u et v, Xu et al. proposent dans [22] plusieurs implémentations numériques. Dans notre application, nous avons utilisées la GVF sur l’axe majeure de la composante connexe dans chaque fenêtre (voir Figure 3).
![](/Wicri/Sic/CIDE/fr/images/thumb/0/04/CIDE_%282009%29_Ouwayed_fig_3.jpg/400px-CIDE_%282009%29_Ouwayed_fig_3.jpg)
Détection des zones multi-orientées
Cette étape consiste à extraire la première orientation dans les fenêtres et les étendre vers les fenêtres voisines. Ces deux étapes se déroulent comme suit.
Estimation de l’orientation dans la fenêtre
Traditionnellement, l’estimation de l’orientation est faite en analysant l’histogramme de projection [9, 16, 23] ou par une autre méthode comme la transformée de Fourier [19]. Cependant, ce découpage en petites fenêtres peut parfois favoriser les orientations individuelles des mots à celle des lignes. Nous corrigeons ce biais en utilisant une distribution énergétique de Cohen [6, 7, 10] sur le profil de projection. Cette distribution réagit mieux que la projection aux pics engendrés par les lignes en traduisant leur présence en forte énergie. En effet, l’histogramme de projection crée des faux maxima qui perturbent l’extraction de l’orientation. Nous nous sommes limités à la distribution de Wigner-Ville (DWV) dont les propriétés permettent d’être plus réactive à ces présences de pics que les autres distributions de la classe de Cohen [4].
La DWV est définie comme la transformée de Fourier du signal représentant le profil de projection. Ce signal est donné par : x(t+τ/2) x*(t- τ/2) où τ exprime le retard et montre que la distribution est invariante aux translations temporelles et fréquentielles, ce qui peut tolérer le décalage du profil dans les fenêtres. La valeur de DWV est : Wx (t, ) x(t / 2) x (t / 2)e d (3) La DWV a quelques propriétés intéressantes par rapport aux autres distributions, comme la production de valeur réelle, facilitant son interprétation :
W x ( t , ) dtdv
x ( t )
2 dt
(4) Pour estimer l’angle d’inclinaison, on projette la fenêtre suivant de multiples angles [-75° ; +90°] avec un pas de +15° donnant à chaque fois un signal x(t). Ensuite, la DWV est appliquée à chaque x(t) pour déterminer l’intensité d’énergie. L’angle correspondant au profil de projection ayant l’intensité d’énergie la plus élevée est choisi comme angle d’orientation (voir Figure 4, l’angle exact est +15° qui correspond au profil de projection qui a les pics les plus aigus et les vallées le plus creusées). Figure 7.b montre la première estimation de l’orientation pour le document dans la Figure 1.a.
Correction et extension de l’orientation
Deux cas peuvent arriver après l’estimation de l’orientation. Le premier cas arrive lorsque l’orientation au sein d’une fenêtre n’est pas franche, alors la fenêtre est découpée suivant la vallée de projection la plus profonde. Ensuite, chaque orientation de la fenêtre est revue en fonction de l’orientation des fenêtres voisines, prises suivant les règles d’écriture de l’Arabe : Est-Ouest, Est-NordOuest, Est-SudOuest, Sud-Nord et Nord- Sud. Soit, l’orientation est confirmée et étendue aux deux fenêtres, soit gardée identique dans chaque fenêtre. Cette opération est suivie d’une étape de correction du fenêtrage qui consiste à décaler les limites de fenêtres suivant l’orientation principale, de manière à ne pas intercepter les lignes d’écriture (voir Figure 7.b).
Extraction de lignes
En nous basant sur l’orientation dans les fenêtres, nous recalculons la projection par rapport à cette orientation, puis on procède à la recherche de nouveaux maxima (voir Figure 5.a). Chaque maxima représente le point de départ d’une ligne Ps, à partir duquel nous suivons la ligne de base blj en respectant l’angle de l’orientation. Le suivi commence dans la première fenêtre dans le coin droite du document. Le point d’arrivé Pe de la ligne de base est calculé en utilisant, l'angle, la largeur et la longueur de chaque fenêtre (voir Figure 5.b). La ligne de base blj est calculée en se fondant sur les deux points (Ps, Pe) et sur l'orientation de la fenêtre. Pendant ce suivi, les composantes connexes qui appartiennent à une ligne de base sont recherchées pour former les lignes dans chaque fenêtre (voir Figure 5.c).
Une étape de correction de la détection suit cette étape pour attribuer les composantes connexes non détectées et les symboles diacritiques à la ligne appropriée (voir Figure 5.c et Figure 5.d). Une méthode de distance est utilisée pour résoudre ce problème. D'abord, la distance entre le centre de gravité de la composante non détectée ou symbole diacritique (Ci) et la ligne est calculée. Ci est attribué à la ligne lj si dci,lj< dci,lj+1 sinon à lj+1 (voir Figure 6).
Pour chaque zone, les lignes sont groupées pour former les lignes de zone. Les relations entre les lignes de zones sont alors étudiées pour composer les lignes de document (voir Figure 7.c). Pour cela, nous regardons si une composante connexe appartient à deux lignes dans deux zones différentes. Si c'est le cas, nous fusionnons les deux lignes en une ligne.
Séparation de lignes connectées
La dernière étape de la méthode est relative à la séparation des lignes adjacentes. La connexion est relativement fréquente dans les documents manuscrits Arabe souvent favorisée par l’extension des lettres terminales de la ligne supérieure avec les hampes des lettres de la ligne inférieure (voir Figure 10.a).
Là encore, nous avons privilégié une technique prenant en compte la morphologie de l’écriture Arabe. Deux configurations de ligatures sont d’abord identifiées suivant l’orientation des boucles des lettres terminales
- boucle ouverte vers la gauche (cas du RA, WAW, NOUN, etc.) et boucle orientée vers la droite (cas du HA, KHA, AIN, etc.) (voir Figure 8). Chacune peut se ligaturer soit avec un allographe vertical (cas du ALEF, LEM, KEF, etc.), soit avec un allographe avec boucle (cas du TA, SA, HA, etc.). Nous cherchons à reconstituer les terminales en suivant les tracés ayant une continuité, i.e. la même variance angulaire.
La technique démarre des points d’intersection trouvés entre les lignes d’écriture adjacentes. L’analyse se concentre dans une fenêtre autour de chaque point (Sp). On suit ensuite le tracé à partir du point le plus haut de la fenêtre (Bp), et on le prolonge au-delà du point d’intersection avec le tracé qui a la même variance angulaire que lui. Dans le cas de la Figure 10, le tracé d’étiquette 1 se poursuit avec celui d’étiquette 3, correspondant à la lettre RA, puis le 2 va avec le 4 : cas du ALEF. La Figure 10.b montre les lignes séparées suivant des couleurs différentes (pour des détails [17]).
Résultats expérimentaux et discussion
Pour étudier l'efficacité de notre approche, nous l'avons testée sur 100 documents arabes manuscrits anciens qui contiennent 2500 lignes. Ce sont des manuscrits de la bibliothèque nationale de Tunisie [1], la bibliothèque nationale de médicine aux États-Unis [2] et la bibliothèque et archives de l'Égypte [3]. Les essais ont été préparés après un calcul
manuel de zones et de lignes de chaque document, l'angle de rotation examiné pendant ces expériences varie du -75° jusqu’au +90°. Le temps d'exécution est mesuré à partir du maillage jusqu'à la séparation de lignes. Il dépend de la taille du document et de la taille de la fenêtre du maillage. Les essais ont été effectués sur un PC équipé d'un microprocesseur Pentium M de 1.4 GHz et une mémoire cache de 1 GO sous Windows XP. L'application a été développée avec MATLAB R2009b. Dans la détection de zones multi-inclinées, nous avons obtenu un pourcentage de détection autour de 96%, qui passe à 98% si nous ne prenons pas en considération les petites zones non-détectées. Le taux d'erreur de 2% est dû au maillage et à la fausse inclinaison.
Dans le niveau de la segmentation en lignes, nous avons eu un taux d’extraction de 97.6%. Le 1.5% de lignes non détectées est dû au l'algorithme de la détection de zones. Le taux d'erreur de 0.9% est dû à la présence des symboles diacritiques dans le début de lignes qui créent des faux maxima. La Figure 11 illustre l’efficacité de notre algorithme sur un échantillon de 4 documents choisis arbitrairement parmi les 100 documents traités. Pour identifier les lignes, chaque paire consécutive de lignes sont présentées par deux couleurs différentes. Le Tableau 1 décrit les résultats de notre méthode.
Extraites Non- Extraites Erreur Zones 96 % 2 % 2 % Lignes 97.6 % 1.5 % 0.9 % Tableau 1: Résultats de notre méthode.
Conclusion et perspectives
Nous avons proposé dans cet article une approche originale, qui vise à extraire les lignes multi-orientées dans les documents arabes manuscrits anciens. Au début, les zones multi-inclinées sont détectées en utilisant un maillage automatique du document. Après, l’orientation est estimée, corrigée et étendue afin de trouver toutes les orientations locales en utilisant la distribution de Wigner-Ville sur l’histogramme de projection. Ensuite, les lignes sont extraites en se basant sur l'orientation et les lignes de base de chaque fenêtre. Enfin, les lignes adjacentes connectées sont séparées en utilisant des informations statistiques sur la morphologie des lettres terminales Arabes. Le taux d'extraction de 97.6% montre l'efficacité et la performance de notre approche. La prochaine étape dans notre travail sera la généralisation de l’approche pour d’autres scripts comme (Latin, Urdu etc.) et l’application sur des documents contient un mélange des textes et des images. Remerciements Nous tenons à remercier la Bibliothèque Nationale de Tunis,la Bibliothèque Nationale de médecine aux U.S.A, l’Archives et Bibliothèque Nationales d’Egypte qui ont bien voulu mettre à disposition du public leurs documents et qui ont constitués notre ressource essentielle de données.
Références bibliographiques
[1] ↑ < http://www.bibliotheque.nat.tn/ >
[2] ↑ < http://www.nlm.nih.gov/hmd/arabic/welcome.html >
[3] ↑ < http://portal.unesco.org/ci/photos/showgallery.php/cat/559. >
[4] ↑ L. Cohen. Generalized phase-space distribution functions. J. Math. Phys., 7(5):781-786, 1966.
[5] ↑ F. Yin, C. Liu. Handwritten text line segmentation by clustering with distance metric learning. In Proc. 11th ICFHR, pages 229-234, 2008.
[6] ↑ P. Flandrin. Time-Frequency/Time-Scale Analysis. Academic Press, San Diego, CA, 1999.
[7] ↑ P. Flandrin and W. Martin. A general class of estimators for the Wigner-Ville spectrum of nonstationary processes, a. bensoussan, j. l. eds. lions. systems Analysis and Optimization of Systems, Lecture Notes in Control and Information Sciences, 62:15-23, 1984.
[8] ↑ B. Gatos, A. Antonacopoulos, and N. Stamatopoulos. Handwriting segmentation contest. In ICDAR '07: Proceedings of the Ninth International Conference on Document Analysis and Recognition, pages 1284-1288, 2007.
[9] ↑ A. Hashizume, P. S. Yeh, and A. Rosenfeld. A method of detection the orientation of aligned components. Pattern Recognit. Lett., 4:125-132, 1986.
[10] ↑ F. Hlawatsch and G. F. Boudreaux-Bartels. Linear and quadratic time- frequency signal representation. IEEE Signal Process. Mag., 9(2) :21- 67, 1992.
[11] ↑ M. Kass, A. Witkin, and D. Terzopoulos. Snakes: Active contour models. Proc. 1st ICCV, pages 259-268, June 1987.
[12] ↑ L. Likforman-Sulem and C. Faure. Extracting lines on handwritten documents by perceptual grouping, in advances in handwiting and drawing: multidisciplinary approach. C. Faure, P. Keuss, G. Lorette, A. Winter (Eds), pages 21-38, 1994.
[13] ↑ L. Likforman-Sulem, A. Hanimyan, and C. Faure. A Hough based algorithm for extracting text lines in handwritten document. In Proc. of ICDAR'95, pages 774-777, 1995.
[14] ↑ L. Likforman-Sulem, A. Zahour, and B. Taconet. Text line segmentation of historical documents: a survey. 9(2) :123-138, 2007.
[15] ↑ U. Mahadevan and R. C. Nagabushnam. Gap metrics for word separation in handwritten lines. In ICDAR '95: Proceedings of the Third International Conference on Document Analysis and Recognition (Volume 1), page 124-127, 1995.
[16] ↑ G. Nagy, S. Seth, and M. Viswanathan. A prototype document image analysis system for technical journals. Computer, 25:10-22, 1992.
[17] ↑ N. Ouwayed and A. Belaïd. Separation of overlapping and touching lines within handwritten Arabic documents. In the 13th International Conference on Computer Analysis of Images and Patterns (CAIP'2009), to appear in September 2009.
[18] ↑ E. Oztop, A. Y. Mulayim, V. Atalay, and F. Y. Vural. Repulsive attractive network for baseline extraction on document images. Signal Processing, 75 :1-10, 1999.
[19] ↑ W. Postl. Detection of linear oblique structures and skew scan in digitized documents. In Proceedings of the Eighth International Conference on Pattern Recognition, IEEE CS Press, Los Alamitos, CA, pages 687-689, 1986.
[20] ↑ Y. Pu and Z. Shi. A natural learning algorithm based on hough transform for text lines extraction in handwritten document. pages 637- 646, 1998.
[21] ↑ Z. Shi and V. Govindaraju. Line separation for complex document images using fuzzy run length. In Int. Workshop on Document Image Analysis for Librairies, 2004.
[22] ↑ C. Xu and J. L. Prince. Gradient vector Flow: A new external force for snakes. Proc. IEEE Conf. on Comp. Vis. Patt. Recog. (CVPR), pages 66-71, June 1997.
[23] ↑ A. Zahour, L. Likforman-Sulem, W. Boussellaa, and B. Taconet. Text line segmentation of historical Arabic documents. In 9th Int. Conf. on Document Analysis and Recognition, pages 138-142, 2007[23]A. Zahour, L. Likforman-Sulem, W. Boussellaa, and B. Taconet. Text line segmentation of historical Arabic documents. In 9th Int. Conf. on Document Analysis and Recognition, pages 138-142, 2007.