This is a follow-up to the previous post about generalized roof duality and will contain some experimental results.
We have performed experiments with polynomials of degree 3 and 4. While these two cases are very similar in concept, implementing the degree 3 case is considerably easier.
1. Random polynomials
The first experiment used random polynomials of degree three. The following image shows how many labeled variables (persistencies) we obtained out of a total number of 1000. One hundred random polynomials were tested.
2. Image denoising
Image denoising is used in Ishikawa’s 2011 PAMI paper as a benchmark for quartic polynomial minimization. Below is a comparison.
This experiment had both methods solve exactly the same optimization problem in each iteration. If we instead let both methods progress independently, we can look at how the target energy evolves:
The previous comparison is not really fair, since we are required to solve a linear program, which takes time. However, as is hinted in the paper, we do not really need to find the optimal relaxation. Often, finding an approximate one can be almost as good. Below is a very preliminary experiment with this approach. The heuristics takes only a small fraction of the total time.
Finally, a better comparison would be obtained if HOCR was iterated as well, using obtained persistencies to simplify the polynomial. Our future experiments will take this into consideration.
As usual, see the full paper for details.