Premium
Large‐Scale Integer Linear Programming for Orientation Preserving 3 D Shape Matching
Author(s) -
Windheuser Thomas,
Schlickwei Ulrich,
Schimdt Frank R.,
Cremers Daniel
Publication year - 2011
Publication title -
computer graphics forum
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.578
H-Index - 120
eISSN - 1467-8659
pISSN - 0167-7055
DOI - 10.1111/j.1467-8659.2011.02021.x
Subject(s) - integer programming , linear programming , matching (statistics) , computer science , integer (computer science) , orientation (vector space) , algorithm , time complexity , mathematical optimization , mathematics , theoretical computer science , geometry , statistics , programming language
We study an algorithmic framework for computing an elastic orientation‐preserving matching of non‐rigid 3 D 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.