Frank R. Schmidt

Efficient Shape Matching via Graph Cuts

Energy Minimization Methods in Computer Vision and Pattern Recognition (EMMCVPR), Volume 4679, page 39--54 - Aug 2007
Download the publication: 625 KB 
Share the publication:
Meaningful notions of distance between planar shapes typically involve the computation of a correspondence between points on one shape and points on the other. To determine an optimal correspondence is a computationally challenging combinatorial problem. Traditionally it has been formulated as a shortest path problem which can be solved efficiently by Dynamic Time Warping.
In this paper, we show that shape matching can be cast as a problem of finding a minimum cut through a graph which can be solved efficiently by computing the maximum network flow. In particular, we show the equivalence of the minimum cut formulation and the shortest path formulation, i.e. we show that there exists a one-to-one correspondence of a shortest path and a graph cut and that the length of the path is identical to the cost of the cut. In addition, we provide and analyze some examples for which the proposed algorithm is faster resp. slower than the shortest path method.

Images and movies

graphcut.png (27 KB)

BibTex references

  author       = "Schmidt, Frank R. and T{\"o}ppe, Eno and Cremers, Daniel and Boykov, Yuri",
  title        = "Efficient Shape Matching via Graph Cuts",
  booktitle    = "Energy Minimization Methods in Computer Vision and Pattern Recognition (EMMCVPR)",
  series       = "LNCS",
  volume       = "4679",
  pages        = "39--54",
  month        = "Aug",
  year         = "2007",
  publisher    = "Springer",
  address      = "Ezhou, China",
  url          = ""