Fusion-move optimization for MRFs with an extensive label space

The efficient optimization of Markov random fields is in general a very challenging task, as discussed in many of the other chapters in this book (e.g., 11, 3, and 4). One popular class of optimization methods is based on the move-making paradigm, which is introduced in chapter 3. That chapter describes the expansion-move and swap-move algorithms. In the present chapter another move-making algorithm is described, the fusion move. The expansion-move and swap-move algorithms are particular instances of the fusion-move technique. The main benefit of this algorithm is its generality and, hence, its applicability too many different application scenarios, even outside the traditional scope of move-making methods. In particular it is demonstrated that fusion move can be utilized to parallelize the expansion-move algorithm, and can also be applied to MRFs where the underlying label space is continuous, such as those used for optical flow. One practical challenge during the application of the fusion-move algorithm is that it comprises a set of binary optimization problems that in general are NP-hard to optimize. We will discuss how to deal with this issue and analyze the practical relevance of this problem.