The doctoral dissertations of the former Helsinki University of Technology (TKK) and Aalto University Schools of Technology (CHEM, ELEC, ENG, SCI) published in electronic format are available in the electronic publications archive of Aalto University - Aaltodoc.

Attribute Trees as Adaptive Object Models in Image Analysis

Markus Peura

Dissertation for the degree of Doctor of Science in Technology to be presented with due permission of the Department of Computer Science and Engineering for public examination and debate in Auditorium T2 at Helsinki University of Technology (Espoo, Finland) on the 23rd of February, 2001, at 12 o'clock noon.

Overview in PDF format (ISBN 951-22-5363-1)   [1904 KB]
Dissertation is also available in print (ISBN 951-666-567-5)


This thesis focuses on the analysis of irregular hierarchical visual objects. The main approach involves modelling the objects as unordered attribute trees. A tree presents the overall organization, or topology, of an object, while the vertex attributes describe further visual properties such as intensity, color, or size. Techniques for extracting, matching, comparing, and interpolating attribute trees are presented, principally aiming at systems that can learn to recognize objects. Analysis of weather radar images has been the pilot application for this study, but the main ideas are applicable in structural pattern recognition more generally.

The central original contribution of this thesis is the Self-Organizing Map of Attribute Trees (SOM-AT) which demonstrates how the proposed tree processing techniques - tree indexing, matching, distance functions, and mixtures - can be embedded in a learning system; the SOM-AT is a variant of the Self-Organizing Map (SOM), the neural network model invented by Prof. Teuvo Kohonen. The SOM is especially suited to visualizing distributions of objects, classifying objects and monitoring changes in objects. Hence, the SOM-AT can be applied in the respective tasks involving hierarchical objects. More generally, the proposed ideas are applicable in learning systems involving comparisons and interpolations of trees.

The suggested heuristic index-based tree matching scheme is another independent contribution. The basic idea of the heuristic is to divide trees to subtrees and match the subtrees recursively by means of topological indices. Given two attribute trees, the larger of which has N vertices, and the maximal child count (out-degree) is D vertices, the complexity of the scheme is only O(N log D) operations while exact matching schemes seem to have at least quadratic complexity: O(N2.5) operations in checking isomorphisms and O(N3) operations in matching attribute trees. The proposed scheme is efficient also in terms of its "hit rate", the number of successfully matched vertices. In matching two random trees of N <= 10 vertices, the number of heuristically matched vertices is on average 99% of the optimum, and the accuracy for trees of N <= 500 vertices is still above 90%.

The feasibility of the proposed techniques is demonstrated by database querying, monitoring, and clustering of weather radar images. A related tracking scheme is outlined as well. In addition to weather radar images, a case study is presented on Northern light (Aurora Borealis) images. Due to the generic approach, there are also medical and geographical applications in view.

This thesis consists of an overview and of the following 7 publications:

  1. Jukka Iivarinen, Markus Peura, Jaakko Särelä, and Ari Visa. Comparison of combined shape descriptors for irregular objects. In Adrian F. Clark, editor, 8th British Machine Vision Conference (BMVC'97), volume 2, pages 430-439, September 1997.
  2. Markus Peura. A statistical classification method for hierarchical irregular objects. In Alberto del Bimbo, editor, Image Analysis and Processing - 9th International Conference, (ICIAP'97), volume 1310 of Lecture Notes in Computer Science, pages 604-611. Springer, September 1997.
  3. Markus Peura. The self-organizing map of trees. Neural Processing Letters, 8(2):155-162, October 1998.
  4. Markus Peura, Elena Saltikoff, and Mikko Syrjäsuo. Image analysis by means of attribute trees - remote sensing applications. In IEEE 99 International Geoscience and Remote Sensing Symposium (IGARSS'99), pages 696-698, June-July 1999.
  5. Markus Peura. Classifying, monitoring and tracking precipitation cells by means of attribute trees. In 29th International Conference on Radar Meteorology, pages 86-89. American Meteorological Society, July 1999.
  6. Markus Peura. The self-organizing map of attribute trees. In International Conference on Artificial Neural Networks (ICANN99), pages 168-173. IEE, September 1999.
  7. Markus Peura. Attribute trees in image analysis - heuristic matching and learning techniques. In 10th International Conference on Image Analysis and Processing (ICIAP'99), pages 1160-1165. IEEE Computer Society, September 1999.

Keywords: image analysis, trees, weighted trees, attribute trees, tree matching, unordered tree matching, heuristic tree matching, self-organizing map

This publication is copyrighted. You may download, display and print it for Your own personal use. Commercial use is prohibited.

© 2001 Helsinki University of Technology

Last update 2011-05-26