Hi,
Let's play a little game. Forget all you know, or think you know.
Without any context at all, what does the following pattern make you think
of?
<p> X -> X X -> X
| ^
v |
X <- X X <- X
| ^
v |
X X -> X X
| ^ | ^
v | v |
X -> X X -> X
<p>
--
-Mike Melanson
<p><p>--- >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@xiph.org'
containing only the word 'unsubscribe' in the body. No subject is
needed.
Unsubscribe messages sent to the list will be ignored/filtered.
On Thu, 2003-02-27 at 16:56, Mike Melanson wrote:> Hi, > Let's play a little game. Forget all you know, or think you know. > Without any context at all, what does the following pattern make you think > of? > > > X -> X X -> X > | ^ > v | > X <- X X <- X > | ^ > v | > X X -> X X > | ^ | ^ > v | v | > X -> X X -> XThat's Hilbert's Curve, isn't it? (Of course I can't answer this if I forget all I know :) Carsten Haese <p>--- >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@xiph.org' containing only the word 'unsubscribe' in the body. No subject is needed. Unsubscribe messages sent to the list will be ignored/filtered.
> From: Mike Melanson [mailto:melanson@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@xiph.org' containing only the word 'unsubscribe' in the body. No subject is needed. Unsubscribe messages sent to the list will be ignored/filtered.
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@xiph.org > Subject: RE: [theora-dev] What's in a name? > > > > From: Mike Melanson [mailto:melanson@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@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@xiph.org' containing only the word 'unsubscribe' in the body. No subject is needed. Unsubscribe messages sent to the list will be ignored/filtered.
quote from the person directly responsible: "It is sort of like a mini-hilbert traversal on a super block row." So apparently Hilbert was involved. He also said the pattern reminded him of Space Invaders. <p>> -----Original Message-----> From: Mike Melanson [mailto:melanson@pcisys.net] > Sent: Friday, February 28, 2003 2:35 PM > To: theora-dev@xiph.org > Subject: RE: [theora-dev] What's in a name? > > > On Fri, 28 Feb 2003, Dan Miller wrote: > > > 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? > > I'm not sure if I follow you here. From my analysis, that is the > pattern used to code DCT coefficients. First, all of the DC coeffs are > decoded according to that pattern. Then all of the 1st AC > coeffs, 2nd AC > coeffs, etc. > > I don't see the pattern as having anything to do with DC > prediction. After all of the coeffs are unpacked and arranged > in rows of > fragments, the DC prediction is reversed. > > -- > -Mike Melanson > > > > --- >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@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@xiph.org' containing only the word 'unsubscribe' in the body. No subject is needed. Unsubscribe messages sent to the list will be ignored/filtered.