Ruprecht-Karls-Universitšt Heidelberg
HCI->Computer Vision Group->Research->Max-Margin Regularization for Chamfer Matching

Max-Margin Regularization for Chamfer Matching

Chamfer matching is an effective and widely used technique for detecting objects or parts thereof by their shape. However, a serious limitation is its susceptibility to background clutter. The primary reason for this is that the presence of individual model points in a query image is measured independently. A match with the object model is then represented by the sum of all the individual model point distance transformations. Consequently, i) all object pixels are treated as being independent and equally relevant, and ii) the model contour (the foreground) is prone to accidental matches with background clutter.

As demonstrated by Attneave [1], and various experiments on illusionary contours, object boundary pixels are not all equally important due to their statistical interdependence. Moreover, in dense background clutter the points on the model have a high likelihood to find good spurious matches [1, 3]. However, any arbitrary model would match to such a cluttered region, which consequently gives rise to matches with high accidentalness. Chamfer matching only matches the template contour and thus fails to discount the matching score by the accidentalness, i.e., the likelihood that this is a spurious match.

Processing Pipeline


We take account of the fact that boundary pixels are not all equally important by applying a discriminative approach to chamfer distance computation, thereby increasing its robustness. Let and be the sets of template and query edge map respectively. Let denote the edge orientation of the edge point . For a given location of the template in the query image, directional chamfer matching [1] finds the best for each , thus resulting in a matching cost .


Adjacent template pixels are statistically dependent and, thus, we do average Eq.1 over the direct neighbors of pixel . The resulting are then used to learn the importance of contour pixels.

While learning the weights for individual pixels improves the robustness of template matching, chamfer matching is still prone to accidental responses in spurious background clutter. To estimate the accidentalness of a match, a small dictionary of simple background contours is utilized. Rather than placing background contours at a fixed single location, i.e., at the center of the model contour as in [3], background elements are trained to focus at locations where, relative to the foreground, typically accidental matches occur.

Let denote the directional chamfer distance between and with a relative displacement . To measure where clutter typically interferes with the model contour we compute between each background contour and the object template . We consider placements of the background contour with better (lower) chamfer matching score to be more important since they occur on or close to the model contour. In order to weight these matching locations higher we create a mask

To describe the background matching costs for a hypothesis in a robust way we build weighted histograms over chamfer matching scores obtained from matching a background contour with the query image . Let be the bounding box region with center for a specific placement of the foreground template in the query image . For each foreground hypothesis we build weighted histograms over the directional chamfer matching scores in the corresponding bounding box region. The weights introduced in are used to weight the histogram votes. Therefore chamfer matching scores are weighted according to their position relative to the foreground template. Each histogram consists of bins where is the range of the kth bin and . A histogram bin is defined as

for each background contour on a certain position of the foreground template in the query image .
For each object hypothesis we build a feature vector consisting of the average pixel cost and the corresponding background histograms , where L is the number of template edge pixels and G is the number of background contours.
Finally, a max-margin classifier is employed to learn the co-placement of all background contours and the foreground template. This classifier yields a regularized distance function


denotes the kernel used in the SVM. b denotes the offset. , denotes the support vectors and their respective coefficients.
Our approach is easily integrated into an off-the-shelf directional chamfer matching approach and it shows significant improvements over state-of-the-art chamfer matching on standard benchmark datasets. The qualitative and quantitative results are detailed in the paper.


For our experimental evaluation, we use the TUD Pedestrians, TUD Cows and the ETHZ Shape datasets. Comparison of average precision for three datasets namely, TUD Pedestrians, Cows and the ETHZ Shape classes. We compare DCM [1] which constitutes the basis of our approach with the suggested forground reweighting and our final learning of regularized chamfer matching. All the detections are evaluated based on PASCAL overlap criterion with the groundtruth object annotations.


Angela Eigenstetter*, Pradeep Yarlagadda*, and Björn Ommer,
Max-Margin Regularization for Reducing Accidentalness in Chamfer Matching,
in: ACCV'12, Springer, 2012 (* indicates equal contribution, accepted, in press). [Poster]

Pradeep Yarlagadda*, Angela Eigenstetter*, and Björn Ommer,
Learning Discriminative Chamfer Regularization,
in: BMVC'12, 2012 (* indicates equal contribution, accepted, in press).


  1. F. Attneave. Some informational aspects of visual perception. Psych. Review, 61(3), 1954.
  2. M. Liu and O. Tuzel and A. Veeraraghavan and R. Chellappa. Fast Directional Chamfer Matching. In CVPR, 2010.
  3. T. Ma and X. Xang and L. Latecki. Boosting Chamfer Matching by Learning Chamfer Distance Normalization. In ECCV, 2010.

[ People | Publications | Research | Projects | Teaching | Student Projects | HCI Home | CompVis Home ]     

Last update: 25.03.2015, 13:36
zum Seitenanfang