Hashing-based vector quantization

Details Hashing-based vector quantization Hashing-based vector quantization

1995-05-03

1998-11-03

Kelley, Christopher S.

Image analysis

Image compression or coding

Quantization

348418, 348422, G06K 936

Patent

active

058321314

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: 5353305 (1994-10-01), Acero et al.
patent: 5371544 (1994-12-01), Jacquin et al.
patent: 5444488 (1995-08-01), Goubault et al.
Panneerselvam et al., "New Architectures for Systolic Hashing," IEEE/IEE Systolic Arrays, 1988 International Conf., pp. 73-82.
Ramakrishna, "An Exact Probability Model for Finite Hash Tables," IEEE/IEE Date Engineering, 1988 4th International Conf., pp. 362-368.
Yen et al., "Hash Table and Sorted Array: A Case Study of Multi-Entry Data Structures in Massively Parallel Systems," IEEE/IEE Frontiers of Massively Parallel Computation 1990, pp. 51-54.
Kanada, "A Vectorization Technique of Hashing and its Application to Several Sorting Algorithms," IEEE/IEE PARBASE '90, pp. 147-151.
Sezan et al., Motion Analysis and Image Sequence Processing, Kluwer Academic Publishers, 1993, pp. 256-283.
Aho et al., The Design and Analysis of Computer Algorithms, Addison-Wesley Series, 1974, Bell Telephone Laboratories, Inc., pp. 110-113.
Nasrabadi et al., "Dynamic Finite-State Vector Quantization of Digital Images," IEEE Trans, on Communications, vol. 42, No. 5, May, 1994, pp. 2145-2154.
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, 1992, pp. 410-423.
Choo et al., "Evaluation of Design Parameters for Cache Vector Quantization System," IEEE International Conf. on Image Processing, vol. I, 1994, pp. 129-133.
Linde et al., "An Algorithm for Vector Quantizer Design," IEEE Transactions on Communications, vol. COM-28, No. 1, Jan., 1980, pp. 84-94.

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-699410