La reconnaissance de formes s'intéresse à la détection automatique de motifs dans des données d'entrée, afin de pouvoir, par exemple, les classer en catégories. La matière première de ces techniques est bien souvent l'image numérique. Cette dernière, dans sa forme la plus courante, est codée sous la forme d'une matrice de pixels. Néanmoins, la question du développement de représentations plus riches se pose. Ainsi, la structuration de l'information contenue dans l'image devrait permettre la mise en évidence des différents objets représentés, et des liens les unissant. C'est pourquoi nous proposons de modéliser les images numériques sous forme de graphes, pour leur richesse et expressivité d'une part, et pour exploiter les résultats de la théorie des graphes en reconnaissance de formes d'autre part. Nous développons pour cela une méthode d'extraction de graphes plans à partir d'images, basée sur le respect de la sémantique. Nous montrons que nous pouvons, étant donné un graphe, reconstruire avec perte limitée l'image d'origine. Par la suite, nous introduisons les graphes plans à trous, graphes dont les faces peuvent être visibles ou invisibles. Leur justification trouve sa place dans la recherche de motifs notamment, pour laquelle les éléments constituant l'arrière-plan d'une image ne doivent pas être retrouvés. En dirigeant notre attention sur la planarité de ces graphes, nous proposons des algorithmes polynomiaux d'isomorphisme de graphes plans et de motifs ; nous traitons également leur équivalence, qui se trouve être un isomorphisme aux faces invisibles près / Pattern recognition deals with automatically detecting patterns in input values, so as to, for example, classify them into categories. Digital images often constitute the raw material for these applications. The term digital images usually refers to bitmap images, i. e. images represented as matrices of pixels. However, alternative representations can be considered. Thus, structuring the information contained in the image should underline the different objects depected in the image, as well as the links existing between them. This is the reason why we propose to use graph-based representations. Indeed, on the one hand, graphs are complex data structures with important expressive power and, on the other hand, we should benefit from graphs theory result and apply them to pattern recognition tasks. To this extent, we develop a method for extracting semantically well- founded plane graphs from images. We show that it is possible to rebuild the original image from this kind of graphs, with limited loss. Furthermore, we introduce open plane graphs, i. e. graphs whose faces can be visible or invisible. These graphs are useful in pattern recognition, when it is needed to search for patterns independently of the background. Focusing on the planarity of these graphs, we propose polynomial algorithms for plane graphs isomorphism and subgraphs isomorphism. We also address the equivalence issue, which is an isomorphism variant not taking into account visible faces

La reconnaissance de formes s'intéresse à la détection automatique de motifs dans des données d'entrée, afin de pouvoir, par exemple, les classer en catégories. La matière première de ces techniques est bien souvent l'image numérique. Cette dernière, dans sa forme la plus courante, est codée sous la forme d'une matrice de pixels. Néanmoins, la question du développement de représentations plus riches se pose. Ainsi, la structuration de l'information contenue dans l'image devrait permettre la mise en évidence des différents objets représentés, et des liens les unissant. C'est pourquoi nous proposons de modéliser les images numériques sous forme de graphes, pour leur richesse et expressivité d'une part, et pour exploiter les résultats de la théorie des graphes en reconnaissance de formes d'autre part. Nous développons pour cela une méthode d'extraction de graphes plans à partir d'images, basée sur le respect de la sémantique. Nous montrons que nous pouvons, étant donné un graphe, reconstruire avec perte limitée l'image d'origine. Par la suite, nous introduisons les graphes plans à trous, graphes dont les faces peuvent être visibles ou invisibles. Leur justification trouve sa place dans la recherche de motifs notamment, pour laquelle les éléments constituant l'arrière-plan d'une image ne doivent pas être retrouvés. En dirigeant notre attention sur la planarité de ces graphes, nous proposons des algorithmes polynomiaux d'isomorphisme de graphes plans et de motifs ; nous traitons également leur équivalence, qui se trouve être un isomorphisme aux faces invisibles près

La reconnaissance de formes s'intéresse à la détection automatique de motifs dans des données d'entrée, afin de pouvoir, par exemple, les classer en catégories. La matière première de ces techniques est bien souvent l'image numérique. Cette dernière, dans sa forme la plus courante, est codée sous la forme d'une matrice de pixels. Néanmoins, la question du développement de représentations plus riches se pose. Ainsi, la structuration de l'information contenue dans l'image devrait permettre la mise en évidence des différents objets représentés, et des liens les unissant. C'est pourquoi nous proposons de modéliser les images numériques sous forme de graphes, pour leur richesse et expressivité d'une part, et pour exploiter les résultats de la théorie des graphes en reconnaissance de formes d'autre part. Nous développons pour cela une méthode d'extraction de graphes plans à partir d'images, basée sur le respect de la sémantique. Nous montrons que nous pouvons, étant donné un graphe, reconstruire avec perte limitée l'image d'origine. Par la suite, nous introduisons les graphes plans à trous, graphes dont les faces peuvent être visibles ou invisibles. Leur justification trouve sa place dans la recherche de motifs notamment, pour laquelle les éléments constituant l'arrière plan d'une image ne doivent pas être retrouvés. En dirigeant notre attention sur la planarité de ces graphes, nous proposons des algorithmes polynomiaux d'isomorphisme de graphes plans et de motifs ; nous traitons également leur équivalence, qui se trouve être un isomorphisme aux faces invisibles près.

Le problème d’´équivalence de code joue un rôle important dans la théorie de code et la cryptographie basée sur le code. Cela est dû à son importance dans la classification des codes ainsi que dans la construction et la cryptanalyse des cryptosystèmes à base de codes. Il est également lié à un problème ouvert d’isomorphisme de graphes, un problème bien connu dans le domaine de la théorie de la complexité. Nous prouvons pour les codes ayant un hull trivial qu’il existe une réduction polynomiale de l’équivalence par permutation de codes à l’isomorphisme de graphes. Cela montre que cette sous-classe d’équivalence de permutation n’est pas plus dure que l’isomorphisme de graphes. Nous introduisons une nouvelle méthode pour résoudre le problème d’équivalence de code. Nous développons des approches algébriques pour résoudre le problème dans ses deux versions : en permutation et en diagonale. Nous construisons un système algébrique en établissant des relations entre les matrices génératrices et les matrices de parité des codes équivalents. Nous nous retrouvons avecun système plusieurs variables d’équations linéaires et quadratiques qui peut être résolu en utilisant des outils algébriques tels que les bases de Groebner et les techniques associées. Il est possible en théorie de résoudre l’équivalence de code avec des techniques utilisant des bases de Groebner. Cependant, le calcul en pratique devient complexe à mesure que la longueur du code augmente. Nous avons introduit plusieurs améliorations telles que la linéarisation par bloc et l’action de Frobenius. En utilisant ces techniques, nous identifions de nombreux cas où le problème d’équivalence de permutation peut être résolu efficacement. Notre méthode d’équivalence diagonale résout efficacement le problème dans les corps de petites tailles, à savoir F3 et F4. L’augmentation de la taille du corps entraîne une augmentation du nombre de variables dans notre système algébrique, ce qui le rend difficile à résoudre. Nous nous intéressons enfin au problème d’isomorphisme de graphes en considérant un système algébrique quadratique pour l’isomorphisme de graphes. Pour des instances tirées aléatoirement, le système possède des propriétés intéressantes en termes de rang de la partie linéaire et du nombre de variables. Nousrésolvons efficacement le problème d’isomorphisme de graphes pour des graphes aléatoires avec un grand nombre de sommets, et également pour certains graphes réguliers tels que ceux de Petersen, Cubical et Wagner.123 / Code equivalence problem plays an important role in coding theory and code based cryptography.That is due to its significance in classification of codes and also construction and cryptanalysis of code based cryptosystems. It is also related to the long standing problem of graph isomorphism, a well-known problem in the world of complexity theory. We introduce new method for solving code equivalence problem. We develop algebraic approaches to solve the problem in its permutation and diagonal versions. We build algebraic system by establishing relations between generator matrices and parity check matrices of the equivalent codes. We end up with system of multivariables of linear and quadratic equations which can be solved using algebraic tools such as Groebner basis and related techniques. By using Groebner basis techniques we can solve the code equivalence but the computation becomes complex as the length of the code increases. We introduced several improvements such as block linearization and Frobenius action. Using these techniques we identify many cases where permutation equivalence problem can be solved efficiently. Our method for diagonal equivalence solves the problem efficiently in small fields, namely F3 and F4. The increase in the field size results in an increase in the number of variables in our algebraic system which makes it difficult to solve. We introduce a new reduction from permutation code equivalence when the hull is trivial to graph isomorphism. This shows that this subclass of permutation equivalence is not harder than graph isomorphism.Using this reduction we obtain an algebraic system for graph isomorphism with interesting properties in terms of the rank of the linear part and the number of variables. We solve the graph isomorphism problem efficiently for random graphs with large number of vertices and also for some regular graphs such as Petersen, Cubical and Wagner Graphs.