Marvin Arroz(marroz)

CS129 / Project 3 / Seam Carving

Motivation

When we want to resize an image, the naive method would be to resize it. This, however, causes the image to look quite distorted. If we want to intelligently resize images, we can use a dynamic programming algorithm called seam carving that removes the "unimportant features." For instance, on the right, the algorithm removes a big part of the field. This part of the image is "unimportant" because there is little variation. Notice that the two buildings in the background are preserved and also the woman sitting in the foreground is preserved. The algorithm is not perfect however. We can see artifacts in the shape of the building on the left and also we see that her legs have also completely disappeared.

Algorithm

The algorithm first computes an energy table using a gradient filter over the image. The pixels of the image that have high gradients will be weighted with more energy so it will cause more to have it removed. Next, in the dynamic programming step, we find the "seam" going down the image that will cost the least. We then remove the seam and loop the algorithm until we get our preferred size. Note that this removes vertical seems so it only resizes it to the target width. To get to our preferred height, we perform the same algorithm on the transpose of the image.

Algorithm's Failures

While the algorithm shines in images that have a lot of repetitions (low gradients), we can conversely see how poorly the algorithm does on certain images.

The original image is on the left. We can resize it with seem carving to attain the image in the middle. There are some artifacts. For instance, the door frame is slightly warped as are parts of the ceiling. However if I try to resize the image to be smaller, the algorithm runs out of low energy things to remove, so it begins to remove the lowest energy things it has left, even if it means causing glaring artifacts. More examples of artifacts are below on the last two rows. Note that the algorithm does poorly with legs because there is no gradient within the legs. Also note that the algorithm works poorly with faces.

Results in a table