|
Contact: Remco Veltkamp
Terms of use
General
Polygonal Approximation
Polyline Matching
Evolutionary Algorithms in Shape Matching
Plans
People
Acknowledgement
Terms of use
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).
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]
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.
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.
-
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.
The following people are involved, or have been involved in the development
of the library:
This work is supported by the Dutch Technology Foundation STW, under
grant UIF.5055.
webmaster: Remco Veltkamp
|