**Name**

**flbg_train** Generates a sequence of codebooks from a training set of vectors using LBG (generalized Lloyd) algorithm

**Command Synopsis**

**flbg_train** [-s *CodeBookSize*] [-W *Weight*] [-M] [-i *InitCodeBook*] [-p] [-f *NResCB*] [-g *NResResCB*] [-a *ResCodeBook*] [-b *ResResCodeBook*] *TrainSet* *.* *CodeBook*

-sCodeBookSize: Size of output codebook

-WWeight: Weighting factors for the components of vector (fsignal)

-M : Generate a sequence of codebooks of size equal to a power of two and < = Size

-iInitCodeBook: Initial codebook (fimage)

-p : Print number of iterations for each loop instead of distortion rate results

-fNResCB: Index of first residual codebook (in ResCodeBook)

-gNResResCB: Index of second residual codebook (in ResResCodeBook)

-aResCodeBook: First residual codebook (fimage)

-bResResCodeBook: Second residual codebook (fimage)

TrainSet: Training set of vectors (fimage)

. (screen output) : Quantization mean square error

CodeBook: Output codebook (fimage)

**Function Summary**

void flbg_train (Size , Weight , MultiCB , InitCodeBook , NResCB , NResResCB , ResCodeBook , ResResCodeBook , PrintSNR , TrainSet , MSE , CodeBook )

int *Size ;

Fsignal Weight ;

int *MultiCB ;

Fimage InitCodeBook ;

int *NResCB , *NResResCB ;

Fimage ResCodeBook , ResResCodeBook ;

int *PrintSNR ;

Fimage TrainSet ;

float *MSE ;

Fimage CodeBook ;

**Description**

This module generates a codebook (or a set of codebooks) adapted to a given
training set of vectors using the LBG algorithm.
The training set is read in the *TrainSet* file which must have been created with
the *mk_trainset* module (see *mk_trainset* documentation for
further details). The generated codebook is stored in the *CodeBook*
file. It can be used for example for the vector quantization of images
with the *fvq* module.

The LBG or generalized Lloyd's algorithm is a two step iterative algorithm which is meant to adapt an initial codebook to a given probability density function or a training set of vectors (see [GG92], [LBG80]). We are only considering here the training set version of this algorithm.

If
= {*Y*_{i}}_{1 i I}, is the training set of
*K*-dimensional vectors
*Y*_{i} = (*Y*_{i, k})_{1 k K}, and if
= {*C*_{m}}_{1 m M} is a codebook, then the LBG algorithm
searches a local minimum of

- Compute
*Q*(*Y*_{i}), or more precisely the index of*Q*(*Y*_{i}). - Denote
*P*_{m}= {*i*:*Q*(*Y*_{i}) =*X*_{m}}, and compute for each*m*=Replace for each*Y*_{i}.*m**C*_{m}by and go to step 1.

One has to find an initial codebook to feed the iterative LBG algorithm.
To do this, the *flbg_train* module offers two possiblities :

- The initial codebook can be specified by the user with the -i option.
- The initial codebook can be computed using the ``splitting trick'' (see [LBG80]).

The size of the codebook (*M*) is specified by the -s option.
*CodeBookSize* must be a strictly positive integer.

It is possible to replace the plain m.s.e. by a weighted version of it
using the -W option. *Weight* is a Fsignal file containing the weights
which must be distributed to each component of the vectors.

If the -M option is selected, then all the optimized codebooks of size
equal to a power of two (or a power of two multiplied by the size of
the initial codebook if the -i option has been selected) which are generated
before each new splitting are kept in memory and stored together
with the final codebook of size *CodeBookSize* in the *CodeBook* file.
This means that this file contains not one, but several codebooks
of different sizes. These codebooks are indexed, starting from 0
for the smallest one, up to
log_{2}*CodeBookSize*.
If the -M option is not selected, then only the final size *CodeBookSize*
codebook is stored in *CodeBook* file.

It is possible to generate codebooks which are specially adapted to residual
vector quantization (see *fvq* documentation and [GG92])
with the help of -a, -b, -f and -g options. If the -a option is selected,
then the training set is first quantized using the codebook read in
*ResCodeBook* file, and each vector in the training set is
replaced by the residue of this quantization, i.e. *Y*_{i} is replaced
by
*Y*_{i} - *Q*_{Res}(*Y*_{i}). If the -b option is selected, then this resulting
training set is further quantized using the codebook read in
*ResResCodeBook* file, and each vector in the training set is
replaced by the residue of this quantization, i.e.
*Y*_{i} - *Q*_{Res}(*Y*_{i})
is replaced by
*Y*_{i} - *Q*_{Res}(*Y*_{i}) - *Q*_{ResRes}(*Y*_{i} - *Q*_{Res}(*Y*_{i})).
The resulting training set serves as input for the splitting/LBG loop.
If the -f option is selected, this means that *ResCodeBook*
contains in fact several codebooks of different sizes (i.e. it has
been generated with the -M option). Then *NResCB* is the index
of the codebook to choose in *ResCodeBook* in order to quantize
the training set. The -g option does the equivalent for *ResResCodeBook*.
To be consistent, *ResCodeBook*, *ResResCodeBook* and *CodeBook*
should be generated using the same training set file *TrainSet*.
*NResCB* and *NResResCB* must be of course positive integers.
Notice that the -a, -b, -f and -g options do not modify the LBG
or splitting algorithms at all. They only change the input training set.

The -p option enables to choose the printed information on the
generating process. If selected, it gives the constant rate
(
= log_{2}*M*), the entropic rate, and the signal to noise ratio
for each generated codebook. If not selected, it only gives the number
of iteration in the LBG algorithm for each outer (splitting) loop.

**Example**

In order to generate a set of codebooks of size 1, 2, 2^{2}, ..., 2^{8},
adapted to the training set contained in the file *TrainSet* and
put them in the file *CodeBook*, run

**flb_train** -s 256 -M *TrainSet* *CodeBook*

In order to generate a set of codebooks of size 1, 2, 2^{2}, ..., 2^{8},
for the residual vector quantization after quantization with the
codebook with index 9 in *CodeBook* file (i.e. the codebook with size
256), and put them in the file *ResCodeBook*, run

**flb_train** -s 256 -M -a *CodeBook* -f 9 *TrainSet*
*ResCodeBook*

In order to generate a set of codebooks of size 1, 2, 2^{2}, ..., 2^{8}
and 347 for the residual vector quantization after quantization with the
codebook with index 9 in *CodeBook* file (i.e. the codebook with size
256) and the codebook with index 7 in *ResCodeBook* file
(i.e. the codebook with size 64), and put them in the file
*ResResCodeBook*, run

**flb_train** -s 347 -M -a *CodeBook* -f 9 *TrainSet*
-b *ResCodeBook* -g 7 *TrainSet* *ResResCodeBook*

**See Also**

**Version 2.00**

Last Modification date : Thu Nov 29 20:23:57 2001

**Author**

Jean-Pierre D'Ales