Example gif taken from https://github.com/andrewdcampbell/seam-carving
The goal of this project is to perform content-aware image resizing for both reduction and expansion with seam carving operator. This allows image to be resized without losing or distorting meaningful content from scaling. The code in this repository and technique described below is an implementation of the algorithm presented in Avidan and Shamir (2007) and Avidan, Rubinstein, and Shamir (2008) algorithms.
http://www.eng.tau.ac.il/~avidan/papers/vidret.pdf
https://www.merl.com/publications/docs/TR2008-064.pdf
- Calculate energy map:
Energy is calculated by sum the absolute value of the gradient in both x direction and y direction for all three channel (B, G, R). Energy map is a 2D image with the same dimension as input image.
- Build accumulated cost matrix using forward energy:
This step is implemented with dynamic programming. The value of each pixel is equal to its corresponding value in the energy map added to the minimum new neighbor energy introduced by removing one of its three top neighbors (top-left, top-center, and top-right)
- Find and remove minimum seam from top to bottom edge:
Backtracking from the bottom to the top edge of the accumulated cost matrix to find the minimum seam. All the pixels in each row after the pixel to be removed are shifted over one column to the left if it has index greater than the minimum seam.
- Repeat step 1 - 3 until achieving targeting width
Seam insertion can be thought of as inversion of seam removal and inserts new artificial pixels/seams into the image. We first perform seam removal for n seams on a duplicated input image and record all the coordinates in the same order when removing. Then, we insert new seams to original input image in the same order at the recorded coordinates location. The inserted artificial pixel values are derived from an average of left and right neighbors.
