- We developed a new state-of-the-art Block Coordinate Ascent (BCA) algorithm for dense graphical models based on the Handshake [3] operation.
- The method is state-of-the-art on all dataset instances with graph density >10% of all possible edges. We tested on the following datasets:
- Worms [5]
- Pose-6D [6]
- Stereo [4]
- Protein Folding [4]
- We developed parallel implementation for both CPU and GPU based on processing edges belonging to maximal matchings of the graph.
References:
[1] Kolmogorov, V., “Convergent tree-reweighted message passing for energy minimization”, PAMI, 2006.
[2] Globerson et al., “Fixing Max-Product: Convergent Message Passing Algorithms for MAP LP-Relaxations”, NIPS, 2008.
[3] Shekhovtsov, A., et al., “Solving Dense Image Matching in Real-Time Using Discrete-Continuous Optimization”, CVWW 2016.
[4] Kappes, J. et al. , “A comparative study of modern inference techniques for discrete energy minimization problems”, IJCV, 2015.
[5] Kainmueller, D., et al., “Graph matching problems for annotating C. Elegans”, IST Austria, Data Repository, 2017.
[6] Michel, F. et al., “Global hypothesis generation for {6D} object pose estimation”, CVPR, 2017.