Yan Li (yanli)

CS129 / Project 3 / Seam Carving

            

Goal of the project

The goal of this project is to implement Seam Carving, which is a content-based technique for scaling an image.

This technique is introduced in 2007 by Shai Avidan and Ariel Shamir.

Algorithms Used: Dynamic Programming, Gradient Filtering.

 

My Works

1 Optimal seam finding

    2 Horizontal and vertical seams

    3 Removing seams

    4 Failure case and discussion

    5 Scaling up using seam carving (Extra Credit)

    6 Object removal and protection (Extra Credit)

    7 Forward energy formulation (Extra Credit)

 

Basic Algorithm

 

Unlike scaling, which stretches out the whole images and brings apparent artifacts; or cropping, which crops the specific region regardless of whether the cropped content is important or not, seam carving is a technique that can preserve the important details in an image. Since our humans are sensitive to gradient changes rather than the pixel itself, seam carving cuts those seams with lowest gradient energy that we may not notice the changes after carving. In order to make the image after carving aligned, we cut those vertical seams which have only one pixel in each row if we want to scale down in X direction. As for cutting those horizontal seams, the method is the same with cutting vertical seams except that we must firstly transpose the image and after seam carving, we transpose the image back to the normal direction.

 

The basic algorithm for seam carving is quite simple, I firstly use a gradient filter to generate the energy image of the test image, and then use dynamic programming to get a score matrix. After doing that, I firstly find the lowest value in the bottom row of the score matrix, and then trace back up by following the smallest value in any of the positions above that are valid for a seam (top right, top, and top left).

 

     The pseudo code for seam carving is the following:

    %  if horizontal_seam

    %    img = transpose_image(img);

    %  end

    % 

%  for i: cut_columns

    %    energy = image_energy(img);

    %    path = find_min_path(energy);

    %    img = remove_x_coords(img, path);

    %  end

    %  if horizontal_seam

    %    img = transpose_image(img);

% end       

 

    In the project, I didn’t use the code structure like the above pseudo code. The TAs have provided us with a good function that can build the table of removal order, which is quite useful for other operations like drawing the seams. This may spend more time for one image, but I think it’s still in an accepted speed.

 

 

Results in a table

     Here are some of the results that the 200 columns of the original images are cut.

 

Here are some of the results that the 80 rows of the original images are cut.

 

Scaling up

    Seam carving can be used for scaling up as well. The technique is still quite easy: I just extract those seams with lowest energy, and copy them once. For example, if I want to scale up to 1.5 times the size of the original one, the seams that need to be copied should be 1.5*src_width – src_width. Here are the results of the comparison between scaling with seam carving and naively scaling up by 1.5 times, notice that some of the results are not very good.

 

 

 

Object Removal and protection

    Seam carving can also be used for object removal and protection. The user firstly specifies two regions: one for protection and the other one for removal. The region for protection will be set to very large value of energy, while the region for removal will be set to very small value of energy. By doing that, the min path for seam will primarily choose those position passing through the removal region while pass around the region of protection. Here are some examples, the green region is the region of protection, while the red region is removal region:

Notice that the girl in the image is perfectly preserved, while the house is removed.

    Notice that the boat is removed, while the mountain is preserved perfectly.

 

    Object removal may generate some artifacts as well because of the image content is continuous. After removing the object, it won’t be seamless any longer. The following result is one of the worst object removals.

 

Forward energy

   In some cases, using traditional backwards removal method will generate some new energy, since the new energy won’t be taken into account. Using forward energy to calculate the score matrix will be a good method to fix that problem. Here is the comparison between using forward energy and backward energy.

   

The formulation for the old backward energy is:

 

M(i,j) = E(i,j) +

  

The formulation for the new forward energy is:

M(I,j) = min

 

 

Using backward energy:

Using forward energy:

 

 

 

Using backward energy

Using forward energy:

 

 

 

Failure cases and analysis:

As you have seen above, some of the results are very bad. The reasons for this are complex, and I summarize the reasons in the following:

 

1 The seam carving destroys the continuity of the image:

    

(Even though successfully removing the tree on the right side, the sky and the grass are connected. Even if I can try to fill out those missed seams by scaling up, the problem cannot be solved as well)

 

2 The seam carving destroys the gradient of the image:

    

(Do you notice the strange mountain? The gradient of the image is not preserved）

 

3 The seam carving destroy some important content of an image:

  

(The hair of Monalisa is totally removed. This is because the energy of hair is very low. To solve this, maybe add a region of protection is OK, or try using a face detector).