Seam Carving
Aaron Hsu
Code
Given an image, and number of pixels, we want to remove n minimum seams. Through dynamic programming,
we can calculate the minimum seams in an image by observing the "energy" through an image.
In this case, I only used gradient magnitude to determine our energy. It provided satisfactory results.
To calculate our gradient magnitude, it is simply the square root of the sum of squares of our horizontal and vertical gradients.
img_gradient = sqrt( Ix.^2 + Iy.^2 )
From here, we divide our seam-carving into subproblems. We create a table such that at some given row and column,
it represents an optimized subproblem which holds the sum of the minimum seam up to that row.
For example, a vertical seam travels by looking at adjacent pixels (left, down, right).
Once we have our table, we take n vertical seams and remove those seams - shrinking the image horizontally.
To vertically shrink the image, we transpose the image and take the n vertical seams of that transposed image.
Once we transpose it back, we have shrunk the image vertically.
All the following images were shrinked by 25% of their original image size (in either direction).
Uncharted 3 Desert Ruins
My first example will be from one of my all-time favorite games - Uncharted 3. Here's a pretty spectacular graphics rending of an in-game scene.
 |
 |
 |
 |
| original |
gradient magnitude |
horizontal shrink |
vertical shrink |
I thought this was done decently well on the whole. When it comes to the vertical shrink image, we got rid of the horizon
and a few bottom layers of sand were removed. This is exactly what we were trying to go for.
If you look at the other objects in the image, the character (our hero Nate Drake), is still intact
as well as many of the building ruins you see in the desert.
For the horizontal shrink, on the other hand, it worked mostly well other than the apparent shading line of the sand and a little bit of the horizon.
One of the buildings might seem a little funky as well, but on the most part, if we used some sort of image blending, we could easily cover up this line.
The line is mostly apparent due to differences in sand shading.
Beach Scene
Just some beach with some chairs
 |
 |
 |
 |
| original |
gradient magnitude |
horizontal shrink |
vertical shrink |
Both examples are pretty fair. In the horizontal shrink, we see that the beach chairs have moved together.
I don't really see any apparent artifacts from the seam-carving, so I would say it was a success!
The vertical shrink seemed to cut off most of the top and a little bit of the bottom.
Judging from the given image, I wouldn't see how else we would cut out seams when doing a vertical shrink.
The top just had the sky and one leaf. Any other horizontal seams would be affected by the trees and chairs and ocean!
Cruise Ship
 |
 |
 |
 |
| original |
gradient magnitude |
horizontal shrink |
vertical shrink |
In this scenario, we see that the horizontal shrink was pretty fair. In my opinion, it might've cut too much
of the end of the cruise ship. But since the cruise ship is farther back than the tree of pier, it would make more sense to cut out the cruise ship
(but it wouldn't make sense if the code had known this was an advertisement for the cruise ship!).
On the other hand, we see that the vertical shrink messed up a bit. The palm tree just got shifted down a lot.
However, this is a reasonable result because the horizontal seams removed were those that transitioned from the ocean
to the sky. Both are blue and would definitely be the minimum seams as the horizon is realy the ONLY contribution to
the sum of these minimum seams. As a result, it would make sense that the seams removed would be the ones connecting
the ocean to the sky as there are no other "main" objects in their path.
People
We're going to try several different examples with people in them and see what happens...
| original |
gradient magnitude |
horizontal shrink |
vertical shrink |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
In general, it seems, unfortunately, that our main objects in these images always get cut out!
Usually, the vertical shrinking isn't a problem as it "focuses" more on the main people at hand (rush_hour and assassin creed pictures).
However, our bane vertical shrinking gets owned. I would say that this is because looking at our image gradient,
there's LOTS of textures in the bottom. The batmobile, the texture of the stone stairs, and the people are much more defined
compared the the upper rows with just bane's head and pillars. As a result, the upper rows would get cut out.
However, most of the problems come from the horizontal shrinking. The people ALWAYs get cut out! =[
Again, I would attribute this mostly to the image gradient. Because our energy function doesn't realy take into account
depth of our object and is heavily affected by texture, compared to the backgrounds with plenty of texture,
the non-textured parts of the people are cut out.
For example, in our rush hour picture, Jackie Chan basically vanishes into the night like a true ninja.
He's wearing black which blends with the night sky and he himself has almost no texture (as you can see in the image magnitude).
Bane and the assassin from Assassin's Creed get parts of them cut out because their clothing, compared to the background, just pale
in comparison when it comes to texture. For instance, the gradient image of the assassin's creed, the cities
are highlighted a lot more due to their textures and abundance of edges and such.
If I could do this again, I would definitely try a different energy function to use for seam-carving for people. One that isn't so dependent on texture.