Efficient Subgraph Isomorphism with“A Priori” Knowledge: Application to 3D Reconstruction of Buildings for Cartography

摘要

In this paper, a procedure which computes error-correcting subgraph isomorphisms is proposed in order to be able to take into account some external information. When matching a model graph and a data graph, if the correspondance between vertices of the model graph and some vertices of the data graph are known “a priori”, the procedure is able to integrate this knowledge in an efficient way. The efficiency of the method is obtained in the first step of the procedure, namely, by the recursive decomposition of the model graph into subgraphs. During this step, these external information are propagated as far as possible thanks to a new procedure which makes the graphs able to share them. Since the data structure is now able to fully integrate the external information, the matching step itself becomes more efficient. The theoretical aspects of this methodology are presented, as well as practical experiments on real images. The procedure is tested in the field of 3-D building reconstruction for cartographic issues, where it allows to match model graphs partially, and then perform full matches.