Seam Carving
15-463: Computational Photography
Author: Stephen Tawa (stawa)
The goal of this assignment is to implement a basic seam carving algorithm for content-aware image resizing. Seam carving allows us to shrink images vertically or horizontally while preserving "important" content as defined by an energy function.
All images that I used are from the course website or Wikipedia.
The algorithm involves repeatedly locating and removing the lowest cost seam until we have resized the image to a desired width or height. My energy function was the magnitude of the gradient of the grayscale image. I used a DP approach with backtracking to find the lowest cost seam in the image. I wrote the algorithm to find and remove vertical seams, so to remove horizontal seams I must transpose the image first.
My initial implementation was fairly slow because I recomputed the energy function for the entire image after I removed each seam. I also tried the other extreme, where we find and remove the k lowest cost non-overlapping seams from the original image. As expected, this was faster but gave less satisfying results. I found that if we want to remove k vertical seams, then we can recompute energy every .1k to .2k iterations to achieve a balance of efficiency and good results.
(By the way, this is a great album.)
These images work well because they consist of prominent objects on simple backgrounds. If this is not the case, we run into problems...
Here, there are many diagonal edges that become distorted. Also, the background is not sufficiently boring for the human to remain intact.
Once again, diagonal edges and human faces cause problems.
Humans probably consider the water as boring as the sky, but the algorithm thinks that the sky is far more boring.
Marmots can survive seam carving, but apparently horses do not (neither do diagonal edges, as we've seen before).
This was an attempt at a worst-case image for seam carving: no foreground or background and lots of diagonal edges.
When we removed horizontal seams, the algorithm correctly identified the water as unimportant. But when we remove vertical seams, the algorithm fails to remove the right portion of the image, even though humans probably find it boring.