Correspondência inexata entre grafos
Resumo
Neste trabalho de mestrado estudamos o problema de correspondência inexata entre grafos que tem diversas variantes como descrevemos a seguir, com importantes aplicações, especialmente em processamento de imagens e visão computacional. Obtivemos resultados teóricos e práticos no mestrado: pudemos mostrar que uma variante do problema é NP-difícil mesmo quando os grafos da entrada são árvores. Através de formulações usando programação linear inteira e algoritmos de programação dinâmica pudemos resolver instâncias práticas de um problema de processamento de imagens com resultados promissores. Os resultados obtidos neste mestrado estão detalhados em dois artigos [Ferreira and Freire 2009, Freire et al. 2009].Referências
Arvind, V. and Kurur, P. P. (2002). Graph isomorphism is in spp. Proceedings of the 43rd Symposium on Foundations of Computer Science, pages 743–750.
Boeres, M. C. S. (2002). Heurísticas para reconhecimento de cenas por correspondência de grafos. PhD thesis, Universidade Federal do Rio de Janeiro.
Bunke, H. (2000). Graph matching: Theoretical foundations, algorithms, and applications. In Vision Interface, pages 82–88.
Cesar-Jr., R. M., Bengoetxea, E., Bloch, I., and Larrañaga, P. (2005). Inexact graph matching for model-based recognition: Evaluation and comparison of optimization algorithms. Pattern Recognition, 38:2099–2113.
Chopra, S. and Rao, M. R. (1993). The partition problem. Mathematical Programming, 59:87–115.
Duarte, A. R. (2004). Novas heurísticas e uma abordagem por programação inteira para um problema de correspondência inexata de grafos. Master’s thesis, Pontifícia Universidade Católica do Rio de Janeiro.
Ferreira, C. E. and Freire, A. S. (2009). The graph mapping problem: NP-hardness proof, formulations and algorithms. Submetido.
Freire, A. S. (2008). Correspondência inexata entre grafos. Master’s thesis, Instituto de Matemática e Estatística da Universidade de São Paulo.
Freire, A. S., Noma, A., Ferreira, C. E., and Cesar-Jr, R. M. (2009). Inexact graph matching: a heuristic based on spanning trees. Em preparação.
Garey, M. R. and Johnson, D. S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman.
Graciano, A. B. V. (2007). Rastreamento de objetos baseado em reconhecimento estrutural de padrões. Master’s thesis, Universidade de São Paulo - Instituto de Matemática e Estatística.
Hopcroft, J. E. and Wong, J. K. (1974). Linear time algorithm for isomorphism of planar graphs (preliminary report). In STOC ’74: Proceedings of the sixth annual ACM symposium on Theory of computing, pages 172–184, New York, NY, USA. ACM Press.
Jiang, X., Münger, A., and Bunke, H. (1999). Synthesis of representative graphical symbols by generalized median graph computation. In 3rd IAPR Workshop on Graphics Recognition.
Kuhn, H. W. (1955). The hungarian method for the assignment problem. Naval Research Logistics Quarterly, pages 83–97.
L. Lovász, M. D. P. (1986). Matching theory. Elsevier Science.
Lee, S. W., Kim, J. H., and Groen, F. C. A. (1990). Translation, rotation and scale invariant recognition of hand drawn symbols in schematic diagrams. Pattern Recognition and Artificial Intelligence.
Lu, S. W., Ren, Y., and Suen, C. Y. (1991). Hierarchical attributed graph representation and recognition of handwritten chinese characters. Pattern Recognition.
Luks, E. M. (1982). Isomorphism of graphs of bounded valence can be tested in polynomial time. Journal of Computer and System Sciences, pages 42–65.
Noma, A., Graciano, A. B. V., Consularo, L. A., Cesar-Jr, R. M., and Bloch, I. (2008). A new algorithm for interactive structural image segmentation. Technical report, IME-USP. arXiv:0805.1854v2 [cs.CV].
Rocha, J. and Pavlidis, T. (1994). A shape analysis model with applications to a character recognition system. IEEE Trans. PAMI.
Saarinen, K. (1994). Color image segmentation by a watershed algorithm and region adjacency graph processing. Image Processing, IEEE International Conference.
Tengan, E. (2002). Automorfismo de grafos. Master’s thesis, Universidade de São Paulo – Instituto de Matemática e Estatística.
Boeres, M. C. S. (2002). Heurísticas para reconhecimento de cenas por correspondência de grafos. PhD thesis, Universidade Federal do Rio de Janeiro.
Bunke, H. (2000). Graph matching: Theoretical foundations, algorithms, and applications. In Vision Interface, pages 82–88.
Cesar-Jr., R. M., Bengoetxea, E., Bloch, I., and Larrañaga, P. (2005). Inexact graph matching for model-based recognition: Evaluation and comparison of optimization algorithms. Pattern Recognition, 38:2099–2113.
Chopra, S. and Rao, M. R. (1993). The partition problem. Mathematical Programming, 59:87–115.
Duarte, A. R. (2004). Novas heurísticas e uma abordagem por programação inteira para um problema de correspondência inexata de grafos. Master’s thesis, Pontifícia Universidade Católica do Rio de Janeiro.
Ferreira, C. E. and Freire, A. S. (2009). The graph mapping problem: NP-hardness proof, formulations and algorithms. Submetido.
Freire, A. S. (2008). Correspondência inexata entre grafos. Master’s thesis, Instituto de Matemática e Estatística da Universidade de São Paulo.
Freire, A. S., Noma, A., Ferreira, C. E., and Cesar-Jr, R. M. (2009). Inexact graph matching: a heuristic based on spanning trees. Em preparação.
Garey, M. R. and Johnson, D. S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman.
Graciano, A. B. V. (2007). Rastreamento de objetos baseado em reconhecimento estrutural de padrões. Master’s thesis, Universidade de São Paulo - Instituto de Matemática e Estatística.
Hopcroft, J. E. and Wong, J. K. (1974). Linear time algorithm for isomorphism of planar graphs (preliminary report). In STOC ’74: Proceedings of the sixth annual ACM symposium on Theory of computing, pages 172–184, New York, NY, USA. ACM Press.
Jiang, X., Münger, A., and Bunke, H. (1999). Synthesis of representative graphical symbols by generalized median graph computation. In 3rd IAPR Workshop on Graphics Recognition.
Kuhn, H. W. (1955). The hungarian method for the assignment problem. Naval Research Logistics Quarterly, pages 83–97.
L. Lovász, M. D. P. (1986). Matching theory. Elsevier Science.
Lee, S. W., Kim, J. H., and Groen, F. C. A. (1990). Translation, rotation and scale invariant recognition of hand drawn symbols in schematic diagrams. Pattern Recognition and Artificial Intelligence.
Lu, S. W., Ren, Y., and Suen, C. Y. (1991). Hierarchical attributed graph representation and recognition of handwritten chinese characters. Pattern Recognition.
Luks, E. M. (1982). Isomorphism of graphs of bounded valence can be tested in polynomial time. Journal of Computer and System Sciences, pages 42–65.
Noma, A., Graciano, A. B. V., Consularo, L. A., Cesar-Jr, R. M., and Bloch, I. (2008). A new algorithm for interactive structural image segmentation. Technical report, IME-USP. arXiv:0805.1854v2 [cs.CV].
Rocha, J. and Pavlidis, T. (1994). A shape analysis model with applications to a character recognition system. IEEE Trans. PAMI.
Saarinen, K. (1994). Color image segmentation by a watershed algorithm and region adjacency graph processing. Image Processing, IEEE International Conference.
Tengan, E. (2002). Automorfismo de grafos. Master’s thesis, Universidade de São Paulo – Instituto de Matemática e Estatística.
Publicado
20/07/2009
Como Citar
FREIRE, Alexandre S.; FERREIRA, Carlos E..
Correspondência inexata entre grafos. In: CONCURSO DE TESES E DISSERTAÇÕES (CTD), 22. , 2009, Bento Gonçalves/RS.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2009
.
p. 49-56.
ISSN 2763-8820.
