Abstract
An approach for the recognition of polymorphic patterns by subgraph isomorphism computation of parameterized graphs will be presented. Parameterized graphs (short: p-graphs) are extensions of undirected graphs by parameter vectors at the nodes and edges. We will define p-graphs and basic concepts of subgraph isomorphism computation for p-graphs. A bottom-up algorithm for p-subgraph isomorphism computation according to a given search graph and a template graph will be described. Since the enumeration of all induced p-subgraphs require tremendous effort, we will propose four pruning mechanisms in order to reduce the size of the search space. The computed subisomorphisms provide useful background knowledge for 3D building reconstruction in order to alleviate the occurring ambiguities, namely occlusions, inverse mapping, and noise. Using an extensive suburban scene it will be shown how polymorphic patterns can be recognized. Finally, we will estimate and discuss an upper bound complexity of the algorithm according to the application.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Braun, C., Kolbe, T. H., Lang, F., Schickler W., Steinhage, V., Cremers, A. B., Förstner W., Plümer, L.: Models for photogrammetric building reconstruction. Comput. Graphics 19, 109–118 (1995).
Duda, R. O., Hart, P. E.: Pattern classification and scene analysis. New York: J. Wiley, 1973.
Englert, R.: Inducing integrity constraints from knowledge bases. In: Proceedings of the 19th Annual German Conference on Artificial Intelligence (Wachsmuth, L., Rollinger, C. R., Brawer, W., eds.), pp. 77–88. Lecture Notes in Artificial Intelligence, Vol. 981. Berlin Heidelberg New York Tokyo: Springer, 1995.
Englert, R., Cremers, A. B.: Improving reconstruction of man-made objects from sensor images by machine learning. In: Proceedings of the 11th SPIE’s International Symposium on Aero-Sense: Integrating Photogrammetric Techniques with Scene Analysis and Machine Vision III (McKeown, D. H., McGlone, G., Jamet, O., eds.), pp. 263–274, SPIE Proceedings: Birmingham (U.K.), 1997.
Englert, R., Gulch, E.: A one-eye stereo system for the acquisition of complex 3D-bound structures. Geo Inf. Syst., 9, 16–21 (1996).
Englert, R., Seelmann-Eggebert, J.: P-subgraph isomorphism computation and upper bound complexity estimation. Technical Report IAI-TR-97-2, University of Bonn, Institute of Computer Science III, Bonn, Germany, 1997.
Grün, A., Kübier, O., Agouris, P. (eds.): Automatic extraction of man-made objects from aerial and space images. Basel: Birkhäuser, 1995.
Harary, F.: Graph Theory. Reading: Addison-Wesley, 1972.
Papadimitriou, C., Steiglitz, K.: Combinatorial optimization: algorithms and complexity. Englewood Cliffs: Prentice-Hall, 1982.
Ullmann, J. R.: An algorithm for subgraph isomorphism testing. J. ACM 23, 31–42 (1976).
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1998 Springer-Verlag Wien
About this paper
Cite this paper
Englert, R., Cremers, A.B., Seelmann-Eggebert, J. (1998). Recognition of Polymorphic Patterns in Parameterized Graphs for 3D Building Reconstruction. In: Jolion, JM., Kropatsch, W.G. (eds) Graph Based Representations in Pattern Recognition. Computing Supplement, vol 12. Springer, Vienna. https://doi.org/10.1007/978-3-7091-6487-7_2
Download citation
DOI: https://doi.org/10.1007/978-3-7091-6487-7_2
Publisher Name: Springer, Vienna
Print ISBN: 978-3-211-83121-2
Online ISBN: 978-3-7091-6487-7
eBook Packages: Springer Book Archive