Shortest Paths with Curvature and Torsion

December 21, 2013

Johannes Ulén, Fredrik Kahl and I have recently been to the International Conference on Computer Vision to present our paper Shortest Paths with Curvature and Torsion, in which we explore applications of higher-order regularization for shortest paths.

See the paper here.

The code is available here.

Generalized Roof Duality: Experiments

August 17, 2011

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.

Read the rest of this entry »

ICCV 2011: Generalized Roof Duality

August 7, 2011

Fredrik Kahl and I have a paper accepted to ICCV titled Generalized Roof Duality for Pseudo-Boolean Optimization.

Just as in the previous post, the problem of interest is to minimize degree-{m} polynomials {f: \mathbf{B}^n \rightarrow \bf \mathbf{R}} of the form:

\displaystyle  	f(\boldsymbol{x}) = \sum_i a_ix_i + \sum_{i<j} a_{ij}x_ix_j + \sum_{i<j<k} a_{ijk}x_ix_jx_k + \ldots.

The previous post showed that many different reductions to the quadratic case are possible. Our paper describes a generalization of roof duality which does not rely on reductions and is in a suitable sense optimal.

Read the rest of this entry »