**A high‑speed codebook design algorithm for** **ECVQ using angular constraint with search** **space partitioning**

著者 Swilem Ahmed, Imamura Kousuke, Hashimoto Hideo journal or

publication title

2004 IEEE International Conference on Multimedia and Expo (ICME)

volume 1

page range 371‑374

year 2004‑01‑01

URL http://hdl.handle.net/2297/6710

**A High-Speed Codebook Design Algorithm for ECVQ Using Angular ** **Constraint with Search Space Partitioning **

### Ahmed Swilem, Kousuke Imamura, Hideo Hashimoto *Kanazawa University, Japan *

*ahmed@gin.ec.t.kanazawa-u.ac.jp imamura,hasimoto@is.t.kanazawa-u.ac.jp *

**Abstract **

*In this paper, we propose a fast codebook *
*generation algorithm for entropy-constrained vector *
*quantization (ECVQ). The algorithm uses the angular *
*constraint and employs a suitable hyperplane to *
*partition the codebook and image data in order to *
*reduce the search area and accelerate the search *
*process in the codebook design. This algorithm allows *
*significant acceleration in codebook design process. *

*Experimental results are presented on image block *
*data. These results show that our new algorithm *
*performs better than the previously known methods. *

**1. Introduction **

Vector quantization (VQ) [1],[2] has played an important role in numerous data compression systems.

The key aspect of VQ is to design a good codebook which contains the most representative codewords and will be used by the encoder and the decoder. The encoding phase is equivalent to find the vector

minimizing the distortion defined as the
Euclidean distance between the vector and . The
decoding phase is simply a table look-up procedure
that uses the received index *i* to deduce the
reproduction codeword , and then uses to
represent the input vector .

, } ..., , ,

{*y*_{1} *y*_{2} *y*_{N}*Y* =

*Y*
*y*
*x*
*Q*( )= * _{i}* ∈

*x* *y*_{i}

*y**i*

)
,
(*x* *y*_{i}*d*

*y**i*

Entropy-constrained vector quantization (ECVQ) *x*
[3] employs a modified cost measure using both the
effective distortion of the signal and the expected
length of the transmitted code. We define the cost
function for encoding the vector x by the codeword
as the Lagrangian function,

, (1)

*y**i*

) ( ) , ( ) ,

(*x* *y*_{i}*d* *x* *y*_{i}*R* *y*_{i}

*J* = +λ

where is a constant called the Lagrange multiplier allowing to control the rate-distortion ratio and is the length of the codeword .

λ *R*(*y** _{i}*)

*y**i*

The computational cost of finding the best suitable codeword in the codebook design and encoding

imposes practical limits on the codebook size N. When
*N becomes larger, the computational complexity *
problem occurs for full codebook search. This has
motivated the development of many fast nearest
neighbor search algorithms [4]-[7]. These algorithms to
reduce search complexity concentrate on narrowing the
area of the candidate codewords for which distortion
must be calculated. The well known acceleration
methods for nearest neighbor search for ECVQ are the
double annulus method [5] and Cardinal method [6].

This paper introduces a new algorithm to reduce the time complexity of codeword search for ECVQ. The proposed algorithm employs the projection angles of input vectors and codewords to a reference line in the signal space. It also uses a hyperplane partitioning rule, which separates the codebook and the training vectors into two parts, and searches in only one part according to the vector feature. The searching in this method speeds up the codebook design process with a negligible small sacrifice of encoding quality.

**2. Previous works **

**2.1. Double annulus method **

Johnson et al. [5] introduced an excellent method called the double annulus method for ECVQ using two annular constraints, and tried to search only those codewords lying in their overlapped area. The first annulus is centered at the origin that is the first reference point. For a given input vector of distance

from the origin and a current best codeword with Lagrangian distortion , any closer codeword to than in the sense of the Lagrangian cost measure will satisfy the following relationships:

*x*

||

||*x* *y*_{i}

)
,
(*x* *y*_{i}*J*
*y**j* *x* *y*_{i}

) , (

||

||

) (

||

||*y** _{j}* +λ

*R*

*y*

*<*

_{j}*x*+

*J*

*x*

*y*

*, (2) and ||*

_{i}*y*

*||−λ*

_{j}*R*(

*y*

*)>||*

_{j}*x*||−

*J*(

*x*,

*y*

*), (3) where ||| is the Euclidean distance of from the origin, and is the length of the codeword . Thus, for any codeword satisfying (2) and (3), the hypersphere centered at with radius must*

_{i}*j* |
*y*

*R* *y*^{j}

(*y*
*R*
)

(*y*_{j}*y*_{j}

*y**j*

*y**j* λ * _{j}*)

0-7803-8603-5/04/$20.00 ©2004 IEEE.

then belongs to the upper half-space.

By using (7) and (8), The hyperplane H separates the training vectors into lower and upper sub-groups.

Moreover, it divides the codebook into lower and upper sub-codebooks. Searching for the training vectors in the lower sub-group is carried out in the lower sub-codebook and for the training vectors in the upper sub-group in the upper sub-codebook. Hence, this technique accelerates the search process.

**3. The proposed method **

**3.1. Angular constraint**

As we mentioned in the last section, the first annulus constrains the search region by two inequalities (2) and (3). For any codeword satisfying (2) and (3), the hypersphere centered at with radius must be fully contained in the annulus region defined by and || . Additional another constraint in our method is as follows.

Let l be a reference line in the search space and it
contains a unit vector on it. For any
vector *z, we define the angle between z and the *
reference vector u as:

. (9)
Because the values of all vector components are
nonnegative, then the angle _{4} . The angle is
called the projection angle to the reference line l. We
define another angle between the input vector x and the
tangent from the origin to the hypersphere centered at x
**Figure 1. Geometrical interpretation of double **

** annulus method in 2-dimensional case.**

be fully contained in the annulus defined by

and || .

The second annulus is centered at the farthest codeword from the origin, which is the second reference point, . By using the distance to this

eword, the following inequalities can be defined:

) , (

||

||*x* +*J* *x* *y*_{i}*x*||−*J*(*x*,*y** _{i}*)

*y**r*

cod

, (4) and

. (5) )

, ( ) , ( ) ( ) ,

(*y*_{j}*y*_{r}*R* *y*_{j}*d* *x* *y*_{r}*J* *x* *y*_{i}

*d* +λ < +

) , ( ) , ( ) ( ) ,

(*y*_{j}*y*_{r}*R* *y*_{j}*d* *x* *y*_{r}*J* *x* *y*_{i}

*d* −λ > −

The inequalities (2), (3), (4) and (5) constrain the
distortion calculation to the codeword whose
hypersphere is completely contained in the search
region shown in Figure 1. Using two annulus
constraints reduces the search area than using one
annulus constraint, but the double annulus method
requires additional calculation in every
iteration during the codebook design process. *d*(*x*,*y** _{r}*)

**2.2. Hyperplane decision rule **

Most nearest-neighbor search techniques employ searching the best codeword in the same search region for all training vectors. We introduced a technique using a hyperplane to divide the signal space into two half-spaces according to the vector feature in [7].

The chosen hyperplane is perpendicular to the central line, which contains a unit vector

on it. H contains the centroid of the

training vectors and its

projection point on the central line

### ,

where is the mean value of . The hyperplane H can be expressed as:*H*
*H*
*k*

*u*=(1,1,...,1)/

)
...,*m*_{xc}

)
...,
,
,*x*_{c}_{2} *x*_{ck}

=

*x**p* =
(*x*_{c}_{1}

*x**c*
*xc*

,
,
(*m*_{xc}*m*_{xc}

*x**c*

*m*

*i=1* . (6)
This hyperplane is used as a decision function that
discriminates to which half-space a given vector
belongs by the following conditions:

*xc*
*k*

*k* *ci*
*c**T*

*T* *ux* *x* *k* *m*

*z*
*u*

*H*^{:} = = ^{1}

### ∑

=*H*

*x*

**Figure 2. Geometrical interpretation of angular **
**constraint method in 2-dimensional case.**

)
,
(*x**y**i*
*J*

θ*x*

θ*x*

α*x*
*y**j*

α

*y**j*

θ
*y**j*

)
(*y** _{j}*
λ

*R*

*o*

) , (

||

||*x* +*J**x**y**i*
)
,
(

||

||*x* −*J* *x**y**i*
*x*

*x* θ

α −

*x*

*x* θ

α +

*j*

*j* *y*

*y* θ

α +

*j*

*j* *y*

*y* θ

α −

*z*1
*z*2

*u*
)

,
(
)
,
(*x**y*_{r}*J**x**y*_{i}

*d* −

*y**r*

) , (

||

||*x* +*J**x**y*_{i}

) , (

||

||*x* −*J**x**y*_{i}

)
(*y** _{r}*
λ

*R*

•

•

) , ( ) ,

(*x**y*_{r}*J**x**y*_{i}

*d* +

)
,
(*x**y*_{i}*J*
*y**i*

*y**j*

•
*x*

•

o

• If *u* ^{1} ^{k}_{i}* _{xc}*, (7)

*k*

*T* *x* *km*

*x* =

### ∑

<*x* ^{i}^{=}^{1}

then belongs to the lower half-space.

• If *u* , (8)

1

1 *xc*

*k*

*i* *i*

*k*

*T* *x* *km*

*x* =

### ∑

≥*x* =

*y**j*

*y**j*

||−*J*

)
(*y** _{j}*
λ

*R*)

, (

||

||*x* +*J* *x* *y*_{i}*x* (*x*,*y** _{i}*)

*k*

*u*=(1,1,...,1)/

||

cos ^{1} ||

*z*
*z*

*z* = − *u*

α ^{T}

]
,
0
[ ^{π}

α∈ α

Origin

Search region

*l *

*x*
*y**i*
*y**j*

θ

Search region

with radius , where is the current best
codeword, as: *J*(*x*,*y** _{i}*)

*y*

_{i}sin )

*x* = −

θ

*j*

||

*j*)

*x*,
θ
θ*x*
*y** _{j}* sin

θ =

α*y*
*y*
*y** _{j}* θ

_{j}α +

*y*
*y** _{j}* θ

_{j}α −

*H*

*Y**lw*

*Y**up*

||

||

,

1 (
*x*

*y*
*x*

*J* _{i}

. (10)

By the same way, we can define the angle between any
codeword and the tangent from the origin to the
hypersphere centered at *y* with radius as:

*y**j* λ*R*(*y** _{j}*)
λ

*R*

. (11)

Figure 2 shows the geometrical interpretation of the angular constraint method in 2-dimensional case. For a given input vector x with its projection angle to the reference line l and the closest codeword with its projection angle , the following inequalities should be satisfied:

||

1 (
*y**j*

− *y*

α*x*

*y**j*
*j*

(12)

and <α* ^{x}*+

α*x*−

> . (13)

The inequalities (2), (3), (12) and (13) constrain the distortion calculation to the codeword whose hypersphere is completely contained in the search region shown in Figure 2.

**3.2. Angular constraint with hyperplane **
** decision rule **

In this section, we develop the angular constraint method by using the hyperplane decision rule defined in section 2. L. Guan and M. Kamel [4] studied the distribution of some images data and found that most images data vectors are located around the diagonal or the central line. Hence, only a small portion of vectors will be near to the chosen hyperplane . Then the possibility for the hypersphere centered at the input vector to cross over this hyperplane is small. As a result, failure in best codeword searching becomes to be less even if searching is performed in either half-space dependent on the input vector feature.

Now we depict the proposed method that uses the
hyperplane to separate both the training vectors and
the codewords. The proposed method divides the
training vectors into two sub-groups *T* and T , and
each sub-group contains the vectors satisfying (7) or
(8), respectively. Also, it divides the codebook into two
sub-codebooks , and *Y* by the same equations.

Searching for the training vectors in the sub-group *T*
is carried out in the sub-codebook *Y* and for the
training vectors in the sub-group T in the sub-
codebook , by using the constraints in the
inequalities (2), (3), (12) and (13). Hence, the proposed
method can reduce the search area and speed up the
search process. The proposed method may be easily
understood with the geometrical interpretation for 2-
dimensional case in Figure 3. This figure includes the

*H*

*lw*

*lw*
*up*

*up*

*up*

*lw*

**Figure 3. Geometrical interpretation of angular **
**constraint with hyperplane decision rule **

)
,
(*x**y**i*
*J*

θ*x*

θ*x*

α*x*

*o* ||*x*||+*J*(*x*,*y** _{i}*)

) , (

||

||*x* −*J**x**y*_{i}*x*

*x* θ

α −

*x*

*x* θ

α +

*z*1
*z*2

*u*

*x*

*y**i*

**method in 2-dimensional case. **

proposed hyperplane . The hyperplane divides the signal space into two half-spaces, and each half- space includes its own training vectors and codewords.

*H* *H*

**4. Experimental results **

Experiments were carried on vectors taken from the USC grayscale image set. We used Lena image with size 512

### ×

512 and 256 gray levels. The image was divided into 4### ×

4 blocks, so the training set has 16384 blocks. The tested methods are full search (FS), double annulus (DA), Cardinal (CARD) [6], which is the most acceleration method for ECVQ, and angular constraint with hyperplane decision rule (ANGHP). Figure 4 shows the PSNR comparison between the FS method and the ANGHP method for codebook sizes (32, 256 and 1024) at various values of (0.5, 2, 4 and 8) with Lena image. Although the ANGHP method is a lossy design method, it has almost the same performance as the FS method at larger codebook size. For example, the performance of the ANGHP method is only 0.073 dB less than the FS method at codebook size 256, and this value decreases by increasing the codebook size.There is a small degradation for smaller codebook size;

for example, the ANGHP method has 0.141 dB less than the FS method at codebook size 32. This is because the best codeword happens to be in the other half-space and is missed to be searched out. However, there may be a small failure possibility in the case of large codebook size and smooth codebook distribution.

Figure 5 presents a comparison of the execution time (in seconds) with different codebook sizes at = 0.5.

λ

λ

*l*

*y**i* ||*x*||−*J*(*x*,*y**i*)

) , (

||

||*x* +*J**x**y*_{i}*x*

*x**c*
*x**p*

*H*

8 16 32 64 128 256 512 1024 2048 0

2 4 6 8 10 (x 106 )

λ = 0.5

Total number of distortion calculations

Codebook size DA

CARD ANGHP

0.1 0.2 0.3 0.4 0.5 0.6 0.7

26 27 28 29 30 31 32 33 34 35 36

FS ANGHP

N = 32

N = 256 N = 1024

λ = 8 λ = 4

λ = 2 λ = 0.5

PSNR (dB)

Rate (bits/pel)

The timings were made on Pentium III (866 MHZ).

The ANGHP method reduces the time around to 51%

of the DA method and 65% of the CARD method. It can be seen that as the codebook size increases, the efficiency of the ANGHP method increases. This is an important merit of the ANGHP method, because design of a larger codebook requires more intensive computation. Figure 6 shows the total number of distortion calculations, which is a dominant figure of the computational complexity, for Lena image at = 0.5. The total number of distortion calculations of the ANGHP method is around to 48% of that of the DA method and 63% of that of the CARD method. From those results, only a small number of distortion calculations are carried out in the ANGHP method.

λ

**5. Conclusions **

In this paper, we have proposed a new algorithm of accelerating the codebook design for ECVQ. The proposed algorithm (ANGHP) uses a new constraint called angular constraint. This constraint employs the

projection angles of the vectors to a reference line in the signal space. Moreover, the ANGHP method utilizes a hyperplane decision technique for separating the training vectors and the codebook into two sub- groups, and carries on searching within one sub-group according to the vector feature. The obtained results show that the ANGHP method is more efficiency than the DA method and the CARD method. Furthermore, the performance of the ANGHP method is quite close to that of the FS method.

**6. References **

[1] Y. Linde, A. Buzo, and R. M. Gray, “An algorithm for vector quantizer design”, IEEE Trans. Commun., vol.

COM-28, Jan. 1980, pp. 84-95.

[2] A. Gersho and R. M. Gray, “Vector quantization and signal compression”, Boston, Kluwer, 1991.

[3] P. A. Chou, T. Lookabough, and R. M. Gray, “Entropy- constrained vector quantization”, IEEE Trans. Acoust., Speech, Signal Process., vol. 37, Jan. 1989, pp. 31-42.

[4] L. Guan and M. Kamel, “Equal-average hyperplane partitioning method for vector quantization of image data”, Pattern Recognition Letters, vol. 13, no. 10, Oct.

1992, pp. 693-699.

[5] M. H. Johnson, R. Ladner and E. A. Riskin, ”Fast nearest neighbor search for ECVQ and other modified distortion measures”, Proc. ICIP-96, vol. 3, Sept. 1996, pp. 423-426.

[6] J. Cardinal, “Fast search for entropy-constrained VQ”, Proc. ICIAP-99 the 10 International Conference on Image Analysis and Process., Sept. 1999, pp. 1038- 1042.

th

[7] A. Swilem, K. Imamura, and H. Hashimoto, “A fast
search algorithm for ECVQ based on hyperplane
partitioning rule”, Proc. IEEE INES 2003 7^{th}
International Conference on Intelligent Engineering
Systems, vol. 2, Mar. 2003, pp. 704-709.

**Figure 4. Comparison of PSNR for Lena.** **Figure 6. Comparison of total number **
**of distortion calculations for Lena. **

8 16 32 64 128 256 512 1024 2048 0

5 10 15 20 25

λ = 0.5

Time (s)

Codebook size DA

CARD ANGHP

**Figure 5. Comparison of execution time for**
**Lena. **