Graphcut

Steve Gomez (steveg) . February 25, 2010

In this project, we find optimal seams for stitching using the graphcut technique described in "Graphcut Textures: Image and Video Synthesis Using Graph Cuts", by Kwatra et al, in SIGGRAPH 2003.

Algorithm implementation

The core of the algorithm is formulating the labeling problem ("should pixel p come from image A or image B?") as finding a min-cut between regions of interest in each image. The actual min-cut dynamic programming code is graciously provided to us by Michael Rubinstein's maxflow Matlab library. So our task is to form the adjacency constraint matrix and sink-source data matrix to pass off to the solver. The output is a max flow (which we don't really care about, aside from it saying something about the quality of the best cut it chooses) and a vector of labels indicating our pixel partitions from the two images we want to composite.

The easy part is collecting the data matrix for the source and sink. I have users interactively select a polygon of interest in each of the photos (with the option to store these masks and have them automatically loaded in the future). I then weight each pixel selected with a high value, leaving the rest as 0. So we now have weights for each pixel location, in each of the two images we are compositing. The data matrix has dimensions [m*n 2], for image size m*n, and we fill this by copying our weights from each image into the two column vectors. In other words, the (i,j)th pixel in our output image is given source weight D(ind(i,j),1) and sink weight D(ind(i,j),2), for the constructed data matrix D.

The constraint matrix is a sparse matrix whose entries say something about the color difference between adjacent pixels. I implemented the sparse matrix similar to the previous assignment -- constructing the vectors of values and building it all at once to be efficient. I fill this matrix out by looping through the pixel locations in the output image, computing sum of squared differences from R, G, and B channels between neighbor pixels. This basically follows the pseudocode on the handout. At the end, we have a symmetric matrix that is mostly 0 (i.e. cells corresponding to non-adjacencies) but contains our arc constraints. Finding the min-cut will try to avoid locations corresponding to highly varied color differences, which is like finding a seam that leaves similar colors intact or aligned. With this 'best cut', I fix color constancy by using Poisson blending in the composite (without mixed-gradient transparency, because the graph cut should already be creating clean borders).

Building panoramas with Graphcut

One application I explored was using the graphcut algorithm to stitch together panoramas. Panorama stitching can be thought of as matching textures along the overlap of the frames. I've got two examples I tried below. Both came out surprisingly well, but as I explain below, we expect good results when the frames are well-aligned (which I did, approximating the offsets). One thing that graphcut succeeded on was good seams around minor rotation/perspective issues.

Brown, CIT 5th floor balcony

UIUC north campus

One difficulty is that we still need to align the photos if we want a convincing stitching. That almost makes the graphcut trivial, in the sense that if you had a perfect alignment with a working panorama, the seam would already be well-defined. In practice, the masks that graphcut produced on the panoramas were not purely vertical cuts -- so maybe the algorithm is actually selecting a better-than-natural composite!

Challenges, extensions

One feature to make this run more smoothly would be automatic detection of regions of interest in the source images. We could imagine an automatic, context-aware process that selects salient features (like faces) for the source and sink pixels. I was hoping to give that a try for extra credit, but ran out of time. Similarly, automatic alignment of the images before compositing would be very helpful, if we had a smart way of doing that.