Image Analysis: Building and Rebuilding Graph Pyramids

Research project P 14445 Image Analysis: Building and Rebuilding Graph Pyramids Walter G. KROPATSCH 26.6.2000 Graph pyramids allow to represent images on multiple levels of scale and abstraction. The proposed project aims at the application of methods from combinatorial optimization to a model-based building and rebuilding of graph pyramids. The models provide objective functions for iterated parallel transformations, which are divided into three classes according to their use for * the building of higher and more abstract pyramid levels, * the relinking of the graph pyramid, * the adjustment of the attributes in the graph pyramid for the purpose of classification. The theoretical foundation of our approach is provided by recent developments in the theory of excluded minors, valuated matroids and relaxation labeling. Excluded minors are related to the notion of abstraction in graph pyramids, while valuated matrolds and relaxation form the basis for the optimization of the pyramid`s structure and classification respectively. In order to utilize all the information contained in the graph pyramid, we aim at extending the concept of excluded minors to excluded attributed embedded minors. We will also clarify the relations between the three classes of iterative parallel transformations, excluded (attributed embedded) minors, topological isomorphism of graphs and graph grammars. We will demonstrate the applicability of our results by * making a contribution to motion analysis and tracking, * developing a scale space approach for the representation of line images and * designing similarity measures for the retrieval in image databases