First, we divide the X into 3 parts, and assign a different primary color to each part. We then corrupt the RGB channels with independent Gaussian noise to make a colored noisy X. We then fit a CRF with a pseudo-likelihood approximation subject to relevant constraints that will allow us to apply the algorithms discussed in this section (we discuss these operations in more detail in a later demo). This is implemented by the function:

Below is an example of the colored X and a noisy version of it:getNoisyX2

In the previous demo, we discussed the relative 'strengths' of the local optima found by ICM, block ICM, and graph cuts. Performing alpha-beta swaps until we reach a local optima yields another characterization of a local optima: the solution found by the alpha-beta swap moves can not be improved by changing any combination of nodes, restricted to combinations where all nodes are assigned to only 2 of the states. Thus, alpha-beta swap moves find a stronger local optima than ICM, and for binary models they find a stronger local optimum than block ICM. For non-binary models, we will not generally be able to compare the strengths of the optima found by block ICM and alpha-beta swaps.

To use the alpha-beta swap local search method in UGM, we can use:

Below, we plot the results for a sample of the colored noisy X problem. The first plot shows the approximate decoding found by ICM, while the next two plots show the approximate decoding found by block ICM and alpha-beta swaps (where we initialize these two with the ICM decoding).alphaBetaDecode = UGM_Decode_AlphaBetaSwap(nodePot,edgePot,edgeStruct,@UGM_Decode_GraphCut);

Notice that the block ICM algorithm was not able to remove the misclassified block of pixels in the upper-left arm, but that the alpha-beta swaps fixed this. Of course, the block ICM method could also fix this if we added a suitably constructed block.

To use alpha-expansions for decoding, we can use:

alphaExpDecode = UGM_Decode_AlphaExpansion(nodePot,edgePot,edgeStruct,@UGM_Decode_GraphCut);

To use alpha-expansion beta-shrink moves for decoding, we can use:

SettingbetaSelect = 3; alphaExpBetaShrinkDecode = UGM_Decode_AlphaExpansionBetaShrink(nodePot,edgePot,edgeStruct,@UGM_Decode_GraphCut,betaSelect,ICMDecoding);

At this point, we are left with a somewhat unsatisfying answer as to which greedy decoding method works the best. This is because we don't know whether block ICM or alpha-expansion beta-shrink moves will give a stronger local optima. Fortunately, there is an easy solution to this. We could simply alternate between block ICM and alpha-expansion beta-shrink moves until neither can make any improvements. This leads to a combined algorithm that reaches a local optimum in a stronger sense than either algorithm alone. Further, we could augment this algorithm with random restarts (or other stochastic local search tricks) if we want to ensure that the method will eventually find the global optimum.

The alpha-beta swap and alpha-expansion moves originated in the computer vision community, where the required assumptions are often satisfied. In particular, they are discussed in:

- Boykov Veksler Zabih (2001). Fast Approximate Energy Minimization via Graph Cuts. IEEE Transactions of Pattern Analysis and Machine Intelligence.

- Leichter (2009). The Swap and Expansion Moves Revisited and Fused. International Conference on Computer Vision.

- Rother Kumar Kolmogorov Blake (2005). Digital Tapestry. IEEE Conference on Computer Vision and Pattern Recognition.

In some applications the edge potentials are identical across edges, up to multiplying their logarithm by a constant. The code available here includes more efficient implementations of the methods discussed in this demo for this scenario.

Mark Schmidt > Software > UGM > AlphaBeta Demo