The following problem appeared as an assignment in the Algorithm Course (COS 226) at Princeton University taught by Prof. Sedgewick.  The following description of the problem is taken from the assignment itself.

The Seam Carving Problem

• Seam-carving is a content-aware image resizing technique where the image is reduced in size by one pixel of height (or width) at a time.

• A vertical seam in an image is a path of pixels connected from the top to the bottom with one pixel in each row.

• A horizontal seam is a path of pixels connected from the left to the right with one pixel in each column.

• Although the underlying algorithm (the original paper from MERL) is simple and elegant, it was not discovered until 2007.  Now, it is now a core feature in Adobe Photoshop and other computer graphics applications.

• Unlike standard content-agnostic resizing techniques (such as cropping and scaling), seam carving preserves the most interesting features (aspect ratio, set of objects present, etc.) of the image.

• In this assignment, a data type needs to be created that resizes a W-by-H image using the seam-carving technique.

• Finding and removing a seam involves three parts:
  
  
  1. Energy calculation.

     The first step is to calculate the energy of a pixel, which is a measure of its importance—the higher the energy, the less likely that the pixel will be included as part of a seam (as you will see in the next step).

     In this assignment, we shall use the dual-gradient energy function, which is described below.

     Computing the energy of a pixel. With the dual-gradient energy function, the energy of  pixel (x,y) is  given by the following:

     

  2. Seam identification.

     The next step is to find a vertical seam of minimum total energy. (Finding a horizontal seam is analogous.) This is similar to the classic shortest path problem in an edge-weighted digraph, but there are three important differences:

     • The weights are on the vertices instead of the edges.
     • The goal is to find the shortest path from any of the W pixels in the top row to any of the W pixels in the bottom row.
     • The digraph is acyclic, where there is a downward edge from pixel (x, y) to pixels (x − 1, y + 1), (x, y + 1), and (x + 1, y + 1). assuming that the coordinates are in the prescribed ranges.
     • Also, Seams cannot wrap around the image (e.g., a vertical seam cannot cross from the leftmost column of the image to the rightmost column).
     • As described in the paper, the optimal seam can be found using dynamic programming. The first step is to traverse the image from the second row to the last row and compute the cumulative minimum energy M for all possible connected seams for each pixel (i, j):

       

  3. Seam removal.

     The final step is remove from the image all of the pixels along the vertical or horizontal seam.

Results with a few images

The following image is the original 507×284 pixel input image taken from the same assignment. The next few images and animations show the outputs of the seam carvingalgorithm implementation. The shape (the transpose of the image shape is reported) and size of the image (in terms of the memory taken by python np array as float, to store the image) is also reported for each iteration of the algorithm. As can be seen, the algorithm resizes the image by removing  the minimum energy vertical (and horizontal seams) iteratively one at a time, by keeping the main objects as is.

Input Original Image

       

Removing the Vertical Seams

After Removing 200 Vertical Seams

Removing the Vertical and the Horizontal Seams in alternating manner

After Removing 100 Vertical Seams and 100 Horizontal Seams

The following is the original 1024×576 image of the Dakshineswar Temple, Kolkata along with the removed vertical seams with content-aware resizing.

Output image after removing 500 Vertical Seams

 

The next image is the original dolphin 239×200 image taken from the paper, along with the removed vertical seams with content-aware resizing.

                   

           After removing 112 Vertical Seams

 

The next image is the original 750×498 bird image taken from the paper, along with the removed vertical seams with content-aware resizing.

         After Removing 297 Vertical Seams

 

The next image is the original 450×299 sea image taken from the paper, along with the removed vertical seams with content-aware resizing.

 

The next image is the original 628×413 cycle image taken from the paper, along with the removed vertical seams with content-aware resizing.

After Removing 99 Vertical Seams

 

The next image is the original 697×706 Fuji image again taken from the paper, along with the removed vertical seams with content-aware resizing.

 

               After Removing 282 Vertical Seams

 

Object Removal

The same technique can be applied with mask to remove objects from an image. For example. consider the following image of the shoes taken from the same paper.

Let’s use a black mask to remove a shoe that we don’t want, as shown in the next figure.

Finally the vertical seams can be forced to go through the masked object, as shown in the next animation,  in order to remove the masked object completely just by using context-aware resizing.

Output after removing the shoe with content-aware image resize algorithm