[ca] Existeix un ressorgiment en l'ús de mètodes estructurals per al problema de reconeixement i recuperació per contingut d'objectes en imatges. La teoria de grafs, en particular, la posada en correspondència de grafs (graph matching) juga un paper rellevant en aixó. En particular, la detecció d'un objecte (o una part) en una imatge es pot formular com un aparellament de subgrafs en termes de característiques estructurals. El matching de subgrafs és una tasca difícil. Especialment a causa de la presència de valors atípics, molts dels algoritmes existents per al matching de grafs tenen di- ficultats en l'escenari de matching de subgrafs. A més, l'aparellament de subgrafs de manera exacta s'ha demostrat ser una problema NP-complet. Així que hi ha una activitat intensa a la comunitat cientíca per proporcionar algoritmes eficaços per abordar el problema de manera suboptimal. La majoria d'ells treballen amb algoritmes aproximats que tracten d'obtenir una solució inexacta en forma aproximada. A més, el reconeixement habitualment ha de fer front a la distorsió. L'aparellament de subgrafs de manera inexacta consisteix a trobar el millor isomorfisme sota una mesura de similitud. Des del punt de vista teòric, aquesta tesi proposa algoritmes per a la solució al problema de l'aparellament de subgrafs de manera aproximada i inexacta. Des d'un punt de vista aplicat, aquesta tesi tracta el problema de la detecció de símbols en imatges de documents gràfics o dibuixos lineals (symbol spotting). Aquest és un problema ben conegut a la comunitat de reconeixement de gràfics. Es pot aplicar per a la indexació i classificació de documents sobre la base dels seus continguts. El caràcter estructural d'aquest tipus de documents motiva de forma natural la utilització d'una representació de grafs. Així el problema de detectar símbols en documents gràfics pot ser considerat com un problema d'aparellament de subgrafs. Els principals desaàments en aquest domini d'aplicació són el soroll i les distorsions que provenen de l'ús, la digitalització i la conversió de ràster a vectors d'aquests documents. A part que la visió per computador en l'actualitat no limita les aplicacions a un nombre limitat d'imatges. Així que el pas a l'escala i tractar un gran nombre d'imatges en el reconeixement de documents gràfics és un altre desaàment. En aquesta tesi, d'una banda, hem treballat en representacions de grafs eficients i robustes per solucionar el soroll i les distorsions dels documents. D'altra banda, hem treballat en diferents mètodes de matching de grafs per resoldre el problema de l'aparellament inexacte de subgrafs, que també sigui escalable davant d'un considerable nombre d'imatges. En primer lloc, es proposa un mètode per a detectar símbols mitjançant funcions de hash de subgrafs serialitzats. L'organització del graf una vegada factoritzat en subestructures comunes, que es poden organitzar en taules hash en funció de les similituds estructurals, i la serialització de les mateixes en estructures unidimensionals com ara camins, són dues aportacions d'aquesta part de la tesi. L'ús de les tècniques de hashing ajuda a reduir substancialment l'espai de cerca i accelera el procediment de la detecció. En segon lloc, presentem mecanismes de similitud contextual basades en la propagació basada en camins (walks) sobre el graf producte (tensor product graph). Aquestes similituds contextuals impliquen més informació d'ordre superior i més àble que les similituds locals. Utilitzem aquestes similituds d'ordre superior per formular l'aparellament de subgrafs com una problema de selecció de nodes i arestes al graf producte. En tercer lloc, proposem agrupament perceptual basat en convexitats per formar regions quasi convexes que elimina les limitacions de la representació tradicional dels grafs de regions per al reconeixement gràfic. En quart lloc, es proposa una representació de graf jeràrquic mitjançant la simplificació/correcció dels errors estructurals per crear un graf jeràrquic del graf de base. Aquests estructures de grafs jeràrquics s'integren en mètodes d'aparellament de grafs. A part d'aixó, en aquesta tesi hem proporcionat una comparació experimental general de tots els mètodes i alguns dels mètodes de l'estat de l'art. A més, també s'han proporcionat bases de dades d'experimentació.

[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.