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

[Vitor]

Hi

Michael Niedermayer wrote:
> 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.
>>>       
> [...]
>   
>> +
>> +    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)
>
>
>   

I agree that doing just one dot product instead of two is faster, but I 
that code is not very speed critical, so I left it as it is for 
legibility. If you don't agree, I can change it.

> [...]
>   
>> +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
>
>   

I've tried both with inconclusive results... I guess both work equally 
well, so I kept the 1/3--2/3 version for being documented and having a 
nice geometrical interpretation.

> [...]
>   

And the rest I agree. Btw, if it is accepted, I suggest the log message 
"Codebook generator using the ELBG algorithm."

-Vitor
-------------- next part --------------
A non-text attachment was scrubbed...
Name: elbg2.diff
Type: text/x-patch
Size: 16611 bytes
Desc: not available
URL: <http://lists.mplayerhq.hu/pipermail/ffmpeg-devel/attachments/20070529/06fb1171/attachment.bin>