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

Data Structures
struct	cell_s
	In the ELBG jargon, a cell is the set of points that are closest to a codebook entry. More...

struct	ELBGContext
	ELBG internal data. More...

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

#define	BIG_PRIME 433494437LL

#define	ALLOCATE_IF_NECESSARY(field, new_elements, multiplicator)

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 (ELBGContext elbg, int centroid, cell *cells)

static int	get_closest_codebook (ELBGContext *elbg, int index)

static int	get_high_utility_cell (ELBGContext *elbg)

static int	simple_lbg (ELBGContext 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 (ELBGContext elbg, int huc, int newcentroid_i, int *newcentroid_p)

static void	shift_codebook (ELBGContext elbg, int indexes, int *newcentroid[3])
	Add the points in the low utility cell to its closest cell. More...

static void	evaluate_utility_inc (ELBGContext *elbg)

static void	update_utility_and_n_cb (ELBGContext *elbg, int idx, int newutility)

static void	try_shift_candidate (ELBGContext *elbg, int idx[3])
	Evaluate if a shift lower the error. More...

static void	do_shiftings (ELBGContext *elbg)
	Implementation of the ELBG block. More...

static void	do_elbg (ELBGContext av_restrict elbg, int points, int numpoints, int max_steps)

static void	init_elbg (ELBGContext av_restrict elbg, int points, int *temp_points, int numpoints, int max_steps)
	Initialize the codebook vector for the elbg algorithm. More...

int	avpriv_elbg_do (ELBGContext *elbgp, int points, int dim, int numpoints, int codebook, int num_cb, int max_steps, int closest_cb, AVLFG *rand_state, uintptr_t flags)
	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...

av_cold void	avpriv_elbg_free (ELBGContext **elbgp)
	Free an ELBGContext and reset the pointer to it. More...

Detailed Description

Codebook Generator using the ELBG algorithm

Definition in file elbg.c.

Macro Definition Documentation

◆ DELTA_ERR_MAX

#define DELTA_ERR_MAX 0.1

Precision of the ELBG algorithm (as percentage error)

Definition at line 33 of file elbg.c.

◆ BIG_PRIME

#define BIG_PRIME 433494437LL

Definition at line 430 of file elbg.c.

◆ ALLOCATE_IF_NECESSARY

#define ALLOCATE_IF_NECESSARY	(	field,
		new_elements,
		multiplicator
	)

Value:

    if (elbg->field ## _allocated < new_elements) {                          \
        av_freep(&elbg->field);                                              \
        elbg->field = av_malloc_array(new_elements,                          \
                                      multiplicator * sizeof(*elbg->field)); \
        if (!elbg->field) {                                                  \
            elbg->field ## _allocated = 0;                                   \
            return AVERROR(ENOMEM);                                          \
        }                                                                    \
        elbg->field ## _allocated = new_elements;                            \
    }

Function Documentation

◆ distance_limited()

static int distance_limited	(	int *	a,
		int *	b,
		int	dim,
		int	limit
	)

inlinestatic

Definition at line 74 of file elbg.c.

Referenced by do_elbg(), eval_error_cell(), get_closest_codebook(), shift_codebook(), and simple_lbg().

◆ vect_division()

static void vect_division	(	int *	res,
		int *	vect,
		int	div,
		int	dim
	)

inlinestatic

Definition at line 89 of file elbg.c.

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

◆ eval_error_cell()

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

static

Definition at line 100 of file elbg.c.

Referenced by try_shift_candidate().

◆ get_closest_codebook()

static int get_closest_codebook	(	ELBGContext *	elbg,
		int	index
	)

static

Definition at line 113 of file elbg.c.

Referenced by do_shiftings().

◆ get_high_utility_cell()

static int get_high_utility_cell ( ELBGContext * elbg )

static

Definition at line 128 of file elbg.c.

Referenced by do_shiftings().

◆ simple_lbg()

static int simple_lbg	(	ELBGContext *	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 153 of file elbg.c.

Referenced by try_shift_candidate().

◆ get_new_centroids()

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

static

Definition at line 197 of file elbg.c.

Referenced by try_shift_candidate().

◆ shift_codebook()

static void shift_codebook	(	ELBGContext *	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

elbg	Internal elbg data
indexes	{luc, huc, cluc}
newcentroid	A vector with the position of the new centroids

Definition at line 233 of file elbg.c.

Referenced by try_shift_candidate().

◆ evaluate_utility_inc()

static void evaluate_utility_inc ( ELBGContext * elbg )

static

Definition at line 261 of file elbg.c.

Referenced by do_shiftings(), and try_shift_candidate().

◆ update_utility_and_n_cb()

static void update_utility_and_n_cb	(	ELBGContext *	elbg,
		int	idx,
		int	newutility
	)

static

Definition at line 273 of file elbg.c.

Referenced by try_shift_candidate().

◆ try_shift_candidate()

static void try_shift_candidate	(	ELBGContext *	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

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

Definition at line 289 of file elbg.c.

Referenced by do_shiftings().

◆ do_shiftings()

static void do_shiftings ( ELBGContext * elbg )

static

Implementation of the ELBG block.

Definition at line 345 of file elbg.c.

Referenced by do_elbg().

◆ do_elbg()

static void do_elbg	(	ELBGContext *av_restrict	elbg,
		int *	points,
		int	numpoints,
		int	max_steps
	)

static

Definition at line 364 of file elbg.c.

Referenced by avpriv_elbg_do(), and init_elbg().

◆ init_elbg()

static void init_elbg	(	ELBGContext *av_restrict	elbg,
		int *	points,
		int *	temp_points,
		int	numpoints,
		int	max_steps
	)

static

Initialize the codebook vector for the elbg algorithm.

If numpoints <= 24 * num_cb this function fills codebook with random numbers. If not, it calls do_elbg for a (smaller) random sample of the points in points.

Definition at line 438 of file elbg.c.

Referenced by avpriv_elbg_do().

◆ avpriv_elbg_do()

int avpriv_elbg_do	(	struct ELBGContext **	ctx,
		int *	points,
		int	dim,
		int	numpoints,
		int *	codebook,
		int	num_cb,
		int	num_steps,
		int *	closest_cb,
		AVLFG *	rand_state,
		uintptr_t	flags
	)

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

ctx	A pointer to a pointer to an already allocated ELBGContext or a pointer to NULL. In the latter case, this function will allocate an ELBGContext and put a pointer to it in `*ctx`.
points	Input points.
dim	Dimension of the points.
numpoints	Num of points in **points.
codebook	Pointer to the output codebook. Must be allocated.
num_cb	Number of points in the codebook.
num_steps	The maximum number of steps. One step is already a good compromise between time and quality.
closest_cb	Return the closest codebook to each point. Must be allocated.
rand_state	A random number generator state. Should be already initialized by av_lfg_init().
flags	Currently unused; must be set to 0.

Returns: < 0 in case of error, 0 otherwise

Definition at line 462 of file elbg.c.

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

◆ avpriv_elbg_free()

av_cold void avpriv_elbg_free ( ELBGContext ** elbgp )

Free an ELBGContext and reset the pointer to it.

Definition at line 515 of file elbg.c.

Referenced by a64multi_close_encoder(), cinepak_encode_end(), encode_end(), roq_encode_end(), and uninit().

Data Structures

Macros

Functions

Detailed Description

Macro Definition Documentation

◆ DELTA_ERR_MAX

◆ BIG_PRIME

◆ ALLOCATE_IF_NECESSARY

Function Documentation

◆ distance_limited()

◆ vect_division()

◆ eval_error_cell()

◆ get_closest_codebook()

◆ get_high_utility_cell()

◆ simple_lbg()

◆ get_new_centroids()

◆ shift_codebook()

◆ evaluate_utility_inc()

◆ update_utility_and_n_cb()

◆ try_shift_candidate()

◆ do_shiftings()

◆ do_elbg()

◆ init_elbg()

◆ avpriv_elbg_do()

◆ avpriv_elbg_free()