Ikke's Blog

Archives for: September 2007

Sep 8
Oh so true...

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.

Matt Mullenweg

Ikke • LifePermalink 1 comment
Sep 3

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)?

Ikke • LifePermalink 4 comments
Sep 2
Seam Carving: Content-aware image resizing

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 using Gimp

Resized image, 150px
Resized using seam carving

Overview of removed pixels
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
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.


Who's Online?

  • Guest Users: 164


XML Feeds

What is RSS?