Improved fast search method for vector quantization using discrete Walsh transform

Zhibin Pan, Koji Kotani, Tadahiro Ohmi

Research output: Contribution to journalConference articlepeer-review


In a framework of vector quantization (VQ), the fast search method for finding the best-matched codeword (winner) is a key issue because it is the time bottleneck for practical applications. To speed up VQ encoding process, some fast search methods that are based on the concept of projection axes or Walsh transform have already been proposed in previous works [4]-[9]. However, there still exist two serious problems in them because they use both spatial domain and partial Walsh domain simultaneously. First, they need extra memories for storing projected values on selected projection axes or the first several elements in partial Walsh domain, which becomes an overhead of memory. Second, once all rejection tests fail finally, they completely discard the obtained distortion that has already been computed in partial Walsh domain and return to spatial domain to compute real Euclidean distance again from the very beginning, which is certainly a waste and becomes an overhead of computation. In order to solve the overhead problems of both memory and computation as described above, firstly a memory-efficient storing way for a vector is proposed by completely mapping a vector into Walsh domain but NOT using the original spatial domain anymore, which can avoid extra memory requirement Secondly, the discarded distortion in partial Walsh domain is reused so as to avoid any waste to the executed computation. In addition, a more efficient rejection test is suggested to reduce more search space. Experimental results confirmed that the proposed method outperforms the previous works obviously.

Original languageEnglish
Pages (from-to)3177-3180
Number of pages4
JournalProceedings - International Conference on Image Processing, ICIP
Publication statusPublished - 2004
Event2004 International Conference on Image Processing, ICIP 2004 - , Singapore
Duration: 2004 Oct 182004 Oct 21

ASJC Scopus subject areas

  • Engineering(all)


Dive into the research topics of 'Improved fast search method for vector quantization using discrete Walsh transform'. Together they form a unique fingerprint.

Cite this