[Ffmpeg-devel] Trellis Quantization Applied To (A)DPCM

[Michael Niedermayer]

Hi

On Sun, Jun 04, 2006 at 10:01:01PM -0700, Loren Merritt wrote:
> On Sun, 4 Jun 2006, Michael Niedermayer wrote:
> >On Sat, Jun 03, 2006 at 09:45:36PM -0700, Loren Merritt wrote:
> >>
> >>Hmm... my initial implementation doesn't see noticeable gains from K-Means
> >>over just using a constant exponential table.
> >
> >i think that in case of optimally choosing the deltas a less "regular" 
> >table
> >then your constant table would be supperior, the reason why i think so is 
> >that
> >in your constant table many sums of elements are equal which should lead to
> >fewer "easy reachable" values, for example:
> >
> >if we have a input of 0 12 3 then that could be encoded with +16,-16 or
> >+8,-8 with your table if the table where slightly less regular then the
> >2 cases would be able to reach 2 different final results and that might
> >lead to a better approximation ...
> 
> Added some asymmetric tables. They helped only a little, but I don't 
> really know what to optimize for when writing a table by hand.
> 
> OTOH, a brute-force iterative search isn't too ridiculously slow. The next 

the iterative search seems to get stuck in local minima ...
if i add the following:
                for(i=0; i<16*16*4; i++){
                    int i0= i&15;
                    int i1= (i>>4)&15;
                    int d0= ((i>>8)&1)*2-1;
                    int d1= ((i>>9)&1)*2-1;

                    if(i0>=i1)
                        continue;
                    memcpy(tmp, table, 16);
                    tmp[i0] += d0;
                    tmp[i1] += d1;
                    if(   tmp[i0] >= tmp[i0+1] || tmp[i0] <= tmp[i0-1]
                       || tmp[i1] >= tmp[i1+1] || tmp[i1] <= tmp[i1-1])
                        continue;

                    try_table(tmp, table, &bssd, pix, w, h, stride);
                }
then 
fn 23 tables_tried 7823 
  4fa79  14e26b                   5179d   4d7ad  15cf7c  1117b2 s    
  4d7ad  c0 e0 f0 f8 fc fe ff  0  1  2  3  6  c 18 30 60
  46089  bf df ef f7 fb fe ff  0  1  2  3  6  d 18 30 5a
  40d5c  c0 de ef f7 fb fe ff  0  1  2  4  6  d 1a 30 53
  3e8f1  c1 de ee f6 fb fe ff  0  1  2  3  6  e 1a 30 54
  3c80c  c0 de ed f6 fb fe ff  0  1  2  3  7  e 1a 30 53
   8902    34bc    3c4a         
   34bc  e0 f0 f8 fa fc fd fe ff  0  1  2  3  4  6  8 10
   2878  e2 ef f5 f9 fc fd fe ff  0  1  2  3  4  6  a 10
   2672  e4 ef f4 f9 fc fd fe ff  0  1  2  3  4  6  a 10
   262a  e5 ef f4 f9 fc fd fe ff  0  1  2  3  4  6  a 10
  10fb4    40d4    4de0         
   40d4  e0 f0 f8 fa fc fd fe ff  0  1  2  3  4  6  8 10
   31be  e5 f3 f7 f9 fc fd fe ff  0  1  2  3  4  6  a 10
   2712  ec f3 f6 f9 fc fd fe ff  0  1  2  3  4  7  a 10
changes too
fn 23 tables_tried 46783 
  4fa79  14e26b                   5179d   4d7ad  15cf7c  1117b2 s    
  4d7ad  c0 e0 f0 f8 fc fe ff  0  1  2  3  6  c 18 30 60
  38668  bf dc eb f4 fb fe ff  0  1  2  5  9 10 1f 35 5a
  2fbbc  bf d7 e7 f1 f7 fc ff  0  1  2  5  a 12 21 36 53
  2deab  bf d7 e6 f1 f7 fc ff  0  1  2  5  a 13 21 35 50
   8902    34bc    3c4a         
   34bc  e0 f0 f8 fa fc fd fe ff  0  1  2  3  4  6  8 10
   26ee  e2 ed f4 f9 fc fd fe ff  0  1  2  3  4  7  a 10
   2634  e3 ee f3 f8 fb fd fe ff  0  1  2  3  4  7  a 10
   23a2  e4 ec f2 f7 fa fd fe ff  0  1  2  3  6  8  b 10
   2302  e4 ec f2 f7 fa fd fe ff  0  1  2  3  6  9  b 11
   22fa  e4 ec f2 f7 fa fd fe ff  0  1  2  3  6  9  c 11
   22ee  e4 eb f2 f7 fa fd fe ff  0  1  2  3  6  9  c 11
  10fb4    40d4    4de0         
   40d4  e0 f0 f8 fa fc fd fe ff  0  1  2  3  4  6  8 10
   2bba  e5 ef f6 f9 fc fd fe ff  0  1  2  3  4  7  a 10
   2a10  e7 ef f5 f8 fb fd fe ff  0  1  2  3  4  7  a 10
   29ac  e8 f0 f5 f8 fb fd fe ff  0  1  2  3  4  7  a 10
   2862  eb f0 f5 f8 fb fd fe ff  0  1  2  3  4  7  a 10

[...]

-- 
Michael     GnuPG fingerprint: 9FF2128B147EF6730BADF133611EC787040B0FAB

In the past you could go to a library and read, borrow or copy any book
Today you'd get arrested for mere telling someone where the library is