Graph Cut __ Writeup

Sam Potasznik (spotaszn)
January 29, 2010

Algorithm

For this project, I followed the basic algorithm as described in the handout and in the Kwatra, et al. paper. I constructed a matrix A such that A(i,j) represented the weight between pixels i and j. I defined weight as being the sum of the squared differences between pixel i in the source and target image and pixel j in the source and target image. This matrix was then used by the max_flow algorithm to produce a labeling of each pixel as coming from the source or the sink. To help facilitate this process, I constrained pixels designated by the user as coming from one image or the other by setting their label before the max_flow algorithm had a chance to work.

Results Images

Graph Cut Graph Cut + Poisson

Sweatshirt Camouflage

The following image set shows me trying to camouflage into a set of tie-dyed sheets. Luckily, I was in posession of a tie-dyed sweatshirt. Shown are results from simple cutting and pasting, followed by the graph cut algorithm, graph cut coupled with Poisson blending, and then Poisson blending by itself.

These results show the plusses and minuses of compositing images using graph cut. One major aspect is that colors from the source are not corrected. This is a plus in that my face still looks like my face, not like a ghost. Additionally, I am somewhat blended into the bed through graph cut's seam selection. Definitely, using Poisson blending makes me look more blended into the bed. However, the downside is that I look like a ghost. Which actually may be good for camouflaging.

Cut + Paste Graph Cut Graph Cut + Poisson Just Poisson

Apple Door

This next set of images is an attempt to blend an apple into my dorm room's door. For the most part Poisson seems to do a better job than graph cut. Because the apple's and door's colors are similar, but not extremely similar, Poisson does a much better job of covering up differences than choosing a seam between two somewhat dissimilar regions

Cut + Paste Graph Cut Graph Cut + Poisson Just Poisson

Sleepin' Dogs

This is probably my most successful graph cut image. In the image that was only graph cut, much of the seem is impossible to find. Additionally, there is a nice effect of my pillow extending outwards. Again though, we see the algorithm fail when regions are too dissimilar. Around the carving's nose and my forehead, the seem is very noticable. This is because the nose of the carving is under the mask in the source. Leaving the nose out of the mask produced a better seam, but left out the nose. It was, literally, cutting of the nose to save my face.

Cut + Paste Graph Cut Graph Cut + Poisson Just Poisson

Bee's Knees

For this image, I used a slightly different technique. I wanted to match up actual beeswax with the beeswax pattern found in Minden Hall bathrooms. The problem presented here is that the hexagon edges are light in the actual beeswax and dark in the tiles, and the reverse of true of the hexagon areas. I figured to get around this, I could compare not the pictures themselves, but the images after run through edge detection filter. This novel approach yielded, shall we say, "novel" results. The bottom row is the results of the edge detect and filters, and the top row is the when the mask from those results are applied to the real images.

Cut + Paste Graph Cut Graph Cut + Poisson Just Poisson