[theora-dev] What's in a name?

[Dan Miller]

> From: Mike Melanson [mailto:melanson at pcisys.net]
...
> > >
> > >
> > >       X -> X    X -> X
> > >            |    ^
> > >            v    |
> > >       X <- X    X <- X
> > >       |              ^
> > >       v              |
> > >       X    X -> X    X
> > >       |    ^    |    ^
> > >       v    |    v    |
> > >       X -> X    X -> X
> >
...
> 	Dan: Can you confirm or deny that the pattern is based on the
> Hilbert Curve? Or is that some strange coincidence?

This pattern is basically a solution to the traveling salesman problem on a 4x4 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 8x8 blocks 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.
--- >8 ----
List archives:  http://www.xiph.org/archives/
Ogg project homepage: http://www.xiph.org/ogg/
To unsubscribe from this list, send a message to 'theora-dev-request at xiph.org'
containing only the word 'unsubscribe' in the body.  No subject is needed.
Unsubscribe messages sent to the list will be ignored/filtered.