An Order Reduction Design Framework for Higher-Order Binary Markov Random Fields

The order reduction method is an important approach to optimize higher-order binary Markov random fields (HoMRFs), which are widely used in information theory, machine learning and image analysis. It transforms an HoMRF into an equivalent and easier reduced first-order binary Markov random field (RMRF) by elaborately setting the coefficients and auxiliary variables of RMRF. However, designing order reduction methods is difficult, and no previous study has investigated this design issue. In this paper, we propose an order reduction design framework to study this problem for the first time. Through study, we find that the design difficulty mainly lies in that the coefficients and variables of RMRF must be set simultaneously. Therefore, the proposed framework decomposes the design difficulty into two processes, and each process mainly considers the coefficients or auxiliary variables of RMRF. Some valuable properties are also proven. Based on our framework, a new family of 14 order reduction methods is provided. Experiments, such as synthetic data and image denoising, demonstrate the superiority of our method.