## Archives for: September 2007

## 09/08/07

*Spend 10 minutes collecting everything you need to work on a problem, and unplug the internet for 2 hours. You’ll finish in 30 minutes.*

## 09/03/07

Maths exam was a complete disaster, don't really know where to go next. Is it really that hard if one hasn't got a diploma to get a decent job (both now and in the far future)?

## 09/02/07

Most people most likely saw the YouTube movie on content-aware image resizing which got blogged quite a lot lately. I read the corresponding paper, and wrote an implementation (not finished/perfect at all, but well) in Python. If it would ever become "production quality" a Gimp and/or GEGL plugin would be nice.

Here's a sample:

__Original image__

__Resized using Gimp, cubic interpolation, 150px__

__Resized image, 150px__

__Overview of removed pixels__

This transformation is done in about 2 seconds (mainly because of some calculations in pure Python. For most calculations I use the Python Imaging Library and SciPy/NumPy, which are mainly C modules and much faster). As you can see the implementation still needs lots of love.

You can see another sample (image resized from 1000 to 250px in 8 seconds) here.

Git repository is here. Please email any patches!

The algorithm itself is surprisingly "simple" and easy to understand, great job by the researchers! More on that later. I should be studying mathematical analysis now, 2nd time I got to redo this exam, bloody university :-(

Update:

__Using very expensive algorithm__

This image was generated by:

- Loading the input image
- 150 times:

- Calculate energy and cost of current working picture
- For every pixel in the top row, calculate the cost of the "best path" starting at this pixel
- Figure out which path is the cheapest
- Create an image which is the working image, minus this best path
- Replace the working image with the image generated in the previous step

This took 273 seconds on my system, as the complexity is something like O(150*N*N*N*N*N*N*M) where M is the complexity of the gradient magnitude calculation.

Conclusion: not a workable solution :D

Do notice there are significant changes between this image and the one posted above. As I wrote this as a quick hack, I didn't include code to show which paths were removed from the original image.

**
**