Minimizing Energy Functions on 4-Connected Lattices Using Elimination
Abstract
We describe an energy minimization algorithm for functions defined on 4-connected lattices, of the type usually encountered in problems involving images. Such functions are often minimized using graph-cuts/max-flow, but this method is only applicable to submodular problems. In this paper, we describe an algorithm that will solve any binary problem, irrespective of whether it is submodular or not, and for multilabel problems we use alpha-expansion. The method is based on the elimination algorithm, which eliminates nodes from the graph until the remaining function is submodular. It can then be solved using max-flow. Values of eliminated variables are recovered using back-substitution. We compare the algorithm's performance against alternative methods for solving non-submodular problems, with favourable results.
Cite
Text
Carr and Hartley. "Minimizing Energy Functions on 4-Connected Lattices Using Elimination." IEEE/CVF International Conference on Computer Vision, 2009. doi:10.1109/ICCV.2009.5459450Markdown
[Carr and Hartley. "Minimizing Energy Functions on 4-Connected Lattices Using Elimination." IEEE/CVF International Conference on Computer Vision, 2009.](https://mlanthology.org/iccv/2009/carr2009iccv-minimizing/) doi:10.1109/ICCV.2009.5459450BibTeX
@inproceedings{carr2009iccv-minimizing,
title = {{Minimizing Energy Functions on 4-Connected Lattices Using Elimination}},
author = {Carr, Peter and Hartley, Richard I.},
booktitle = {IEEE/CVF International Conference on Computer Vision},
year = {2009},
pages = {2042-2049},
doi = {10.1109/ICCV.2009.5459450},
url = {https://mlanthology.org/iccv/2009/carr2009iccv-minimizing/}
}