[FFmpeg-devel] [PATCH] Add a codebook generator
Vitor
vitor1001
Tue May 29 22:14:11 CEST 2007
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>
More information about the ffmpeg-devel
mailing list