Shape Matching

Contact: Remco Veltkamp

Description
Projects
People
Facilities
Student projects
Publications

Description
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 .

Projects

SHAME (Shape Matching Environment)
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.

NODES (Novel Techniques for Describing Shape)
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.

Past Projects:

Geometric Pattern Matching
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.

People

The following people are involved in this research area:

Facilities

For implementation and testing we have a lab 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.

Student projects

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 Remco Veltkamp. For more information see the education page.

webmaster: Remco Veltkamp