Optimization Techniques for Multi-Graph Matching (acronym OPTEMA)

• Applicant: Dr. Bogdan Savchynskyy
• Subject Area: Image and Language Processing, Computer Graphics and Visualisation, Human Computer Interaction, Ubiquitous and Wearable Computing
• Term: since 2024
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 539435352

Multi-graph matching is a well-established discrete optimization problem with a number of applications in computer vision and bio-imaging. These include, but are not limited to, multi-view reconstruction, tracking objects in videos, or shape collection alignment. Multi-graph matching problem instances are often of very large size. This makes standard off-the-shelf integer programming solvers like Gurobi prohibitively slow. There are no scalable methods that deliver high quality solutions. Fast methods are mostly inaccurate, and accurate methods are slow and do not scale well. The modern practical approach to multi-graph matching includes deep learning. This improves modeling, but not optimization. Arguably, more accurate and fast optimization would open a way to learn better models as soon as the optimization method is fast enough to be called inside a learning loop. The goal of the project is to develop fast and accurate multi-graph matching optimization methods. Their speed should allow for utilization in a learning loop and their accuracy for non-trivial applications. Due to the typical multi-graph matching problem size, we believe that achieving high accuracy in a short time is possible only via massive parallelization. The latter, therefore, is going to be an intrinsic property of the algorithms developed within the project.

• DFG Programme: Research Grants