CS129 / Project 3 / Seam Carving

1.Seam Carving

1.1 Background

To reduce size of images, there are 3 methods are used commonly: cropping, scaling down and retargeting. However, downsizing by cropping may cause lose of important information, especially when the cropping window is not big enough. And scaling down directly will change the ratio of the objects in images, which may cause some visual discomfort. While retargeting by seam carving can not only avoid lose of important part but also ensure the ratio of main object.

Original image
Cropping
Scaling
Retargeting

1.2 Algorithm

Shai Avidan and Ariel Shamir's paper introduced a way to retarget images by removing seams with the minimal energy. There are several methods to measure the energy of pixels, for example gradient magnitude, entropy and visual saliency.

Here is the algorithm:

  1. compute the original energy matrix of the image, that is, every element in the matrix is the energy value of according pixel in the image.
  2. compute the score matrix according to the original matrix we get in step 1. Here we have:
    3. 
%Pseudocode
if (the first row)
   score_matrix(row,col) = ori_energy(row,col)
elseif (the first column && not the first row)
   score_matrix(row,col) = ori_energy(row,col)+min(score_matrix(row-1,col), score_matrix(row-1,col+1))
elseif (the last column && not the first row)
   score_matrix(row,col) = ori_energy(row,col)+min(score_matrix(row-1,col-1), score_matrix(row-1,col))
else
   score_matrix(row,col) = ori_energy(row,col)+min(score_matrix(row-1,col-1), score_matrix(row-1,col), score_matrix(row-1,col+1))
  3. find the smallest value in the last row of the score_matrix and trace back up by finding the minimal value around 3 value above, until to the first row. That is the optimal seam with the lowest energy.
  4. remove the seam in the image according to the optimal seam we find in score_matrix.
  5. repeat step1-step4 until the image reaches the proper size.

1.3 Implementation

1.3.1 Obtain original energy matrix

To measure the energy, I used pixel's gradient magnitude by filtering the image with sobel filter. At the very beginning, I filtered image by using default sobel filter in Matlab(fspecial('sobel')) which only emphasizes the horizontal edges. So the final results were not satisfactory. To improve this, I transposed the sobel kernel to make it emphasize vertical edges and filtered the original image again. And I average the two results as my energy matrix, that is, energy = sqrt(Sobel_result_x^2+Sobel_result_y^2). Then I got the much better result images.

Original image
Horizontal edges
Both edges
1.3.2 Optimal seams order

When cutting both horizontal and vertical seams, how can we decide in what order those seams should be removed? Here I tried two ways: 1.carving all vertical seams firstly and then carving all horizontal seams. 2. using a transport map T which records the energy cost of each carving operation(mentioned in the paper chapter 4.2). In the method 2, I compute the T by using the formula:T(r,c) = min((T(r-1,c) + SeamEnergy(n-r-1,m-c)),(T(r,c-1) + SeamEnergy(n-r,m-c-1)), where T(r,c) means the minimal cost of removing r seams and c seams in horizontal and vertical direction. Then we trace from T(r,c) to T(0,0) to find the optimal carving order. Actually, comparing method 1 output with method 2 output, I found not much difference. For example, the second image below is the method 1 output and the third image is the method 2 output, both of them were cutting 200 pixels vertically and 250 pixels horizontally.

Original image
Vertical and horizontal
Optimal order

1.4 Result Images

1.4.1 Seam carving vertically
Original image
Seam carving image

As we can see above, the seam carving algorithm works pretty well in most of images except 'Monalisa'. The reason is that, as its gradient magnitude image shows, the gradients of the background are pretty high, especially compared with Monalisa's hair part. So when seam carving it, the background was not carved as we hoped, instead it removed the hair part and outer body part.

1.4.2 Seam carving vertically and horizontally
Original image
Carving vertically
Carving vertically and horizontally

2.Extra Credit

2.1 Image Enlarging

I implemented image enlarging by finding the the seam with lowest energy and average it with their left and right neighbors separately (or top and bottom neighbors when inserting horizontal seams). One thing have to be noticed is that if we find only one optimal seam and doing insertion and then do those two steps repeatedly, the output image will be creepy because we just choose that one seam every time. To improve this, I found first m optimal seams at one time and doing insertion one by one(m was the size we want to expand). During implementation, I used a path_shift matrix to record the changes of the coordinates after every insertion.

Result Images
Original image
Expanded image

2.2 Object Removal

To decide which part of the pixels should be removed, I made a mask in real-time by using getmask.m. After getting the original energy matrix, I changed the energy values under the mask to negative infinity and did seam carving until all pixels under the mask were removed. Then I enlarged the image to its original size by inserting seams. In most cases, removing objects by seam carving works well. But when the background of objects to be removed has high energy or continuity, the output results will be less realistic.

Original image
Seam carving
Seam inserting
Result Images
Original image
Removal image
Failure Images