Archives for: September 2007
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.
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)?
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:
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 :-(
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.