Contact: Remco Veltkamp
For shape-based image matching, features are extracted from images, such as edge
and corner points, curves, and regions. The set of feature of one image is then
translated, rotated, and scaled so as to minimize some similarity function with
respect to the features from the other image. We develop similarity functions
that are robust against noise, occlusion, blurring, and small deformations,
as well as algorithms to compute them efficiently.
The following is an example of one of our matching algorithms in action.
Here are two different pictures of an SR71 airplane:
To these image we have applied an edge detection filter. Subsequent
thresholding yields a number of pixels that form a dot pattern.
Matching these two patterns under translation and scaling with
respect to the Hausdorff distance gives the following result on the
left. Applying the corresponding transformation to the images gives
the result on the right.
However, matching the same patterns with respect to what we call the
absolute difference metric, yields the results below. For more
information, see our
article in IJCV
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. At
the same time, we see that most of the problems solved are still relatively
simple (matching of point sets, matching of two curves or two regions) while
practical applications are more complex (point sets with accuracy weights,
collections of curves and regions, articulated curves, shape deformation).
Therefore, the objectives of this project are to further develop the theory in
these more complex areas, and to develop a state of the art software shape
matching environment (SHAME) of currently available algorithms.
In computer graphics, the common way to describe images and shapes is by
means of pixels (for image analysis) and triangles (for image synthesis). These
descriptions have their inherent shortcomings. Due to technological
developments (Moore's Law) the geometrical models are becoming so large
that these shortcomings become inadmissible. Therefore we propose a
significant enhancement of traditional shape description methods based on a
semantically higher level geometric description language. At the beginning of
this century mathematicians have introduced concepts (such as homotopy and
morse theory) that might be useful to overcome the barriers of existing shape
description techniques. Preliminary investigations carried out by e.g. T. Kunii
and coworkers show promising results. NODES is an assessment project to
validate the ideas and to prepare a full-scale project.
The type of pattern matching that we consider is the following. Given two sets
of dots, curves, or regions, find a transformation that brings one set close to
the other. One aspect of this is the choice of transformation type, for example,
combinations of translation, rotation, and scaling. Another aspect is the choice
of the `closeness' or distance measure; examples of this are the Hausdorff
distance, Frechet distance for curves, and area of symmetric difference for
regions. Our research is concerned with the development of algorithms, data
structures, and distance measures that have desirable properties, such as
invariance under a chosen type of transformation, robustness against local
deformation (for example due to digitization), noise, occlusion, blurring, and
change of topology.
The following people are involved in this research area:
For implementation and testing we have a
available with a 190 Gigabyte file server, a web server, and modern top-end
PC workstations with stereo viewing facilities.
This lab was partially donated by Microsoft and the Dutch Science Foundation.
There are ample opportunities for students to do master projects in this area.
The list above gives a number of research themes. The projects can both be
theoretically oriented and more experimental in nature.
The lab is available for the students to work in. If you are interested, contact
For more information see the
webmaster: Remco Veltkamp