Joint Graph Decomposition and Node Labeling: Problem, Algorithms, Applications

Alexander (Oleksandr) Shekhovtsov
(Czech Technical University Prague, Czech Republic)


In this talk I will present an algorithm for discrete energy minimization (MAP of MRF), which is massively parallel and when implemented in GPU is suitable for time-critical applications like stereo and optical flow.

Many heuristics have been proposed previously for stereo to achieve real-timeness, such as very popular semi-global matching, which however sacrifice some quality when compared to proper optimization methods. The proposed algorithm is closely related to a family of message-passing methods that are sound in the sense that they monotonously improve on the convex dual of the problem. The fastest member of the family, tree-reweighted message passing, is unfortunately harder to parallelize. The proposed method, explained as a minorize-maximize technique on the convex dual, requires less

synchronization and makes better progress in initial iterations. I will also describe a recent application in stereo, where all local costs as well as regularization weights are CNN models trained for the best performance of the inference.