32 #define DELTA_ERR_MAX 0.1
62 for (i=0; i<
dim; i++) {
63 dist += (a[i] - b[i])*(a[i] - b[i]);
78 memcpy(res, vect, dim*
sizeof(
int));
85 for (; cells; cells=cells->
next)
93 int i, pick=0, diff, diff_min = INT_MAX;
94 for (i=0; i<elbg->
numCB; i++)
97 if (diff < diff_min) {
113 assert(elbg->
cells[i]);
129 int numpoints[2] = {0,0};
130 int *newcentroid[2] = {
136 memset(newcentroid[0], 0, 2 * dim *
sizeof(*newcentroid[0]));
141 for (tempcell = cells; tempcell; tempcell=tempcell->
next) {
145 for (i=0; i<
dim; i++)
146 newcentroid[idx][i] += points[tempcell->
index*dim + i];
149 vect_division(centroid[0], newcentroid[0], numpoints[0], dim);
150 vect_division(centroid[1], newcentroid[1], numpoints[1], dim);
152 for (tempcell = cells; tempcell; tempcell=tempcell->
next) {
155 int idx = dist[0] > dist[1];
156 newutility[idx] += dist[idx];
159 return newutility[0] + newutility[1];
166 int *
min = newcentroid_i;
167 int *max = newcentroid_p;
170 for (i=0; i< elbg->
dim; i++) {
175 for (tempcell = elbg->
cells[huc]; tempcell; tempcell = tempcell->
next)
176 for(i=0; i<elbg->
dim; i++) {
181 for (i=0; i<elbg->
dim; i++) {
182 int ni = min[i] + (max[i] - min[i])/3;
183 int np = min[i] + (2*(max[i] - min[i]))/3;
184 newcentroid_i[i] = ni;
185 newcentroid_p[i] = np;
207 *pp = elbg->
cells[indexes[0]];
210 tempdata = elbg->
cells[indexes[1]];
216 newcentroid[0], elbg->
dim, INT_MAX) >
218 newcentroid[1], elbg->
dim, INT_MAX);
220 tempdata->
next = elbg->
cells[indexes[idx]];
221 elbg->
cells[indexes[idx]] = tempdata;
222 tempdata = tempcell2;
230 for (i=0; i < elbg->
numCB; i++) {
242 elbg->
utility[idx] = newutility;
243 for (tempcell=elbg->
cells[idx]; tempcell; tempcell=tempcell->
next)
256 int j, k, olderror=0, newerror, cont=0;
258 int *newcentroid[3] = {
266 olderror += elbg->
utility[idx[j]];
268 memset(newcentroid[2], 0, elbg->
dim*
sizeof(
int));
271 for (tempcell=elbg->
cells[idx[2*k]]; tempcell; tempcell=tempcell->
next) {
273 for (j=0; j<elbg->
dim; j++)
284 newerror = newutility[2];
287 elbg->
cells[idx[1]]);
289 if (olderror > newerror) {
292 elbg->
error += newerror - olderror;
310 for (idx[0]=0; idx[0] < elbg->
numCB; idx[0]++)
318 if (idx[1] != idx[0] && idx[1] != idx[2])
323 #define BIG_PRIME 433494437LL
326 int numCB,
int max_steps,
int *closest_cb,
331 if (numpoints > 24*numCB) {
334 int *temp_points =
av_malloc(dim*(numpoints/8)*
sizeof(
int));
335 for (i=0; i<numpoints/8; i++) {
337 memcpy(temp_points + i*dim, points + k*dim, dim*
sizeof(
int));
340 ff_init_elbg(temp_points, dim, numpoints/8, codebook, numCB, 2*max_steps, closest_cb, rand_state);
341 ff_do_elbg(temp_points, dim, numpoints/8, codebook, numCB, 2*max_steps, closest_cb, rand_state);
346 for (i=0; i < numCB; i++)
347 memcpy(codebook + i*dim, points + ((i*
BIG_PRIME)%numpoints)*dim,
353 int numCB,
int max_steps,
int *closest_cb,
359 int i, j, k, last_error, steps=0;
360 int *dist_cb =
av_malloc(numpoints*
sizeof(
int));
361 int *size_part =
av_malloc(numCB*
sizeof(
int));
364 int best_dist, best_idx = 0;
366 elbg->
error = INT_MAX;
380 free_cells = list_buffer;
381 last_error = elbg->
error;
383 memset(elbg->
utility, 0, numCB*
sizeof(
int));
384 memset(elbg->
cells, 0, numCB*
sizeof(
cell *));
390 for (i=0; i < numpoints; i++) {
392 for (k=0; k < elbg->
numCB; k++) {
394 if (dist < best_dist) {
400 dist_cb[i] = best_dist;
401 elbg->
error += dist_cb[i];
403 free_cells->
index = i;
411 memset(size_part, 0, numCB*
sizeof(
int));
415 for (i=0; i < numpoints; i++) {
417 for (j=0; j < elbg->
dim; j++)
422 for (i=0; i < elbg->
numCB; i++)
427 (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)
struct cell_s cell
In the ELBG jargon, a cell is the set of points that are closest to a codebook entry.
static void evaluate_utility_inc(elbg_data *elbg)
#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)
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...
static int get_high_utility_cell(elbg_data *elbg)
static int get_closest_codebook(elbg_data *elbg, int index)
static void update_utility_and_n_cb(elbg_data *elbg, int idx, int newutility)
static unsigned int av_lfg_get(AVLFG *c)
Get the next random unsigned 32-bit number using an ALFG.
void * av_malloc(size_t size)
Allocate a block of size bytes with alignment suitable for all memory accesses (including vectors if ...
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)
In the ELBG jargon, a cell is the set of points that are closest to a codebook entry.
static void try_shift_candidate(elbg_data *elbg, int idx[3])
Evaluate if a shift lower the error.