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

[Michael Niedermayer]

Hi

On Fri, Jun 01, 2007 at 11:21:10PM +0200, Vitor wrote:
[...]
> +    int *nearest_neigh;

_neigh is a little ambigous, IMHO it should rather be _cb so its clear that
its the nearest codebook and not the nearest point


> +    int *points;
> +    AVRandomState *rand_state;
> +} elbg_data;
> +
> +static inline int distance_limited(int *a, int *b, int dim, int limit)
> +{
> +    int i, dist=0;
> +    for (i=0; i<dim; i++) {
> +        dist += (a[i] - b[i])*(a[i] - b[i]);
> +        if (dist > limit)
> +            return INT_MAX;
> +    }
> +
> +    return dist;
> +}

if a and b where 16bit/short then it would be trivial to calculate the
above with mmx
its possible with int too but it would need 2x as many reads and would
need to convert from 32 to 16bit ...


> +
> +static inline int distance(int *a, int *b, int dim)
> +{
> +    return distance_limited(a, b, dim, INT_MAX);
> +}

why not just replace the calls to distance() by distance_limited(,,,INT_MAX)
?


> +
> +static inline void vect_division(int *res, int *vect, int div, int dim)
> +{
> +    int i;
> +    if (div > 1)
> +        for (i=0; i<dim; i++)
> +            res[i] = vect[i]/div;

this should be rounded to nearest like:

if vect[i] is guranteed to be positive
(vect[i] + div/2)/div;
else 
ROUNDED_DIV(vect[i], div)


[...]
> +/**
> + * Implementation of the simple LBG algorithm for just two codebooks
> + */
> +static int simple_lbg(int *centroid0, int *centroid1,
> +                      int *newutility0, int *newutility1,
> +                      int *points,
> +                      cell *cells, int dim)
> +{
> +    int i, idx;
> +    int numpoints[2] = {0,0};
> +    int newutility[2] = {0,0};
> +    int newcentroid[2][dim];
> +    cell *tempcell;
> +
> +    memset(newcentroid[0], 0, dim*sizeof(int));
> +    memset(newcentroid[1], 0, dim*sizeof(int));

memset(newcentroid, 0, sizeof(newcentroid));


> +
> +    for (tempcell = cells; tempcell; tempcell=tempcell->next) {
> +        idx = distance(centroid0, points + tempcell->index*dim, dim) >=
> +              distance(centroid1, points + tempcell->index*dim, dim);
> +        numpoints[idx]++;
> +        for (i=0; i<dim; i++)
> +            newcentroid[idx][i] += points[tempcell->index*dim + i];
> +    }
> +
> +    vect_division(centroid0, newcentroid[0], numpoints[0], dim);
> +    vect_division(centroid1, newcentroid[1], numpoints[1], dim);
> +
> +    for (tempcell = cells; tempcell; tempcell=tempcell->next) {
> +        int dist[2] = {distance(centroid0, points + tempcell->index*dim, dim),
> +                       distance(centroid1, points + tempcell->index*dim, dim)};
> +        int idx = dist[0] > dist[1];
> +        newutility[idx] += dist[idx];
> +    }
> +
> +    *newutility0=newutility[0];
> +    *newutility1=newutility[1];

the one and only call to simple_lbg has the newutility* elements in an array
so it might make sense to pass that array instead of 2 pointers which then get
set to the values of the internal array


[...]
> +    elbg->cells[indexes[0]]=NULL;
> +    tempdata=elbg->cells[indexes[1]];
> +    elbg->cells[indexes[1]] = NULL;

nitpick: the spaces around = are inconsistant


[...]
> +static void do_shiftings(elbg_data *elbg)
> +{
> +    int luc;
> +    int huc, cluc;
> +    int idx[3];
> +
> +    evaluate_utility_inc(elbg);
> +
> +    for (luc=0; luc < elbg->numCB; luc++)
> +        if (elbg->numCB*elbg->utility[luc] < elbg->error) {
> +            if (elbg->utility_inc[elbg->numCB-1] == 0)
> +                return;
> +
> +            huc = get_high_utility_cell(elbg);
> +            cluc = get_closest_codebook(elbg, luc);
> +
> +            idx[0]=luc;
> +            idx[1]=huc;
> +            idx[2]=cluc;
> +
> +            try_shift_candidate(elbg, idx);
> +        }
> +}

the huc, cluc variables are useless, the array could easily be used
as destination directly


> +
> +void ff_init_elbg(int *points, int dim, int numpoints, int *codebook,
> +                  int numCB, int max_steps, int *closest_cb,
> +                  AVRandomState *rand_state)
> +{
> +    int *temp_points;
> +    int i, k;
> +
> +    if (numpoints > 24*numCB) {
> +        /* ELBG is very costly for a big number of points. So if we have a lot
> +           of them, get a good initial codebook to save on iterations       */
> +        temp_points = av_malloc(dim*(numpoints/8)*sizeof(int));
> +        for (i=0; i<numpoints/8; i++) {
> +            k = (i*97) % numpoints;

97 is not guranteed to be relative prim to numpoints
if for example numpoints is x*97 this will not behave well ...
simply choosing a larger prime should fix that
for example 433494437LL would be an option (picked from 
http://en.wikipedia.org/wiki/List_of_prime_numbers)


> +            memcpy(temp_points + i*dim, points + k*dim, dim*sizeof(int));
> +        }
> +
> +        ff_init_elbg(temp_points, dim, numpoints/8, codebook, numCB, 2*max_steps, closest_cb, rand_state);
> +        ff_do_elbg(temp_points, dim, numpoints/8, codebook, numCB, 2*max_steps, closest_cb, rand_state);
> +
> +        av_free(temp_points);
> +
> +    } else  // If not, initialize the codebook with random positions
> +        for (i=0; i < numCB; i++)
> +            memcpy(codebook + i*dim, points + ((i*97)%numCB)*dim,
> +                   dim*sizeof(int));

shouldnt this be % numpoints instead of numCB?


[...]
> +        for (i=0; i < elbg->numCB; i++)
> +          vect_division(elbg->codebook + i*elbg->dim,
> +                        elbg->codebook + i*elbg->dim, size_part[i],
> +                        elbg->dim);

indention is inconsistant


[...]
> +/**
> + * Implementation of the Enhanced LBG Algorithm
> + * Based on the paper "Neural Networks 14:1219-1237" that can be found in
> + * http://citeseer.ist.psu.edu/patan01enhanced.html .
> + *
> + * @param points Input points
> + * @param dim Dimension of the points
> + * @param numpoints Num of points in **points
> + * @param codebook Pointer to the output codebook. Must be allocated.
> + * @param numCB Number of points in the codebook
> + * @param max_steps The maximum number of steps. One step is already a good compromise between time and quality.

max_steps vs. num_steps



> + * @param rand_state A random number generator state. Should be already initialised by av_init_random.
> + */

closest_cb is missing

[...]

-- 
Michael     GnuPG fingerprint: 9FF2128B147EF6730BADF133611EC787040B0FAB

The misfortune of the wise is better than the prosperity of the fool.
-- Epicurus
-------------- 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/20070602/52b475f0/attachment.pgp>