La vision permet aux animaux de recueillir une information riche et détaillée sur leur environnent proche ou lointain. Les machines ont aussi accès à cette information riche via leurs caméras. Mais, elles n'ont pas encore le logiciel adéquat leur permettant de la traiter pour transformer les valeurs brutes des pixels de l'image en information plus utile telle que la nature, la position, et la fonction des objets environnants. Voilà une des raisons pour laquelle il leur est difficile de se mouvoir dans un environnement inconnu, et d'interagir avec les humains ou du matériel dans des scénarios non-planifiés. Cependant, la conception de ce logiciel comporte de multiples défis. Parmi ceux-ci, il est difficile de comparer deux images entre elles, par exemple, afin que la machine puisse reconnaître que ce qu'elle voit est similaire à une image qu'elle a déjà vue et identifiée. Une des raisons de cette difficulté est que la machine ne sait pas, a priori, quelles parties des deux images se correspondent, et ne sait donc pas quoi comparer avec quoi. Cette thèse s'attaque à ce problème et propose une série d'algorithmes permettant de trouver les parties correspondantes entre plusieurs images, ou en d'autre terme d'aligner les images. La première méthode proposée permet d'apparier ces parties de manière cohérente en prenant en compte les interactions entre plus de deux d'entre elles. Le deuxième algorithme proposé applique avec succès une méthode d'alignement pour déterminer la catégorie d'un objet centré dans une image. Le troisième est optimisé pour la vitesse et tente de détecter un objet d'une catégorie donné où qu'il soit dans l'image.

Seeing allows animals and people alike to gather information from a distance, often with high spatial and temporal resolution. Machines have access to this rich pool of information thanks to their cameras. But, they still do not have the software to process it, in order to transform the raw pixel values into useful information such as nature, position, and function of the surrounding objects. That is one of the reasons why it is still difficult for them to naviguate in an unknown environment and interract with people and objects in an un-planned fashion. However, the design of such a software implies many challenges. Among them, it is hard to compare two images, for insance, in order to recognize that the seen image is similar to another which has been previously seen and identified. One of the difficulties here is that the software cannot know  – a priori – which parts of the two images match. So, it cannot know which parts it should compare. This thesis tackles that problem, and presents a set of algorithm to find correspondences in images, or in other words, to align them. The first proposed method match parts in images, in a coherent fachion, taking into account higher order interactions between more than to of them. The second proposed algorithm apply with success alignment technique to discover the category of an object centered in an image. The third one is optimized for speed and…

Dans cette thèse nous montrons que le raisonnement symbolique associé à la vérification de la consistance d'arc avec propagation de contraintes est un outil efficace pour interpréter les images. Nous montrons dans un premier temps que ce cadre théorique permet de vérifier l'organisation spatiale de différentes composantes d'un objet complexe dans une image. Nous proposons ensuite d'étendre l'utilisation de celui-ci à la reconnaissance sélective des formes décrites par des équations mathématiques, grâce à la notion de consistance d'hyper-arc à deux niveaux de contraintes. La pertinence et la faisabilité de cette approche ont été validées par de multiples tests. En outre, les résultats obtenus sur des images sur-segmentées montrent que la méthode proposée est résistante au bruit, même dans des conditions où les humains (dans certains cas d'agnosie visuelle) peuvent échouer. Ces résultats soutiennent l'intérêt du raisonnement symbolique dans la compréhension de l'image.

In this thesis we show that symbolic reasoning associated with arc consistency checking is an efficient tool for images interpretation. We first show that this theoretical framework makes it possible to verify the spatial organization of different components of a complex object in an image. We then propose to extend the use of this framework to the selective recognition of shapes described by mathematical equations, thanks to the notion of hyper-arc consistency with bi-levels constraint. The relevance and feasibility of this approach have been validated by multiple tests. In addition, the results obtained on over-segmented images show that the proposed method is noise-resistant, even under conditions where humans (in some cases visual agnosia) may fail. These results support the interest of symbolic reasoning in image understanding.

Les graphes sont des structures mathématiques utilisées pour modéliser les relations par paires entre objets. Malgré leur structure simple, les graphes ont des applications dans divers domaines tels que l'informatique, la physique, la biologie et la sociologie. L'objectif principal de ce travail est de continuer l'étude des problèmes de coloration et de détection dans le cadre de classes de graphes fermées par sous-graphes induits (que nous appelons classes de graphes héréditaires).La première classe que nous considérons est graphes sans ISK4 - les graphes qui ne contiennent aucune subdivision de en tant que sous-graphe induit. Nous montrons que le nombre chromatique de cette classe est limité à 24, une amélioration considérable par rapport à la borne existant précédemment. Nous donnons également une bien meilleure limite dans le cas sans triangle. De plus, nous prouvons qu'il existe un algorithme de complexité pour détecter cette classe, ce qui répond à une question de Chudnovsky et al. et Lévêque et al.La deuxième classe que nous étudions est celle des graphes sans trou pair et sans étoile d’articulation. Cela est motivé par l'utilisation de la technique de décomposition pour résoudre certains problèmes d'optimisation. Nous garantissons la fonction χ-bounding optimale pour cette classe. Nous montrons que la classe a rank-width bornée, ce qui implique l'existence d'un algorithme de coloration en temps polynomial. Enfin, la coloration gloutonne connexe dans les graphes sans griffes est considérée. Une façon naturelle de colorier un graphe est d'avoir un ordre de ses sommets et d'affecter pour chaque sommet la première couleur disponible. Beaucoup de recherches ont été faites pour des ordres généraux. Cependant, nous connaissons très peu de choses sur la caractérisation des bons graphes par rapport aux ordres connexes. Un graphe est bon si pour chaque sous-graphe induit connexe de , chaque ordre connexe donne à une coloration optimale. Nous donnons la caractérisation complète de bons graphes sans griffes en termes de sous-graphes induits minimaux interdits.

Graphs are mathematical structures used to model pairwise relations between objects. Despite their simple structures, graphs have applications in various areas like computer science, physics, biology and sociology. The main focus of this work is to continue the study of the coloring and detecting problems in the setting of graph classes closed under taking induced subgraphs (which we call hereditary graph classes). The first class we consider is ISK4-free graphs - the graphs that do not contain any subdivision of K4 as an induced subgraph. We prove that the chromatic number of this class is bounded by 24, a huge improvement compared to the best-known bound. We also give a much better bound in the triangle-free case. Furthermore, we prove that there exists an O(n 9) algorithm for detecting this class, which answers a question by Chudnovsky et al. and Lévêque et al. The second class we study is even-hole-free graphs with no star cutset. This was motivated by the…

Dans cette thèse, nous nous intéressons à la recherche d’images similaires avec des descripteurs structurés par découpages d’images sur les graphes.Nous proposons une nouvelle approche appelée “bag-of-bags of words” (BBoW) pour la recherche d’images par le contenu (CBIR). Il s’agit d’une extension du modèle classique dit sac-de-mots (bag of words - BoW). Dans notre approche, une image est représentée par un graphe placé sur une grille régulière de pixels d’image. Les poids sur les arêtes dépendent de caractéristiques locales de couleur et texture. Le graphe est découpé en un nombre fixe de régions qui constituent une partition irrégulière de l’image. Enfin, chaque partition est représentée par sa propre signature suivant le même schéma que le BoW. Une image est donc décrite par un ensemble de signatures qui sont ensuite combinées pour la recherche d’images similaires dans une base de données. Contrairement aux méthodes existantes telles que Spatial Pyramid Matching (SPM), le modèle BBoW proposé ne repose pas sur l’hypothèse que des parties similaires d’une scène apparaissent toujours au même endroit dans des images d’une même catégorie. L’extension de cette méthode ` a une approche multi-échelle, appelée Irregular Pyramid Matching (IPM), est ´ également décrite. Les résultats montrent la qualité de notre approche lorsque les partitions obtenues sont stables au sein d’une même catégorie d’images. Une analyse statistique est menée pour définir concrètement la notion de partition stable.Nous donnons nos résultats sur des bases de données pour la reconnaissance d’objets, d’indexation et de recherche d’images par le contenu afin de montrer le caractère général de nos contributions

Image representation is a fundamental question for several computer vision tasks. The contributions discussed in this thesis extend the basic bag-of-words representations for the tasks of object recognition and image retrieval.In the present thesis, we are interested in image description by structural graph descriptors. We propose a model, named bag-of-bags of words (BBoW), to address the problems of object recognition (for object search by similarity), and especially Content-Based Image Retrieval (CBIR) from image databases. The proposed BBoW model, is an approach based on irregular pyramid partitions over the image. An image is first represented as a connected graph of local features on a regular grid of pixels. Irregular partitions (subgraphs) of the image are further built by using graph partitioning methods. Each subgraph in the partition is then represented by its own signature. The BBoW model with the aid of graphs, extends the classical bag-of-words (BoW) model by embedding color homogeneity and limited spatial information through irregular partitions of an image. Compared to existing methods for image retrieval, such as Spatial Pyramid Matching (SPM), the BBoW model does not assume that similar parts of a scene always appear at the same location in images of the same category. The extension of the proposed model to pyramid gives rise…