# [FFmpeg-devel] [PATCH] Add a codebook generator

Michael Niedermayer michaelni
Wed May 30 21:54:48 CEST 2007

```Hi

On Wed, May 30, 2007 at 09:33:08PM +0200, Benjamin Larsson wrote:
> Hi
>
> Michael Niedermayer wrote:
> > Hi
> >
> > [...]
> >
> >> +        /* This loop evaluate the actual Voronoi partition. It is the most
> >> +           costly part of the algorithm. */
> >> +        for (i=0; i < numpoints; i++) {
> >> +            for (k=0; k < elbg->numCB; k++) {
> >> +                dist = distance_limited(elbg->points[i], elbg->codebook[k], dim, dist_neigh[i]);
> >> +                if (dist < dist_neigh[i]) {
> >> +                    dist_neigh[i] = dist;
> >> +                    elbg->nearest_neigh[i] = k;
> >> +                }
> >> +            }
> >> +            elbg->error += dist_neigh[i];
> >> +            elbg->utility[elbg->nearest_neigh[i]] += dist_neigh[i];
> >> +            free_cells->index = i;
> >> +            free_cells->next = elbg->cells[elbg->nearest_neigh[i]];
> >> +            elbg->cells[elbg->nearest_neigh[i]] = free_cells;
> >> +            free_cells++;
> >> +        }
> >
> > one trick which might speed this up is to apply a orthogonal decorrelation
> > transform on the points (for example the DCT or hadamard transform) the
> > reason why this might be faster is that it concentrates the energy into
> > the first few coefficients
>
> Doesn't this depend on the distribution of the points? Can you always be
> sure the DCT or Hadamard transform will make it better? I think this
> would work if the transform used is the KLT. As it concentrates the
> energy optimally.

it of course does depend on the distribution but i think you overestimate
the gain from the KLT over the DCT for audio/video data, if that where
so big, most codecs would be based on the KLT not the DCT

but if anyone wants to try the KLT, see
http://guru.multimedia.cx/wp-content/pca.{c,h}

PS: for trying the DCT, dont forget the zigzag ordering so that coeffs are
ordered from low to high frequencs for the 2D DCT

[...]
--

I do not agree with what you have to say, but I'll defend to the death your
right to say it. -- Voltaire
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 189 bytes
Desc: not available
URL: <http://lists.mplayerhq.hu/pipermail/ffmpeg-devel/attachments/20070530/947afb61/attachment.pgp>

```