Seam Carving Images

Boy - there were a number of interesting things at this year's SIGGRAPPH, but so-called "Seam Carving" really seems to have caught people's attention. It seems to have hit upon exactly the right combination of: (1) Easy to demo, (2) Fake AI/magic (seeming) computer smarts, and (most importantly) (3) Relatively trivial to code. Still, even having read the preprints, I'm surprised at all the attention it seems to be receiving.

Video, which explains what I'm talking about (it is fun to watch in action):



And demos, for Windows, in Java, and even Flash, if you just want to try it online (the Windows version is the coolest).

Pretty clever. (And yes, thank you, I've seen it :P)

Shift Registers and De Bruijn Sequences

I tell ya' - everything time you think you've got a novel idea, turns out somebody's been there already... doesn't even seem to matter how small it might be.

For example: I have this minor function I wrote ages ago, which I had recently rewritten/had to re-derive. Its purpose was fairly mundane - I wanted to compute the (integer) log base 2 for a power of 2 integer value. Pretty simple and esoteric problem, but it pops up fairly often in graphics/sound programming (especially 3d stuff).

There are lots of solutions, and its not really a significant performance bottleneck or anything, but I always thought my solution was rather novel. The code looks like this : (link)


The idea is pretty simple, but clever (er... if I do say so myself, I suppose :)).

Very (very) briefly: multiplying by a power of 2 is the same as left-shifting by that power (determining that power being the log we're looking for). Therefore, we can construct a bit pattern that uniquely encodes the possible patterns sequence 0 - 31, such that any 5 bit sequence is uniquely of that range. Then multiplying by a power of two number puts a unique sequence into the top 5 bits of the result, which we can then shift down and use a table to "reverse" into our result. We need the table, because of course the encoding isn't linear with respect to the domain.

There are a number of constants you could use to fulfill this criteria, and I always thought of it as a compression/huffman tree encoding problem. The current constant I computed is 0x04ad19df.

Turns out not only is this a well known idea, but, further, its actually a special class of space filling curves (amongst other things) know as De Bruijn sequences. See the great "Bit Twiddling Hacks" page by Sean Eron Anderson for more information. The constant they computed, which of course also uses a different table, is 0x077CB531.

Results are the same.

Ah, well. Time to move on, I think..... :)

Bit shifting

I always forget that shifting positive integers and negative integers always rounds down (not towards zero), such that 126705>>3 = 15838, but -126705>>3 = -15839, which, of course can be subtle but disastrous for things like, oh, I don't know, rasterization fill conventions. Its supposed to be "live and learn", but it seems like "live, rinse, and repeat"... fixed precision computer math requires surprisingly high attention and focus...

... sigh...

But even that aside, as someone recently pointed out to me, preserving symmetry and sub-pixel accuracy is still an unsolved problem (font hinting could be considered a special case of this domain). I think its not a rasterization problem, but a geometry problem - context matters.

Sampling theory, pt 1: WPFE in pictures

I got a few questions and comments about my comment that WPFE "botched" the sampling rules for bitmaps/images. I tried to explain in the comments, but its clear I wasn't clear.

So, I'll post a clearer text/mathematical explanation shortly but here's the issue, by visual example.

First a simple "linework" image:


Next, the same image if I apply a 400% scale to the canvas, as rendered by WPFE (I cropped the result to the upper left corner):


And now, the same image, with a 400% scale as produced by my (new) rasterizer - this is also the same image that Flash 8+ and OpenGL will produce:


See the problem?

I'll explain why this isn't a black and white issue, but why I think MS landed on the wrong side of it shortly, in a follow-up. The problem is covered well in the seminal computer graphics memo from Alvy Ray Smith, "A Pixel is NOT a little square..."

Alvy Ray, of course (being Alvy Ray), is not wrong in his final conclusion, but that doesn't make his point right for all applications either, and therein lies the rub... most UI designers, I'll posit, think of images as exactly little bags of rectangles...