Friendly Robot Overlord

I recently saw a cool video demonstrating a different way to resize images. I was watching it late at night, and I didn't feel like wearing headphones so I just went without sound. At the end of the video I was suitably impressed. So I decided to make my own version of the program tonight. This is another one of those things where I do a bad, but workable job because of time restraints (this took a bit longer than the dithering algorithm, but I started at midnight and finished at about 1:30, so it is a pretty acceptable time scale).

The basic idea here is that when you resize an image, there are lots of parts which you care about, and lots that you don't. So if you have a person standing in front of a plain wall, it would look best if you concentrated all of your resizing efforts on the wall, since there isn't much detail there. This way, the resized image would have the person in perspective, and they would still look normal.

So, I wrote my image resizer to work like this:

1. Load an image
2. Find the edges (I don't know much about the maths behind what I did here - I used two 3x3 Sobel operators, one horizontal one vertical, and then took the sum of the absolute values for what they returned):
3. Find a path from the top of the image to the bottom, where for each step you can either go down+left, down or down+right. The path should try to go through the blackest areas in the edge picture:
4. Chop out all the pixels along this path (or more accurately, we blend the pixels on this path with the ones just on the right, and shift the rest of the image over). This gives us an image that is one pixel narrower than the original.
5. Repeat until it is narrow enough:

Pretty cool I think. Though I don't think my method is quite as robust as the inspiration. I might read the paper some day to see how they actually did it, rather than my speculation.

(test image from flickr, selected to make the algorithm look good, not to give general expected results)

If there is non-zero demand, I'm happy to put the source up (it is C) under GPL3 perhaps, just because it is new. But right now I want to go to bed.