Mercurial > libavcodec.hg
annotate elbg.c @ 8442:60be1c7d8345 libavcodec
Make h264 parser 50% faster.
author | michael |
---|---|
date | Tue, 23 Dec 2008 02:34:58 +0000 |
parents | 456957d86106 |
children | 5b7d5a33a3e2 |
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]; | |
7353
3d9cdb5a4f01
Do declaration and initialization separately in elbg.c
vitor
parents:
7352
diff
changeset
|
252 int *newcentroid_ptrs[3]; |
5095 | 253 cell *tempcell; |
254 | |
7353
3d9cdb5a4f01
Do declaration and initialization separately in elbg.c
vitor
parents:
7352
diff
changeset
|
255 newcentroid_ptrs[0] = newcentroid[0]; |
3d9cdb5a4f01
Do declaration and initialization separately in elbg.c
vitor
parents:
7352
diff
changeset
|
256 newcentroid_ptrs[1] = newcentroid[1]; |
3d9cdb5a4f01
Do declaration and initialization separately in elbg.c
vitor
parents:
7352
diff
changeset
|
257 newcentroid_ptrs[2] = newcentroid[2]; |
3d9cdb5a4f01
Do declaration and initialization separately in elbg.c
vitor
parents:
7352
diff
changeset
|
258 |
5095 | 259 for (j=0; j<3; j++) |
260 olderror += elbg->utility[idx[j]]; | |
261 | |
262 memset(newcentroid[2], 0, elbg->dim*sizeof(int)); | |
263 | |
264 for (k=0; k<2; k++) | |
265 for (tempcell=elbg->cells[idx[2*k]]; tempcell; tempcell=tempcell->next) { | |
266 cont++; | |
267 for (j=0; j<elbg->dim; j++) | |
268 newcentroid[2][j] += elbg->points[tempcell->index*elbg->dim + j]; | |
269 } | |
270 | |
271 vect_division(newcentroid[2], newcentroid[2], cont, elbg->dim); | |
272 | |
273 get_new_centroids(elbg, idx[1], newcentroid[0], newcentroid[1]); | |
274 | |
275 newutility[2] = eval_error_cell(elbg, newcentroid[2], elbg->cells[idx[0]]); | |
276 newutility[2] += eval_error_cell(elbg, newcentroid[2], elbg->cells[idx[2]]); | |
277 | |
278 newerror = newutility[2]; | |
279 | |
5122 | 280 newerror += simple_lbg(elbg->dim, newcentroid_ptrs, newutility, elbg->points, |
5095 | 281 elbg->cells[idx[1]]); |
282 | |
283 if (olderror > newerror) { | |
5122 | 284 shift_codebook(elbg, idx, newcentroid_ptrs); |
5095 | 285 |
286 elbg->error += newerror - olderror; | |
287 | |
288 for (j=0; j<3; j++) | |
289 update_utility_and_n_cb(elbg, idx[j], newutility[j]); | |
290 | |
291 evaluate_utility_inc(elbg); | |
292 } | |
293 } | |
294 | |
295 /** | |
296 * Implementation of the ELBG block | |
297 */ | |
298 static void do_shiftings(elbg_data *elbg) | |
299 { | |
300 int idx[3]; | |
301 | |
302 evaluate_utility_inc(elbg); | |
303 | |
304 for (idx[0]=0; idx[0] < elbg->numCB; idx[0]++) | |
305 if (elbg->numCB*elbg->utility[idx[0]] < elbg->error) { | |
306 if (elbg->utility_inc[elbg->numCB-1] == 0) | |
307 return; | |
308 | |
7354
456957d86106
My commit at r14340 was not the right solution. For a monochromatic
vitor
parents:
7353
diff
changeset
|
309 idx[1] = get_high_utility_cell(elbg); |
5095 | 310 idx[2] = get_closest_codebook(elbg, idx[0]); |
311 | |
7354
456957d86106
My commit at r14340 was not the right solution. For a monochromatic
vitor
parents:
7353
diff
changeset
|
312 if (idx[1] != idx[0] && idx[1] != idx[2]) |
456957d86106
My commit at r14340 was not the right solution. For a monochromatic
vitor
parents:
7353
diff
changeset
|
313 try_shift_candidate(elbg, idx); |
5095 | 314 } |
315 } | |
316 | |
317 #define BIG_PRIME 433494437LL | |
318 | |
319 void ff_init_elbg(int *points, int dim, int numpoints, int *codebook, | |
320 int numCB, int max_steps, int *closest_cb, | |
321 AVRandomState *rand_state) | |
322 { | |
323 int i, k; | |
324 | |
325 if (numpoints > 24*numCB) { | |
326 /* ELBG is very costly for a big number of points. So if we have a lot | |
327 of them, get a good initial codebook to save on iterations */ | |
328 int *temp_points = av_malloc(dim*(numpoints/8)*sizeof(int)); | |
329 for (i=0; i<numpoints/8; i++) { | |
330 k = (i*BIG_PRIME) % numpoints; | |
331 memcpy(temp_points + i*dim, points + k*dim, dim*sizeof(int)); | |
332 } | |
333 | |
334 ff_init_elbg(temp_points, dim, numpoints/8, codebook, numCB, 2*max_steps, closest_cb, rand_state); | |
335 ff_do_elbg(temp_points, dim, numpoints/8, codebook, numCB, 2*max_steps, closest_cb, rand_state); | |
336 | |
337 av_free(temp_points); | |
338 | |
339 } else // If not, initialize the codebook with random positions | |
340 for (i=0; i < numCB; i++) | |
341 memcpy(codebook + i*dim, points + ((i*BIG_PRIME)%numpoints)*dim, | |
342 dim*sizeof(int)); | |
343 | |
344 } | |
345 | |
346 void ff_do_elbg(int *points, int dim, int numpoints, int *codebook, | |
347 int numCB, int max_steps, int *closest_cb, | |
348 AVRandomState *rand_state) | |
349 { | |
350 int dist; | |
351 elbg_data elbg_d; | |
352 elbg_data *elbg = &elbg_d; | |
353 int i, j, k, last_error, steps=0; | |
354 int *dist_cb = av_malloc(numpoints*sizeof(int)); | |
355 int *size_part = av_malloc(numCB*sizeof(int)); | |
356 cell *list_buffer = av_malloc(numpoints*sizeof(cell)); | |
357 cell *free_cells; | |
358 | |
359 elbg->error = INT_MAX; | |
360 elbg->dim = dim; | |
361 elbg->numCB = numCB; | |
362 elbg->codebook = codebook; | |
363 elbg->cells = av_malloc(numCB*sizeof(cell *)); | |
364 elbg->utility = av_malloc(numCB*sizeof(int)); | |
365 elbg->nearest_cb = closest_cb; | |
366 elbg->points = points; | |
367 elbg->utility_inc = av_malloc(numCB*sizeof(int)); | |
368 | |
369 elbg->rand_state = rand_state; | |
370 | |
371 do { | |
372 free_cells = list_buffer; | |
373 last_error = elbg->error; | |
374 steps++; | |
375 memset(elbg->utility, 0, numCB*sizeof(int)); | |
376 memset(elbg->cells, 0, numCB*sizeof(cell *)); | |
377 | |
378 elbg->error = 0; | |
379 | |
380 /* This loop evaluate the actual Voronoi partition. It is the most | |
381 costly part of the algorithm. */ | |
382 for (i=0; i < numpoints; i++) { | |
383 dist_cb[i] = INT_MAX; | |
384 for (k=0; k < elbg->numCB; k++) { | |
385 dist = distance_limited(elbg->points + i*elbg->dim, elbg->codebook + k*elbg->dim, dim, dist_cb[i]); | |
386 if (dist < dist_cb[i]) { | |
387 dist_cb[i] = dist; | |
388 elbg->nearest_cb[i] = k; | |
389 } | |
390 } | |
391 elbg->error += dist_cb[i]; | |
392 elbg->utility[elbg->nearest_cb[i]] += dist_cb[i]; | |
393 free_cells->index = i; | |
394 free_cells->next = elbg->cells[elbg->nearest_cb[i]]; | |
395 elbg->cells[elbg->nearest_cb[i]] = free_cells; | |
396 free_cells++; | |
397 } | |
398 | |
399 do_shiftings(elbg); | |
400 | |
401 memset(size_part, 0, numCB*sizeof(int)); | |
402 | |
403 memset(elbg->codebook, 0, elbg->numCB*dim*sizeof(int)); | |
404 | |
405 for (i=0; i < numpoints; i++) { | |
406 size_part[elbg->nearest_cb[i]]++; | |
407 for (j=0; j < elbg->dim; j++) | |
408 elbg->codebook[elbg->nearest_cb[i]*elbg->dim + j] += | |
409 elbg->points[i*elbg->dim + j]; | |
410 } | |
411 | |
412 for (i=0; i < elbg->numCB; i++) | |
413 vect_division(elbg->codebook + i*elbg->dim, | |
414 elbg->codebook + i*elbg->dim, size_part[i], elbg->dim); | |
415 | |
416 } while(((last_error - elbg->error) > DELTA_ERR_MAX*elbg->error) && | |
417 (steps < max_steps)); | |
418 | |
419 av_free(dist_cb); | |
420 av_free(size_part); | |
421 av_free(elbg->utility); | |
422 av_free(list_buffer); | |
423 av_free(elbg->cells); | |
424 av_free(elbg->utility_inc); | |
425 } |