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 .
, } ..., , ,
{y1 y2 yN Y =
Y y x Q( )= i ∈
x yi
yi
) , (x yi d
yi
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)
yi
) ( ) , ( ) ,
(x yi d x yi R yi
J = +λ
where is a constant called the Lagrange multiplier allowing to control the rate-distortion ratio and is the length of the codeword .
λ R(yi)
yi
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 yi
) , (x yi J yj x yi
) , (
||
||
) (
||
||yj +λR yj < x +J x yi , (2) and ||yj||−λR(yj)>||x||−J(x,yi), (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
j | y
R yj
(y R )
(yj yj
yj
yj λ 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 constraintAs 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 yi x||−J(x,yi)
yr
cod
, (4) and
. (5) )
, ( ) , ( ) ( ) ,
(yj yr R yj d x yr J x yi
d +λ < +
) , ( ) , ( ) ( ) ,
(yj yr R yj d x yr J x yi
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,yr)
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)/
) ...,mxc
) ..., , ,xc2 xck
=
xp = (xc1
xc xc
, , (mxc mxc
xc
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 cT
T ux x k m
z u
H: = = 1
∑
=H
x
Figure 2. Geometrical interpretation of angular constraint method in 2-dimensional case.
) , (xyi J
θx
θx
αx yj
α
yj
θ yj
) (yj λR
o
) , (
||
||x +Jxyi ) , (
||
||x −J xyi x
x θ
α −
x
x θ
α +
j
j y
y θ
α +
j
j y
y θ
α −
z1 z2
u )
, ( ) , (xyr Jxyi
d −
yr
) , (
||
||x +Jxyi
) , (
||
||x −Jxyi
) (yr λR
•
•
) , ( ) ,
(xyr Jxyi
d +
) , (xyi J yi
yj
• 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 =
yj
yj
||−J
) (yj λR )
, (
||
||x +J x yi x (x,yi) k u=(1,1,...,1)/
||
cos 1 ||
z z
z = − u
α T
] , 0 [ π
α∈ α
Origin
Search region
l
x yi yj
θ
Search region
with radius , where is the current best codeword, as: J(x,yi) yi
sin )
x = −
θ
j
||
j)
x, θ θx yj sin
θ =
αy y yj θ j
α +
y yj θ j
α −
H
Ylw
Yup
||
||
,
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:
yj λR(yj) λ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 ( yj
− y
αx
yj 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
) , (xyi J
θx
θx
αx
o ||x||+J(x,yi)
) , (
||
||x −Jxyi x
x θ
α −
x
x θ
α +
z1 z2
u
x
yi
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
yi ||x||−J(x,yi)
) , (
||
||x +Jxyi x
xc xp
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 7th 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.
