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

doi:10.1016/j.amc.2003.12.134

2005-03-01

PRE

Shiuh-Jeng Wang *

Cheng-Hsing Yang

DOI：10.1016/j.amc.2003.12.134

原文链接

原文求助

摘要

En 中文

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 [log(k) N] 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[log(k) N], 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 tile 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[log(k) N]/N times the full search method. It is worth noting that tile 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 tile codewords distribution in tile 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 ill the closest codeword searching for vector quantization of image data. (C) 2004 Elsevier Inc. All rights reserved.

Keyword:

codeword

duplicate

VQ search

hierarchy