GCC Code Coverage Report
Directory: ../../../ffmpeg/ Exec Total Coverage
File: src/libavcodec/elbg.c Lines: 218 226 96.5 %
Date: 2019-11-22 03:34:36 Branches: 97 110 88.2 %

Line Branch Exec Source
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
23
 * Codebook Generator using the ELBG algorithm
24
 */
25
26
#include <string.h>
27
28
#include "libavutil/avassert.h"
29
#include "libavutil/common.h"
30
#include "libavutil/lfg.h"
31
#include "elbg.h"
32
#include "avcodec.h"
33
34
#define DELTA_ERR_MAX 0.1  ///< Precision of the ELBG algorithm (as percentage error)
35
36
/**
37
 * In the ELBG jargon, a cell is the set of points that are closest to a
38
 * codebook entry. Not to be confused with a RoQ Video cell. */
39
typedef struct cell_s {
40
    int index;
41
    struct cell_s *next;
42
} cell;
43
44
/**
45
 * ELBG internal data
46
 */
47
typedef struct elbg_data {
48
    int error;
49
    int dim;
50
    int numCB;
51
    int *codebook;
52
    cell **cells;
53
    int *utility;
54
    int64_t *utility_inc;
55
    int *nearest_cb;
56
    int *points;
57
    AVLFG *rand_state;
58
    int *scratchbuf;
59
} elbg_data;
60
61
2512940434
static inline int distance_limited(int *a, int *b, int dim, int limit)
62
{
63
2512940434
    int i, dist=0;
64
5371859070
    for (i=0; i<dim; i++) {
65
5028816911
        dist += (a[i] - b[i])*(a[i] - b[i]);
66
5028816911
        if (dist > limit)
67
2169898275
            return INT_MAX;
68
    }
69
70
343042159
    return dist;
71
}
72
73
17887608
static inline void vect_division(int *res, int *vect, int div, int dim)
74
{
75
    int i;
76
17887608
    if (div > 1)
77
69873730
        for (i=0; i<dim; i++)
78
56803470
            res[i] = ROUNDED_DIV(vect[i],div);
79
4817348
    else if (res != vect)
80
749779
        memcpy(res, vect, dim*sizeof(int));
81
82
17887608
}
83
84
2955954
static int eval_error_cell(elbg_data *elbg, int *centroid, cell *cells)
85
{
86
2955954
    int error=0;
87
28530259
    for (; cells; cells=cells->next)
88
25574305
        error += distance_limited(centroid, elbg->points + cells->index*elbg->dim, elbg->dim, INT_MAX);
89
90
2955954
    return error;
91
}
92
93
5909519
static int get_closest_codebook(elbg_data *elbg, int index)
94
{
95
5909519
    int i, pick=0, diff, diff_min = INT_MAX;
96
238648065
    for (i=0; i<elbg->numCB; i++)
97
232738546
        if (i != index) {
98
226829027
            diff = distance_limited(elbg->codebook + i*elbg->dim, elbg->codebook + index*elbg->dim, elbg->dim, diff_min);
99
226829027
            if (diff < diff_min) {
100
12118877
                pick = i;
101
12118877
                diff_min = diff;
102
            }
103
        }
104
5909519
    return pick;
105
}
106
107
5909519
static int get_high_utility_cell(elbg_data *elbg)
108
{
109
5909519
    int i=0;
110
    /* Using linear search, do binary if it ever turns to be speed critical */
111
    uint64_t r;
112
113
5909519
    if (elbg->utility_inc[elbg->numCB-1] < INT_MAX) {
114
5909519
        r = av_lfg_get(elbg->rand_state) % (unsigned int)elbg->utility_inc[elbg->numCB-1] + 1;
115
    } else {
116
        r = av_lfg_get(elbg->rand_state);
117
        r = (av_lfg_get(elbg->rand_state) + (r<<32)) % elbg->utility_inc[elbg->numCB-1] + 1;
118
    }
119
120
117999996
    while (elbg->utility_inc[i] < r) {
121
112090477
        i++;
122
    }
123
124
    av_assert2(elbg->cells[i]);
125
126
5909519
    return i;
127
}
128
129
/**
130
 * Implementation of the simple LBG algorithm for just two codebooks
131
 */
132
1477977
static int simple_lbg(elbg_data *elbg,
133
                      int dim,
134
                      int *centroid[3],
135
                      int newutility[3],
136
                      int *points,
137
                      cell *cells)
138
{
139
    int i, idx;
140
1477977
    int numpoints[2] = {0,0};
141
1477977
    int *newcentroid[2] = {
142
1477977
        elbg->scratchbuf + 3*dim,
143
1477977
        elbg->scratchbuf + 4*dim
144
    };
145
    cell *tempcell;
146
147
1477977
    memset(newcentroid[0], 0, 2 * dim * sizeof(*newcentroid[0]));
148
149
1477977
    newutility[0] =
150
1477977
    newutility[1] = 0;
151
152
21666058
    for (tempcell = cells; tempcell; tempcell=tempcell->next) {
153
20188081
        idx = distance_limited(centroid[0], points + tempcell->index*dim, dim, INT_MAX)>=
154
20188081
              distance_limited(centroid[1], points + tempcell->index*dim, dim, INT_MAX);
155
20188081
        numpoints[idx]++;
156
144432511
        for (i=0; i<dim; i++)
157
124244430
            newcentroid[idx][i] += points[tempcell->index*dim + i];
158
    }
159
160
1477977
    vect_division(centroid[0], newcentroid[0], numpoints[0], dim);
161
1477977
    vect_division(centroid[1], newcentroid[1], numpoints[1], dim);
162
163
21666058
    for (tempcell = cells; tempcell; tempcell=tempcell->next) {
164
20188081
        int dist[2] = {distance_limited(centroid[0], points + tempcell->index*dim, dim, INT_MAX),
165
20188081
                       distance_limited(centroid[1], points + tempcell->index*dim, dim, INT_MAX)};
166
20188081
        int idx = dist[0] > dist[1];
167
20188081
        newutility[idx] += dist[idx];
168
    }
169
170
1477977
    return newutility[0] + newutility[1];
171
}
172
173
1477977
static void get_new_centroids(elbg_data *elbg, int huc, int *newcentroid_i,
174
                              int *newcentroid_p)
175
{
176
    cell *tempcell;
177
1477977
    int *min = newcentroid_i;
178
1477977
    int *max = newcentroid_p;
179
    int i;
180
181
10535721
    for (i=0; i< elbg->dim; i++) {
182
9057744
        min[i]=INT_MAX;
183
9057744
        max[i]=0;
184
    }
185
186
21666058
    for (tempcell = elbg->cells[huc]; tempcell; tempcell = tempcell->next)
187
144432511
        for(i=0; i<elbg->dim; i++) {
188
124244430
            min[i]=FFMIN(min[i], elbg->points[tempcell->index*elbg->dim + i]);
189
124244430
            max[i]=FFMAX(max[i], elbg->points[tempcell->index*elbg->dim + i]);
190
        }
191
192
10535721
    for (i=0; i<elbg->dim; i++) {
193
9057744
        int ni = min[i] + (max[i] - min[i])/3;
194
9057744
        int np = min[i] + (2*(max[i] - min[i]))/3;
195
9057744
        newcentroid_i[i] = ni;
196
9057744
        newcentroid_p[i] = np;
197
    }
198
1477977
}
199
200
/**
201
 * Add the points in the low utility cell to its closest cell. Split the high
202
 * utility cell, putting the separated points in the (now empty) low utility
203
 * cell.
204
 *
205
 * @param elbg         Internal elbg data
206
 * @param indexes      {luc, huc, cluc}
207
 * @param newcentroid  A vector with the position of the new centroids
208
 */
209
759468
static void shift_codebook(elbg_data *elbg, int *indexes,
210
                           int *newcentroid[3])
211
{
212
    cell *tempdata;
213
759468
    cell **pp = &elbg->cells[indexes[2]];
214
215
6803461
    while(*pp)
216
6043993
        pp= &(*pp)->next;
217
218
759468
    *pp = elbg->cells[indexes[0]];
219
220
759468
    elbg->cells[indexes[0]] = NULL;
221
759468
    tempdata = elbg->cells[indexes[1]];
222
759468
    elbg->cells[indexes[1]] = NULL;
223
224
9363792
    while(tempdata) {
225
8604324
        cell *tempcell2 = tempdata->next;
226
8604324
        int idx = distance_limited(elbg->points + tempdata->index*elbg->dim,
227
8604324
                           newcentroid[0], elbg->dim, INT_MAX) >
228
8604324
                  distance_limited(elbg->points + tempdata->index*elbg->dim,
229
8604324
                           newcentroid[1], elbg->dim, INT_MAX);
230
231
8604324
        tempdata->next = elbg->cells[indexes[idx]];
232
8604324
        elbg->cells[indexes[idx]] = tempdata;
233
8604324
        tempdata = tempcell2;
234
    }
235
759468
}
236
237
6589862
static void evaluate_utility_inc(elbg_data *elbg)
238
{
239
    int i;
240
6589862
    int64_t inc=0;
241
242
138541051
    for (i=0; i < elbg->numCB; i++) {
243
131951189
        if (elbg->numCB*elbg->utility[i] > elbg->error)
244
45667224
            inc += elbg->utility[i];
245
131951189
        elbg->utility_inc[i] = inc;
246
    }
247
6589862
}
248
249
250
2278404
static void update_utility_and_n_cb(elbg_data *elbg, int idx, int newutility)
251
{
252
    cell *tempcell;
253
254
2278404
    elbg->utility[idx] = newutility;
255
21120685
    for (tempcell=elbg->cells[idx]; tempcell; tempcell=tempcell->next)
256
18842281
        elbg->nearest_cb[tempcell->index] = idx;
257
2278404
}
258
259
/**
260
 * Evaluate if a shift lower the error. If it does, call shift_codebooks
261
 * and update elbg->error, elbg->utility and elbg->nearest_cb.
262
 *
263
 * @param elbg  Internal elbg data
264
 * @param idx   {luc (low utility cell, huc (high utility cell), cluc (closest cell to low utility cell)}
265
 */
266
1477977
static void try_shift_candidate(elbg_data *elbg, int idx[3])
267
{
268
1477977
    int j, k, olderror=0, newerror, cont=0;
269
    int newutility[3];
270
1477977
    int *newcentroid[3] = {
271
1477977
        elbg->scratchbuf,
272
1477977
        elbg->scratchbuf + elbg->dim,
273
1477977
        elbg->scratchbuf + 2*elbg->dim
274
    };
275
    cell *tempcell;
276
277
5911908
    for (j=0; j<3; j++)
278
4433931
        olderror += elbg->utility[idx[j]];
279
280
1477977
    memset(newcentroid[2], 0, elbg->dim*sizeof(int));
281
282
4433931
    for (k=0; k<2; k++)
283
28530259
        for (tempcell=elbg->cells[idx[2*k]]; tempcell; tempcell=tempcell->next) {
284
25574305
            cont++;
285
186440797
            for (j=0; j<elbg->dim; j++)
286
160866492
                newcentroid[2][j] += elbg->points[tempcell->index*elbg->dim + j];
287
        }
288
289
1477977
    vect_division(newcentroid[2], newcentroid[2], cont, elbg->dim);
290
291
1477977
    get_new_centroids(elbg, idx[1], newcentroid[0], newcentroid[1]);
292
293
1477977
    newutility[2]  = eval_error_cell(elbg, newcentroid[2], elbg->cells[idx[0]]);
294
1477977
    newutility[2] += eval_error_cell(elbg, newcentroid[2], elbg->cells[idx[2]]);
295
296
1477977
    newerror = newutility[2];
297
298
2955954
    newerror += simple_lbg(elbg, elbg->dim, newcentroid, newutility, elbg->points,
299
1477977
                           elbg->cells[idx[1]]);
300
301
1477977
    if (olderror > newerror) {
302
759468
        shift_codebook(elbg, idx, newcentroid);
303
304
759468
        elbg->error += newerror - olderror;
305
306
3037872
        for (j=0; j<3; j++)
307
2278404
            update_utility_and_n_cb(elbg, idx[j], newutility[j]);
308
309
759468
        evaluate_utility_inc(elbg);
310
    }
311
1477977
 }
312
313
/**
314
 * Implementation of the ELBG block
315
 */
316
5830394
static void do_shiftings(elbg_data *elbg)
317
{
318
    int idx[3];
319
320
5830394
    evaluate_utility_inc(elbg);
321
322
19284071
    for (idx[0]=0; idx[0] < elbg->numCB; idx[0]++)
323
13453677
        if (elbg->numCB*elbg->utility[idx[0]] < elbg->error) {
324
5909519
            if (elbg->utility_inc[elbg->numCB-1] == 0)
325
                return;
326
327
5909519
            idx[1] = get_high_utility_cell(elbg);
328
5909519
            idx[2] = get_closest_codebook(elbg, idx[0]);
329
330

5909519
            if (idx[1] != idx[0] && idx[1] != idx[2])
331
1477977
                try_shift_candidate(elbg, idx);
332
        }
333
}
334
335
#define BIG_PRIME 433494437LL
336
337
5792078
int avpriv_init_elbg(int *points, int dim, int numpoints, int *codebook,
338
                 int numCB, int max_steps, int *closest_cb,
339
                 AVLFG *rand_state)
340
{
341
5792078
    int i, k, ret = 0;
342
343
5792078
    if (numpoints > 24*numCB) {
344
        /* ELBG is very costly for a big number of points. So if we have a lot
345
           of them, get a good initial codebook to save on iterations       */
346
31211
        int *temp_points = av_malloc_array(dim, (numpoints/8)*sizeof(int));
347
31211
        if (!temp_points)
348
            return AVERROR(ENOMEM);
349
1989867
        for (i=0; i<numpoints/8; i++) {
350
1958656
            k = (i*BIG_PRIME) % numpoints;
351
1958656
            memcpy(temp_points + i*dim, points + k*dim, dim*sizeof(int));
352
        }
353
354
31211
        ret = avpriv_init_elbg(temp_points, dim, numpoints / 8, codebook,
355
                               numCB, 2 * max_steps, closest_cb, rand_state);
356
31211
        if (ret < 0) {
357
            av_freep(&temp_points);
358
            return ret;
359
        }
360
31211
        ret = avpriv_do_elbg(temp_points, dim, numpoints / 8, codebook,
361
                             numCB, 2 * max_steps, closest_cb, rand_state);
362
31211
        av_free(temp_points);
363
364
    } else  // If not, initialize the codebook with random positions
365
18857953
        for (i=0; i < numCB; i++)
366
13097086
            memcpy(codebook + i*dim, points + ((i*BIG_PRIME)%numpoints)*dim,
367
                   dim*sizeof(int));
368
5792078
    return ret;
369
}
370
371
5792078
int avpriv_do_elbg(int *points, int dim, int numpoints, int *codebook,
372
                int numCB, int max_steps, int *closest_cb,
373
                AVLFG *rand_state)
374
{
375
    int dist;
376
    elbg_data elbg_d;
377
5792078
    elbg_data *elbg = &elbg_d;
378
5792078
    int i, j, k, last_error, steps = 0, ret = 0;
379
5792078
    int *dist_cb = av_malloc_array(numpoints, sizeof(int));
380
5792078
    int *size_part = av_malloc_array(numCB, sizeof(int));
381
5792078
    cell *list_buffer = av_malloc_array(numpoints, sizeof(cell));
382
    cell *free_cells;
383
5792078
    int best_dist, best_idx = 0;
384
385
5792078
    elbg->error = INT_MAX;
386
5792078
    elbg->dim = dim;
387
5792078
    elbg->numCB = numCB;
388
5792078
    elbg->codebook = codebook;
389
5792078
    elbg->cells = av_malloc_array(numCB, sizeof(cell *));
390
5792078
    elbg->utility = av_malloc_array(numCB, sizeof(int));
391
5792078
    elbg->nearest_cb = closest_cb;
392
5792078
    elbg->points = points;
393
5792078
    elbg->utility_inc = av_malloc_array(numCB, sizeof(*elbg->utility_inc));
394
5792078
    elbg->scratchbuf = av_malloc_array(5*dim, sizeof(int));
395
396


5792078
    if (!dist_cb || !size_part || !list_buffer || !elbg->cells ||
397

5792078
        !elbg->utility || !elbg->utility_inc || !elbg->scratchbuf) {
398
        ret = AVERROR(ENOMEM);
399
        goto out;
400
    }
401
402
5792078
    elbg->rand_state = rand_state;
403
404
    do {
405
5830394
        free_cells = list_buffer;
406
5830394
        last_error = elbg->error;
407
5830394
        steps++;
408
5830394
        memset(elbg->utility, 0, numCB*sizeof(int));
409
5830394
        memset(elbg->cells, 0, numCB*sizeof(cell *));
410
411
5830394
        elbg->error = 0;
412
413
        /* This loop evaluate the actual Voronoi partition. It is the most
414
           costly part of the algorithm. */
415
83063239
        for (i=0; i < numpoints; i++) {
416
77232845
            best_dist = distance_limited(elbg->points + i*elbg->dim, elbg->codebook + best_idx*elbg->dim, dim, INT_MAX);
417
2162576130
            for (k=0; k < elbg->numCB; k++) {
418
2085343285
                dist = distance_limited(elbg->points + i*elbg->dim, elbg->codebook + k*elbg->dim, dim, best_dist);
419
2085343285
                if (dist < best_dist) {
420
66209922
                    best_dist = dist;
421
66209922
                    best_idx = k;
422
                }
423
            }
424
77232845
            elbg->nearest_cb[i] = best_idx;
425
77232845
            dist_cb[i] = best_dist;
426
77232845
            elbg->error += dist_cb[i];
427
77232845
            elbg->utility[elbg->nearest_cb[i]] += dist_cb[i];
428
77232845
            free_cells->index = i;
429
77232845
            free_cells->next = elbg->cells[elbg->nearest_cb[i]];
430
77232845
            elbg->cells[elbg->nearest_cb[i]] = free_cells;
431
77232845
            free_cells++;
432
        }
433
434
5830394
        do_shiftings(elbg);
435
436
5830394
        memset(size_part, 0, numCB*sizeof(int));
437
438
5830394
        memset(elbg->codebook, 0, elbg->numCB*dim*sizeof(int));
439
440
83063239
        for (i=0; i < numpoints; i++) {
441
77232845
            size_part[elbg->nearest_cb[i]]++;
442
408122555
            for (j=0; j < elbg->dim; j++)
443
330889710
                elbg->codebook[elbg->nearest_cb[i]*elbg->dim + j] +=
444
330889710
                    elbg->points[i*elbg->dim + j];
445
        }
446
447
19284071
        for (i=0; i < elbg->numCB; i++)
448
13453677
            vect_division(elbg->codebook + i*elbg->dim,
449
13453677
                          elbg->codebook + i*elbg->dim, size_part[i], elbg->dim);
450
451
5817605
    } while(((last_error - elbg->error) > DELTA_ERR_MAX*elbg->error) &&
452
5830394
            (steps < max_steps));
453
454
5792078
out:
455
5792078
    av_free(dist_cb);
456
5792078
    av_free(size_part);
457
5792078
    av_free(elbg->utility);
458
5792078
    av_free(list_buffer);
459
5792078
    av_free(elbg->cells);
460
5792078
    av_free(elbg->utility_inc);
461
5792078
    av_free(elbg->scratchbuf);
462
5792078
    return ret;
463
}