[FFmpeg-devel] [PATCH] Add a codebook generator
Michael Niedermayer
michaelni
Wed May 30 21:03:31 CEST 2007
Hi
On Wed, May 30, 2007 at 12:45:07PM +0200, Vitor wrote:
> Hi
>
> Benoit Fouet wrote:
> >Hi,
> >
> >>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;
> >>+}
> >>+
> >>
> >>
> >
> >
> The idea was not to spend time dividing the whole vector by 1. But there
> was a bug in the code, I changed it to
>
> if (div > 1)
> for (i=0; i<dim; i++)
> res[i] = vect[i]/div;
> else if (res != vect)
> for (i=0; i<dim; i++)
> res[i] = vect[i];
>
>
> And I agree with the other comments.
[...]
> +/**
> + * ELBG internal data
> + */
> +typedef struct{
> + int error;
> + int dim;
> + int numCB;
> + int **codebook;
> + cell **cells;
> + int *utility;
> + int *utility_inc;
> + int *nearest_neigh;
> + int **points;
why not *points and points[index + component] instead of
points[index][component]?
this would avoid an extra pointer dereference, simplify allocation, freeing
and memseting of the array, it also would ensure that the array is
contiguous in memory which might improve speed
same question for codebook
[...]
> +static inline int distance(int *a, int *b, int dim)
> +{
> + int i, dist=0;
> + for (i=0; i<dim; i++)
> + dist += (a[i] - b[i])*(a[i] - b[i]);
> +
> + return dist;
> +}
> +
> +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;
> +}
hmm doesnt gcc optimize the check away if
distance_limited(,,, INT_MAX)
is used?
it should realize that the check cant be true ...
[...]
> + for (i=0; i<dim; i++)
> + res[i] = vect[i];
memcpy()
[...]
> +static int get_closest_codebook(elbg_data *elbg, int index)
> +{
> + int i, pick=0, diff, diff_min = INT_MAX;
> + for (i=0; i<elbg->numCB; i++)
> + if (i != index) {
> + diff = distance(elbg->codebook[i], elbg->codebook[index], elbg->dim);
> + if (diff < diff_min) {
> + pick = i;
> + diff_min = diff;
> + }
> + }
> + return pick;
> +}
this should use distance_limited()
[...]
> +
> +/**
> + * 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];
> + 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;
int numpoints[2]={0,0};
int newcentroid[2][dim]= {0};
> +
> + for (tempcell = cells; tempcell != NULL; tempcell=tempcell->next) {
for (tempcell = cells; tempcell; tempcell=tempcell->next) {
> + idx = distance(centroid0, points[tempcell->index], dim) <
> + distance(centroid1, points[tempcell->index], dim) ? 0 : 1;
int idx= distance(centroid0, points[tempcell->index], dim) >=
distance(centroid1, points[tempcell->index], dim);
(that is 1. align for better readability and 2. removing unneeded ?0:1)
[...]
> + *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;
newutility[0]=
newutility[1]= 0;
for(tempcell = cells; tempcell; tempcell=tempcell->next){
int dist[2]= {distance(centroid0, points[tempcell->index], dim),
distance(centroid1, points[tempcell->index], dim)};
int idx= dist[0] > dist[1];
newutility[idx] += dist[idx];
}
[...]
> +/**
> + * Add the points in the i cell to the l cell. Split the p cell, putting the
> + * separed points in the (now empty) i cell.
> + */
> +static void shift_codebook(elbg_data *elbg, int i, int p, int l,
> + int *newcentroid_i, int *newcentroid_p,
> + int *newcentroid_l)
> +{
> + cell *tempdata, *tempcell2;
> +
> + if (elbg->cells[l] == NULL)
> + elbg->cells[l] = elbg->cells[i];
> + else {
> + for(tempdata=elbg->cells[l]; tempdata->next!=NULL;
> + tempdata=tempdata->next);
> + tempdata->next = elbg->cells[i];> + }
cell **pp= &elbg->cells[l];
while(*pp)
pp= &(*pp)->next;
*pp= elbg->cells[i];
[...]
> + while(tempdata != NULL) {
> + tempcell2=tempdata->next;
> +
> + if (distance(elbg->points[tempdata->index], newcentroid_i, elbg->dim) >
> + distance(elbg->points[tempdata->index], newcentroid_p, elbg->dim)) {
> + tempdata->next = elbg->cells[p];
> + elbg->cells[p] = tempdata;
> + } else {
> + tempdata->next = elbg->cells[i];
> + elbg->cells[i] = tempdata;
> + }
> + tempdata = tempcell2;
> + }
while(tempdata) {
cell *tempcell2=tempdata->next;
int idx= distance(elbg->points[tempdata->index], newcentroid[0], elbg->dim) >
distance(elbg->points[tempdata->index], newcentroid[1], elbg->dim);
tempdata->next = elbg->cells[i[idx]];
elbg->cells[i[idx]] = tempdata;
tempdata = tempcell2;
}
[...]
> +/**
> + * 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
may i protest against the i/p/l naming
a more logic naming would be
luc low utility cell
huc high utility cell
cluc The closest cell to the low untilit cell
there are of course millions of other namings but the i/p/l looks completely
arbitrary to me, also i is generally an integer used in for loops and not
some argument ...
and these parameters could also be passed as an array like
{cluc, luc, huc} or another order
this would simplify some code, for example it would avoid the
int idx[2] = {i, l};
[...]
> + update_utility_and_neigh(elbg, i, newutility_i);
> + update_utility_and_neigh(elbg, p, newutility_p);
> + update_utility_and_neigh(elbg, l, newutility_l);
for(j=0; j<3; j++)
update_utility_and_neigh(elbg, idx[j], newutility[j]);
[...]
> +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);
> + for (i=0; i<numpoints/8; i++) {
> + temp_points[i] = av_malloc(dim*sizeof(int));
> + k=av_random(rand_state)%(numpoints);
why not just take every 8th point? it would be simpler and avoid taking
some points twice
if you are concerned about the non randomness you could also use a more
complex selection like
(i * P) % numpoints
where P is relative prim to numpoints
this too would avoid taking points twice
> + for (j=0; j<dim; j++)
> + temp_points[i][j] = points[k][j];
memcpy()
[...]
> + /* If not, initialize the codebook with random positions */
> + for (j=0; j < dim; j++) {
> + max[j] = 0;
> + min[j] = INT_MAX;
> + }
> + for (i=0; i < numpoints; i++)
> + for (j=0; j < dim; j++) {
> + max[j] = FFMAX(max[j], points[i][j]);
> + min[j] = FFMIN(min[j], points[i][j]);
> + }
> +
> + for (i=0; i < numCB; i++)
> + for (j=0; j < dim; j++)
> + codebook[i][j] = min[j] +
> + av_random(rand_state)%(max[j]-min[j]+1);
hmm, isnt simply taking random points as initial codebook better?
[...]
> + /* 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 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 ...
[...]
--
Michael GnuPG fingerprint: 9FF2128B147EF6730BADF133611EC787040B0FAB
The worst form of inequality is to try to make unequal things equal.
-- Aristotle
-------------- 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/037e3243/attachment.pgp>
More information about the ffmpeg-devel
mailing list