CS129 / Project 3 / Seam Carving
In this project, I implemented dynamic resizing using seam carving on images in both the horizontal and vertical directions. This sometimes gives us better images than if we simply cropped the image or resized it in a trivial fashion by stretching or shrinking it in the corresponding directions.
Algorithm
For every image, we calculate an image energy map using gradient energy (i.e. how different a cell is compared to its neighboring cells - the higher the difference, the greater the energy in our map). This is simply done by finding the difference between each pixel and its neighboring pixels across the 3 color channels (RGB).
Next, we attempt to find the seam with the lowest cost in the entire matrix by dynamic programming. We start at the top of the image, and gradually make our way down. Every time we arrive at a new row, we update the corresponding position in a new matrix with the same size as our image with the direction each cell points to. Since we want the lowest cost path, we make sure that we set the direction towards the cell with the lowest cost path that led to it. When we reach the bottom of the image, we pick the cell which has the path with the lowest cumulative cost leading to it, and then work our way back up the matrix from that cell, storing the path we take back up into another matrix that is basically a column vector with the same number of rows as the image, but only a width of 1.
Finally, we remove this seam from the image. This involves generating a new matrix that is the same dimensions as the original image, but with 1 less column. For every row, for every pixel leading up to the pixel we want to remove, we just copy the value of the cells over to the same position in the new matrix. But for every column after the pixel we want to remove, we copy the value of the cells over to a position corresponding to column minus one in the new matrix. We return the new matrix, which has the lowest energy seam removed. This is repeated for as many seams we want to remove till we hit the desired size of the image, resulting in a dynamically-resized image.
To remove horizontal seams, we simply transpose the image and then carry out seam carving as usual. When we are ready to return the image, we transpose it again so that the image is returned in the right direction.
Results in a table
The first image in each row is the original image, the second image is the resized image by just normal resizing, the third image is the dynamically resized image. As you can see, sometimes the dynamically-resized image looks better and at other times, normal resizing works well by itself. See below for a discussion of success and failure cases.
|
|
|
|
|
|
|
|
|
|
|
Discussion
A noteworthy success case is the first image (boat). The "normal-resized" image has the boat looking too thin, whereas our image preserves the most important part of the image (the boat) entirely by simply giving less space to the mountain ranges.
A failure case is the Mona Lisa painting. In our result, her hair has been largely removed because it is a large patch of black and hence low energy in our energy gradient. The same goes for most of her shoulders. This is undesirable because now the image looks weird and completely unnatural.
By Kai Herng Loh (Computer Science-Economics, Brown '14)