I implemented the seam carving algorithm described both in class on 26/28 September and in the project 3 assignment. I used the sum of the absolute value of the gradients (which I found after first gaussian blurring the image so as to disregard the less important higher frequency gradients) in each color channel as my energy matrix, and from there, the optimal seam is calculated with the dynamic programming algorithm we discussed: working row-by-row from the top of the image, the algorithm determines the minimum energy required to reach each pixel. To find the actual optimal seam, we backtrack up from the bottom of the image, starting with the pixel with the minimal value in the bottom row and then following whichever adjacent pixel in the row above has the minimal value, and this seam is then removed from the image. This process is repeated every time the image's horizontal dimension is shrunk by a pixel (e.g. to shrink the image by 200 pixels horizontally, this process is applied iteratively 200 times). Vertical shrinkage is accomplished by transposing the matrix both before and after this process.
Here's a sampling of the final resized photos, with the original on the left, the horizontally-scaled in the middle on the left. The boat image in the first row has additionally been resized in both dimensions (from 400x400 to 200x300), with this extra image appearing to the right of the other two. The final three photos are my own.
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
This algorithm works wonderfully on images with relatively small areas of high importance against a backdrop of low importance, as you can see in rows one, four, five, and six. It works surprisingly well for both dimensions on the image of the sign in row nine for this reason, but row eight shows an image for which only the vertical resizing yields anything close to a reasonable picture.
This failure on the eighth row's horizontal resizing comes from the algorithm's inability to preserve straight lines, as also seen in the Kandinsky example in the third row. This can be mitigated to an extent by the forward-energy solution we saw in class.
One way the algorithm breaks down is when you simply try to remove too much information: there comes a point when the image is so small that removing another pixel in each row causes vital loss of key parts of the image which were preserved until this point, as in this extreme resizing of the photo of the Stata Center (which you can compare to the more reasonable vertical resizing of it on the right in the penultimate row up above):
A subtler and less common issue is that the algorithm has no higher-level understanding of the scene. It doesn't know that at the bottom left of the Picasso in the second row there is a miniature replica of the painting which should also be rescaled so as to remain accurate.
Maybe the biggest problem can be seen in the horizontal-scaling of the Mona Lisa way up in the fourth row. The algorithm works exactly as we want it to: it removes areas of the image which have small gradients. Since her hair is far smoother than the rest of the image, it is, naturally, what the algorithm removes even though we know that a good resizing won't remove all the hair. To be fair, this algorithm preserves her face, which is arguably the most "important" part of the painting, but a better algorithm would more even distribute the areas which are removed, although honestly I don't know how I would go about implementing that just yet.
I unfortunately didn't implement anything above and beyond for extra credit.