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) {
140 int numpoints[2] = {0,0};
141 int *newcentroid[2] = {
147 memset(newcentroid[0], 0, 2 * dim *
sizeof(*newcentroid[0]));
152 for (tempcell = cells; tempcell; tempcell=tempcell->
next) {
156 for (i=0; i<
dim; i++)
157 newcentroid[idx][i] += points[tempcell->
index*dim + i];
160 vect_division(centroid[0], newcentroid[0], numpoints[0], dim);
161 vect_division(centroid[1], newcentroid[1], numpoints[1], dim);
163 for (tempcell = cells; tempcell; tempcell=tempcell->
next) {
166 int idx = dist[0] > dist[1];
167 newutility[idx] += dist[idx];
170 return newutility[0] + newutility[1];
177 int *
min = newcentroid_i;
178 int *
max = newcentroid_p;
181 for (i=0; i< elbg->
dim; i++) {
186 for (tempcell = elbg->
cells[huc]; tempcell; tempcell = tempcell->
next)
187 for(i=0; i<elbg->
dim; i++) {
192 for (i=0; i<elbg->
dim; i++) {
193 int ni = min[
i] + (max[
i] - min[
i])/3;
194 int np = min[
i] + (2*(max[
i] - min[
i]))/3;
195 newcentroid_i[
i] = ni;
196 newcentroid_p[
i] = np;
218 *pp = elbg->
cells[indexes[0]];
221 tempdata = elbg->
cells[indexes[1]];
227 newcentroid[0], elbg->
dim, INT_MAX) >
229 newcentroid[1], elbg->
dim, INT_MAX);
231 tempdata->
next = elbg->
cells[indexes[idx]];
232 elbg->
cells[indexes[idx]] = tempdata;
233 tempdata = tempcell2;
242 for (i=0; i < elbg->
numCB; i++) {
254 elbg->
utility[idx] = newutility;
255 for (tempcell=elbg->
cells[idx]; tempcell; tempcell=tempcell->
next)
268 int j, k, olderror=0, newerror, cont=0;
270 int *newcentroid[3] = {
278 olderror += elbg->
utility[idx[j]];
280 memset(newcentroid[2], 0, elbg->
dim*
sizeof(
int));
283 for (tempcell=elbg->
cells[idx[2*k]]; tempcell; tempcell=tempcell->
next) {
285 for (j=0; j<elbg->
dim; j++)
296 newerror = newutility[2];
299 elbg->
cells[idx[1]]);
301 if (olderror > newerror) {
304 elbg->
error += newerror - olderror;
322 for (idx[0]=0; idx[0] < elbg->
numCB; idx[0]++)
330 if (idx[1] != idx[0] && idx[1] != idx[2])
335 #define BIG_PRIME 433494437LL 338 int numCB,
int max_steps,
int *closest_cb,
343 if (numpoints > 24*numCB) {
349 for (i=0; i<numpoints/8; i++) {
351 memcpy(temp_points + i*dim, points + k*dim, dim*
sizeof(
int));
355 numCB, 2 * max_steps, closest_cb, rand_state);
361 numCB, 2 * max_steps, closest_cb, rand_state);
365 for (i=0; i < numCB; i++)
366 memcpy(codebook + i*dim, points + ((i*
BIG_PRIME)%numpoints)*dim,
372 int numCB,
int max_steps,
int *closest_cb,
378 int i, j, k, last_error, steps = 0,
ret = 0;
383 int best_dist, best_idx = 0;
385 elbg->
error = INT_MAX;
396 if (!dist_cb || !size_part || !list_buffer || !elbg->
cells ||
405 free_cells = list_buffer;
406 last_error = elbg->
error;
408 memset(elbg->
utility, 0, numCB*
sizeof(
int));
409 memset(elbg->
cells, 0, numCB*
sizeof(
cell *));
415 for (i=0; i < numpoints; i++) {
417 for (k=0; k < elbg->
numCB; k++) {
419 if (dist < best_dist) {
425 dist_cb[
i] = best_dist;
426 elbg->
error += dist_cb[
i];
436 memset(size_part, 0, numCB*
sizeof(
int));
440 for (i=0; i < numpoints; i++) {
442 for (j=0; j < elbg->
dim; j++)
447 for (i=0; i < elbg->
numCB; i++)
452 (steps < max_steps));
Context structure for the Lagged Fibonacci PRNG.
static const unsigned codebook[256][2]
static void do_shiftings(elbg_data *elbg)
Implementation of the ELBG block.
static int simple_lbg(elbg_data *elbg, int dim, int *centroid[3], int newutility[3], int *points, cell *cells)
Implementation of the simple LBG algorithm for just two codebooks.
The reader does not expect b to be semantically here and if the code is changed by maybe adding a a division or other the signedness will almost certainly be mistaken To avoid this confusion a new type was SUINT is the C unsigned type but it holds a signed int to use the same example SUINT a
static void error(const char *err)
static int distance_limited(int *a, int *b, int dim, int limit)
static void get_new_centroids(elbg_data *elbg, int huc, int *newcentroid_i, int *newcentroid_p)
static void evaluate_utility_inc(elbg_data *elbg)
#define av_assert2(cond)
assert() equivalent, that does lie in speed critical code.
int avpriv_do_elbg(int *points, int dim, int numpoints, int *codebook, int numCB, int max_steps, int *closest_cb, AVLFG *rand_state)
Implementation of the Enhanced LBG Algorithm Based on the paper "Neural Networks 14:1219-1237" that c...
#define ROUNDED_DIV(a, b)
static void vect_division(int *res, int *vect, int div, int dim)
simple assert() macros that are a bit more flexible than ISO C assert().
In the ELBG jargon, a cell is the set of points that are closest to a codebook entry.
static int get_high_utility_cell(elbg_data *elbg)
static int get_closest_codebook(elbg_data *elbg, int index)
static void update_utility_and_n_cb(elbg_data *elbg, int idx, int newutility)
int avpriv_init_elbg(int *points, int dim, int numpoints, int *codebook, int numCB, int max_steps, int *closest_cb, AVLFG *rand_state)
Initialize the **codebook vector for the elbg algorithm.
Libavcodec external API header.
static unsigned int av_lfg_get(AVLFG *c)
Get the next random unsigned 32-bit number using an ALFG.
static void shift_codebook(elbg_data *elbg, int *indexes, int *newcentroid[3])
Add the points in the low utility cell to its closest cell.
static int eval_error_cell(elbg_data *elbg, int *centroid, cell *cells)
common internal and external API header
static av_always_inline int diff(const uint32_t a, const uint32_t b)
#define DELTA_ERR_MAX
Precision of the ELBG algorithm (as percentage error)
#define av_malloc_array(a, b)
static void try_shift_candidate(elbg_data *elbg, int idx[3])
Evaluate if a shift lower the error.
Filter the word “frame” indicates either a video frame or a group of audio as stored in an AVFrame structure Format for each input and each output the list of supported formats For video that means pixel format For audio that means channel sample they are references to shared objects When the negotiation mechanism computes the intersection of the formats supported at each end of a all references to both lists are replaced with a reference to the intersection And when a single format is eventually chosen for a link amongst the remaining all references to the list are updated That means that if a filter requires that its input and output have the same format amongst a supported all it has to do is use a reference to the same list of formats query_formats can leave some formats unset and return AVERROR(EAGAIN) to cause the negotiation mechanism toagain later.That can be used by filters with complex requirements to use the format negotiated on one link to set the formats supported on another.Frame references ownership and permissions