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ó. / 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. / 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.
| Identifer | oai:union.ndltd.org:TDX_UAB/oai:www.tdx.cat:10803/283518 |
| Date | 06 May 2014 |
| Creators | Dutta, Anjan |
| Contributors | Lladós Canet, Josep, Universitat Autònoma de Barcelona. Departament de Ciències de la Computació |
| Publisher | Universitat Autònoma de Barcelona |
| Source Sets | Universitat Autònoma de Barcelona |
| Language | English |
| Detected Language | Spanish |
| Type | info:eu-repo/semantics/doctoralThesis, info:eu-repo/semantics/publishedVersion |
| Format | 163 p., application/pdf |
| Source | TDX (Tesis Doctorals en Xarxa) |
| Rights | ADVERTIMENT. L'accés als continguts d'aquesta tesi doctoral i la seva utilització ha de respectar els drets de la persona autora. Pot ser utilitzada per a consulta o estudi personal, així com en activitats o materials d'investigació i docència en els termes establerts a l'art. 32 del Text Refós de la Llei de Propietat Intel·lectual (RDL 1/1996). Per altres utilitzacions es requereix l'autorització prèvia i expressa de la persona autora. En qualsevol cas, en la utilització dels seus continguts caldrà indicar de forma clara el nom i cognoms de la persona autora i el títol de la tesi doctoral. No s'autoritza la seva reproducció o altres formes d'explotació efectuades amb finalitats de lucre ni la seva comunicació pública des d'un lloc aliè al servei TDX. Tampoc s'autoritza la presentació del seu contingut en una finestra o marc aliè a TDX (framing). Aquesta reserva de drets afecta tant als continguts de la tesi com als seus resums i índexs., info:eu-repo/semantics/openAccess |
Page generated in 0.0043 seconds