[FFmpeg-devel] [PATCH] Add a codebook generator
Michael Niedermayer
michaelni
Tue May 29 01:21:31 CEST 2007
Hi
On Mon, May 28, 2007 at 01:23:33PM +0200, Vitor wrote:
> Vitor wrote:
> >This patch add a codebook generator to be used in the RoQ video encoder.
[...]
> +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 */
> + int r = random()%elbg->utility_inc[elbg->numCB-1];
> + while (elbg->utility_inc[i] < r)
> + i++;
> + return i;
> +}
rand*() and similar functions cannot be used as they modify the applications
state, also they are not thread safe
see libavutil/random.h
> +
> +/**
> + * Implementation of the simple LBG algorithm for just two codebooks
> + */
> +static int simple_lbg(int *centroid1, int *centroid2,
> + int *newutility1, int *newutility2,
> + int **points,
> + cell *cells, int dim)
> +{
> + int cont, error, i;
> + int numpoints1, numpoints2;
> + int *newcentroid1 = av_malloc(dim*sizeof(int));
> + int *newcentroid2 = av_malloc(dim*sizeof(int));
> + cell *tempcell;
> +
> + memset(newcentroid1, 0, dim*sizeof(int));
> + memset(newcentroid2, 0, dim*sizeof(int));
a simple
int newcentroid[2][dim];
would avoid the av_malloc() and av_free()
(note, this way of allocating arrays is only safe for small arrays so
dont use it for megabyte sized stuff, it would cause problems on some
OSs)
> +
> + numpoints1=0;
> + numpoints2=0;
> + error=0;
> + cont = 0;
> + for (tempcell = cells; tempcell != NULL; tempcell=tempcell->next) {
> + cont++;
> + if (distance(centroid1, points[tempcell->index], dim) >
> + distance(centroid2, points[tempcell->index], dim)) {
> + numpoints2++;
> + for (i=0; i<dim; i++)
> + newcentroid2[i] += points[tempcell->index][i];
> + } else {
> + numpoints1++;
> + for (i=0; i<dim; i++)
> + newcentroid1[i] += points[tempcell->index][i];
> + }
> + }
idx= distance(centroid[0], points[tempcell->index], dim) <
distance(centroid[1], points[tempcell->index], dim);
numpoints[idx]++
for (i=0; i<dim; i++)
newcentroid[idx][i] += points[tempcell->index][i];
also
(centr0 - point[i])^2 - (centr1 - point[i])^2
can be simplified to
centr0^2 - centr1^2 + 2*point[i](centr1 - centr0)
(note centr and point[] are vectors, their multiplication is the dot product)
[...]
> +static void get_new_centroids(int i, cell **cells, int *newcentroid_i,
> + int *newcentroid_p,
> + int **points, int dim)
> +{
> + cell *tempcell;
> + int *min=av_malloc(dim*sizeof(int));
> + int *max=av_malloc(dim*sizeof(int));
> + int j;
> +
> + for (j=0; j< dim; j++) {
> + min[j]=INT_MAX;
> + max[j]=0;
> + }
> +
> + for (tempcell = cells[i]; tempcell != NULL; tempcell = tempcell->next) {
> + for(j=0; j<dim; j++) {
> + min[j]=FFMIN(min[j], points[tempcell->index][j]);
> + max[j]=FFMAX(max[j], points[tempcell->index][j]);
> + }
> + }
> +
> + for (i=0; i<dim; i++) {
> + newcentroid_i[i] = min[i] + (max[i] - min[i])/3;
> + newcentroid_p[i] = min[i] + (2*(max[i] - min[i]))/3;
> + }
> +
> + av_free(min);
> + av_free(max);
> +}
iam wondering if this is better than randomly picking 2 points and making
them the 2 centroids
for example in a case like
point0 {3,-3}
point1 {-3,3}
would make
{-1,-1} and {1,1} the new centroids which would be equaly distant from both
points
[...]
> + for (tempcell=elbg->cells[i]; tempcell!=NULL; tempcell=tempcell->next) {
> + cont++;
> + for (j=0; j<elbg->dim; j++)
> + newcentroid_l[j] += elbg->points[tempcell->index][j];
> + }
> +
> + for (tempcell=elbg->cells[l]; tempcell!=NULL; tempcell=tempcell->next) {
> + cont++;
> + for (j=0; j<elbg->dim; j++)
> + newcentroid_l[j] += elbg->points[tempcell->index][j];
> + }
these 2 can be merged
> +
> + if (cont != 0)
> + for (j=0; j<elbg->dim; j++)
> + newcentroid_l[j] = newcentroid_l[j]/cont;
it should be if(cont>1) optimally
[...]
> + elbg->error -= olderror;
> + elbg->error += newerror;
elbg->error += newerror - olderror;
> +
> + elbg->utility[i] = newutility_i;
> + elbg->utility[p] = newutility_p;
> + elbg->utility[l] = newutility_l;
> +
> + for (tempcell=elbg->cells[p]; tempcell != NULL; tempcell=tempcell->next)
> + elbg->nearest_neigh[tempcell->index] = p;
> +
> + for (tempcell=elbg->cells[i]; tempcell!=NULL; tempcell=tempcell->next)
> + elbg->nearest_neigh[tempcell->index] = i;
> +
> + for (tempcell=elbg->cells[l]; tempcell!=NULL; tempcell=tempcell->next)
> + elbg->nearest_neigh[tempcell->index] = l;
putting this update stuff in a function should avoid the code triplication
[...]
> + fflush(stderr);
hmmm, this does not look like it should be in here ...
[...]
> + if (elbg->utility[0] > elbg->error*elbg->numCB)
> + elbg->utility_inc[0] = elbg->utility[0];
> + else
> + elbg->utility_inc[0] = 0;
> +
> + for (i=1; i < elbg->numCB; i++)
> + if (elbg->numCB*elbg->utility[i] > elbg->error)
> + elbg->utility_inc[i] = elbg->utility_inc[i-1] + elbg->utility[i];
> + else
> + elbg->utility_inc[i] = elbg->utility_inc[i-1];
this is duplicated, besides that it can be simplifed like:
int inc=0;
for (i=0; i < elbg->numCB; i++){
if(elbg->numCB*elbg->utility[i] > elbg->error)
inc += elbg->utility[i];
elbg->utility_inc[i]= inc;
}
[...]
> + /* 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++)
> + if (max[j] != min[j])
> + codebook[i][j] = min[j] + random()%(max[j]-min[j]);
> + else
> + codebook[i][j] = min[j];
max[j]-min[j]+1
would avoid the div by zero check and is also more correct as max cant
be reached otherwise while min can
[...]
> +
> +/**
> + * 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 .
> + *
> + * @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.
> + * @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.
> + */
> +void ff_do_elbg(int **points, int dim, int numpoints,
> + int **codebook, int numCB, int max_steps, int *closest_cb)
> +{
doxygen comments should be in the headers whenever possible (elbg.h here)
this makes them much easier to find for someone looking at the "public"
API in the header
[...]
> + elbg->error = 0;
> + /* 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(elbg->points[i], elbg->codebook[k], dim);
> + if (dist < dist_neigh[i]) {
> + dist_neigh[i] = dist;
> + elbg->nearest_neigh[i] = k;
> + }
you could pass the dist_neigh[i] to the distance() function and return
INT_MAX if the internal distance exceeds it
[...]
> + for (i=0; i < numpoints; i++) {
> + size_part[elbg->nearest_neigh[i]]++;
> + for (j=0; j < elbg->dim; j++)
> + elbg->codebook[elbg->nearest_neigh[i]][j] += elbg->points[i][j];
> + }
> +
> + for (i=0; i < elbg->numCB; i++)
> + for (j=0; j < elbg->dim; j++)
> + if(size_part[i] != 0)
> + elbg->codebook[i][j] = elbg->codebook[i][j]/size_part[i];
> + else
> + elbg->codebook[i][j] = 0;
this centroid calculation also occurs a few times in the code, maybe it
could be moved to its own function?
[...]
--
Michael GnuPG fingerprint: 9FF2128B147EF6730BADF133611EC787040B0FAB
it is not once nor twice but times without number that the same ideas make
their appearance in the world. -- 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/20070529/f3609a74/attachment.pgp>
More information about the ffmpeg-devel
mailing list