vqdesign.3

speech signal process tools

.\" Copyright (c) 1987 Entropic Speech, Inc.; All rights reserved
.\" @(#)vqdesign.3	1.8 03 Jan 1993 ESI
.TH VQDESIGN 3\-ESPSsp 03 Jan 1993
.ds ]W "\fI\s+4\ze\h'0.05'e\s-4\v'-0.4m'\fP\(*p\v'0.4m'\ Entropic Speech, Inc.
.SH NAME
vqdesign \- design full-search vector quantization codebook
.SH SYNOPSIS
.ft B
.nf
#include <esps/vq.h>
#include <stdio.h>
.ta .8i
int
vqdesign	(histrm, hdetail, data, len, dim, cbk, enc, init, split_crit, 
	get_chunk, vec_to_cdwd, distort, split, checkpoint, max_iter)
FILE 		*histrm;
int 		hdetail;
float		**data;
long		len;
long		dim;
struct		vqcbk *cbk;
int 		init;
long		*enc;
int 		split_crit;
long		(*get_chunk)();
int 		(*vec_to_cdwd)();
double		(*distort)();
int		(*split)();
int		(*checkpoint)();
int		max_iter;
.fi
.ft
.SH GENERAL DESCRIPTION
.I vqdesign
is a fairly-general routine that uses the Linde-Buzo-Gray (LBG)
(generalized Lloyd) algorithm to design a full-search vector
quantization codebooks based on a training sequence of feature vectors.
.I vqdesign
can be used whether or not the training data fits entirely in 
memory.  Provided that certain conditions are satisfied, 
.I vqdesign
can be used with arbitrary distortion measures and arbitrary
codebook-splitting algorithms.  
.PP
The main assumption that restricts the
application of 
.I vqdesign
concerns the computation of a cluster centroid.  It is assumed that a
cluster centroid is a function (\fIvec_to_cdwd\fP) of the feature vector
that results from averaging, component by component, all of the feature
vectors in the cluster.  This assumption holds for a large class of
distortion measures, including mean-square error, weighted mean-square
error, and Itakura-Saito.  It holds for the class of minimum
relative-entropy distortion measures discussed in [1], of which the
Itakura-Saito is a special case.  
.PP
The training data is passed to 
.I vqdesign
through the parameter 
.I data,
which points to
.I len
feature vectors of dimension
.I dim.
The array 
.I data
may or may not contain the entire set of training data.  If it 
does not (for example, when the training data does not fit in memory),
.I vqdesign
uses the function
.I get_chunk
to update 
.I data
whenever a chunk of training data is needed.  If 
.I get_chunk
is NULL, then 
.I data
is assumed to contain the entire training sequence.  
.PP
The codebook designed by 
.I vqdesign
is passed back to the calling program through the parameter 
.I cbk.
If the codebook passed through 
.I cbk
is not empty when 
.I vqdesign
is called, then this codebook is used as an initial codebook 
by 
.I vqdesign.  
In this case, the input codebook may or may not
be re-clustered before splitting, depending on the value 
of 
.I init
(see below).  
.PP
The parameter 
.I enc
is used by 
.I vqdesign
to pass back the indices of the closest codeword corresponding to 
the feature vectors passed via 
.I data.
If 
.I data
holds the full training sequence, then , after 
.I vqdesign 
returns, \fIenc\fP[\fIi\fP] is the index of the final codeword closest
to \fIdata\fP[\fIi\fP]; that is,
\fIcbk\->codeword\fP[\fIenc\fP[\fIi\fP]] is the closest codeword to
\fIdata\fP[\fIi\fP].  Actually, 
.I enc
is used throughout the design process to hold the indices of the 
closest codewords to the feature vectors in 
.I data.
Thus, provided that the pointer \fIenc\fP passed to 
.I vqdesign
is in the scope of 
.I get_chunk,
the current contents of 
.I enc
could be copied elsewhere whenever
.I get_chunk
is called.  
This may be useful when 
.I data
does not hold the full training sequence, i.e., if 
.I get_chunk
is used to step through the training sequence.  
.PP
Besides 
.I get_chunk,
several other function pointers are passed to 
.I vqdesign,
namely
.I vec_to_cdwd,
.I distort,
.I split,
and
.I checkpoint. 
.PP
The function
.I vec_to_cdwd
transforms a feature vector into a codeword; if it is NULL, then 
no transformation is necessary.  
.PP
The function 
.I distort
computes a distortion measure between a feature vector and a codeword;
if it is NULL a mean-square-error distortion function is used by 
default.  
.PP
The function
.I split
is used to split a codeword whenever an additional codeword 
is needed, either because an empty cell has been found or because
the codebook is being enlarged.  Which codeword to split is 
determined by
.I split_crit.
The 
.I split
function performs the actual splitting operation.  If 
.I split
is NULL, a "generic split" routine is used by default.  This generic
routine splits each codeword by adding or subtracting a random amount
from each codeword element.  The amount is uniformly distributed over 1%
of the particular codeword element, and the algorithm is used both to
compute a new codeword from an existing as well as to modify the
existing one.  
.PP
The function
.I checkpoint
is called by
.I vqdesign
periodically to allow the current codebook to be written to 
a checkpoint file.  It is called after each adjustment of the 
cluster centroids (i.e., after each pass through the training
sequence); it is also called before the current codebook is 
to be enlarged (i.e., after the design has converged at a given 
size).  
.PP
The parameter 
.I max_iter
specifies the maximum number of iterations for clustering at 
any given level.  
.PP
.I
vqdesign
writes history and debugging information to the stream 
.I histrm.
The amount of information written to 
.I histrm 
increases as the value of 
.I hdetail
increases from 0.  If 
.I hdetail
is zero, only fatal error messages are written.  No information is
written if 
.I histrm
is NULL.
.PP
.I vqdesign
returns one of the following integer status values, which are 
defined in <esps/vq.h>:
.nf
.ta .25i 1.5i

	0	normal exit, codebook designed OK;
	VQ_NOCONVG	convergence failed
	VQ_GC_ERR	error in \fIget_chunk\fP
	VQ_VECWD_ERR	error in \fIvec_to_cdwd\fP
	VQ_DIST_ERR	error in \fIdistort\fP
	VQ_SPLIT_ERR	error in \fIsplit\fP
	VQ_INPUT_ERR	inconsistency or other problem with input parameters;
.fi
.PP
The function parameters \fIvec_to_cdwd, split, \fRand\fI checkpoint\fR
should really be of type \fBvoid\fP.  Type \fBint\fP is used owing to
compiler bugs on certain machines.  
.PP
For more information, see the section "DETAILED DESCRIPTION".  
.SH PARAMETERS
.TP 
.I "histrm, hdetail"
.I Histrm 
points to an output stream used by 
.I vqdesign
to write out history and debugging information.  
The amount of information written to 
.I histrm 
increases as the value of 
.I hdetail
increases from 0, as described in the following (information 
written when \fIhdetail == n\fP includes all information 
written when \fIhdetail \fP< \fIn\fP):
.IP
\fIhdetail == \fPNULL
.IP
No information is written.
.IP
\fIhdetail == \fP0
.IP
Only fatal error messages are written.  
.IP
\fIhdetail == \fP1
.IP
Each time the codebook has converged at a given current size or after
empty cells have been filled, the following are written:  current
date and time, current codebook size, size of training sequence for
current codebook, total number of clustering iterations so far,
average distortion of the current codebook, the total number of
empty cells found so far, and the entropy of the current codebook
(probability of each cluster computed as proportional to the cluster
size).
.IP
\fIhdetail == \fP2
.IP
Each time the full training sequence is encoded with respect to the
current codebook, the average distortion is written.  Whenever 
empty cells are found, the identities of the empty cell and the 
cell split to replace the empty cell are written.  
.IP
\fIhdetail == \fP3
Each time the information for \fIhdetail == \fP1 is written, 
so are the following:  the size of each cluster in the last pass over
the training sequence, the average distortion of each cluster, and
the current set of codewords (transformed cluster centroids).  
The current set of codewords is also written each time the 
codebook is enlarged.  Whenever an empty cell has been discarded 
(and another cell split), the foregoing information is also written.    
.IP
\fIhdetail == \fP4
.IP
The information described for \fIhdetail == \fP1 and \fIhdetail == \fP3
is written again after each cluster iteration, i.e., each time the
training sequence has been encoded and the codebook adjusted.  
.IP
\fIhdetail == \fP5
.IP
The number of training vectors resulting from each call to 
.I get_chunk
is written.
.IP
\fIhdetail == \fP6
.IP
Each time a feature vector is encoded with respect to the current
codebook, the following are written out: the feature vector, the
index of the closest codeword, and the distortion with respect
to that codeword.
.TP
.I "data, len, dim"
.I vqdesign
interprets 
.I data
as a pointer to a 
.IR len\- row
by
.IR dim\- column
matrix of floats.  Space for this matrix must be allocated by 
the calling program \- such a pointer can be assigned by
means of 
.I f_mat_alloc
(3\-ESPSu).  With this interpretation, the pointers
\fIdata\fR[0]...\fIdata\fR[\fIlen\fR\-1] each points to a "row"
containing a feature vector of dimension 
.I dim.  
Thus, \fIdata\fR[\fIi\fR][\fIj\fR] is
the \fIj\fRth element of the \fIi\fRth feature vector.  
.TP
.I cbk
This parameter is a pointer to a codebook structure of type 
.I vqcbk,
which is defined in <esps/vq.h>.  The following structure 
definition contains the subset of the definition in <esps/vq.h> that
is relevant to 
.I vqdesign\fR:
.nf
.ta 1.75i

\fBstruct\fP vqcbk {
\fBdouble\fP *conv_ratio;	\fI/*fractional distortion convergence threshold*/\fP
\fBdouble\fP *final_dist;	\fI/*average distortion of current codebook*/\fP
\fBfloat\fP **codebook;	\fI/*codeword matrix; codeword[j] points to jth codeword*/\fP
\fBfloat\fP *clusterdist;	\fI/*distortion of the cluster corresponding 
				    to each codeword*/\fP
\fBlong\fP *clustersize;	\fI/*size of the cluster corresponding to each codeword*/\fP
\fBlong\fP *train_length;	\fI/*length of training sequence used*/\fP
\fBlong\fP *design_size;	\fI/*design goal for number of codewords*/\fP
\fBlong\fP *current_size;	\fI/*current number of codewords in codebook*/\fP
\fBlong\fP *dimen;	\fI/*dimension of codewords*/\fP
\fBlong\fP *num_iter;	\fI/*total number of cluster iterations*/\fP
\fBshort\fP *cbk_type; 	\fI/*codebook type, e.g, RC_VQCBK;
				  see vq_cbk_types[] in <esps/header.h>*/\fP
\fBshort\fP *dist_type;	\fI/*distortion type, e.g, MSE; see
				  dist_types[] in <esps/header.h>*/ \fP
\fBshort\fP *cbk_struct;	\fI/*codebook structure, e.g., FULL_SEARCH;
				  see cbk_structs[] in <esps/header.h>*/\fP
};

.fi
.I cbk\->codebook
is interpreted as a pointer to a matrix of floats containing
.I cbk\->design_size
rows of 
.I cbk\->dimen
columns each.  Prior to calling 
.I vqdesign,
the calling program must set the values of 
.I *cbk\->design_size,
.I *cbk\->current_size,
.I *cbk\->dimen,
.I cbk\->codebook,
and
.I *cbk\->conv_ratio.  
It should also set 
.I *cbk\->dist_type,
although this does not affect the operation of 
.I vqdesign.  
As in the case of 
.I data,
the pointer 
.I cbk\->codebook 
can be assigned by means of 
.I f_mat_alloc
(3\-ESPSu).  In most cases, the value of 
.I cbk\->dimen 
will be the same as that of the 
.I vqdesign
parameter 
.I dim 
(dimension of feature vectors), but that is not necessary 
provided that the functions 
.I vec_to_cdwd
and
.I distort
are defined appropriately. 
.IP
If 
.I *cbk\->current_size 
is not zero, this number of rows from 
.I cbk\->codebook 
are considered to define an initial codebook.  
.IP
Before
.I vqdesign
returns, it sets the values of 
.I "*cbk\->train_length, *cbk\->current_size, *cbk\->final_dist,"
and
.I *cbk\->num_iter.  
(
.I *cbk\->num_iter
is the total number of clustering iterations since the start of the 
codebook design.)  
.I vqdesign
fills the first 
.I *cbk\->current_size
rows of 
.I cbk\->codebook 
with the codewords resulting from the design algorithm.  (Usually, 
.I "*cbk\->current_size = *cbk\->design_size"
when 
.I vqdesign 
terminates.)  Also, the values of 
\fIcbk\->clustersize\fR[\fIj\fR] and \fIcbk\->clusterdist\fR[\fIj\fR]
are set to the size and average distortion of the final cluster
corresponding to \fIcbk\->codebook\fR[\fIj\fR] (this codeword is the 
transformed centroid of the cluster).  
.IP
The value
.I *cbk\->cbk_struct 
is set to FULL_SEARCH by
.I vqdesign.  
The values of 
.I *cbk\->dist_type
and
.I *cbk\->cbk_type
are not changed by 
.I vqdesign.
.TP
.I enc
This is a pointer to 
.I len
\fBlong\fP values that are used by 
.I vqdesign
to pass back the index of the closest codeword to the corresponding
feature vector in \fIdata\fP[\fIi\fP].  For more information, see
"GENERAL DESCRIPTION".  
.TP 
.I init
This parameter determines whether or not an initial codebook is 
clustered before being split, according to the following values which
are defined in <esps/vq.h>:
.nf
.ta .25i 1.5i

	INIT_CLUSTER	cluster initial codebook before splitting
	INIT_NOCLUSTER	do not cluster initial codebook before splitting