Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

UNIVERSITÉ FRANÇOIS RABELAIS DE TOURS ÉCOLE DOCTORALE MIPTIS Laboratoire d’Info

UNIVERSITÉ FRANÇOIS RABELAIS DE TOURS ÉCOLE DOCTORALE MIPTIS Laboratoire d’Informatique (EA 6300) THÈSE présentée par : The Anh PHAM soutenue le : 27 novembre 2013 pour obtenir le grade de : Docteur de l’université François - Rabelais de Tours Discipline/ Spécialité : INFORMATIQUE Détection robuste de jonctions et points d’intérêt dans les images et indexation rapide de caractéristiques dans un espace de grande dimension THÈSE dirigée par : Ramel Jean-Yves Professeur, Université François Rabelais de Tours Co-encadrants: Delalandre Mathieu Maître de Conférences, Université François Rabelais de Tours Barrat Sabine Maître de Conférences, Université François Rabelais de Tours RAPPORTEURS : Tabbone Salvatore-Antoine Professeur, Université de Lorraine, France. Ogier Jean-Marc Professeur, Université de La Rochelle, France. JURY : Llados Josep Professeur, Université Autonoma de Barcelone, Espagne. Tabbone Salvatore-Antoine Professeur, Université de Lorraine, France. Ogier Jean-Marc Professeur, Université de La Rochelle, France. Kise Koichi Professeur, Université Osaka Prefecture, Japon. Ramel Jean-Yves Professeur, Université François Rabelais de Tours Delalandre Mathieu Maître de Conférences, Université François Rabelais de Tours Barrat Sabine Maître de Conférences, Université François Rabelais de Tours Acknowledgments "Gratitude is the sign of noble souls." – Aesop First of all, I would like to present my warmest regards to my advisors: Dr. Mathieu Delalandre, Dr. Sabine Barrat, and Professor Jean-Yves Ramel. I am delighted and I feel privileged to be supervised by you all. All the achievement that I have obtained during my PhD are due to your patience, openness and devotion provided to me during the past three years. I appreciate so very much all the open discussion that we have exchanged with each other through a huge number of reading groups during this thesis. I feel blessed to keep forever all your kind guidance, great eﬀorts, and considerable enthusiasm at the bottom of my heart. I am grateful to the reviewers for taking time to give me valuable comments and sugges- tions on this manuscript. Despite of my exhaustive eﬀort on fulﬁlling this work, there are still a number of issues that need to be pointed out and corrected by you. Your comments and feedback shall deﬁnitely make this dissertation improved considerably. I musk thank the administration staﬀof Laboratory of Computer Science (François Rabelais University of Tours) for their pretty kind assistance and support during three years of my thesis research. Thank you very much for making easier all the administrative works involved in my thesis and part of my life here in Tours. In particular, on behalf of Vietnamese students at Polytech’Tours, I would like to present my special thanks to Professor Jean-Charles Billaut for his openness, kindness, and inﬁnite help and support. I am deﬁnitely sure that you all are very friendly, open-hearted, and helpful people that I have ever had the change of knowing you. Thank you very much all my friends. When I ﬁrst came here, everything is new and strange for me, but you have helped me a lot. You make me more and more familiar to the new environment. You gave me the chance to participate in our excellent PhD student network in which we can freely discuss about our work and share our ideas together. I realize that you all are very friendly, intelligent, and humorous people. I sincerely hope we shall have the chance to meet together in the future. At last, I would like to thank the people from my personal side. I am thankful to Vietnam International Education Development (VIED)1 for awarding scholarship to fulﬁll 1www.vied.vn 3 ACKNOWLEDGMENTS my PhD research. Many thanks to my aﬃliation in Vietnam, Hong Duc University (HDU)2, for making all the arrangements to allow me to concentrate entirely on my PhD research abroad. Big thanks to Vietnamese Student Association in Tours and Blois (AEViVaL)3 for your support and promoting me as a vice-president during two years in the past. Thanks a million to the association of Touraine-Vietnam4 for your considerable encouragement and assistance. Special thanks to my little family, parents and brothers. Your love and moral support actually made me go through the crucial and diﬃcult phases of this thesis. Thank you so very much! November 27th, 2013 (Tours, France). The Anh Pham 2www.hdu.edu.vn 3Association des Etudiants Vietnamiens du Val de Loire (AEViVaL): www.aevival.fr 4www.touraine-vietnam.fr 4 Résumé Les caractéristiques locales sont essentielles dans de nombreux domaines de l’analyse d’images comme la détection et la reconnaissance d’objets, la recherche d’images, etc. Ces dernières années, plusieurs détecteurs dits locaux ont été proposés pour extraire de telles caractéristiques. Ces détecteurs locaux fonctionnent généralement bien pour certaines ap- plications, mais pas pour toutes. Prenons, par exemple, une application de recherche dans une large base d’images. Dans ce cas, un détecteur à base de caractéristiques bi- naires pourrait être préféré à un autre exploitant des valeurs réelles. En eﬀet, la précision des résultats de recherche pourrait être moins bonne tout en restant raisonnable, mais probablement avec un temps de réponse beaucoup plus court. En général, les détecteurs locaux sont utilisés en combinaison avec une méthode d’indexation. En eﬀet, une méthode d’indexation devient nécessaire dans le cas où les ensembles de points traités sont composés de milliards de points, où chaque point est représenté par un vecteur de caractéristiques de grande dimension. Malgré le succès des nombreuses méthodes proposées dans la littérature pour la mise en place de tels détecteurs, aucune approche robuste de détection au sein des images de trait ne semble exister. Par conséquent, la première contribution de cette thèse est de proposer une telle approche. Plus précisément, une nouvelle méthode de détection de jonctions dans les images de trait est présentée. La méthode proposée possède plusieurs caractéristiques intéressantes. Tout d’abord, cette méthode est robuste au problème de déformation des jonctions. De plus, cette méthode peut détecter plusieurs jonctions dans une même zone, supportant ainsi les cas de détection multiple. Ensuite, les jonctions sont détectées avec peu d’erreurs de localisation, caractérisant ainsi la précision de la méthode. La méthode proposée a également une faible complexité algorithmique, lui permettant ainsi de supporter des applications à fort coût de calcul comme la localisation, la recherche ou la reconnaissance de symboles. Enﬁn, elle est invariante aux transformations géométriques habituelles (rotation, changement d’échelle et translation) et robuste aux déformations communes rencontrées dans les images de documents (comme le bruit d’impression, la basse résolution et artefacts de compression). Des expériences approfondies ont été menées pour étudier le comportement de la méth- ode proposée. Celle-ci a été comparée à deux méthodes référentes de l’état de l’art. Les résultats ont montré que la méthode proposée surclasse signiﬁcativement les approches de l’état de l’art. De plus, cette méthode s’est avérée utile pour la réalisation d’applications de plus haut-niveau. En eﬀet, une application de localisation de symboles a été développée, démontrant que les jonctions détectées pouvaient être un support essentiel à l’extraction des autres primitives graphiques composant le document, permettant ainsi une localisation 5 RÉSUMÉ et une reconnaissance robustes des symboles. La seconde contribution de cette thèse traite de l’indexation de caractéristiques. Les méthodes de recherche de plus proches voisins rapides sont devenues un besoin crucial pour de nombreux systèmes de recherche ou de reconnaissance. Bien que de nombreuses tech- niques d’indexation aient été proposées dans la littérature, leurs performances de recherche restent limitées à certains domaines d’application seulement. De plus, les méthodes exis- tantes, qui sont eﬃcaces dans le cas de la recherche approximative de plus proches voisins, s’avèrent moins eﬃcaces pour ce qui est de la recherche exacte. Les limites de ces méthodes nous ont conduits à proposer un algorithme d’indexation avancé. L’algorithme d’indexation proposé fonctionne aussi bien pour les tâches de recherche approximative que de recherche exacte de plus proches voisins. Des expériences approfondies ont été menées aﬁn de com- parer l’algorithme proposé à plusieurs méthodes de l’état de l’art. Ces tests ont montré que l’algorithme proposé améliore signiﬁcativement les performances de recherche, pour diﬀérents types de caractéristiques, par rapport aux méthodes auxquelles notre algorithme a été comparé. Enﬁn, les codes source des deux ont été rendus disponibles pour l’intérêt des chercheurs. Mots clés : Détection de jonctions, caractérisation de jonctions, détection de points d’intérêt, documents graphiques, images de trait, recherche approximative de plus proches voisins, indexation de caractéristiques, arbres de clustering. 6 Abstract Local features are of central importance to deal with many diﬀerent problems in image analysis and understanding including image registration, object detection and recognition, image retrieval, etc. Over the years, many local detectors have been presented to detect such features. Such a local detector usually works well for some particular applications but not all. Taking an application of image retrieval in large database as an example, an eﬃcient method for detecting binary features should be preferred to other real-valued feature detection methods. The reason is easily seen: it is expected to have a reasonable precision of retrieval results but the time response must be as fast as possible. Generally, local features are used in combination with an indexing scheme. This is highly needed for the case where the dataset is composed of billions of data points, each of which is in a uploads/Litterature/ robust-junction-detector-in-line-drawing-images-and-time-efficient-feature-indexing-in-feature-vector-space.pdf