28 #include "libavutil/common.h"
29 #include "libavutil/lfg.h"
33 #define DELTA_ERR_MAX 0.1
38 typedef struct cell_s {
63 for (i=0; i<
dim; i++) {
64 dist += (a[i] - b[i])*(a[i] - b[i]);
79 memcpy(res, vect, dim*
sizeof(
int));
86 for (; cells; cells=cells->
next)
94 int i, pick=0, diff, diff_min = INT_MAX;
95 for (i=0; i<elbg->
numCB; i++)
98 if (diff < diff_min) {
114 assert(elbg->
cells[i]);
130 int numpoints[2] = {0,0};
131 int *newcentroid[2] = {
137 memset(newcentroid[0], 0, 2 * dim *
sizeof(*newcentroid[0]));
142 for (tempcell = cells; tempcell; tempcell=tempcell->
next) {
146 for (i=0; i<
dim; i++)
147 newcentroid[idx][i] += points[tempcell->
index*dim + i];
150 vect_division(centroid[0], newcentroid[0], numpoints[0], dim);
151 vect_division(centroid[1], newcentroid[1], numpoints[1], dim);
153 for (tempcell = cells; tempcell; tempcell=tempcell->
next) {
156 int idx = dist[0] > dist[1];
157 newutility[idx] += dist[idx];
160 return newutility[0] + newutility[1];
167 int *
min = newcentroid_i;
168 int *max = newcentroid_p;
171 for (i=0; i< elbg->
dim; i++) {
176 for (tempcell = elbg->
cells[huc]; tempcell; tempcell = tempcell->
next)
177 for(i=0; i<elbg->
dim; i++) {
182 for (i=0; i<elbg->
dim; i++) {
183 int ni = min[i] + (max[i] - min[i])/3;
184 int np = min[i] + (2*(max[i] - min[i]))/3;
185 newcentroid_i[i] = ni;
186 newcentroid_p[i] = np;
208 *pp = elbg->
cells[indexes[0]];
211 tempdata = elbg->
cells[indexes[1]];
217 newcentroid[0], elbg->
dim, INT_MAX) >
219 newcentroid[1], elbg->
dim, INT_MAX);
221 tempdata->
next = elbg->
cells[indexes[idx]];
222 elbg->
cells[indexes[idx]] = tempdata;
223 tempdata = tempcell2;
231 for (i=0; i < elbg->
numCB; i++) {
243 elbg->
utility[idx] = newutility;
244 for (tempcell=elbg->
cells[idx]; tempcell; tempcell=tempcell->
next)
257 int j, k, olderror=0, newerror, cont=0;
259 int *newcentroid[3] = {
267 olderror += elbg->
utility[idx[j]];
269 memset(newcentroid[2], 0, elbg->
dim*
sizeof(
int));
272 for (tempcell=elbg->
cells[idx[2*k]]; tempcell; tempcell=tempcell->
next) {
274 for (j=0; j<elbg->
dim; j++)
285 newerror = newutility[2];
288 elbg->
cells[idx[1]]);
290 if (olderror > newerror) {
293 elbg->
error += newerror - olderror;
311 for (idx[0]=0; idx[0] < elbg->
numCB; idx[0]++)
319 if (idx[1] != idx[0] && idx[1] != idx[2])
324 #define BIG_PRIME 433494437LL
327 int numCB,
int max_steps,
int *closest_cb,
332 if (numpoints > 24*numCB) {
335 int *temp_points =
av_malloc(dim*(numpoints/8)*
sizeof(
int));
336 for (i=0; i<numpoints/8; i++) {
338 memcpy(temp_points + i*dim, points + k*dim, dim*
sizeof(
int));
341 ff_init_elbg(temp_points, dim, numpoints/8, codebook, numCB, 2*max_steps, closest_cb, rand_state);
342 ff_do_elbg(temp_points, dim, numpoints/8, codebook, numCB, 2*max_steps, closest_cb, rand_state);
347 for (i=0; i < numCB; i++)
348 memcpy(codebook + i*dim, points + ((i*
BIG_PRIME)%numpoints)*dim,
354 int numCB,
int max_steps,
int *closest_cb,
360 int i, j, k, last_error, steps=0;
361 int *dist_cb =
av_malloc(numpoints*
sizeof(
int));
362 int *size_part =
av_malloc(numCB*
sizeof(
int));
365 int best_dist, best_idx = 0;
367 elbg->
error = INT_MAX;
381 free_cells = list_buffer;
382 last_error = elbg->
error;
384 memset(elbg->
utility, 0, numCB*
sizeof(
int));
385 memset(elbg->
cells, 0, numCB*
sizeof(
cell *));
391 for (i=0; i < numpoints; i++) {
393 for (k=0; k < elbg->
numCB; k++) {
395 if (dist < best_dist) {
401 dist_cb[i] = best_dist;
402 elbg->
error += dist_cb[i];
404 free_cells->
index = i;
412 memset(size_part, 0, numCB*
sizeof(
int));
416 for (i=0; i < numpoints; i++) {
418 for (j=0; j < elbg->
dim; j++)
423 for (i=0; i < elbg->
numCB; i++)
428 (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.
#define ROUNDED_DIV(a, b)
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.
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.