Evaluation of Convex Optimization Techniques for the Weighted Graph-Matching Problem in Computer Vision

Christian Schellewald, Stefan Roth, and Christoph Schnörr
B. Radig, S. Florczyk (Eds.), Pattern Recognition, Lecture Notes in Computer Science, Vol. 2191, Springer Verlag, Berlin, pp. 361-368, 2001.

Abstract. We present a novel approach to the weighted graph-matching problem in computer vision, based on a convex relaxation of the underlying combinatorial optimization problem. The approach always computes a lower bound of the objective function, which is a favorable property in the context of exact search algorithms. Furthermore, no tuning parameters have to be selected by the user, due to the convexity of the relaxed problem formulation. For comparison, we implemented a recently published deterministic annealing approach and conducted numerous experiments for both established benchmark experiments from combinatorial mathematics, and for random ground-truth experiments using computer-generated graphs. Our results show similar performance for both approaches. In contrast to the convex approach, however, four parameters have to be determined by hand for the annealing algorithm to become competitive.

	@InProceedings{schellewald-roth-schnoerr-01,
  author =    "Schellewald, C. and Roth, S. and Schn{\"o}rr, C.",
  title =     "Evaluation of Convex Optimization Techniques for the Weighted Graph-Matching Problem in Computer Vision" 
  editor =    "Radig, B. and Florczyk, S.",
  volume =    "2191",
  series =    "Lect.~Notes Comp.~Science",
  pages =     "361--368",
  booktitle = "Mustererkennung 2001",
  year =      "2001",
  publisher = "Springer",
  address =   "Munich, Germany",
  month =     "Sept.~12--14"
}

Note: The copyright of the content lies with the respective holder.