Multiplication-free fast codeword search algorithm using Haar transform with squared-distance measure

Wen Jyi Hwang, Ray Shine Lin, Wen Liang Hwang, Chung Kun Wu

Research output: Contribution to journalArticle

Abstract

This letter presents novel multiplication-free fast codeword search algorithms for encoding of vector quantizers (VQs) based on squared-distance measure. The algorithms accomplish fast codeword search by performing the partial distance search (PDS) in the wavelet domain. To eliminate the requirement for multiplication, simple Haar wavelet is used so that the wavelet coefficients of codewords are finite precision numbers. The computation of squared distance for PDS can therefore be effectively realized using additions. To further enhance the computational efficiency of the algorithms, the addition-based squared-distance computation is decomposed into a number of stages. The PDS process is then extended to these stages to reduce the addition complexity of the algorithm. In addition, by performing PDS over smaller number of stages, lower computational complexity can be obtained at the expense of slightly higher average distortion for encoding. Simulation results show that our algorithms are very effective for the encoding of VQs, where both low computational complexity and average distortion are desired.

Original languageEnglish
Pages (from-to)399-405
Number of pages7
JournalPattern Recognition Letters
Volume21
Issue number5
DOIs
Publication statusPublished - 2000 May

    Fingerprint

Keywords

  • Fast codeword search
  • Image compression
  • Vector quantization

ASJC Scopus subject areas

  • Software
  • Signal Processing
  • Computer Vision and Pattern Recognition
  • Artificial Intelligence

Cite this