← Back to branch summary

~ubuntu-branches/ubuntu/jaunty/xvidcap/jaunty-proposed

« back to all changes in this revision

Viewing changes to ffmpeg/libavcodec/elbg.c

  • Committer: Bazaar Package Importer
  • Author(s): Lionel Le Folgoc, Andrew Starr-Bochicchio, Lionel Le Folgoc
  • Date: 2008-12-26 00:10:06 UTC
  • mfrom: (1.1.2 upstream)
  • Revision ID: james.westby@ubuntu.com-20081226001006-2040ls9680bd1blt
Tags: 1.1.7-0.2ubuntu1
https://launchpad.net/bugs/298547
https://launchpad.net/bugs/311412
[ Andrew Starr-Bochicchio ]
* Merge from debian-multimedia (LP: #298547), Ubuntu Changes:
 - For ffmpeg-related build-deps, fix versionized dependencies
   as the ubuntu versioning is different than debian-multimedia's.

[ Lionel Le Folgoc ]
* LP: #311412 is fixed since the 1.1.7~rc1-0.1 revision.
* debian/patches/03_ffmpeg.diff: updated to fix FTBFS due to libswscale API
  change (cherry-pick from Gentoo #234383).

Show diffs side-by-side

added added

removed removed

Lines of Context:
ffmpeg/libavcodec/elbg.c
 
1
/*
 
2
 * Copyright (C) 2007 Vitor Sessak <vitor1001@gmail.com>
 
3
 *
 
4
 * This file is part of FFmpeg.
 
5
 *
 
6
 * FFmpeg is free software; you can redistribute it and/or
 
7
 * modify it under the terms of the GNU Lesser General Public
 
8
 * License as published by the Free Software Foundation; either
 
9
 * version 2.1 of the License, or (at your option) any later version.
 
10
 *
 
11
 * FFmpeg is distributed in the hope that it will be useful,
 
12
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 
13
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 
14
 * Lesser General Public License for more details.
 
15
 *
 
16
 * You should have received a copy of the GNU Lesser General Public
 
17
 * License along with FFmpeg; if not, write to the Free Software
 
18
 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
 
19
 */
 
20
 
 
21
/**
 
22
 * @file cbook_gen.c
 
23
 * Codebook Generator using the ELBG algorithm
 
24
 */
 
25
 
 
26
#include <string.h>
 
27
 
 
28
#include "elbg.h"
 
29
#include "avcodec.h"
 
30
#include "random.h"
 
31
 
 
32
#define DELTA_ERR_MAX 0.1  ///< Precision of the ELBG algorithm (as percentual error)
 
33
 
 
34
/**
 
35
 * In the ELBG jargon, a cell is the set of points that are closest to a
 
36
 * codebook entry. Not to be confused with a RoQ Video cell. */
 
37
typedef struct cell_s {
 
38
    int index;
 
39
    struct cell_s *next;
 
40
} cell;
 
41
 
 
42
/**
 
43
 * ELBG internal data
 
44
 */
 
45
typedef struct{
 
46
    int error;
 
47
    int dim;
 
48
    int numCB;
 
49
    int *codebook;
 
50
    cell **cells;
 
51
    int *utility;
 
52
    int *utility_inc;
 
53
    int *nearest_cb;
 
54
    int *points;
 
55
    AVRandomState *rand_state;
 
56
} elbg_data;
 
57
 
 
58
static inline int distance_limited(int *a, int *b, int dim, int limit)
 
59
{
 
60
    int i, dist=0;
 
61
    for (i=0; i<dim; i++) {
 
62
        dist += (a[i] - b[i])*(a[i] - b[i]);
 
63
        if (dist > limit)
 
64
            return INT_MAX;
 
65
    }
 
66
 
 
67
    return dist;
 
68
}
 
69
 
 
70
static inline void vect_division(int *res, int *vect, int div, int dim)
 
71
{
 
72
    int i;
 
73
    if (div > 1)
 
74
        for (i=0; i<dim; i++)
 
75
            res[i] = ROUNDED_DIV(vect[i],div);
 
76
    else if (res != vect)
 
77
        memcpy(res, vect, dim*sizeof(int));
 
78
 
 
79
}
 
80
 
 
81
static int eval_error_cell(elbg_data *elbg, int *centroid, cell *cells)
 
82
{
 
83
    int error=0;
 
84
    for (; cells; cells=cells->next)
 
85
        error += distance_limited(centroid, elbg->points + cells->index*elbg->dim, elbg->dim, INT_MAX);
 
86
 
 
87
    return error;
 
88
}
 
89
 
 
90
static int get_closest_codebook(elbg_data *elbg, int index)
 
91
{
 
92
    int i, pick=0, diff, diff_min = INT_MAX;
 
93
    for (i=0; i<elbg->numCB; i++)
 
94
        if (i != index) {
 
95
            diff = distance_limited(elbg->codebook + i*elbg->dim, elbg->codebook + index*elbg->dim, elbg->dim, diff_min);
 
96
            if (diff < diff_min) {
 
97
                pick = i;
 
98
                diff_min = diff;
 
99
            }
 
100
        }
 
101
    return pick;
 
102
}
 
103
 
 
104
static int get_high_utility_cell(elbg_data *elbg)
 
105
{
 
106
    int i=0;
 
107
    /* Using linear search, do binary if it ever turns to be speed critical */
 
108
    int r = av_random(elbg->rand_state)%elbg->utility_inc[elbg->numCB-1];
 
109
    while (elbg->utility_inc[i] < r)
 
110
        i++;
 
111
    return i;
 
112
}
 
113
 
 
114
/**
 
115
 * Implementation of the simple LBG algorithm for just two codebooks
 
116
 */
 
117
static int simple_lbg(int dim,
 
118
                      int *centroid[3],
 
119
                      int newutility[3],
 
120
                      int *points,
 
121
                      cell *cells)
 
122
{
 
123
    int i, idx;
 
124
    int numpoints[2] = {0,0};
 
125
    int newcentroid[2][dim];
 
126
    cell *tempcell;
 
127
 
 
128
    memset(newcentroid, 0, sizeof(newcentroid));
 
129
 
 
130
    newutility[0] =
 
131
    newutility[1] = 0;
 
132
 
 
133
    for (tempcell = cells; tempcell; tempcell=tempcell->next) {
 
134
        idx = distance_limited(centroid[0], points + tempcell->index*dim, dim, INT_MAX)>=
 
135
              distance_limited(centroid[1], points + tempcell->index*dim, dim, INT_MAX);
 
136
        numpoints[idx]++;
 
137
        for (i=0; i<dim; i++)
 
138
            newcentroid[idx][i] += points[tempcell->index*dim + i];
 
139
    }
 
140
 
 
141
    vect_division(centroid[0], newcentroid[0], numpoints[0], dim);
 
142
    vect_division(centroid[1], newcentroid[1], numpoints[1], dim);
 
143
 
 
144
    for (tempcell = cells; tempcell; tempcell=tempcell->next) {
 
145
        int dist[2] = {distance_limited(centroid[0], points + tempcell->index*dim, dim, INT_MAX),
 
146
                       distance_limited(centroid[1], points + tempcell->index*dim, dim, INT_MAX)};
 
147
        int idx = dist[0] > dist[1];
 
148
        newutility[idx] += dist[idx];
 
149
    }
 
150
 
 
151
    return newutility[0] + newutility[1];
 
152
}
 
153
 
 
154
static void get_new_centroids(elbg_data *elbg, int huc, int *newcentroid_i,
 
155
                              int *newcentroid_p)
 
156
{
 
157
    cell *tempcell;
 
158
    int min[elbg->dim];
 
159
    int max[elbg->dim];
 
160
    int i;
 
161
 
 
162
    for (i=0; i< elbg->dim; i++) {
 
163
        min[i]=INT_MAX;
 
164
        max[i]=0;
 
165
    }
 
166
 
 
167
    for (tempcell = elbg->cells[huc]; tempcell; tempcell = tempcell->next)
 
168
        for(i=0; i<elbg->dim; i++) {
 
169
            min[i]=FFMIN(min[i], elbg->points[tempcell->index*elbg->dim + i]);
 
170
            max[i]=FFMAX(max[i], elbg->points[tempcell->index*elbg->dim + i]);
 
171
        }
 
172
 
 
173
    for (i=0; i<elbg->dim; i++) {
 
174
        newcentroid_i[i] = min[i] + (max[i] - min[i])/3;
 
175
        newcentroid_p[i] = min[i] + (2*(max[i] - min[i]))/3;
 
176
    }
 
177
}
 
178
 
 
179
/**
 
180
 * Add the points in the low utility cell to its closest cell. Split the high
 
181
 * utility cell, putting the separed points in the (now empty) low utility
 
182
 * cell.
 
183
 *
 
184
 * @param elbg         Internal elbg data
 
185
 * @param indexes      {luc, huc, cluc}
 
186
 * @param newcentroid  A vector with the position of the new centroids
 
187
 */
 
188
static void shift_codebook(elbg_data *elbg, int *indexes,
 
189
                           int *newcentroid[3])
 
190
{
 
191
    cell *tempdata;
 
192
    cell **pp = &elbg->cells[indexes[2]];
 
193
 
 
194
    while(*pp)
 
195
        pp= &(*pp)->next;
 
196
 
 
197
    *pp = elbg->cells[indexes[0]];
 
198
 
 
199
    elbg->cells[indexes[0]] = NULL;
 
200
    tempdata = elbg->cells[indexes[1]];
 
201
    elbg->cells[indexes[1]] = NULL;
 
202
 
 
203
    while(tempdata) {
 
204
        cell *tempcell2 = tempdata->next;
 
205
        int idx = distance_limited(elbg->points + tempdata->index*elbg->dim,
 
206
                           newcentroid[0], elbg->dim, INT_MAX) >
 
207
                  distance_limited(elbg->points + tempdata->index*elbg->dim,
 
208
                           newcentroid[1], elbg->dim, INT_MAX);
 
209
 
 
210
        tempdata->next = elbg->cells[indexes[idx]];
 
211
        elbg->cells[indexes[idx]] = tempdata;
 
212
        tempdata = tempcell2;
 
213
    }
 
214
}
 
215
 
 
216
static void evaluate_utility_inc(elbg_data *elbg)
 
217
{
 
218
    int i, inc=0;
 
219
 
 
220
    for (i=0; i < elbg->numCB; i++) {
 
221
        if (elbg->numCB*elbg->utility[i] > elbg->error)
 
222
            inc += elbg->utility[i];
 
223
        elbg->utility_inc[i] = inc;
 
224
    }
 
225
}
 
226
 
 
227
 
 
228
static void update_utility_and_n_cb(elbg_data *elbg, int idx, int newutility)
 
229
{
 
230
    cell *tempcell;
 
231
 
 
232
    elbg->utility[idx] = newutility;
 
233
    for (tempcell=elbg->cells[idx]; tempcell; tempcell=tempcell->next)
 
234
        elbg->nearest_cb[tempcell->index] = idx;
 
235
}
 
236
 
 
237
/**
 
238
 * Evaluate if a shift lower the error. If it does, call shift_codebooks
 
239
 * and update elbg->error, elbg->utility and elbg->nearest_cb.
 
240
 *
 
241
 * @param elbg  Internal elbg data
 
242
 * @param indexes      {luc (low utility cell, huc (high utility cell), cluc (closest cell to low utility cell)}
 
243
 */
 
244
static void try_shift_candidate(elbg_data *elbg, int idx[3])
 
245
{
 
246
    int j, k, olderror=0, newerror, cont=0;
 
247
    int newutility[3];
 
248
    int newcentroid[3][elbg->dim];
 
249
    int *newcentroid_ptrs[3] = { newcentroid[0], newcentroid[1], newcentroid[2] };
 
250
    cell *tempcell;
 
251
 
 
252
    for (j=0; j<3; j++)
 
253
        olderror += elbg->utility[idx[j]];
 
254
 
 
255
    memset(newcentroid[2], 0, elbg->dim*sizeof(int));
 
256
 
 
257
    for (k=0; k<2; k++)
 
258
        for (tempcell=elbg->cells[idx[2*k]]; tempcell; tempcell=tempcell->next) {
 
259
            cont++;
 
260
            for (j=0; j<elbg->dim; j++)
 
261
                newcentroid[2][j] += elbg->points[tempcell->index*elbg->dim + j];
 
262
        }
 
263
 
 
264
    vect_division(newcentroid[2], newcentroid[2], cont, elbg->dim);
 
265
 
 
266
    get_new_centroids(elbg, idx[1], newcentroid[0], newcentroid[1]);
 
267
 
 
268
    newutility[2]  = eval_error_cell(elbg, newcentroid[2], elbg->cells[idx[0]]);
 
269
    newutility[2] += eval_error_cell(elbg, newcentroid[2], elbg->cells[idx[2]]);
 
270
 
 
271
    newerror = newutility[2];
 
272
 
 
273
    newerror += simple_lbg(elbg->dim, newcentroid_ptrs, newutility, elbg->points,
 
274
                           elbg->cells[idx[1]]);
 
275
 
 
276
    if (olderror > newerror) {
 
277
        shift_codebook(elbg, idx, newcentroid_ptrs);
 
278
 
 
279
        elbg->error += newerror - olderror;
 
280
 
 
281
        for (j=0; j<3; j++)
 
282
            update_utility_and_n_cb(elbg, idx[j], newutility[j]);
 
283
 
 
284
        evaluate_utility_inc(elbg);
 
285
    }
 
286
 }
 
287
 
 
288
/**
 
289
 * Implementation of the ELBG block
 
290
 */
 
291
static void do_shiftings(elbg_data *elbg)
 
292
{
 
293
    int idx[3];
 
294
 
 
295
    evaluate_utility_inc(elbg);
 
296
 
 
297
    for (idx[0]=0; idx[0] < elbg->numCB; idx[0]++)
 
298
        if (elbg->numCB*elbg->utility[idx[0]] < elbg->error) {
 
299
            if (elbg->utility_inc[elbg->numCB-1] == 0)
 
300
                return;
 
301
 
 
302
            idx[1] = get_high_utility_cell(elbg);
 
303
            idx[2] = get_closest_codebook(elbg, idx[0]);
 
304
 
 
305
            try_shift_candidate(elbg, idx);
 
306
        }
 
307
}
 
308
 
 
309
#define BIG_PRIME 433494437LL
 
310
 
 
311
void ff_init_elbg(int *points, int dim, int numpoints, int *codebook,
 
312
                  int numCB, int max_steps, int *closest_cb,
 
313
                  AVRandomState *rand_state)
 
314
{
 
315
    int i, k;
 
316
 
 
317
    if (numpoints > 24*numCB) {
 
318
        /* ELBG is very costly for a big number of points. So if we have a lot
 
319
           of them, get a good initial codebook to save on iterations       */
 
320
        int *temp_points = av_malloc(dim*(numpoints/8)*sizeof(int));
 
321
        for (i=0; i<numpoints/8; i++) {
 
322
            k = (i*BIG_PRIME) % numpoints;
 
323
            memcpy(temp_points + i*dim, points + k*dim, dim*sizeof(int));
 
324
        }
 
325
 
 
326
        ff_init_elbg(temp_points, dim, numpoints/8, codebook, numCB, 2*max_steps, closest_cb, rand_state);
 
327
        ff_do_elbg(temp_points, dim, numpoints/8, codebook, numCB, 2*max_steps, closest_cb, rand_state);
 
328
 
 
329
        av_free(temp_points);
 
330
 
 
331
    } else  // If not, initialize the codebook with random positions
 
332
        for (i=0; i < numCB; i++)
 
333
            memcpy(codebook + i*dim, points + ((i*BIG_PRIME)%numpoints)*dim,
 
334
                   dim*sizeof(int));
 
335
 
 
336
}
 
337
 
 
338
void ff_do_elbg(int *points, int dim, int numpoints, int *codebook,
 
339
                int numCB, int max_steps, int *closest_cb,
 
340
                AVRandomState *rand_state)
 
341
{
 
342
    int dist;
 
343
    elbg_data elbg_d;
 
344
    elbg_data *elbg = &elbg_d;
 
345
    int i, j, k, last_error, steps=0;
 
346
    int *dist_cb = av_malloc(numpoints*sizeof(int));
 
347
    int *size_part = av_malloc(numCB*sizeof(int));
 
348
    cell *list_buffer = av_malloc(numpoints*sizeof(cell));
 
349
    cell *free_cells;
 
350
 
 
351
    elbg->error = INT_MAX;
 
352
    elbg->dim = dim;
 
353
    elbg->numCB = numCB;
 
354
    elbg->codebook = codebook;
 
355
    elbg->cells = av_malloc(numCB*sizeof(cell *));
 
356
    elbg->utility = av_malloc(numCB*sizeof(int));
 
357
    elbg->nearest_cb = closest_cb;
 
358
    elbg->points = points;
 
359
    elbg->utility_inc = av_malloc(numCB*sizeof(int));
 
360
 
 
361
    elbg->rand_state = rand_state;
 
362
 
 
363
    do {
 
364
        free_cells = list_buffer;
 
365
        last_error = elbg->error;
 
366
        steps++;
 
367
        memset(elbg->utility, 0, numCB*sizeof(int));
 
368
        memset(elbg->cells, 0, numCB*sizeof(cell *));
 
369
 
 
370
        elbg->error = 0;
 
371
 
 
372
        /* This loop evaluate the actual Voronoi partition. It is the most
 
373
           costly part of the algorithm. */
 
374
        for (i=0; i < numpoints; i++) {
 
375
            dist_cb[i] = INT_MAX;
 
376
            for (k=0; k < elbg->numCB; k++) {
 
377
                dist = distance_limited(elbg->points + i*elbg->dim, elbg->codebook + k*elbg->dim, dim, dist_cb[i]);
 
378
                if (dist < dist_cb[i]) {
 
379
                    dist_cb[i] = dist;
 
380
                    elbg->nearest_cb[i] = k;
 
381
                }
 
382
            }
 
383
            elbg->error += dist_cb[i];
 
384
            elbg->utility[elbg->nearest_cb[i]] += dist_cb[i];
 
385
            free_cells->index = i;
 
386
            free_cells->next = elbg->cells[elbg->nearest_cb[i]];
 
387
            elbg->cells[elbg->nearest_cb[i]] = free_cells;
 
388
            free_cells++;
 
389
        }
 
390
 
 
391
        do_shiftings(elbg);
 
392
 
 
393
        memset(size_part, 0, numCB*sizeof(int));
 
394
 
 
395
        memset(elbg->codebook, 0, elbg->numCB*dim*sizeof(int));
 
396
 
 
397
        for (i=0; i < numpoints; i++) {
 
398
            size_part[elbg->nearest_cb[i]]++;
 
399
            for (j=0; j < elbg->dim; j++)
 
400
                elbg->codebook[elbg->nearest_cb[i]*elbg->dim + j] +=
 
401
                    elbg->points[i*elbg->dim + j];
 
402
        }
 
403
 
 
404
        for (i=0; i < elbg->numCB; i++)
 
405
            vect_division(elbg->codebook + i*elbg->dim,
 
406
                          elbg->codebook + i*elbg->dim, size_part[i], elbg->dim);
 
407
 
 
408
    } while(((last_error - elbg->error) > DELTA_ERR_MAX*elbg->error) &&
 
409
            (steps < max_steps));
 
410
 
 
411
    av_free(dist_cb);
 
412
    av_free(size_part);
 
413
    av_free(elbg->utility);
 
414
    av_free(list_buffer);
 
415
    av_free(elbg->cells);
 
416
    av_free(elbg->utility_inc);
 
417
}