US5832131A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Hashing-based vector quantization
Assignee: National Semiconductor Corp
•
Filing: 1995-05-03
•
Granted: 1998-11-03
•
Expires: 2015-05-03
Abstract
Abstract A hashing-based vector quantization process partitions a codebook into buckets. A hashing function determines the locations of buckets in the codebook and is selected so that buckets containing similar codevectors start near each other in the codebook. One hashing function forms an index from the most significant bits of components of a vector. During encoding, the hashing function generates an index from an input vector, and a search for a codevector matching the image vector begins in a bucket indicated by the index. In one embodiment, the codebook contains flag fields to indicate the starts of buckets and pointer fields to create linked lists of codevectors which form the buckets. Codevectors are compared to the input vector by determining the mean squared error of the difference between the codevector and the input vector. A search is complete when the search finds a codevector having a difference with a MSE less than a threshold. Search time is reduced because each search begins in a bucket likely to contain a codevector matching the image vector.
Inventors
- 👤 Chang Y. Choo
- 👤 Xiaonong Ran
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-08 07:32
CPC Classifications
G; G06; G06T; G06T9/00; G06T9/008; H; H03; H03M; H03M7/00; H03M7/30; H03M7/3082; H04; H04N; H04N19/00; H04N19/90; H04N19/94
Claims Analysis
Total Claims: 12
Claim 1
Independent Claim
284 words
A method for encoding information, comprising: applying a hashing function to codevectors to generate a hashed index for each of the codevectors; storing the codevectors in a codebook, wherein storing the codevectors comprises storing at least one of the codevectors at an address in the codebook indicated by the hashed index for the codevector, wherein storing the codevectors in the codebook comprises: partitioning the codebook into bins, wherein each bin has a different address; determining a hashed index of a first codevector; determining whether a first bin which has an address corresponding to the hashed index of the first codevector is vacant; storing the first codevector in the first bin if the first bin is vacant; and if the first bin is not vacant: determining whether a second codevector which is stored in the first bin is more popular than the first codevector; storing the first codevector in a second bin if the first codevector is less popular than the second codevector; and storing the first codevector in the first bin and the second codevector in the second bin if the first codevector is more popular than the second codevector; generating an input vector which represents a portion of the information; applying the hashing function to the input vector to generate a hashed index corresponding to the input vector; searching the codebook to find in the codebook a codevector such that a measure of a difference between the codevector and the input vector is less than a threshold, wherein searching begins in the codebook, at an address that depends on the hashed index of the input vector; and generating a signal which represents a codebook index of a codevector found in the searching step.
Claim 2
Independent Claim
284 words
A method for encoding information, comprising: applying a hashing function to codevectors to generate a hashed index for each of the codevectors; storing the codevectors in a codebook, wherein storing the codevectors comprises storing at least one of the codevectors at an address in the codebook indicated by the hashed index for the codevector, wherein storing the codevectors in the codebook comprises: partitioning the codebook into bins, wherein each bin has a different address; determining a hashed index of a first codevector; determining whether a first bin which has an address corresponding to the hashed index of the first codevector is vacant; storing the first codevector in the first bin if the first bin is vacant; and if the first bin is not vacant: determining whether a second codevector which is stored in the first bin is more popular than the first codevector; storing the first codevector in a second bin if the first codevector is less popular than the second codevector; and storing the first codevector in the first bin and the second codevector in the second bin if the first codevector is more popular than the second codevector; generating an input vector which represents a portion of the information; applying the hashing function to the input vector to generate a hashed index corresponding to the input vector; searching the codebook to find in the codebook a codevector such that a measure of a difference between the codevector and the input vector is less than a threshold, wherein searching begins in the codebook, at an address that depends on the hashed index of the input vector; and generating a signal which represents a codebook index of a codevector found in the searching step.
Claim 3
Dependent Claim
29 words
The method of claim 1, wherein storing the first codevector in the second bin further comprises creating a linked list which links the second bin to the first bin.
Claim 4
Dependent Claim
42 words
The method of claim 2, wherein searching the codebook comprises comparing the input vector to codevectors, and the codevector in the second bin is compared to the input vector after the codevector in the first bin is compared to the input vector.
Claim 5
Independent Claim
175 words
A method for constructing a codebook for use in a vector quantization circuit, comprising: partitioning a memory into bins; applying a hashing function to a codevector to determine a hashed index; determining whether a first bin that has an address corresponding to the hashed index is vacant; storing the codevector in the first bin if the first bin is vacant and in a second bin if the first bin is not vacant, wherein the second bin is vacant before storing the codevector and has an address not corresponding to the hashed index; in response to storing the codevector in the first bin, setting a flag field in the first bin to indicate that the codevector is stored in a bin that has an address corresponding to the hashed index of the codevector; and in response to storing the codevector in the second bin, setting a flag field in the second bin to indicate that the codevector is stored in a bin that does not have an address corresponding to the hashed index of the codevector.
Claim 6
Independent Claim
175 words
A method for constructing a codebook for use in a vector quantization circuit, comprising: partitioning a memory into bins; applying a hashing function to a codevector to determine a hashed index; determining whether a first bin that has an address corresponding to the hashed index is vacant; storing the codevector in the first bin if the first bin is vacant and in a second bin if the first bin is not vacant, wherein the second bin is vacant before storing the codevector and has an address not corresponding to the hashed index; in response to storing the codevector in the first bin, setting a flag field in the first bin to indicate that the codevector is stored in a bin that has an address corresponding to the hashed index of the codevector; and in response to storing the codevector in the second bin, setting a flag field in the second bin to indicate that the codevector is stored in a bin that does not have an address corresponding to the hashed index of the codevector.
Claim 7
Dependent Claim
27 words
The method of claim 4, further comprises storing a pointer to the first bin, in the first bin in response to determining the first bin is vacant.
Claim 8
Independent Claim
135 words
A method for constructing a codebook for use in a vector quantization process comprising: partitioning a memory into bins; applying a hashing function to a first codevector to determine a hashed index: determining whether a bin which has an address corresponding to the hashed index is vacant: storing the first codevector in the bin if the bin is vacant: comparing popularity of the first codevector to popularity of a second codevector which is stored in the bin if the bin is not vacant; storing the first codevector in a second bin if the comparison indicates the first codevector is less popular than the second codevector; and storing the first codevector in the bin and the second codevector in a second bin if the comparison indicates the first codevector is more popular than the second codevector.
Claim 9
Independent Claim
135 words
A method for constructing a codebook for use in a vector quantization process comprising: partitioning a memory into bins; applying a hashing function to a first codevector to determine a hashed index: determining whether a bin which has an address corresponding to the hashed index is vacant: storing the first codevector in the bin if the bin is vacant: comparing popularity of the first codevector to popularity of a second codevector which is stored in the bin if the bin is not vacant; storing the first codevector in a second bin if the comparison indicates the first codevector is less popular than the second codevector; and storing the first codevector in the bin and the second codevector in a second bin if the comparison indicates the first codevector is more popular than the second codevector.
Claim 10
Dependent Claim
33 words
The method of claim 6, wherein storing one of the first and second codevectors in the second bin further comprises creating a linked list that links the second bin to the first bin.
Claim 11
Dependent Claim
28 words
The method of claim 4, wherein storing the codevectors in the second bin further comprises creating a linked list that links the second bin to the first bin.
Claim 12
Dependent Claim
63 words
The method of claim 4, further comprising repeating the applying, determining, storing, and setting steps once for each codevector found by a training process, wherein no codevector is stored in a bin having an address not corresponding to the codevector until after each codevector to be stored in a bin having an address corresponding to a hashed index for the codevector is stored.
References Cited (Backward Citations)
US4791670A
Cited
US5353305A
Cited
US4979039A
Cited
US5130797A
Cited
US5282255A
Cited
US5231485A
Cited
US5371544A
Cited
US5444488A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2001-11-02 | 2002-05-04 | 2002-11-03 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2005-11-02 | 2006-05-04 | 2006-11-03 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2009-11-02 | 2010-05-04 | 2010-11-03 | $7700.00 | Window Closed / Lapsed |