﻿ Seam Carving

# Seam Carving

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).

## Introduction

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.

## Algorithm

Seam Carving reduces image size by repeatedly remove vertical seams or horizontal seams from it. Every vertical seam is defined as a 8-connected 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.

### Formal definition of a seam

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(i-1)|≤1\$\$

### Energy Function

Seam Carving finds the least important seam, and the importance is characterized by an energy function. In the original paper, L1 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}|\$\$

### Searching the optimal seam

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(i-1,j-1),M(i-1,j),M(i-1,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.

### Optimal seam removal sequence

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.

## Results

Disclaimer: I don't own the images, I collect them either from Internet or from the authors for study purposes.

Note how objects are compressed towards the center while the image still appears natural.

## My Experiments

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.

### Energy Function

I found that the authors' usage of L1-norm 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.

The energy inside dolphin's body is so low(black in the right-most image) that seam may pass through it.

[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 block-ish artifacts (see the spray for example), because it cannot preserve the edges well.

Saliency map is not good at preserving small edges

So I combined these two energy functions by weighting them carefully, the results below appear more natural.

The combined energy function works best.

More results:

Input
 L1 norm of gradient Saliency Map Combined energy function

### Greedy algorithm for seam searching

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,

• In the first step I compute minimum energy for elements in row 2,4,6,8, by choosing among the three neighboring pixels on their above rows
• Then I link row 2 and 3, row 6 and 7 similarly
• Finally I link row 4 and 5.

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

## Future Work

• As seen in some results, seam carving may introduce some noticeable edges to the image, this is because it merely removes seams with minimum energy, without considering the new energy introduced into the image. [2] accounts for this energy increase by using a so-called Forward Energy. I will try it in the future.
• Experiment more energy functions.
• Improve the optimal seams removal sequence computation to make the program run at interactive rates.

## Reference

1. Shai Avidan and Ariel Shamir, “Seam Carving for content aware image resizing”, ACM Transactions on Graphics (SIGGRAPH), vol. 26, no. 3, pp. 10, July 2007.
2. Michael Rubinstein, Ariel Shamir, and Shai Avidan, “Improved seam caring for video retargeting”, ACM Transactions on Graphics (SIGGRAPH), vol. 27, 2008.
3. Radhakrishna Achanta and Sabine Susstrunk, “Saliency detection for content-aware image resizing”, Image Processing (ICIP), 2009 16th IEEE International Conference on. IEEE, 2009.
4. Radhakrishna Achanta, Sheila Hemami, Francisco Estrada, and Sabine Susstrunk, “Frequency-tuned salient region detection”, IEEE International Conference on Computer Vision and Pattern Recognition (CVPR), pp. 1597-1604, June 2009.
5. Wang, Yu-Shuen, et al. "Optimized scale-and-stretch for image resizing." ACM Transactions on Graphics (TOG) 27.5 (2008): 118.

Last updated 10/13/2014