Full text of DOI:10.1016/S0167-8655(00)00007-6

Pattern Recognition Letters 21 (2000) 399±405
www.elsevier.nl/locate/patrec
Multiplication-free fast codeword search algorithm using Haar
transform with squared-distance measure
Wen-Jyi Hwang a,*, Ray-Shine Lin a, Wen-Liang Hwang b, Chung-Kun Wu c
a
Department of Electrical Engineering, Chung Yuan Christian University, Chung-li 32023, Taiwan, ROC
b
Institute of Information Science, Academia Sinica, Taiwan, ROC
Department of Electrical Engineering, Chung Yuan Christian University, Chung-li 32023, Taiwan, ROC
c
Received 29 June 1999; received in revised form 30 December 1999; accepted 18 January 2000
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 coecients of codewords are ®nite precision numbers. The computation of squared distance for
PDS can therefore be e€ectively realized using additions. To further enhance the computational eciency of the al-
gorithms, 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 e€ective for the encoding of VQs, where
both low computational complexity and average distortion are desired. Ó 2000 Elsevier Science B.V. All rights
reserved.
Keywords: Vector quantization; Fast codeword search; Image compression
1. Introduction
for encoding is usually the important concern. For
the full-search VQs with high vector dimension
and/or large number of codewords, although a
good rate-distortion performance can be achieved,
the high computational complexity for encoding
might cause the VQs impractical for the imple-
mentation of realtime processing systems. To
eliminate the drawback, a number of fast code-
word search algorithms (Bei and Gray, 1985;
Hwang et al., 1997; Paliwal and Ramasubrama-
nian, 1989) have been proposed for the encoding
of full-search VQs. Although reasonable reduc-
tion in computational complexity is achieved,
Vector quantizers (VQs) (Abut, 1990; Gersho
and Gray, 1992) have been shown to be very ef-
fective for signal compression and video coding. In
the design of a VQ, in addition to its rate-distor-
tion performance, the computational complexity
* Corresponding author. Tel.: +886-3-456-3171-4808; fax:
+886-3-456-3160.
E-mail address: whwang@dec.ee.cycu.edu.tw (W.-J.
Hwang).
0167-8655/00/$ - see front matter Ó 2000 Elsevier Science B.V. All rights reserved.
PII: S 0 1 6 7 - 8 6 5 5 ( 0 0 ) 0 0 0 0 7 - 6

400
W.-J. Hwang et al. / Pattern Recognition Letters 21 (2000) 399±405
multiplications are still required for these algo-
rithms.
The objective of this letter therefore is to
present multiplication-free fast codeword search
algorithms for the encoding of full-search VQs
based on squared-distance measure. Similar to
the technique presented in (Hwang et al., 1997),
our algorithms achieve fast encoding by per-
forming the partial distance search (PDS) (Bei
and Gray, 1985) in the wavelet domain (Vetterli
and Kovacevic, 1995). The wavelet used for the
fast search is the simple Haar wavelet so that the
wavelet coecients of codewords are ®nite-preci-
sion numbers. Consequently, squared distance
calculation can be realized using additions. In our
algorithms, the addition-based squared computa-
tion is decomposed into a number of stages. The
PDS is also extended to these stages to further
reduce the addition complexity of the algorithm.
When all the stages for squared computation are
considered in PDS, the actual closest codeword to
each sourceword can always be found and the
rate-distortion performance is not degraded.
Moreover, by performing the PDS over smaller
number of stages, lower computational complex-
ity can be obtained at the expense of possible
slight degradation in average distortion. There-
fore, in our algorithms, in addition to be multi-
plication-free, the addition complexity is allowed
to be controlled to provide best trade o€ be-
tween computational complexity and rate-distor-
tion performance in accordance with the
application needs.
Fig. 1. The DWT of a vector x.
orientation selective highpass sub-vectors),
k ˆ n; . . . ; 1, are obtained recursively from
xLꢀk‡1† with xL0 ˆ x. The decomposition of xLꢀk‡1†
into four sub-vectors xLk; xVk; xHk; xDk can be car-
ried out using a simple quadrature mirror ®lter
(QMF) scheme as shown in (Vetterli and Kovac-
evic, 1995).
Now, suppose there are K codewords in the
codebook of a full-search VQ: y1; . . . ; yK, each one
with dimension 2n  2n. Let x be the sourceword
with the same dimension as these codewords. The
objective of the fast search algorithm for the full-
search VQ is to reduce the computational time for
®nding a codeword whose squared distance is
closest to the sourceword. That is, the algorithm
reduces the computational complexities for ®nding
yj , wherejà ˆ arg min1 6 j 6 KDꢀx; yj†; andDꢀu; v† ˆ
Ã
2. Preliminaries
P
N
iˆ1
2
ꢀui vi† is the squared distance between u
and v and N is the dimension of u and v.
In this section we review some basic facts of
wavelet transform (Vetterli and Kovacevic, 1995)
and the fast codeword search algorithm perform-
ing PDS in the wavelet domain (Hwang et al.,
1997). Let X be the n-stage discrete wavelet
transform (DWT) of a 2n  2n vector x. Then,
as shown in Fig. 1, X is also a 2n  2n vector
Let X and Yj be the n-stage DWT of x and yj,
respectively. It can be shown that Dꢀx; yj† ˆ
DꢀX; Yj†: Starting from the upper-left corner of
the DWT coecients, we index the elements of
vectors X and Yj in the zig-zag order as shown
in Fig. 2. Let Xi and Yij be the ith element of X
and Yj, respectively. Moreover, let DmꢀX; Yj† ˆ
containing sub-vectors xLꢀ
and xVk; xHk; xDk;
n†
P
m
iˆ1
ꢀXi Yij†2; m ˆ 1; . . . ; 2n  2n; be the partial
k ˆ n; . . . ; 1, each with dimension 2ꢀn‡k†
Â
distance between X and Yj. Since DꢀX; Yj† >
DmꢀX; Yj†, it follows that:
2ꢀk‡n†. Note that, in the DWT, the sub-vectors xLk
(lowpass sub-vectors) and xVk; xHk; xDk (V, H and D

W.-J. Hwang et al. / Pattern Recognition Letters 21 (2000) 399±405
401
codeword to x and the Dmin is the corresponding
distance.
3. Multiplication-free partial distance search in the
transform domain
Although performing PDS in the wavelet do-
main can signi®cantly reduce the computational
complexity without degrading rate-distortion per-
formance of VQs, multiplications are still required
for the algorithm. The objective of this letter
therefore is to present multiplication-free fast
search techniques which performs PDS in the
transform domain. In our algorithm, the Haar
wavelet is used to obtain wavelet coecients for
PDS. This is because the coecients in Haar do-
main are ®nite-precision numbers so that the
squared distance calculation for PDS can be real-
ized without multiplications. In addition, because
of the simplicity of the Haar wavelet, even the
®xed-point DSP processors can be e€ectively used
for implementing the transform without large
computational overhead.
Fig. 2. Zig-zag ordering of DWT coecients.
Dꢀx; yj† > DmꢀX; Yj†:
ꢀ1†
In particular, for m ˆ 1, we have Dꢀx; yj† >
ꢀX1 Y1j†2. It then follows that:
p
Dꢀx; yj† > jX1 Y1jj:
ꢀ2†
In the algorithm, before the search process,
we obtain the DWT of the codewords. To perform
the fast codeword search, ®rst we initialize the
current closest codeword to be yp, where p ˆ
arg minj D1ꢀX; Yj† and the current minimum dis-
tortion Dmin to be Dꢀx; yp†. For each codeword yj
Assume the elements in a vector x are q-bit in-
tegers. That is, if x is an element of x, then x can be
expressed as
1
2
x ˆ Xq 12q ‡ Xq 22q ‡ Á Á Á ‡ X020;
ꢀ3†
to be searched and we compute jY1j X1j. Suppose
p
where Xi; q 1 6 i 6 0, are binary numbers taking
only values of 0 or 1. Let X be an element of X in
the Haar domain. Based on Eq. (3), if X is located
in the subbands at intermediate resolution level k,
jY1j X1j >
D
min, it follows from Eq. (2) that
p
p
Dꢀx; yj† >
D
min. Hence, yj is not the closest
codeword to x and can be rejected. Suppose
p
(that is, X 2 fxHk; xVk; xDkg, where
ꢀn 1† 6
jY1j X1j <
D
min; then we perform the following
k 6 1) then X can be expressed as
PDS process. Starting from m ˆ 2, for each value
of m, m ˆ 2; . . . ; 2n  2n, we ®rst evaluate
DmꢀX; Yj†. Suppose DmꢀX; Yj† > Dmin; then from
Eq. (1), it follows that Dꢀx; yj† > Dmin and yj can
be rejected. Otherwise, we go to the next value of
m and repeat the same process. This PDS process
is continued until yj is rejected or m reaches
2n  2n. If m ˆ 2n  2n, then we compare DꢀX; Yj†
with Dmin. If DꢀX; Yj† < Dmin; then the current
minimum distortion Dmin is replaced by DꢀX; Yj†
and the current closest codeword to x is set to yj.
After all the codewords are searched, the ®nal
current closest codeword is the actual closest
k
1
k 2
X ˆ Xq 12q
‡ Xq 22q
‡ Á Á Á ‡ Xk2k;
k
k
ꢀ4†
1, are also binary num-
where Xi; k 6 i 6 q
k
bers taking only values of 0 or 1. Otherwise, if X is
located in the lowest resolution level, (that is,
X 2 fxLꢀ ; xHꢀ ; xV ꢀ ; xDꢀ g) then the number
n†
n†
n†
n†
of bits required for storing X becomes largest and
X can be expressed as:
1
2
n
X ˆ Xq‡n 12q‡n ‡ Xq‡n 22q‡n ‡ Á Á Á ‡ X n2
:
ꢀ5†

402
W.-J. Hwang et al. / Pattern Recognition Letters 21 (2000) 399±405
Given two vectors x and y, de®ne Am ˆ jXm Ymj,
where the indexing of DWT coecients are given
in Fig. 2. Suppose Xm and Ym are inside subbands
at resolution level k, then Am can be written as
q
k
1
q
k
1
r
1
X
X X
A2m ˆ
A2s 22s ‡ 2
ArAs2r2s:
ꢀ11†
sˆk
rˆk‡1 sˆk
Let
k
1
k 2
Am ˆ Aq 12q
‡ Aq 22q
‡ Á Á Á ‡ Ak2k;
k
k
q
k
1
X
C ˆ
A2s 22s
ꢀ12†
ꢀ13†
ꢀ6†
1 are binary numbers
sˆk
where Ai; k 6 i 6 q
k
and
taking only values of 0 or 1. When performing the
PDS, the computation of A2m is necessary. To
eliminate the requirement for multiplication when
computing A2m, in this letter we propose two tech-
niques: the usual partial product accumulation
(PPA) (Katz, 1995) and modi®ed PPA.
r
X
Cr ˆ
Ar‡1As2r‡s‡2
;
sˆk
where k 6 r 6 ꢀq
k
2†. We therefore can rewrite
A2m as
The PPA technique is based on the fact that
q
k
2
X
A2m ˆ C ‡
Cr:
ꢀ14†
k
1
A2 ˆ AmꢀAq 12q
‡ Á Á Á ‡ Ak2k†;
ꢀ7†
ꢀ8†
k
m
rˆk
q
k
2
X
A2m ˆ B ‡
Br;
Let S2 ˆ fC; Cr; k 6 r 6 q
k
2g be the set
rˆk
of elements for PDS for modi®ed PPA. Observe
that, Ck ˆ Ak‡1Ak22k‡2, which is the element
that contain least energy among the elements in
where
k
1
B ˆ AmAq 12q
and
ꢀ9†
k
S2, in general has much less energy than Bk ˆ
AkAm2k ˆ AkꢀAq 12q ‡ Á Á Á ‡ Ak22k†, which
1
k
Br ˆ AmAr2r:
ꢀ10†
is the element that contain least energy among the
elements in S1. In addition, the di€erence in en-
ergy between C and B, the elements that contain
highest energy in S2 and S1, respectively, is rel-
atively small. Therefore, S2 has higher discrep-
ancy in energy among its elements and can be quite
e€ective for PDS.
De®ne S1 ˆ fB; Br; k 6 r 6 q
k
2g. Since the
computation of elements in S1 require only shift
operations, multiplication is not necessary when
PPA is used for computing A2m. In addition, from
Eq. (8), it follows that A2m can be decomposed into
q
2k terms in which each term involves only the
In the following, we present the PDS technique
based on PPA and modi®ed PPA in more detail.
Suppose yj is the current codeword to be searched
computation of distinct single element in S1.
Therefore, the PDS can be extended over these
terms to further reduce the computational com-
plexity. From Eqs. (9) and (10), it is observed that
B and Br having larger r value in S1 have higher
energy than the other elements. Consequently,
these elements are scanned ®rst for PDS. It is
known that higher discrepancy in energy among
elements for PDS can result in higher eciency for
fast codeword search. Nevertheless, all the ele-
ments in S1 are simply the shifted version of Am,
and therefore the di€erence in energy among them
might not be large. To enhance the discrepancy in
energy, the modi®ed PPA is proposed for PDS.
In the modi®ed PPA, we ®rst note that, from
j
1†
and it has been found that Dꢀm ꢀX; Y † is less
than the current Dmin. In the original PDS in the
j
j
1†
transform domain, DmꢀX; Y † ˆ Dꢀm ꢀX; Y † ‡
2
ꢀXm Ymj † is computed and compared to current
Dmin. This operation requires one multiplication.
To eliminate the need for multiplications, we ®rst
2
let A2m ˆ ꢀXm Ymj † in the novel PDS algorithm.
Then, the PDS is extended over the computation
j
of A2m. That is, Dꢀm ꢀX; Y † ‡ D is ®rst compared
with Dmin, where D ˆ B when PPA is employed
and D ˆ C when modi®ed PPA is employed.
1†
j
1†
If Dꢀm ꢀX; Y † ‡ D > Dmin
,
it follows that
Dꢀx; yj† > Dmin and yj can be rejected. Otherwise,
2
Eq. (6), A2m ˆ ꢀXm Ym† can be expressed as
we start the following fast search process which

W.-J. Hwang et al. / Pattern Recognition Letters 21 (2000) 399±405
403
Step 1.
scans the elements having higher energy ®rst (that
is, the Br or Cr having higher index r value).
For simplicity, depending on whether PPA or
modi®ed PPA is used, we assume Dr ˆ Br (for
PPA), or Dr ˆ Cr (for modi®ed PPA). Starting
For any input source vector x, ®nd X.
Find initial current closest codeword yp;
where
p ˆ arg minj D1T ꢀX; Yj†.
Set initial current Dmin ˆ DT ꢀX; Yp†.
from i ˆ q
k
2, for each value of i, i ˆ
j
1†
1†
q
k
2; . . . ; k, we compare Dꢀm ꢀX; Y † ‡
Step 2.
P
i
j
For each codeword yj to be searched:
Set D0T ꢀX; Yj† ˆ 0.
D ‡
2 Dr with Dmin. If Dꢀm ꢀX; Y † ‡
rˆq
k
P
i
D ‡
2 Dr > Dmin, then we reject yj. Other-
wise, we go to next value of i and repeat the same
rˆq
k
For m ˆ 1 to 2n  2n do
Find the resolution level k of Xm and Ymj .
Compute Am ˆ jXm Ymj j.
Obtain D from Am.
process. This process is continued until yj is re-
j
jected, or i reaches k. If i ˆ k and Dꢀm ꢀX; Y † ‡
1†
P
k
D ‡
2 Dr < Dmin, then DmꢀX; Yj† < Dmin
.
rˆq
k
j
1
Set S ˆ DmT ꢀX; Y † ‡ D
If S > Dmin, then
Reject yj,
In this case. we increase the value of m by one and
the same PDS process for the computation of A2m is
executed. This process is continued until yj is re-
n
n
jected or DꢀX; Yj† ˆ D2 Â2 ꢀX; Yj† < Dmin is ob-
served. In the latter case, we replace the current
Dmin by DꢀX; Yj†. After all the codewords are
searched, the actual closest codeword to x are then
identi®ed.
Goto Step 3.
Endif
For r ˆ q
k
2 downto T ‡ 1
Compute Dr from Am
S S ‡ Dr
If S > Dmin, then
Reject yj,
The novel PDS technique can always ®nd the
closest codeword to each sourceword and there-
fore the average distortion for the encoding is not
increased. Nevertheless, the multiplication com-
plexity is eliminated at the expense of increase in
addition complexity. To further reduce the addi-
tion complexity, we can select an integer threshold
Goto Step 3.
Endif
Next r
DmT ꢀX; Yj† ˆ S.
Next m
Dmin DT ꢀX; Yj†
T, where k 1 6 T 6 q
k
2. During the PDS
current closest codeword yj.
process, for each m value, all the Drs having r 6 T
are ignored (note that D is always included for
PDS). Therefore, for a larger T value, addition
complexity can be signi®cantly reduced at the ex-
pense of slight increase in average distortion since
the actual closest codeword to each sourceword
might not be identi®ed by ignoring some Drs
for PDS. For simplicity, we de®ne A2mꢀT † ˆ D ‡
Step 3.
If all the codewords are searched, then stop,
Otherwise, goto Step 2.
4. Simulation results
P
P
q
k
m
rˆT‡21 Dr and DTmꢀX; Yj† ˆ iˆ1 A2mꢀT†. In addi-
In this section, we present some simulation re-
sults to demonstrate the e€ectiveness of the novel
PDS technique. The VQ used for encoding is de-
signed using the generalized Lloyd algorithm
(Linde et al., 1980). The number of codewords K in
the VQ is 1024 and the dimension of vectors is
23 Â 23. The training images for the VQ design are
three 512 Â 512 images ``Lena'', ``Pepper'' and
``Girl''. All the elements of codewords after VQ
design are quantized with an 8-bit scalar quantizer
(i.e., q ˆ 8).
n
n
tion, DT ꢀX; Yp† ˆ D2T Â2 ꢀX; Yp†.
A detailed outline for our algorithm is listed
below:
Initialization
Given:
DWT of codewords: fY1; Y2; . . . ; YKg,
Number of bits for each element in vec-
tors in the original domain: q,
Threshold for PDS: T.

404
W.-J. Hwang et al. / Pattern Recognition Letters 21 (2000) 399±405
Fig. 3 shows the addition complexity vs. PSNR
N ˆ 2n  2n is the vector dimension. The addition
complexity is measured on the images Lena, Pep-
per and Girl. From Fig. 3, it is observed that the
novel multiplication-free PDS technique based on
modi®ed PPA enjoys lower addition complexity
than the PDS technique based on PPA. This is
because the discrepancy in energy among the ele-
ments for PDS based on modi®ed PPA is higher
than that for PDS based on PPA. In addition, we
®nd that the degradation of the PSNRs for both
PPA and modi®ed PPA is quite small even for
highest T value. In particular, when T ˆ 9, all the
Drs are ignored for the PDS search and therefore
the maximum degradation in PSNR is achieved. In
this case, the PSNR for modi®ed PPA is only de-
graded by 0.17 dB (from 27.30 to 27.13 dB);
whereas, the reduction in addition complexity is
67.91% (from 54.60 to 17.52). These results dem-
onstrated the e€ectiveness of our algorithm.
for the novel PDS technique based on both PPA
and modi®ed PPA for various T value. The PSNR
is de®ned as PSNR ˆ 10 log 2552/(MSE of the re-
constructed images). The addition complexity Ca is
ꢀ
ꢀ
de®ned as Ca ˆ Za=ꢀ2N 1†, where Za is the av-
erage number of additions per sourceword and
For comparison purpose we also implement
the exhaustive search, the PDS in the original
domain (Bei and Gray, 1985) and the PDS in the
wavelet domain without eliminating multiplication
(Hwang et al., 1997) for VQ encoding. Table 1
shows the addition complexities, multiplication
complexities, time complexities and the PSNRs of
these algorithms. The multiplication complexity
ꢀ
ꢀ
Cm is de®ned as Cm ˆ Zm=N, where Zm is the av-
erage number of multiplications per sourceword.
The time complexity Ct of each codeword search
algorithm is de®ned as the total CPU time re-
quired for arithmetic operations of that algorithm
for the images to be encoded. The PC with Pen-
tium III 450 CPU is used for CPU time measure-
ment. All the complexities listed in the table are
measured on the images Lena, Pepper and Girl.
Fig. 3. The PSNR and additional complexity for the novel PDS
techniques based on PPA and modi®ed PPA for various T
values.
Table 1
Addition complexities, multiplication complexities, time complexities and PSNRs of various existing codeword search algorithms
Ca
Cm
Ct
PSNR
Exhaustive search
PDS (Bei and Gray, 1985)
1024
1024
50.49
4.55
0.91
1.09
0.34
0.57
0.27
0.19
27.30
27.30
27.30
27.30
27.23
27.30
27.16
27.13
89.87
85.32
16.28
PDS + wavelet (Hwang et al., 1997)
PDS + PPA + wavelet (T ˆ 4)
PDS + PPA + wavelet (T ˆ 9)
PDS + modi®ed PPA + wavelet (T ˆ 4)
PDS + modi®ed PPA + wavelet (T ˆ 6)
PDS + modi®ed PPA + wavelet (T ˆ 9)
24.82
103.69
32.27
54.60
24.81
17.52
0
0
0
0
0

W.-J. Hwang et al. / Pattern Recognition Letters 21 (2000) 399±405
405
From Fig. 3 and Table 1, it is observed that when
T P 6, the addition complexities of the novel PDS
technique based on modi®ed PPA are less than
those of all the other search techniques listed in
Table 1. In addition, the time complexities of the
novel PDS algorithm for all T values are lower
than those of all the other methods. Based on the
simulation results shown above, the novel PDS
technique therefore can be an e€ective alternative
for the applications where both real-time process-
ing and high PSNR performance are desired.
average distortion. Therefore, the algorithm can
be eciently used for the encoding of VQs having
high vector dimension and/or large number of
codewords.
References
Abut, H., 1990. Vector Quantization. IEEE Press, New York.
Bei, C.D., Gray, R.M., 1985. An improvement of the minimum
distortion encoding algorithm for vector quantization.
IEEE Trans. Commun. 33, 1132±1133.
Gersho, A., Gray, R.M., 1992. Vector Quantization and
Signal Compression. Kluwer Academic Publishers, Dordr-
echt.
5. Concluding remarks
Hwang, W.J., Jeng, S.S., Chen, B.Y., 1997. Fast codeword
search algorithm using wavelet transform and partial
distance search techniques. Electron. Lett. 33, 365±366.
Katz, R.H., 1995. Contemporary Logic Design. Benjamin/
Cummings, Menlo Park, CA.
We have shown that the PDS technique based
on modi®ed PPA in the wavelet domain is very
e€ective for multiplication-free fast codeword
search. While eliminating the requirements for
multiplication, the algorithm also signi®cantly re-
duces the addition complexity without increasing
the average distortion for VQ encoding. In addi-
tion, the algorithm can accelerate the encoding
process further by ignoring some insigni®cant
stages for PDS at the expense of a slight increase in
Linde, Y., Buzo, A., Gray, R., 1980. An algorithm for vector
quantizer design. IEEE Trans. Commun. 28, 84±95.
Paliwal, K.K., Ramasubramanian, V., 1989. E€ect of ordering
the codebook on the eciency of the partial distance search
algorithm for vector quantization. IEEE Trans. Commun.
37, 538±540.
Vetterli, M., Kovacevic, J., 1995. Wavelets and Subband
Coding. Prentice-Hall, Eaglewood Cli€s, NJ.