By default, the UGM_Decode_GraphCut function searches for the mex wrapper to the maxflow code. If this software is not found on the path, then UGM_Decode_GraphCut uses a simple implementation of the Ford-Fulkerson method. Note that the Ford-Fulkerson implementation is very slow, so it recommended to install the maxflow software for larger graphs.

It is a 32 by 32 binary image. If we corrupt it with independent Gaussian noise, it will look something like this:

Given the noisy X, our task is to assign binary states to the pixels to try and recover the original X (or whatever other binary image has been corrupted by noise).

The first approach we might try to solve this problem is to threshold the pixel
values. Decoding by independently thresholding the pixels gives this result:

Independently thresholding the pixels doesn't take into account that
neighboring pixels are likely to take the same value. One way to model this
dependency is with a UGM.

load X.mat % Load the image X = X + randn(size(X))/2; % Make a noisy version of it [nRows,nCols] = size(X); nNodes = nRows*nCols; nStates = 2; adj = sparse(nNodes,nNodes); % Add Down Edges ind = 1:nNodes; exclude = sub2ind([nRows nCols],repmat(nRows,[1 nCols]),1:nCols); % No Down edge for last row ind = setdiff(ind,exclude); adj(sub2ind([nNodes nNodes],ind,ind+1)) = 1; % Add Right Edges ind = 1:nNodes; exclude = sub2ind([nRows nCols],1:nRows,repmat(nCols,[1 nRows])); % No right edge for last column ind = setdiff(ind,exclude); adj(sub2ind([nNodes nNodes],ind,ind+nRows)) = 1; % Add Up/Left Edges adj = adj+adj'; edgeStruct = UGM_makeEdgeStruct(adj,nStates); % Standardize Features Xstd = UGM_standardizeCols(reshape(X,[1 1 nNodes]),1);

nodePot = zeros(nNodes,nStates); nodePot(:,1) = exp(-1-2.5*Xstd(:)); nodePot(:,2) = 1;

edgePot = zeros(nStates,nStates,edgeStruct.nEdges); for e = 1:edgeStruct.nEdges n1 = edgeStruct.edgeEnds(e,1); n2 = edgeStruct.edgeEnds(e,2); pot_same = exp(1.8 + .3*1/(1+abs(Xstd(n1)-Xstd(n2)))); edgePot(:,:,e) = [pot_same 1;1 pot_same]; end

This looks much better than the independent model, but as we will see next the locally optimal decoding found by ICM is not as good as the globally optimal decoding.

We can use UGM to find the optimal decoding in a model satisfying these restrictions using:

The optimal decoding of the UGM gives the following more satisfactory result:optimalDecoding = UGM_Decode_GraphCut(nodePot,edgePot,edgeStruct); imagesc(reshape(optimalDecoding,nRows,nCols)); colormap gray

Graph cuts were originally proposed for finding the optimal decoding in an image denoising problem in:

- D.M. Greig, B.T. Porteous, and A.H. Seheult.
**Exact Maximum A Posteriori Estimation for Binary Images**. Journal of the Royal Statistical Society Series B, 1989.

- V. Kolmogorv and R. Zabih.
**What energy functions can be minimized via graph cuts?**IEEE Transactions on Pattern Analysis, 2004.

Mark Schmidt > Software > UGM > GraphCuts Demo