Image Resizing with Seam Carving

Greg Methvin (gmethvin)

This project was an attempt to use seam carving to resize images. Seam carving works by finding vertical or horizontal paths (called seams) through images containing the least important pixels. The process is also called retargeting, as it changes the image to target certain pixels of the image which are seen as more important. This project was my experiment with creating algorithms to do this.

Process

My algorithm first calculated the importance of each pixel of the image. I found the Laplacian of the Gaussian to be useful in doing this. Laplacian also worked well, but I feel that I obtained better results after using the Gaussian to filter out noise. After calculating this map, I used dynamic programming to calculate the path of least cost of the seam down/across the image. I did this by simply calculating the lowest value for each pixel based on the three possible source pixels and stored a direction map. When I reached the last row, I took the pixel with the lowest cumulative value and followed the direction matrix to find the seam.

Problems

The algorithm has trouble identifying important features easily recognizable to humans, such as faces and body parts. This often results in people looking squished and causes the algorithm to sometimes remove pieces of people's faces. In cases where the energy in the image is concentrated in a few main places, this problem does not show up as often, but it can become a serious issue for most real-life situations that don't have simple backgrounds.

Bells and Whistles

I attempted to precompute the map to make the algorithm faster, so I can remove several seams at once using the same map. When I remove a seam I simply remove that seam from the map and choose the next best one to remove next. I find that with this strategy it is necessary to recalculate the map occasionally since when I remove seams from the matrix the importance map is no longer accurate.

Results

I've summarized my results below. The successes and problems of the algorithm on that particular image are described below each retargeted image. The images are scaled to fit the width of the table.

Original Image	Retargeted Image
Source: Wikimedia Commons	This image was retargeted to be about 60% of its original width. The trees around the edges appear a bit distorted, but the pagodas in the middle still look pretty good. Resizing past this point causes noticeable distortion, but this does a good job of removing the excess ground and sky without distorting the main focus of the image.
Source: Wikimedia Commons	This image was resized to half its original height using seam removal. This process compressed the area of fog in the image and some of the sky. The ground, bridge, and the small piece of San Francisco shown in the image were preserved quite well. Without seeing the original image it's hard to notice the small amount of distortion in the retargeted image.
Source: Wikimedia Commons	Seam carving was used to resize this image to 75 percent of its original size in both dimensions. This resizing has the effect of removing the sky and bringing the stream in the image to greater prominence. It does distort the image a bit, but it also removes some of the sky at the top which is of little importance. This image seems to have areas of varying relative importance but I feel like the seam carving still does pretty well.
Source: Wikipedia	About 25% of the width of this image was removed along with about 50% of the height. This resulted in removing a large portion of the sky and squishing the piece of the coast shown in the distance of this picture. The people also appear a bit distorted, but it's hard to tell because they are so small.
Source: Flickr	This image was not resized correctly by my seam carving algorithm. It seemed to take out much of the cat's face in the background, and avoided removing pieces of grass at the bottom which would have been more appropriate to remove.
Source: Wikipedia	This image was resized to 70% in both directions. The algorithm removed the white around the edges, like we would expect it to, but, since it was unable to assign greater importance to the faces, many of the faces in the image came out looking distorted. The algorithm chose to remove horizontal seams there instead of in the bottom of the image where it would have been more appropriate. This is probably because of the solid white colors and lack of change through much of the rest of the image along those seams. In this particular situation, cropping the image may have produced more desirable results than using seam carving.