Hierarchy-oriented searching algorithms using alternative duplicate codewords for vector quantization mechanism

摘要

In this paper, we will show those algorithms that speed up the search of a closest codeword over a given codebook. The mechanism is based on a multilevel concept constructed as a hierarchical organization. For a given codebook with size N (existing N codewords), there are only ⌈logkN⌉ levels that need to be constructed in order to find the closest codeword, where k is a parameter selection to optimize the comparisons in the course of the searching. Theoretically, the comparisons required to find the closest codeword are on average k⌈logkN⌉, which is substantially faster than that of a full search job. Besides, in order to approach the perfect match with the exact one among the codewords, a duplicate mechanism is also applied to our algorithm so that the lowest possible distortion is achieved. As is observed from the results of the experiments, the estimation of comparisons in our execution, without codeword duplicate, is on average about k⌈logkN⌉/N times the full search method. It is worth noting that the larger the size of the codebook, the more the speed increases. In particular, there are two classifications, non-duplicate and duplicate method which are associated with the codewords distribution in the dominated set, which were experimented on some tables. The duplicate is manipulated by the training set containing six popular image data, to demonstrate the efficiency of our scheme. Also, the time requirement to find the closest codeword is effectively reduced, especially in the case of a large sized codebook. Therefore, our scheme offers a novel exploration and achieves a faster performance in the closest codeword searching for vector quantization of image data.