2024-03-28T17:10:37Zhttps://www.tdx.cat/oai/requestoai:www.tdx.cat:10803/2835182023-06-09T09:40:55Zcom_10803_120col_10803_178
nam a 5i 4500
Subgraph mateling
Graph theory
Symbol spotting
Inexact Subgraph Matching Applied to Symbol Spotting in Graphical Documents
[Barcelona] :
Universitat Autònoma de Barcelona,
2014
Accés lliure
http://hdl.handle.net/10803/283518
cr |||||||||||
AAMMDDs2014 sp ||||fsm||||0|| 0 eng|c
9788449045639
Dutta, Anjan,
autor
1 recurs en línia (163 pàgines)
Tesi
Doctorat
Universitat Autònoma de Barcelona. Departament de Ciències de la Computació
2014
Universitat Autònoma de Barcelona. Departament de Ciències de la Computació
Tesis i dissertacions electròniques
Lladós Canet, Josep,
supervisor acadèmic
TDX
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ó.
a
ES-BaCBU
cat
rda
ES-BaCBU
text
txt
rdacontent
informàtic
c
rdamedia
recurs en línia
cr
rdacarrier