Geometric vector quantization
First Claim
1. A method of coding a set of multi-level signals comprising the steps of:
- ordering the multi-level signals according to values of a signal parameter;
one or more times, partitioning the order of multi-level signals into two or more elements, each element including one or more multi-level signals;
determining a magnitude for an element based upon signal parameter values for signals in the element;
comparing a partition of elements with the set of multi-level signals to determine a difference metric based on partition element magnitudes and multi-level signal parameter values; and
selecting as a vector representing the set of multi-level signals a partition of elements which satisfies a difference metric criterion.
1 Assignment
0 Petitions
Accused Products
Abstract
A geometric vector quantizer coding technique is illustrated in the context of a full motion video coder based on a three-dimensional sub-band framework. The original image data is decomposed into different spatial-temporal frequency bands and based on the data in each band, different quantization strategies are applied to the bands. The lowest spatial-temporal frequency band is coded using a traditional three-dimensional switched predictor and optimum scaler quantizer. The non-dominant sub-bands are coded using the vector quantization approach to efficiently encode the images while appropriately exploiting the sparse, highly structured nature of the data to design the codebooks. Variable resolution is achieved using these techniques and no training is needed to establish or maintain the codebook. A fast codebook search technique is provided for identifying the optimal codebook vector for representing a block of input data. Examples of two and three level geometric vector quantizers are also provided.
-
Citations
23 Claims
-
1. A method of coding a set of multi-level signals comprising the steps of:
-
ordering the multi-level signals according to values of a signal parameter; one or more times, partitioning the order of multi-level signals into two or more elements, each element including one or more multi-level signals; determining a magnitude for an element based upon signal parameter values for signals in the element; comparing a partition of elements with the set of multi-level signals to determine a difference metric based on partition element magnitudes and multi-level signal parameter values; and selecting as a vector representing the set of multi-level signals a partition of elements which satisfies a difference metric criterion. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11)
-
-
12. A method of coding a set of multi-level signals comprising the steps of:
-
providing a set of vectors, each of said vectors comprising a geometric array of elements, wherein one or more first elements of each vector have associated therewith predetermined magnitudes, and wherein one or more other elements of each vector have associated therewith magnitudes determined based on levels of multi-level signals being coded; comparing multi-level signals with one or more of the vectors to determine, for each such vector, a difference metric based on multi-level signal levels and vector element magnitudes; and representing the set of multi-level signals with use of a vector which satisfies a difference metric criterion. - View Dependent Claims (13, 14, 15)
-
-
16. A method of coding a set of multi-level signals, wherein the set of multi-level signals comprises at least one signal having a positive level and at least one signal having a negative level, the method comprising the steps of:
-
a. ordering multi-level signals of the set according to signal level; b. a plurality of times, partitioning the ordered, non-positive multi-level signals into at least two groups of non-positive signals; c. for a partition of ordered, non-positive multi-level signals, 1. forming a first vector of signals, the first vector including first and second sets of signals, i. the signals of the first vector'"'"'s first set having predetermined magnitudes and corresponding to a first group of non-positive multi-level signals in the partition, and ii. the signals of the first vector'"'"'s second set having magnitudes based on levels of signals in a second group of non-positive multi-level signals in the partition; 2. comparing the first vector of signals with ordered, non-positive multi-level signals to determine a first difference metric; d. identifying a first vector of signals having a first difference metric which satisfies a first difference metric criterion; e. a plurality of times, partitioning the ordered, non-negative multi-level signals into at least two groups of non-negative signals; f. for a partition of ordered, non-negative multi-level signals, - View Dependent Claims (18, 21)
-
-
17. forming a second vector of signals, the second vector including first and second sets of signals,
i. the signals of the second vector'"'"'s first set having predetermined magnitudes and corresponding to a first group of non-negative multi-level signals in the partition, and ii. the signals of the second vector'"'"'s second set having magnitudes based on levels of signals in a second group of non-negative multi-level signals in the partition; -
2. comparing the second vector of signals with ordered, non-negative multi-level signals to determine a second difference metric; g. identifying a second vector of signals having a difference metric which satisfies a second difference metric criterion; and h. combining the identified first and second vectors of non-positive and non-negative signals to determine a vector of signals for use in coding the set of multi-level signals.
-
-
19. A method of coding a set of multi-level signals, wherein the set of multi-level signals includes non-positive signal levels only, the method comprising the steps of:
-
a. ordering multi-level signals of the set according to signal level; b. a plurality of times, forming a vector of signals by 2. partitioning the ordered, multi-level signals into first and second groups of signals, the first group of signals comprising at least one of the least negative multi-level signals and the second group comprising one or more of the balance of the multi-level signals, 2. assigning a predetermined magnitude to one or more first signals of the vector, which first signals correspond to the signals of the first group of signals,
-
-
20. a plurality of times, partitioning the second group of multi-level signals into first and second sub-groups of multi-level signals,for a partition of the second group of multi-level signals
i. assigning a magnitude to one or more second signals of the vector based on the multi-level signals of the first sub-group of multi-level signals, ii. assigning a magnitude to one or more third signals of the vector based on the multi-level signals of the second sub-group of multi-level signals, iii. comparing the second and third signals of the vector with ordered, non-positive multi-level signals to determine a first difference metric; -
5. identifying second and third signals of the vector having a .first difference metric which satisfies a first difference metric criterion; and 6. comparing the vector of signals with ordered, multi-level signals to determine a second difference metric based on vector signal magnitudes and multi-level signal levels; and c. identifying a vector of signals for use in coding the multi-level signals, the identified vector having a second difference metric which satisfies a second difference metric criterion. - View Dependent Claims (23)
-
-
22. A method of coding a set of multi-level signals, wherein the set of multi-level signals includes non-negative signal levels only, the method comprising the steps of:
-
a. ordering multi-level signals of the set according to signal level; b. a plurality of times, forming a vector of signals by 1. partitioning the ordered, multi-level signals into first and second groups of signals, the first group of signals comprising at least one of the least positive multi-level signals and the second group comprising one or more of the balance of the multi-level signals, 2. assigning a predetermined magnitude to one or more first signals of the vector, which first signals correspond to the signals of the first group of signals, 3. a plurality of times, partitioning the second group of multi-level signals into first and second sub-groups of multi-level signals, 4. for a partition of the second group of multi-level signals, i. assigning a magnitude to one or more second signals of the vector based on the multi-level signals of the first sub-group of multi-level signals, ii. assigning a magnitude to one or more third signals of the vector based on the multi-level signals of the second sub-group of multi-level signals; iii. comparing the second and third signals of the vector with ordered, non-negative multi-level signals to determine a first difference metric; 5. identifying second and third signals of the vector having a first difference metric which satisfies a first difference metric criterion; 6. comparing the vector of signals with ordered, multi-level signals to determine a second difference metric based on vector signal magnitudes and multi-level signal levels; and c. identifying a vector of signals for use in coding the multi-level signals, the identified vector having a second difference metric which satisfies a second difference metric criterion.
-
Specification