Représentation des mots manuscrits par graphe pour la

recherche par similarité

Peng Wang, Véronique Eglin, Christine Largeron, Christophe Garcia, Josep Lladós,
Alicia Fornés
Dans Document numérique 2014/3 (Vol. 17), pages 53 à 75
Éditions Lavoisier
ISSN 1279-5127
ISBN 9782746247000
© Lavoisier | Téléchargé le 29/12/2023 sur www.cairn.info (IP: 196.117.40.229)

© Lavoisier | Téléchargé le 29/12/2023 sur www.cairn.info (IP: 196.117.40.229)

Article disponible en ligne à l’adresse

https://www.cairn.info/revue-document-numerique-2014-3-page-53.htm

Découvrir le sommaire de ce numéro, suivre la revue par email, s’abonner...

Flashez ce QR Code pour accéder à la page de ce numéro sur Cairn.info.

Distribution électronique Cairn.info pour Lavoisier.

La reproduction ou représentation de cet article, notamment par photocopie, n'est autorisée que dans les limites des conditions générales d'utilisation du site ou, le
cas échéant, des conditions générales de la licence souscrite par votre établissement. Toute autre reproduction ou représentation, en tout ou partie, sous quelque
forme et de quelque manière que ce soit, est interdite sauf accord préalable et écrit de l'éditeur, en dehors des cas prévus par la législation en vigueur en France. Il est
précisé que son stockage dans une base de données est également interdit.
 Représentation des mots manuscrits par
graphe pour la recherche par similarité

Peng Wang1, Véronique Eglin1, Christine Largeron2,

Christophe Garcia1, Josep Lladós3, Alicia Fornés3
1. Université de Lyon, LIRIS UMR5205, INSA-Lyon, France
{peng.wang, veronique.eglin, christophe.garcia}@liris.cnrs.fr
2. Université Jean Monnet, LAHC, CNRS UMR5516, Saint Etienne, France
[email protected]
3. Universitat Autònoma de Barcelona, Computer Vision Center, Espagne
{josep, afornes}@cvc.uab.es

RÉSUMÉ. Dans ce papier, nous proposons une nouvelle approche de la recherche de mots par
similarité reposant sur une structure de graphes intégrant des informations sur la topologie,
la morphologie locale des mots ainsi que des informations contextuelles du voisinage de
chaque point d’intérêt. Chaque mot est représenté par une séquence de graphes associés
chacun à un objet connexe. Un graphe est construit sur la base d’un squelette décrit par le
contexte de formes : descripteur riche et compact en chaque point sommet. Afin d’être
robuste aux distorsions de l’écriture et aux changements de scripteurs, l’appariement entre
mots repose sur une distance dynamique et un usage adapté du coût d’édition approximé
entre graphes. Les expérimentations sont réalisées sur la base de George Washington et la
base de registres de mariages de la cathédrale de Barcelone. L’analyse de performances
montre la pertinence de l’approche comparativement aux approches structurelles actuelles.
ABSTRACT. Effective information retrieval on handwritten document images has always been a
challenging task. In this paper, we propose a novel handwritten word-spotting approach
based on graph representation. The presented model comprises both topological and
morphological signatures of handwriting. Skeleton-based graphs with the Shape Context labeled
vertexes are established for connected components. Each word image is represented as a
sequence of graphs. In order to be robust to the handwriting variations, an exhaustive merging
© Lavoisier | Téléchargé le 29/12/2023 sur www.cairn.info (IP: 196.117.40.229)

© Lavoisier | Téléchargé le 29/12/2023 sur www.cairn.info (IP: 196.117.40.229)

process based on DTW alignment results introduced in the similarity measure between word
images. With respect to the computation complexity, an approximate graph edit distance
approach using bipartite matching is employed for graph matching. The experiments on the
George Washington dataset and the marriage records from the Barcelona Cathedral dataset
demonstrate that the proposed approach outperforms the state-of-the-art structural methods.
MOTS-CLES : recherche de mots par similarité, représentation par graphes, contexte de
formes, distance d’édition, DTW, fusion d’information, interrogation par l’exemple.
KEYWORDS: word-spotting, graph-based representation, shape context description, graph edit
distance, DTW, block merging, query by example.
DOI:10.3166/DN.17.3.53-75 © 2014 Lavoisier

Document numérique – n° 3/2014, 53-75

 54 DN. Volume 17 – n° 3/2014

1. Introduction

Les applications fondées sur l’exploitation des manuscrits reposent pour une
grande partie sur des versions numérisées. L’accès au contenu nécessite alors de
pouvoir considérer les textes à travers une représentation qui doit être concise,
discriminante et informante. Ce sont sur ces représentations que sont fondées les
techniques de recherche par le contenu (recherche par similarités de formes, word
retrieval, word-spotting…). De nombreux défis scientifiques sont ainsi associés à la
recherche par le contenu dans les images de traits. Autour de la recherche par
similarité de formes écrites, un élément central concerne l’étude de la variabilité
interne des écritures ainsi que celle qui permet de distinguer deux écritures de mains
différentes. Il est désormais communément admis que les techniques d’OCR sont
totalement inopérantes sur la plupart des textes écrits, en particulier sur les supports
anciens et historiques souvent très dégradés et présentant des particularités
graphiques associées à une grande diversité de styles d’écriture. Généralement on
associe le word-spotting à deux types d’approches : une première famille repose sur
la considération de mots prédéfinis en lien avec des mécanismes d’apprentissage
spécifiques dédiés à ces mots. On peut citer les travaux de Fischer et Rodriguez
(2010) et Rodriguez-Serrano et Perronnin (2009) par exemple reposant sur des
modèles de Markov cachés et des vocabulaires ad-hoc. À côté de ces approches, on
généralise les techniques de word-spotting par le développement de techniques de
représentation et de processus d’appariement flexible mettant les mots requêtes en
correspondance avec les cibles issues de l’image (voir (Rath et Manmatha, 2007) et
(Leydier et al, 2009)). Dans les deux cas, l’accès au contenu dans l’image nécessite
de disposer de représentations complètes assurant à la fois une bonne rigueur de
description et une souplesse nécessaire pour absorber les variations présentes dans
les pages d’écritures (Fischer et al., 2010 ; Rodriguez-Serrano et Perronnin, 2009 ;
Rath et Manmatha, 2007). Finalement c’est sur la mesure de similarité permettant de
déterminer les appariements acceptables qu’une attention particulière doit être
portée. Cette mesure doit offrir le maximum de robustesse aux déformations, aux
changements d’échelles, aux irrégularités dans la formation des traits ainsi qu’aux
dégradations qui entament généralement la description des contours et des
extrémités de formes.
COMPENSER L’ABSENCE D’APPRENTISSAGE PAR DES ADAPTATIONS AU CONTEXTE.
Nous avons été motivés dans ces travaux par la volonté de produire une description
© Lavoisier | Téléchargé le 29/12/2023 sur www.cairn.info (IP: 196.117.40.229)

© Lavoisier | Téléchargé le 29/12/2023 sur www.cairn.info (IP: 196.117.40.229)

complète de l’écriture reposant sur des dimensions complémentaires (les contours, le
squelette, et la notion de connexité vue comme une composition unitaire dans le
processus d’exécution du tracé) et la nécessité de définir des métriques souples pour
les comparaisons à partir d’approximations acceptables qui dans une certaine mesure
permettent de compenser l’absence d’apprentissage. En effet, compte tenu du fait
que l’on ne peut garantir l’existence de suffisamment de connaissances a priori
(fréquence d’un mot, variabilité interne d’une écriture, nature du bruit…), nous
avons choisi de résoudre les questions relatives à l’appariement de mots à partir
d’adaptations au contexte. Ces adaptations sont liées d’une part à la prise en compte
de l’environnement local dans lequel s’inscrit un point d’intérêt, un caractère ou un
mot (en adaptant notamment l’analyse à l’échelle de l’information considérée), et
 Modélisation par graphe de l’écriture 55

d’autre part à l’introduction d’approximations dans les calculs et d’optimisations

dans l’estimation des distances (DTW, coût d’édition approximé reposant sur des
structures de graphes).
UN CHOIX PORTE SUR LES REPRESENTATIONS STRUCTURELLES. Les
représentations structurelles des formes fondées sur les graphes sont populaires car
elles permettent de modéliser très finement les dimensions structurelles et
topologiques des objets. Dans certains domaines de l’imagerie graphique, comme en
reconnaissance de symboles et de formules chimiques, ces techniques ont un essor
considérable ces dernières années (voir Luqman et al ., 2011). Cependant, on
constate que les représentations graphiques demeurent très insuffisamment
exploitées dans le domaine de l’écrit ou bien souvent ce sont des mécanismes moins
rigides qui sont employés car ils assurent une meilleure tolérance aux variations
internes de l’écriture. On peut cependant citer quelques tentatives réalisées dans ce
domaine qui ont abouti à des premiers résultats prometteurs pour la reconnaissance
du chinois et des textes à la dimension structurelle particulièrement prégnante (voir
Lu et al., 1991 ; Zaslavsky et al., 2009). Bien que le modèle hiérarchique proposé
par Lu (Lu et al., 1991) reflète la nature complexe des caractères écrits chinois, les
mécanismes de représentation associés aux textes écrits sont généralement plus
sophistiqués pour permettre de distinguer des formes similaires. On peut citer ici les
travaux de Fischer (Fischer et al., 2010 ; 2013) qui a développé un modèle de
représentation graphique basé sur le squelette de l’image des mots à partir de
l’encodage des sommets. En ajoutant une quantité suffisante de points d’intersection
sélectionnés parmi les points d’intérêt de l’image, les informations structurelles
demeurent préservées et peuvent prévenir des nombreuses insuffisances liées à
l’usage exclusif d’une représentation reposant sur un squelette potentiellement bruité
ou incomplet. Le risque alors est de disposer d’un trop grand nombre de sommets et
de complexifier les calculs car l’usage des graphes peut engendrer une complexité
calculatoire exponentielle. En effet, le coût des correspondances entre formes
graphiques, les transformations des représentations graphiques en leur équivalent
vectoriel (vecteurs de caractéristiques) rappellent ces considérations calculatoires
importantes (voir Chherawala et al., 2011). Ces derniers auteurs présentent la
construction d’un graphe direct acyclique pour chaque sous-mot présent dans le
texte, converti ensuite en un vecteur exprimant la signature topologique des mots.
Lladós et al., (2012) ont adapté le concept de sérialisation de graphes pour des
applications d’appariements de graphes appliqués au word-spotting. En extrayant et
© Lavoisier | Téléchargé le 29/12/2023 sur www.cairn.info (IP: 196.117.40.229)

© Lavoisier | Téléchargé le 29/12/2023 sur www.cairn.info (IP: 196.117.40.229)

en classifiant les chemins acycliques du graphe en une représentation
unidimensionnelle, les auteurs ont pu créer un mécanisme de description des mots
fondé sur des « sacs de chemins » (Bag of Paths, BoP). Les applications de word-
spotting où les irrégularités et les imprécisions sont omniprésentes conduisent à des
résultats faibles.
Notre motivation à exploiter une représentation structurelle à partir des graphes
(plutôt que de modèles d’apparence, comme ceux récemment associés à une
description en points d’intérêt ou à des indicateurs de formes, comme les
histogrammes de projection de points de contours, de courbures ou d’orientations)
est liée à la stabilité structurelle des mots. Il existe en effet des règles d’exécution
 56 DN. Volume 17 – n° 3/2014

reproductibles que les points de jonction, de bifurcation et les points extrêmaux dans
les traits d’écriture permettent d’encoder (voir Daher et al., 2010). Les
caractéristiques topologiques des traits et la nature bidimensionnelle de l’écriture
nous semblent constituer des indications suffisantes pour écarter les descriptions
unidimensionnelles produites par des valeurs scalaires uniquement (Chherawala et
al., 2011). Par ailleurs, la polyvalence de la représentation recherchée nous a
conduits à considérer l’information dans son contexte selon un niveau d’échelle
modulable (l’échelle retenue ici est la connexité). Pour le contexte d’abord, nous
avons choisi d’exploiter une description fondée sur le Contexte de formes noté SC
pour Shape Context décrit dans Puzicha et Belongie (2002), estimé à partir de points
cibles extraits des formes. Nous l’appliquerons dans notre proposition à des données
de contours. Cette description pourra s’étendre à des données non segmentées
directement capturées de l’image en niveaux de gris ou en couleurs, ou encore sur
les squelettes des mots. Pour l’échelle d’analyse, nous avons retenu l’objet connexe,
car il est très informant dans l’écriture et permet de centrer l’analyse sur des entités
lexicales liées à une exécution continue typique du scripteur. L’entité de base
exploitée dans ces travaux peut également être considérée à d’autres échelles
d’analyse : le fragment (graphème) ou le mot (combinaison de fragments ou d’objets
connexes).
PRINCIPE GENERAL DE LA PROPOSITION. Nous proposons une approche générique
de word-spotting ne nécessitant pas de paramétrage lourd, n’ayant pas recours à
l’apprentissage et reposant sur une représentation des mots par graphe. La
description du graphe est fondée sur des primitives morphologiques obtenues par le
descripteur contextuel de Contexte de formes. Cette description est intégrée au
modèle de représentation pour indiquer localement en chaque sommet du graphe la
nature de son voisinage et les relations de proximité que les contours ont entre eux.
Ce descripteur est estimé sur la longueur totale d’un mot en tout point du graphe.
Chaque mot est finalement représenté par une séquence de graphes formés à partir
des connexités initialement repérés lors d’une étape de prétraitement. La
comparaison entre les mots image (requête et cibles) est finalement obtenue par le
calcul de la moyenne des distances d’édition entre graphes pair à pair. Au préalable,
une mesure dynamique (Dynamic Time Warping) est exploitée entre les graphes
Requête et Cibles comme processus de fusion de connexités garantissant les
meilleures correspondances et les meilleurs appariements de graphes. Une distance
d’édition approximée initialement définie dans (Riesen et Bunke, 2009) a été choisie
© Lavoisier | Téléchargé le 29/12/2023 sur www.cairn.info (IP: 196.117.40.229)

© Lavoisier | Téléchargé le 29/12/2023 sur www.cairn.info (IP: 196.117.40.229)

dans nos travaux afin de gagner en temps de calcul. Les performances de la
description comparées à d’autres approches sont étudiées pour des applications
d’interrogations par l’exemple.
La suite est organisée ainsi : après une brève introduction portant sur les étapes
de prétraitement pour l’obtention d’un squelette, de contours et de points structurels
exploitables, nous présentons formellement le concept de graphe pour la
représentation des formes écrites (section 3). Nous développons ensuite les
métriques retenues pour assurer une comparaison de graphes robuste aux variations
internes d’écriture : la comparaison des graphes requêtes et cibles par l’application
de la DTW permet de produire les meilleures configurations internes (fusion de
 Modélisation par graphe de l’écriture 57

graphes) qui sont ensuite évaluées par la distance d’édition approximée entre
graphes (section 4). Les résultats expérimentaux et l’analyse des performances
reposent sur la comparaison entre quatre approches de word-spotting du domaine et
notre proposition (section 5). Nous concluons enfin sur de possibles améliorations
pour des applications de word-spotting sans segmentation.

2. Prétraitements

Afin de produire un système comparable à l’existant, nous sommes partis de l’a

priori de l’existence d’une segmentation en mots. Nous disposons donc pour ce
travail de mots Requêtes bien identifiés dans le benchmark de l’étude (et qui sera
détaillé en section 5) et de mots Cibles que nous avons extraits pour les besoins de
l’étude. En réalité, cette étape est purement artificielle car le mécanisme complet de
recherche de mots ne peut se passer d’une approche bas niveau de localisation de
régions d’intérêt. Cette contribution n’est pas présentée dans ce papier mais a fait
l’objet d’un travail spécifique de recherche de régions (mots) d’intérêt candidates,
(Wang et al, 2014). Cette recherche a permis de sélectionner avec la plus grande
probabilité une série de mots plus proches de la requête avant d’y appliquer la
recherche par similarité fondée sur les graphes que nous détaillons dans ce papier.

2.1. Formation des lignes

Les étapes de prétraitement dédiées à une analyse d’images de documents

anciens ont fait l’objet de nombreux travaux ces dernières années. L’accès à un
patrimoine marqué par le temps, par les usures et les dégradations a orienté les
recherches vers des mécanismes portant autant sur la restauration des images que sur
les mécanismes d’accès robustes aux contenus (impliquant notamment des méthodes
d’analyse sans segmentation). Nous ne présenterons ici les étapes de prétraitement
que dans ses grandes lignes. Le workflow responsable de l’extraction des connexités
et du squelette des mots débute par une segmentation en lignes.
Après l’application d’un filtre gaussien dont l’écart type est choisi en fonction de
la dimension du plus petit élément de contenu (le caractère), nous appliquons une
binarisation adaptative basée sur la méthode d’Otsu. Une étape de détection de
lignes est conduite à partir de projections horizontales dont les maxima locaux sont
© Lavoisier | Téléchargé le 29/12/2023 sur www.cairn.info (IP: 196.117.40.229)

© Lavoisier | Téléchargé le 29/12/2023 sur www.cairn.info (IP: 196.117.40.229)

obtenus à partir de la dérivée première calculée sur le résultat de la convolution de la
projection par une fonction gaussienne. Des hypothèses d’horizontalité fortes sont
requises dans cette étape, réduisant ainsi l’application de l’approche sur des textes
fortement inclinés. Une adaptation reposant sur une recherche de l’axe médian des
lignes à partir de la détection de pics de la fonction d’autocorrélation calculée selon
un déplacement vertical peut être exploitée ici pour rendre l’approche plus robuste
aux variations d’orientations locales des lignes, (voir Leydier et al., 2014). La
transformée de Hough est également une alternative très fréquemment utilisée pour
améliorer la détection des lignes déformées, (voir Malleron et al., 2009). Enfin une
adaptation de l’approche de Aida (Aida-Zade & Hasanov, 2009) a été exploitée afin
de repérer avec précision les lignes de bases hautes et basses.
 58 DN. Volume 17 – n° 3/2014

2.2. Principe d’une description fondée sur le squelette

Du point de vue de la description des formes, il est nécessaire de considérer des

informations complémentaires liant les données de contours aux données de
squelette, même s’il est possible de rencontrer des situations très particulières où les
indications fournies par le contour ne sont pas symétriquement décrites par les
informations issues du squelette. À ce jour peu d’études ont tenté d’exploiter
conjointement les informations de contours et de squelettes dans la représentation
des caractères ou des mots. Cette double vue nous a semblé indispensable pour
produire une description plus robuste et nous l’avons intégrée dans la représentation
complète que nous proposons des mots. Pour obtenir les informations topologiques
de l’écriture et un squelette unitaire constituant l’entrée du mécanisme de sélection
de points structurels, nous avons appliqué l’algorithme de squelettisation de Zhang
et Suen (1984). Cet algorithme possède une version parallélisable appliquable à des
images binaires (voir figure 1). Un grand nombre de méthodes de squelettisation
nécessite une étape de binarisation qui contribue à accentuer les défauts des traits
lorsque les irrégularités ou les ruptures sont évidentes. Des alternatives intéressantes
ont été proposées dès 2007 par Lebourgeois (2007) qui a choisi d’exploiter la
diffusion des champs de vecteurs pour extraire l’axe médian des caractères le long
des lignes où la divergence du champ potentiel s’annule. Des approches assez
similaires sur le principe ont également été proposées par Daher et al. (2010) afin
d’extraire l’axe médian directement à partir d’un suivi de points situés à
équidistance des bords en se servant des orientations du champ de vecteurs gradients
en tous points du tracé.
Compte tenu de la dégradation des traits particulièrement visible sur les images
de manuscrits anciens, nous avons choisi de compenser les discontinuités
irréversibles du squelette par une approche de reconstruction adaptée du vote
tensoriel introduit par Medioni et al. (2000) et qui a essentiellement été exploité en
imagerie médicale sur des traits dégradés, ou plus généralement pour la
reconstruction de perspectives sur des images de scènes. Le vote tensoriel repose sur
le principe du groupement perceptuel à partir de l’agencement local de points
caractérisés par une valeur locale du champ tensoriel estimé dans un voisinage. Le
tenseur est une matrice symétrique du second ordre permettant de renseigner sur la
nature d’un point de structure, d’un point de région courbe, d’un point de
discontinuités, ou d’un bruit. Afin de déterminer la nature de chaque point de
© Lavoisier | Téléchargé le 29/12/2023 sur www.cairn.info (IP: 196.117.40.229)

© Lavoisier | Téléchargé le 29/12/2023 sur www.cairn.info (IP: 196.117.40.229)

singularités (dans notre cas il s’agit de points extrémaux au niveau des ruptures de
traits), on s’intéresse à leur information de géométrie différentielle du premier ordre
qui peut être définie à partir d’un tenseur du second ordre. Le vote tensoriel consiste
alors en une accumulation locale de tenseurs locaux permettant de favoriser
localement l’orientation préférée du voisinage du vote et de permettre de rediriger
localement les structures. En permettant de combler les discontinuités locales, le
vote tensoriel garantit un rendu réaliste et plus conforme à la production du trait
d’origine impliquant notamment la conservation de la courbure, voir figure 1.
L’évaluation de l’application du vote tensoriel sur les points de discontinuités
locales sera réalisée dans la section 5 de l’article.
 Modélisation par graphe de l’écriture 59

(a) (b)

Figure 1. (a) Exemples de squelettes extraits par la méthode de Zhang et Suen

(1984) pour 3 instances d’un mot extrait de la collection George Washington
(b) Leur apparence après l’application du vote tensoriel sur le squelette initial

2.3. Points de structure

La représentation reposant sur le squelette permet de disposer d’une information

© Lavoisier | Téléchargé le 29/12/2023 sur www.cairn.info (IP: 196.117.40.229)

© Lavoisier | Téléchargé le 29/12/2023 sur www.cairn.info (IP: 196.117.40.229)

importante sur la morphologie de l’écriture. Celle-ci est caractérisée par la présence
de points de structure qui peuvent être classifiés en trois familles : des points de
forte courbure, des points de croisement, et des points extrémaux. Ces points sont
très génériques et totalement indépendants des types de langue et d’écriture
considérés. La méthode d’extraction et de classification des points est présentée dans
(Wang et al., 2013). La figure 2d illustre cette décomposition produisant une version
segmentée de l’écriture en lignes et courbes concaves ou convexes séparées par des
points d’accroche. Afin de caractériser les informations morphologiques des mots,
nous avons choisi d’utiliser le contour extérieur de l’écriture. Après une étape de
comblement des trous et des zones de discontinuités dans le tracé, le détecteur de
contour de Canny-Deriche est utilisé pour extraire des bords (voir Deriche, 1987).
 60 DN. Volume 17 – n° 3/2014

Une procédure de suivi de contour est ensuite appliquée pour assurer une extraction
continue sans rupture de tracé (voir figure 2b). La pertinence des points de structure
tels que nous les avons définis dans ce travail peut s’évaluer à partir de l’étude
comparative de différents détecteurs de points d’intérêt usuellement exploités pour
la localisation ou la reconnaissance de régions d’intérêt : points DoG (Difference of
Gaussian), points issus du Hessien.

(a) (b) (c) (d)

Figure 2. (a) mot manuscrit (b) son contour (c) son squelette (d) points structurels
(rouge: points extrémaux, vert: points de haute courbure, bleu: point de croisement)

Figure 3. Trois approches de détection de points saillants (en ligne) et visualisation

© Lavoisier | Téléchargé le 29/12/2023 sur www.cairn.info (IP: 196.117.40.229)

© Lavoisier | Téléchargé le 29/12/2023 sur www.cairn.info (IP: 196.117.40.229)

des résultats en fonction d’une dégradation par flou gaussien croissant.
Détecteur de points de structure (ligne 1), détecteur de point DoG (ligne 2)
et détecteur de points par matrice Hessienne (ligne 3)

La figure 3 illustre la stabilité des points DoG, des points issus du Hessien et des
points structurels en situation de bruit croissant (de gauche à droite). On observe
d’abord le fait que le nombre de points structurels est plus stable, et non
conditionnés par des seuils permettant d’en contrôler artificiellement la quantité. La
stabilité provient de l’existence de configurations stables de l’écriture repérables à
des niveaux d’échelles et de résolutions variables. Compte tenu du fait que les points
 Modélisation par graphe de l’écriture 61

DoG et Hessiens sont issus d’une analyse de l’amplitude du gradient local, leur
détection et leur stabilité sont liées à des critères de contrastes, et de résolution
locale. On peut ainsi constater sur la figure 3 qu’à mesure que l’image se dégrade,
les quantités des points DoG et Hessiens diminuent tandis que les points structurels
restent stables.
Une étude de la répétabilité des points a été menée. Elle a permis de conduire
aux résultats suivants en termes de stabilité globale lors de dégradations
progressives de l’image: (Points de structure) RStructurel = 80 %, (Points DoG)
RDoG = 65.71 % et (Points hessiens) RHessian = 72.73 %.

3. Modèle de graphe pour la représentation structurelle des mots

Les représentations reposant sur les modèles de graphes possèdent l’avantage de

préserver les propriétés topologiques et dispositionnelles des segments internes
présents dans l’écriture. Nous avons choisi de représenter les propriétés structurelles
de l’écriture en nous intéressant à son squelette qui contient à lui seul toutes les
indications morphologiques que nous souhaitons retenir. Les sommets du graphe
correspondent aux points structurels extraits par l’analyse des configurations locales
du squelette et des arêtes (voir figure 5). L’information morphologique contextuelle
de chaque sommet en relation avec son proche voisinage est décrite par le contexte
de formes (SC : Shape Context descriptor, (voir Puzicha et Belongie, 2002), qui
capture la distribution de contours du voisinage d’un point en un vecteur riche et
informant. Ce descripteur a été exploité dans des contextes similaires pour la
reconnaissance de formes graphiques (Do et al., 2013), voir figure 4. Chaque
descripteur calculé en point du contour est représenté par un histogramme log-
polaire de distribution des contours dans le voisinage polaire autour de ce point. À la
figure 5, on exploite 5 rayons concentriques et 12 secteurs angulaires pour produire
la description. Les correspondances sont ensuite estimées en utilisant un
appariement bipartite pondéré par la distance du χ 2 estimée entre histogramme, (voir
Puzicha et Belongie, 2002).
Considérons Cij = C(pi, qj) le coût d’appariement estimé entre deux points. Ce
coût s’exprime alors par la distance du χ 2 estimée sur les histogrammes normalisés
hi et hj de dimension K.
© Lavoisier | Téléchargé le 29/12/2023 sur www.cairn.info (IP: 196.117.40.229)

© Lavoisier | Téléchargé le 29/12/2023 sur www.cairn.info (IP: 196.117.40.229)

( ) ( )
≡ , = ∑ (1)
( ) ( )

Le descripteur de contexte de formes est associé ici à chaque sommet du graphe.

Les arêtes du graphe sont également décrites par la longueur des segments estimée à
partir du décompte de points du squelette entre deux sommets adjacents. Chaque
composante connexe génère ainsi un graphe propre. Un mot est donc constitué d’un
ensemble de graphes définis individuellement et à ce stade ne possédant aucune
connexion entre eux. La figure 5 illustre une représentation en séquence de graphes
du mot ”Savay” : les trois graphes sont réellement constitués des portions de mots
”S”, ”av” et ”ay”.
 62 DN. Volume 17 – n° 3/2014

Figure 4. Illustration du descripteur de Contexte de Formes (SC).

(a) et (b) images originales ; (c) et (d) points de contours ;
(e), (f) et (g) histogrammes SC estimés à partir des trois points notés ◊, ∆ et ○

Figure 5. Représentation en une séquence de trois graphes du mot « Savay »

La définition du graphe peut ainsi se présenter de la façon suivante :

© Lavoisier | Téléchargé le 29/12/2023 sur www.cairn.info (IP: 196.117.40.229)

© Lavoisier | Téléchargé le 29/12/2023 sur www.cairn.info (IP: 196.117.40.229)

Définition 1. (Graph) Un graphe est un 4-tuple 4 = ( , , $, + , où :
– V représente l’ensemble des sommets correspondant
correspondant aux points structurels
– ⊆ est l, ensemble des arêtes, correspondant aux segments entre
deux sommets adjacents
– $: → ' ()* la fonction qui associe à chaque sommet son vecteur de contexte
de formes (SC : 5 niveaux concentriques et 12 secteurs angulaires, soit 60
dimensions)
– +: → ', est la fonction qui associe à chaque arête du graphe sa longueur
estimée entre deux sommets.
 Modélisation par graphe de l’écriture 63

4. Appariements entre mots et mesures de similarité

Au-delà des métriques reposant sur une comparaison exhaustive des

composantes du graphe et interdisant toute distorsion ou souplesse dans l’alignement
des arêtes et des nœuds à comparer, nous avons choisi d’exploiter des mesures de
similarités non linéaires permettant :
– de comparer chaque paire de composantes connexes d’un mot à l’autre à l’aide
d’une distance d’édition approximée (définie en 4.1)
– d’estimer les similarités internes interprétées comme des critères de fusion,
simplifiant ainsi le modèle de représentation des mots cibles en diminuant leur
nombre de connexités (section 4.2)
– d’estimer la distance finale entre deux mots par le cumul des distances internes
L’approche structurelle sur laquelle nous fondons la comparaison de mots
souligne tout l’intérêt de la prise en compte de la structure des entités dans la
métrique de comparaison, complexifiant inévitablement la vision qui ramène le
problème à un espace mathématique où les objets sont comparables linéairement
selon un calcul de distance entre vecteurs de caractéristiques. L’idée de procéder à
une approche relevant de l’étude de l’alignement structurel entre deux graphes
revient donc à prendre en compte non seulement les correspondances entre sommets
mais aussi les ressemblances dans leurs connexions (arêtes).

4.1. Correspondance entre graphes et distance d’édition approximée

Puisque les composantes connexes sont représentées par des graphes, leur
comparaison se ramène à un problème de correspondance de graphes. Afin d’éviter
les débordements calculatoires vite atteints dans de telles situations, nous avons opté
pour l’exploitation d’une comparaison approximée entre graphes proposée
initialement par Riesen et Bunke (2009) reposant sur la recherche du coût d’édition
minimal entre deux graphes.
Définition 2. (Distance d’édition entre graphes) Soit g = (V , E , μ , v ) le
graphe associé à la représentation de l’image Requête et g = (V , E , μ , v ) le
graphe associé à l’image Cible. La distance d’édition entre les deux graphes g1 et g2
© Lavoisier | Téléchargé le 29/12/2023 sur www.cairn.info (IP: 196.117.40.229)

© Lavoisier | Téléchargé le 29/12/2023 sur www.cairn.info (IP: 196.117.40.229)

est définie par :
d(g , g ) = min(?@ ,…,?B)∈D(E@ ,E ) ∑GF c(eF ) (2)

où H(4 , 4 )représente l’ensemble des chemins d’édition possibles permettant la

transformation du graphe g1 en graphe g2. La fonctionI(( )représente le coût
cumulant les coûts intermédiaires nécessaires pour transformer le graphe g1 en g2.
Les opérations indépendantes de coût ( peuvent être: des opérations d’insertion, de
suppression ou de substitution de sommets et d’arêtes, voir figure 6.
 64 DN. Volume 17 – n° 3/2014

Figure 6. Exemple de chemin d’édition modélisant la transformation du graphe G1

en graphe G2 : (a) suppression d’une arête (b) substitution d’un sommet (c)
insertion d’un nœud (d) insertion d’une arête

Typiquement, la distance d’édition entre graphes est calculée avec une approche
de type recherche arborescente présentant une complexité calculatoire exponentielle.
L’algorithme de comparaison sous-optimal est basé sur la considération des graphes
internes à chaque connexité (une connexité étant, rappelons-le constituée de n
sommets et m arêtes). Les graphes internes sont donc ici définis comme un ensemble
centré en un sommet et décrit par sa structure adjacente locale. Par conséquent, la
distance d’édition entre deux graphes peut être reformulée comme la recherche d’un
chemin optimal entre sommets et leurs structures locales respectives. L’appariement
exact de deux graphes demeurant un problème très couteux malgré l’utilisation de la
programmation dynamique, nous avons choisi de le traiter comme un problème
d’affectation. Pour cela l’algorithme hongrois de Munkres (Hungarian matrix) a été
choisi pour résoudre ce problème de recherche d’optimal entre graphes minimisant
le coût lié aux transformations de sommets et d’arêtes des graphes en temps
polynomial. Ces différences sont importantes à considérer pour le traitement de
masses de données conséquentes, ce qui est notamment le cas pour les applications
d’exploration de collections manuscrites anciennes.
En entrée, l’algorithme d’optimisation prend la matrice totale de coût C suivante
(3).
© Lavoisier | Téléchargé le 29/12/2023 sur www.cairn.info (IP: 196.117.40.229)

© Lavoisier | Téléchargé le 29/12/2023 sur www.cairn.info (IP: 196.117.40.229)

(3)

où Ci,j représente le coût de substitution d’un nœud i de V1 en j de V2, Ci, ϵ

représente le coût de suppression d’un nœud i de V1, Cϵ,j le coût d’insertion d’un
 Modélisation par graphe de l’écriture 65

nœud j de V2. L’algorithme de Munkres détermine d’abord les coûts minimaux de

substitution assurant un coût total minimal, puis les coûts de suppression et enfin de
suppression de nœuds. Tous les sommets du graphe le plus petit sont substitués et
les sommets restants du graphe le plus grand sont soit supprimés (s’ils appartiennent
au premier graphe) soit insérés (s’ils appartiennent au second).
Afin d’estimer les coûts de substitution d’un sommet en un autre, deux
composantes ont été mesurées : le premier indice permet de comparer la description
locale reposant sur le contexte de formes entre deux sommets et le second repose sur
la comparaison de la structure locale entre deux graphes impliquant les longueurs de
segments séparant deux sommets, (voir équation 4). Nous avons testé les
performances de la distance d’édition entre graphes avec différentes valeurs de
pondérations de ces coûts intermédiaires : K = 0.2 et K = 0.8, K = 0.5 et K = 0.5,
K = 0.8 et K = 0.2. Constatant sur un grand jeu de tests que la description reposant
sur la description des sommets par le contexte de formes demeure plus discriminante
que l’information contenue dans la structure voisine de chaque sommet, nous avons
choisi de fixer les valeurs de poids à 0.8 pour K et 0.2 pour K . Les deux constantes
a et d ont été choisies expérimentalement.
Csubstitution = w1 CSC_cost + w2 Clocal_structure (4)
Cdeletion = d (5)
Cinsertion = a (6)

Compte tenu des intervalles de valeurs choisis pour exprimer les coûts de
substitution, les deux constantes restantes liées au coût d’insertion et de suppression
sont fixées à 0.5. LM représente le coût associé au descripteur de contexte de formes
des sommets défini à l’équation (1). Le coût de substitution s’exprime alors par la
somme pondérée entre le coût de contexte de formes LM et le coût
NOPQN_STUVPTVUW défini comme le coût de substitution lié aux valeurs de longueurs des
arêtes. Pour un sommet considéré, on estime le coût de substitution de la façon
suivante : 1 − (S OUT /(NO[\ , avec (S OUT la longueur du contour le plus court
rattachant le sommet considéré à un voisin direct et (NO[\ la longueur la plus
importante dans ce voisinage.
© Lavoisier | Téléchargé le 29/12/2023 sur www.cairn.info (IP: 196.117.40.229)

© Lavoisier | Téléchargé le 29/12/2023 sur www.cairn.info (IP: 196.117.40.229)

4.2. Appariement complet de mots

Puisque un mot est représenté par une séquence de graphes (représentant les
objets connexités), la distance dynamique DTW est la mesure la plus adaptée pour
permettre un appariement souple entre graphes en intégrant la distance d’édition
présentée en section 4.1. Un des éléments fondamentaux de cette distance est de
permettre d’intégrer une variation parfois importante de connexités entre deux mots
à comparer. En effet, on peut rapidement observer que les mots présents dans un
texte manuscrit sont marqués par la présence de ruptures en des points non réguliers
du texte, ceci se traduit par la présence d’objets connexes en nombre variable entre
l’image Requête et l’image Cible. Ces variations sont remarquables entre scripteurs
 66 DN. Volume 17 – n° 3/2014

mais également pour un même scripteur, voir figure 7. Cette figure présente un
exemple de deux instances d’un même mot écrit par la même main possédant
respectivement cinq et trois connexités. Cette particularité graphique va plus
généralement pouvoir se résoudre par la comparaison de n graphes (issus du mot
Requête) avec m graphes (issus du mot Cible).

(a) (b)

Figure 7. Exemple de deux instances du mot ”Otheos” composées d’un nombre

variable de connexités (Correspondances clandestines 18e siècle1)

Pour rendre la mesure de similarité robuste aux variations internes de

de connexités,
nous avons proposé de les reconsidérer en réduisant leur nombre par un processus de
fusion. Les graphes affectés à une même connexité à l’issue de l’appariement par
DTW sont proposés à la fusion et reconsidérés comme un unique graphe. Dans ce
cas, la séquence de graphes de la Requête et la séquence de l’image Cible peuvent
être transformées. A l’issue de ces opérations de fusion, la distance d’édition entre
graphes est à nouveau calculée, ce qui crée mécaniquement de nouvelles
correspondances. La distance moyenne obtenue à l’issue de ces nouvelles
évaluations internes entre graphes est la mesure finale retenue entre les deux mots.
cela un exemple reposant sur un mot de taille moyenne :
Considérons pour cela
Otheos représenté sur la figure 7. On considère_ 4Q , ⋯ , 4Qa la séquence de
graphes représentant le mot de la figure 7 (a) et b 4] , ⋯ , 4]^ représente le mot de la
figure 7 (b). A l’issue de l’étape d’alignement obtenue par la distance dynamique
DTW, les graphes 4Q et 4] sont appariés, et les graphes 4Q et 4Q^ associés au graphe
4] et les trois graphes 4Q^ , 4Qb , 4Qa au graphe 4]^ . Par conséquent, en respectant la
procédure de fusion, les graphes 4Q , 4Q^ , 4Qb et 4Qa sont rassemblés en un seul et
même graphe renommé pour l’exemple 4Q , , ayant en commun le graphe 4Q^
© Lavoisier | Téléchargé le 29/12/2023 sur www.cairn.info (IP: 196.117.40.229)

© Lavoisier | Téléchargé le 29/12/2023 sur www.cairn.info (IP: 196.117.40.229)

réagissant positivement à deux graphes communs du mot b. Les graphes 4] et
4]^ sont également fusionnés en un unique graphe 4] , , car tous deux sont
appariables à 4Q^ (résultat obtenu par la distance d’édition). Ainsi les deux
représentations des images (a) et (b) peuvent être reformulées comme deux
nouvelles séquences réduites de deux graphes. La distance d’édition entre les deux
nouvelles séquences de graphes est à nouveau calculée : c’est-à-dire entre les
graphes 4Q et 4] , puis entre les graphes 4Q , et 4] , , distances que nous notons

1. Projet CITERE : ANR Blanc SHS 2009-2011, Circulations, Territoires et Réseaux de l’âge
classique aux Lumières.
 Modélisation par graphe de l’écriture 67

respectivement 4(c(4Q , 4] et 4(c 4Q , , 4] , . La distance finale entre les deux

mots (a) et (b) s’exprime alors par la moyenne des deux distances,
distances, voir figure 8.
c _, d = ∑[ 4(c 4Q , 4] (7)

Figure 8. Illustration du processus de fusion de blocs reposant sur la distance DTW

(les flèches indiquent le chemin optimal suivi pour l’appariement)

5. Expérimentations et protocoles

Les expérimentations sur lesquelles portent cette étude reposent sur deux
ensembles de données : la base de données désormais usuelle pour les applications
de word-spotting et composée des lettres manuscrites de George Washington (1780)
(voir Rath et Manmatha, 2007) et le registre de mariages célébrés en la Cathédrale
de Barcelone dont les manuscrits sont datés des périodes allant de 1451 à 1905 et
qui nommé la base 5CofM (The Five Centuries of Marriages Database), (voir
Fernandez et al., 2011). Les résultats obtenus sur ces deux bases de tests ont été
comparés à cinq autres approches développées dans le domaine du word- word-spotting.
La première approche comparative a été développée dans Rath et Manmatha (2007)
et traite de l’alignement de séquences utilisant la distance DTW exploitant des
attributs structurels de contours. Elle est notée DTW dans les graphiques de
résultats. La seconde approche proposée par Lladós et al., (2012) concerne la
construction de sacs de mots visuels à plusieurs échelles générant un modèle
statistique pour la comparaison de mots sur la base d’un clustering de formes. Elle
est notée BoVW dans les tableaux de résultats. La troisième approche vise le
développement d’un modèle pseudo-structurel utilisant une représentation reposant
sur les descripteurs Loci (voir Lladós et al., 2012). Elle est nommée Pseudo-Struct
© Lavoisier | Téléchargé le 29/12/2023 sur www.cairn.info (IP: 196.117.40.229)

© Lavoisier | Téléchargé le 29/12/2023 sur www.cairn.info (IP: 196.117.40.229)

dans les tableaux de résultats. Ces descripteurs structurels encodent la fréquence
d’intersections entre le mot centré en un point caractéristique choisi dans l’écriture
et huit orientations autour de ce point. La quatrième approche servant de référence
est structurelle et fondée sur une modélisation par graphe utilisant les descripteurs
nommés bag-of-paths par analogie avec la notion plus communément admise de
bag-of-word, (voir Lladós et al., 2012). Nous l’avons nommée Struct. La cinquième
méthode de word-spotting proposée par Leydier et al. (2009) est exploitée ici. Elle
repose sur une approche sans segmentation des textes et l’extraction de guides pour
le repérage de points d’ancrage initiant la recherche et une distance cohésive souple
reposant sur des intensités locales de gradients orientés et qui assure des
appariements très robustes aux déformations locales. Nous la nommerons Leydier
 68 DN. Volume 17 – n° 3/2014

dans les graphiques et tableaux ci-dessous. L’étude des résultats est réalisée à partir
de l’exploitation d’indicateurs statistiques de rappel, de précision et de précision
moyenne illustrés dans la section suivante.

5.1. Données expérimentales et évaluation de performances

La première base sur laquelle repose les tests est la base composée de vingt
pages de la collection de lettres manuscrites issues de la base GW. La seconde
évaluation repose sur l’exploitation des données issues de vingt sept pages issues de
la base 5CofM . Les deux corpus sont conçus comme des corpus étalons disposant
d’une segmentation en mots transcrits et permettant donc de réaliser une étude de
performance pertinente. Pour la collection GW, on dispose de 4 860 mots segmentés
avec 1 124 transcriptions, et pour la collection 5CofMon dispose de 6 544 mots
associés à 1751 transcriptions. Tous les mots possédant au minimum 3 lettres et
apparaissant au minimum 10 fois dans la collection sont sélectionnés comme mot
requête. Par conséquent, les expérimentations se fondent sur précisément 1 847
requêtes correspondant à 68 mots différents pour la base GW et 514 requêtes de 32
mots pour la base 5CofM. La figure 9 illustre quelques extraits de mots de la base
des registres de mariages (5CofM).

Figure 9. Exemples de mots du registre de mariages de la cathédrale de Barcelone,

5CofM (1825)

Afin d’évaluer les performances de l’approche que nous avons proposée, nous
avons choisi trois indices relevant des valeurs de rappel et de précision. Considérant
une requête, on notera Rel l’ensemble de réponses pertinentes relativement à cette
© Lavoisier | Téléchargé le 29/12/2023 sur www.cairn.info (IP: 196.117.40.229)

© Lavoisier | Téléchargé le 29/12/2023 sur www.cairn.info (IP: 196.117.40.229)

requête et Ret l’ensemble des éléments effectivement retrouvés dans la base de tests.
– P@n — est la précision obtenue au rang n, considérant uniquement les
npremiers retours du système. Dans nos tests, nous ne considérons que les retours
aux rangs n= 10 et 20.
– R-Précision — la R-Précision est la précision obtenue après que R images
aient été retrouvées, avec R le nombre de documents pertinents pour la requête
considérée.
– mAP (mean Average Precision) — mAP ou moyenne des précisions obtenues
chaque fois qu’un mot image pertinent est retrouvé. Il correspond à l’indice calculé à
 Modélisation par graphe de l’écriture 69

partir de chaque valeur de précision pour chaque rang. Pour une requête donnée, en
notant r(n) la fonction indiquant le nombre de retours positifs du système au rang n,
cette précision moyenne s’exprime comme le rapport suivant (Card(req) est le
nombre de requêtes) :
jklm(nop)
∑qr@ (h@[×U([))
efg (8)
MQUs(tWu)

5.2 Résultats et discussion

La figure 10 présente la courbe de précision-rappel obtenues pour l’ensemble des

tests pour les deux bases de données traitées (GW et 5CofM). Les tableaux 1 et 2
illustrent les résultats complets d’évaluation de performances pour les deux bases en
exploitant notre proposition à partir de deux versions du squelette : une version
basique (reposant sur l’extraction d’un squelette selon (Zhang et Suen, 1987))
nommée Proposed without TV et une version améliorée intégrant le vote tensoriel
pour la reconstruction des lignes aux points de discontinuités nommée Proposed.

(a) (b)

Figure 10. Courbes de précision-rappel pour 7 méthodes de word-spotting portant

sur (a) la base George Washington GW et (b) le registre de mariages
de la cathédrale de Barcelone 5CofM
© Lavoisier | Téléchargé le 29/12/2023 sur www.cairn.info (IP: 196.117.40.229)

© Lavoisier | Téléchargé le 29/12/2023 sur www.cairn.info (IP: 196.117.40.229)

On peut tout d’abord constater sur les deux bases que notre proposition surpasse
les performances des méthodes structurelles et pseudo-structurelles (dénommées
respectivement Pseudo-Struct et Struct et faisant référence aux travaux décrits dans
(Lladós et al., 2012)). La méthode dénommée BoVW reposant sur les sacs de mots
visuels réalise les meilleures performances sur les deux jeux de données, cela est
sans doute en lien avec le processus de description des mots basé directement sur
l’image à niveaux de gris sans segmentation binaire. Les autres méthodes comparées
dans cette étude basent leur description sur une version binaire des images,
augmentant ainsi la sensibilité aux données bruitées des mécanismes mis en jeux.
 70 DN. Volume 17 – n° 3/2014

Il est intéressant dans notre cas de constater que notre proposition réalise ses
meilleures performances sur la base 5CofM. La raison vient du fait déjà évoqué
précédemment que les images de la collection GW présentent de plus nombreuses
dégradations que celles contenues dans la base 5CofM. Celles-ci impactent
fortement la construction du squelette établi sur un algorithme simple
d’amincissement morphologique. Dans notre approche, c’est davantage la qualité du
squelette qui est mise en cause en provoquant des discontinuités dans la
reconstruction des traits et qui génère un nombre de connexités souvent supérieur à
celui qui est effectivement observé, voir figure 1. La correction par vote tensoriel
conduit à une amélioration significative du squelette mais qui se traduit par une
augmentation globalement assez faible de la précision (sur le jeu de données GW)
notamment du fait de la présence exceptionnellement élevée de zones de
discontinuités très larges, (voir tableaux 1 et 2). Cependant l’exploitation
d’approches variationnelles, des tenseurs d’inertie ou de la diffusion anisotrope est
néanmoins très prometteuse car elle offre des possibilités d’extraire un squelette sur
des formes non binaires.

Tableau 1. Performances pour l’ensemble des méthodes

testées sur la base GW (TV : Tensor Voting)

P@10 P@20 R-précision mAP

Proposed approach (without TV) 0.372 0.312 0.206 0.175
Proposed approach 0.393 0.329 0.203 0.175
DTW (Manmatha) 0.346 0.286 0.191 0.169
BoVW 0.606 0.523 0.412 0.422
Pseudo-Struct 0.183 0.149 0.096 0.072
Structural 0.059 0.049 0.036 0.028
Leydier 0.449 0.359 0.269 0.238

Tableau 2. Performances pour l’ensemble des méthodes testées

sur la base 5CofM (TV : Tensor Voting)

P@10 P@20 R-précision mAP

© Lavoisier | Téléchargé le 29/12/2023 sur www.cairn.info (IP: 196.117.40.229)

© Lavoisier | Téléchargé le 29/12/2023 sur www.cairn.info (IP: 196.117.40.229)

Proposed approach (without TV) 0.342 0.241 0.270 0.246
Proposed approach 0.347 0.246 0.273 0.247
DTW (Manmatha) 0.288 0.201 0.214 0.192
BoVW 0.378 0.289 0.303 0.3
Pseudo-Struct 0.273 0.189 0.199 0.178
Structural 0.155 0.12 0.118 0.097
Leydier 0.235 0.153 0.170 0.145
 Modélisation par graphe de l’écriture 71

Excepté la méthode de Leydier, les autres méthodes reposent sur des versions
binaires de l’image. Par conséquent, les méthodes fondées sur des modèles
d’apparence basées sur les variations de luminosité locales (BoVW, DTW de
Manmatha et l’approche de Leydier) produisent sur des textes de résolution
moyenne plus faible, des résultats meilleurs que les méthodes purement structurelles
(la nôtre, la méthode Pseudo-Struct et Structural).
L’approche statistique BoVW décrite à partir d’une sélection de points d’intérêt
SIFT permet une description bas niveau robuste aux variations, elle est également
compacte et complète dans sa prise en compte de l’information de luminance en
chaque point d’intérêt. Elle est globalement plus insensible aux distorsions internes
de l’écriture. Notons cependant que la classification des mots visuels issus de la
méthode BoVW nécessite une comparaison reposant sur une représentation
pyramidale des données (Algorithme SPM : Spatial Pyramidal Matching décrit dans
(Lladós et al., 2012) qui encode les relations spatiales non intégrées dans les
codebooks visuels. Elle offre ainsi un meilleur pouvoir discriminant mais augmente
de façon significative les temps de calcul, ce qui réduit son champ d’application (à
de plus larges collections de documents).
À l’exception de l’approche BoVW, notre proposition s’est montrée plus
performante que les approches structurelles et pseudo-structurelles reposant sur des
graphes et procédant sans apprentissage. Cela illustre en particulier l’efficacité du
choix des points structurels définis sur le squelette des mots pour diriger la structure
du graphe qui le décrit, au lieu de points maximisant une variation locale d’intensité
lumineuse, comme cela est généralement le cas pour les points d’intérêt plus
standards. Par ailleurs, les informations contextuelles apportées par une description
par contexte de formes (SC) constituent une description très riche de ces points.
Le coût global permettant de conduire la recherche de mot par similarité est
difficile à établir du fait du grand nombre d’étapes allant de la description bas niveau
à l’appariement proprement dit (pour l’approche BoVW, il est nécessaire de
considérer la construction du codebook, la classification des points SIFT et enfin
l’appariement complet). Nous pouvons cependant proposer de comparer
qualitativement les durées de traitement, les performances relatives (déduites des
taux figurant dans les tableaux 1 et 2) et différents critères usuellement exploités
pour caractériser les capacités d’adaptation des systèmes (facilité du passage à
l’échelle, aisance à l’indexation), voir tableau 3.
© Lavoisier | Téléchargé le 29/12/2023 sur www.cairn.info (IP: 196.117.40.229)

© Lavoisier | Téléchargé le 29/12/2023 sur www.cairn.info (IP: 196.117.40.229)

Notons enfin que les résultats de notre approche même s’ils présentent la
faiblesse de faire ressortir en faux positifs des mots structurellement proches du mot
requête (mais néanmoins différents du point de vue d’un appariement strict),
permettent de retrouver des mots construits sur la même base lexicale (mots
présentant un radical commun et des variantes en début ou en fin). Ce qui peut être
considéré comme une faiblesse pour un appariement strict peut en contre partie être
vu comme un atout dans la perspective de retrouver des mots visuellement
similaires, des mots de même famille ou de radicaux communs ( comme cela est le
cas dans la collection de Lettres Clandestines du 18e siècle du projet ANR CITERE
en lien avec ce travail – le lien du projet est indiqué dans les remerciements).
 72 DN. Volume 17 – n° 3/2014

Tableau 3. Comparaison qualitative de cinq approches de word-spotting

(reprise des tableaux de comparaisons 1 et 2)

Taille Temps Index- Prétrai- Performanc Passage

able tement e à l’échelle
−
Proposed + − ++ −− ++
(temps)
DTW −
+ −− − − +
(Manmatha) (taille)
−
BoVW −− + + + ++
(temps)
−
Leydier −− + − + +
(temps)
−
Pseudo-
++ ++ ++ − + (pouvoir
Struct
discriminatif)
−
Structural ++ ++ ++ −− − (pouvoir
discriminatif)

La complexité des méthodes structurelles est un de leurs points faibles et cela

accompagne la difficulté d’un bon passage à l’échelle. Nous pouvons l’observer
avec les temps de calcul nécessaires pour traiter une page. Dans notre cas, pour
réduire la complexité, deux voies peuvent être exploitées : d’une part, on peut
envisager de réaliser une comparaison sur un graphe unique (concaténation des
graphes composant le mot) évitant ainsi l’étape d’estimation de la distance
dynamique DTW et un second calcul de la distance d’édition entre les graphes
fusionnés ; d’autre part on peut modifier la représentation du graphe en considérant
les nœuds non plus comme étant les points structurels de l’écriture mais comme les
graphèmes (segments entre sommets que l’on peut classifier et dont on ne retient
que le représentant de la classe). Dans ce cas l’étape de calcul du coût d’édition peut
se réaliser hors ligne et un gain de temps conséquent peut être obtenu. Ces deux
voies sont en cours d’investigation sur la collection des correspondances
clandestines du projet ANR CITERE.
© Lavoisier | Téléchargé le 29/12/2023 sur www.cairn.info (IP: 196.117.40.229)

© Lavoisier | Téléchargé le 29/12/2023 sur www.cairn.info (IP: 196.117.40.229)

6. Conclusion et perspectives

Ce papier est la présentation de deux contributions dans le domaine de la

recherche de mots par similarité. Tout d’abord, nous avons proposé une nouvelle
approche de la description des mots images fondée sur une structure de graphes
construit sur une sélection de points structurels et morphologiques de l’écriture.
Dans un second temps, nous avons proposé un nouveau mécanisme de capture de
similarités souples basé sur une distance dynamique permettant de comparer les
séquences de graphes formant les mots à l’aide d’une distance d’édition approximée
et permettant de reconstruire une séquence optimale facilitant les appariements.
 Modélisation par graphe de l’écriture 73

L’information bas niveau de l’image est exploitée dans ses expressions de contours
(par le descripteur de contexte de formes) et de squelette (permettant une sélection
rapide de points d’intérêt structurels). La souplesse offerte par l’usage de la distance
dynamique (DTW) pour l’appariement et son rôle dans le processus de fusion des
objets connexes permet de compenser les distorsions subies par l’écriture lors de la
formation des mots et les irrégularités relevées par l’étape de squelettisation. Celle-
ci peut parfois créer artificiellement des connexités non visibles ou ne faisant pas
sens. Notre proposition repose ainsi sur un mécanisme de comparaison de graphes et
un usage intensif d’une distance d’édition approximée sans aucun apprentissage
préalable. Cette approche n’avait jamais été exploitée dans un contexte de recherche
de mots manuscrits. L’application à de nouveaux corpus plus volumineux constitue
le prochain enjeu de cette étude, en lien avec les données du projet ANR CITERE
aux volumes très conséquents. C’est donc sur la complexité calculatoire qu’un effort
devra être réalisé, sachant que la comparaison de graphes même partielle est très
consommatrice de puissance de calculs (DTW, coût d’édition en deux passes et
itérations en un très grand nombre de fenêtres d’analyse sur une page de texte
exploitant un descripteur de formes de dimension 60). Notre volonté de conserver
les deux dimensions de la représentation par graphe au lieu de ramener la
description à une séquence 1D de caractéristiques est un défi que nous tenterons de
maintenir malgré l’augmentation de taille des corpus à analyser.
Actuellement, nos travaux portent sur l’élaboration d’une stratégie complète pré-
sélectionnant des régions d’intérêt dans les images au fort potentiel en rapport avec
les propriétés morphologiques du mot-requête soumis au système. Cette étape vise
ainsi à rejeter massivement des propositions non pertinentes et de ne traiter que les
fenêtres d’analyse candidates. Une reconsidération locale de la description par
contexte de formes autour des sommets des graphes décrivant les objets connexes
pourrait ainsi soutenir cette étape de recherche de zones candidates.

Remerciements
Nous tenons à remercier le professeur Antony McKenna responsable du projet
ANR CITERE et d’un fonds de manuscrits numérisés uniques : « Les
correspondances clandestines de l’Europe des Lumières » ainsi que « Les
correspondances de Pierre Bayle ». Cette recherche est soutenue par un projet
régional d’ARC de la région Rhônes-Alpes en lien avec le projet ANR CITERE et
© Lavoisier | Téléchargé le 29/12/2023 sur www.cairn.info (IP: 196.117.40.229)

© Lavoisier | Téléchargé le 29/12/2023 sur www.cairn.info (IP: 196.117.40.229)

soutenue également par le projet espagnol TIN2012-37475-C02-02 ainsi que le
projet européen ERC-2010-AdG-20100407-269796 au sein du CVC de Barcelone.

Bibliographie

Aida-Zade K. R., Hasanov J. Z. (2009). Word base line detection in handwritten text
recognition systems. International Journal of Electrical and Computer Engineering,
vol. 4, n° 5, p. 310-314.
Chherawala Y., Wisnovsky R., Cheriet M. (2011). Tsv-lr: Topological signature vector-based
lexicon reduction for fast recognition of premodern Arabic subwords. Proc. of the
Workshop HIP, p. 6-13.
 74 DN. Volume 17 – n° 3/2014

Deriche R. (1987). Using Canny’s criteria to derive a recursively implemented optimal edge
detector. Int. J. Computer Vision, vol. 1, p. 167-187.
Do T-H., Tabbone S., Terrades O.R. (2013). New Approach for Symbol Recognition
Combining Shape Context of Interest Points with Sparse Representation. Proc. of the
ICDAR, p. 265-269.
Fernandez D., Lladós J., Fornés A. (2011). Handwritten word-spotting in old manuscript
images using a pseudo-structural descriptor organized in a hash structure. Pattern
Recognition and Image Analysis, vol. 6669, p. 628-635.
Fischer A., Keller A., Frinken V., Bunke H. (2010). HMM-based word spotting in
handwritten documents using subword models. Proc. of the ICPR, 2010, p. 3416-3419.
Fischer A., Riesen K., Bunke H. (2010). Graph similarity features for HMM-based
handwriting recognition in historical documents. Proc. of the ICFHR, p. 253-258.
Fischer A., Suen C. Y., Frinken V., Riesen K., Bunke H. (2013). A fast matching algorithm
for graph-based handwriting recognition. Lecture Notes in Computer Science, vol. 7887,
p. 194-203.
Hani D., Eglin V., Bres S., Vincent N. (2010). A new approach for centerline extraction in
handwrittenstrokes: an application to the constitution of a codebook. International
Workshop on Document Analysis Systems, p. 425-425.
Lladós J., Rusinol M., Fornés A., Fernandez D., and Dutta A. (2012). On the influence of
word representations for handwritten word-spotting in historical documents. Pattern
Recognition and Artificial Intelligence,vol. 26, n° 5, p. 1 263 002.1-1 263 002.25.
Lebourgeois F., Emptoz H. (2007). Skeletonization by Gradient Regularization and Diffusion.
Proc. of the ICDAR, p.1118-1122.
Leydier Y., Ouji A., LeBourgeois F., Emptoz H. (2009). Towards an omnilingual word
retrieval system for ancient manuscripts. PR, vol. 42, n° 9, p. 2089-2105.
Leydier Y., Eglin V., Bres S., Stutzmann D. (2014). Learning-free text-image alignment for
medieval manuscripts. Proceedings of Int. Conference of Frontiers of Handwriting
Recognition, p. 81-87.
Lu S., Ren Y., and Suen C. (1991). Hierarchical attributed graph representation and
recognition of handwritten Chinese characters. PR, vol. 24, n° 7, p. 617-632.
Luqman M.M., Ramel J-Y., Lladós J., Brouard T. (2011). Sub-graph Spotting through
Explicit Graph Embedding: An Application to Content Spotting in Graphic Document
© Lavoisier | Téléchargé le 29/12/2023 sur www.cairn.info (IP: 196.117.40.229)

Images. International Conference on Document Analysis and Recognition, p.870-874.

© Lavoisier | Téléchargé le 29/12/2023 sur www.cairn.info (IP: 196.117.40.229)

Malleron V., Eglin V., Emptoz H., Dord-Crouslé S., Régnier P. (2009). Text lines and
snippets extraction for 19th century handwriting documents layout analysis. Int.
Conference on Document Analysis and Recognition, Barcelone. p. 1001-1005.
Medioni G., Tang C. K., Lee M. S (2000). Tensor voting: theory and applications.
Proceedings of the Int. Conf. RIFA, 2000.
Munkres J. (1957). Algorithms for the assignment and transportation problems. The Society
for Industrial and Applied Mathematics, vol. 5, p. 32-38.
Puzicha J., Belongie S., Malik J. (2002). Shape matching and object recognition using shape
contexts. PAMI, vol. 24, p. 509-522.
 Modélisation par graphe de l’écriture 75

Rath T., Manmatha R. (2007). Word-spotting for historical documents. Proc. of the ICDAR,
vol. 9, n° 2-4, p. 139-152.
Riesen K., Bunke H. (2009). Approximate graph edit distance computation by means of
bipartite graph matching. Image and Vision Computing, vol. 27, n° 7, p. 950-959.
Rodriguez-Serrano J., Perronnin F. (2009). Handwritten word-spotting using hidden markov
models and universal vocabularies; PR, vol. 42, n° 9, p. 2106-2116.
Wang P., Eglin V., Largeron C., McKenna A., Garcia C. (2013). A comprehensive
representation model for handwriting dedicated to word-spotting. Proc. of the ICDAR,
p. 450-454.
Wang P., Eglin V., Largeron C., Garcia C., Fornès A., Llados J. (2014). A Coarse-to-Fine
Word Spotting Approach for Historical Handwritten Documents Based on Graph
Embedding and Graph Edit Distance. ICPR, International Conference on Pattern
Recognition, p. 363-368.
Zaslavskiy M., Bach F., Vert J. (2009). A path following algorithm for the graph matching
problem. PAMI, vol. 31, n° 12, p. 2227-2241.
Zhang T. Y., Suen C. Y. (1984). A fast parallel algorithm for thinning digital patterns.
Communication of the ACM, vol. 27, p. 236-239.
© Lavoisier | Téléchargé le 29/12/2023 sur www.cairn.info (IP: 196.117.40.229)

© Lavoisier | Téléchargé le 29/12/2023 sur www.cairn.info (IP: 196.117.40.229)