Mercurial > libavcodec.hg
comparison elbg.c @ 5095:ed41cfae128d libavcodec
Codebook generator using the ELBG algorithm
patch by Vitor: printf(vitor%d gmail com, 1001)
original thread: Re: [FFmpeg-devel] [PATCH] Add a codebook generator
(was: [PATCH] RoQ video encoder, take 2)
date: 05/28/2007 01:21 PM
author | benoit |
---|---|
date | Mon, 04 Jun 2007 07:28:34 +0000 |
parents | |
children | 753230e2dcf0 |
comparison
equal
deleted
inserted
replaced
5094:ce57e3f2b2a7 | 5095:ed41cfae128d |
---|---|
1 /* | |
2 * Copyright (C) 2007 Vitor <vitor1001@gmail.com> | |
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 | |
28 #include "elbg.h" | |
29 #include "avcodec.h" | |
30 #include "random.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 */ | |
108 int r = av_random(elbg->rand_state)%elbg->utility_inc[elbg->numCB-1]; | |
109 while (elbg->utility_inc[i] < r) | |
110 i++; | |
111 return i; | |
112 } | |
113 | |
114 /** | |
115 * Implementation of the simple LBG algorithm for just two codebooks | |
116 */ | |
117 static int simple_lbg(int dim, | |
118 int centroid[3][dim], | |
119 int newutility[3], | |
120 int *points, | |
121 cell *cells) | |
122 { | |
123 int i, idx; | |
124 int numpoints[2] = {0,0}; | |
125 int newcentroid[2][dim]; | |
126 cell *tempcell; | |
127 | |
128 memset(newcentroid, 0, sizeof(newcentroid)); | |
129 | |
130 newutility[0] = | |
131 newutility[1] = 0; | |
132 | |
133 for (tempcell = cells; tempcell; tempcell=tempcell->next) { | |
134 idx = distance_limited(centroid[0], points + tempcell->index*dim, dim, INT_MAX)>= | |
135 distance_limited(centroid[1], points + tempcell->index*dim, dim, INT_MAX); | |
136 numpoints[idx]++; | |
137 for (i=0; i<dim; i++) | |
138 newcentroid[idx][i] += points[tempcell->index*dim + i]; | |
139 } | |
140 | |
141 vect_division(centroid[0], newcentroid[0], numpoints[0], dim); | |
142 vect_division(centroid[1], newcentroid[1], numpoints[1], dim); | |
143 | |
144 for (tempcell = cells; tempcell; tempcell=tempcell->next) { | |
145 int dist[2] = {distance_limited(centroid[0], points + tempcell->index*dim, dim, INT_MAX), | |
146 distance_limited(centroid[1], points + tempcell->index*dim, dim, INT_MAX)}; | |
147 int idx = dist[0] > dist[1]; | |
148 newutility[idx] += dist[idx]; | |
149 } | |
150 | |
151 return newutility[0] + newutility[1]; | |
152 } | |
153 | |
154 static void get_new_centroids(elbg_data *elbg, int huc, int *newcentroid_i, | |
155 int *newcentroid_p) | |
156 { | |
157 cell *tempcell; | |
158 int min[elbg->dim]; | |
159 int max[elbg->dim]; | |
160 int i; | |
161 | |
162 for (i=0; i< elbg->dim; i++) { | |
163 min[i]=INT_MAX; | |
164 max[i]=0; | |
165 } | |
166 | |
167 for (tempcell = elbg->cells[huc]; tempcell; tempcell = tempcell->next) | |
168 for(i=0; i<elbg->dim; i++) { | |
169 min[i]=FFMIN(min[i], elbg->points[tempcell->index*elbg->dim + i]); | |
170 max[i]=FFMAX(max[i], elbg->points[tempcell->index*elbg->dim + i]); | |
171 } | |
172 | |
173 for (i=0; i<elbg->dim; i++) { | |
174 newcentroid_i[i] = min[i] + (max[i] - min[i])/3; | |
175 newcentroid_p[i] = min[i] + (2*(max[i] - min[i]))/3; | |
176 } | |
177 } | |
178 | |
179 /** | |
180 * Add the points in the low utility cell to its closest cell. Split the high | |
181 * utility cell, putting the separed points in the (now empty) low utility | |
182 * cell. | |
183 * | |
184 * @param elbg Internal elbg data | |
185 * @param indexes {luc, huc, cluc} | |
186 * @param newcentroid A vector with the position of the new centroids | |
187 */ | |
188 static void shift_codebook(elbg_data *elbg, int *indexes, | |
189 int newcentroid[3][elbg->dim]) | |
190 { | |
191 cell *tempdata; | |
192 cell **pp = &elbg->cells[indexes[2]]; | |
193 | |
194 while(*pp) | |
195 pp= &(*pp)->next; | |
196 | |
197 *pp = elbg->cells[indexes[0]]; | |
198 | |
199 elbg->cells[indexes[0]] = NULL; | |
200 tempdata = elbg->cells[indexes[1]]; | |
201 elbg->cells[indexes[1]] = NULL; | |
202 | |
203 while(tempdata) { | |
204 cell *tempcell2 = tempdata->next; | |
205 int idx = distance_limited(elbg->points + tempdata->index*elbg->dim, | |
206 newcentroid[0], elbg->dim, INT_MAX) > | |
207 distance_limited(elbg->points + tempdata->index*elbg->dim, | |
208 newcentroid[1], elbg->dim, INT_MAX); | |
209 | |
210 tempdata->next = elbg->cells[indexes[idx]]; | |
211 elbg->cells[indexes[idx]] = tempdata; | |
212 tempdata = tempcell2; | |
213 } | |
214 } | |
215 | |
216 static void evaluate_utility_inc(elbg_data *elbg) | |
217 { | |
218 int i, inc=0; | |
219 | |
220 for (i=0; i < elbg->numCB; i++) { | |
221 if (elbg->numCB*elbg->utility[i] > elbg->error) | |
222 inc += elbg->utility[i]; | |
223 elbg->utility_inc[i] = inc; | |
224 } | |
225 } | |
226 | |
227 | |
228 static void update_utility_and_n_cb(elbg_data *elbg, int idx, int newutility) | |
229 { | |
230 cell *tempcell; | |
231 | |
232 elbg->utility[idx] = newutility; | |
233 for (tempcell=elbg->cells[idx]; tempcell; tempcell=tempcell->next) | |
234 elbg->nearest_cb[tempcell->index] = idx; | |
235 } | |
236 | |
237 /** | |
238 * Evaluate if a shift lower the error. If it does, call shift_codebooks | |
239 * and update elbg->error, elbg->utility and elbg->nearest_cb. | |
240 * | |
241 * @param elbg Internal elbg data | |
242 * @param indexes {luc (low utility cell, huc (high utility cell), cluc (closest cell to low utility cell)} | |
243 */ | |
244 static void try_shift_candidate(elbg_data *elbg, int idx[3]) | |
245 { | |
246 int j, k, olderror=0, newerror, cont=0; | |
247 int newutility[3]; | |
248 int newcentroid[3][elbg->dim]; | |
249 cell *tempcell; | |
250 | |
251 for (j=0; j<3; j++) | |
252 olderror += elbg->utility[idx[j]]; | |
253 | |
254 memset(newcentroid[2], 0, elbg->dim*sizeof(int)); | |
255 | |
256 for (k=0; k<2; k++) | |
257 for (tempcell=elbg->cells[idx[2*k]]; tempcell; tempcell=tempcell->next) { | |
258 cont++; | |
259 for (j=0; j<elbg->dim; j++) | |
260 newcentroid[2][j] += elbg->points[tempcell->index*elbg->dim + j]; | |
261 } | |
262 | |
263 vect_division(newcentroid[2], newcentroid[2], cont, elbg->dim); | |
264 | |
265 get_new_centroids(elbg, idx[1], newcentroid[0], newcentroid[1]); | |
266 | |
267 newutility[2] = eval_error_cell(elbg, newcentroid[2], elbg->cells[idx[0]]); | |
268 newutility[2] += eval_error_cell(elbg, newcentroid[2], elbg->cells[idx[2]]); | |
269 | |
270 newerror = newutility[2]; | |
271 | |
272 newerror += simple_lbg(elbg->dim, newcentroid, newutility, elbg->points, | |
273 elbg->cells[idx[1]]); | |
274 | |
275 if (olderror > newerror) { | |
276 shift_codebook(elbg, idx, newcentroid); | |
277 | |
278 elbg->error += newerror - olderror; | |
279 | |
280 for (j=0; j<3; j++) | |
281 update_utility_and_n_cb(elbg, idx[j], newutility[j]); | |
282 | |
283 evaluate_utility_inc(elbg); | |
284 } | |
285 } | |
286 | |
287 /** | |
288 * Implementation of the ELBG block | |
289 */ | |
290 static void do_shiftings(elbg_data *elbg) | |
291 { | |
292 int idx[3]; | |
293 | |
294 evaluate_utility_inc(elbg); | |
295 | |
296 for (idx[0]=0; idx[0] < elbg->numCB; idx[0]++) | |
297 if (elbg->numCB*elbg->utility[idx[0]] < elbg->error) { | |
298 if (elbg->utility_inc[elbg->numCB-1] == 0) | |
299 return; | |
300 | |
301 idx[1] = get_high_utility_cell(elbg); | |
302 idx[2] = get_closest_codebook(elbg, idx[0]); | |
303 | |
304 try_shift_candidate(elbg, idx); | |
305 } | |
306 } | |
307 | |
308 #define BIG_PRIME 433494437LL | |
309 | |
310 void ff_init_elbg(int *points, int dim, int numpoints, int *codebook, | |
311 int numCB, int max_steps, int *closest_cb, | |
312 AVRandomState *rand_state) | |
313 { | |
314 int i, k; | |
315 | |
316 if (numpoints > 24*numCB) { | |
317 /* ELBG is very costly for a big number of points. So if we have a lot | |
318 of them, get a good initial codebook to save on iterations */ | |
319 int *temp_points = av_malloc(dim*(numpoints/8)*sizeof(int)); | |
320 for (i=0; i<numpoints/8; i++) { | |
321 k = (i*BIG_PRIME) % numpoints; | |
322 memcpy(temp_points + i*dim, points + k*dim, dim*sizeof(int)); | |
323 } | |
324 | |
325 ff_init_elbg(temp_points, dim, numpoints/8, codebook, numCB, 2*max_steps, closest_cb, rand_state); | |
326 ff_do_elbg(temp_points, dim, numpoints/8, codebook, numCB, 2*max_steps, closest_cb, rand_state); | |
327 | |
328 av_free(temp_points); | |
329 | |
330 } else // If not, initialize the codebook with random positions | |
331 for (i=0; i < numCB; i++) | |
332 memcpy(codebook + i*dim, points + ((i*BIG_PRIME)%numpoints)*dim, | |
333 dim*sizeof(int)); | |
334 | |
335 } | |
336 | |
337 void ff_do_elbg(int *points, int dim, int numpoints, int *codebook, | |
338 int numCB, int max_steps, int *closest_cb, | |
339 AVRandomState *rand_state) | |
340 { | |
341 int dist; | |
342 elbg_data elbg_d; | |
343 elbg_data *elbg = &elbg_d; | |
344 int i, j, k, last_error, steps=0; | |
345 int *dist_cb = av_malloc(numpoints*sizeof(int)); | |
346 int *size_part = av_malloc(numCB*sizeof(int)); | |
347 cell *list_buffer = av_malloc(numpoints*sizeof(cell)); | |
348 cell *free_cells; | |
349 | |
350 elbg->error = INT_MAX; | |
351 elbg->dim = dim; | |
352 elbg->numCB = numCB; | |
353 elbg->codebook = codebook; | |
354 elbg->cells = av_malloc(numCB*sizeof(cell *)); | |
355 elbg->utility = av_malloc(numCB*sizeof(int)); | |
356 elbg->nearest_cb = closest_cb; | |
357 elbg->points = points; | |
358 elbg->utility_inc = av_malloc(numCB*sizeof(int)); | |
359 | |
360 elbg->rand_state = rand_state; | |
361 | |
362 do { | |
363 free_cells = list_buffer; | |
364 last_error = elbg->error; | |
365 steps++; | |
366 memset(elbg->utility, 0, numCB*sizeof(int)); | |
367 memset(elbg->cells, 0, numCB*sizeof(cell *)); | |
368 | |
369 elbg->error = 0; | |
370 | |
371 /* This loop evaluate the actual Voronoi partition. It is the most | |
372 costly part of the algorithm. */ | |
373 for (i=0; i < numpoints; i++) { | |
374 dist_cb[i] = INT_MAX; | |
375 for (k=0; k < elbg->numCB; k++) { | |
376 dist = distance_limited(elbg->points + i*elbg->dim, elbg->codebook + k*elbg->dim, dim, dist_cb[i]); | |
377 if (dist < dist_cb[i]) { | |
378 dist_cb[i] = dist; | |
379 elbg->nearest_cb[i] = k; | |
380 } | |
381 } | |
382 elbg->error += dist_cb[i]; | |
383 elbg->utility[elbg->nearest_cb[i]] += dist_cb[i]; | |
384 free_cells->index = i; | |
385 free_cells->next = elbg->cells[elbg->nearest_cb[i]]; | |
386 elbg->cells[elbg->nearest_cb[i]] = free_cells; | |
387 free_cells++; | |
388 } | |
389 | |
390 do_shiftings(elbg); | |
391 | |
392 memset(size_part, 0, numCB*sizeof(int)); | |
393 | |
394 memset(elbg->codebook, 0, elbg->numCB*dim*sizeof(int)); | |
395 | |
396 for (i=0; i < numpoints; i++) { | |
397 size_part[elbg->nearest_cb[i]]++; | |
398 for (j=0; j < elbg->dim; j++) | |
399 elbg->codebook[elbg->nearest_cb[i]*elbg->dim + j] += | |
400 elbg->points[i*elbg->dim + j]; | |
401 } | |
402 | |
403 for (i=0; i < elbg->numCB; i++) | |
404 vect_division(elbg->codebook + i*elbg->dim, | |
405 elbg->codebook + i*elbg->dim, size_part[i], elbg->dim); | |
406 | |
407 } while(((last_error - elbg->error) > DELTA_ERR_MAX*elbg->error) && | |
408 (steps < max_steps)); | |
409 | |
410 av_free(dist_cb); | |
411 av_free(size_part); | |
412 av_free(elbg->utility); | |
413 av_free(list_buffer); | |
414 av_free(elbg->cells); | |
415 av_free(elbg->utility_inc); | |
416 } |