Seam carving with OpenCV, Python, and scikit-image

seam_carving_animation

Easily one of my all-time favorite papers in computer vision literature is Seam Carving for Content-Aware Image Resizing by Avidan and Shamir from Mitsubishi Electric Research Labs (MERL).

Originally published in the SIGGRAPH 2007 proceedings, I read this paper for the first time during my computational photography class as an undergraduate student.

This paper, along with the demo video from the authorsmade the algorithm feel like magic, especially to a student who was just getting his feet wet in the world of computer vision and image processing.

The seam carving algorithm works by finding connected pixels called seams with low energy (i.e., least important) that traverse the entire image from left-to-right or top-to-bottom.

These seams are then removed from the original image, allowing us to resize the image while preserving the most salient regions (the original algorithm also supports adding seams, allowing us to increase the image size as well).

In the remainder of today’s blog post I’ll discuss the seam carving algorithm, how it works, and how to apply seam carving using Python, OpenCV, and sickit-image.

To learn more about this classic computer vision algorithm, just keep reading!

Looking for the source code to this post?
Jump right to the downloads section.

Seam carving with OpenCV, Python, and scikit-image

The first part of this blog post will discuss what the seam carving algorithm is and why we may prefer to use it over traditional resizing methods.

From there I’ll demonstrate how to use seam carving using OpenCV, Python, and scikit-image.

Finally, I’ll wrap up this tutorial by providing a demonstration of the seam carving algorithm in action.

The seam carving algorithm

Introduced by Avidan and Shimar in 2007, the seam carving algorithm is used to resize (both downsample and upsample) an image by removing/adding seams that have low energy.

Seams are defined as connected pixels that flow from left-to-right or top-to-bottom provided that they traverse the entire width/height of the image.

Thus, in order to perform seam carving we need two important inputs:

  1. The original image. This is the input image that we want to resize.
  2. The energy map. We derive the energy map from the original image. The energy map should represent the most salient regions of the image. Typically, this is either the gradient magnitude representation (i.e., output of Sobel, Scharr, etc. operators), entropy maps, or saliency maps.

For example, let’s take a look at the following image:

Figure 1: Our input image to the seam carving algorithm [source: Wikipedia].

Figure 1: Our input image to the seam carving algorithm [source: Wikipedia].

Using this image as an input, we can compute the gradient magnitude to serve as our energy map:

Figure 2: Computing the gradient magnitude representation of of the input image. This representation will serve as our energy map [source: Wikipedia].

Figure 2: Computing the gradient magnitude representation of of the input image. This representation will serve as our energy map [source: Wikipedia].

Given our energy map we can then generate a set of seams that either span the image from left-to-right or top-to-bottom:

Figure 3: Generating seams from the energy map. Low energy seams can be removed/duplicated to perform the actual resizing [source: Wikipedia].

Figure 3: Generating seams from the energy map. Low energy seams can be removed/duplicated to perform the actual resizing [source: Wikipedia].

These seams are efficiently computed via dynamic programming and are sorted by their energy. Seams with low energy are placed at the front of the list while high energy seams are placed at the back of the list.

To resize an image we either remove seams with low energy to downsample an image or we duplicate seams with low energy to upsample the image.

Below is an example of taking the original image, finding the seams with the lowest energy, and then removing them to reduce the final size of the output image:

Figure 4: Removing low energy seams from an image using the seam carving algorithm [source: Wikipedia].

Figure 4: Removing low energy seams from an image using the seam carving algorithm [source: Wikipedia].

For more information on the seam carving algorithm, please see the original publication.

Why use traditional seam carving over traditional resizing?

Keep in mind that the purpose of seam carving is to preserve the most salient (i.e., “interesting”) regions of an image while still resizing the image itself.

Using traditional methods for resizing changes the dimensions of the entire image — no care is taken to determine what part of the image is most or least important.

Seam carving instead applies heuristics/path finding derived from the energy map to determine which regions of the image can be removed/duplicated to ensure (1) all “interesting” regions of the image are preserved and (2) this is done in an aesthetically pleasing way.

Note: Preserving the most interesting regions of an image in an aesthetically pleasing manner is a lot harder than it sounds. While seam carving may seem like magic, it’s actually not — and it has its limitations. See the “Summary” section for more information on these limitations.

To compare traditional resizing versus seam carving, consider the following input image:

Figure 5: An example image to resize.

Figure 5: An example image to resize.

This image has a width of 600 pixels and I would like to resize it to approximately 500 pixels.

Using traditional interpolation methods my resized image would look like this:

Figure 6: Resizing an image using traditional interpolation techniques.

Figure 6: Resizing an image using traditional interpolation techniques. Notice how the height changes along with the width to retain the aspect aspect ratio.

However, by applying seam carving I can “shrink” the image along the horizontal dimension and still preserve the most interesting regions of the image without changing the image height:

Figure 7: Resizing the image using seam carving.

Figure 7: Resizing the image using seam carving.

Utilizing seam carving in computer vision and image processing

In this section I’ll demonstrate how to use seam carving with OpenCV, Python, and scikit-image.

I’ll assume you already have OpenCV installed on your system — if not, please refer to this page where I provided resources to install OpenCV on many different operating systems.

From there, you should ensure you have scikit-image installed as well. This page provides more information on installing scikit-image, but for most systems you can use  pip :

Let’s go ahead and see how we can apply seam carving to our own images.

Open up a new file, name it seam_carving.py , and insert the following code:

Lines 2-5 import our required Python packages while Lines 8-13 parse our command line arguments. This script will require one argument followed by a second optional one:

  • --image : The path to the input image we want to apply seam carving to.
  • --direction : The direction in which we’ll apply seam carving. A value of vertical  will adjust the image width while a value of horizontal  will adjust the image height. We default the carving direction to vertical .

Next, let’s load our input image from disk, convert it to grayscale, and compute the Sobel gradient magnitude representation (i.e., our energy map):

In order to apply seam carving we’ll be using the implementation inside the scikit-image library. The seam_carve  function accepts four required parameters:

  1. The input image  that we are applying seam carving to.
  2. An energy map.
  3. The direction in which we’ll be applying seam carving (either horizontal or vertical).
  4. The number of seams to remove. At this point in time the seam_carve  function only supports downsampling images — no upsample support is provided.

To demonstrate seam carving in action, let’s loop over a number of seams to remove:

We call the seam_carve  function on Lines 33 and 34, removing the current number of numSeams .

The new carved image dimensions are printed to our terminal on Lines 35-37.

We also display the seam carved image to our screen on Lines 40 and 41.

Seam carving results

To give this seam carving example a try for yourself, be sure to download the source code and example image using the “Downloads” section at the bottom of this blog post.

From there, execute the following command:

Figure 8: (Left) The original input image. (Right) Removing vertical seams from the image, thereby decreasing the image width.

Figure 8: (Left) The original input image. (Right) Removing vertical seams from the image, thereby decreasing the image width.

On the left you can see the original input image — a photo of Bryce Canyon, one of the most beautiful National Parks to visit in the United States. Then on the right we have the seam carved image. As you can see, we have removed vertical seams from the image, thereby decreasing the image width.

We can reduce the image height by removing horizontal seams:

Figure 9: (Left) The original image. (Right) Removing horizontal seams from the image to decrease height.

Figure 9: (Left) The original image. (Right) Removing horizontal seams from the image to decrease height.

I have also included a GIF animation below that demonstrates seam carving one pixel at a time to give you a better feel for the algorithm:

Figure 10: Applying seam carving to an image using OpenCV, Python, and scikit-image.

Figure 10: Applying seam carving to an image using OpenCV, Python, and scikit-image.

Summary

In today’s blog post I discussed the seminal seam carving algorithm used for content-aware resizing of images.

This is a classic algorithm in computer vision literature, so if you haven’t read the original publication, I suggest you add it to your reading list.

Inside the paper Avidan and Shimar demonstrate that seam carving can not only be used for reducing image size, but also for increasing image size as well; however, the scikit-image implementation currently only supports downsampling.

While this algorithm may have felt like “magic” to myself as an undergraduate, I eventually learned there is no such thing as magic in the computer vision world — every algorithm has its limitations.

For seam carving, these limitations often demonstrate themselves as less than visually appealing results where important semantic information of the image is partially destroyed or cut out entirely. A great example would be applying seam carving to an image that contains faces and seams from the faces are removed.

To get around this we can annotate our image to provide “hints” to the seam carving algorithm, ensuring the labeled regions are not cut during the seam carving process. In an ideal world, we could provide energy maps that better reflect the salient regions of the image we wish to keep, thereby requiring no modification to the actual seam carving algorithm.

Personally, I’m interested to see the future landscape of seam carving. With deep learning algorithms used for tasks such as saliency detection, these salient maps can then be used for seam carving. We may eventually see an end-to-end seam carving network.

Anyway, I hope you enjoyed the discussion of this classic computer vision paper!

To be notified when future blog posts go live, be sure to enter your email address in the form below.

Downloads:

If you would like to download the code and images used in this post, please enter your email address in the form below. Not only will you get a .zip of the code, I’ll also send you a FREE 11-page Resource Guide on Computer Vision and Image Search Engines, including exclusive techniques that I don’t post on this blog! Sound good? If so, enter your email address and I’ll send you the code immediately!

, , ,

18 Responses to Seam carving with OpenCV, Python, and scikit-image

  1. Filip Kubicz January 23, 2017 at 12:42 pm #

    Thanks Adrian! I cannot see much use in actual vision system, but it can be great way to edit photographs or movies with important objects which must stay, but you have to resize the frame.

    • Adrian Rosebrock January 24, 2017 at 2:26 pm #

      Absolutely. The original thought behind the implementation was to use algorithms such as seam carving to help make images more displayable on small screen devices.

  2. Miguel January 23, 2017 at 1:52 pm #

    Impresionante. I don’t know this method. Is there a way to detect if it has been applied this technique on an image without knowing the original image?

    • Adrian Rosebrock January 24, 2017 at 2:25 pm #

      Without having the original image it would be challenging to determine if seam carving had been applied unless there was obvious visual artifacts after applying seam carving.

  3. Hilman January 24, 2017 at 12:27 am #

    Wow! This algorithm is really cool!

    • Fredrik January 25, 2017 at 2:58 pm #

      Agree, very nice 🙂

  4. Safwan Erooth January 24, 2017 at 2:13 pm #

    Really interesting write-up. The effort you take to write and the kind of details you share are really great. Keep up the good work.

    • Adrian Rosebrock January 24, 2017 at 2:33 pm #

      Thank you for the kind words Safwan, I appreciate it 🙂

  5. Utkarsh Chauhan January 25, 2017 at 8:02 am #

    Great algorithm. I tried it on one of my test images (width = 600, h = 400) and started founding visual artefacts at h = 380.

    • Adrian Rosebrock January 26, 2017 at 8:23 am #

      Visual artifacts can and will happen. The downside is that the artifacts are dependent on the input image. Dimensions that work for one image will not work for others. When this happens you can supply ROIs to the seam carving algorithm to specify “don’t touch this area” or the algorithm can be updated to be non-greedy and instead “look ahead” and what removing a given seam may do to the aesthetics of the image. Refer to the original publication for details on this.

  6. Marco January 27, 2017 at 2:55 am #

    I’m sorry, i’m having troubles with the:
    ap.add_argument(“-i”, “–image”, required=True, help=”path to input image file”)
    Where exactly i have to put the path.

    • Adrian Rosebrock January 28, 2017 at 6:57 am #

      Hey Marco — you don’t need to edit any code. You need to supply the path via command line argument, like this:

      $ python seam_carving.py --image bryce_canyon.jpg

      I would suggest you read up on command line arguments before you continue.

  7. Andy Traumüller January 27, 2017 at 7:48 am #

    Have you thought about using keras to even improve the quality of the seaming?

  8. JJ January 29, 2017 at 10:58 am #

    It is esay to get distorted.

  9. Helia January 31, 2017 at 7:42 am #

    Hi Adrian;

    Thank you for your interesting tutorials. May I request you for a tutorial on how to plot/monitor accuracy and loss in Keras. I want to visualise in real time the processing of training my dataset.

    Thanks.

    • Adrian Rosebrock February 1, 2017 at 12:55 pm #

      Absolutely, I will certainly do that. I also demonstrate how to plot/monitor accuracy in real-time inside my upcoming deep learning book.

  10. Dean February 11, 2017 at 8:24 pm #

    Hello Adrian,

    I have a question about the scikit-image installation. When I run ‘pip install scikit-image’ inside of my virtual environment the download bar fills up but sklearn or scipy are not available when I try to import them. Although, when I am outside of my virtual environment I am able to import scipy and sklearn but not use opencv. Do you have any ideas why I would be encountering this problem? Any help would be much appreciated.

    Thanks,
    Dean

    • Adrian Rosebrock February 13, 2017 at 1:46 pm #

      Hey Dean — it sounds like you have installed some packages into your global system Python and then some packages into your virtual environment. I would suggest you access your virtual environment and then install NumPy and SciPy followed by scikit-learn:

       workon your_env_name
      $ pip install numpy scipy
      $ pip install -U scikit-image

Leave a Reply