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

[Benjamin Larsson]

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.

> and so the distance_limited() will on average stop sooner
> note that the euclidian distance does not change between orthogonally
> transformed (=rotated) points
> though this maybe should be left for a future patch ...

MvH
Benjamin Larsson