SHAME - Shape Matching Environment

Contact: Remco Veltkamp

Terms of use
General
Polygonal Approximation
Polyline Matching
Evolutionary Algorithms in Shape Matching
Plans
People
Acknowledgement


Terms of use

General

The state-of-the-art results in shape matching with computational geometry techniques are all very recent. Unfortunately, many useful shape matching algorithms have not found their way into practice yet, because these algorithms are inherently complex. Also, most theoretical papers assume arithmetic over real numbers and ignore degenerate cases, while in practice often floating point arithmetic is used, and input data is often degenerate by construction. Therefore, we are developing a state-of-the-art shape matching environment (SHAME) of currently available algorithms.

The SHAME library consists of a number of packages, all written in C++. The general philosophy is to provide generic, skeletal, algorithms, were a user can plug in iterators over different type of containers (such as vectors/arrays and lists), different point types (such as Cartesian and homogeneous points), and different distance functions when appropriate (such as the value of p for the Lp distance).

Polygonal Approximation

Description
This package provides polyline/polygon simplification (approximation) algorithms. These are useful for example for reducing the number of vertices of polylines before matching takes place, in particular when the polylines are extracted from raster images. The package contains different kinds of approximation algorithms:

  • Algorithms to compute an optimal approximation:
    • Given a polyline and a number k, construct the polyline of k vertices that minimizes the approximation error.
    • Given a polyline and an e, construct the polyline of that has an approximation error of at most e, and minimizes the number of vertices.
    For these problems we have implemented dynamic programming algorithms as well as a graph search method. Like the dynamic programming method, the graph search method finds the optimal number of vertices for a given error bound, or the other way around. It is much faster than the dynamic programming, but also less general: it works for a smaller number of distance functions.
  • Three heuristic recursive split algorithms:
    • An algorithm that recursively splits the approximation polyline at the vertex of furthest distance [Douglas & Peucker 1973].
    • A faster version of this algorithms that uses a hull data structure [Hershberger & Snoeyink 1992].
    • An algorithms that recursively splits at the vertex of largest enclosing intersection of two circles [Veltkamp 1998].
In all these algorithms, various distance measures can be plugged in.

Software
The software is written in Visual C++ version 6.

  • The package consists of the source code of the approximation functions, several distance functions to plug in, and a simple example pogram. [zip file]
  • A demo program showing much of the available functionality is provided as source code [zip file], and as executable [zip file].

Manuals
User and reference manual. [zip file]

Further reading
The following technical report describes the architecture design, implementation decisions, and experimental results:

Ovidiu Grigore, Remco C. Veltkamp. On the Implementation of Polygonal Approximation Algorithms. Technical Report UU-CS-2003-005. [pdf file]

Polyline Matching

Description
This package provides a function to compute the Fréchet distance between two polygonal curves. This is done in O(mnlog(mn)) time using an optimization technique called parametric search [Alt & Godeau 1995]. Until now, parametric search was considered of mainly theoretical interest because of the complexity of implementation. Our implementation is the first that actually uses parametric search, and runs faster than an implementation based on binary search instead of parametric search, something which is often advocated as a good alternative.

Software
The software is developed with gcc version 3.3.5. Since it uses only standard C++ features, porting to other platforms should be relatively easy. It consists of the source code of the Fréchet distance function as well as the framework to perform general parametric search. Note that the Fréchet distance code uses CGAL, so this should be installed as well. A demo program is provided as source code. [gzipped tar-file]

Manuals
Reference manual. [pdf file]
Tutorial. [pdf file]

Further reading
The following paper describes the architecture design, implementation decisions, and experimental results:

René van Oostrum and Remco C. Veltkamp. Parametric search made practical. Computational Geometry: Theory and Applications, 28(2-3):75-88, 2004. Special issue on the 18th Annual Symposium on Computational Geometry, on invitation.

The paper is also available as technical report:

René van Oostrum and Remco C. Veltkamp. Parametric search made practical. Technical Report UU-CS-2002-050, Utrecht University, 2002.

Reusable Evolutionary Algorithms in Shape Matching (REALISM)

Description
The heart of this C++ library is the function evofunc, which implements an evolutionary optimisation method, one of many methods to do non-linear optimisation. If you have a function for which you'd like to find a global minimum, and can't do so analytically, then maybe this package will help.
The library is designed for the following problem in particular: given a source object that can be transformed, what are the transformation parameters that take the source closest to the target?
All you need to provide is:

  • the type of the source, transformed source, and target object
  • a function that transforms an object of the source type, given a set of parameters
  • a function that computes an error value given an object of the transformed source type and one of the target type

Software
This package was successfully compiled under Windows 2000, using Visual Studio C++ 7.1, under Linux kernel 2.4.20, using gcc 3.2.2, and under Mac OS X kernel Darwin 6.8, also using gcc. Download.

Plans
  • Point sets under various transformations using multiresolution transformation space subdivion.
  • Weighted point sets using the Earth Movers' Distance and the Proportional Transportation Distance.
  • Polygons and polylines using the function difference between accumulative turning angle functions.
People
The following people are involved, or have been involved in the development of the library:
Acknowledgement
This work is supported by the Dutch Technology Foundation STW, under grant UIF.5055.
webmaster: Remco Veltkamp