[en] There is a resurgence in the use of structural approaches in the usual object recognition and retrieval problem. Graph theory, in particular, graph matching plays a relevant role in that. Specifically, the detection of an object (or a part of that) in an image in terms of structural features can be formulated as a subgraph matching. Subgraph matching is a challenging task. Specially due to the presence of outliers most of the graph matching algorithms do not perform well in subgraph matching scenario. Also exact subgraph isomorphism has proven to be an NP-complete problem. So naturally, in graph matching community, there are lot of efiorts addressing the problem of subgraph matching within suboptimal bound. Most of them work with approximate algorithms that try to get an inexact solution in approximate way. In addition, usual recognition must cope with distortion. Inexact graph matching consists in finding the best isomorphism under a similarity measure. Theoretically this thesis proposes algorithms for solving subgraph matching in an approximate and inexact way. We consider the symbol spotting problem on graphical documents or line drawings from application point of view. This is a well known problem in the graphics recognition community. It can be further applied for indexing and classification of documents based on their contents. The structural nature of this kind of documents easily motivates one for giving a graph based representation. So the symbol spotting problem on graphical documents can be considered as a subgraph matching problem. The main challenges in this application domain is the noise and distortions that might come during the usage, digitalization and raster to vector conversion of those documents. Apart from that computer vision nowadays is not any more confined within a limited number of images. So dealing a huge number of images with graph based method is a further challenge. In this thesis, on one hand, we have worked on eficient and robust graph representation to cope with the noise and distortions coming from documents. On the other hand, we have worked on difierent graph based methods and framework to solve the subgraph matching problem in a better approximated way, which can also deal with considerable number of images. Firstly, we propose a symbol spotting method by hashing serialized subgraphs. Graph serialization allows to create factorized substructures such as graph paths, which can be organized in hash tables depending on the structural similarities of the serialized subgraphs. The involvement of hashing techniques helps to reduce the search space substantially and speeds up the spotting procedure. Secondly, we introduce contextual similarities based on the walk based propagation on tensor product graph. These contextual similarities involve higher order information and more reliable than pairwise similarities. We use these higher order similarities to formulate subgraph matching as a node and edge selection problem in the tensor product graph. Thirdly, we propose near convex grouping to form near convex region adjacency graph which eliminates the limitations of traditional region adjacency graph representation for graphic recognition. Fourthly, we propose a hierarchical graph representation by simplifying/correcting the structural errors to create a hierarchical graph of the base graph. Later these hierarchical graph structures are matched with some graph matching methods. Apart from that, in this thesis we have provided an overall experimental comparison of all the methods and some of the state-of-the-art methods. Furthermore, some dataset models have also been proposed.

[es] Existe un resurgimiento en el uso de métodos estructurales para el problema de reconocimiento y recuperación por contenido de objetos en imágenes. La teoría de grafos, en particular la puesta en correspondencia de grafos (graph matching) juega un papel relevante en ello. Así, la detección de un objeto (o una parte) en una imagen se puede formular como un emparejamiento de subgrafos en términos de características estructurals. El matching de subgrafos es una tarea difícil. Especialmente debido a la presencia de valores atípicos, muchos de los algoritmos existentes para el matching de grafos tienen dificultades en el escenario de matching de subgrafos. Además, el apareamiento de subgrafos de manera exacta ha demostrado ser una problema NP-completo . Así que hay una actividad intensa en la comunidad científica para proporcionar algoritmos eficaces para abordar el problema de manera suboptimal. La mayoría de ellos trabajan con algoritmos aproximados que tratan de obtener una solución inexacta en forma aproximada. Además, el reconocimiento habitualmente debe hacer frente a la distorsión. El emparejamiento de subgrafos de manera inexacta consiste en encontrar el mejor isomorfismo bajo una medida de similitud. Desde el punto de vista teórico, esta tesis propone algoritmos para la solución al problema del emparejamiento de subgrafos de manera aproximada e inexacta. Desde un punto de vista aplicado, esta tesis trata el problema de la detección de símbolos en imágenes de documentos gráficos o dibujos lineales (symbol spotting). Este es un problema conocido en la comunidad de reconocimiento de gráficos. Se puede aplicar para la indexación y clasificación de documentos sobre la base de sus contenidos. El carácter estructural de este tipo de documentos motiva de forma natural la utilización de una representación de grafos. Así el problema de detectar símbolos en documentos gráficos puede ser considerado como un problema de apareamiento de subgrafos. Los principales desafiós en este dominio de aplicación son el ruido y las distorsiones que provienen del uso, la digitalización y la conversión de raster a vectores de estos documentos. Aparte de que la visión por computador en la actualidad no limita las aplicaciones a un número limitado de imágenes. Así que el paso a la escala y tratar un gran número de imágenes en el reconocimiento de documentos gráficos es otro desafió. En esta tesis, por una parte, hemos trabajado en representaciones de grafos efi- cientes y robustas para solucionar el ruido y las distorsiones de los documentos. Por otra parte, hemos trabajado en diferentes métodos de matching de grafos para resolver el problema del emparejamiento inexacto de subgrafos, que también sea escalable ante un considerable número de imágenes. En primer lugar, se propone un método para de tectar símbolos mediante funciones de hash de subgrafos serializados. La organización del grafo una vez factorizado en subestructuras comunes, que se pueden organizar en tablas hash en función de las similitudes estructurales, y la serialización de las mismas en estructuras unidimensionales como caminos, son dos aportaciones de esta parte de la tesis. El uso de las técnicas de hashing ayuda a reducir sustancialmente el espacio de búsqueda y acelera el procedimiento de la detección. En segundo lugar, presentamos mecanismos de similitud contextual basadas en la propagación basada en caminos (walks) sobre el grafo producto (tensor product graph). Estas similitudes contextuales implican más información de orden superior y más áble que las similitudes locales. Utilizamos estas similitudes de orden superior para formular el apareamiento de subgrafos como una problema de selección de nodos y aristas al grafo producto. En tercer lugar, proponemos agrupamiento perceptual basado en convexidades para formar regiones casi convexas que elimina las limitaciones de la representación tradicional de los grafos de regiones para el reconocimiento gráfico. En cuarto lugar, se propone una representación de grafo jerárquico mediante la simplificación/corrección de los errores estructurales para crear un grafo jerárquico del grafo de base. Estos estructuras de grafos jerárquicos integran en métodos de emparejamiento de grafos. Aparte de esto, en esta tesis hemos proporcionado una comparación experimental general de todos los métodos y algunos de los métodos del estado del arte. Además, también se han proporcionado bases de datos de experimentación.