Hashing-based vector quantization

Details Hashing-based vector quantization Hashing-based vector quantization

1998-02-03

1999-11-23

Kelley, Christopher S.

Image analysis

Image compression or coding

Quantization

348418, G06K 936

Patent

active

059914556

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.

REFERENCES:
patent: 4791670 (1988-12-01), Copperi et al.
patent: 4979039 (1990-12-01), Kisor et al.
patent: 5130797 (1992-07-01), Murakami et al.
patent: 5231485 (1993-07-01), Israelsen et al.
patent: 5282255 (1994-01-01), Bovik et al.
patent: 5371544 (1994-12-01), Jacquin et al.
patent: 5444488 (1995-08-01), Goubault et al.
patent: 5535305 (1996-07-01), Acero et al.
patent: 5649030 (1997-07-01), Normile et al.
Aho et al., The Design and Analysis of Computer Algorithms, Addison-Wesley Series, Jun. 1974, Bell Telephone Laboratories, Inc., pp. 110-113.
Choo et al., "Evaluation of Design Parameters for Cache Vector Quantization Systems", IEEE International Conf. On Image Procession, vol. I, Apr. 1994, pp. 129-133.
Feng et al., "A Self-Organizing Adaptive Vector Quantization Technique", Journal of Visual Communication and Image Representation, vol. 2, No. 2, Jun. 1991, pp. 129-137.
Gersho et al., Vector Quantization and Signal Compression, Kluwer Academic Publishers, Sep. 1992, pp. 410-423.
Kanada, "A Vectorization Technique of Hashing and its Application to Several Sorting Algorithms", IEEE/IEE PARBASE '90, pp. 147-151. Apr. 1990.
Linde et al., "An Algorithm for Vector Quantizer Design", IEEE Transactions on Communications, vol. COM-28, No. 1, Jan. 1980, pp. 84-94.
Nasrabadi et al., "Dynamic Finite-State Vector Quantization fo Digital Images", IEEE Trans. on Communication, vol. 42, No. 5, May 1994, pp. 2145-2154.
Panneerselvam et al., "New Architecture for Systolic Hashing", IEEE/IEE Systolic Arrays, Aug. 1988, International Conf., pp. 73-82.
Ramakrishna, "An Exact Probability Model for Finite Hash Tables", IEEE/IEE Date Engineering, Jul. 1988, 4th International Conf., pp. 362-368.
Sezan et al., Motion Analysis and Image Sequence Processing, Kluwer Academic Publishers, Jun. 1993, pp. 256-283.
Yen et al., "Hash Table and Sorted Array: A Case Study of Mult-Entry Data Structures in Massively Parallel Systems", IEEE/IEE Fronties of Massively Parallel Computation, Feb. 1990, pp. 51-54.

Affiliated with

Also associated with

Rating

Hashing-based vector quantization does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Hashing-based vector quantization, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Hashing-based vector quantization will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-1231504