In this assignment, I used dynamic programming to remove the least cost path in an image to crop it in a context-aware way: this is called seam carving, as described in this paper. I also tested different energy functions, composed my own image, and implemented seam removal as extra credit. All the images were taken or drawn by me unless otherwise stated! You can right click and open them in new tabs to view fullsize.
First, I calculated an image's "energy" from its grayscale representation--in this case, I just took the sum of the absolute values of its x and y gradients (partial derivatives). I then used dynamic programming to propogate these values to create matrix representing various vertical paths through the image (if I wanted to crop by height, I would just flip the image and do this calculation). I then traced back this matrix, finding the minimum adjacent entry for each pixel, to remove a "least cost" path. I did this iteratively for however many pixels I wanted to crop by: one pixel = one path removed. My code takes a few parameters: the image to be cropped, an axis to crop it by, the energy function to use (more on this later), and how much to crop it by, and if that's in % change or in raw pixels.
Because the foilage is very detailed to computers although we as humans perceive it as a group, this crop mainly focused on removing parts of the cloud.
It's nice to see all the details of the bottom strip (lake, trees, etc) compressed, not simply cropped out.
I took this photo with my Nexus 4, a few hours before falling into a river with it and frying its battery. I think it's the nicest photo my cellphone camera has ever captured.
Again the comment about foilage being detailed to computers. In this case, compositionally I think a traditional crop in the middle would have looked better: the clouds look too compressed.
I took this while studying abroad in Cambridge 2 summers ago! It's the River Cam on the way to Grantchester.
Now I can Instagram with context!
Of course, when you study abroad in the UK, you have to travel to Europe.
I'm not a huge fan of the whitespace by the building.
I have a full sized poster print of this hanging in my room :)
Again, grass takes priority over clouds.
I really like how it pushes the leaves together; also, not many artifacts are detectable in the background
At Yellowstone 5 years ago.
Technically he's a reconstructed photograph from my project 1.
I like how his turban shrank, since it was all a uniform color.
I drew this in Photshop a few years ago. When I still had time to do things. And not coding projects.
I think seam carving works especially well with pixel art.
Image from Tumblr.
Seam carving can be used to crop comics with minimal panel disruption too!
I took inspiration from the resizable text window as seen in the research video. Image from Tumblr.
An attack on whitespace. Sadly, the faces suffered some damage. This brings on our next part...
Unfortunately, seam carving is far from a perfect magic algorithm. Here are some examples that didn't work so well, whether it be their composition or that I tried to crop too much.
Photo from imgur.
While the cat and bunny pancake are unscathed, the chair and table could have smoother transitions with the wall (which is textured).
I made this poster in 2012 for one of my favorite musicians!
Seam carving didn't work well with this piece of digital art. I think it was because the background was textured, and there's no clear path across the image that doesn't run into something (be it the monkey, waves, or moon). The text was mostly preserved, though.
I took this photo in London, through the gates at Buckingham. I wanted to see if I could seamlessly remove the black bar.
Seam carving did remove the bar, but it didn't align the tiles in the background, so the disreptancy is obvious.
This was my Facebook profile picture for a while, but what if I want it also as my cover photo?
Nope, too much! My face doesn't stand a chance against the detailed grass.
Thus is the concert life
Some faces had to be sacrificed (glad it wasn't mine!)
I then tried my hand at object removal by defining a mask for the image. The part you want to remove is defined by black pixels while the part you want to keep is white pixels. I then add this mask (weighted by .8) to the original energy description. When I seam carve the image, I also seam carve the mask, to keep things consistent.
Photo from some ad-ridden news site.
Photo by NASA (they released a lot of Apollo photo archives!)
Screencap by the BBC (episode: The Sign of Three)
Although this result has its artifacts: Mary was blocking the wall and a part of Sherlock's body.
Photo by Sim Chi Yi (please watch this 10 minute documentary, it's really powerful.)
Compositionally though, I would have cropped some of the foilage on the left: but again, leaves = detailed = computers think they're important.
In addition to using the gradient, I tried two more energy functions: Canny edges and image entropy. Canny edges are a combination of smoothing, gradient intensities, and hysteresis while entropy is a measure of how much information is encoded an image using a log scale of its histogram (so you expect more "detailed" areas like edges to have a higher entropy score.)
Below is a comparison across 3 images. In my opinion, entropy and gradient give very similar results while Canny edges act more as a "normal" crop. Everything was cropped 10% in height.
A doodle I did on Photoshop
To celebrate the announcement of VR game Pokemon Go, I superimposed some X/Y promo art on top of a picture of a street in Cantebury. I also drew Pokemon of my own to add.
You can tell the characters stay the same size as the background shifts.
I really enjoyed how this project used dynamic programming: I learned about it in my algorithms class, thought it was boring, but now really appreciate it in application! I also loved how I could edit images from my own camera using a context-aware method with my own code. I own it all! I could, like, port this to a personal Photoshop extension. The coolest thing I learned from the assignment was the removal mask trick to recommend the least cost path to take a certain way, and I can imagine integrating it with gradient domain fusion to eliminate more hard artifacts. I also learned that computers love nature.