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

[Dan Miller]

thinking some more --

a down-up scan would also solve the salesman's dilemma.  I think we also wanted to keep the scan as 'local' as possible, ie get as much correlation from the immediate 2D neighborhood as possible.  So in a sense, it solves the 2x2 traveling salesman on each 2x2 block, then solves it globally on the 4x4 block.  Something like that.

I was looking at this pattern for some other reason once, but I can't remember why.

> -----Original Message-----
> From: Dan Miller 
> Sent: Friday, February 28, 2003 1:48 AM
> To: theora-dev at xiph.org
> Subject: RE: [theora-dev] What's in a name?
> 
> 
> > 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.
> 
--- >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.