Seam Carving Jingyi Li, cs194-bx

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.

Normal Seam Carving

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.

A photo I took in Yukon, Canada

Cropped 20% vertically

Cropped 40% vertically

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.

Cropped 20% horizontally

It's nice to see all the details of the bottom strip (lake, trees, etc) compressed, not simply cropped out.

Cropped 40% horizontally

Yosemite

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.

Cropped 33% vertically

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.

Geese

I took this while studying abroad in Cambridge 2 summers ago! It's the River Cam on the way to Grantchester.

Cropped to a perfect square (500x500)

Now I can Instagram with context!

The Louvre

Of course, when you study abroad in the UK, you have to travel to Europe.

Cropped 25% vertically

I'm not a huge fan of the whitespace by the building.

Dover

I have a full sized poster print of this hanging in my room :)

Cropped to a perfect square (500x500)

Again, grass takes priority over clouds.

Some plants in Cardiff

Cropped to a perfect square (500x500)

I really like how it pushes the leaves together; also, not many artifacts are detectable in the background

Bison

At Yellowstone 5 years ago.

Cropped to a perfect square (500x500)

Normal Seam Carving (with non-photographs)

Emir

Technically he's a reconstructed photograph from my project 1.

Cropped 25% vertically

I like how his turban shrank, since it was all a uniform color.

Chinese Dragons

I drew this in Photshop a few years ago. When I still had time to do things. And not coding projects.

Cropped 33% vertically

I think seam carving works especially well with pixel art.

Dog Comic

Image from Tumblr.

Cropped 33% horizontally

Seam carving can be used to crop comics with minimal panel disruption too!

Dank Meme

I took inspiration from the resizable text window as seen in the research video. Image from Tumblr.

Cropped 33% horizontally, and then 20% vertically

An attack on whitespace. Sadly, the faces suffered some damage. This brings on our next part...

Failures

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.

Friends

Photo from imgur.

Cropped 20% vertically

While the cat and bunny pancake are unscathed, the chair and table could have smoother transitions with the wall (which is textured).

Andrew Bird Concert Poster

I made this poster in 2012 for one of my favorite musicians!

Cropped 33% vertically

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.

Buckingham Palace

I took this photo in London, through the gates at Buckingham. I wanted to see if I could seamlessly remove the black bar.

Cropped 20% horizontally

Seam carving did remove the bar, but it didn't align the tiles in the background, so the disreptancy is obvious.

Me in Edinburgh

This was my Facebook profile picture for a while, but what if I want it also as my cover photo?

Cropped to the dimensions of a cover photo

Nope, too much! My face doesn't stand a chance against the detailed grass.

Me and some strangers w/ Alex Kapranos of Franz Ferdinand

Thus is the concert life

Cropped 25% horizontally

Some faces had to be sacrificed (glad it wasn't mine!)

Bell & Whistle: Object Removal (or preservation)

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.

Three adorable baby animals!

Photo from some ad-ridden news site.

The mask to remove the middle duck.

Two adorable baby animals!

The moon!

Photo by NASA (they released a lot of Apollo photo archives!)

The moon mask to preserve the astronaunt.

Cropped 25% horizontally without a mask.

Astronaunt preserved with the mask.

John and Mary's wedding.

Screencap by the BBC (episode: The Sign of Three)

The mask to remove Mary.

John and Sherlock's wedding.

Although this result has its artifacts: Mary was blocking the wall and a part of Sherlock's body.

He Quangui and his wife Mi Shixiu.

Photo by Sim Chi Yi (please watch this 10 minute documentary, it's really powerful.)

The mask to preserve them.

Cropped 25% horizontally without a mask.

Them preserved with the mask.

Compositionally though, I would have cropped some of the foilage on the left: but again, leaves = detailed = computers think they're important.

Bell & Whistle: Different energy functions

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.

Canada (again)

Lion from Steven Universe

A doodle I did on Photoshop

Amsterdam

Canada

Gradient

Canny edges

Entropy

Lion

Gradient

Canny edges

Entropy

Amsterdam

Gradient

Canny edges

Entropy

Finally! For 7.24 points: My own scene

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.

Base Image 1

Base Image 2

The composed image.

Seam carved 10% horizontally and vertically.

You can tell the characters stay the same size as the background shifts.

Takeaways

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.