Hashing-based vector quantization

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.