vqdesign.3

speech signal process tools

.fi
The value of 
.I init
is ignored if 
.I vqdesign 
is called with
\fIcbk\->current_size == \fR0.  
.TP
.I split_crit
Whenever a codeword must be split, either to enlarge the codebook 
or to replace an empty cell, 
.I split_crit
determines which codeword is split.  It has the following possible
values, which are defined in <esps/vq.h>:  
.nf
.ta .25i 1.5i

	SPLIT_POP	split cluster with largest population
	SPLIT_DIST	split cluster with largest average distortion

.fi
If more than one codeword is to be split the criterion is applied 
repeatedly.  
.TP
.I get_chunk
This is a pointer to a function that updates 
.I data
with the next "chunk" of training data.  Such functions must 
have the following synopsis:
.nf
.ft B

long
get_chunk(data, len, dim, num_prev, error)
float **data;
long len;
long dim;
long num_prev;
int *error;
.ft

.fi
As in 
.I vqdesign,
.I data
is interpreted as a pointer to a 
.IR len\- row
by
.IR dim\- column
matrix of floats.  
.I Get_chunk
fills 
.I data
with up to 
.I len 
new feature vectors of dimension 
.I dim.  
.I Get_chunk
must return the number of new feature vectors that are in 
.I data, 
and it must return the value 0 when the training-sequence is exhausted.  If 
.I get_chunk
is called with \fInum_prev\fR == 0, it must start (perhaps again) from 
the beginning of the training sequence.  When 
.I get_chunk 
is called from 
.I vqdesign, 
the parameter 
.I num_prev 
will always be set equal to the total number of vectors from the 
training sequence that have been supplied by previous calls to 
.I get_chunk 
ever since it was called with \fInum_prev\fR == 0.  
.I Get_chunk 
returns, in \fIerror\fP, a return status that should be set to 
values other than 0 whenever an error is detected.  For normal 
returns, \fI*error\fR == 0.  
.I vqdesign 
sets \f*error\fR == 0 before calling 
.I get_chunk.  
.TP
.I vec_to_cdwd
This is a pointer to a function that transforms a feature vector 
into a codeword.  For many applications, no such transformation is
needed \- a feature vector (e.g., the centroid of a cluster of 
feature vectors) can be used as a codeword without transformation.  
In such cases, 
.I vec_to_cdwd
is set to NULL and the transformation is bypassed.  In other
applications, a transformation is needed \- for example, in 
some applications of vector quantization to speech coding, the feature
vector components are autocorrelations while the codeword components 
are filter coefficients, so a transformation is needed.  If it is 
supplied, the function 
.I vec_to_cdwd 
must have the following synopsis:
.nf
.ft B

int
vec_to_cdwd(fea_vector, vec_dim, codeword, cdwd_dim, error)
float *fea_vector;
long vec_dim;
float *codeword;
long cdwd_dim;
int *error;
.ft

.fi
The feature vector to be transformed is passed to 
.I vec_to_cdwd 
via the parameter
.I fea_vector,
and the resulting codeword is passed back via
.I codeword.
The dimensions of 
.I fea_vector
and
.I codeword
are given respectively
by 
.I vec_dim
and
.I cdwd_dim.
.I Vec_to_cdwd
returns, in \fIerror\fP, a return status that should be set to
values other than 0 whenever an error is detected.  For normal 
returns, \fIerror\fR == 0.   
.I vqdesign 
sets \f*error\fR == 0 before calling 
.I vec_to_cdwd.  
.IP
If \fIget_chunk \fP== NULL, then 
.I data
is assumed to hold the entire training sequence.  
.TP
.I distort
This is a pointer to a function that computes a distortion measure
between a feature vector and a codeword.  Such functions must have the
following synopsis:  
.nf
.ft B

double
distort(fea_vector, vec_dim, codeword, cdwd_dim, error)
float *fea_vector;
long vec_dim;
float *codeword;
long cdwd_dim;
int *error;
.ft

.fi
.I Distort
computes the distortion between the feature vector 
.I fea_vector
and the codeword
.I codeword.  
The resulting distortion value is the function's return value.
The dimensions of 
.I fea_vector
and
.I codeword
are given respectively
by 
.I vec_dim
and
.I cdwd_dim.  
.I Distort
also returns, in \fIerror\fP, a return status that should be set to
values other than 0 whenever an error is detected.  For normal returns,
\fIerror\fR == 0.  
.I vqdesign 
sets \f*error\fR == 0 before calling 
.I distort.  
.IP
If \fIdistort\fP == NULL, then a mean-square-error distortion 
function is used, but this requires that 
.I dim
and
.I cbk\->dimen
be the same.  
.TP
.I split
This is a pointer to a function that splits a codeword.  Such functions
must have the following synopsis:  
.nf
.ft B

int
split(cdwd_dest, cdwd_src, cdwd_size)
float	*cdwd_dest;	
float	cdwd_src;	
long	cdwd_size;
.ft

.fi
.I Cdwd_src
points to 
.I cdwd_size
floats containing a codeword that is to be split, and 
.I cdwd_dest
points to 
.I cdwd_size
floats in which 
.I split
writes the new codeword.  
.I Split
may also modify the source codeword
.I cdwd_src.  
.IP
If \fIsplit \fP==NULL, a generic split routine is used; this generic
routine modifies both
.I cdwd_dest
and
.I cdwd_src.
For details about the generic split algorithm, see "GENERAL
DESCRIPTION".
.TP
.I checkpoint
This is a pointer to a function that can be used to write the 
current codebook out to a checkpoint file or to calculate 
and output some intermediate information.  (At least that's the 
motivation; in principle, 
.I checkpoint 
can do anything with or to the current codebook.)  It must have the
following synopsis:
.nf
.ft B

int
checkpoint(cdbk, chk_type)
struct vqcbk *cdbk;
int chk_type;
.ft

.fi
.I Cdbk
is a pointer to the current codebook.  Note that unpredictable things will
happen if 
.I checkpoint
modifies the current codebook.  
.IP
.I Chk_type
is set by 
.I vqdesign
to indicate at which design stage the call to 
.I checkpoint 
is being made.  If \fIchk_type\fP == CHK_ENCODE, then the call to 
.I checkpoint
occured after the codewords were adjusted following a pass through
the training sequence.  If \fIchk_type\fP == SPLIT, the call to 
.I checkpoint
occured after the codebook converged at a given size and before it
is enlarged by means of a call to 
.I split.  
(There are many more calls with \fIchk_type\fP == CHK_ENCODE than 
with \fIchk_type\fP == CHK_SPLIT.)  For an example, see the source
for 
.I vqdes
(1\-ESPS), where a 
.I checkpoint
routine does nothing when \fIchk_type\fP == CHK_ENCODE and writes 
out the current codebook to a checkpoint file when \fIchk_type\fP ==
CHK_SPLIT.  
.IP
If \fIcheckpoint\fR == NULL, then no checkpoint-related action is 
taken.  
.TP
.I max_iter
This parameter determines the maximum number of iterations allowed
at any one clustering level.  If the number is exceeded, a message
is written to the history output and 
.I vqdesign
exist with return value VQ_NOCONVG.  
.SH DETAILED DESCRIPTION
.PP
If 
.I vqdesign
is called with \fIcbk\->current_size\fR !=0, 
it interprets the first \fIcbk\->current_size\fR rows of 
\fIcbk\->codebook\fR to be an initial codebook.  Alternatively, 
if
.I vqdesign 
is called with \fIcbk\->current_size\fR == 0, it designs a rate 0 
initial codebook by finding the centroid of the entire training
sequence.  It does this by averaging each component of the feature 
vectors in the training sequence and then transforming the resulting
vector to a codeword by means of 
.I vec_to_cdwd.  
.PP
As mentioned earlier, 
.I vqdesign
interprets 
.I data
as a pointer to a 
.IR len\- row
by
.IR dim\- column
matrix of floats, and each row of 
.I data
is one feature vector from the training sequence.  
If \fIget_chunk\fR == NULL, 
.I vqdesign
assumes that there are only 
.I len 
feature vectors in the training sequence, and that they are all 
stored in 
.I data.  
Otherwise, 
.I vqdesign
uses the function
.I get_chunk 
to step through the training sequence.  In this case (\fIget_chunk\fR !=
NULL), \fIvqdesign\fR does not assume that any of the training 
sequence is stored in 
.I data
when 
.I vqdesign
is called.  (It does, however, assume that the space for \fIdata\fR 
was allocated properly in the calling program.)
.PP
If 
.I vqdesign
is called with an initial codebook (\fIcbk\->current_size\fR != 0), 
and if \fIinit\fR == INIT_CLUSTER, 
.I vqdesign 
will "cluster" the initial codebook before proceeding.  This works as
follows:  The entire training sequence is encoded with respect to the
codebook; this determines a set of codeword clusters (a codeword cluster
comprises all of the feature vectors that are closest to a particular
codeword), and it determines the average distortion of all cluster 
members with respect to the corresponding codeword.  (The function 
.I distort
is used to compute the distortion between a feature vector 
and a codeword.)  Next, the 
centroid of each codeword cluster is computed by averaging the feature
vectors in the cluster, and the function 
.I vec_to_cdwd
is used to replace each codeword with the corresponding feature-vector
centroid.  This process is repeated iteratively until the fractional
decrease in the overall average distortion between successive iterations
falls below 
.I cbk\->conv_ratio
(successful convergence \- see below), or until 
.I max_iter
iterations have been tried, in which case
.I vqdesign
exits.  
.PP
If convergence was successful but an empty cluster remains, the 
empty cluster is 
discarded and then filled by splitting a codeword selected by the criterion
determined by 
.I split_crit
and using the
.I split
function on this codeword. Note that the new codeword will be created
with a codeword index immediately following the codeword that is split. 
The codebook is then reclustered until convergence is reached again.  
This process continues until no empty cells remain.  If the number 
distinct vectors in the training sequence is less than the desired 
number of codewords, this process could loop forever.  However, 
it will terminate when the limit 
.I max_iter
is reached. 
.PP
If convergence was successful and no empty cells remain,
.I vqdesign
enlarges the codebook by selecting codewords according to 
.I split_crit
and using the 
.I split
function on these codewords.  
.I vqdesign
continues to select and split codewords like this until
the codebook has been exhausted, in which case it has doubled 
in size, or the design size is reached.  
.PP
The enlarged codebook is then clustered 
as described above, and the the split-cluster process iterates
until the codebook size reaches 
.I cbk\->design_size.  
.PP
If any of the functions 
.I "get_chunk, distort, vec_to_cdwd,"
or 
.I split
report a non-zero error status, 
.I vqdesign 
writes a suitable message on 
.I histrm 
(provided \fIhistrm\fP != NULL) and returns with an appropriate 
status value (see the list, above).  
.PP
If the codebook does not converge during any of the clustering steps, 
.I vqdesign
writes appropriate information on 
.I histrm
and returns with the value VQ_NOCONVG.  
.SH ASSUMPTIONS
.PP
It is assumed that 
a cluster centroid can be obtained by applying 
.I vec_to_cdwd
to 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.  
.SH FUTURE CHANGES
.PP
.SH BUGS
None known.
.SH SEE ALSO
.PP
vqencode(3\-ESPSsp), f_mat_alloc (3\-ESPSu), 
vqdes(1\-ESPS), vq(1\-ESPS)
.SH REFERENCES
.LP
[1] J. E. Shore and R. M. Gray, "Minimum cross-entropy pattern
classification and cluster analysis," \fIIEEE Trans. Pattern 
Analysis and Machine Intelligence \fBPAMI-4\fR, January, 1982, 
pp. 11-17.  
.LP
[2] Y. Linde, A. Buzo, and R. M. Gray, "An algorithm for vector quantizer
design," \fIIEEE Trans. on Communications \fBCOM-28\fR, January, 
1980, pp. 84-95.
.LP
[3] R. M. Gray, "Vector quantization," \fIIEEE ASSP Magazine\fR, April, 
1984, pp. 4-29.
.LP
[4] J. Makhoul, S. Roucos, and H. Gish, "Vector quantization in speech 
coding," \fIProceedings IEEE \fB73\fR, November, 1985, pp. 1551-1588.
.SH AUTHOR
Manual page and program by John Shore.