Fun with seam cut and graph cut

Last Updated on February 28, 2014 by nghiaho12

This fun little project was inspired by a forum post for the Coursera course Discrete Inference and Learning in Artificial Vision.Β 

I use the method outlined inΒ Graphcut Textures: Image and Video Synthesis Using Graph Cuts.

The toy problem is as follows. Given two images overlaid on top of each, with say a 50% overlap, find the best seam cut through the top most image to produce the best “blended” looking image. No actual alpha blending is performed though!

This is a task that can be done physically with two photos and a pair of scissors.

The problem is illustrated with the example below. Here the second image I want to blend with is a duplicate of the first image. The aim is to find a suitable seam cut in the top image such that when I merge the two images it produces the smoothest transition. This may seem unintuitive without alpha blending but it possible depending on the image, not all type of images will work with this method.

apple_seamcut

By formulating the problem as a graph cut problem we get the following result.

graphcut_apple

and the actual seam cut in thin red line. You might have to squint.

graphcut_and_cut_line

If you look closely you’ll see some strangeness at the seam, it’s not perfect. But from a distance it’s pretty convincing.

Here are a more examples using the same method as above, that is: duplicate the input image, shift by 50% in the x direction, find the seam cut in the top layer image.

strawberry

graphcut_strawberry

This one is very realistic.

Who likes penguins?

penguins-795082

graphcut_penguin

Code

SeamCut.tar.gz

You’ll need OpenCV 2.x install.

I’ve also included the maxflow library from http://vision.csd.uwo.ca/code/ for convenience.

To run call

$ ./SeamCut img.jpg

14 thoughts on “Fun with seam cut and graph cut”

  1. Hi,
    I have tried your code with Visual Studio 2012 in Windows 7, OpenCV 2.4.8. After running the program, it can output :
    >> SeamCut.exe strawberry.jpg
    max flow: 32803

    Then the program failed.

    I think there are bugs between line 128 – 156.

    May you have a look at it?

    Thanks!

  2. Maybe some trivial changes:

    g.add_edge(idx, y * overlap_width + x + 1, cap0 + cap1, cap0 + cap1);
    may be modified as:
    g.add_edge(idx, idx + 1, (int)(cap0 + cap1), (int)(cap0 + cap1));

    g.add_edge(idx, (y+1)*overlap_width + x, cap0 + cap2, cap0 + cap2);
    maybe modified as:
    g.add_edge(idx, idx + overlap_width, (int)(cap0 + cap2), (int)(cap0 + cap2));

      1. Yes, that eliminate the double to int warnings.

        Or, define the GraphType template as:

        typedef Graph GraphType;

        Thanks for sharing!

      2. Hi Nghia,
        the ” are ignored. I just mean that change GraphType template parameters from int to double πŸ™‚

  3. Hi Nghia,
    I have another idea: may you extend your code to deal with below matters:
    ——————————–
    | 1 | 2 |
    |———————————
    | 3 | 4 |
    ———————————

    Original code can synthesis two images at horizontal direction.
    My figure means that the code can synthesis four images at horizontal and vertical directions.

    1. That’s also a reasonable idea. But right now I’d like to leave this code as it is. Any extension can be an excercise for the reader πŸ™‚

      1. Sounds good.
        Because your code has all the essential parts for that idea, so I will do the exercise.

  4. Maybe the statement “Mat no_graphcut(A.rows, A.cols * 2 – overlap_width, A.type());”
    should be “Mat no_graphcut(A.rows, A.cols + B.cols – overlap_width, A.type());”

    Because when A.cols != B.cols, the composite image column numbers is equals “A.cols + B.cols – overlap_width”.

Leave a Reply to nghiaho12 Cancel reply

Your email address will not be published. Required fields are marked *