Frank R. Schmidt

Postdoctoral Researcher


Large-Scale Integer Linear Programming for Orientation Preserving 3D Shape Matching

Thomas Windheuser, Ulrich Schlickewei, Frank R. Schmidt, Daniel Cremers
Computer Graphics Forum, Volume 30, Number 5, page 1471--1480 - Aug 2011
Download the publication : 3.1 MB 
We study an algorithmic framework for computing an elastic orientation-preserving matching of non-rigid 3D shapes. We outline an Integer Linear Programming formulation whose relaxed version can be minimized globally in polynomial time. Because of the high number of optimization variables, the key algorithmic challenge lies in efficiently solving the linear program. We present a performance analysis of several Linear Programming algorithms on our problem. Furthermore, we introduce a multiresolution strategy which allows the matching of higher resolution models.

Images and movies

wssc_sgp11.png (233 KB)

BibTex references

  author       = "Windheuser, Thomas and Schlickewei, Ulrich and Schmidt, Frank R. and Cremers, Daniel",
  title        = "Large-Scale Integer Linear Programming for Orientation Preserving 3D Shape Matching",
  journal      = "Computer Graphics Forum",
  number       = "5",
  volume       = "30",
  pages        = "1471--1480",
  month        = "Aug",
  year         = "2011",
  keywords     = "I.3.5 [Computer Graphics]: Computational Geometry and Object Modeling—",
  url          = ""