CS129 Project #3: Seam Carving
October 7, 2012
Background
Images are scaled for a wide variety of reasons. Scaling does not always preserve the aspect ratio (height to width ratio) of an image so the content of an image must be modified to fit the new dimensions. Naive resizing techniques include stretching and cropping. Neither of these options are ideal as stretching distorts the image and cropping reduces the image content. "Seam carving" provides a generally superior method. At a high level, seam carving is an algorithm that preserves the sizes and shapes of "important" objects, while resizing "less important" parts if the image.
Method
Seam carving involves selecting a 1 pixel wide "path" from the top of the image to the bottom, containing unimportant pixels that can be deleted. Keeping the pixels on a connected path prevents the image from becoming distorted after the deletion and ensures that the same number of pixels are deleted from each row of pixels in the image. A pixel is deemed unimportant if the magnitude of its gradient value is small. In other words, the brightness values of its color channels do not differ greatly from those of its neighbors. The gradient value is calculated by applying a horizontal and vertical sobel filter to each pixel.
To calculate a path of pixels, the algorithm begins by calculating a table (matrix) of possible paths. For the top row, it gives each pixel the value of its gradient magnitude. It then calculates the values of the other pixels in row order. Each pixel value is determined by summing its gradient magnitude value with the least greatest value of the three neigbor pixels above it (its top-left, upper, and top-right neighbor pixels, whose values have at this point already been calculated). When the matrix has been calculated, it can be traversed from bottom to top to find the lowest-cost path. Starting at the bottom row, the smallest valued entry of the matrix (which has a corresponding index in the actual image) is chosen. The algorithm then chooses the pixel with the smallest value of the chosen pixel's upper three neighbors. This is repeated until the algorithm reaches the top of the image. The path that the algorithm traversed is then deleted and the process is repeated.
Optimizations
The algorithm described is not especially fast as is. A 500x500 pixel image could take about a minute to process if its width is decreased by 150 pixels. To improve the run time, several opitimizations were incorporated. The first takes advantage of the fact that the removal of a seam affects only a small part of an image. There is no need to recalculate the entire matrix of gradient values when many of the values are still valid. It turns out that the pixels that need to be recalculated are contained in a triangle whose point stems from the pixel located at the start of the removed path at the top of the image. This is because the only value that might change a given pixel's value is its above three neighbors. A removed pixel therefore affects the three pixels below it, and each of those pixels affect the values of the three pixels below them (some pixels overlap). The effect of this optimization largely depends on the aspect ratio of the image being processed, but testing suggests that one can expect the change to make the algorithm about 30% faster.
The other optimization implemented trades accuracy for speed, so it is not an unequivocal improvement to the original algorithm. The basic idea is that multiple seams can be carved off of the image using only one calculated value matrix. The seams are carved from least cost to greater cost. Consequent seams may not be based on perfectly accurate values, but results suggest that for an image whose width is 500 pixels, up to 4 seams can be carved per matrix with negligible impact on the quality of the carving.
Extra Features
Object Protection
Since the algorithm is based entirely on the gradients of pixels it can sometimes mistake an object deemed important by a human simply because that object has small gradient values. To correct this, a user-controlled mask creation tool can be used to manually select an object to "protect." The pixels selected are incorporated into the gradient value matrix, making the corresponding values "high-cost."
Object Deletion
Similarly, objects can be deleted from an image by negatively weighting parts of the gradient value matrix. Using a tool that closely resembles the object protection feature, the user can select a region to negatively weight, causing all paths to contain the selected region.
Note that in the examples to the left, simply using the object deletion tool damaged the person originally on the right. To ensure a smooth deletion, the object protection tool was used as well.
Another feature (not implemented) involves the duplication of low-gradient seams to expand an image. An image that underwent a deletion operation can be re-expanded to the original size, resulting in the illusion that the image contains the scenery located behind the deleted object.
Forward Energy
In truth, the algorithm ultimately employed by this project did not use the gradient magnitude calculations often associated with seam carving (although that algorithm was implemented for comparison purposes). There is a different method of calculating a matrix of values that can be used to determine a least-cost path. The original method's shortcoming lies in the fact that it does not take into account the gradients it may be inserting into the image when it deletes a chosen path. The original algorithm can create undesirable distortions in the image. At a high level, the final algorithm implemented calculates a pixel's cost by minimizing the gradient values created in the image by the potential removal of one of its three upper neighbors. After the matrix is calculated, a path can then be chosen that picks the pixels whose upper neighbors will cause the least gradient disturbance, ideally preventing image warping, broken edges, and other distortions.
Results
Although the improved algorithm usually provides better results, its run-time is dramatically longer--it takes about 5 times as long as the original algorithm. Its runtime is further slowed by the incorporation of object deletion and protection options which are not as computationally burdensome on the original algorithm. Runtime can be improved if these features are turned off. Furthermore, the improved algorithm greatly reduces broken edges but it cannot completely eliminate distortions. As can be seen below, the track lines do not remain straight and the deletion of a runner is not without artifacts. Since a large number of seams were taken from the same location, it is impossible for the remaining pixels to seamlessly blend together. (An addition of a Poisson blending algorithm could remedy this). Despite the numerous drawbacks, seam carving provides a useful alternative to naive image resizing by offering a more intelligent approach that takes into account image content.
