Accelerating VQ-based codeword search on the basis of partial search strategy

摘要

In this paper, a technique for accelerating the search on VQ-based codeword search is proposed. With our approach, all the pixel blocks of vector representation in an image picture could be encoded efficiently into their corresponding indices, and be associated with the closest codeword in the pre-generated codebook. The technique adopted in our scheme is inspired by the concept of space partition of the initial codebook. It is accomplished in a manner that the search range for the image block is significantly reduced. There is a key-codebook comprised of numerous key-codewords, and with a smaller book size, which is generated from the given codewords during system initialization. Any image block is then directed to look for the closest key-codeword in the key-codebook. Ultimately, the best-match codeword is checked out according to the relation between the closest key-codeword and the 'genuine' codewords in the given codebook. This short-time achievement is obtained because of the considerable book size reduction. A flexible radius, spread by a key-codeword is imposed in our elaborated algorithm to attain the most precise hit ratio estimation. The experiments show that our scheme is at least two and a half times faster than that of a full search in VQ implementation. Moreover, the strategy we proposed is also compatible with the search algorithms in finding the closest codeword, and the high quality of image display remained the same.