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

[Benoit Fouet]

Hi,

Vitor wrote:
> Hi
>

[snip]

> And the rest I agree. Btw, if it is accepted, I suggest the log
> message "Codebook generator using the ELBG algorithm."
>
> -Vitor
> ------------------------------------------------------------------------
>
> Index: libavcodec/elbg.c
> ===================================================================
> --- libavcodec/elbg.c	(revision 0)
> +++ libavcodec/elbg.c	(revision 0)
>   

[snip]

> +static inline void vect_division(int *res, int *vect, int div, int dim)
> +{
> +    int i;
> +    if (div > 1)
>   

why not just if(div) ?

> +        for (i=0; i<dim; i++)
> +            res[i] = vect[i]/div;
> +}
> +
>   

[snip]

> +static int get_high_utility_cell(elbg_data *elbg)
> +{
> +    int i=0;
> +    /* Using linear search, do binary if it evers turns to be speed critical */
>   

no s to ever

> +    int r = av_random(elbg->rand_state)%elbg->utility_inc[elbg->numCB-1];
> +    while (elbg->utility_inc[i] < r)
> +        i++;
> +    return i;
> +}
> +
> +/**
> + * 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 cont, error, i, idx;
> +    int numpoints[2];
> +    int newcentroid[2][dim];
> +    cell *tempcell;
> +
> +    memset(newcentroid[0], 0, dim*sizeof(int));
> +    memset(newcentroid[1], 0, dim*sizeof(int));
> +
> +    numpoints[0]=0;
> +    numpoints[1]=0;
> +    error=0;
> +    cont = 0;
>   

error and cont are unused

> +    for (tempcell = cells; tempcell != NULL; tempcell=tempcell->next) {
> +        cont++;
> +        idx = distance(centroid0, points[tempcell->index], dim) <
> +          distance(centroid1, points[tempcell->index], dim) ? 0 : 1;
> +        numpoints[idx]++;
> +        for (i=0; i<dim; i++)
> +            newcentroid[idx][i] += points[tempcell->index][i];
> +    }
> +
> +    vect_division(centroid0, newcentroid[0], numpoints[0], dim);
> +    vect_division(centroid1, newcentroid[1], numpoints[1], dim);
> +
> +    *newutility0=0;
> +    *newutility1=0;
> +    for (tempcell = cells; tempcell != NULL; tempcell=tempcell->next)
> +        if (distance(centroid0, points[tempcell->index], dim) >
> +            distance(centroid1, points[tempcell->index], dim))
> +            *newutility1 += distance(centroid1, points[tempcell->index], dim);
> +        else
> +            *newutility0 += distance(centroid0, points[tempcell->index], dim);
> +
> +    return *newutility0 + *newutility1;
> +}
> +
>   

[snip]

> +/**
> + * Evaluate if a shift lower the error. If it does, call shift_codebooks
> + * and update elbg->error, elbg->utility and elbg->nearest_neigh.
> + *
> + * @param i The low utility cell
> + * @param p The high utility cell
> + * @param l The closest cell to the i'th cell
> + */
>   

your doxygen comment lacks elbg

> +static void try_shift_candidate(elbg_data *elbg, int i, int p, int l)
>   

[snip]

> +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 max[dim];
> +    int min[dim];
> +    int i, j, 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(numpoints*sizeof(int)/8);
>   

sizeof(int*)


> Index: libavcodec/elbg.h
> ===================================================================
> --- libavcodec/elbg.h	(revision 0)
> +++ libavcodec/elbg.h	(revision 0)
> +/**
> + * Implementation of the Enhanced LBG Algorithm
> + * Based in the paper "Neural Networks 14:1219-1237" that can be found in
> + * http://citeseer.ist.psu.edu/patan01enhanced.html .
> + *
>   

based on ?

> + * @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 alloqued.
>   

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.
> + * @param rand_state A random number generator state. Should be already initialised by av_init_random.
> + */
> +
> +void ff_do_elbg(int **points, int dim, int numpoints, int **codebook,
> +                int numCB, int num_steps, int *closest_cb,
> +                AVRandomState *rand_state);
> +
>   

don't break a line between doxy comment and your function prototype

> +/**
> + * Initialize the **codebook vector for the elbg algorithm. If you have already
> + * a codebook and you want to refine it, you shouldn't call this function.
> + * If numpoints < 8*numCB this function fills **codebook with random numbers.
> + * If not, it calls ff_do_elbg for a (smaller) random sample of the points in
> + * **points. Get the same parameters as ff_do_elbg.
> + */
> +void ff_init_elbg(int **points, int dim, int numpoints, int **codebook,
> +                  int numCB, int num_steps, int *closest_cb,
> +                  AVRandomState *rand_state);
>   

Ben
-- 
Purple Labs S.A.
www.purplelabs.com