May 19, 2013

Seam Carving algorithm for Content-Aware Image Resizing

This semester I'm doing a subject in 3D graphics at the university and so far it's been very interesting! The contents of the course are based on the '3D computer graphics' book from Alan Watt and the professor, Marcelo Bertalmio, is really experienced on the field.

Last week as practical work we had to implement the Seam Carving algorithm for Content-Aware Image resizing using C++, from scratch. They gave us a month for the deadline to deliver our code and the report, but we couldn't get to work until the last day due to other assignments.

Original Image with vertical seams drawn (500 x 500 pixels)


My two lab partners and I started to program early in the morning and we didn't stop until the following morning, but we could get the algorithm to work!

The idea was that the program had to be able to resize an image, both by enlarging and reducing, by considering its content. Due to the time we had we only implemented the reducing process but it shouldn't be much harder to add the enlarging. 

The algorithm searches for the paths of pixels with less energy, both vertical and horizontal, from the gradient of the image, and eliminates these paths sequentially until we achieve the desired size. The paths must be independent from each other in the sense that they should not share any of the pixels. Therefore, we just need to remove the pixels of the path from the image and reorder them. For the enlarging process instead of removing the pixels we would repeat some of the paths with less energy next to each other until we reach to the final size.

You can see here some of the images we used, where we have drawn (in red) some of the first vertical paths with less energy (seams):

Original Image with vertical seams drawn (384 x 200 pixels)
Original Image with vertical seams drawn (285 x 190 pixels)
 So if we eliminate the seams, we get the following results:

Image after eliminating 40 vertical seams (245 x 190 pixels)
Image after eliminating 100 vertical seams (185 x 190 pixels)
Original Image (300 x 150 pixels)
Image after eliminating 100 vertical seams (200 x 150 pixels)
Image after eliminating 150 vertical seams (234 x 200 pixels)
Image after eliminating 150 vertical and 100 horizontal seams (234 x 100 pixels)
Image after eliminating 250 vertical and 100 horizontal seams (250 x 400 pixels)
Next practical lab is about creating a 3D visualization of an object from the data coordinates stored in a file, but as we haven't started yet... I will explain more details in the next post! Hope it will be soon :)