Generalized Fast Approximate Energy Minimization via Graph Cuts: Alpha-Expansion Beta-Shrink Moves

Mark Schmidt (INRIA Paris - Rocquencourt), Karteek Alahari (INRIA Paris - Rocquencourt)
Proceedings of the 27th Conference on Uncertainty in Artificial Intelligence, PMLR R9:724-731, 2011.

Abstract

We present alpha-expansion beta-shrink moves, a simple generalization of the widely-used alpha-beta swap and alpha-expansion algorithms for approximate energy minimization. We show that in a certain sense, these moves dominate both alpha-beta-swap and alpha-expansion moves, but unlike previous generalizations the new moves require no additional assumptions and are still solvable in polynomial-time. We show promising experimental results with the new moves, which we believe could be used in any context where alpha-expansions are currently employed.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR9-rocquencourt-11a, title = {Generalized Fast Approximate Energy Minimization via Graph Cuts: Alpha-Expansion Beta-Shrink Moves}, author = {Rocquencourt), Mark Schmidt (INRIA Paris - and Rocquencourt), Karteek Alahari (INRIA Paris -}, booktitle = {Proceedings of the 27th Conference on Uncertainty in Artificial Intelligence}, pages = {724--731}, year = {2011}, editor = {Cozman, Fabio and Pfeffer, Avi}, volume = {R9}, series = {Proceedings of Machine Learning Research}, month = {14--17 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r9/main/assets/rocquencourt-11a/rocquencourt-11a.pdf}, url = {https://proceedings.mlr.press/r9/rocquencourt-11a.html}, abstract = {We present alpha-expansion beta-shrink moves, a simple generalization of the widely-used alpha-beta swap and alpha-expansion algorithms for approximate energy minimization. We show that in a certain sense, these moves dominate both alpha-beta-swap and alpha-expansion moves, but unlike previous generalizations the new moves require no additional assumptions and are still solvable in polynomial-time. We show promising experimental results with the new moves, which we believe could be used in any context where alpha-expansions are currently employed.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Generalized Fast Approximate Energy Minimization via Graph Cuts: Alpha-Expansion Beta-Shrink Moves %A Mark Schmidt (INRIA Paris - Rocquencourt) %A Karteek Alahari (INRIA Paris - Rocquencourt) %B Proceedings of the 27th Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2011 %E Fabio Cozman %E Avi Pfeffer %F pmlr-vR9-rocquencourt-11a %I PMLR %P 724--731 %U https://proceedings.mlr.press/r9/rocquencourt-11a.html %V R9 %X We present alpha-expansion beta-shrink moves, a simple generalization of the widely-used alpha-beta swap and alpha-expansion algorithms for approximate energy minimization. We show that in a certain sense, these moves dominate both alpha-beta-swap and alpha-expansion moves, but unlike previous generalizations the new moves require no additional assumptions and are still solvable in polynomial-time. We show promising experimental results with the new moves, which we believe could be used in any context where alpha-expansions are currently employed. %Z Reissued by PMLR on 04 October 2026.
APA
Rocquencourt), M.S.(.P.-. & Rocquencourt), K.A.(.P.-.. (2011). Generalized Fast Approximate Energy Minimization via Graph Cuts: Alpha-Expansion Beta-Shrink Moves. Proceedings of the 27th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R9:724-731 Available from https://proceedings.mlr.press/r9/rocquencourt-11a.html. Reissued by PMLR on 04 October 2026.

Related Material