Seam Carving
CS129 Computational Photography Project 3
Seam Carving for Content-Aware Image Resizing
Background
Seam Carving, also known as Content Aware Image-Resizing, Image Retargeting, is a technique to "smart" resize the images. The technique basically resizes images based on the content of the image i.e. it preserves the content in order of its importance.This technique was first introduced by Shai Avidan and Ariel Shamir in this paper.
Goal
The goal of this project is to implement seam carving and use it to retarget images. In order to do this we need to find optimal seams of low energy and remove it (if we want to reduce image size) or add it (if we want to increase the size) from or to the image.
|
|
Algorithm
The high-level view of algorithm is described below :
- The first step in algorithm is to compute the energy matrix. (Taking gradient in either horizontal or vertical direction).
- The next step is to find an optimal seam using Dynamic Programming. I have used a "forward energy" formulation in order to decrease the energy added to the image after seam removal.
- After finding the optimal seam, I remove it and now the image(width or height) is smaller by one pixel.
- The same process is repeated on the smaller image in order to resize it to a more smaller image.
Retargeted in horizontal direction
|
|
Retargeted in vertical direction
|
|
Retargeted in both direction
|
|
Extra Credit : "Forward energy"
Removing low energy seams from the image inserts new energy. The inserted energy is due to new edges created by previously non adjacent pixels that become neighbors once the seam is removed. This change can be measures by taking gradient between the new neighbours. Using such forward energy we can compare the amount of energy inserted by each seam and reduce it by choosing the seam which inserts the lowest amount of energy. The comparision between backward energy seam carving and forward energy seam carving is shown in the following figures.
|
|
|
| Original | Backward energy | Forward energy |
|
|
|
| Original | Backward energy | Forward energy |
Extra Credit : "Seam Insertion"
The images can be enlarged by adding low energy seams into the image. As human eye is sensitive mostly towards edges, it is not able to preceive low energies added to the image. The following example shows the image enlargement using seam insertion.
|
|
|
|
Extra Credit : "Object Removal"
The seam carving algorithm can be used for object removal. In order to remove objects from the image, we make changes to the energy matrix in order to force seams to pass through the object. This can be done by reweighting the area of energy matrix where the object appears.
|
|
Retargeted Images
Decreased width by 200px
|
|
|
|
| Wyeth | Backward energy | Forward energy |
|
|
|
| Kandinsky | Backward energy | Forward energy |
|
|
|
| Ratatouille | Backward energy | Forward energy |
|
|
|
| Monalisa | Backward energy | Forward energy |
|
|
|
| Plier | Backward energy | Forward energy |
|
|
|
| Snow | Backward energy | Forward energy |
|
|
|
| Dali | Backward energy | Forward energy |
|
|
|
| Car | Backward energy | Forward energy |
Increased width by 100px
|
|
|
| Boat | Enlarged |
|
|
|
| Kandinsky | Enlarged |
|
|
|
| Monalisa | Enlarged |
|
|
|
| Pamir | Enlarged |
|
|
|
| Car | Enlarged |