David Picard
email: picard@ensea.fr

Philippe-Henri Gosselin
email: gosselin@ensea.fr

IMPROVING IMAGE SIMILARITY WITH VECTORS OF LOCALLY AGGREGATED TENSORS

Keywords: Image classification, Image representation, Bag of Words

Within the Content Based Image Retrieval (CBIR) framework, three main points can be highlighted: visual descriptors extraction, image signatures and their associated similarity measures, and machine learning based relevance functions. While the first and the last points have vastly improved in recent years, this paper addresses the second point. We propose a novel approach to compute vector representations extending state of the art methods in the field. Furthermore, our method can be viewed as a linearization of efficient well known kernel methods. The evaluation shows that our representation significantly improve state of the art results on the difficult VOC2007 database by a fair margin.

INTRODUCTION

In recent times, Content Based Image Retrieval (CBIR) benefited from significant advances in many of the fields it relies on. The first step is the introduction of powerful descriptors with high discriminative capacities like SIFT [START_REF] Lowe | Distinctive image features from scale-invariant keypoints[END_REF]. Either for similarity search or for image classification the local descriptors approach seems to be the most efficient for image matching. The second step is the introduction of efficient machine learning tools such as SVM with non-linear kernels [START_REF] Gosselin | Kernel on bags of fuzzy regions for fast object retrieval[END_REF]. Such techniques have great generalization capabilities that vastly improve results, and provide a unified framework for all image retrieval tasks.

In order to further improve the quality of the retrieval, recent work aims at filling the gap between descriptors and learning techniques. In this area, two steps can be investigated. The first consists in providing efficient image representation based on extracted descriptors. The main method for computing image representations is based on the "Bag of Features" scheme [START_REF] Sivic | Video Google: A text retrieval approach to object matching in videos[END_REF]. The latest works in this area show that results can be fairly improved by fine tuning image representations [START_REF] Lazebnik | Beyond bags of features: Spatial pyramid matching for recognizing natural scene categories[END_REF][START_REF] Wang | Locality-constrained linear coding for image classification[END_REF]. The second step tackles the problem of similarity measures between image representations. Most advanced methods improve the similarity measure by combining several representations obtained from different features. Such combined similarities can be learned along with the classifier and thus further improve the results [START_REF] Picard | An efficient system for combining complementary kernels in complex visual categorization tasks[END_REF].

In this paper, we propose a new scheme of signatures aggregating a set of descriptors extracted from the images. It sums tensor product of the descriptors which we show is a good approximation of insightful similarity measures between descriptors. We find our scheme to outperform state of the art signatures on well known images.

This paper is organized as follows: the next section describes recent related work on image representation and similarities. Section 3 introduces our novel approach and gives insight on its soundness. We then present successful experiments on the very difficult VOC2007 dataset, before we conclude.

IMAGE REPRESENTATION AND SIMILARITIES

All recent approaches in image retrieval and classification use a set of local descriptors to encode the information contained in the image, such as SIFT [START_REF] Lowe | Distinctive image features from scale-invariant keypoints[END_REF].

Providing two images I r and I s , represented by two sets of local descriptors B r = {b ri ∈ R N } i and B s = {b sj ∈ R N } j (N being the dimension of descriptor space), the difficult point is to provide a relevant similarity measure between the sets B r and B s . Moreover, this similarity must conform the Mercer conditions in order to be used within the powerful Kernel Machines framework.

There are two main families of methods to obtain such similarities. The first category keeps the bag of descriptors in its entirety and tries to conduct similarities on bags of vectors. The second approach aims at producing a single vector representation for each image by aggregating its descriptors, and then using well known vector similarities (i.e. linear, rbf, polynomial, etc).

The remaining of this section details both families of methods.

Kernels on bags

Given two bags of vectors B r = {b ri ∈ R N } i and B s = {b sj ∈ R N } j representing the sets of descriptors (of dimension N ) in two images, and a minor kernel function k on R N × R N , the simplest kernel one can build to measure the similarity between these bags is the sum kernel [START_REF] Gosselin | Kernel on bags for multi-object database retrieval[END_REF]:

K(B r , B s ) = i,j k(b ri , b sj ) (1)
However, this kernel tends to behave poorly when the cardinality of the bags increase. In fact, the sum of noisy values (corresponding to non matching pairs (b ri , b sj )) increases quadratically whereas the sum of relevant ones (i.e. matching pairs (b ri , b sj )) increases linearly with the size of the bags.

To handle the increasing noise in the sum, one can use a highly discriminative minor kernel, such as the Gaussian

kernel k(b ri , b sj ) = e -||b ri -b sj || 2 σ 2
, with a very small standard deviation. Several kernels on bags have been proposed to handle the noise introduced by non-matching pairs by removing them from the sum [START_REF] Gosselin | Kernel on bags of fuzzy regions for fast object retrieval[END_REF][START_REF] Gosselin | Kernel on bags for multi-object database retrieval[END_REF]. For instance, taking the average of maximum matching pairs is shown to have good performances in [START_REF] Gosselin | Kernel on bags for multi-object database retrieval[END_REF]:

K(B r , B s ) = 1 |B r | i max j k(b ri , b sj ) + 1 |B s | j max i k(b ri , b sj ) (2)
The main drawback of the kernel on bags methods is their high computational cost, which increase quadratically with the size of the bags. Recently, approaches have been introduced trying to reduce the overhead in computation [START_REF] Gorisse | Scalable active learning strategy for object category retrieval[END_REF].

Vector representations

To get rid of the computational cost of kernels on bags, one can pack the set of descriptors of each image into a single vector representation. The most famous method of this kind is the Bag of Features (BOF) approach [START_REF] Sivic | Video Google: A text retrieval approach to object matching in videos[END_REF]. Providing a visual codebook of k prototypes of descriptors (named "visual words"), the produced vectors can be seen as the histogram of visual words occurrences within the bag. Visual words are usually obtained by k-Means clustering. Practically, each descriptor in a bag is assigned to its closest visual word, and the corresponding bin in the signature is increased.

Novel approaches are proposed to better optimize the signatures [START_REF] Wang | Locality-constrained linear coding for image classification[END_REF]. They split the problem in two steps. Firstly, they compute an assignment of each descriptor of the image to each visual codeword. For each image, they thus obtain a set of vectors corresponding to a projection of each descriptor onto the codebook. This step is called the "coding" step.

Then, the set of assignment vectors is aggregated into a single vector of dimension k during what is named the "pooling" step. Taking the maximum value over the assignment values has been shown to be a relevant pooling step in [START_REF] Wang | Locality-constrained linear coding for image classification[END_REF].

In order to be efficient, the BOF approach requires a large codebook of several thousands visual words. However clustering high dimensional feature spaces (typically 128 dimensions for SIFT) into that many clusters is not an easy task. To tackle this problem, Jégou et al. proposed signatures named VLAD that use smaller codebooks [START_REF] Jegou | Aggregating local descriptors into a compact image representation[END_REF]. Given a small codebook of visual words {c n } n , they compute the vector υ n for each visual word c n , sum of difference vectors b ric n of all descriptors b ri for which c n is the closest visual word:

υ n = bri such that NN(bri)=cn b ri -c n ( 3
)
The signature is obtained by concatenating the υ n vectors. Hence, its dimension is k × N , where k is the size of the codebook, and N the dimension of the descriptors.

VLAD approach may be seen as a simplification of the Fisher vectors proposed in [START_REF] Perronnin | Improving the fisher kernel for large-scale image classification[END_REF]. In this method, a parametric generative model is estimated on the training set. The description vector is the sum of gradients of the descriptors likelihood with respect to the parameters of the model. It encodes the deviation in parameter space of the samples relatively to the model. Generally, a Gaussian Mixture Model (GMM) with diagonal variance matrices is used as model.

VLAT: VECTOR OF LOCALLY AGGREGATED TENSORS

We propose to expend the VLAD approach by adding an aggregation of the tensor product of descriptors.

As in VLAD, we first compute a visual codebook by clustering the descriptor space using k-Means. Let c n be the center (i.e. "visual word") of cluster n. For each visual word c n , we then compute a signature over the descriptors b ri of image I r that fall into cluster n. This signature is composed of several terms. The first term is the sum of differences between b ri and c n , like in VLAD:

T 1 n = bri such that NN(bri)=cn b ri -c n (4)
The second term is the sum of self tensor product of descriptors b ri centered to c n :

T 2 n = bri such that NN(bri)=cn (b ri -c n ) ⊗ (b ri -c n )(5) = bri such that NN(bri)=cn (b ri -c n )(b ri -c n ) ⊤ (6)
More generally, we could add further tensor terms to the signature by computing higher order p of tensor products on centered descriptors:

T p n = bri such that NN(bri)=cn ⊗ p (b ri -c n ) (7)
In practice, we limit the number of terms to the second order. The final image signature is the vector concatenating all the T p n flatten in vectors for all clusters n. A further ℓ 2 normalization of the signatures is done to ensure that images with different numbers of descriptors are still comparable.

Relation to kernels on bags

In order to prove the soundness of the VLAT approach, let us recall the sum kernel on bags for the Gaussian minor kernel:

K(B r , B s ) = i,j e -||b ri -b sj || 2 σ 2 (8)
If we assume that bag elements are normalized to unit ℓ 2norm, we can simplify the above expression as:

K(B r , B s ) = i,j e -2 σ 2 e 2<b ri ,b sj > σ 2 (9)
Let us now compute its Taylor expansion:

K(B r , B s ) = i,j ∞ p α p (< b ri , b sj >) p (10)
With α p being the coefficients of expansion. We now remark (< b ri , b sj >) p is the dot product between tensors of order p:

(< b ri , b sj >) p =< ⊗ p b ri , ⊗ p b sj > (11)
As the dot product is bilinear, we can further reduce the sum kernel a sum of dot product between n-order tensor of elements of the bags:

K(B r , B s ) = ∞ p α p < i ⊗ p b ri , j ⊗ p b sj > (12)
When limiting the order of expansion to a finite number P, the sum can be interpreted as a dot product in a space concatenating flatten tensors. Furthermore, the higher the order of the expansion, the better is the approximation of the Gaussian kernel. However, this comes at the expense of the dimension D of the signatures, which increases exponentially with the order of expansion:

D = P p=1 k × N p (13)
The main advantage of this approach is that it reduces a costly quadratic computation of exponentials to a simple dot product in a well chosen higher dimensional space obtained by non-linear mapping.

Using this interpretation, we can explain the underlying kernel on bags for the VLAT approach. It can be seen as the sum kernel on bags with the following minor kernel:

k(b ri , b sj ) =            P p=1 < ⊗ p (b ri -c), ⊗ p (b sj -c) > if NN(b ri ) = NN(b sj ) = c, 0 otherwise (14)
This kernel is a sum of dot products on tensors of centered vectors falling in the same cluster. We claim this kernel has two advantages: firstly, it reduces the noise of the sum kernel by removing pairs not falling in the same cluster. The higher the number of clusters, the less non matching pairs will be added to the sum. Secondly, the minor kernel measuring the similarity of a matching pair is non linear, and is indeed a good approximation of the Gaussian kernel.

EXPERIMENTS

We tested our method on the well known VOC2007 [START_REF] Everingham | The PASCAL Visual Object Classes Challenge 2007[END_REF] dataset. This challenge is known as one of the most difficult image classification tasks. It consists in about 10000 images and 20 different categories. Fig. 1 shows random images taken from this dataset highlighting the variety of categories. We extracted SIFT features on a dense grid with 3 different scales in order to obtain bags of about 15000 SIFT for each image (about 150 millions of descriptors for the whole dataset). All descriptors are reduced to only 32 dimension using Principal Component Analysis (PCA).

We compared our approach with VLAD and state of the art BOF approach like in [START_REF] Wang | Locality-constrained linear coding for image classification[END_REF]. The same set of descriptors were used for all methods. For the BOF approach, we generated a codebook of k =4000 visual words, which is known to have good performances. For the VLAD and VLAT approach, we had the parameter k varied from 16 to 64. All vector representations are normalized to unit ℓ 2 -norm. We used a standard SVM classifier with a triangular kernel, trained on the trainval set, and evaluated on the test set. The hyperparameter C of the SVM is set to 10, regardless of the category. No spatial pyramids ( [START_REF] Lazebnik | Beyond bags of features: Spatial pyramid matching for recognizing natural scene categories[END_REF]) were used for any of the methods, but all of them be improved with it. Tab. 1 sums up the mean Average Precision (mAP) for all methods. At first, we remark that the BOF approach is outperformed by VLAD, even with a much simpler codebook. This is consistent with recently reported results.

For same sized dictionaries, our method improve the results over VLAD by a fair margin of about 4% of mAP. On the category bicycle, the improvement is even as high as 9%. Furthermore, we find by comparing VLAD for k = 64 and VLAT for k = 16 that our method can lead to an improvement even with a smaller codebook, which highlight the soundness of the approach.

CONCLUSION

In this paper, we introduced a new vector image representation based on the aggregation of tensor products of local descriptors. Our representation can be seen as a generalization of state of the art representation methods, and outperforms them on the very difficult dataset VOC2007 by about 4%. When using more restrictive parameters such as a smaller codebook, our approach can still provide better results than state of the art with less restrictive parameters.

Moreover, we provide insightful clues showing that our method can be seen as an approximation of kernels on bags. This further explains the good performances of our signatures, and is encouraging to further developments.

Table 1 .

 1 Comparison of mAP between VLAD and VLAT for different size of dictionaries on VOC2007 dataset.

		BOF		VLAD		VLAT
	Category	4k	16	32	64	16 32 64
	aeroplane	65.3 60,2 61,0 62,0 64,6 65,9 66,1
	bicycle	44.5 35,3 38,6 40,3 45,3 47,2 49,2
	bird	38.7 33,7 34,6 35,1 38,1 39,6 39,5
	boat	49.4 53,7 55,8 55,3 57,4 59,5 58,7
	bottle	18.7 13,9 16,0 17,2 17,2 18,5 19,1
	bus	37.1 41,0 44,8 47,6 46,8 48,3 48,9
	car	63.3 65,8 68,3 69,2 70,5 71,1 71,0
	cat	33.9 35,2 37,9 40,9 40,8 41,1 43,1
	chair	39.0 38,2 40,2 40,4 41,3 43,1 42,8
	cow	24.8 22,7 22,7 25,3 25,2 26,9 27,3
	diningtable 22.3 23,3 25,9 28,3 25,7 30,4 30,4
	dog	26.9 34,1 32,4 34,0 36,6 37,0 37,3
	horse	58.4 65,8 65,2 66,7 70,7 70,6 70,8
	motorbike 36.2 45,2 47,2 49,2 49,6 51,1 51,3
	person	75.6 75,6 77,4 78,0 79,4 80,1 79,9
	pottedplant 11.9 11,9 14,4 17,0 14,9 15,8 16,7
	sheep	24.2 20,2 26,1 28,6 23,1 28,2 28,2
	sofa	33.9 34,3 36,2 35,0 39,4 39,7 38,9
	train	57.7 60,7 64,6 64,3 66,1 66,3 65,3
	tvmonitor	39.8 37,3 34,9 38,3 38,1 42,3 42,4
	all	40.1 40,4 42,2 43,6 44,5 46,1 46,4


V Eglin

D Gaceb

D Hani

S Bres

N Vincent

Outils d'analyse de la dynamique des écritures médiévales Pour l'aide à l'expertise paléographique

Keywords: Paleography, graph coloring, automatic analysis of manuscripts, text segmentation, features extraction, clustering. Auteur

Ce papier retrace les progrès de nos recherches en collaboration avec l'équipe de paléographe de l'Institut de Recherche en Histoire des Textes de Paris dans le cadre du projet ANR Graphem. Il s'agit d'un projet pluridisciplinaire visant à l'analyse informatisée des écritures médiévales. Notre objectif principal en tant qu'informaticiens est de développer des traitements informatiques pour assister les experts en paléographie dans le délicat travail d'étude et de déchiffrage des écritures anciennes. Nous présentons dans ce papier nos nouvelles méthodes d'analyse de contenu, de décomposition de l'écriture manuscrite en graphèmes, de construction d'une table de codage livrant la présence et la fréquence d'apparition des graphèmes de l'écriture. Les diverses techniques développées sont inspirées de méthodes empruntées à l'imagerie au sens large (dont l'imagerie médicale) et de modèles mathématiques avec la théorie des graphes (coloration de graphes) et l'optimisation combinatoire. La sélection d'approches très spécifiques à ces divers domaines s'est montrée particulièrement intéressante dans notre cas d'étude, en apportant d'une part une caractérisation fine et rapide basée sur le suivi de mouvement de la plume (courbure, épaisseur, direction, etc.)

et d'autre part une méthodologie d'analyse très performante pour la catégorisation des formes de base: les graphèmes. Les outils que nous avons produits ont pour ambition de permettre aux paléographes d'étudier rapidement et avec plus de précision un grand volume de manuscrits et d'extraire un nombre important de caractères spécifiques d'un individu ou d'une époque. Nous indiquerons à ce titre en quoi les retours des paléographes sur nos résultats sont indispensables pour évaluer nos algorithmes et produire les paramétrages les plus adéquats.

ABSTRACT. This paper recount the progress of our research in collaboration with SHS in the Graphem ANR project . This multidisciplinary project aims to the computerized analysis of medieval manuscripts. Our main objective as computer scientists is to develop computer processing methods to help experts in paleography in the delicate task of study and MOTS-CLÉS : paléographie, coloration de graphes, analyse d'image, segmentation des textes manuscrits, extraction de caractéristiques, clustering.

deciphering of ancient manuscripts. We present in this paper our new methods of content analysis, decomposition of the handwriting in graphemes and the construction of a code book. The various developed techniques are inspired by methods from imaging in a board sense (including medical imaging) with graph theory (graph coloring) and combinatorial optimization. The selection of very specific approaches from these areas has been particularly interesting in our case study, providing firstly a rapid and detailed characterization based on tracking the pen movement (curvature, thickness, direction, etc..) and secondly a highperformance methodical analysis for the categorization of basic shapes: the graphemes. The tools that we have produced enable the paleographers to study quickly and more accurately a large number of manuscripts and to extract an important number of features that are specific to an individual or era. We will indicate in this context how important the feedback from paleographers are to evaluate our algorithms and produce the most appropriate settings.

Outils d'analyse de la dynamique des écritures médiévales 3

Introduction

Cet article s'inscrit dans le cadre du projet ANR GRAPHEM. Il représente une contribution méthodologique applicable à l'analyse automatique des écritures manuscrites anciennes pour assister les experts en paléographie dans le délicat travail d'étude et de déchiffrage de ces écritures. Nous nous sommes intéressés en particulier aux anciens manuscrits latins du Moyen Âge qui précèdent la période de la Renaissance, avant l'émergence de l'imprimerie. La production de l'écrit au Moyen Âge présente la particularité d'avoir des procédures raisonnées de fabrication et de contrôle de qualité nécessitant de chercher les indices les plus subtils présents dans les manuscrits, et de faire «parler» des signes souvent visuels présents dans les formes et les mots. En ce sens, il faut bien comprendre la production de l'écrit du Moyen Âge comme un art à la fois visuel et manuel basé sur la réplication d'un ensemble de signes, de formes et d'images. L'enquête paléographique et philologique révèle, à travers l'histoire de la production écrite, que les textes du Moyen Âge sont autant de formes ou de signes que de contenus relatant la culture ancienne. L'étude de l'évolution de l'écriture a conduit les paléographes à s'intéresser de près aux spécialisations des ateliers de copies et à comprendre les circuits des influences graphologiques qui sont aussi celles des idées et des savoirs.

Le projet GRAPHEM 2 s'inscrit dans ce contexte d'études savantes de l'évolution des écritures et va chercher à mettre au point des méthodes et des techniques qui 1 IRHT : Institut de recherche et d'histoire des textes 2 GRAPHEM : Projet ANR Masses de données et Connaissances, http://liris.cnrs.fr/graphem/ permettront d'aider les experts paléographes à retrouver et comprendre les origines souvent énigmatiques des manuscrits anciens. Dans ce travail, nous ne nous intéressons pas spécifiquement au sens dégagé des textes, mais à l'analyse des traits d'écriture qui sont perçus ici comme autant de marques permettant d'en définir la provenance, d'aider les experts à resituer le texte dans son contexte historique ou géographique et à en exploiter le contenu. L'analyse du texte et l'exploitation de son contenu portent ainsi sur l'analyse de l'écriture et de ses particularités morphologiques. La notion de graphème est donc centrale dans cet article. Elle est à mettre ici en relation directe avec l'idée d'une décomposition de l'écriture en petits fragments ou petites unités qui constituent l'écriture dans son ensemble et participent à l'impression générale qui s'en dégage.

Sur le million environ de manuscrits médiévaux conservés dans le monde, très peu sont à ce jour décrits avec la précision souhaitable, moins de 10 % dans les bibliothèques majeures. Un immense travail reste donc à réaliser pour éditer les textes en étudiant notamment les nombreuses sources inédites, de manière à mettre leur contenu à la disposition de la communauté scientifique. Une très grande partie de ces documents dédiés au Moyen Âge sont détenus et numérisés par l'Institut de Recherche et d'Histoire des Textes (IRHT), partenaire de ce projet. Plusieurs centaines de milliers de manuscrits médiévaux numérisés en mode image attendent d'être analysés pour pouvoir être accessibles sur Internet et mis à disposition des chercheurs du monde entier. Contrairement aux documents imprimés numérisés dont les contenus textuels peuvent être automatiquement reconnus par OCR (Optical Character Recognition), les documents médiévaux totalement manuscrits ou peints sont actuellement hors de portée des processus de traitements automatisés. Cette description des contenus des images est nécessaire pour le fonctionnement des moteurs de recherche sur Internet (Google, yahoo, Quaero…) et des bibliothèques numériques (Bibliothèque Nationale de France « Gallica », Bibliothèque Numérique Européenne « BNUE », Europea). Cependant, il existe un trop petit nombre d'experts face à une trop grande quantité de documents à analyser pour que le minutieux travail de description puisse être réalisé dans des délais raisonnables. Les outils informatiques sont alors nécessaires non seulement pour assister les historiens dans leur travail de recherche mais aussi pour augmenter l'efficacité et la précision de leurs méthodes de travail. Le développement de traitements informatisés destinés aux experts pour les assister dans leur travail de description des contenus ne peut se faire que sur la base d'une collaboration étroite entre les chercheurs en Sciences Humaines et Sociales (SHS) et les chercheurs en informatique (STIC).

Sur ce type de manuscrits, des particularités spécifiques aux documents anciens doivent être prises en compte, comme le vieillissement des supports et des encres, l'imprégnation irrégulière des encres, les plissements, déchirements, cassures et autres dégradations du papier. De plus, les règles d'exécution des écritures en paléographie sont très strictes : certaines lettres et combinaisons de lettres ne peuvent être produites que selon une unique dynamique d'exécution. Celle-ci est parfaitement maîtrisée par les paléographes qui connaissent très précisément les contraintes de formation des lettres et de construction des ductus. Il est donc nécessaire de tenir compte dans notre étude de toutes ces contraintes et ces particularités d'exécution des écritures. Les objectifs de cette étude sont multiples et interviennent à plusieurs niveaux d'analyse. Les principaux obstacles qu'il faut lever dans ce travail sont liés au manque crucial d'outils informatiques pour l'assistance du travail de description et l'analyse experte dans les disciplines des Sciences Humaines. Il s'agit dont pour nous de développer des traitements informatiques pour assister les experts SHS dans leur étude de ces manuscrits.

Concrètement il s'agit pour nous :

-de produire une décomposition de l'écriture en graphèmes cohérents, en évitant notamment de produire des graphèmes qui correspondraient à certains gestes de rebroussement (retour en arrière du mouvement de la plume), qui sont considérés comme des mouvements incompatibles avec la nature des plumes (le plus souvent des calames) et des supports (nature du papier) à ces époques.

-de produire une classification de l'ensemble des graphèmes produisant une table de codage (code book en anglais) des formes, considérée comme un dictionnaire des graphèmes triés par similarité. Cette classification est destinée à un usage paléographique : elle intègre la possibilité pour les experts en Sciences Humaines de modifier avec beaucoup de facilité les résultats de la classification par la saisie d'une seule valeur de seuil.

Il s'agit seulement pour les chercheurs en Sciences Humaines de remettre en cause leurs méthodes de travail et de rendre les expertises plus objectives qu'elles ne le sont actuellement. La collaboration avec les chercheurs en Informatique a notamment nécessité pour les chercheurs en SHS de décrire leurs méthodes actuelles de travail. Elle leur a permis de disposer de nouvelles méthodes plus adaptées aux traitements informatisés. Grâce à l'assistance de l'informatique, le passage d'une étude ponctuelle sur quelques ouvrages à une recherche sur une plus grande échelle va permettre aux chercheurs en SHS de réaliser de nouvelles découvertes.

Dans ce travail, nous démontrons la faisabilité d'un tel objectif sur une étude portant sur des échantillons d'écritures sélectionnés pour leurs particularités morphologiques et leurs différences visuelles.

Nous montrerons comment l'approche de l'analyse des écritures par décomposition en graphèmes est une étape indispensable à la reconnaissance des styles d'écriture des manuscrits. Afin d'argumenter la validité de nos contributions, Nous présenterons dans les sections suivantes les insuffisances des méthodes conventionnelles ainsi que les principes et modèles scientifiques qui soutiennent ces travaux. Nous détaillerons notamment le principe de la décomposition en graphèmes basée sur la détection de l'axe médian directement réalisée sur l'image en niveaux de gris puis la classification des graphèmes basée sur la coloration de graphes.

Décomposition des manuscrits en graphèmes

Les tentatives informatiques portant sur l'analyse des écritures du Moyen-Âge sont encore très rares. On peut à ce titre citer le système SPI «System for Paleographic Inspections» [START_REF] Aiolli | SPI : a System for Palaeographic Inspections[END_REF] qui constitue à ce jour la seule tentative de réalisation d'un système d'assistance automatique en paléographie On peut reprocher à ce système d'être impraticable sur des grandes bases d'images médiévales en Europe puisqu'il ne permet d'identifier deux écritures de la même famille paléographique si elles présentent de faibles variations dans le tracé des caractères et la qualité dans l'exécution de l'écriture. Il faut donc proposer de nouvelles approches moins sensibles à ces variations et capables de mesurer les formes d'écritures indépendamment du contenu des textes, de la qualité de l'exécution de l'écriture et du style personnel du scripteur.

En dehors des seuls travaux reconnus et publiés sur la discrimination des écritures médiévales, nous pouvons citer les plus nombreux travaux sur la caractérisation des écritures pour des applications différentes de celle de la paléographie. Toutes ces études sont naturellement liées à notre problématique mais ne sont pas toutes directement ré-exploitables pour l'étude paléographique puisqu'elles agissent sur des écritures contemporaines aux nôtres.

Les techniques vers lesquelles nous nous sommes tournées relèvent d'une approche structurelle portant sur les invariants et les singularités des écritures. Au sein de cette famille, on peut citer les travaux fondateurs de [START_REF] Kuckuck | Writer recognition by spectra analysis[END_REF] et de [START_REF] Said | Writer identification from non-uniformly skewed handwriting Images[END_REF] qui considèrent les propriétés visuelles et globales des textes comme autant d'indices sur lesquels repose l'analyse. D'autres travaux portant sur la définition de caractéristiques locales des styles d'écritures basées sur des calculs de gradients, de concavité et d'orientations ont été proposés par [START_REF] Tomai | Discriminatory power of Handwritten words for writer recognition[END_REF]. (Bulacu et Schomaker, 2003) s'intéresseront également à la directionnalité des formes et aux probabilités de distributions des contours orientés pour réaliser des outils robustes de discrimination de scripteurs.

Parmi les pionniers de l'analyse des orientations pour la classification des styles d'écritures, on peut citer les travaux de [START_REF] Crettez | A set of handwriting families: style recognition[END_REF] qui utilise la rose des directions des formes binaires pour identifier les formes différentes d'écritures en vue de leur reconnaissance.

Dans ce contexte, les analyses portant à la fois sur la considération de zones d'écritures étendues et sur celle de petits fragments d'écritures ont été nos principales sources d'inspiration, car elles rendent complémentaires deux approches, locales et globales. Notre contribution s'inscrit donc dans ce schéma de principe impliquant une décomposition des formes écrites en petits fragments. Pour cela, nous exploitons une approche originale de suivi de tracé, de détection de l'axe médian et de découpage du tracé en graphèmes. Cette décomposition est résumée par la suite sous la forme d'une signature statistique globale qui exprime la fréquence d'apparitions de ces graphèmes à partir d'un tri réalisé sur leur similarité morphologique.

Suivi du tracé et détection de l'axe médian

Afin de bien mesurer l'importance de la détection des informations de structure dans les images dans un domaine très particulier, la radiographie du squelette est indispensable pour réaliser certains diagnostics de l'allure du corps humain à partir d'une analyse structurelle plus simple et plus intuitive des formes. La notion de squelettisation fut introduite pour la première fois dans le domaine de la reconnaissance des formes par [START_REF] Blum | A transformation for extracting new descriptors of shape[END_REF]. La réduction d'un objet à ses éléments essentiels peut permettre l'élimination de contours dénaturés tout en gardant ses propriétés topologiques et géométriques. Les deux propriétés visées sont l'homotopie et la réversibilité. Le tracé manuscrit et son squelette ont le même nombre de composantes connexes et chacune des propriétés possède une forme comparable. Centré dans la forme de tracé, le squelette fournit une représentation équivalente au tracé et de plus unidimensionnelle. Le découpage de l'écriture en graphèmes peut se faire entièrement (et plus simplement) à travers celui du squelette qui possède la majorité de l'information synthétisée. L'extraction du squelette sur des documents anciens dégradés devient plus exigeante dans la mesure où les bruits du bord et les irrégularités de contour sont des paramètres nuisibles. Il existe actuellement une grande variété de méthodes de suivi et de détection de l'axe médian où le choix dépend de la nature des images. Dans la littérature, ces méthodes peuvent être regroupées en six catégories selon la technique utilisée :

-L'amincissement morphologique : l'amincissement consiste à retirer au fur et à mesure les points du contour de la forme, tout en préservant ses caractéristiques topologiques. Ces méthodes nécessitent une étape préalable de binarisation des images en niveaux de gris. Celle-ci conduit à une grande perte d'informations lorsque les documents sont anciens et de mauvaise qualité [START_REF] Lee | A new methodology for gray-scale character segmentation and recognition, Pattern Analysis and Machine Intelligence[END_REF][START_REF] Maio | Direct Gray-Scale Minutiae Detection in Fingerprints[END_REF]. Elle donne ainsi des traits binaires dégradés : caractères cassés, fusionnés ou biaisés (trous, bruit). Ces dégradations déforment souvent le squelette des traits et provoquent des erreurs significatives dans leur appariement [START_REF] Suh | Stroke extraction from gray-scale character image[END_REF].

-Le Diagramme de Voronoï : leur squelette d'une forme continue est inclus dans le diagramme de Voronoï des points de sa frontière [START_REF] Schmidt | Some ex. of algo. analysis in comput. geometry by means of math. morphology techniques[END_REF]. Cette approche est définie dans un espace continu et produit un squelette connecté. L'inconvénient de ce type de méthodes revient à la difficulté de l'échantillonnage des contours qui définissent la qualité du diagramme de Voronoï et le découpage des branches à l'aide d'étapes complexes de post-traitement [START_REF] Attali | Squelettes et graphes de Voronoi 2D et 3D[END_REF].

-La transformée de distance : la carte de distances d'un objet consiste à associer à chacun de ses points sa distance au point de contour le plus proche. Les maxima locaux de la carte de distance correspondent exactement aux points du squelette de l'objet. Plusieurs distances ont été utilisées dans ce cadre : Euclidienne [START_REF] Danielsson | Euclidean Distance Mapping[END_REF][START_REF] Choi | Extraction of the Euclidean skeleton based on a connectivity criterion[END_REF], Chamfer [START_REF] Rosenfeld | Distance Functions on Digital Pictures[END_REF], etc. appliquées le plus souvent sur des images binaires mais aussi sur des images en niveaux de gris. Avec ces méthodes, l'extraction de l'axe médian du tracé est fortement sensible aux déformations des contours de tracé qu'on rencontre souvent sur nos images.

-Des heuristiques : ces méthodes s'appliquent directement sur les images en niveaux de gris en utilisant des heuristiques pour régler des paramètres qui gèrent la détection de l'axe médian. Elles sont très utilisées pour l'extraction du squelette des traits sur des empreintes digitales et leurs résultats sont nettement plus robustes et efficaces sur des images dégradées que ceux de deux familles de méthodes précédentes [START_REF] Maio | Direct Gray-Scale Minutiae Detection in Fingerprints[END_REF][START_REF] Qi | Fingerprint Ridge Line Reconstruction[END_REF]. Nous pouvons également retrouver ces approches dans le domaine de l'imagerie médicale comme dans les travaux de [START_REF] Sun | Automated identification of arterial contours in coronay arteriograms by an adaptive tracking algorithm[END_REF] qui présente un algorithme géométrique de suivi du tracé sur les images de rayon-X. Cet algorithme est connu sous le nom de « Algorithme de Sun ». [START_REF] Aylward | Initialization, noise, singularities, and scale in height ridge traversal for tubular object centerline extraction[END_REF] ont adapté ce principe aux objets tubulaires (vaisseaux sanguins) sur des images 3D en niveau de gris. L'inconvénient principal de ces méthodes c'est l'absence de l'auto adaptation aux changements d'orientation, de diamètre et aux problèmes de chevauchement et de croisement de vaisseaux sanguins ou de traits sur des images dégradées.

-La détection des contours : ces méthodes utilisent les contours pour naviguer le long du trait et détecter l'axe médian par corrélation entre une ligne et ses deux bords. Dans ce cadre, une approche itérative intéressante est proposée dans [START_REF] Zhang | A novel tracing algorithm for high throughout imaging Screening of neuron-based assays[END_REF] pour détecter l'axe médian dans des images de neurones. D'autres méthodes, fondées sur le même principe, sont utilisées dans le suivi des routes sur des images satellitaires [START_REF] Peteri | Detection and extraction of road networks from high resolution satellite images[END_REF][START_REF] Poz | Automated extraction of road network from medium and high-resolution images[END_REF]. Ce type de méthodes ne peut pas être facilement appliqué sur des manuscrits dégradés où les contours de traits sont souvent déformés et discontinus. Dans ce cas, le suivi de contours risque de se perdre dans de petites chaines parasites.

-De nouvelles techniques ont vu le jour notamment avec les ondelettes (You et al., 2003), l'équation aux dérivées partielles (EDP) utilisant des champs de diffusion [START_REF] Grigorishin | Skeletonisation: An Electrostatic Field Based Approach[END_REF][START_REF] Chung | Segmentation-Free Skeletonization of Gray-Scale Images via PDE[END_REF][START_REF] Siddiqi | Hamilton-Jacobi skeletons[END_REF][START_REF] Yu | A Segmentation-Free Approach for Skeletonization of Gray-Scale Images via Anisotropic Vectore Diffusion[END_REF][START_REF] Pervouchine | Handwritten character skeletonisation for forensic document analysis[END_REF][START_REF] Cheriet | Amincissement-sans-segmentation et rehaussement des images de niveau de gris par un filtre de chocs utilisant des champs de diffusion, I-Revues[END_REF], et l'approche 3D [START_REF] Baja | 2D Grey-level Skeleton Computation: A Discret 3D Approach[END_REF]. Les deux dernières approches permettent de squelettiser des images en niveaux de gris en évitant toutes les limites liées à la squelettisation des images binaires. Ce type d'approches nécessite plusieurs itérations de lissage, mais il est plus robuste aux dégradations.

Notre méthode de détection de l'axe médian

Notre approche s'applique directement sur les images en niveaux de gris de manuscrits anciens. Elle combine les aspects de différentes catégories citées cidessus, offrant un suivi souple et une détection de l'axe médian du tracé plus précise et robuste aux dégradations. Pour cela, nous nous sommes inspirés de différentes méthodes de squelettisation des vaisseaux sanguins sur des images médicales [START_REF] Xu | An improved algorithm for vessel centerline tracking in coronary angiograms[END_REF][START_REF] Frangi | Multiscale Vessel Enhancement Filtering[END_REF]. Les vaisseaux sanguins ont des propriétés comparables à celles des traits noirs de l'écriture (voir la figure suivante) c'est la raison pour laquelle notre choix s'est porté sur ce type de méthodes. -la méthode de Frangi [START_REF] Frangi | Multiscale Vessel Enhancement Filtering[END_REF] (utilisée à l'origine pour détecter des vaisseaux sanguins de propriétés comparables à celles des traits noirs de l'écriture) est appliquée directement sur l'image initiale pour mettre en évidence le tracé par rapport au fond. Le résultat subit un lissage gaussien pour enlever les discontinuités, les trous, les bruits ou les déformations qui peuvent être présents sur le tracé.

-la transformée de distance de Chamfer est appliquée sur la carte de Frangi pour déterminer d'une manière automatique le rayon (distance par rapport au point contour le plus proche) de chaque point du tracé. Ceci nous libère de tous les inconvénients liés à l'utilisation d'un rayon avec une taille fixe dans la méthode de Xu et offre à notre méthode une meilleure adaptation au changement d'épaisseur de traits.

-le suivi de l'axe médian repose, d'une part, sur une squelettisation par diffusion [START_REF] Yu | A Segmentation-Free Approach for Skeletonization of Gray-Scale Images via Anisotropic Vectore Diffusion[END_REF]

Découpage de tracé en graphèmes

D'un point de vue méthodologique, la segmentation des traits en graphèmes cohérents est réalisée le long de l'axe médian de la façon suivante : entre chaque point de départ et d'arrêt, tous les points impliqués dans la formation d'un trait sont sauvegardés dans une liste avec leurs directions et épaisseurs. Les points d'épaisseur minimale (minimum local) sont ensuite marqués et proposés comme point de découpage, comme cela est effectivement le cas dans la formation d'un trait. Chaque segment du tracé a une couleur différente. On identifie par cette approche les zones de croisements, les points de lever et de poser de plume. La décomposition présentée dans la figure 7 Afin de construire avec robustesse une table de codage pour chaque page manuscrite à partir de ces graphèmes découpés, nous nous sommes intéressés à une approche innovante de regroupement des graphèmes similaires utilisant le concept de coloration de graphes, jamais exploitée dans un tel contexte. Cette méthode n'exige pas la connaissance a priori du nombre de classes, ni un apprentissage préalable et permet d'offrir une bonne homogénéité intra-classes et une bonne disparité inter-classes. Elle s'adapte mieux à la nature des graphèmes réellement présents, à l'inverse des méthodes conventionnelles qui nécessitent l'introduction préalable du nombre de classes et l'étiquetage manuel des graphèmes durant l'apprentissage en introduisant des erreurs éventuelles à chaque niveau d'intervention de l'utilisateur. On peut citer, à titre d'exemple, la méthode de [START_REF] Zhu | Language Identification for Handwritten Document Images Using A Shape Codebook[END_REF] et la méthode de [START_REF] Kumar | Handwritten Arabic Text Zone Detection using A Shape Codebook[END_REF] qui sont basées sur les SVM et la méthode de [START_REF] Schomaker | using codebooks of fragmented connected-component contours in forensic and historic writer identification[END_REF] basée sur une carte de Kohonen.

Principe théorique de la coloration de graphes

La coloration de graphes constitue une branche très importante de la théorie des graphes. Ses applications sont nombreuses dans différents domaines scientifiques (optimisation des réseaux de transports ou de communication, des formules chimiques, etc.). Les définitions de la coloration sont simples et de véritables problèmes de recherche peuvent être posés sous une forme bien structurée dont la formulation peut recouvrir de grandes difficultés pratiques. Ce modèle a été introduit la première fois dans le domaine de documents par [START_REF] Gaceb | Improvement of postal mail sorting system[END_REF] qui l'ont adapté à toutes les étapes d'analyse des documents (de l'extraction de la structure physique à la reconnaissance) pour consolider la coopération et assouplir les échanges d'information entre les différents modules. Grâce à sa simplicité et son potentiel en matière de classification, nous avons pu imaginer une méthode originale

Types de colorations existantes

Il existe plusieurs types de colorations de graphe : la coloration de sommets à laquelle nous nous sommes intéressés, la coloration d'arêtes, la coloration par liste, etc. [START_REF] Gaceb | Improvement of postal mail sorting system[END_REF][START_REF] Paschos | Optimisation combinatoire : problèmes paradigmatiques et nouvelles problématiques[END_REF]. Une coloration de graphes G(V,E) est une fonction qui affecte une couleur à chaque sommet et qui est telle que deux sommets reliés par une arête (adjacents ou voisins ) n'ont pas la même couleur (contrainte de propreté). Les couleurs (ou entiers) attribuées aux sommets du graphe servent uniquement à regrouper les sommets en classes.

Modélisation du problème de classification de graphèmes en termes de coloration

Le regroupement d'un ensemble X={x 1 ,…,x n } de n graphèmes en plusieurs groupes homogènes se base sur un principe simple : chaque groupe doit réunir le plus de graphèmes similaires. Les regroupements portent sur un critère de similarité S. Les paires de graphèmes qui vérifient ce critère de similarité (distance ou dissimilarité inférieure à un seuil par exemple) seront regroupées. De même les paires de graphèmes {x i , x j } qui ne vérifient pas ce critère ne peuvent être fusionnées au sein d'un même groupe. Pour résoudre ce problème de partitionnement (ou de classification), il est possible de formuler la question suivante : quel est le plus petit nombre de groupes homogènes que l'on peut former en respectant la contrainte S. L'intérêt de formuler le problème de cette manière, est qu'il devient alors possible de le modéliser en termes de coloration de graphes. Le positionnement du problème est alors le suivant : nous représentons chaque graphème x i par un sommet v i ∈ V d'un graphe simple G et nous ajoutons une arête E(v i ,v j ) entre chaque paire de graphèmes dissemblables (qui ne respectent pas la contrainte S).

La coloration des sommets du graphe G(V,E) consiste alors à affecter à tous ses sommets une couleur de telle sorte que deux sommets adjacents (dissemblables) ne puissent pas porter la même couleur. Ces couleurs vont correspondre aux différents groupes homogènes qui constituent les différentes classes de graphèmes. Dans ce problème de regroupement, la question de la détermination du plus petit nombre de groupes homogènes, revient à rechercher le plus petit k pour lequel le graphe G correspondant admet une k-coloration : c'est donc précisément le nombre chromatique χ (G) du graphe G qu'il faut déterminer. De plus, cette modélisation présente l'avantage de gérer facilement plusieurs sortes d'ambiguïtés inhérentes à la forme des graphèmes par rapport aux mécanismes de regroupements classiques.

Figure 8. Etapes de construction d'une table de codage par coloration de graphes.

Construction de la table de codage

La première étape consiste à produire une description vectorielle de chacun des graphèmes, qui sera ensuite traitée pour définir les critères de similarité nécessaires à la classification. Nous avons utilisé, deux types caractéristiques : caractéristiques topologiques et les moments de Zernike.

Extraction des caractéristiques

La description de la forme des graphèmes est une étape importante pour la construction d'une table de codage. Si le graphème a une forme simple, a une silhouette compacte ou une frontière convexe, sa description peut être donnée en termes géométriques comme l'aire, le périmètre, la courbure, la direction, les moments, etc. Au départ, on produit une description vectorielle de chacun des graphèmes, qui sera ensuite traitée pour définir les critères de similarité nécessaire à la classification. Pour cela, deux descripteurs sont utilisés : un descripteur de 15 caractéristiques topologiques et un descripteur de 25 moments de Zernike.

Caractéristiques topologiques

Dix caractéristiques de forme ont été extraites à partir des graphèmes binaires. La longueur et la largeur du graphème sont utilisées pour différencier les styles d'écriture ainsi que la plume utilisée. L'orientation permet de connaître l'inclinaison du graphème et de différencier les différents mouvements d'exécution d'écriture. L'excentricité permet de savoir la forme globale du graphème. L'épaisseur permet de connaitre l'épaisseur de la plume et le style d'écriture. Par exemple dans les écritures gothiques l'épaisseur de la plume est grande ce qui n'est pas le cas des Couleurs = 3 classes de graphèmes écritures modernes utilisant des stylos fins. Les trois dernières caractéristiques sont reliées à la surface qu'un graphème occupe dans un manuscrit par rapport aux autres.

Cinq caractéristiques de courbure (directions de la plus grande et de la plus petite courbure, les courbures Gaussienne et moyenne et le Laplacien de la courbure) sont extraites à partir des graphèmes en niveau de gris et sont calculées à partir de la matrice Hessienne [START_REF] Qi | Fingerprint Ridge Line Reconstruction[END_REF]. Elles représentent la forme des courbes de graphèmes et reflètent les propriétés structurelles, telles que la convexité et la concavité. Leur rôle est important car elles sont des indicateurs essentiels permettant de différencier le style et l'époque de l'écriture. La combinaison des caractéristiques joue un rôle très important dans la construction de la table de codage et la classification des manuscrits.

La combinaison de plusieurs caractéristiques a aussi été adoptée dans d'autres travaux similaires pour augmenter la qualité des résultats. [START_REF] Bulacu | Combining multiple features for text-independent writer identification and verification[END_REF][START_REF] Xu | An improved algorithm for vessel centerline tracking in coronary angiograms[END_REF] ont combinés trois types de caractéristiques : la probabilité de densité (PDF) directionnelle jointe calculée sur les contours, la probabilité de la densité des graphèmes binaires et les Run-length PDFs. Les auteurs ont montré que chaque caractéristique isolée ne peut pas assurer une séparabilité suffisante pour la construction d'une table de codage représentative avec un classifieur de type KPPV« Leave one out». Les tests sur des manuscrits médiévaux montrent que cette combinaison donne des résultats nettement meilleurs que ceux obtenus avec l'entropie, l'auto-corrélation et les ondelettes [START_REF] Brink | How much handwritten text is needed for text-independent writer verification and identification[END_REF]. Une autre formule d'alliance de caractéristiques a été proposée par [START_REF] Dalitz | Using the Gamera Framework for Building a Lute Tablature Recognition System[END_REF] ( )

1 ( , ) , n m n m x y n A f x y V ρ θ π + = ⋅ ∑ ∑ [1]
V nm (ρ,θ) est un ensemble de polynômes complexes dans l'espace à deux dimensions qui forme un ensemble orthogonal sur l'intérieur du cercle unité (x²+y²=1), avec :

( , ) im n m n m V R e θ ρ θ = [2]
où ρ est la longueur du vecteur d'origine au point de coordonnées (x , y). θ est l'angle entre le précédent vecteur et l'axe des abscisses. R n,m = R n,-m est un polynôme radial défini comme suit :

( ) ( ) ( ) ( ) 2 2 0 .! 1 ! -S ! ! 2 2 n m S n S n m S n S R n m n m S S ρ ρ - - = - = -  +   -  -         ∑ [3]
Pour calculer les moments de Zernike, le centre de chaque graphème binaire est pris comme origine du repère et les coordonnées des pixels de l'image sont transformées de manière à être dans le domaine du cercle unité. Comme nous l'avons signalé précédemment les moments de Zernike sont invariants seulement à la rotation. Pour les rendre invariants au changement d'échelle [START_REF] Teague | Image analysis via the general theory of moments[END_REF], il faut normaliser l'image binaire du graphème par le moment du premier ordre m 00 défini comme étant la surface du graphème. ( )

1 1 ( , ) Nc k k k i j k Ds g v v α α = = ∑ [4]
Nc est la longueur des vecteurs des caractéristiques. g k est la fonction de dissemblance qui compare les caractéristiques deux à deux.

Construction du graphe

La construction d'un graphe G à colorer à partir d'un ensemble X={x 1 ,…,x n } de n graphèmes (où chaque sommet v i correspond au vecteur descripteur de graphème x i ) est principalement basée sur le calcul de la matrice de distances MD s . Cette matrice traduit les dissimilarités Ds(x i , x j ) existant entre les paires de graphèmes (x i , x j ) données par la relation suivante : i≠j). Une fois v calculée, nous associons à X un graphe seuil supérieur G ≥S =(V=X, E ≥S ) en utilisant la relation suivante :

MDs[v i ,v j ]=Ds( x i , x j ) avec i∈ [1,n] et j∈ [1,n] | (
1 si ( , ) ( , ) 0 sinon i j i j S i j Ds x x Ds v v S E , ν ν ≥ = ≥    =     [5]
Pour ne pas confondre le terme adjacence (ou voisinage) avec le terme similarité, il faut noter que deux sommets sont adjacents s'ils ont une dissimilarité supérieure au seuil S. Le seuil S est également nommé seuil d'adjacence. Ce seuil peut être ajusté manuellement en s'aidant de l'expertise des paléographes par exemple ou automatiquement en maximisant la qualité de classification ψ donnée par [START_REF] Gaceb | Improvement of postal mail sorting system[END_REF] :

Classification des graphèmes

Une fois le graphe G construit à partir de l'ensemble des graphèmes, on applique l'algorithme de coloration de [START_REF] Gaceb | Improvement of postal mail sorting system[END_REF]. Les différentes couleurs résultantes représentent les classes de graphèmes.

Résultats et application

Nous présentons ici le résultat de l'application de notre méthode de décomposition en graphèmes sur 12 pages de textes manuscrites du Moyen-âge de différents types (voir figure 10). Un ensemble de 4863 graphèmes répartis de la façon suivante a été extrait des douze pages manuscrites : {p1=343, p2=583, p3=643, p4=248, p5=398, p6=528, p7=564, p8=316, p9=499, p10=193, p11=269, 12=279}. Cette décomposition a été soumise à la validation des experts paléographes et a obtenu leur approbation. La figure suivante montre un extrait de la table de codage construite à partir des graphèmes de la page p1 par coloration de graphes. Il est important de noter ici que les descripteurs topologiques ont permis de mettre en évidence la dynamique dans la formation du tracé : les graphèmes qui présentent ainsi les mêmes particularités de mouvement (arrondis droits ou gauches) de la plume sont regroupés dans une même classe. Une vérification complète réalisée par les experts paléographes permet de l'attester. Nous pouvont estimer à partir cette table que le style de la page p7 est le plus proche de celui de la page p1 puis de la page p5, et que le style de la page p2 est plus proche de celui de la page p10, et ainsi de suite. Compte tenu de l'évidence visuelle facile à obtenir en observant les images de la base, cette distance est un indicateur efficace de similarités entre écriture. Ces premiers tests sont actuellement complétés par des tests en vraie grandeur sur la base paléographiques de 10000 images au sein de laquelle des différences plus difficiles à relever devront être mises en évidence.

Conclusion

Dans cet article, nous présentons une contribution majeure au projet ANR Graphem portant sur la mise en place d'une approche locale de caractérisation et de découpage des écritures du Moyen Age. Le principe consiste en une décomposition de l'image de textes en motifs élémentaires (graphèmes) qui servent de base à la comparaison des écritures. Sans chercher à segmenter les caractères dans les mots, la recherche de graphèmes similaires permet de caractériser une écriture médiévale : les écritures gothiques cursives possèdent en effet des formes de graphèmes particulières très différentes d'une écriture gothique textualis, par exemple. De même, la fréquence d'apparition des graphèmes apporte une information importante sur la régularité de l'écriture et sa qualité d'exécution (currens, libraria, formata, prescissa, etc.). C'est pour cette raison que la constitution de l'écriture en table de codage est fondamentale pour parvenir à une caractérisation et un classement efficace. Contrairement aux approches globales procédant par une analyse de texture, notre proposition d'approche locale à partir de l'analyse des graphèmes et de leurs redondances, permet d'utiliser pleinement les informations morphologiques et les terminaisons des lettres que seule la recherche de l'axe médian que nous proposons permet de mettre en lumière. Nous avons présenté une nouvelle méthode de découpage de l'écriture manuscrite en graphèmes et la construction de tables de codage des écritures bien adaptées aux exigences de notre domaine et aux besoins des experts paléographes. Pour cela, nous avons exploité la coloration de graphes qui s'est avérée être un outil de regroupement des graphèmes en classes très

Figure 1 .

 1 Figure 1. Exemples de manuscrits anciens latins du Moyen Âge, IRHT 1 .

Figure 2 .

 2 Figure 2. Squelette de la lettre V.

Figure 3 .

 3 Figure 3. (a) Image de manuscrit ancien latin du Moyen Âge (Cursive Gothique de style Formata), (b) Image d'une rétine issue de l'imagerie médicale par rayon X (Base de donnée DRIVE). Notre méthode unifiée combine les différents concepts cités précédemment et elle se déroule de la façon suivante :

Figure 4 .

 4 Figure 4. Détection des points de départ sur les deux types d'images.

Figure 5 .

 5 Figure 5. (a) La distance Look-ahead d k entre les points P k et P k+1 , (b et c) Suivi du tracé et extraction de l'axe médian. La figure suivante montre le résultat de l'extraction de l'axe médian par notre méthode qui est nettement meilleur que celui obtenu par la méthode classique de Zhang. Nous remarquons que notre méthode a bien détecté l'axe médian, même dans les situations où l'encre était dégradée ou très claire.

Figure 6 .

 6 Figure 6. (a) Extraction de l'axe médian par notre méthode sans binarisation, (b) binarisation par la méthode de Sauvola et extraction de l'axe médian par la méthode de Zhang., (c) résultat de notre méthode sur un manuscrit dégradé (encre claire, bruit, trait effacé).

  (a) montre que les lettres sont constituées de fragments adjacents rattachés aux points d'épaisseur minimale supposés correspondre souvent à des points de poser et de lever de plume. Comme le montrent les courbes de la figure 7(b), la lettre « C » est découpée une seul fois alors que la lettre « O » est découpée deux fois.

Figure 7 .

 7 Figure 7. (a) Exemple de décomposition des traits en graphèmes par notre méthode, (b) Courbes des épaisseurs des points de l'axe médian des lettres « O » et « C», et points de découpage en graphèmes.

  'une table de codage représentative de la distribution des graphèmes de l'écriture et de leurs fréquences d'apparition.

Figure 9 .

 9 Figure 9. Invariance à la rotation des 25 moments de Zernike (n=8).

  Mesure de similaritéLa dissimilarité entre v i et v j est donnée par la distance généralisée de Minkowski d'ordre α (α = 2 : distance euclidienne).

Figure 10 .

 10 Figure 10. Extraits des 12 manuscrits.

Figure 11 .

 11 Figure 11. (a) Table de codage de la page p1 (13 classes de graphèmes, S=0.3), (b) graphèmes colorés superposés sur l'image originale, (c) occurrences d'une lettre.

  dp entre les 12 pages sont illustrées dans le tableau suivant : Distances entre les codes book de pages.

  Le tableau suivant fait le bilan de ces méthodes de squelettisation selon la technique utilisée, le domaine d'application et le type d'images.

		Méthode	Domaine d'application	Type d'images
	Sun et al., 1998	Heuristiques	Imagerie médicale	Niveaux de gris
	Aylward et al., 2002	Heuristiques	Objets tubulaires	Niveaux de gris
	Lorigo et al., 1999	Level sets	Objets tubulaires	Niveaux de gris
	Wilson et Nobel, 1999	Seuillage global	Objets non tubulaires	Binaire
	Bullitt et al., 2000	Heuristiques	Imagerie medicale	Niveaux de gris
	Attali, 1995	Diagramme de Voronoï	Objets tubulaires arbitraires	Binaire
	Grigorishin, 1998	Champs électrostatique	Reconnaissance de formes	Binaire
	Ahuja et chuang, 1997	Champs de diffusion	Reconnaissance de formes	Binaire
	Chung et Sapiro, 2000	Diffusion de vecteur, anisotropique	Letters et images médicales	Niveaux de gris
	Cheriet et Doré, 2006	EDP	Reconnaissance de l'écriture	Niveaux de gris
	Danielsson,1980	Transformée de distance	Reconnaissance de formes	Binaire
	Rosenfeld et Pfalz, 1968	Transformée de distance	Reconnaissance de formes	Binaire
	Kang et Kim 2004	Heuristiques	Reconnaissance des chiffres	Niveaux de gris
	Su et al., 2009	Amincissement et graphe	Analyse des manuscrits	Binaire
	Pervouchine et al., 2005	B-splines	Analyse des manuscrits	Niveaux de gris
	Choi et al., 2003	Distance euclidienne	Reconnaissance de formes	Binaire

Tableau 1. Bilan sur les méthodes de suivi du tracé : aspects méthodologiques, domaine d'application et type d'images traitées.

  pour chercher des mots ou des caractères similaires sur des images historiques de notes musicales. La méthode combine les moments de Zernike, les moments conventionnels et 64 densités calculées sur une grille 8×8. Dans le tableau suivant, nous avons résumé les différentes méthodes liées à la construction de la table de codage.Les 25 moments de Zernike utilisés pour décrire les graphèmes sont classés parmi les moments orthogonaux (géométrique, de Legendre, etc.) car ils possèdent la propriété d'invariance à la rotation.Le moment de Zernike d'ordre n avec la répétition m (n -|m| est paire et |m|<n) est définie par :

	Schomaker et al., 2003	PDF du contour	250 écrivains	KPPV
	Brink et al., 2008	Hinge, Fraglets, runW,Brush	501 écrivains	KPPV
	Tableau 2. Différentes méthodes de construction de la table de codage.
	4.1.2. Moments de Zernike
	Article	Caractéristiques	Base	Algorithme
	Bulacu et Schomake, 2006	PDF directionnelle jointe graphème, Run-length PDFs basé sur les contours, PDF du	900 écrivains	KPPV. Neyman-Pearson
	Schomaker et al., 2007	PDF de composantes connexes	250 écrivains	Distance de Hamming
	Bulacu et Schomaker, 2007	PDF de composantes connexes	700 écrivains	χ 2 Distance
				K-means, Kohonen
	Balacu et Schomaker, 2005	PDF de composantes connexes	465 écrivains	SOM 1D et 2D. KPPV, Distance χ 2

Table de

 de Pour reconnaitre le style des manuscrits chacune des 12 pages manuscrites p i est représentée par sa table de codage cb(p i ) de k i classes de graphèmes (k i nombre chromatique de la coloration de graphes) avec On peut donc estimer la similarité entre chaque paire de pages (p i ,p j ) par la distance dp suivante :

	codage de la page p1 (13 classes de graphèmes, S=0.3), (b)
	graphèmes colorés superposés sur l'image originale, (c) occurrences d'une lettre.
	contient n t graphèmes avec	t c	=	1 { ,..., } t t nt x x	1 ( ) { ,..., } i i i k cb p c c = .	. Chaque classe c t

(a) (b) (c)


H Daher
email: hani.daher@insa-lyon.fr

D Gaceb

V Eglin

S Bres

N Vincent

Décomposition des manuscrits anciens en graphèmes et construction des codes book basée sur la coloration de graphe

Keywords: Clustering, Coloration de graphe, Moments de Zernike, Segmentation des manuscrits anciens

Nous présentons dans cet article une nouvelle méthode d'analyse et de décomposition de l'écriture manuscrite en graphèmes pour la construction d'un code book. Les diverses techniques développées sont inspirées de méthodes empruntées à l'imagerie au sens large et de modèles mathématiques issus de la coloration de graphes. Nos approches apportent d'une part une caractérisation fine et rapide basée sur le suivi de mouvement de la plume (courbure, épaisseur, direction, etc.) et d'autre part une méthodologie d'analyse très performante pour la catégorisation des formes de base: les graphèmes. Les outils que nous avons produits permettent aux paléographes d'étudier rapidement et avec plus de précision un grand volume de manuscrits et d'extraire un nombre important de caractères spécifiques d'un individu, ou d'une époque.

Introduction

Cet article s'inscrit dans le cadre du projet ANR GRAPHEM.

Il représente une contribution méthodologique applicable à l'analyse automatique des écritures manuscrites anciennes pour assister les experts en paléographie dans le délicat travail d'étude et de déchiffrage de ces écritures. Nous nous sommes intéressés en particulier aux anciens manuscrits latins du Moyen Âge qui précède la période de la Renaissance, avant l'émergence de l'imprimerie. Sur ce type de manuscrits, on se trouve confronté à plusieurs contraintes à cause du vieillissement des supports et des encres : imprégnation irrégulière des encres, plissement, déchirement, cassures et autres dégradations du papier. De plus, les règles d'exécution des écritures en paléographie sont très strictes : certaines lettres et combinaison de lettres ne peuvent être produites que selon une unique dynamique d'exécution. Il est donc nécessaire de tenir compte dans notre étude de toutes ces contraintes et ces particularités d'exécution d'écritures. Notre objectif est :

-de produire une décomposition de l'écriture en graphèmes cohérents, en évitant notamment de produire des graphèmes qui correspondraient à certains gestes de rebroussement (retour en arrière du mouvement de la plume)

-de produire une classification robuste et modulable de l'ensemble de graphèmes obtenus sous la forme d'un code book (table de similarités de graphèmes). Nous montrerons comment ces éléments peuvent servir à la reconnaissance des styles d'écriture des manuscrits. Nous présenterons, dans les sections suivantes, les insuffisances des méthodes conventionnelles ainsi que le principe de nos approches originales conçues pour être plus adaptées aux conditions citées ci-dessus. Nos approches se basent sur :

-une décomposition en graphèmes qui est basée sur la détection de l'axe médian directement réalisée sur l'image en niveau de gris.

-une classification de graphèmes par coloration de graphe.

Décomposition des manuscrits en graphèmes

Cette décomposition se réalise en deux étapes :

-Suivi de tracé et détection de l'axe médian -Découpage du tracé en graphèmes

Suivi du tracé et détection de l'axe médian

Il existe actuellement une grande variété de méthodes de suivi et de détection de l'axe médian (ou squelette) de tracé. Dans la littérature, ces méthodes peuvent être regroupées selon quatre catégories basées sur (pour plus de détails voir [START_REF] Daher | A New approach for centerline extraction in handwritten strokes…[END_REF]) :

-L'amincissement morphologique : l'amincissement consiste à retirer au fur et à mesure les points du contour de la forme, tout en préservant ses caractéristiques topologiques. Ces méthodes nécessitant une étape préalable de binarisation des images en niveaux de gris. Celle-ci conduit à une grande perte d'informations lorsque les documents sont anciens (de mauvaise qualité) [START_REF] Lee | A new methodology for gray-scale character segmentation and recognition[END_REF][START_REF] Maio | Direct Gray-Scale Minutiae Detection in Fingerprints[END_REF] et donne des traits binaires dégradés : caractères cassés, fusionnés ou biaisés (trous, bruit). Ces dégradations déforment souvent le squelette des traits et provoquent des erreurs significatives dans l'appariement de traits [START_REF] Suh | Stroke extraction from gray-scale character image[END_REF]. Ces limites ont donné naissance à d'autres méthodes de squelettisation qui s'appliquent directement sur les images en niveaux de gris comme la méthode basée sur les champs de potentiels 2D [START_REF] Grigorishin | Skeletonisation: An Electrostatic Field Based Approach[END_REF]. Ce type d'approche nécessite de couteuses opérations de lissage, mais il est plus robuste aux dégradations des images. Comme exemples, nous pouvons citer :

-La transformée de distance : la carte de distances d'un objet consiste à associer à chacun de ses points sa distance au point de contour le plus proche. Les maxima locaux de la carte de distance correspondent exactement aux points du squelette de l'objet. Plusieurs distances ont été utilisées dans ce cadre (Euclidienne [START_REF] Danielsson | Euclidean Distance Mapping[END_REF], Chamfer [START_REF] Rosenfeld | Distance Functions on Digital Pictures[END_REF], etc.) appliquées le plus souvent sur des images binaires mais aussi sur des images en niveaux de gris.

-Des heuristiques : ces méthodes s'appliquent directement sur les images en niveaux de gris en utilisant des heuristiques pour régler un grand nombre de paramètres qui gèrent la détection de l'axe médian. Elles ont été développées à l'origine pour extraire le squelette des traits sur des empreintes digitales et leurs résultats sont nettement plus robustes et efficaces sur des images dégradées que ceux de deux familles de méthodes précédentes [START_REF] Maio | Direct Gray-Scale Minutiae Detection in Fingerprints[END_REF][START_REF] Qi | Fingerprint Ridge Line Reconstruction[END_REF].

-La détection des contours : Ces méthodes utilisent les contours pour naviguer le long du trait et détecter l'axe médian par corrélation entre une ligne et ses deux bords. Dans ce cadre, une approche itérative intéressante est proposée dans [START_REF] Zhang | A novel tracing algorithm for high throughout imaging Screening of neuron-based assays[END_REF] pour détecter l'axe médian dans des images de neurones. D'autres méthodes, fondées sur le même principe, sont utilisées dans le suivi des routes sur des images satellitaires [START_REF] Poz | Automated extraction of road network from medium and high-resolution images[END_REF][START_REF] Peteri | Detection and extraction of road networks from high resolution satellite images[END_REF]. Ce type de méthodes ne peut pas être facilement appliqué sur des manuscrits dégradés où les contours de traits sont souvent déformés et discontinus et le suivi de contours risque de se perdre dans des petites chaines parasites.

Notre méthode de détection de l'axe médian

Notre approche s'applique directement sur les images en niveaux de gris de manuscrits anciens. Elle s'adapte mieux aux dégradations des manuscrits comme la discontinuité des traits tout en préservant et reconstituant, dans la mesure de possible, la forme initiale des traits. Grâce à la grande diversité technique utilisée combinant les 3 premières catégories citées ci-dessus, notre méthode offre un suivi et une détection de l'axe médian plus précise. La combinaison des méthodes se déroule de la façon suivante :

-la méthode de Frangi [START_REF] Frangi | Multiscale Vessel Enhancement Filtering[END_REF] (utilisée à l'origine pour détecter des vaisseaux sanguins de propriétés comparables à celles des traits noirs de l'écriture) est appliquée directement sur l'image initiale pour mettre en évidence le tracé par rapport au fond. Le résultat subit un lissage gaussien pour enlever les discontinuités, les trous, les bruits ou les déformations qui peuvent être présents sur le tracé.

-la transformé de distance de Chamfer est appliquée sur la carte de -Mise à jour de la direction dans On peut citer, à titre d'exemple, la méthode de Zhu [START_REF] Zhu | Language Identification for Handwritten Document Images Using A Shape Codebook[END_REF] et la méthode de Kumar [START_REF] Kumar | Handwritten Arabic Text Zone Detection using A Shape Codebook[END_REF] qui sont basées sur les SVM et la méthode de Schomaker [START_REF] Schomaker | using codebooks of fragmented connectedcomponent contours in forensic and historic writer identification[END_REF] basée sur la carte de Kohonen.

Figure 3 -Exemple de décomposition des traits en graphèmes par notre méthode.

Principe théorique de la coloration de graphes

La coloration de graphe constitue une branche très importante de la théorie de graphes. Ses applications sont nombreuses dans différents domaines scientifiques (optimisation des réseaux de transports ou de communication, des formules chimiques, …). Les définitions de la coloration sont simples et de véritables problèmes de recherche peuvent être posés sous une forme bien structurée dont la formulation peut recouvrir de grandes difficultés pratiques. Ce modèle a été introduit la première fois dans le domaine de documents par Gaceb et Eglin [START_REF] Gaceb | Improvement of postal mail sorting system[END_REF] qui l'ont adapté à toutes les étapes d'analyse des documents (de l'extraction de la structure physique et la localisation à la reconnaissance) pour consolider la coopération et assouplir les échanges d'information entre les différents modules. Grâce à sa simplicité et son potentiel en matière de classification, nous avons pu imaginer une méthode originale de construction de code book représentatif de la distribution des graphèmes de l'écriture et de leurs fréquences d'apparition.

Types de coloration existantes

Il existe ainsi plusieurs types de colorations de graphe : la coloration de sommets à laquelle nous nous sommes intéressés, la coloration d'arêtes, la coloration par liste, etc. [START_REF] Gaceb | Improvement of postal mail sorting system[END_REF][START_REF] Paschos | Optimisation combinatoire5: problèmes paradigmatiques et nouvelles problématiques[END_REF]. Une coloration de graphe G(V,E) est une fonction qui affecte une couleur à chaque sommet, et qui est telle que deux sommets reliés par une arête (adjacents ou voisins ) n'ont pas la même couleur (contrainte de propreté). Les couleurs (ou entiers) attribuées aux sommets du graphe servent uniquement à regrouper les sommets en classes.

Modalisation du problème de classification de graphèmes en termes de coloration

Le regroupement d'un ensemble X={x 1 ,.., x n } de n graphèmes en plusieurs groupes homogènes se base sur le principe que chaque groupe doit réunir le plus de graphèmes similaires. Les regroupements portent sur un critère de similarité S. Ce critère spécifie que certaines paires de graphèmes {x i , x j } ne peuvent être fusionnées au sein d'un même groupe. Pour résoudre ce problème de partitionnement (ou de classification), on peut partir du point de vue inverse et formuler la question suivante, à savoir : quel est le plus petit nombre de groupes homogènes que l'on peut former en respectant la contrainte S. L'intérêt de formuler le problème de cette manière, est qu'il devient alors possible de le modéliser en termes de coloration de graphe. Le positionnement du problème est alors le suivant : nous représentons chaque graphème xi par un sommet v i ∈ V d'un graphe simple G et nous ajoutons une arête E(v i ,v j ) entre chaque paire de graphèmes dissemblables ( qui ne respectent pas la contrainte S).

Construction du codes book

A partir de l'ensemble des graphèmes extraits dans l'étape précédente, nous procédons à la construction du code book de l'écriture (appelé aussi table de similarités).

Extraction des caractéristiques

Au départ, on produit une description vectorielle de chacun des graphèmes, qui sera ensuite traitée pour définir les critères de similarité nécessaire à la classification. Nous avons utilisé selon le besoin deux types de descripteurs : un descripteur de 15 caractéristiques topologiques et un descripteur de 25 moments de Zernike.

Caractéristiques topologiques

Dix caractéristiques de forme ont été extraites à partir des graphèmes binaires. La longueur et la largeur du graphème sont utilisées pour différencier les styles d'écriture ainsi que la plume utilisée. L'orientation permet de connaître l'inclinaison du graphème et de différencier les différents mouvements d'exécution d'écriture. L'excentricité permet de savoir la forme globale du graphème. L'épaisseur permet connaitre l'épaisseur de la plume et le style d'écriture. Par exemple dans les écritures gothiques l'épaisseur de la plume est grande ce qui n'est pas le cas des écritures modernes utilisant des stylos fins. Les trois dernières caractéristiques sont reliées à la surface qu'un graphème occupe dans un manuscrit par rapport aux autres. Cinq caractéristiques de courbure (directions de la plus grande et de la plus petite courbure, les courbures Gaussienne et moyenne et le Laplacien de la courbure) sont extraites à partir des graphèmes en niveau de gris et sont calculées à partir de la matrice Hessienne [START_REF] Qi | Fingerprint Ridge Line Reconstruction[END_REF]. Elles représentent la forme des courbes de graphèmes et reflète les propriétés structurelles telles que la convexité et concavité. Leur rôle est important, car elles sont des indicateurs essentiels permettant de différencier le style et l'époque de l'écriture.

Moments de Zernike

Les 25 moments de Zernike utilisés pour décrire les graphèmes sont classés parmi les moments orthogonaux (géométrique, de Legendre, etc.) car ils possèdent la propriété d'invariance à la rotation.

Le moment de Zernike d'ordre n avec la répétition m (n -|m| est paire et |m|<n) est définie par : V nm (ρ,θ) est un ensemble de polynômes complexes dans l'espace à deux dimensions qui forme un ensemble orthogonal sur l'intérieur du cercle unité (x²+y²=1), avec :

( ) ∑ ∑ ⋅ + = x y nm nm V y x f n A θ ρ π , ) , ( 1
( , ) im n m n m V R e θ ρ θ =
Où ρ est la longueur du vecteur d'origine au point de coordonnées (x , y). θ est l'angle entre le vecteur ρ et l'axe des abscisses. R n,m = R n,-m est un polynôme radial défini comme suit :

( ) ( ) ( ) ( ) 2 2 0 .! 1 ! -S ! ! 2 2 n m S n S n m S n S R n m n m S S ρ ρ - - = - = -  +   -  -         ∑
Pour calculer les moments de Zernike, le centre de chaque graphème binaire est pris comme origine du repère et les coordonnées des pixels de l'image sont transformées de manière à être dans le domaine du cercle unité. Comme nous l'avons signalé précédemment les moments de Zernike sont invariants seulement à la Rotation. Pour les rendre invariants au changement d'échelle [START_REF] Teague | Image analysis via the general theory of moments[END_REF], on doit normaliser l'image binaire du graphème par le moment du premier ordre m 00 défini comme étant la surface du graphème.

Mesure de similarité

La dissimilarité entre v i et v j est donnée par la distance généralisée de Minkowski d'ordre α (α = 2 : distance euclidienne).

( )

1 1 ( , ) Nc k k k i j k Ds g v v α α = = ∑
Nc est la longueur des vecteurs des caractéristiques. g k est la fonction de dissemblance qui compare les caractéristiques deux à deux.

Construction du graphe

La construction d'un graphe G à colorer à partir d'un ensemble X={x 1 ,…,x n } de n graphèmes (où chaque sommet v i correspond au vecteur descripteur de graphème x i ) est principalement basée sur le calcul de la matrice de distances MD s . Cette matrice traduit les dissimilarités Ds(x i , x j ) existantes entre les paires de graphèmes (x i , x j ) données par la relation suivante : MDs[v i ,v j ]=Ds( x i , x j ) avec i∈ [1,n] et j∈ [1,n] | (i≠j). Une fois v calculée, nous associons à X un graphe seuil supérieur G ≥S =(V=X, E ≥S ) en utilisant la relation suivante :

1 si ( , ) ( , ) 0 sinon

i j i j S i j Ds x x Ds v v S E , ν ν ≥ = ≥    =    
Pour ne pas confondre le terme adjacence (ou voisinage) avec le terme similarité, il faut noter que deux sommets sont adjacents s'ils ont une dissimilarité supérieur au seuil S. Le seuil S est également nommé seuil d'adjacence. Ce seuil peut être ajusté manuellement à l'aide des paléographes ou automatiquement en maximisant la qualité de classification ψ donné par [START_REF] Gaceb | Improvement of postal mail sorting system[END_REF]:

a rg m a x ( ( )} O p tim a l i S S ψ =

Classification des graphèmes

Une fois le graphe G construit à partir de l'ensemble des graphèmes, on applique l'algorithme de coloration de Gaceb et Eglin [START_REF] Gaceb | Improvement of postal mail sorting system[END_REF]. Les différentes couleurs résultantes représentent les classes de graphèmes.

Résultats et application

Nous avons testé notre méthode de décomposition en graphèmes sur 12 pages de textes manuscrites du Moyenâge de différents types. Un ensemble des 4863 graphèmes répartis de la façon suivante a été extrait des douze pages manuscrites. : {p1=343, p2=583, p3=643, p4=248, p5=398, p6=528, p7=564, p8=316, p9=499, p10=193, p11=269, 12=279}. Cette décomposition a été soumise à la validation des experts paléographes et a obtenu leur approbation. La figure suivante montre un extrait de code book construit à partir des graphèmes de la page 12 par coloration de graphe (section 4). Il est important de noter ici que les descripteurs topologiques ont permis de mettre en évidence la dynamique dans la formation du tracé : les graphèmes qui représentent ainsi les mêmes particularités de mouvement (arrondis droits ou gauches) de la plume Pour reconnaitre le style des manuscrits : chacune des 12 pages manuscrites p i est représentée par son code book cb(p i ) de k i classes de graphèmes (k i nombre chromatique de la coloration de graphe) avec Tableau 1 -Distances entres les codes book de pages.

On peut estimer à partir cette table que le style de la page 7 et le plus proche de celui de la page 1, que celui de la page 2 est plus proche de celui de la page 10, et ainsi de suite. Compte tenu de l'évidence visuelle facile à obtenir en observant les images de la base, cette distance est un indicateur efficace de similarités entre écriture. Ces premiers tests sont actuellement complétés par des tests en vraie grandeur sur la base paléographiques de 10000 images au sein de laquelle des différences plus difficiles à relever devront être relevées.

Conclusion

Nous avons présenté dans cet article une nouvelle méthode de découpage de l'écriture manuscrite en graphèmes et une construction d'un code book robuste bien adaptés aux exigences de notre domaine et basée sur la coloration de graphes. En perspective de ce travail, nous envisageons de reconnaitre automatiquement les styles et l'époque des manuscrits de la base complète paléographique. Ce travail sera intégré prochainement dans un prototype expérimental à l'usage des experts paléographes du projet GRAPHEM.

  Frangi pour déterminer d'une manière automatique le rayon (distance par rapport au point contour le plus proche) de chaque point du tracé. Ceci nous libère de tous les inconvénients liés à l'utilisation d'un rayon avec une taille fixe dans la méthode de Xu et offre à notre méthode une meilleure adaptation au changement d'épaisseur de traits. -le suivi de l'axe médian repose, d'une part, sur une squelitisation par diffusion [21] de la carte de Frangi et d'autre par sur le principe de la méthode de Xu adapté à notre application. Nous avons amélioré la méthode de Xu, en utilisant à chaque point la combinaison de deux directions complémentaire. a) la direction géométrique pour assurer une certaine robustesse aux situations indésirables de bifurcations et de croisement. b) la direction dynamique basée sur l'intensité lumineuse pour garantir un suivi robuste au changement soudain d'orientation ou d'épaisseur le long des traits. Cette dernière utilise une fenêtre de taille dynamique pour chercher le point suivant qui va appartenir à l'axe médian. La taille de la fenêtre varie automatiquement selon que l'on se situe dans le cas d'une bifurcation, d'un croisement ou d'une ligne droite.

Figure 1 -

 1 Figure 1 -Suivi du tracé et extraction de l'axe médian Les étapes de notre méthode de suivi et de détection de l'axe médian sont résumées dans l'algorithme suivant : a) Initialisation -Détecter les points de départ la carte issue de la diffusion (un point est considéré comme point de départ si son intensité lumineuse est maximale par rapport à ses voisins), -Extraire le rayon de chaque point de départ, -Commencer à partir de premier point de départ rencontré, -Déterminer le point suivant 0 1 k P + en utilisant dk « Look ahead Distance »,

Figure 4 -

 4 Figure 4 -Etapes de construction de code book par coloration de graphe. La coloration des sommets du graphe G(V,E) consiste alors à affecter à tous ses sommets une couleur de telle sorte que deux sommets adjacents (dissemblables) ne puissent pas porter la même couleur. Ces couleurs vont correspondre aux différents groupes homogènes qui constituent les différentes classes de graphèmes. Dans ce problème de regroupement, la question de la détermination du plus petit nombre de groupes homogènes, revient à rechercher le plus petit k pour lequel le graphe G correspondant admet une k-coloration : c'est

Figure 5 -

 5 Figure 5 -Invariance à la rotation des 25 moments de Zernike (n=8).

Figure 6 -

 6 Figure 6 -Extraits des 12 manuscrits.

  une même classe. Une vérification complète produite par les experts paléographes permet de l'attester.

Figure 7 -

 7 Figure 7 -Extrait de code book de page p12.

  Chaque segment du tracé a une couleur différente. On identifie par cette approche les zones de croisements, les points de levers et de posers de plume (voir le zoom de la figure3). La décomposition présentée dans la figure suivante montre que les lettres sont constituées de fragments adjacents rattachés aux points d'épaisseur minimale supposée correspondre à des points de poser et de lever de plume. Afin de construire avec robustesse un code book pour chaque page manuscrite à partir de ces graphèmes découpés, nous nous sommes intéressés à une approche innovante de regroupement des graphèmes similaires utilisant le concept de coloration de graphes, jamais exploitée dans un tel contexte. Cette méthode n'exige pas la connaissance a priori du nombre de classes, ni un apprentissage préalable et permet d'offrir une bonne homogénéité intra-classes et une bonne disparité inter-classes. Elle s'adapte mieux à la nature des graphèmes réellement présents, à l'inverse des méthodes conventionnelles qui nécessitent l'introduction préalable du nombre de classes et l'étiquetage manuel des graphèmes durant l'apprentissage en introduisant des erreurs à plusieurs niveaux d'intervention de l'utilisateur.

			1 k + Ψ afin de déterminer le point 1
		suivant	1 k p + qui aura la valeur du rayon calculée avant, 1
	-	Procéder de la même façon par calcul du profil de densité pour avoir le
		point Pk+1, point de convergence au centre du trait. Calculer sa direction
		Ψk+1,
	-	Marquer ce point comme un point visité, de cette façon il ne sera pas visité
		une autre fois par notre suivi de tracé.
	C) Critères d'arrêt
	-	Dans le cas où on rencontre un point de bifurcation et que ce point a déjà
		été visité, on arrête le suivi du tracé si on arrive à un point marqué comme
		point de départ, il sera enlevé de la liste des points de départ.
	-	-Réitération du processus le long du trait jusqu'à ce qu'un critère d'arrêt
		soit atteint.

La figure suivante montre le résultat de l'extraction de l'axe médian par notre méthode qui est nettement meilleur que celui obtenu par la méthode classique de Zhang. On remarque que notre méthode a bien détecté l'axe médian, même dans les situations où l'encre était dégradée ou très claire. Figure 2 -Extraction de l'axe médian par : (a) notre méthode, (b) la méthode de Zhang. (c) binarisation par la méthode de Sauvola 2.3 Découpage de tracé en graphèmes D'un point de vue méthodologique, la segmentation des traits en graphèmes cohérents est réalisée de la façon suivante : entre chaque point de départ et d'arrêt, tous les points impliqués dans la formation d'un trait sont sauvegardés dans une liste avec leurs directions et épaisseurs. Les points d'épaisseur minimale (minimum local) sont ensuite marqués et proposés comme point de découpage, comme cela est effectivement le cas dans la formation d'un trait.