@conference {Tourani2018, title = {MPLP++: Fast, Parallel Dual Block-Coordinate Ascent for Dense Graphical Models}, booktitle = {Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)}, volume = {11208 LNCS}, year = {2018}, pages = {264{\textendash}281}, abstract = {Dense, discrete Graphical Models with pairwise potentials are a powerful class of models which are employed in state-of-the-art computer vision and bio-imaging applications. This work introduces a new MAP-solver, based on the popular Dual Block-Coordinate Ascent principle. Surprisingly, by making a small change to a low-performing solver, the Max Product Linear Programming (MPLP) algorithm [7], we derive the new solver MPLP++ that significantly outperforms all existing solvers by a large margin, including the state-of-the-art solver Tree-Reweighted Sequential (TRW-S) message-passing algorithm [17]. Additionally, our solver is highly parallel, in contrast to TRW-S, which gives a further boost in performance with the proposed GPU and multi-thread CPU implementations. We verify the superiority of our algorithm on dense problems from publicly available benchmarks as well as a new benchmark for 6D Object Pose estimation. We also provide an ablation study with respect to graph density.}, keywords = {Block-Coordinate-Ascent, graphical models, Message passing algorithms}, isbn = {9783030012243}, issn = {16113349}, doi = {10.1007/978-3-030-01225-0_16}, author = {Tourani, Siddharth and Shekhovtsov, Alexander and Carsten Rother and Savchynskyy, Bogdan} }