Mercurial > libavcodec.hg
annotate elbg.c @ 7352:c2318e551ff5 libavcodec
When picking a "high utility centroid" do not pick one
that has no corresponding points. Not only it is the
worst possible pick, but also the code was written
without this case in mind.
author | vitor |
---|---|
date | Wed, 23 Jul 2008 03:55:37 +0000 |
parents | 1502ba3beb72 |
children | 3d9cdb5a4f01 |
rev | line source |
---|---|
5095 | 1 /* |
5219 | 2 * Copyright (C) 2007 Vitor Sessak <vitor1001@gmail.com> |
5095 | 3 * |
4 * This file is part of FFmpeg. | |
5 * | |
6 * FFmpeg is free software; you can redistribute it and/or | |
7 * modify it under the terms of the GNU Lesser General Public | |
8 * License as published by the Free Software Foundation; either | |
9 * version 2.1 of the License, or (at your option) any later version. | |
10 * | |
11 * FFmpeg is distributed in the hope that it will be useful, | |
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of | |
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU | |
14 * Lesser General Public License for more details. | |
15 * | |
16 * You should have received a copy of the GNU Lesser General Public | |
17 * License along with FFmpeg; if not, write to the Free Software | |
18 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA | |
19 */ | |
20 | |
21 /** | |
22 * @file cbook_gen.c | |
23 * Codebook Generator using the ELBG algorithm | |
24 */ | |
25 | |
26 #include <string.h> | |
27 | |
6763 | 28 #include "libavutil/random.h" |
5095 | 29 #include "elbg.h" |
30 #include "avcodec.h" | |
31 | |
32 #define DELTA_ERR_MAX 0.1 ///< Precision of the ELBG algorithm (as percentual error) | |
33 | |
34 /** | |
35 * In the ELBG jargon, a cell is the set of points that are closest to a | |
36 * codebook entry. Not to be confused with a RoQ Video cell. */ | |
37 typedef struct cell_s { | |
38 int index; | |
39 struct cell_s *next; | |
40 } cell; | |
41 | |
42 /** | |
43 * ELBG internal data | |
44 */ | |
45 typedef struct{ | |
46 int error; | |
47 int dim; | |
48 int numCB; | |
49 int *codebook; | |
50 cell **cells; | |
51 int *utility; | |
52 int *utility_inc; | |
53 int *nearest_cb; | |
54 int *points; | |
55 AVRandomState *rand_state; | |
56 } elbg_data; | |
57 | |
58 static inline int distance_limited(int *a, int *b, int dim, int limit) | |
59 { | |
60 int i, dist=0; | |
61 for (i=0; i<dim; i++) { | |
62 dist += (a[i] - b[i])*(a[i] - b[i]); | |
63 if (dist > limit) | |
64 return INT_MAX; | |
65 } | |
66 | |
67 return dist; | |
68 } | |
69 | |
70 static inline void vect_division(int *res, int *vect, int div, int dim) | |
71 { | |
72 int i; | |
73 if (div > 1) | |
74 for (i=0; i<dim; i++) | |
75 res[i] = ROUNDED_DIV(vect[i],div); | |
76 else if (res != vect) | |
77 memcpy(res, vect, dim*sizeof(int)); | |
78 | |
79 } | |
80 | |
81 static int eval_error_cell(elbg_data *elbg, int *centroid, cell *cells) | |
82 { | |
83 int error=0; | |
84 for (; cells; cells=cells->next) | |
85 error += distance_limited(centroid, elbg->points + cells->index*elbg->dim, elbg->dim, INT_MAX); | |
86 | |
87 return error; | |
88 } | |
89 | |
90 static int get_closest_codebook(elbg_data *elbg, int index) | |
91 { | |
92 int i, pick=0, diff, diff_min = INT_MAX; | |
93 for (i=0; i<elbg->numCB; i++) | |
94 if (i != index) { | |
95 diff = distance_limited(elbg->codebook + i*elbg->dim, elbg->codebook + index*elbg->dim, elbg->dim, diff_min); | |
96 if (diff < diff_min) { | |
97 pick = i; | |
98 diff_min = diff; | |
99 } | |
100 } | |
101 return pick; | |
102 } | |
103 | |
104 static int get_high_utility_cell(elbg_data *elbg) | |
105 { | |
106 int i=0; | |
107 /* Using linear search, do binary if it ever turns to be speed critical */ | |
7352
c2318e551ff5
When picking a "high utility centroid" do not pick one
vitor
parents:
7351
diff
changeset
|
108 int r = av_random(elbg->rand_state)%(elbg->utility_inc[elbg->numCB-1]-1) + 1; |
5095 | 109 while (elbg->utility_inc[i] < r) |
110 i++; | |
7352
c2318e551ff5
When picking a "high utility centroid" do not pick one
vitor
parents:
7351
diff
changeset
|
111 |
c2318e551ff5
When picking a "high utility centroid" do not pick one
vitor
parents:
7351
diff
changeset
|
112 assert(!elbg->cells[i]); |
c2318e551ff5
When picking a "high utility centroid" do not pick one
vitor
parents:
7351
diff
changeset
|
113 |
5095 | 114 return i; |
115 } | |
116 | |
117 /** | |
118 * Implementation of the simple LBG algorithm for just two codebooks | |
119 */ | |
120 static int simple_lbg(int dim, | |
5122 | 121 int *centroid[3], |
5095 | 122 int newutility[3], |
123 int *points, | |
124 cell *cells) | |
125 { | |
126 int i, idx; | |
127 int numpoints[2] = {0,0}; | |
128 int newcentroid[2][dim]; | |
129 cell *tempcell; | |
130 | |
131 memset(newcentroid, 0, sizeof(newcentroid)); | |
132 | |
133 newutility[0] = | |
134 newutility[1] = 0; | |
135 | |
136 for (tempcell = cells; tempcell; tempcell=tempcell->next) { | |
137 idx = distance_limited(centroid[0], points + tempcell->index*dim, dim, INT_MAX)>= | |
138 distance_limited(centroid[1], points + tempcell->index*dim, dim, INT_MAX); | |
139 numpoints[idx]++; | |
140 for (i=0; i<dim; i++) | |
141 newcentroid[idx][i] += points[tempcell->index*dim + i]; | |
142 } | |
143 | |
144 vect_division(centroid[0], newcentroid[0], numpoints[0], dim); | |
145 vect_division(centroid[1], newcentroid[1], numpoints[1], dim); | |
146 | |
147 for (tempcell = cells; tempcell; tempcell=tempcell->next) { | |
148 int dist[2] = {distance_limited(centroid[0], points + tempcell->index*dim, dim, INT_MAX), | |
149 distance_limited(centroid[1], points + tempcell->index*dim, dim, INT_MAX)}; | |
150 int idx = dist[0] > dist[1]; | |
151 newutility[idx] += dist[idx]; | |
152 } | |
153 | |
154 return newutility[0] + newutility[1]; | |
155 } | |
156 | |
157 static void get_new_centroids(elbg_data *elbg, int huc, int *newcentroid_i, | |
158 int *newcentroid_p) | |
159 { | |
160 cell *tempcell; | |
161 int min[elbg->dim]; | |
162 int max[elbg->dim]; | |
163 int i; | |
164 | |
165 for (i=0; i< elbg->dim; i++) { | |
166 min[i]=INT_MAX; | |
167 max[i]=0; | |
168 } | |
169 | |
170 for (tempcell = elbg->cells[huc]; tempcell; tempcell = tempcell->next) | |
171 for(i=0; i<elbg->dim; i++) { | |
172 min[i]=FFMIN(min[i], elbg->points[tempcell->index*elbg->dim + i]); | |
173 max[i]=FFMAX(max[i], elbg->points[tempcell->index*elbg->dim + i]); | |
174 } | |
175 | |
176 for (i=0; i<elbg->dim; i++) { | |
177 newcentroid_i[i] = min[i] + (max[i] - min[i])/3; | |
178 newcentroid_p[i] = min[i] + (2*(max[i] - min[i]))/3; | |
179 } | |
180 } | |
181 | |
182 /** | |
183 * Add the points in the low utility cell to its closest cell. Split the high | |
184 * utility cell, putting the separed points in the (now empty) low utility | |
185 * cell. | |
186 * | |
187 * @param elbg Internal elbg data | |
188 * @param indexes {luc, huc, cluc} | |
189 * @param newcentroid A vector with the position of the new centroids | |
190 */ | |
191 static void shift_codebook(elbg_data *elbg, int *indexes, | |
5122 | 192 int *newcentroid[3]) |
5095 | 193 { |
194 cell *tempdata; | |
195 cell **pp = &elbg->cells[indexes[2]]; | |
196 | |
197 while(*pp) | |
198 pp= &(*pp)->next; | |
199 | |
200 *pp = elbg->cells[indexes[0]]; | |
201 | |
202 elbg->cells[indexes[0]] = NULL; | |
203 tempdata = elbg->cells[indexes[1]]; | |
204 elbg->cells[indexes[1]] = NULL; | |
205 | |
206 while(tempdata) { | |
207 cell *tempcell2 = tempdata->next; | |
208 int idx = distance_limited(elbg->points + tempdata->index*elbg->dim, | |
209 newcentroid[0], elbg->dim, INT_MAX) > | |
210 distance_limited(elbg->points + tempdata->index*elbg->dim, | |
211 newcentroid[1], elbg->dim, INT_MAX); | |
212 | |
213 tempdata->next = elbg->cells[indexes[idx]]; | |
214 elbg->cells[indexes[idx]] = tempdata; | |
215 tempdata = tempcell2; | |
216 } | |
217 } | |
218 | |
219 static void evaluate_utility_inc(elbg_data *elbg) | |
220 { | |
221 int i, inc=0; | |
222 | |
223 for (i=0; i < elbg->numCB; i++) { | |
224 if (elbg->numCB*elbg->utility[i] > elbg->error) | |
225 inc += elbg->utility[i]; | |
226 elbg->utility_inc[i] = inc; | |
227 } | |
228 } | |
229 | |
230 | |
231 static void update_utility_and_n_cb(elbg_data *elbg, int idx, int newutility) | |
232 { | |
233 cell *tempcell; | |
234 | |
235 elbg->utility[idx] = newutility; | |
236 for (tempcell=elbg->cells[idx]; tempcell; tempcell=tempcell->next) | |
237 elbg->nearest_cb[tempcell->index] = idx; | |
238 } | |
239 | |
240 /** | |
241 * Evaluate if a shift lower the error. If it does, call shift_codebooks | |
242 * and update elbg->error, elbg->utility and elbg->nearest_cb. | |
243 * | |
244 * @param elbg Internal elbg data | |
245 * @param indexes {luc (low utility cell, huc (high utility cell), cluc (closest cell to low utility cell)} | |
246 */ | |
247 static void try_shift_candidate(elbg_data *elbg, int idx[3]) | |
248 { | |
249 int j, k, olderror=0, newerror, cont=0; | |
250 int newutility[3]; | |
251 int newcentroid[3][elbg->dim]; | |
5122 | 252 int *newcentroid_ptrs[3] = { newcentroid[0], newcentroid[1], newcentroid[2] }; |
5095 | 253 cell *tempcell; |
254 | |
255 for (j=0; j<3; j++) | |
256 olderror += elbg->utility[idx[j]]; | |
257 | |
258 memset(newcentroid[2], 0, elbg->dim*sizeof(int)); | |
259 | |
260 for (k=0; k<2; k++) | |
261 for (tempcell=elbg->cells[idx[2*k]]; tempcell; tempcell=tempcell->next) { | |
262 cont++; | |
263 for (j=0; j<elbg->dim; j++) | |
264 newcentroid[2][j] += elbg->points[tempcell->index*elbg->dim + j]; | |
265 } | |
266 | |
267 vect_division(newcentroid[2], newcentroid[2], cont, elbg->dim); | |
268 | |
269 get_new_centroids(elbg, idx[1], newcentroid[0], newcentroid[1]); | |
270 | |
271 newutility[2] = eval_error_cell(elbg, newcentroid[2], elbg->cells[idx[0]]); | |
272 newutility[2] += eval_error_cell(elbg, newcentroid[2], elbg->cells[idx[2]]); | |
273 | |
274 newerror = newutility[2]; | |
275 | |
5122 | 276 newerror += simple_lbg(elbg->dim, newcentroid_ptrs, newutility, elbg->points, |
5095 | 277 elbg->cells[idx[1]]); |
278 | |
279 if (olderror > newerror) { | |
5122 | 280 shift_codebook(elbg, idx, newcentroid_ptrs); |
5095 | 281 |
282 elbg->error += newerror - olderror; | |
283 | |
284 for (j=0; j<3; j++) | |
285 update_utility_and_n_cb(elbg, idx[j], newutility[j]); | |
286 | |
287 evaluate_utility_inc(elbg); | |
288 } | |
289 } | |
290 | |
291 /** | |
292 * Implementation of the ELBG block | |
293 */ | |
294 static void do_shiftings(elbg_data *elbg) | |
295 { | |
296 int idx[3]; | |
297 | |
298 evaluate_utility_inc(elbg); | |
299 | |
300 for (idx[0]=0; idx[0] < elbg->numCB; idx[0]++) | |
301 if (elbg->numCB*elbg->utility[idx[0]] < elbg->error) { | |
302 if (elbg->utility_inc[elbg->numCB-1] == 0) | |
303 return; | |
304 | |
305 idx[2] = get_closest_codebook(elbg, idx[0]); | |
7351
1502ba3beb72
The codebook generator algorithm involves picking three
vitor
parents:
6763
diff
changeset
|
306 do { |
1502ba3beb72
The codebook generator algorithm involves picking three
vitor
parents:
6763
diff
changeset
|
307 idx[1] = get_high_utility_cell(elbg); |
1502ba3beb72
The codebook generator algorithm involves picking three
vitor
parents:
6763
diff
changeset
|
308 } while (idx[1] == idx[0] || idx[1] == idx[2]); |
5095 | 309 |
310 try_shift_candidate(elbg, idx); | |
311 } | |
312 } | |
313 | |
314 #define BIG_PRIME 433494437LL | |
315 | |
316 void ff_init_elbg(int *points, int dim, int numpoints, int *codebook, | |
317 int numCB, int max_steps, int *closest_cb, | |
318 AVRandomState *rand_state) | |
319 { | |
320 int i, k; | |
321 | |
322 if (numpoints > 24*numCB) { | |
323 /* ELBG is very costly for a big number of points. So if we have a lot | |
324 of them, get a good initial codebook to save on iterations */ | |
325 int *temp_points = av_malloc(dim*(numpoints/8)*sizeof(int)); | |
326 for (i=0; i<numpoints/8; i++) { | |
327 k = (i*BIG_PRIME) % numpoints; | |
328 memcpy(temp_points + i*dim, points + k*dim, dim*sizeof(int)); | |
329 } | |
330 | |
331 ff_init_elbg(temp_points, dim, numpoints/8, codebook, numCB, 2*max_steps, closest_cb, rand_state); | |
332 ff_do_elbg(temp_points, dim, numpoints/8, codebook, numCB, 2*max_steps, closest_cb, rand_state); | |
333 | |
334 av_free(temp_points); | |
335 | |
336 } else // If not, initialize the codebook with random positions | |
337 for (i=0; i < numCB; i++) | |
338 memcpy(codebook + i*dim, points + ((i*BIG_PRIME)%numpoints)*dim, | |
339 dim*sizeof(int)); | |
340 | |
341 } | |
342 | |
343 void ff_do_elbg(int *points, int dim, int numpoints, int *codebook, | |
344 int numCB, int max_steps, int *closest_cb, | |
345 AVRandomState *rand_state) | |
346 { | |
347 int dist; | |
348 elbg_data elbg_d; | |
349 elbg_data *elbg = &elbg_d; | |
350 int i, j, k, last_error, steps=0; | |
351 int *dist_cb = av_malloc(numpoints*sizeof(int)); | |
352 int *size_part = av_malloc(numCB*sizeof(int)); | |
353 cell *list_buffer = av_malloc(numpoints*sizeof(cell)); | |
354 cell *free_cells; | |
355 | |
356 elbg->error = INT_MAX; | |
357 elbg->dim = dim; | |
358 elbg->numCB = numCB; | |
359 elbg->codebook = codebook; | |
360 elbg->cells = av_malloc(numCB*sizeof(cell *)); | |
361 elbg->utility = av_malloc(numCB*sizeof(int)); | |
362 elbg->nearest_cb = closest_cb; | |
363 elbg->points = points; | |
364 elbg->utility_inc = av_malloc(numCB*sizeof(int)); | |
365 | |
366 elbg->rand_state = rand_state; | |
367 | |
368 do { | |
369 free_cells = list_buffer; | |
370 last_error = elbg->error; | |
371 steps++; | |
372 memset(elbg->utility, 0, numCB*sizeof(int)); | |
373 memset(elbg->cells, 0, numCB*sizeof(cell *)); | |
374 | |
375 elbg->error = 0; | |
376 | |
377 /* This loop evaluate the actual Voronoi partition. It is the most | |
378 costly part of the algorithm. */ | |
379 for (i=0; i < numpoints; i++) { | |
380 dist_cb[i] = INT_MAX; | |
381 for (k=0; k < elbg->numCB; k++) { | |
382 dist = distance_limited(elbg->points + i*elbg->dim, elbg->codebook + k*elbg->dim, dim, dist_cb[i]); | |
383 if (dist < dist_cb[i]) { | |
384 dist_cb[i] = dist; | |
385 elbg->nearest_cb[i] = k; | |
386 } | |
387 } | |
388 elbg->error += dist_cb[i]; | |
389 elbg->utility[elbg->nearest_cb[i]] += dist_cb[i]; | |
390 free_cells->index = i; | |
391 free_cells->next = elbg->cells[elbg->nearest_cb[i]]; | |
392 elbg->cells[elbg->nearest_cb[i]] = free_cells; | |
393 free_cells++; | |
394 } | |
395 | |
396 do_shiftings(elbg); | |
397 | |
398 memset(size_part, 0, numCB*sizeof(int)); | |
399 | |
400 memset(elbg->codebook, 0, elbg->numCB*dim*sizeof(int)); | |
401 | |
402 for (i=0; i < numpoints; i++) { | |
403 size_part[elbg->nearest_cb[i]]++; | |
404 for (j=0; j < elbg->dim; j++) | |
405 elbg->codebook[elbg->nearest_cb[i]*elbg->dim + j] += | |
406 elbg->points[i*elbg->dim + j]; | |
407 } | |
408 | |
409 for (i=0; i < elbg->numCB; i++) | |
410 vect_division(elbg->codebook + i*elbg->dim, | |
411 elbg->codebook + i*elbg->dim, size_part[i], elbg->dim); | |
412 | |
413 } while(((last_error - elbg->error) > DELTA_ERR_MAX*elbg->error) && | |
414 (steps < max_steps)); | |
415 | |
416 av_free(dist_cb); | |
417 av_free(size_part); | |
418 av_free(elbg->utility); | |
419 av_free(list_buffer); | |
420 av_free(elbg->cells); | |
421 av_free(elbg->utility_inc); | |
422 } |