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

Michael Niedermayer michaelni
Mon Jun 5 12:58:08 CEST 2006

```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

```

More information about the ffmpeg-devel mailing list