Implementation of Seam Carving

Project for CS766 (Computer Vision), Spring 2018 UW-Madison

Team Members

Shuo Sun, ssun99@wisc.edu
Shilu Zhang, szhang256@wisc.edu

Introduction

The problem that our group is trying to focus on is image retargeting/content-aware image resizing. It is an important concern when we want to remove unused space from images, or add extra contents, but keep the main objects at their original aspects. Generally speaking, there are three guidelines that we need to follow when we try to resize/retarget an image:

preserve important content of original media
limit visual artifacts in resulting media
preserve internal structures of original media

Seams, by definition, are the least-important connected pixels in an image. Therefore it comes intuitively that they are the things that we try to remove first when we want to remove unwanted contents from an image. So we choose the topic of seam carving, which is proposed by Avidan & Shamir 07 and improved by Rubinstein, Shamir & Avidan 08, as the main focus for our project.

Current state-of-the-art

Besides seam carving, there are many different approaches for content-aware image resizing. Among them are scale-and-stretch warping method by Wang et al. 2008, shift-map by Pritch et al. 2009, and multi-operator by Rubinstein et al. 2009. There is a paper that summarizes all these different methods: A Comparative Study of Image Retargeting by Rubinstein et al. 2009. There is also a website dedicated to running image retargeting related benchmark programs called RetargetMe.

Our approach

We adapt our major approach from Avidan & Shamir 07.

Given an image I, we can calculate its energy by

then we use dynamic programming to trace back from the last line of the image to the first line to calculate the minimum energy matrix M

and finally, we can find the optimal seam to remove by

Results

1. Aspect ratio change

We can successfully apply the algorithm to reduce the width of an image to a target size. Figure 1 shows the result of reducing the width of the image by 100 pixels.


(a) Original Input	(b) Original Input with vertial seams	(c) Seam Carving

Figure 1: Result of seam carving to reduce an image

2. Retargeting with Optimal Seams-Order

When we try to fit the image to a new size, the order of removing seams may matter, especially when both horizontal and vertical seams are included. Optimal order reflects the most energy-efficient way when that happens.

Original Input


(a) horizontal then vertical	(b) vertical then horizontal	(c) alternate between horizontal and vertical	(d) optimal order retargeting

Figure 2: Result of retargeting image with optimal seams-order using seam carving

3. Image Enlarging

We can also enlarge an image through seam carving. To achieve that purpose we need to calculate the seams that we are trying to remove first, then add these seams back to the original image. img credit


(a) Original Input	(b) Calculate seams	(c) Add to original image

Figure 3: Result of image enlarging using seam carving

4. Content Amplification

Sometimes we want to amplify certain contents of an image. We can first use standard scaling to enlarge the image and then apply seam carving on the larger image to carve the image back to its original size.


(a) Original Input	(b) Resizing	(c) Seam Carving

Figure 4: Result of content amplification using seam carving

5. Object Removal

To remove a target object from an image, we first mask the target object to be removed (the woman in green), and a region to project (the man in red). Seams are removed from the image until all marked pixels are gone. The algorithm computes the smaller of the vertical or horizontal diameters of the target removal regions and perform vertical or horizontal removals accordingly.


(a) Original Input	(b) Mask	(c) Object Removed

Figure 5: Result of object removal using seam carving

6. Object Removal and Resize

Sometimes we want to resize the image to original size after removing a target object. Here we removed the girl from the image by removing vertical seams and recorded all the coordinates and insert new seams in the same order at the recorded coordinates location of removal to regain the original size of the image.


(a) Original Input	(b) Girl Removed	(c) Girl Removed and Resized

Figure 6: Result of object removal and resizing using seam carving

7. Forward Energy vs Backward Energy

The original algorithm using Backward Energy choose to remove seams with the least amount of energy from the image, ignoring energy that are inserted into the retargeted image. The new algorithm in the Rubinstein et al paper looks forward at the resulting image and searches for the seam whose removal inserts the minimal amount of energy into the image.

The cost is measured as forward differences between the pixels that become new neighbors.

We use these costs in a new accumulative cost matrix M to calculate the seams using dynamic programming. Here is the formula for vertical seams:

Here is an comparison between the original seam carving backward energy (a) and the new forward energy (b) for resizing an image. The new results suffer much less from the artifacts generated using backward energy such as the distortions of the bench bars and skeleton.