CS1699 Homework1 – Part IV (Seam Carving)

Please refer to 【http://people.cs.pitt.edu/~kovashka/cs1699/】

We are required to reproduce a paper regarding seam carving in our CS1699 course. The name of the paper is 【Seam Carving for Content-Aware Image Resizing】which is written by Shai Avidan and Ariel Shamir. Thus in this post, I will first introduce my understanding about this paper, then, give a implementation of my reproduce work (also, my home assignment).

Unlike the traditional image resizing method, seam carving does not crop an image from its border. The paper suppose that there may be very important information hiding in the border. Thus, a new approach is proposed to handle this issue, which is seam carving.

So, how to resize an image in this situation? A basic intuition is to find a vertical or horizontal line in the image containing the least information, e.g. we can use the entropy to measure the containing data, then find a least informative line and remove it.

The paper goes a step further, it does not search for a line, but for a seam. First, an energy image is computed (E(I) = sqrt(dx ^ 2 + dy ^ 2)), then, a dynamic programming algorithm is applied to this energy image in order to find the least informative seam. M(i, j)=e(i, j)+min(M(i−1, j−1), M(i−1, j), M(i−1, j+1)). Matrix M is called the cumulative image, backtrace technologies can be used here to trace for the principle route. Finally, a seam forms.

Compute Energy Image

Compute Cumulative Image

Backtrace for Seam

Iteratively Execute above Steps

 

Demo Result

12

Leave a Reply