Source image
Energy map
The objective of this project was to implement a version of the seam-carving algorithm presented by Shai Avidan and Ariel Shamir in their 2007 paper "Seam Carving for Content-Aware Image Resizing". Traditional resizing of images does not take into consideration the content of an image and cropping can discard important information from an image and is limited to its periphery. Seam-carving is a way of finding the least important part of an image and removing those while keeping the important elements intact.
In order to determine the important parts of an image, it is necessary to implement an energy function which will
attribute a weight to every pixel, the higher the energy the more important the pixel. In this implementation of the
algorithm, the sum of the gradient magnitude (x and y) of each pixel is used. This function will have the effect of attributing
high value energy to pixels which are close to borders where the gradient is more pronounced. Using this energy map, the path
of least energy going from the top of the image to the bottom is computed. This path is called a seam, it has exactly
one pixel per row (or column for a horizontal seam) from top to bottom of the image (or left to right) and each group of three
pixels have to be within three column of each other (or row if using horizontal seam). When trying to find the seam of minimum
energy we use the following equation to find the next pixel for the seam:
M(i,j) = e(i,j)+ min(M(i−1,j−1),M(i−1,j),M(i−1,j+1))
Where M(i,j) represents the sum of all the energy of the previous pixels in the seam and e(i,j) the energy of the current pixel.
These value of M are stored in a matrix the same size as the image and the pixel with the smallest M value on the last column of the
is the last pixel of the minimum seam. While the values of M are computed, another matrix is used to store the predecessor of each pixels
using values of -1, 0 and 1 to represent above left, directly above or above right respectively.
When trying to resize an image, there is three ways of proceeding, either you eliminate the vertical seams then the horizontals, horizontals then verticals, or find if the current optimal seam is either a vertical one or a horizontal one and then remove that one. The following results use the later method. We can realize that the more crowded and image is in terms of different element, the more visual artefacts appear because the seams do not have a ways of traversing the image without going inside objects.
