Overview

Usually when resizing an image, there are two options: scaling and cropping. Both, although fast and extremely easy, pose problems. First, scaling distorts objects in the image: once tall buildings become vertically squished when scaling to decrease height. Cropping, on the other hand, means you lose parts of the image. Furthermore, you cannot crop empty space in the middle of the image to keep important objects on the edge in the picture.

To solve this, we can dynamically resize images by removeing low-energy seams, i.e. seams whose overall importance in the image is very low. Using the algorithm described below, seam carving can reduce the image size while still keeping important features intact.

Algorithm

To seam carve, first the energy of every pixel must be determined. Energy, in this case, is the absolute value of the x-gradient and the absolute value of the y-gradient of one of the color channels added together. This results in a per-pixel energy matrix.

Then, this energy matrix is copied over to a new matrix, M, which keeps track of total seam energies as we dynamically calculate them. These seams are calculated by comparing the energy of the current pixel with the total energy of the pixels above it and to the left, directly above it, and above it and to the right. The current pixel value in M is then set to its current value and the minimum of the three total energies above it.

While these seams are being calculated, another matrix, D, can keep track of directions. If the minimum pixel from above is to the left, D would get a -1. If the minimum was directly above, then D would get a 0. And D would get a 1 if the minimum was above and to the right. This direction array makes it really easy to calculate the path.

The path is calculated by first obtaining the lowest total energy seam, which would be the minimum total energy in the last row of M. Starting from the index of that minimum energy, we can follow the directional matrix D upward and find the pixel that should be removed next. We can add all these "to-remove" pixels to a column vector to remove.

Results