28 #include "libavutil/avassert.h"
29 #include "libavutil/common.h"
30 #include "libavutil/lfg.h"
34 #define DELTA_ERR_MAX 0.1
39 typedef struct cell_s {
64 for (i=0; i<
dim; i++) {
65 dist += (a[i] - b[i])*(a[i] - b[i]);
80 memcpy(res, vect, dim*
sizeof(
int));
87 for (; cells; cells=cells->
next)
95 int i, pick=0, diff, diff_min = INT_MAX;
96 for (i=0; i<elbg->
numCB; i++)
99 if (diff < diff_min) {
131 int numpoints[2] = {0,0};
132 int *newcentroid[2] = {
138 memset(newcentroid[0], 0, 2 * dim *
sizeof(*newcentroid[0]));
143 for (tempcell = cells; tempcell; tempcell=tempcell->
next) {
147 for (i=0; i<
dim; i++)
148 newcentroid[idx][i] += points[tempcell->
index*dim + i];
151 vect_division(centroid[0], newcentroid[0], numpoints[0], dim);
152 vect_division(centroid[1], newcentroid[1], numpoints[1], dim);
154 for (tempcell = cells; tempcell; tempcell=tempcell->
next) {
157 int idx = dist[0] > dist[1];
158 newutility[idx] += dist[idx];
161 return newutility[0] + newutility[1];
168 int *
min = newcentroid_i;
169 int *max = newcentroid_p;
172 for (i=0; i< elbg->
dim; i++) {
177 for (tempcell = elbg->
cells[huc]; tempcell; tempcell = tempcell->
next)
178 for(i=0; i<elbg->
dim; i++) {
183 for (i=0; i<elbg->
dim; i++) {
184 int ni = min[i] + (max[i] - min[i])/3;
185 int np = min[i] + (2*(max[i] - min[i]))/3;
186 newcentroid_i[i] = ni;
187 newcentroid_p[i] = np;
209 *pp = elbg->
cells[indexes[0]];
211 elbg->
cells[indexes[0]] = NULL;
212 tempdata = elbg->
cells[indexes[1]];
213 elbg->
cells[indexes[1]] = NULL;
218 newcentroid[0], elbg->
dim, INT_MAX) >
220 newcentroid[1], elbg->
dim, INT_MAX);
222 tempdata->
next = elbg->
cells[indexes[idx]];
223 elbg->
cells[indexes[idx]] = tempdata;
224 tempdata = tempcell2;
232 for (i=0; i < elbg->
numCB; i++) {
244 elbg->
utility[idx] = newutility;
245 for (tempcell=elbg->
cells[idx]; tempcell; tempcell=tempcell->
next)
258 int j, k, olderror=0, newerror, cont=0;
260 int *newcentroid[3] = {
268 olderror += elbg->
utility[idx[j]];
270 memset(newcentroid[2], 0, elbg->
dim*
sizeof(
int));
273 for (tempcell=elbg->
cells[idx[2*k]]; tempcell; tempcell=tempcell->
next) {
275 for (j=0; j<elbg->
dim; j++)
286 newerror = newutility[2];
289 elbg->
cells[idx[1]]);
291 if (olderror > newerror) {
294 elbg->
error += newerror - olderror;
312 for (idx[0]=0; idx[0] < elbg->
numCB; idx[0]++)
320 if (idx[1] != idx[0] && idx[1] != idx[2])
325 #define BIG_PRIME 433494437LL
328 int numCB,
int max_steps,
int *closest_cb,
333 if (numpoints > 24*numCB) {
336 int *temp_points =
av_malloc(dim*(numpoints/8)*
sizeof(
int));
337 for (i=0; i<numpoints/8; i++) {
339 memcpy(temp_points + i*dim, points + k*dim, dim*
sizeof(
int));
342 ff_init_elbg(temp_points, dim, numpoints/8, codebook, numCB, 2*max_steps, closest_cb, rand_state);
343 ff_do_elbg(temp_points, dim, numpoints/8, codebook, numCB, 2*max_steps, closest_cb, rand_state);
348 for (i=0; i < numCB; i++)
349 memcpy(codebook + i*dim, points + ((i*
BIG_PRIME)%numpoints)*dim,
355 int numCB,
int max_steps,
int *closest_cb,
361 int i, j, k, last_error, steps=0;
362 int *dist_cb =
av_malloc(numpoints*
sizeof(
int));
363 int *size_part =
av_malloc(numCB*
sizeof(
int));
366 int best_dist, best_idx = 0;
368 elbg->
error = INT_MAX;
382 free_cells = list_buffer;
383 last_error = elbg->
error;
385 memset(elbg->
utility, 0, numCB*
sizeof(
int));
386 memset(elbg->
cells, 0, numCB*
sizeof(
cell *));
392 for (i=0; i < numpoints; i++) {
394 for (k=0; k < elbg->
numCB; k++) {
396 if (dist < best_dist) {
402 dist_cb[i] = best_dist;
403 elbg->
error += dist_cb[i];
405 free_cells->
index = i;
413 memset(size_part, 0, numCB*
sizeof(
int));
417 for (i=0; i < numpoints; i++) {
419 for (j=0; j < elbg->
dim; j++)
424 for (i=0; i < elbg->
numCB; i++)
429 (steps < max_steps));
static void do_shiftings(elbg_data *elbg)
Implementation of the ELBG block.
static int simple_lbg(elbg_data *elbg, int dim, int *centroid[3], int newutility[3], int *points, cell *cells)
Implementation of the simple LBG algorithm for just two codebooks.
static int distance_limited(int *a, int *b, int dim, int limit)
static void get_new_centroids(elbg_data *elbg, int huc, int *newcentroid_i, int *newcentroid_p)
static void evaluate_utility_inc(elbg_data *elbg)
static unsigned int av_lfg_get(AVLFG *c)
Get the next random unsigned 32-bit number using an ALFG.
void av_free(void *ptr)
Free a memory block which has been allocated with av_malloc(z)() or av_realloc(). ...
static void vect_division(int *res, int *vect, int div, int dim)
Libavcodec external API header.
void ff_do_elbg(int *points, int dim, int numpoints, int *codebook, int numCB, int max_steps, int *closest_cb, AVLFG *rand_state)
Implementation of the Enhanced LBG Algorithm Based on the paper "Neural Networks 14:1219-1237" that c...
In the ELBG jargon, a cell is the set of points that are closest to a codebook entry.
static int get_high_utility_cell(elbg_data *elbg)
void * av_malloc(size_t size) av_malloc_attrib 1(1)
Allocate a block of size bytes with alignment suitable for all memory accesses (including vectors if ...
static int get_closest_codebook(elbg_data *elbg, int index)
static void update_utility_and_n_cb(elbg_data *elbg, int idx, int newutility)
void ff_init_elbg(int *points, int dim, int numpoints, int *codebook, int numCB, int max_steps, int *closest_cb, AVLFG *rand_state)
Initialize the **codebook vector for the elbg algorithm.
#define ROUNDED_DIV(a, b)
static void shift_codebook(elbg_data *elbg, int *indexes, int *newcentroid[3])
Add the points in the low utility cell to its closest cell.
static int eval_error_cell(elbg_data *elbg, int *centroid, cell *cells)
#define DELTA_ERR_MAX
Precision of the ELBG algorithm (as percentual error)
static void try_shift_candidate(elbg_data *elbg, int idx[3])
Evaluate if a shift lower the error.
#define av_assert2(cond)
assert() equivalent, that does lie in speed critical code.