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