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));