Faculty of Informatics Vienna University of Technology Institute of Computer Aided Automation PRIP Home PRIP Home
Personal tools
You are here: Home Teaching Informatikpraktika Graph pyramids for tracking with structure

Graph pyramids for tracking with structure

Status des Praktikums: offen
Betreuer: Walter G. Kropatsch


Problem formulation




Graph pyramids are a very efficient structure for representing images and regions. Due to their logarithmic height, every cell/pixel of the input image can be accessed efficiently. They adapt to the input data and are translation and rotation invariant.

The building process is paralel and local (every vertex decides based only on its neighbors) and the amount of abstraction is gradually raised with each new level. (Vertices from higher levels, which characterize bigger regions, store the same amount of information as vertices from lower levels).



Task of Praktikum:

This Praktikum can focus on a number of topics, all concentrating on properties and application of graph pyramids in the context of image analysis and tracking. Example topics are:

  • The height of a pyramid is only one factor that will influence how fast the searched data is found. Another factor is the type of information that is stored in each vertex and used to abstract the input data. This can influence the number of vertices one has to visit to find the information searched for (e.g. whether the decision is clear, or one should try both paths in a backtracking manner). The purpose of the Praktikum is to implement and evaluate different abstraction options (e.g. for 2D coordinates of points, each vertex could contain the min&max of the coordinates, the radius and center of the circle, the ellipse, other?). The observed properties have to be described and characterized. Open problems should be identified.
  • Motivated by sentences like "Wich one is he? He is the one with the red shirt!", the problem is to address different vertices/regions in a pyramid, not based on their "coordinates" but based on the content/properties. This will allow identification of corresponding points/paths in pyramids build in a previous frame for an objects and a part of the pyramid build for the current frame. Studying the profile of the e.g. colour of the regions along a path from the "head" to the "hand" shoud help finding the corresponding path in the new pyramid, given the vertex corresponding to the head.
  • 3D objects are bounded by a 2D surface on which visible features are percieved (e.g. color, texture). The long term goal of this work is to create a pyramid of a closed surface in which "trackabale" features are represented. The representation should be derived automatically from observing an object in a video. The purpose of the Praktikum is to make simple proof of concept experiments, implement the required code, and study&evaluate the results. From a single image, the visible part of an object is extracted as a graph. This graph is closed on the invisble back side to create a closed surface, which is then smoothed in 3D and represented on the screen.


Schedule of the Praktikum:

* Literature study (Segmentation, Segmentation Hierarchies)
* Implementation.
* Tests and Benchmarks.


It is possible to extend this subject to a diploma thesis.