Technical Report CIS-2008-06

Title: Minima w.r.t. Expansions are Minima w.r.t. Swaps - A Proof
Authors: Ido Leichter
Abstract: Many proposed solutions to computer vision and image processing problems involve the minimization of multi-label functions - functions whose variables may assume labels from a finite set of labels. In the context multi-label function minimzation, the swap and the expansion are two types of commonly used moves from one labeling to the next. Efficient algorithms for finding a local minimum with respect to each of these two moves have been developed. These algorithms are restricted by different limits to the maximal number of variables allowed in one term of the objective function and by different conditions related to the function terms. These algorithms work under the condition that the objective functions are reduced into submodular ones, which have been shown to be minimized in polynomial time. This report provides a proof that under this condition minima with respect to expansion moves are also minima with respect to swap moves. This suggests that minimization with respect to the former move type should be more effective than with respect to the latter. This may also give an explanation for obtaining better experimental results for expansion moves than swap moves in previous works.
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