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

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