Breaking Eggs And Making Omelettes

Topics On Multimedia Technology and Reverse Engineering


Archives:

The Legend Of Hilbert

April 19th, 2007 by Multimedia Mike

I’ve been wanting to learn how to use a basic vector drawing program for some time now for the purpose of illustrating certain codec concepts more concretely. Sure, this will be for the benefit of others who are curious about the craft. But mostly, I do it for me because, well… me like pictures.

Behold, my first vector drawing, constructed using OpenOffice’s Draw program:


VP3/Theora Superblock Traversal Pattern

When I was first reverse engineering an English language description of the VP3 format and implementing a new decoder for FFmpeg, I figured out the curious pattern that the codec uses to traverse 4×4 fragments (blocks of 8×8 samples) within a VP3 superblock. I posted to the theora-dev mailing list asking if the pattern struck anyone as familiar. Personally, the pattern reminded me of playing the original NES The Legend of Zelda title, sort of like a pattern for traversing rooms in a dungeon. In fact, early iterations of my decoder used the identifier zelda[].

However, someone on the list identified it as resembling a Hilbert curve, discovered by some famous math dude. One of the codec’s designers chimed in on the list and stated that he had never even heard of Hilbert and that the traversal pattern was chosen to meet certain criteria. Any resemblance to the Hilbert curve was to be considered strictly coincidental.

Looking back on that old mailing list traffic, and taking a good look at the actual Hilbert curve from the link above, I may have made a mistake in using the term “Hilbert pattern” to describe the traversal sequence pictured above. It’s a little late now to change it back to “Zelda pattern”– Google demonstrates that the first term sort of caught on for VP3/Theora-related matters.

Posted in Open Source Multimedia, VP3/Theora | 4 Comments »

4 Responses

  1. Kostya Says:

    Hmm, I don’t think they got it purely coincidental as this is one of space-filling curves and maybe the only one that fills square area.

    Also they could get idea from this source:
    Meander (art)
    BTW, look at the third meander.

  2. Multimedia Mike Says:

    Nice find, Kostya. I dug up the old email from Dan Miller, one of VP3’s designers (he also worked on earlier codecs such as Duck TM1 and TM2):


    This pattern is basically a solution to the traveling salesman problem on a 4×4 grid. Each point on the grid is traversed exactly once, with a minimum distance traveled between gridpoints (one unit). If you tesselate the pattern from left to right, you also travel only one unit between blocks.

    This is important because it maximizes correlation between samples when constrained to a single predictor (ie linear delta coding). I believe this is the pattern we use to predict DC coeffs in a ‘superblock’ (32 x 32 block with 16 8×8 bloc
    ks within), no?

    It also looks to me like one of Knuth’s error-distribution functions (used for greyscale printing on B&W printers).

    I have never heard of the Hilbert curve, but then I’m a college dropout.

  3. Maps For Shadowgate and Uninvited | Gaming Pathology Says:

    […] that “Ok” prompt in the upper left corner. Come to think of it, since I have been playing around with vector drawing programs lately, maybe redoing these maps with such a tool would be a useful […]

  4. Kostya’s Wild Codec World » Bink: pattern-run blocks Says:

    […] in usual scan orders but following one of 16 predefined patterns – columns, spirals, Hilbert curve (Zelda pattern for some of us), […]