Schmidt and Karteek Alahari
Last updated 19 July 2011.
The alphaBeta code implements the alpha-expansion beta-shrink moves and other
methods for approximate energy minimization described
in the paper:
Clicking on the image
below opens a poster giving an overview of the method and results:
The code contains implementations of
several available methods for the problem of
computing an approximate minimizer of the sum of a set of unary and pairwise
real-valued functions over discrete variables:
min_x: sum_i E_i(x_i) + sum_ij E_ij(x_i,x_j),
where the second sum is over a set of edges in a graph. This equivalent to the
problem of MAP estimation, also known as decoding, in a pairwise undirected graphical model.
The particular methods
contained in the package are:
The ICM method requires no assumptions on the energies, but the others assume
that the pairwise functions encourage the neighbors to take
the same state, in the sense that
- iterated conditional mode (ICM): at each iteration, this method
finds the optimal update for a single variable.
- alpha-beta swap: at each iteration, this method finds the optimal
way to swap the labels of all variables assigned to two of the states.
- alpha-expansion: at each iteration, this method finds the optimal
way to expand the set of variables assigned to one state.
- alpha-expansion beta-shrink: at each iteration, this method finds
the optimal way to expand the set of variables assigned to one state
(alpha-expansion) and to replace the variables that currently have that state
with another state (beta-shrink).
E_ij(alpha,alpha) + E_ij(beta,beta) <= E_ij(alpha,beta) +
for all edges ij and all pairs of states alpha and beta.
In order to guarantee that they find the optimal move, the two
alpha-expansion methods require the stronger condition
E_ij(alpha,alpha) + E_ij(gamma_1,gamma_2) <= E_ij(alpha,gamma_2) +
for all edges ij and all triplets of
states alpha, gamma_1, and gamma_2.
However, for iterations where this is not satisfied the implementations
use a truncation of the energies. See the paper/poster linked above for more details on
the problem/methods, and the paper for a list of references.
Download and Examples
To use the code, download and
unzip alphaBeta.zip. To solve the binary energy
minimization problems, you will also need to have
wrapper to the maxflow
code installed in a subfolder of this directory.
Once this is done, type the following in Matlab:
Typing the above commands will load the graph and energy function associated
with a stereo vision data set, and apply various solvers to it (first with the
UGMep implementations, and then with the UGM implementations).
>> cd alphaBeta % Change to the unzipped directory
>> addpath(genpath(pwd)) % Add all sub-directories to the path
>> example_alphaBeta_UGMep % Run the demo with the UGMep code
>> example_alphaBeta_UGM % Run the demo with the UGM code
We have included mex files for several operating systems. To compile the mex
files for other operating systems, run the
included mexAll function.
UGM vs. UGMep
There are two versions of each method available.
The UGMep code works directly with node and edge energies and assumes
that the edge energies are the same across edges except for multiplication by a
scalar. In contrast, the UGM code works with potentials (i.e. pot_i(x_i) =
exp(-E_i(x_i))) and allows arbitrary (non-negative) edge potentials on
each edge. Thus, the UGMep code is slightly faster and requires
substantially less memory if the graph is sparse,
but the UGM code allows more general edge energies.
Note that the full UGM package as well as some introductory material
on undirected graphical models is available here.
Mark Schmidt > Software > alphaBeta