The following problem appeared as an assignment in the ** Algorithm Course** (

*) at*

**COS 226***taught by*

**Princeton University***. The following*

**Prof. Sedgewick***description*of the problem is taken from the assignment itself.

The Seam Carving Problem

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

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

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

- 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),
the*seam carving**preserves*(*most interesting features**aspect ratio*,*set of objects present*, etc.) of the image.

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

and**Finding**a**removing**involves three parts:**seam****Energy calculation***.*The first step is to calculate the

of a*energy*, which is a measure of its*pixel**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

, which is described below.*dual-gradient energy function*With the**Computing the energy of a pixel**., the*dual-gradient energy function*of**energy***pixel**(x,y*is given by the following:*)***Seam identification**.The next step is to find a

of*vertical seam*. (Finding a**minimum total energy***horizontal seam*is analogous.) This is similar to thein an**classic shortest path problem***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
can be found using*optimal seam*. 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*dynamic programming**pixel (i, j)*:

- The
*Seam removal.*The final step is

from the image all of the**remove***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

*algorithm implementation. The*

**seam carving***(the*

**shape***of the*

**transpose***is reported) and*

**image shape***of the*

**size****(in terms of the**

*image***taken by python**

*memory***as**

*np array***, to store the image) is also reported for each iteration of the algorithm. As can be seen, the algorithm**

*float**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

*, Kolkata along with the removed vertical seams with*

**Dakshineswar Temple****.**

*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**