Home » Uncategorized

Seam Carving: Using Dynamic Programming to implement Context-Aware Image Resizing in Python

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 widthat a time.
  • vertical seam in an image is a path of pixels connected from the top to the bottom with one pixel in each row.
  • 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 ratioset of objects present, etc.) of the image.
  • In this assignment, a data type needs to be created that resizes 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:

      f17.png

    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 (xy) to pixels (x − 1, y + 1), (xy + 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):

        f18

    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

       HJoceanSmall.png


Removing the Vertical Seams

energy_000HJoceanSmall
vseam

After Removing 200 Vertical Seams

seam_199_vHJoceanSmall

energy


Removing the Vertical and the Horizontal Seams in alternating manner

vhseam
After Removing 100 Vertical Seams and 100 Horizontal Seams

seam_099_hHJoceanSmall

seam_099_vHJoceanSmall

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

temple

energy__temple
vseamtemple (2).gif

Output image after removing 500 Vertical Seams

seam_499_vtemple

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

                   dolphin

energy_000dolphin.jpg

vseamdolphin

           After removing 112 Vertical Seams

seam_113_vdolphin

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

bird2.png

energy_000bird2.png

vseambird
         After Removing 297 Vertical Seams

seam_299_vbird2

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

sea2.png

vseamsea2

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

cycle.png

energy_000cycle

vseamcycle

After Removing 99 Vertical Seams

seam_199_vcycle

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.

Fuji

vseamfuji

               After Removing 282 Vertical Seams

seam_280_vFuji

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.

shoes

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

masked_shoes.jpg
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.

or_shoes.gif

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

seam_115_vshoes.jpg

Leave a Reply

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