Carola Wenk

Geometrische Mustererkennung in höheren Dimensionen

Betreuer: Prof. Dr. Helmut Alt
Abschluss: PhD
Abgabedatum: 16.12.2002
Homepage des Autors:


The comparison of geometric shapes is a task which naturally arises in many applications, such as in computer vision, computer aided design, robotics, medical imaging, etc. Usually geometric shapes are represented by a number of simple objects (sites) that either describe the boundary of the shape, or the whole shape itself. Sites are often chosen to be linear objects, such as line segments, triangles, or simplices in general, since linear objects are easier to handle in algorithms. But sometimes also patches of algebraic curves or surfaces, such as circular arcs or portions of spheres or cylinders are of interest. In order to compare two shapes we need to have a notion of similarity or dissimilarity, which arises from the desired application. There is a large variety of different similarity measures. Popular similarity notions are, for example, the Hausdorff distance, the area of symmetric difference, or especially for curves the turn-angle distance, or the Fréchet distance. The application usually supplies a distance measure, and furthermore a set of allowed transformations, and the task is to find a transformation that, when applied to the first object, minimizes the distance to the second one. Typical transformation classes are translations, rotations, and rigid motions (which are combinations of translations and rotations).

The contribution of this thesis consists of several algorithms for matching simplicial shapes in dimensions d >= 2. The shapes are either represented as sets of simplicial objects or as polygonal curves with a given parametrization. The considered distance measures are mainly the Hausdorff distance and the Fréchet distance. In the literature most matching algorithms either attack two-dimensional problems, or consider finite point sets in higher dimensions. In the first half of this thesis we present results for the Hausdorff distance in d >= 2dimensions under translations, for a rather general notion of simplicial shapes, as well as for some special shape classes which allow to speed up the computations. In the second half of this thesis we investigate the Fréchet distance for polygonal curves. The Fréchet distance is a natural distance measure for curves, but has not been investigated much in the literature. We present the first algorithms to optimize the Fréchet distance under various transformation classes for polygonal curves in arbitrary dimensions. In the last chapter we consider a partial matching variant in which a geometric graph and another curve are given, and we show how to find a polygonal path in the graph which minimizes the Fréchet distance to the curve.