diff options
Diffstat (limited to 'converter/other/fiasco/codec/approx.c')
| -rw-r--r-- | converter/other/fiasco/codec/approx.c | 140 |
1 files changed, 70 insertions, 70 deletions
diff --git a/converter/other/fiasco/codec/approx.c b/converter/other/fiasco/codec/approx.c index d8fefcaa..a3f6523d 100644 --- a/converter/other/fiasco/codec/approx.c +++ b/converter/other/fiasco/codec/approx.c @@ -2,7 +2,7 @@ * approx.c: Approximation of range images with matching pursuit * * Written by: Ullrich Hafner - * + * * This file is part of FIASCO (Fractal Image And Sequence COdec) * Copyright (C) 1994-2000 Ullrich Hafner */ @@ -35,7 +35,7 @@ /***************************************************************************** local variables - + *****************************************************************************/ typedef struct mp @@ -53,13 +53,13 @@ typedef struct mp /***************************************************************************** prototypes - + *****************************************************************************/ static void orthogonalize (unsigned index, unsigned n, unsigned level, real_t min_norm, const word_t *domain_blocks, const coding_t *c); -static void +static void matching_pursuit (mp_t *mp, bool_t full_search, real_t price, unsigned max_edges, int y_state, const range_t *range, const domain_pool_t *domain_pool, const coeff_t *coeff, @@ -68,14 +68,14 @@ matching_pursuit (mp_t *mp, bool_t full_search, real_t price, /***************************************************************************** public code - + *****************************************************************************/ -real_t +real_t approximate_range (real_t max_costs, real_t price, int max_edges, int y_state, range_t *range, domain_pool_t *domain_pool, coeff_t *coeff, const wfa_t *wfa, const coding_t *c) { -/*---------------------------------------------------------------------------- +/*---------------------------------------------------------------------------- Approximate image block 'range' by matching pursuit. This functions calls the matching pursuit algorithm several times (with different parameters) in order to find the best approximation. Refer to function @@ -99,15 +99,15 @@ approximate_range (real_t max_costs, real_t price, int max_edges, */ if (c->options.second_domain_block) { mp_t tmp_mp; - + tmp_mp = mp; /* initial value */ tmp_mp.exclude[0] = tmp_mp.indices [0]; tmp_mp.exclude[1] = NO_EDGE; - + matching_pursuit(&tmp_mp, c->options.full_search, price, max_edges, y_state, range, domain_pool, coeff, wfa, c); - if (tmp_mp.costs < mp.costs) /* success */ + if (tmp_mp.costs < mp.costs) /* success */ mp = tmp_mp; } @@ -123,23 +123,23 @@ approximate_range (real_t max_costs, real_t price, int max_edges, tmp_mp = mp; /* initial value */ iteration = -1; /* initial value */ - + do { int i; - + ++iteration; tmp_mp.exclude[iteration] = NO_EDGE; - + for (i = 0; isdomain(tmp_mp.indices[i]); ++i) { if (tmp_mp.weight [i] == 0) { tmp_mp.exclude[iteration] = tmp_mp.indices [i]; break; } - } + } if (isdomain (tmp_mp.exclude [iteration])) { /* try again */ tmp_mp.exclude [iteration + 1] = NO_EDGE; - + matching_pursuit(&tmp_mp, c->options.full_search, price, max_edges, y_state, range, domain_pool, coeff, wfa, c); @@ -165,25 +165,25 @@ approximate_range (real_t max_costs, real_t price, int max_edges, do { int i; - + ++iteration; tmp_mp.exclude[iteration] = NO_EDGE; - + for (i = 0; isdomain (tmp_mp.indices [i]); ++i) { rpf_t * const rpf = tmp_mp.indices [i] ? coeff->rpf : coeff->dc_rpf; - + if (tmp_mp.weight [i] == btor (rtob (200, rpf), rpf) || tmp_mp.weight [i] == btor (rtob (-200, rpf), rpf)) { tmp_mp.exclude [iteration] = tmp_mp.indices [i]; break; } } - + if (isdomain(tmp_mp.exclude[iteration])) { /* try again */ tmp_mp.exclude[iteration + 1] = NO_EDGE; - + matching_pursuit(&tmp_mp, c->options.full_search, price, max_edges, y_state, range, domain_pool, coeff, wfa, c); @@ -226,10 +226,10 @@ approximate_range (real_t max_costs, real_t price, int max_edges, range->level, y_state, wfa, domain_pool->model); coeff->update (mp.weight, mp.into, range->level, coeff); - + Free(domain_blocks); } - + for (edge = 0; isedge (mp.indices [edge]); ++edge) { range->into [edge] = mp.into [edge]; range->weight [edge] = mp.weight [edge]; @@ -242,7 +242,7 @@ approximate_range (real_t max_costs, real_t price, int max_edges, range->into [0] = NO_EDGE; mp.costs = MAXCOSTS; } - + return mp.costs; } @@ -251,25 +251,25 @@ approximate_range (real_t max_costs, real_t price, int max_edges, /***************************************************************************** local variables - + *****************************************************************************/ -static real_t norm_ortho_vector [MAXSTATES]; +static real_t norm_ortho_vector [MAXSTATES]; /* * Square-norm of the i-th vector of the orthogonal basis (OB) * ||o_i||^2; i = 0, ... ,n */ static real_t ip_image_ortho_vector [MAXEDGES]; -/* - * Inner product between the i-th vector of the OB and the given range: - * <b, o_i>; i = 0, ... ,n +/* + * Inner product between the i-th vector of the OB and the given range: + * <b, o_i>; i = 0, ... ,n */ static real_t ip_domain_ortho_vector [MAXSTATES][MAXEDGES]; -/* - * Inner product between the i-th vector of the OB and the image of domain j: - * <s_j, o_i>; j = 0, ... , wfa->states; i = 0, ... ,n, +/* + * Inner product between the i-th vector of the OB and the image of domain j: + * <s_j, o_i>; j = 0, ... , wfa->states; i = 0, ... ,n, */ -static real_t rem_denominator [MAXSTATES]; +static real_t rem_denominator [MAXSTATES]; static real_t rem_numerator [MAXSTATES]; /* * At step n of the orthogonalization the comparative value @@ -280,7 +280,7 @@ static real_t rem_numerator [MAXSTATES]; * the constant (remaining) parts of every domain are * stored in 'rem_numerator' and 'rem_denominator' separately */ -static bool_t used [MAXSTATES]; +static bool_t used [MAXSTATES]; /* * Shows whether a domain image was already used in a * linear combination (YES) or not (NO) @@ -289,10 +289,10 @@ static bool_t used [MAXSTATES]; /***************************************************************************** private code - + *****************************************************************************/ -static void +static void matching_pursuit (mp_t *mp, bool_t full_search, real_t price, unsigned max_edges, int y_state, const range_t *range, const domain_pool_t *domain_pool, const coeff_t *coeff, @@ -313,7 +313,7 @@ matching_pursuit (mp_t *mp, bool_t full_search, real_t price, * elements in the linear combination is limited by 'max_edges'. In * 'mp', vectors may be specified which should be excluded during the * approximation. - * + * * No return value. * * Side effects: @@ -329,7 +329,7 @@ matching_pursuit (mp_t *mp, bool_t full_search, real_t price, const real_t min_norm = 2e-3; /* lower bound of norm */ unsigned best_n = 0; unsigned size = size_of_level (range->level); - + /* * Initialize domain pool and inner product arrays */ @@ -378,7 +378,7 @@ matching_pursuit (mp_t *mp, bool_t full_search, real_t price, + additional_bits) * price + mp->err; n = 0; - do + do { /* * Current approximation is: b = d_0 o_0 + ... + d_(n-1) o_(n-1) @@ -390,15 +390,15 @@ matching_pursuit (mp_t *mp, bool_t full_search, real_t price, * which has minimal costs: s_index. * (No progress is indicated by index == -1) */ - + real_t min_matrix_bits = 0; real_t min_weights_bits = 0; real_t min_error = 0; real_t min_weight [MAXEDGES]; real_t min_costs = full_search ? MAXCOSTS : mp->costs; - - for (index = -1, domain = 0; domain_blocks [domain] >= 0; domain++) - if (!used [domain]) + + for (index = -1, domain = 0; domain_blocks [domain] >= 0; domain++) + if (!used [domain]) { real_t matrix_bits, weights_bits; /* @@ -413,7 +413,7 @@ matching_pursuit (mp_t *mp, bool_t full_search, real_t price, word_t states [MAXEDGES + 1]; real_t weights [MAXEDGES + 1]; unsigned i, k; - + for (i = 0, k = 0; k < n; k++) if (mp->weight [k] != 0) { @@ -477,7 +477,7 @@ matching_pursuit (mp_t *mp, bool_t full_search, real_t price, f[k] = ip_image_ortho_vector[k] / norm_ortho_vector[k]; v [k] = mp->indices [k]; } - + for (l = n; l >= 0; --l) { rpf_t * const rpf = domain_blocks[v[l]] ? coeff->rpf : coeff->dc_rpf; @@ -488,13 +488,13 @@ matching_pursuit (mp_t *mp, bool_t full_search, real_t price, { real_t const fl = f[l]; - + for (k = 0; k < l; ++k) { f[k] -= fl * ip_domain_ortho_vector[v[l]][k] / norm_ortho_vector[k]; } } - } + } /* * Compute the number of output bits of the linear @@ -507,7 +507,7 @@ matching_pursuit (mp_t *mp, bool_t full_search, real_t price, word_t states [MAXEDGES + 1]; real_t weights [MAXEDGES + 1]; int i; - + for (i = 0, k = 0; k <= n; k++) if (f [k] != 0) { @@ -525,10 +525,10 @@ matching_pursuit (mp_t *mp, bool_t full_search, real_t price, range->level, y_state, wfa, domain_pool->model); } - + /* * To compute the approximation error, the corresponding - * linear factors of the linear combination + * linear factors of the linear combination * b = r_0 o_0 + ... + r_(n-1) o_(n-1) + r_n o_'domain' * with orthogonal vectors must be computed with following * formula: @@ -546,7 +546,7 @@ matching_pursuit (mp_t *mp, bool_t full_search, real_t price, a = get_ip_state_state (domain_blocks [v [l]], domain_blocks [domain], range->level, c); - for (k = 0; k < n; k++) + for (k = 0; k < n; k++) a -= ip_domain_ortho_vector [v [l]][k] / norm_ortho_vector [k] * ip_domain_ortho_vector [domain][k]; @@ -554,7 +554,7 @@ matching_pursuit (mp_t *mp, bool_t full_search, real_t price, } norm_ortho_vector [n] = rem_denominator [domain]; ip_image_ortho_vector [n] = rem_numerator [domain]; - + for (k = 0; k <= n; k++) for (l = k + 1; (unsigned) l <= n; l++) r [k] += ip_domain_ortho_vector [v [l]][k] * r [l] @@ -586,40 +586,40 @@ matching_pursuit (mp_t *mp, bool_t full_search, real_t price, } } } - + if (index >= 0) /* found a better approximation */ { if (min_costs < mp->costs) { unsigned k; - + mp->costs = min_costs; mp->err = min_error; mp->matrix_bits = min_matrix_bits; mp->weights_bits = min_weights_bits; - + for (k = 0; k <= n; k++) mp->weight [k] = min_weight [k]; best_n = n + 1; } - + mp->indices [n] = index; mp->into [n] = domain_blocks [index]; used [index] = YES; - /* - * Gram-Schmidt orthogonalization step n + /* + * Gram-Schmidt orthogonalization step n */ orthogonalize (index, n, range->level, min_norm, domain_blocks, c); n++; - } - } + } + } while (n < max_edges && index >= 0); mp->indices [best_n] = NO_EDGE; - + mp->costs = (mp->matrix_bits + mp->weights_bits + additional_bits) * price + mp->err; @@ -641,31 +641,31 @@ orthogonalize (unsigned index, unsigned n, unsigned level, real_t min_norm, * * Side effects: * The remainder values (numerator and denominator) of - * all 'domain_blocks' are updated. + * all 'domain_blocks' are updated. */ { unsigned domain; - + ip_image_ortho_vector [n] = rem_numerator [index]; norm_ortho_vector [n] = rem_denominator [index]; /* - * Compute inner products between all domain images and + * Compute inner products between all domain images and * vector n of the orthogonal basis: - * for (i = 0, ... , wfa->states) + * for (i = 0, ... , wfa->states) * <s_i, o_n> := <s_i, v_n> - * \sum (k = 0, ... , n - 1){ <v_n, o_k> <s_i, o_k> / ||o_k||^2} * Moreover the denominator and numerator parts of the comparative * value are updated. */ - for (domain = 0; domain_blocks [domain] >= 0; domain++) - if (!used [domain]) + for (domain = 0; domain_blocks [domain] >= 0; domain++) + if (!used [domain]) { unsigned k; real_t tmp = get_ip_state_state (domain_blocks [index], domain_blocks [domain], level, c); - - for (k = 0; k < n; k++) + + for (k = 0; k < n; k++) tmp -= ip_domain_ortho_vector [domain][k] / norm_ortho_vector [k] * ip_domain_ortho_vector [index][k]; ip_domain_ortho_vector [domain][n] = tmp; @@ -677,8 +677,8 @@ orthogonalize (unsigned index, unsigned n, unsigned level, real_t min_norm, /* * Exclude vectors with small denominator */ - if (!used [domain]) - if (rem_denominator [domain] / size_of_level (level) < min_norm) + if (!used [domain]) + if (rem_denominator [domain] / size_of_level (level) < min_norm) used [domain] = YES; } } |