Technical Report CIS-2009-07

Title: The Swap and Expansion Moves Revisited and Fused
Authors: Ido Leichter
Abstract: Many solutions to computer vision and image processing problems involve the minimization of multi-label energy functions with up to K variables in each term. In the minimization process, the swap and the expansion are two types of commonly used moves. This paper re-derives the optimal swap and expansion moves for K=2 in a short manner by using the original solution to the pseudo-Boolean quadratic function minimization problem as a "black box", and reveals that the found minima w.r.t. expansions are actually also minima w.r.t. swaps. This is repeated for K=3. The minima-related result is extended to all objective functions under the condition that they are reduced into submodular ones, which makes it applicable to all expansion move algorithms. These may explain the prevalent impression that expansion algorithms are more effective than swap ones. To have a larger search space, the exwap - a generalization of the expansion and the swap move types - is introduced. Efficient algorithms for minimizing w.r.t. it for K=2 (including a 'truncation' procedure), K=3 and the P^n Potts model are provided. Its capabilities to reach lower energies than those reached by the expansion algorithm are demonstrated for image denoising and stereo matching benchmark problems.
CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the CIS technical reports of 2009
To the main CS technical reports page

Computer science department, Technion