Feature design and lexicon reduction for efficient offline handwriting recognition

Chherawala, Youssouf (2014). Feature design and lexicon reduction for efficient offline handwriting recognition. Thèse de doctorat électronique, Montréal, École de technologie supérieure.

Prévisualisation	PDF Télécharger (2MB) | Prévisualisation
Prévisualisation	PDF Télécharger (1MB) | Prévisualisation

Résumé

This thesis establishes a pattern recognition framework for offline word recognition systems. It focuses on the image level features because they greatly influence the recognition performance. In particular, we consider two complementary aspects of prominent features impact: lexicon reduction and the actual recognition. The first aspect, lexicon reduction, consists in the design of a weak classifier which outputs a set of candidate word hypotheses given a word image. Its main purpose is to reduce the recognition computational time while maintaining (or even improving) the recognition rate. The second aspect is the actual recognition system itself. In fact, several features exist in the literature based on different fields of research, but no consensus exists concerning the most promising ones. The goal of the proposed framework is to improve our understanding of relevant features in order to build better recognition systems. For this purpose, we addressed two specific problems: 1) feature design for lexicon reduction (application to Arabic script), and 2) feature evaluation for cursive handwriting recognition (application to Latin and Arabic scripts).

Few methods exist for lexicon reduction in Arabic script, unlike Latin script. Existing methods use salient features of Arabic words such as the number of subwords and diacritics, but totally ignore the shape of the subwords. Therefore, our first goal is to perform lexicon reductionn based on subwords shape. Our approach is based on shape indexing, where the shape of a query subword is compared to a labeled database of sample subwords. For efficient comparison with a low computational overhead, we proposed the weighted topological signature vector (W-TSV) framework, where the subword shape is modeled as a weighted directed acyclic graph (DAG) from which the W-TSV vector is extracted for efficient indexing. The main contributions of this work are to extend the existing TSV framework to weighted DAG and to propose a shape indexing approach for lexicon reduction. Good performance for lexicon reduction is achieved for Arabic subwords. Nevertheless, the performance remains modest for Arabic words.

Considering the results of our first work on Arabic lexicon reduction, we propose to build a new index for better performance at the word level. The subword shape and the number of subwords and diacritics are all important components of Arabic word shape. We therefore propose the Arabic word descriptor (AWD) which integrates all the aforementioned components. It is built in two steps. First, a structural descriptor (SD) is computed for each connected component (CC) of the word image. It describes the CC shape using the bag-of-words model, where each visual word represents a different local shape structure. Then, the AWD is formed by concatenating the SDs using an efficient heuristic, implicitly discriminating between subwords and diacritics. In the context of lexicon reduction, the AWD is used to index a reference database. The main contribution of this work is the design of the AWD, which integrates lowlevel cues (subword shape structure) and symbolic information (subword counts and diacritics) into a single descriptor. The proposed method has a low computational overhead, it is simple to implement and it provides state-of-the-art performance for lexicon reduction on two Arabic databases, namely the Ibn Sina database of subwords and the IFN/ENIT database of words.

The last part of this thesis focuses on features for word recognition. A large body of features exist in the literature, each of them being motivated by different fields, such as pattern recognition, computer vision or machine learning. Identifying the most promising approaches would improve the design of the next generation of features. Nevertheless, because they are based on different concepts, it is difficult to compare them on a theoretical ground and efficient empirical tools are needed. Therefore, the last objective of the thesis is to provide a method for feature evaluation that assesses the strength and complementarity of existing features. A combination scheme has been designed for this purpose, in which each feature is evaluated through a reference recognition system, based on recurrent neural networks. More precisely, each feature is represented by an agent, which is an instance of the recognition system trained with that feature. The decisions of all the agents are combined using a weighted vote. The weights are jointly optimized during a training phase in order to increase the weighted vote of the true word label. Therefore, they reflect the strength and complementarity of the agents and their features for the given task. Finally, they are converted into a numerical score assigned to each feature, which is easy to interpret under this combination model. To the best of our knowledge, this is the first feature evaluation method able to quantify the importance of each feature, instead of providing a ranking based on the recognition rate. Five state-of-the-art features have been tested, and our results provide interesting insight for future feature design.

Titre traduit

Conception de caractéristiques et réduction du lexique pour la reconnaissance de l'écriture manuscrite hors-ligne

Résumé traduit

Cette thèse établit un cadre de travail de reconnaissance de formes pour les systèmes de reconnaissance de mots hors-ligne. Elle se concentre sur les caractéristiques de l’image, car elles ont une grande influence sur les performances de reconnaissance. En particulier, nous considérons deux aspects complémentaires de l’impact des caractéristiques: la réduction du lexique et la reconnaissance elle-même. Le premier aspect, la réduction du lexique, consiste à concevoir un classifieur faible qui fournit en sortie un ensemble d’hypothèses de mots à partir d’une image de mot. Son objectif principal est de réduire le temps de calcul de la reconnaissance tout en maintenant (voire améliorant) le taux de reconnaissance. Le deuxième aspect est le système de reconnaissance proprement dit. Plusieurs caractéristiques existent dans la littérature, issues de différents domaines de recherche, mais il n’existe pas de consensus sur les pistes les plus prometteuses. L’objectif de cette thèse est d’améliorer notre compréhension des caractéristiques pertinentes pour construire des systèmes de reconnaissance encore plus performants. À cette fin, nous avons abordé deux problèmes spécifiques: 1) la conception de caractéristiques pour la réduction du lexique (appliquée à l’écriture arabe), et 2) l’évaluation de caractéristiques pour la reconnaissance de l’écriture manuscrite cursive (appliquée à l’écriture latine et arabe).

Contrairement à l’écriture latine, la problématique de réduction du lexique est peu abordée pour l’écriture arabe. Les méthodes existantes utilisent certaines caractéristiques fondamentales des mots arabes telles que le nombre de sous-mots et les signes diacritiques, mais ignorent totalement la forme des sous-mots. Par conséquent, notre premier objectif est de créer une méthode de réduction du lexique basée sur la forme des sous-mots. Notre approche utilise l’indexation de formes, où la forme d’un sous-mot requête est comparée à une base de données étiquetée de sous-mots échantillons. Pour une comparaison efficace avec un faible temps de calcul, nous avons proposé le vecteur de signature topologique pondéré (W-TSV), où la forme du sous-mot est modélisée par un graphe acyclique orienté (DAG) pondéré, à partir duquel le vecteur W-TSV est extrait pour l’indexation. La principale contribution de ce travail est d’élargir le cadre existant du vecteur de signature topologique (TSV) aux DAGs pondérés et de proposer une approche d’indexation de formes pour la réduction du lexique. Cette approche est performante pour la réduction d’un lexique composé de sous-mots arabes. Néanmoins, ses performances restent modestes pour les mots arabes.

Compte tenu des résultats de notre premier travail sur la réduction du lexique de mots arabe, nous proposons de construire un nouvel index pour de meilleures performances au niveau du mot. La forme des sous-mots, ainsi que leur nombre et celui des signes diacritiques sont des éléments importants de la forme du mot arabe. Nous proposons donc le descripteur de mot arabe (AWD) qui intègre toutes les composantes mentionnées ci-dessus. Il est construit en deux étapes. Tout d’abord, un descripteur de structure (SD) est calculé pour chaque composante connexe (CC) d’une image de mots. Il décrit la forme de la CC en utilisant le modèle de sac-de-mots, où chaque mot visuel représente une structure locale particulière. Ensuite, l’AWD est formé par la concaténation des SDs en utilisant une heuristique efficace, qui différencie implicitement les sous-mots des signes diacritiques. Dans le contexte de la réduction du lexique, l’AWD est utilisé pour indexer une base de données référence. La principale contribution de ce travail est la conception de l’AWD, qui intègre les caractéristiques de bas niveau (structure de la forme du sous-mot) et les informations symboliques (nombre de sous-mots et de signes diacritiques) en un seul descripteur. La méthode proposée possède un faible temps de calcul et elle est facile à implémenter. Elle fournit de meilleures performances pour la réduction du lexique sur deux bases de données d’écriture arabe, à savoir la base de données de sous-mots Ibn Sina et la base de données de mots IFN/ENIT.

La dernière partie de cette thèse se concentre sur les caractéristiques visuelles pour la reconnaissance de mots. Un grand nombre de caractéristiques existent dans la littérature, chacune d’elles étant motivées par différents domaines, tels que la reconnaissance des formes, la vision par ordinateur ou l’apprentissage machine. Identifier les approches les plus prometteuses servirait à améliorer la conception de la prochaine génération de caractéristiques. Néanmoins, comme elles sont fondées sur des concepts différents, il est difficile de les comparer de manière théorique, des outils empiriques sont donc nécessaires. Par conséquent, le dernier objectif de la thèse est de fournir une méthode d’évaluation de caractéristiques en fonction de leur force et complémentarité. Un modèle de combinaison a été conçu à cet effet, dans lequel chaque caractéristique est évaluée au travers d’un système référence de reconnaissance, basée sur les réseaux de neurones récurrents. Plus précisément, chaque caractéristique est représentée par un agent, qui est une instance du système de reconnaissance entraînée à partir de cette caractéristique. Les décisions de tous les agents sont combinées en utilisant un vote pondéré. Les poids sont optimisés conjointement au cours d’une phase d’entraînement, afin d’augmenter le vote pondéré de la véritable étiquette de chaque mot. Par conséquent, les poids reflètent la force et la complémentarité des agents et de leurs caractéristiques pour la tâche donnée. Enfin, les poids sont convertis en scores numériques attribués aux caractéristiques, qui sont faciles à interpréter sous ce modèle de combinaison. Au meilleur de notre connaissance, c’est la première méthode d’évaluation de caractéristiques capable de quantifier l’importance de chaque caractéristique, au lieu d’établir un classement basé sur le taux de reconnaissance. Cinq caractéristiques de l’état de l’art ont été testées et nos résultats offrent une perspective intéressante pour la conception de futures caractéristiques.

Type de document:	Mémoire ou thèse (Thèse de doctorat électronique)
Renseignements supplémentaires:	"Manuscript-based thesis presented to École de technolgie supérieure in partial fulfillment of the requirements for the degree of doctor of philosophy". Bibliographie : pages 139-149.
Mots-clés libres:	Reconnaissance de caractères (Informatique) Reconnaissance optique des formes (Informatique) Modèles de Markov cachés. Écriture arabe. caractéristique, conception, écriture, évaluation, indexation, latin, lexique, réduction, reconnaissance de l’écriture manuscrite, descripteur de formes, indexation de graphes, réseaux neuronaux récurrent, IFN/ENIT, Ibn Sina, RIMES
Directeur de mémoire/thèse:	Directeur de mémoire/thèse Cheriet, Mohamed
Programme:	Doctorat en génie > Génie
Date de dépôt:	26 mars 2014 20:21
Dernière modification:	10 déc. 2016 16:15
URI:	https://espace.etsmtl.ca/id/eprint/1273

Gestion Actions (Identification requise)

Dernière vérification avant le dépôt