Optimization in Machine Learning and Computer Vision

Dr. Bogdan Savchynskyy, SoSe 2023

This seminar belongs to the Master in Physics (specialisation Computational Physics, code "MVJC"), Master of Data and Computer Science (code "IS") as well as Master Mathematics (code "MS") programs, but is also open for students of Scientific Computing and anyone interested.


Machine learning techniques are tightly coupled with optimization methods. Many techniques become practical only if there exists a supporting optimization tool.

In the seminar we will discuss a number of recent articles on combinatorial optimization with applications in computer vision and machine learning.

The topics of this semester are the

Multi-Graph Matching Problem
Video-Based Scene Analysis.

We will consider inference and learning techniques for these problems as well as the related applications in computer vision.

General Information

Please register for the seminar in Müsli. The first seminar will take place on Wednesday, April 19 at 11:00. Please make sure to participate!

  • Seminar: Wed, 11:00 – 13:00 in Mathematikon B (Berliner Str. 43), SR B128
    Entrance through the door at the side of Berlinerstrasse. Ring the door bell labelled "HCI am IWR" to be let in. The seminar room is on the 3rd floor.
  • Credits: 2 / 4 CP depending on course of study, see LSF

Seminar Repository:

Slides and schedule of the seminar will be placed in HeiBox .

Papers to Choose from:

    Multi-graph matching:

  • Synchronization technique:
    • Spectral methods:
    • [1] Shen, Y., Huang, Q., Srebro, N., Sanghavi, S., 2016. Normalized Spectral Map Synchronization
      [2] Pachauri et al. 2013 - Solving the multi-way matching problem by permutation synchronization
      [3] Arrigoni, F., Maset, E., Fusiello, A., 2017. Synchronization in the Symmetric Inverse Semigroup
      [4] Maset et al. 2017 - Practical and Efficient Multi-View Matching
      [5] Fathian, K., Khosoussi, K., Tian, Y., Lusk, P., How, J.P., 2020. Clear: A consistent lifting, embedding, and alignment rectification algorithm for multiview data association.
      [6] Bernard et al. 2021 - Sparse Quadratic Optimisation over the Stiefel Manifold with Application to Permutation Synchronisation
    • Semidefinite programming relaxations:
    • [7] Chen, Y., Guibas, L.J., Huang, Q.X., 2014. Near-Optimal Joint Object Matching via Convex Relaxation
    • Alternating direction methods of multipliers:
    • [8] Zhou et al . 2015 - Multi-Image Matching via Fast Alternating Minimization
    • Clustering-based (no explicit matrix factorisation):
    • [9] Tron et al . 2017 - Fast Multi-Image Matching via Density-Based Clustering
    • Nonnegative matrix factorisation:
    • [10] Bernard, F., Thunberg, J., Goncalves, J., Theobalt, C., 2019a. Synchronisation of partial multi-matchings via non-negative factorisations.
    • Other:
    • [11] Chen, Candes 2017 - The Projected Power Method: An Efficient Algorithm for Joint Alignment from Pairwise Differences
      [12] Birdal, Şimşekli 2019 - Probabilistic Permutation Synchronization using the Riemannian Structure of the Birkhoff Polytope
  • Other techniques:
    • Alternating optimization:
    • [13] Yan, J., Tian, Y., Zha, H., Yang, X., Zhang, Y., Chu, S.M., 2013. Joint Optimization for Consistent Multiple Graph Matching
    • Matrix decomposition:
    • [14] Yan, J., Xu, H., Zha, H., Yang, X., Liu, H., 2015. A matrix decomposition perspective to multiple graph matching
      [15] Wang, Q., Zhou, X., Daniilidis, K., 2018. Multi-Image Semantic Matching by Mining Consistent Features
    • Semidefinite programmming:
    • [16] Kezurer, I., Kovalsky, S.Z., Basri, R., Lipman, Y., 2015. Tight Relaxation of Quadratic Matching
      [17] Bernard, F., Theobalt, C., Moeller, M., 2018. DS*: Tighter Lifting-Free Convex Relaxations for Quadratic Matching Problems
    • LP relaxation:
    • [18] Swoboda et al . 2019 - A convex relaxation for multi-graph matching
    • Power iterations:
    • [19] Shi, X., Ling, H., Hu, W., Xing, J., 2016. Tensor power iteration for multi-graph matching
      [20] Bernard, F., Thunberg, J., Swoboda, P., Theobalt, C., 2019b. Hippi: Higher-order projected power iterations for scalable multi-matching
  • Uncategorized:
  • [21] Hu et al. 2018 - Distributable Consistent Multi-Object Matching
    [22] Jiang et al. 2021 - Unifying Offline and Online Multi-Graph Matching via Finding Shortest Paths on Supergraph
    [23] Yan et al. 2015 - Consistency-Driven Alternating Optimization for Multigraph Matching: A Unified Approach
    [24] Yan et al. 2016 - A constrained clustering based approach for matching a collection of feature sets
    [25] Cosmo, L., Rodolà, E., Albarelli, A., Mémoli, F., Cremers, D., 2017. Consistent partial matching of shape collections via sparse modeling
  • Learning-based:
  • [26] Chen et al. - 2020 - Deep Semantic Matching with Foreground Detection and Cycle-Consistency
    [27] Zhou et al. - 2016 - Learning Dense Correspondence via 3D-Guided Cycle Consistency
    [28] Ye et al . -2022 - Joint Deep Multi-Graph Matching and 3D Geometry Learning from Inhomogeneous 2D Image Collections
    [29] Z. Nurlanov; F. R. Schmidt; F. Bernard - Universe Points Representation Learning for Partial Multi-Graph Matching. AAAI 2023
    [30] D. Cao; F. Bernard - Self-Supervised Learning for Multimodal Non-Rigid 3D Shape Matching Self-Supervised Learning for Multimodal Non-Rigid 3D Shape Matching, CVPR 2023
    [31] D. Cao; F. Bernard - Unsupervised Deep Multi-Shape Matching, ECCV 2023
    [32] M. Eisenberger; A. Toker; L. Leal-Taixe; F. Bernard; D. Cremers - A Unified Framework for Implicit Sinkhorn Differentiation, CVPR 2022

    Video-based scene analysis::

    [33] Fabian Brickwedde, Steffen Abraham, and Rudolf Mester. Mono-Stixels: Monocular Depth Reconstruction of Dynamic Street Scenes. 2018.
    [34] Sebastian Bullinger, Christoph Bodensteiner, Michael Arens, and Rainer Stiefelhagen. 3D Vehicle Trajectory Reconstruction in Monocular Video Data Using Environment Structure Constraints. 2018
    [35] René Ranftl, Vibhav Vineet, Qifeng Chen, and Vladlen Koltun. Dense monocular depth estimation in complex dynamic scenes. 2016
    [36] Suryansh Kumar, Yuchao Dai, and Hongdong Li. Monocular dense 3D reconstruction of a complex dynamic scene from two perspective frames. 2017
    [37] Amar Mitiche, Yosra Mathlouthi, and Ismail Ben Ayed. Monocular Concurrent Recovery of Structure and Motion Scene Flow. 2015
    [38] Degui Xiao, Qiuwei Yang, Bing Yang, and Wei Wei. Monocular scene flow estimation via variational method. 2015
    [39] Xiaochuan Yin, Xiangwei Wang, Xiaoguo Du, and Qijun Chen. Scale recovery for monocular visual odometry using depth estimated with deep convolutional neural fields. 2017
    [40] Keisuke Tateno, Federico Tombari, Iro Laina, and Nassir Navab. CNN-SLAM: Real-time dense monocular SLAM with learned depth prediction. 2017
    [41]Fácil, José M and Concha, Alejo and Montesano, Luis and Civera, Javier. Single-View and Multi-View Depth Fusion. 2017
    [42] Min Bai, Wenjie Luo, Kaustav Kundu, and Raquel Urtasun. Exploiting semantic information and deep matching for optical flow. 2016
    [43] Koichiro Yamaguchi, David McAllester, and Raquel Urtasun. Robust monocular epipolar flow estimation. 2013
    [44] Koichiro Yamaguchi, David McAllester, and Raquel Urtasun. Efficient Joint Segmentation, Occlusion Labeling, Stereo and Flow Estimation.
    [45] Andreas Geiger, Julius Ziegler, and Christoph Stiller. Stereoscan: Dense 3D reconstruction in real-time. 2011

Presentation schedule



Dr. Bogdan Savchynskyy
In case you contact me via email, its subject should contain the tag [OfMLCV]. Emails without this tag have a very high chance to be lost and get ignored therefore!