This is my final project for Image Processing course, which implements the Seam Carving technique by Shai Avidan and Ariel Shamir [1]. You can see the full report here (in Chinese).
There are many display devices with various resolutions in our life. Resizing images to fit different screen size while preserving prominent features, also known as image retargeting, is a hot topic in image processing research. Seam Carving is a novel image retargeting method based on seam removal or insertion. Simply put, Seam Carving finds least important pixels in an image and delete them. This method is simple yet powerful and has already been adopted in some commercial software, like Photoshop.
Seam Carving reduces image size by repeatedly remove vertical seams or horizontal seams from it. Every vertical seam is defined as a 8connected path running from the top of the image to the bottom, horizontal seam is defined similarly. Because vertical seam contains exactly one pixel on each row, deleting a vertical seam will reduce the image width by 1, and thus preserves image's rectangle shape.
Suppose I is a n×m size image, a vertical seam is defined as:
$$s^x=\{s_i_^x\}_^n_{i=1}=\{(x(i),i)\}_^n_{i=1}, s.t. ∀i, x(i)x(i1)≤1$$Seam Carving finds the least important seam, and the importance is characterized by an energy function. In the original paper, L_{1} norm of the image gradient is used. Intuitively, a pixel that is very different from its neirghbors is important.
$$e(\bo{I})=∂/∂x \bo{I}+∂/∂y \bo{I}$$Given the energy function, energy of a seam is just the sum of the pixels' energy on the seam. We want to find a seam with minimum energy. The paper uses dynamic programming to find it, a n×m matrix M stores the minimum energy of path that ends with pixel (i,j):
$$M(i,j)=e(i,j)+min(M(i1,j1),M(i1,j),M(i1,j+1))$$The minimum element in last row of matrix M is the endpoint of the seam that we are looking for, the seam is then constructed by backtracking.
When an image changes size in both dimensions, we need to find a optimal sequence for removing seams vertically or horizontally, the author also uses dynamic programming here. I didn't implement it so it's not discussed here. In my program, I just deleted seams alternatively in 2 directions.
Disclaimer: I don't own the images, I collect them either from Internet or from the authors for study purposes.
I try to improve the algorithm in two aspects, one is to employ a better energy function, the other is to use a greedy algorithm for finding target seam.
I found that the authors' usage of L1norm energy may not work well in some cases. The energy function concentrates energy on edges of objects, if the body of a object is of very low energy, a seam is very likely to pass through it, yielding unpleasant result. E.g.
[3] proposes to use Saliency Map as energy function, which can preserve object's structure better. But the disadvantage is that it will lead to blockish artifacts (see the spray for example), because it cannot preserve the edges well.
So I combined these two energy functions by weighting them carefully, the results below appear more natural.
More results:
L_{1} norm of gradient  Saliency Map  Combined energy function 
The original DP algorithm in the paper is limited in parallelism. Because each row depends on the row above, parallelism only exists between rows. I come up with a greedy algorithm, the idea is to binary partition the rows and construct seam by combining local minimums. Suppose there are 8 rows in total,
This method increases the parallelism between rows, since the steps required for synchronization between rows reduces from O(n) to O(log n). It boosts the performance a little in my GPU implementation. In addition, by using local minimums, the results turn out to be better than those of original DP algorithm in some cases. I suspect that the greedy method's usage of local minimums can preserve object's structure better.
Input


DP algorithm

Greedy algorithm

Input


DP algorithm

Greedy algorithm
