540 Project: Graph Cuts

For my project, I implemented a graph cuts algorithm for minimizing energy functions in Matlab and used it for exact inference on 2D binary lattice MRFs. This is based on results from What Energy Functions can be Minimized via Graph Cuts? (Kolmogorov and Zabih) and C++ code found here. I also used an M-File MaxFlows.m from a graph theory toolbox written by Sergiy Iglin (GrTheory, found at the Matlab Central File Exchange) and some demo/BP code borrowed from Kevin Murphy.

• myCode: Matlab files for graph cuts. The main interface is graph_cuts.m, which takes a 2 by 2 kernel matrix for edge potentials, and an n by n by 2 matrix for lattice variables local potentials and outputs the optimal assignment.
• Kevin's code: Some of Kevin's Matlab packages. Needed to run lattice_demo.
• GrTheory: Matlab toolbox written by Sergiy Iglin. Needed to solve the max flow problem.
• C++: Code borrowed from here (energy-v1.1.src.tar.gz). Modified to have input parameters the same as those in gc_random_demo. Note: Visual Studio may complain if you execute from a network mapped drive. Move this directory to the local hard drive before running.

1. gc_image_demo: For 4 different black and white pixel images (32 by 32 to 40 by 40), images have 10% of their pixels changed, then graph cuts is run to recover the image with a local potential of 0.9 for a matching assignment to the observed (and 0.1 for not matching) and a kernel of [.75 .25; .25 .75]. Displays before, noised, and after figures for each image.
2. demo_lattice: Modified version of Kevin's demo to compare BP to graph cuts.
3. gc_random_demo: graph cuts is run on a 7 by 7 lattice with hard coded local potentials and kernal. The resulting 0-1 matrix is output. To check that this matches the output of the C++ version of graph cuts, open C++\GraphCuts2\GraphCuts2.vcproj. In Visual Studio select Debug -> Start without debugging (build if neccessary). The output in the console window should match the output of gc_random_demo. This comparison can be done on random, not hard coded potentials by following the procedure described in the block comment in gc_random_demo.m.

• myCode/graph_cuts: Takes in potentials, computes optimal assignment using pot2flow, MaxFlows, reachable, and find_cut. Outputs optimal assignment in a matrix corresponding to the lattice.
• myCode/pot2Flow: Given potentials, constructs the flow network whose min cut will partition vertices into those assigned 0 and 1 in the optimal assignment.
• GrTheory/MaxFlows: Computes the max flow through the network.
• myCode/reachable: Determines saturated arcs and removes them from the network.
• myCode/find_cut: Finds all vertices reachable from the source vertex. These are assigned 0; unreachable vertices are assigned 1.
• myCode/potentials, myCode/noise: Helper functions for gc_image_demo.

Last Updated: December 11th, 4:42 PM, 2005