Adaptive Singular Value Extraction (ASVE) as a
Method of Image Compression
Mei Tian, Siwei Luo, Lingzhi Liao, Lianwei Zhao
School of Computer and Information Technology,
Beijing Jiaotong University, Beijing 100044, China
Abstract. In this paper we describe a neural network model-adaptive singular
value extraction(ASVE) for multiple singular value extraction based on an ex-
tension of the Hebbian learning rule, and then apply it to image compression.
The ASVE-based image compression scheme is based on the APEX–like algo-
rithm proposed by Diamantaras. The model is extracting the singular values
and in this paper we discuss applications in image compression. It is shown ex-
perimentally that the proposed scheme leads to good compression ratio and
satisfactory image quality.
1 Introduction
During the past couple of decades several neural network learning algorithms to ex-
tract the principal component subspace of a given random series have been put for-
ward [1, 2]. Whereas principal components can only be defined for square matrices,
there is an extension of the principal component analysis for arbitrary matrices,
namely the singular value decomposition (SVD). The SVD transformation has the
characteristic of optimal energy compaction in the least square sense [3]. The impor-
tant areas of application of SVD appear to be efficient storage of images in digital
form (., data compression) and image restoration. The PCA scheme needs to be
calculated only once for the whole image ensemble. However, the SVD transforma-
tion has to be calculated for each image. Consequently the SVD often is treated as a
potential transformation but is seldom used in practical applications.
In this paper, we present an adaptive singular value extraction (ASVE) scheme,
and apply it to image compression. This ASVE learning algorithms is based on the
subspace method in principal component analysis with the APEX–like algorithm
proposed by Diamantaras [4, 5]. Plugging the neural network learning algorithms into
the ASVE-based compression method, the proposed scheme leads to a good compres-
sion ratio and satisfactory image quality.
The rest of this paper is organized as follows. In Section 2, the background of SVD
and ASVE are described, respectively. Section 3 provides the ASVE-based image
compression method. In Section 4, some experimental results are illustrated to dem-
onstrate the effect of the proposed image compression scheme. Finally, some conclu-
sions are addressed in Section 5.
1
2 SVD and ASVE
In the SVD [6] an m by n matrix A is factored into
TA U V= Λ , (1)
Where U is an m by m orthogonal matrix with columns that are unit basis vectors
spanning the data space, mR . V is an n by n orthogonal matrix with columns that are
basis vectors spanning the model space, nR . Λ is an m by n diagonal matrix with
diagonal elements called singular values. The singular values along the diagonal of
Λ are customarily arranged in decreasing size, 1 2 min( , ) 0m nσ σ σ≥ ≥ ≥ ≥" . The
columns iu of U are the eigenvectors of
TAA with eigenvalue 2iσ , the columns iv
of V are the eigenvectors of TA A with eigenvalue 2iσ . The iσ are termed the
singular values of the matrix A , the iu and iv are the left and right singular vectors
of A , respectively.
The ASVE algorithm computes the SVD of a cross-correlation matrix A of two
input sequences kx and ky . Our analysis will start from extracting the first singular
value before extending it to the general case.
If x and y are random vectors with cross-covariance matrix ( )TA xy= Ε , consider
the two linear units with inputs nx R∈ , my R∈ , the outputs can be defined as
Ta w x= , (2)
Tb s y= , (3)
Where w and s are the weights of any one of the two units is based on the correlation
between the input and the output of the other one. An extension of the Hebbian learn-
ing rule called the cross-coupled Hebbian rule [4] that updates the weights
1k k k kw w b xβ+ = + , (4)
1k k k ks s a yβ+ = + , (5)
Since SVD is an extension of PCA, we can follow the standard Oja algorithm [7] and
normalize the weights after each iteration. In [4] it is shown that under suitable condi-
tions the algorithm satisfy
1 [ ]k k k k k kw w x w a bβ+ = + − , (6)
1 [ ]k k k k k ks s y s b aβ+ = + − , (7)
2
It’s obvious that Oja’s rule for single principle component extraction [7] becomes a
special case of the system (6), (7) for k ky x≡ .
Algorithm for extracting the first singular value is based on that the model maxi-
mizes the correlation
2 2
{ }
|| || || ||
k kE a bJ
w s
= , (8)
Which is equivalent to the maximizing the ratio
1
2 2
max max
|| || || ||n m
T
w R s R
s Aw J
w s
σ
∈ ∈
= = , (9)
The solution is known to be
1 1( , ) ( , )s w u vρ µ= , (10)
Where ρ and µ are any scalars other than zero [6].
Considering multi-component case, cf. [4] extends the above extracting the first
singular value algorithm as does the APEX algorithm [1] with the one-unit Oja-
algorithm for PCA. It can be achieved by a transformation on the data that so-called
deflation matrix
^Α
( )^ 1 1 1 1T Tu u I u uΑ = Α− Α = − Α , (11)
Except that the singular value 1σ is zero,
^Α has the same SVD as A. Thus, the sec-
ond singular value can be derived with the above algorithm.
The ASVE neuron model is depicted in It’s a multiple hidden units cross-
correlation network with lateral inhibition parameters.
3
. The ASVE network
3 ASVE-Based Image Compression
The fundamental concept of the ASVE-based image compression scheme is to use a
smaller number of singular values to approximate the original matrix. It is easily
verified that the singular value decomposition of an m by n matrix A can written as [8]
( )
1
rank
T T
i i i
i
U V u vσ
Α
=
Α = Λ = ∑ , (12)
The column vectors iu and iv are called singular vectors, and the matrix
T
i iu v is the
out product of the ith column of U with the corresponding column of V.
For a unitary n by n matrix the first column vector may be represented using n-1
components because of its unit length. The second vector may be represented using n-
2 components due to its unit length and being orthogonal to the first vector. Follow-
ing this argument the ith vector may be represented using n-i components. Hence,
That the orthogonality of the U and V matrices, makes it possible to present SVD
decompositions using 2n parameters [9].
The main motivation for using the ASVE in image compression is its energy com-
paction property and its ability to adapt to the variations in local statistics of an image.
Thus, we have a block adaptive transform coder where, for each block, the singular
values and the components of the singular vectors will have to be represented in a bit
efficient manner.
For a given covariance matrix A we construct 200 samples of pairs (X,Y) which
are normally distributed with cross-covariance matrix A. And then computes the SVD
of a cross-correlation matrix A of two input sequences kx and ky based on ASVE
method. A simple way to adaptively select the appropriate singular values to be used
in each image matrix is to specify the percentage of the sum of the singular values
instead of a fixed number. This scheme is derived from the observation of the distri-
bution of the singular values in each matrix. When a image matrix contains complex
image, its singular values are more "spread out" than the one that contain a simple
image. Thus if we specify a certain percentage of the sum to be used, a higher number
of ranks will be used for a complex block than the one with simple image.
4 Experimental Results
In this section, the popular "Lena" image (512 x 512, gray scale) is selected for test-
ing the ASVE-based image compression scheme. Instead of compressing the whole
image at once, we work on the sub-block of the original image. A further reduction
on the singular values is subtracting the mean of the original image before performing
4
the ASVE. The mean is then added back to the ASVE construction to obtain the
reconstructed image. This process essentially compact the distribution of the singular
values. Peak Signal to Noise Ratio（PSNR）is used to measure the effect of the
proposed scheme.
In the the PSNR denotes the image quality of the compressed Lena when ap-
plying the ASVE-based image compression method. shows the results of the
compression with the above scheme. In the experiment the block size is 8 by 8 and
the percentage is from 70 to 85.
. PSNR of the compressed Lena
ASVE-based image com-
pression
percentage PSNR
85
70
. Original and reconstructed Lena
As can be seen from and , It is observed that the proposed image com-
pression scheme can achieve good compression ratio and satisfactory image quality.
And the ASVE-based image compression scheme is feasible on condition of the
higher quality of image compression and the lower quantity of compression.
5 Conclusion
In this paper we present an adaptive singular value extraction (ASVE) scheme which
is based on the APEX–like algorithm proposed by Diamantaras [4,5], and apply it to
image compression. The ASVE-based image compression scheme leads to good com-
pression ratio and satisfactory image quality.
5
Acknowledgements: This paper is supported by the National Natural Science
Foundation of China under Grant Nos. 60373029 and the National Research Founda-
tion for the Doctoral Program of Higher Education of China under Grant Nos.
20020004020.
References
1. Kung S. Y., Diamantaras K. I.: A neural network learning algorithm for adaptive principal
component extraction (APEX). In Proceedings of the International Conference on Acoustics,
Speech and Signal Processing. IEEE, (1990) pages 961-964
2. Pierre F. Baldi, Kurt Homik: Learning in linear neural networks: A survey. IEEE Transac-
tions on Neural networks, 6 (4) (1995)837-858
3. Andrews H. C., Patterson C. L.: Singular value decomposition (SVD) image coding. IEEE
Trans. Commun, (1976) 425-432
4. Diamantaras K. I.: Principal Component Learning Networks and Applications. PhD thesis,
Department of Electrical Engineering, Princeton University (1992)
5. Kung S. Y., Diamantaras K. I.: Adaptive Principal Component Extraction (APEX) and ap-
plications. IEEE Transactions on Signal Processing, 42, (1994) 1202-1217
6. Gene H. Golub, Charles F. Van Loan: Matrix Computations. The Johns Hopkins University
Press, Baltimore, third edition (1996)
7. Oja E.: A simplified neuron model as principal component analyzer. Journal of Mathemati-
cal Biology, 15, (1982) 267-273
8. Alkiviadis G., Akritas, Gennadi I. Malaschonok: Applications of singular-value decomposi-
tion (SVD). Mathematics and Computers in Simulation 67, (2004) 15-31
9. Waldemar P.: Image compression Using Singular Value Decomposition. PhD thesis, Norwe-
gian University of Science and Technology (1997)
6
