Generalized Roof Duality: Experiments

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.


One Response to Generalized Roof Duality: Experiments

  1. Blorp says:

    Nice work!

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s