Technical Report CIS-2008-05

Title: The Swap, Expansion and Exwap Moves - A Simple Derivation and Implementation
Authors: Ido Leichter
Abstract: In the context of multi-label energy function minimization, the swap and the expansion are two types of moves that were introduced by Boykov et al. [2]. They proposed efficient algorithms for finding local minima with respect to each of these two moves when each energy term depends on two variables at most. The minimization was carried out by a sequence of optimal moves that were calculated by seeking minimum cuts of specially constructed weighted graphs. In this paper these optimal swap and expansion moves are obtained in a short and simple manner by incorporating the original algorithm by Greig et al. [5] as a "black box." Our alternative derivation has three advantages over the original one: 1. Given Greig et al.'s original solution as a black box, it is shorter, purely algebraic (that is, no graphs are involved) and, we believe, simpler to understand and implement. 2. It is derived under more general conditions. 3. It contains a proof that the found local minima with respect to expansion moves are actually also local minima with respect to swap moves - a point that seems to have been overlooked in previous work. All the results are extended for energy terms that depend on three variables by using Kolmogorov et al.'s binary minimization algorithm [9] as a black box. In addition, the exwap move type, a generalization of the expansion and the swap move types, is introduced and an efficient algorithm for minimizing with respect to it is derived.
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 2008
To the main CS technical reports page

Computer science department, Technion