Patent ID: 6438268
Filing Date: 2002-08-20
Classification: G06T,H03M,H04N

Abstract:
A method of constructing a vector quantisation codebook from at least one archetypal data array composed of a set of data values, the method comprising:1) selecting from the data array(s) a first multiplicity of n-dimension sample vectors, each sample vector consisting of a set of data values which are contiguous in the array(s) and each sample vector defining. a point in a finite n-dimensional space; 2) partitioning said space into a predetermined number of regions, each region containing substantially the same number of sample vectors; 3) assigning to each said region a unique index, where the indices are selected to codify the partitioning process carried out in step 2); 4) determining for substantially all possible points within said space, the regions in which these points are located, and constructing a look-up index table mapping substantially all possible points to the respective region indices; 5) selecting from the data array(s) a second multiplicity of n-dimension sample vectors, each sample vector consisting of a set of contiguous data values, and replacing each of these sample vectors with the associated region index obtained by looking up the index table generated in step 4) to create a further data array or arrays; 6) iteratively repeating steps 1) to 5) for the further data array(s) and any subsequently generated further data array(s), wherein each index generated in the final iteration is derived from a set of nm dimension sample vectors in the archetypal data array(s), where m is the number of iterations carried out; 7) for each index generated in the final iteration, creating an nm dimension reference vector which is representative of the associated set of nm dimension sample vectors in the archetypal data array; and 8) constructing a codebook containing the reference vectors, where each index generated in the final iteration points to the location in the codebook of the corresponding reference vector.