Seam Carving for
Content-Aware Image Resizing
Contents
Introduction
Content-aware image resizing refers to the process of changing the aspect ratio and size of an image with minimal distortion to the main features of the image. Normally, resizing involves removing features (cropping), or distorting features (scaling). Seam carving, the method explored here, avoids these pitfalls by removing "unimportant" parts of the image at the pixel level.
Specifically, we determine the energy of the image, in this case the magnitude of the gradient, and then find the connected path of pixels from top to bottom that has the lowest total energy. If we remove the pixels in this seam we reduce the width of the image by 1 pixel and hopefully leave no artifacts behind.
References
The method described and implemented here was first outlined in the paper Seam Carving for Content-Aware Image Resizing, by Shai Avidan and Ariel Shamir.
The forward-energy method described in Comparison of Energy Methods was proposed in the paper Improved Seam Carving for Video Retargeting, by Michael Rubinstein, Ariel Shamir, and Shai Avidan.
Both papers were the result of research performed at the Mitsubishi Electric Research Labs
Technical Details
Image resizing via seam carving is implemented in MATLAB as the cawresize (Content-Aware Resize) function. This function takes an image, an amount to resize by, an optional direction, and an optional energy method. Resizing only works in one direction at time, defaulting to horizontal if unspecified. Vertical resizing is accomplished by rotating the image 90 degrees, performing the operation, and then inverting the rotation. The resize amount can be either positive or negative; negative values decrease the size of the image, while positive values enlarge the size by inserting seams. The function uses forward-energy for reductions and backwards-energy for enlargement by default.
Removing Seams
To remove a seam, the input image is converted to grayscale and the energy is calculated. Using the ideas of dynamic programming, we calculate the minimum energy of a connected path from the top of the image to each pixel of the image. Once all path energies have been computed, we find the minimum path energy in the last row of pixels and scan back up the image to construct the minimal energy path.
Energy is measured using one of two methods: backward-energy or forward-energy. Backward-energy is the method described in the original paper, where every pixel is assigned an energy and the sum of the pixel energies in a path determines the cost of the path. In my implementation, I use the magnitude of the gradient as the energy function. Because each pixel has an energy, backwards-energy removes the globally-minimal-energy seam from the image. Normally this works well, but it does not account for the energy introduced by removing the seam and bringing previously separate pixels together.
Forward energy attempts to solve this problem by minimizing the energy introduced by removing a seam, rather than minimizing the energy of the seam. There are three possible ways for a seam to reach a given pixel coming from the row above. By computing the energy (gradient) of the resulting pixels after each possible seam is removed, the path that introduces the smallest amount of energy can be found. The desired side-effect of this is that seams are less likely to cross edges in the image.
Inserting Seams
Inserting n seams into an image is accomplished by finding the first n seams that would be removed and inserting pixels along them. The value of a new pixel is the average of its neighbors. As suggested in the paper, we perform large insertions in several steps, to help vary where pixels are inserted.
Results
Original image is followed by the resized version(s). Forward-energy was used unless otherwise noted. See the title text on the images for more information.
Picture by me
As a comparison, here is the same image resized with traditional scaling. Note the distorted trees.
Picture by me
This was resized first vertically, then horizontally.
Here, only height was increased, to make the image square.
Picture by me
Failures
Of course, seam carving does not work everywhere. As can be inferred from the good results, seam carving seems to work best on landscapes and pictures with small details. When there are only a few large features, distortions and other artifacts are much more noticeable.
The first error is the aspect ratio of the cars &mdash due to lighting, there are similar colors vertically through windshield and hood, causing the center of the car to be removed. Next, we see that the corners of the buildings are tilted, particularly the front corner of the closest building.
This is the result using backward-energy. The cars are a little better, but the buildings are much worse
Picture by me
The problem with this image is that all the seams are in the same place. I think this is because the background on the left side is more uniform than that on the right. As a result, the left eagle seems to be more endangered than his friend on the right.
Perhaps to compensate from above (and for the same reasons in terms of energy), the left eagle is now extremely fat when we expand the image.
Picture by me
The textured background here is in a sense too textured &mdash the chipmunk is the smoothest, lowest energy part of the image. The result is a distorted chipmunk with very tiny legs in a scene with a perspective that is a little off.
Picture by me
Comparison of Energy Methods
In general, forward-energy works well as it is designed to reduce common artifacts. However, there are several case where standard backward-energy seems to work better. Unfortunately, I was not able to find any criteria to help determine ahead of time which method will produce the best results, so it remains a process of trial and error. One case where backward almost always works better is when images are enlarged &mdash it doesn't make sense to use an energy measure based on removing seams when seams will actually be inserted.
What follows are several comparisons between the methods on images from the "Results" section above.
Using forward-energy, there are no highly visible artifacts.
Using backward-energy, the tower begins to curve inward. I find this strange given the vast expanses of water to remove from, but I think the similarity of the railing and the tower at the junction causes the bending.
Using forward-energy, the ceiling shape is preserved, and the windows and walls shrink.
Using backward-energy, the ceiling collapses and the height of the windows in relation to the chairs is mostly the same as in the original.
In both cases the result is aesthetically pleasing, so it is left to artistic discretion which method is preferable.