Software

1. Clique Reduction by Excludable Local Configuration software (a C++ source code)

Version 1.04 (September 12th, 2014.)
Download: ELC1.04.zip

Software (a C++ source code) for minimizing a higher-order function of binary variables x1, ..., xn. What it actually does is to reduce the function into a first-order MRF, or a Quadratic Pseudo-Boolean function, i.e., a function of the form:

E(x1, ..., xn, ..., xm) = Σi Ei(xi) + Σi,j Eij(xi, xj),

possibly with additional variables. Once the function is reduced, minimization itself can be done with known first-order methods, such as the QPBO (roof dual) algorithm below.

In this software, there are two ways to reduce a higher-order monomial to first order (second degree).

A) Finding Excludable Local Configuration (ELC)

Reduces the monomial without adding any variable. For some monomials, it cannot be done. So the B) below must be used after A). The technique is described in the following paper:
[1] Hiroshi Ishikawa. “Higher-Order Clique Reduction without Auxiliary Variables.” PDF
In CVPR2014, Columbus, Ohio. June 23-28, 2014.
Additionally, this software provides an approximation that always reduces the term without additional variables. It does so correctly most of the time, but there is no guarantee. It is much faster, though. This is also described in [1].

B) Higher-Order Clique Reduction (HOCR)

Additional variables are added to reduce the order of the energy. The number of variables increases exponentially as the order of the given energy increases. The technique is described in the following papers:
[2] Hiroshi Ishikawa. “Higher-Order Clique Reduction in Binary Graph Cut.” PDF
In CVPR2009, Miami Beach, Florida. June 20-25, 2009.

[3] Hiroshi Ishikawa. “Transformation of General Binary MRF Minimization to the First Order Case.” PDF
IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 33, no. 6, pp. 1234-1249, June 2011.

A demo program that loads the noise-added image and denoise it with a third-order FoE prior is included.

This software is implemented so that it can be used most conveniently in combination with the QPBO software by Vladimir Kolmogorov available at his page.

Older (buggy) versions are here: ELC1.00.zip ELC1.01.zip ELC1.02.zip ELC1.03.zip

2. Higher-Order Clique Reduction software (a C++ source code)

Note: the ELC software above includes the functionality of this software, and probably faster.

Version 1.02a (November 30th, 2011; URL update.)
Download: HOCR1.02a.zip

Software (a C++ source code) for minimizing a higher-order function of binary variables x1, ..., xn. What it actually does is to reduce the function into a first-order MRF, or a Quadratic Pseudo-Boolean function, i.e., a function of the form:

E(x1, ..., xn, ..., xm) = Σi Ei(xi) + Σi,j Eij(xi, xj),

on which algorithms such as QPBO and BP can be used. The additional binary variables xn+1, ..., xm are added to reduce the order of the energy. The number of variables increases exponentially as the order of the given energy increases.

The technique in this software is described in the following papers:

Hiroshi Ishikawa. “Higher-Order Clique Reduction in Binary Graph Cut.” PDF
In CVPR2009: IEEE Computer Society Conference on Computer Vision and Pattern Recognition, Miami Beach, Florida. June 20-25, 2009.

Hiroshi Ishikawa. “Transformation of General Binary MRF Minimization to the First Order Case.” PDF
IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 33, no. 6, pp. 1234-1249, June 2011.

A demo program that loads the noise-added image and denoise it with a third-order FoE prior is included.

This software is implemented so that it can be used most conveniently in combination with the QPBO software by Vladimir Kolmogorov available at his page.

Older (buggy) versions are here: HOCR1.00.zip HOCR1.01.zip