Interpretació de dibuixos lineals fets a mà alçada mitjançant isomorfisme entre subgrafs i transformació de Hough

CVC Tecnical Report #10

Josep Lladós

Centre de Visió per Computador - Edifici O - Universitat Autònoma de Barcelona.

08193 Bellaterra (Barcelona)

e-mail: josep@cvc.uab.es

Abstract:

L'anàlisi de documents té com a objectiu la interpretació automàtica de documents impresos sobre paper, amb la finalitat d'obtenir una descripció simbòlica d'aquests, que permeti el seu emmagatzemament i posterior tractament computacional. Les tècniques basades en grafs relacionals d'atributs permeten representar de manera compacta la informació continguda en dibuixos lineals conservant la informació geomètrica i topològica que hi apareix. La interpretació posterior del document es pot fer a partir de la identificació de certes estructures dins del graf, és a dir, aplicant tècniques d'isomorfisme entre grafs reconeixent un conjunt de grafs model com a subgrafs del graf que representa el dibuix lineal d'entrada. Actualment, és una qüestió oberta saber si el problema de l'isomorfisme entre grafs pertany a les classes de complexitat P o NP. Tots els algorismes desenvolupats fins al moment per al cas general d'isomorfisme entre grafs requereixen, en el cas pitjor, un temps exponencial. El problema de l'isomorfisme entre subgrafs si que s'ha pogut classificar com a problema NP-complet. Per tant, no existeix un algorisme que garanteixi trobar la solució en un temps polinomial, la qual cosa fa que la resolució computacional sigui inviable si el tamany dels grafs és gran. Amb la finalitat de resoldre aquest problema s'ha proposat diferents criteris heurístics, depenents del domini en el que s'estigui treballant, per a accelerar el procés d'isomorfisme. En aquest informe es descriu un d'aquests criteris utilitzat com a part d'un sistema d'interpretació de plànols fets a mà alçada dins d'un àmbit d'arquitectura. Concretament, es proposa utilitzar tècniques basades en la transformació de Hough amb l'objectiu de detectar regions del document texturades en base a un conjunt de línies paral·leles. La detecció d'aquestes regions permet d'eliminar del graf que representa el document a reconèixer un gran nombre d'arestes i vèrtexs abans d'aplicar la correspondència amb els models. La detecció d'aquestes regions texturades permet també definir certes zones d'interès en les quals buscar els models de manera que l'isomorfisme no s'hagi d'aplicar a tot el graf.
 


Get a postscript version of the paper