Overview
Resizing an image via traditional means usually changes or warps the features within the image, as every pixel is considered as important as every other, and the image is scaled accordingly. Retargeting with the seam carving algorithm, however, chooses a "seam" of pixels through an image such that it passes through the least "important" pixels first; removing this seam will result in a minimal importance loss, while making the image one pixel narrower or shorter. By continuing this process, we can make the image smaller while preserving the integrity of its original features.
Algorithm
Downsizing an image with this method is relatively straightforward, and is described in more detail below. For the purposes of this description, I'll only discuss making an image narrower, but making an image shorter (using horizontal seams) is as simple as transposing the image before processing, and then re-transposing the result.
- Find pixel importances/energy costs: this can be thought of as determining how much each pixel matters, and is as simple as finding the gradient value over that pixel. This is very easy to do using the MATLAB
gradient()function (and summing the values for x and y over all three color channels), and this is indeed what I do in my implementation. These values could also be found by convolving a Laplacian filter with the image. - Find the minimum cost seam: finding a chain of neighboring pixels which runs from the top to the bottom of the image and sums to a minimal total importance seems a challenging task. To the contrary, it's pretty simple with a little dynamic programming:
- Iterate through the values calculated above (one for each pixel), building a matrix of importance sums. For each entry in this matrix (row-wise, from the top), we use the minimum value stored for the three pixels above the current in the cost-sum matrix, and add this to the importance value at the pixel position in question.
- Once we've finished the above process, each entry in the bottom row of the cost-sum matrix will contain the minimum cost of a seam ending in that pixel. Thus, to find the cheapest seam within the image, we need to find the seam that ends at the pixel corresponding to the minimal sum value in the last row.
- To do this, we begin at this minimal value in the bottom row, and trace back up the image, recording the x position of the minimum cost sum value at each y value. Of course, to preserve the connectivity of the seam, we're only comparing the three values directly above the last at each step in this process.
- Remove the minimum cost seam: for each row of the output image, include only the pixels to the left and right of the pixel within the seam for that row.
- Repeat: the above process will only downsize the image by one pixel (one seam), so to narrow it by more pixels, we must repeat the process. This includes repeating the energy calculation, because removing one seam will change the importance of pixels within the image, at least slightly.
Results
Following are the results of my program as applied to the six test images, all resized to 200 pixels less than their original width, as well as two of my own photos resized in different ways. Two notable error cases are Mona Lisa's hair, and the bodies of the women in the second and last of the test images. These are examples of differing measures of importance: we are so accustomed to standard proportions of the human body that we implicitly assign these great importance, while the seam carving algorithm sees relatively untextured hair, legs that blend in with the background, or flat skin color as unimportant regions which should be removed.
Using "Forward Energy"
One downfall of the seam-finding method displayed above is that straight lines are not always preserved, which can make retargeted images look especially unrealistic. The following three images feature many hard edges which the algorithm used above warps heavily, though by taking into account how removing a seam will contribute energy to a photo, we can try to avoid this. In simple terms, we just need to add the gradient difference created by removing a pixel to the cost of each seam going through that pixel, and this will favor seams which do not create sharp corners out of previously linear portions of the image, etc. As you can see in the following images, this adjustment does a lot to help preserve straight lines, or at least favor curved over jagged results. Also note the mug in the second image: it's shape is much better preserved using forward energy seam carving.
Image Expansion
Enlarging photos is a similar task to making them smaller, except now it makes sense to duplicate seams in order of least importance, so that the least important areas of the image become larger, and don't disfigure the more important areas (which will ideally remain the same size). When implementing this, it turns out that I couldn't just order seams as they'd be found in the above algorithm, because seams ending on different pixels at the bottom of the image would often converge on the same unimportant areas closer to the top of the image (essentially using the same pixels in multiple seams). Thus, when calculating a set of seams for duplication, I assign extra cost to using duplicate pixels (pixels already included in seams calculated earlier), so that the algorithm is more likely to choose mostly independent seams. For many images, it turns out that the most unimportant seams are concentrated in one area, which can cause the sort of smearing you see a little in the first image below. However, for images such as the second and third where unimportant space isn't structurally or texturally important to the image, this procedure works very well.
