Chamfer Distance Transforms Object Detection Recognition Shape Matching Hausdorff


	The Chamfer System offers a high-performance solution to shape-based object detection. It covers the detection of arbitrary-shaped objects, whether parametrized (e.g. rectangles and ellipses) or not (e.g. pedestrian outlines). Because the system learns shape distributions of target objects from examples, it is flexible and easily adaptable, without reprogramming. Its pixel-based correlation approach eliminates the need for error-prone contour segmentation. A major advantage is the hierarchical approach of the system (in both shape and transformation space); it results in substantial efficiency gains compared to an equivalent brute-force template matching method. Speed-ups of several orders of magnitude have been measured. The Chamfer System has been employed in a wide range of applications, from object detection on-board smart vehicles, to inspection tasks in industrial vision, and target recognition for the military environment. The Chamfer System is MMX-enabled and runs under Windows/Linux on a standard PC. Depending on the specific application, it runs in real-time or at speeds close to real-time.

		The Basics

	At the core of the Chamfer System lies shape matching using distance transforms. Consider the case of detecting triangles in a scene image. See diagram below. The shape of the target object is captured by a binary template. The scene image is preprocessed by feature extraction (i.e. edge detection) and the so-called distance transform; this results in a distance image, where pixels contain the distances to closest data pixels in the feature image.




Article on the Chamfer System


			Matching consists of translating and positioning the template at various locations of the distance image; the matching measure is determined by the pixel values of the distance image which lie under the data pixels of the transformed template. The lower these values are, the better the match between image and template at this location. If, for example, the average distance value lies below a certain threshold, the target object is considered detected.

			The Main Innovations

			Typically, not just one template needs to be matched with an image, but a whole set of templates. These templates can be geometrical transformations of a single reference template (e.g. rotations, scales), or, more general, be examples capturing the set of appearances of a target object. The idea is to derive a representation off-line which exploits any structure in this template distribution, so that, online, matching can proceed optimized.



			The approach chosen groups similar templates together and represents each group by two entities: a “prototype” template and a distance parameter. The latter needs to capture the dissimilarity between the prototype template and the templates it represents. By matching the prototype template with the image, rather than with the individual templates, one typically achieves a speedup.



			When applied recursively, shape-clustering leads to a template tree. The tree is constructed automatically, level by level, starting at the leaf level, which contains the example shapes. Matching can now be seen as traversing the template tree. Because the traversal process is typically discontinued at the higher levels of the template tree, one achieves significant efficiency gains compared to a nonhierarchical method. Moreover, matching with the template tree is combined with coarse-to-fine matching on the image grid, resulting in additional efficiency gains.


	Article on the Chamfer System

But how to set the many distance thresholds at the nodes of the tree? Their value depends on a number of factors: any edge segmentation errors (“edge gaps”), the granularity of the image grid at the current level and clustering quality of the templates at the successor nodes. Furthermore, their value depends on the shape variation that one wants to tolerate at the leaf level, which in turn is influenced by template size and saliency.






	The Chamfer System uses statistical methods to map per-node distance thresholds onto probabilities during training. In online use, rather than having to input thousands of distance thresholds, the user inputs for each level of the tree a threshold on the posterior value, i.e. on the probability that the target object is present considering the matches obtained in a path from the root downto a node at this level. For more information on the Chamfer System, see recent journal article.



	Here are a few video-clips to illustrate the results obtained with the Chamfer System.

			Traffic Sign Recognition (1999)




	Article on the Chamfer System

0.93 Mb avi

0.87 Mb avi

Pedestrian Detection (1999-)




	More on pedestrian detection.

0.47 Mb avi

1.54 Mb avi

0.84 Mb avi

This last video-clip provided an insight of how the system works internally; i.e. how it “locks” onto a given target. It shows matching results at the intermediate levels of a three-level template hierarchy. Image locations where templates of the first, second and leaf level of the hierarchy matched successfully are shown in colors green, blue and red, respectively.

Finally, here is a tough scene where there are a lot of vertical structures which can be confused as pedestrians. To handle this, a texture-based RBF classifier is added to verify the candidate solutions obtained by the shape-based detection step. Detections which were positively identified as pedestrians are marked with a STOP icon in the following video clip.

0.37 Mb avi


	[Home Gavrila] [Resume] [Research] [People] [Publications] [Datasets] [Media Coverage] [Open Positions] [Search]


	Copyright © 2001-2006 Gavrila. All rights reserved. Disclaimer.

The Basics