Seam Carving for Content-Aware Image Resizing (CAIR)

This is a reimplementation of the seam-carving algorithm described in a 2007 ACM SIGGRAPH paper from S. Avidan and S. Amir done entirely in MATLAB.

License

MIT

Features

• Resize an image both horizontally & vertically
• Dynamic programming in 8-connected pixel paths
• Sobel operator used for better gradient thresholding
• Multidirectional 'low-cost' energy maps
• Backtracking and seam-by-seam carving output

How does it work?

Calculating the Energy of an Image

• Gradients are first computed using the Sobel operator on the input image for the purpose of energy calculation. By taking derivatives between adjacent pixels, this algorithm is able to identify sharp changes in pixel values, better defined as 'edges'. A Sobel filter is applied through convolution to accomplish this on the input image, demonstrated on a 3x3 grid:

• This is the preliminary step and allows for rough identification of objects, which will later be used to determine optimal pixel paths. Shown below is the result of mass-applying the convolution across the whole input image to generate a gradient map:

Input Image	Gradient Map

Generating Low-Cost Energy Matrices

• Once a gradient map has been produced, the process to identify pixel paths is made easier. The next step is generating heatmaps, in both the vertical and horizontal directions, to represent the low-cost energy matrix.

Horizontal Heatmap	Vertical Heatmap

• These heatmaps showcase the cumulative minimum energy for any pixel at (i,j) in either the horizontal or vertical directions. In the above images, a bottom-up matrix has been generated that considers the energies of all 3 neighboring pixels, summing energies as the image is parsed.

• For generating an energy map in the horizontal direction, this formula is used for any (i,j) pixel:

M(i,j) = Energy(i,j) + min(M(i-1,j-1), M(i,j-1), M(i+1,j-1))

• And, for the vertical direction, the below formula is used for all (i,j) pixels:

M(i,j) = Energy(i,j) + min(M(i-1,j-1), M(i-1,j), M(i-1,j+1)) 

Optimal Pixel Paths Using Dynamic Programming

• After the low-cost energy matrix is generated, pixel paths can be computed through the image, defined to be 'low-energy' seams. Let's walkthrough an example of finding a pixel path in the vertical direction. We start with E, our energy matrix:

      1    3    0
E  =  2    8    9
      5    2    6

• Then, the M (low-cost energy) matrix is generated as a heatmap, with the aforementioned M functions:

      1     3     0
M  =  3     8     9
      8     5    14

• Finally, a pixel path is identified using a low-cost approach from the bottom-up:

      [1]   3     0
M  =  [3]   8     9
       8   [5]   14

• This leaves us with our optimal path, 5 -> 3 -> 1 in the M matrix, which is 2 -> 2 -> 1 in the E matrix. From our original input image, the first vertical seam to be removed would look like this:

Demo

Image Width Reduction

• Here's a demonstration of vertically carving seams. Notice how it carves around the Porsche 911, removing low-energy paths:

Image Height Reduction

• And here's what it looks like in the horizontal direction:

Image Width and Height Reduction

• Finally, here's what carving seams in both the horizontal and vertical directions looks like:

More Examples

Let's look at a few more naive (crop) resizes vs CAIR.

Input Image	Naive Resize	CAIR

Input Image	Naive Resize	CAIR

Input Image	Naive Resize	CAIR

For visualization purposes, here are the above images overlaid with all the seams that were removed:

Boat Sunset	Surfer in Ocean	Austin, Texas

Deployment

To test this project, first read in an image in MATLAB:

>> img = imread("imgname.jpg");

Then, use the reduce_img_size(img, width, height) function to change an image's dimensions:

>> new_img = reduce_img_size(img, 400, 300);
>> imshow(new_img);

To visualize the seams that were removed, use the display_seams(rgb_img, vert, horiz) function:

>> seam_img = display_seams(img, 400, 300);
>> imshow(seam_img);

Acknowledgements

• Avidan, S., & Shamir, A. (2007). Seam carving for content-aware image resizing. In ACM SIGGRAPH 2007 papers (pp. 10-es).