Single chip design for fast image compression

• US 5,468,069 A
• Filed: 08/03/1993
• Issued: 11/21/1995
• Est. Priority Date: 08/03/1993
• Status: Expired due to Fees

• Current Assignee: University of Southern California
• Original Assignee: University of So. California
• Inventors: Prasanna, Viktor K., Park, Heonchul, Wang, Cho-Li
• Primary Examiner(s): Mancuso, Joseph
• Assistant Examiner(s): DEL ROSSO, GERARD DOMNICK
• Application Number:
  US08/100,928
• Time in Patent Office: 840 Days
• Field of Search: 382/56, 382/37, 348/422, 358/426, 358/433
• US Class Current: 382/253
• CPC Class Codes: G06T 9/008 Vector quantisation

Abstract

Video data compression techniques reduce necessary storage size and communication channel bandwidth while maintaining acceptable fidelity. Vector quantization provides better overall data compression performance by coding vectors instead of scalars. The search algorithm and VLSI architecture for implementing it is herein disclosed, and such a search algorithm is useful for real-time image processing. The architecture employs a single processing element and external memory for storing the N constant value hyperplanes used in the search, where N is the number of codevectors. The design does not perform any multiplication operation using the constant value hyperplane tree search, since the tree search method is independent of any L_q metric for q between one and infinity. Memory used by the design is significantly less than memory employed in existing architecture.

Claims

1. An apparatus for compressing data in the form of a plurality of input vectors into a set of identification indices associated with a set of codebook vectors, said apparatus comprising:

a. means for receiving the plurality of input vectors;

b. search means connected to the means for receiving the plurality of input vectors, wherein said search means consist of;

(1) means for selecting a set of training vectors;

(2) means for defining an n-dimensional box containing all training vectors, wherein n represents codebook vector dimension;

(3) means for recursively splitting the n-dimensional box using a constant value hyperplane into two subboxes, wherein each subbox contains an equal number of training vectors, until a predetermined number of subboxes is obtained;

(4) means for determining a centroid of each subbox; and

(5) means for assigning a codevector to each centroid;

c. means for storing the set of codebook vectors and the set of constant value hyperplanes;

d. means for searching the set of codebook vectors and matching the plurality of input vectors to the set of codebook vectors using the constant value hyperplanes and assigning an identification index to each input vector based on the closest codebook vector; and

e. means for transmitting the set of identification indices and the set of codebook vectors.

2. The apparatus for compressing data of claim 1, wherein means for storing the set of codebook vectors and the set of constant value hyperplanes is an external memory module circuit and a memory index register circuit.

3. An apparatus for compressing data in the form of a plurality of input vectors into a set of identification indices associated with a set of codebook vectors, said apparatus comprising:

(a) means for calculating the set of codebook vectors and a set of constant value hyperplanes using a set of training vectors comprising;

(1) means for defining an n-dimensional box containing a set of training vectors;

(2) means for repeatedly dividing the n-dimensional box into a set of n-dimensional subboxes containing an equal number of training vectors by using constant value hyperplanes; and

3) means for selecting a center point of each subbox and assigning a codebook vector to said center point;

(b) means for storing the set of codebook vectors and the set of constant value hyperplanes;

(c) means for receiving the plurality of input vectors;

(d) means for searching the set of codebook vectors and matching the plurality of input vectors to the set of codebook vectors using the constant value hyperplanes and assigning an identification index to each input vector based on a closest codebook vector; and

(e) means for transmitting the set of identification indices.

4. The apparatus for compressing data of claim 3, wherein means for repeatedly dividing the n-dimensional box into a set of n-dimensional subboxes containing an equal number of training vectors by using constant value hyperplanes consists of dividing the n-dimensional box and subboxes so that each subbox contains an equal number of training vectors and the constant value hyperplane divides the n-dimensional box or subbox along its longest dimension.

5. The apparatus for compressing data of claim 4, wherein means for storing the set of constant value hyperplanes is an external memory module circuit and a memory index register circuit.

6. The apparatus for compressing data of claim 3, wherein means for calculating the set of codebook vectors and set of constant value hyperplanes consists of:

(a) means for calculating a constant value hyperplane which partitions the set of training vectors, said constant value hyperplane having the form;

##EQU2## (b) means for determining whether one of the training vectors is on One side of the constant value hyperplane;

(c) means for recursively calculating constant value hyperplanes until a predetermined number of constant value hyperplanes is selected; and

(d) means for determining a centroid of the training vectors bounded by the constant value hyperplanes and assigning a codevector to said centroid.

7. The apparatus for compressing data of claim 6, wherein the means for calculating the constant value hyperplane which partitions the set of training vectors consists of:

(a) means for creating an n-dimensional box containing the set of training vectors wherein n represents codebook dimension;

(b) means for calculating the constant value hyperplane along a longest dimension of said n-dimensional box such that the n-dimensional box is split into two n-dimensional boxes, wherein each subbox contains an equal number of training vectors.

8. An apparatus for compressing data in the form of an input vector into an identification code of one of a set of codebook vectors, said apparatus comprising:

(a) means for receiving the input vector and the set of codebook vectors;

(b) means for storing the input vector and set of codebook vectors;

(c) means for selecting a set of codebook vectors by altering a set of training vectors, wherein said means for selecting the set of codebook vectors consist of using a set of constant value hyperplanes to divide the set of training vectors into n-dimensional boxes containing equal numbers of training vectors, comprising;

.

(1) means for defining an n-dimensional box containing a set of training vectors;

(2) means for repeatedly dividing the n-dimensional box into a set of n

dimensional subboxes containing an equal number of training vectors by using constant value hyperplanes; and

(3) means for selecting a center point of each subbox and assigning a codebook vector to said center point;

(d) means for assigning an identification code to each of the set of codebook vectors; and

(e) means for generating an output signal, said output signal representative of the identification code of the closely matching codebook vector.

9. The apparatus for compressing data of claim 8, wherein means for repeatedly dividing the n-dimensional box into a set of n-dimensional subboxes containing an equal number of training vectors by using constant value hyperplanes consists of dividing the n-dimensional box and subboxes so that each subbox contains an equal number of training vectors and the constant value hyperplane divides the n-dimensional box or subbox along its longest dimension.

10. A circuit for performing a fast search of a codebook of codevectors, the circuit comprising:

(a) a processing element which utilizes a tree search to form a search tree which determines the codebook of codevectors and a plurality of constant value hyperplanes, comprising;

(1) a plurality of input data channels;

(2) an index output channel;

(3) an internal comparator;

(4) a plurality of internal storage registers for storing the input vector, data from the hyperplane constant input channel, the hyperplane index data channel, and the index output channel;

(5) an internal data buffer;

(6) a plurality of internal storage registers; and

(7) internal multiplexer;

(b) an external memory module which contains information about the plurality of hyperplanes used in the search; and

(c) a memory index register which stores the address of the location to be accessed in the external memory module using a comparison in the processing element of a hyperplane constant associated with each constant value hyperplane and an input vector corresponding .to a hyperplane index.

11. The circuit for performing a fast search of a codebook of codevectors of claim 10, wherein the plurality of input data channels consists of:

(a) an input data channel;

(b) a hyperplane constant input data channel; and

(c) a hyperplane index input data channel;

12. The circuit for performing a fast search of a codebook of codevectors of claim 11, wherein the plurality of internal storage registers consists of:

(a) an internal comparison storage register;

(b) an internal hyperplane constant storage register; and

(c) an internal hyperplane index storage register.

13. The circuit for performing a fast search of a codebook of codevectors of claim 11, wherein the internal data buffer consists of k registers operating as a word level shift register and is used as a data buffer and k represents codevector dimension.

14. The circuit for performing a fast search of a codebook of codevectors of claim 13, wherein the internal comparison storage register consists of k registers for storing the input to be used for comparison during log N cycles over a time window and N represents number of codevectors.

15. The circuit for performing a fast search of a codebook of codevectors of claim 14, wherein the data input channel consists of means for receiving an element of the input vector every cycle.

16. The circuit for performing a fast search of a codebook of codevectors of claim 15, wherein the hyperplane constant data channel and hyperplane index data channel consist of means for comparing an element of the input vector and hyperplane constant from hyperplane data received from the external memory module with input vector data in the data input channel.

17. The circuit for performing a fast search of a codebook of codevectors of claim 16, wherein the memory index register consists of means for fetching data corresponding to a next sequential level of the search tree, wherein output is available to the memory index register during a log Nth cycle of each window.

18. A circuit for performing a fast search of a codebook of codevectors, the circuit comprising;

(a) a processing element which utilizes a tree search to form a search tree which determines the codebook of codevectors and a plurality of constant value hyperplanes, comprising means for compressing data in the form of a plurality of input vectors into a set of identification indices associated with the codebook of codevectors, said data compression means comprising;

(1) means for receiving the plurality of input vectors;

(2) means for defining an n-dimensional box containing the set of training vectors;

(3) means for repeatedly dividing the n-dimensional box into a set of n-dimensional subboxes containing an equal number of training vectors by using constant value hyperplanes;

(4) means for selecting a center point of each subbox and assigning a codebook vector to said center point;

(5) means for storing the codebook of codevectors and the set of constant value hyperplanes;

(6) means for searching the codebook of codevectors and matching the plurality of input vectors to the codebook of codevectors using the constant value hyperplanes and assigning an identification index to each input vector based on a closest codebook vector; and

(7) means for transmitting the set of identification indices and the codebook of codevectors;

(b) an external memory module which contains information about the plurality of hyperplanes used in the search; and

(c) a memory index register which stores the address of the location to be accessed in the external memory module using a comparison in the processing element of a hyperplane constant associated with each constant value hyperplane and an input vector corresponding to a hyperplane index.

19. The circuit for performing a fast search of a codebook of codevectors of claim 18, wherein the means for repeatedly dividing the n-dimensional box into a set of n-dimensional subboxes containing an equal number of training vectors by using constant value hyperplanes consists of dividing the n-dimensional box and subboxes so that each subbox contains an equal number of training vectors and the constant value hyperplane divides the n-dimensional box or subbox along its longest dimension.

20. A method for searching a set of vectors to determine a vector closest to an input vector, the method comprising:

(a) selecting a set of training vectors;

(b) partitioning an n-dimensional space into a box b containing the set of training vectors wherein n represents vector dimension;

(c) dividing the box b into two subboxes b₁ and b₂ containing an equal number of training vectors using a hyperplane defined by a constant perpendicular to a longest dimension of box b;

(d) recursively finding a pair of training vectors contained in all remaining boxes whose distance is maximum among all pairs of vectors and subsplitting the box containing the pair of training vectors using a hyperplane defined by a constant into two subboxes containing an equal number of training vectors until a predetermined number of subboxes is obtained;

(e) selecting a center point of each subbox and assigning a codevector to the center point; and

(f) determining the closest codevector to an input vector by comparing the input vector to the hyperplanes and determining the subbox which contains the input vector.