US5371544A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Geometric vector quantization
Assignee: AT&T Inc
•
Filing: 1992-02-07
•
Granted: 1994-12-06
•
Expires: 2012-02-07
Abstract
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.
Inventors
- 👤 Arnaud E. Jacquin
- 👤 Nuggehally S. Jayant
- 👤 Christine I. Podilchuk
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-01 20:00
CPC Classifications
G; G06; G06T; G06T9/00; G06T9/008; H; H03; H03M; H03M7/00; H03M7/30; H03M7/3082; H04; H04N; H04N19/00; H04N19/50; H04N19/503; H04N19/60; H04N19/62; H04N19/90; H04N19/94; H04N19/30
Claims Analysis
Total Claims: 30
Claim 1
Independent Claim
110 words
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.
Claim 2
Independent Claim
110 words
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.
Claim 3
Dependent Claim
12 words
The method of claim 1 wherein the signal parameter comprises signal intensity.
Claim 4
Dependent Claim
30 words
The method of claim 1 wherein the magnitude of a partition element is determined based on an average signal parameter value for one or more multi-level signals of the element.
Claim 5
Dependent Claim
14 words
The method of claim 3 wherein the signal parameter value comprises signal intensity value.
Claim 6
Dependent Claim
25 words
The method of claim 1 wherein the step of determining a magnitude comprises the step of determining a magnitude for each element of a partition.
Claim 7
Dependent Claim
14 words
The method of claim 1 wherein the difference metric comprises a mean square difference.
Claim 8
Dependent Claim
15 words
The method of claim 1 wherein the difference metric criterion comprises a minimum difference metric.
Claim 9
Dependent Claim
20 words
The method of claim 1 wherein the step of selecting comprises determining a codebook index to represent the selected vector.
Claim 10
Dependent Claim
18 words
The method of claim 8 further comprising the step of communicating the determined codebook index to a receiver.
Claim 11
Dependent Claim
17 words
The method of claim 1 wherein the set of multi-level signals comprises a set of image pixels.
Claim 12
Dependent Claim
16 words
The method of claim 10 wherein a signal level reflects a gray level of a pixel.
Claim 13
Independent Claim
111 words
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.
Claim 14
Independent Claim
111 words
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.
Claim 15
Dependent Claim
16 words
The method of claim 12 wherein the first difference metric criterion comprises a minimum difference metric.
Claim 16
Dependent Claim
48 words
The method of claim 12 wherein the step of representing the set of multi-level signals comprises the step of determining a codebook index to represent the vector which satisfies the first difference metric criterion and further comprising the step of communicating the determined codebook index to a receiver.
Claim 17
Dependent Claim
42 words
The method of claim 12 wherein the step of providing a set of vectors comprises the step of selecting one or more first elements of a vector to have predetermined magnitudes, the selection of the first elements based on the multi-level signals.
Claim 18
Independent Claim
213 words
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,
Claim 19
Independent Claim
213 words
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,
Claim 20
Dependent Claim
134 words
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.
Claim 21
Dependent Claim
134 words
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.
Claim 22
Dependent Claim
20 words
The method of claim 16 wherein each of the first and second difference metric criteria comprises a minimum difference metric.
Claim 23
Independent Claim
118 words
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,
Claim 24
Independent Claim
118 words
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,
Claim 25
Dependent Claim
177 words
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-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.
Claim 26
Dependent Claim
177 words
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-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.
Claim 27
Dependent Claim
21 words
The method of claim 18 wherein each of the first 2 and second difference metric criteria comprises a minimum difference metric.
Claim 28
Independent Claim
295 words
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.
Claim 29
Independent Claim
295 words
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.
Claim 30
Dependent Claim
20 words
The method of claim 20 wherein each of the first and second difference metric criteria comprises a minimum difference metric.
References Cited (Backward Citations)
US5039741A
Cited
US4769826A
Cited
US4797739A
Cited
US4780761A
Cited
US5010401A
Cited
EP0360502A1
Cited
US4979039A
Cited
US5079631A
Cited
WO1990015485A1
Cited
US5138315A
Cited
US5063444A
Cited
US5136374A
Cited
US5194864A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1997-12-05 | 1998-06-06 | 1998-12-06 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2001-12-05 | 2002-06-06 | 2002-12-06 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2005-12-05 | 2006-06-06 | 2006-12-06 | $7700.00 | Window Closed / Lapsed |