Faculty of Informatics Vienna University of Technology Institute of Computer Aided Automation PRIP Home PRIP Home
Personal tools
You are here: Home Research Current Projects Cognitive Vision Pyramidal Representations

Pyramidal Representations

Regular pyramids are well known tools for analyzing images and signals. Usually, researchers are interested in regular pyramids, which are simpler to build and to analyze. However, those pyramids are not invariant under invertible geometric transformations and many request done on those structures (e.g. adjacency request) cannot be dealt easily.

Irregular pyramids have been introduced to solve those discrepancies. One can see irregular pyramids as sequences of partitions deduced from one another by merging adjacent features. Those pyramids offer promising specter of applications, especially in cognitive vision.

Topological Pyramid Structures

The search for efficient data structures encoding pyramids is vital, as the complexity of the data structure is a limiting factor to the applicability of irregular pyramids in applications. More than data structures themselves, efficient (parallel) algorithms are always needed to compute and use pyramidal representations.

combinatorialPyramid.jpg
A combinatorial pyramid and its implicit encoding

Abstraction & Representation

Irregular pyramids are relevant for different purposes. Pyramids offer a natural way to group low-level objects and primitives into higher level abstractions. Such an approach would lead to pyramidal structure like the one depicted on the following figure.


Abstraction pyramid example
An example of an abstraction pyramid

The first level of the pyramid consists in a description of the geometry of the underlying image (here a simplified image of an house). In the second level of the pyramid, contours are grouped in such a way that they represent simple boundaries of connected objects (like the door, the roof, the background, ..., of the house). On a higher level, adjacent objects are grouped in order to represent compound abstract objects (like the house in our example).

Abstraction encoding poses two obvious problems:

  • What are the models that can benefit from such an approach ? Where are the drawbacks ?
  • How to compute such a description ?

Toward Genericity Encoding

We have shown that pyramid structures appear naturally when comparing several topological partitions. The idea is to produce successively the "union" of "intersection" of partitions. The partitions obtained this way form a pyramid we baptized redundancy pyramid.

An example illustrating the redundancy pyramid principle can be seen on the following figures.

cube1.jpg cube2.jpg cube3.jpg 
0000_all_levels.jpg  0001_all_levels.jpg  0002_all_levels.jpg
 

The previous figures show three cubes (on the top of the figure) with their associated partitions (on the bottom of the figure). The redundancy pyramid is displayed level by level on the following figure.

level0.jpg  level1.jpg  level2.jpg 
Level 1 Level 2 Level 3

The redundancy pyramid has been successfully used for segmentation comparison and background segmentation on an image sequence. It is also a powerful tool when one wants to build generic topological model from scratch. The level of the pyramid indicate how redundant is a particular partition on the analyzed partition, hence giving a hint on how generic is a particular partition for describing a class of objects.

External Collaborations

  1. Prof. Luc Brun, LERI, Université de Reims, France
  2. Prof. Pascal Lienhardt, SIC, Université de Poitiers, France

Related Bibliography

  1. Luc Brun and Walter G. Kropatsch: Construction of Combinatorial Pyramids; Graph Based Representations in Pattern Recognition, Lecture Notes in Computer Science vol. 2726, July 2003
  2. Yll Haxhimusa, Roland Glantz and Walter G. Kropatsch, Constructing Stochastic Pyramids by MIDES - Maximal Independent Directed Edge Set, Graph Based Representations in Pattern Recognition, Lecture Notes in Computer Science vol. 2726, July 2003
  3. Y.Kesselman and S.Dickinson. Generic model abstraction from examples. In CVPR 2001. IEEE CS Press, 2001.
  4. Marchadier Jocelyn, Luc Brun, Walter Kropatsch, Rooted Kernels and Labeled Combinatorial Pyramids, CVWW 2004, page 59-68, 2004.
  5. Marcello Pelillo, Kaleem Siddiqi and Steven W. Zucker, Matching Hierarchical Structures Using Association Graphs, IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 21(11), November 1999.