Mastersthesis,
Design and Implementation of an Algorithm and Data Structure for Matching of Geometric Primitives in Visual Object Classification
Otto-von-Guericke University, Magdeburg, Germany, Internship Report, (April 2005)
Abstract
This report refers to work completed during my internship with the Mechatronics Research Group at the department of Mechanical and Manufacturing Engineering at the University of Melbourne, Australia from September 5th, 2003 until March 5th, 2004.
Recognition of three-dimensional objects in two-dimensional images is a key area of research in computer vision. One approach is to save multiple 2D views instead of a 3D object representation thus reducing the problem to a 2D to 2D matching problem. The Mechatronics Research Group is developing a novel system that focuses on artificial objects and further reduces the 2D views to symbolic descriptions. These descriptions are based on shape-primitives: ellipses, rectangles and isosceles triangles. Evidence insupport of a hypothesis for a certain object classification is collected through an active vision approach.
This work deals with the design and implementation of a data structure that is capable of holding such a symbolic representation and an algorithm for comparison and matching. The chosen symbolic representation of an object view is rotation-, scaling- and translation-invariant. For the comparison and matching of two object views a branch & bound algorithm based on problem specific heuristics is used. Furthermore, a GA-based generalization operator is proposed to reduce the number of object views in the system database.
Experiments show that the query performance scales linearly with the size of the database. For a database containing 10000 entries, a response time of less than a second is expected on an average system.
