Solving MRFs with Higher-Order Smoothness Priors Using Hierarchical Gradient Nodes

In this paper, we propose a new method for solving the

Markov random field

(MRF) energies with higher-order smoothness priors. The main idea of the proposed method is a graph conversion which decomposes higher-order cliques as hierarchical auxiliary nodes. For a special class of smoothness priors which can be formulated as gradient-based potentials, we introduce an efficient representation of an auxiliary node called a gradient node. We denote a graph converted using gradient nodes as a

hierarchical gradient node

(HGN) graph. Given a label set

$\mathcal{L}$

, the computational complexity of message passings of HGN graphs are reduced to

$\mathcal{O}(|\mathcal{L}|^2)$

from exponential complexity of a conventional factor graph representation. Moreover, as the HGN graph can integrate multiple orders of the smoothness priors inside its hierarchical structure, this method provides a way to combine different smoothness orders naturally in MRF frameworks. For optimizing HGN graphs, we apply the tree-reweighted (TRW) message passing which outperforms the belief propagation. In experiments, we show the efficiency of the proposed method on the 1D signal reconstructions and demonstrate the performance of the proposed method in three applications: image denoising, sub-pixel stereo matching and nonrigid image registration.