FFmpeg
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros Groups Pages
Data Structures | Macros | Functions
elbg.c File Reference

Codebook Generator using the ELBG algorithm. More...

#include <string.h>
#include "libavutil/avassert.h"
#include "libavutil/common.h"
#include "libavutil/lfg.h"
#include "elbg.h"
#include "avcodec.h"

Go to the source code of this file.

Data Structures

struct  cell
 In the ELBG jargon, a cell is the set of points that are closest to a codebook entry. More...
 
struct  elbg_data
 ELBG internal data. More...
 

Macros

#define DELTA_ERR_MAX   0.1
 Precision of the ELBG algorithm (as percentage error) More...
 
#define BIG_PRIME   433494437LL
 

Functions

static int distance_limited (int *a, int *b, int dim, int limit)
 
static void vect_division (int *res, int *vect, int div, int dim)
 
static int eval_error_cell (elbg_data *elbg, int *centroid, cell *cells)
 
static int get_closest_codebook (elbg_data *elbg, int index)
 
static int get_high_utility_cell (elbg_data *elbg)
 
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. More...
 
static void get_new_centroids (elbg_data *elbg, int huc, int *newcentroid_i, int *newcentroid_p)
 
static void shift_codebook (elbg_data *elbg, int *indexes, int *newcentroid[3])
 Add the points in the low utility cell to its closest cell. More...
 
static void evaluate_utility_inc (elbg_data *elbg)
 
static void update_utility_and_n_cb (elbg_data *elbg, int idx, int newutility)
 
static void try_shift_candidate (elbg_data *elbg, int idx[3])
 Evaluate if a shift lower the error. More...
 
static void do_shiftings (elbg_data *elbg)
 Implementation of the ELBG block. More...
 
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. More...
 
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 can be found in http://citeseer.ist.psu.edu/patan01enhanced.html . More...
 

Detailed Description

Codebook Generator using the ELBG algorithm.

Definition in file elbg.c.

Macro Definition Documentation

#define DELTA_ERR_MAX   0.1

Precision of the ELBG algorithm (as percentage error)

Definition at line 34 of file elbg.c.

Referenced by avpriv_do_elbg().

#define BIG_PRIME   433494437LL

Definition at line 335 of file elbg.c.

Referenced by avpriv_init_elbg().

Function Documentation

static int distance_limited ( int *  a,
int *  b,
int  dim,
int  limit 
)
inlinestatic
static void vect_division ( int *  res,
int *  vect,
int  div,
int  dim 
)
inlinestatic

Definition at line 73 of file elbg.c.

Referenced by avpriv_do_elbg(), simple_lbg(), and try_shift_candidate().

static int eval_error_cell ( elbg_data elbg,
int *  centroid,
cell cells 
)
static

Definition at line 84 of file elbg.c.

Referenced by try_shift_candidate().

static int get_closest_codebook ( elbg_data elbg,
int  index 
)
static

Definition at line 93 of file elbg.c.

Referenced by do_shiftings().

static int get_high_utility_cell ( elbg_data elbg)
static

Definition at line 107 of file elbg.c.

Referenced by do_shiftings().

static int simple_lbg ( elbg_data elbg,
int  dim,
int *  centroid[3],
int  newutility[3],
int *  points,
cell cells 
)
static

Implementation of the simple LBG algorithm for just two codebooks.

Definition at line 132 of file elbg.c.

Referenced by try_shift_candidate().

static void get_new_centroids ( elbg_data elbg,
int  huc,
int *  newcentroid_i,
int *  newcentroid_p 
)
static

Definition at line 173 of file elbg.c.

Referenced by try_shift_candidate().

static void shift_codebook ( elbg_data elbg,
int *  indexes,
int *  newcentroid[3] 
)
static

Add the points in the low utility cell to its closest cell.

Split the high utility cell, putting the separated points in the (now empty) low utility cell.

Parameters
elbgInternal elbg data
indexes{luc, huc, cluc}
newcentroidA vector with the position of the new centroids

Definition at line 209 of file elbg.c.

Referenced by try_shift_candidate().

static void evaluate_utility_inc ( elbg_data elbg)
static

Definition at line 237 of file elbg.c.

Referenced by do_shiftings(), and try_shift_candidate().

static void update_utility_and_n_cb ( elbg_data elbg,
int  idx,
int  newutility 
)
static

Definition at line 250 of file elbg.c.

Referenced by try_shift_candidate().

static void try_shift_candidate ( elbg_data elbg,
int  idx[3] 
)
static

Evaluate if a shift lower the error.

If it does, call shift_codebooks and update elbg->error, elbg->utility and elbg->nearest_cb.

Parameters
elbgInternal elbg data
idx{luc (low utility cell, huc (high utility cell), cluc (closest cell to low utility cell)}

Definition at line 266 of file elbg.c.

Referenced by do_shiftings().

static void do_shiftings ( elbg_data elbg)
static

Implementation of the ELBG block.

Definition at line 316 of file elbg.c.

Referenced by avpriv_do_elbg().

int avpriv_init_elbg ( int *  points,
int  dim,
int  numpoints,
int *  codebook,
int  numCB,
int  num_steps,
int *  closest_cb,
AVLFG rand_state 
)

Initialize the **codebook vector for the elbg algorithm.

If you have already a codebook and you want to refine it, you shouldn't call this function. If numpoints < 8*numCB this function fills **codebook with random numbers. If not, it calls avpriv_do_elbg for a (smaller) random sample of the points in **points. Get the same parameters as avpriv_do_elbg.

Returns
< 0 in case of error, 0 otherwise

Definition at line 337 of file elbg.c.

Referenced by a64multi_encode_frame(), avpriv_init_elbg(), encode_frame(), filter_frame(), generate_codebook(), and quantize().

int avpriv_do_elbg ( int *  points,
int  dim,
int  numpoints,
int *  codebook,
int  numCB,
int  num_steps,
int *  closest_cb,
AVLFG rand_state 
)

Implementation of the Enhanced LBG Algorithm Based on the paper "Neural Networks 14:1219-1237" that can be found in http://citeseer.ist.psu.edu/patan01enhanced.html .

Parameters
pointsInput points.
dimDimension of the points.
numpointsNum of points in **points.
codebookPointer to the output codebook. Must be allocated.
numCBNumber of points in the codebook.
num_stepsThe maximum number of steps. One step is already a good compromise between time and quality.
closest_cbReturn the closest codebook to each point. Must be allocated.
rand_stateA random number generator state. Should be already initialized by av_lfg_init().
Returns
< 0 in case of error, 0 otherwise

Definition at line 371 of file elbg.c.

Referenced by a64multi_encode_frame(), avpriv_init_elbg(), encode_frame(), filter_frame(), generate_codebook(), and quantize().