|Home | About | Journals | Submit | Contact Us | Français|
Color image compression is a commonly used process to represent image data as few bits as possible, which removes redundancy in the data while maintaining an appropriate level of quality for the user. Color image compression algorithms based on quaternion are very common in recent years. In this paper, we propose a color image compression scheme, based on the real SVD, named real compression scheme. First, we form a new real rectangular matrix C according to the red, green and blue components of the original color image and perform the real SVD for C. Then we select several largest singular values and the corresponding vectors in the left and right unitary matrices to compress the color image. We compare the real compression scheme with quaternion compression scheme by performing quaternion SVD using the real structure-preserving algorithm. We compare the two schemes in terms of operation amount, assignment number, operation speed, PSNR and CR. The experimental results show that with the same numbers of selected singular values, the real compression scheme offers higher CR, much less operation time, but a little bit smaller PSNR than the quaternion compression scheme. When these two schemes have the same CR, the real compression scheme shows more prominent advantages both on the operation time and PSNR.
An image is one of the most important information carriers involved in various areas such as medical imaging, defense, artwork, etc. The increasing use of digital images has raised the issue of storage and transmission. Compression is a commonly used process to represent image data as few bits as possible through exploiting redundancy in the data while maintaining an appropriate level of quality for the user [1–3]. Research on the technology of image compression began with digital TV signal in 1948. Over the past 70 years, a lot of gray-scale image compression method has been developed. However, due to rapid applications of the color image technique in the internet, researchers have turned their attention to color image compression [4, 5]. Compared with the gray-scale image, the color image can greatly improve the capacity and fidelity of the information. It can be broken into multiple prime color channels, so the color image compression is more challenging comparing to compression of single channel gray-scale images. There are various techniques available in literatures for color image like YCbCr, RGB, YIQ and HSI, among which, RGB is apparently the most popular space, because this channel format is the most natural for representing color in the real world. Each of the three channels R, G and B is highly correlated with the other two.
One of the typical algorithms for color image compression is multichannel compression. For example, in , a color image is first decomposed into single color channels which are treated independently, The essence of this approach is to treat gray-scale image. Because there are strong links between each channel of a color image, to do so, it can not reflect the connection between the channels very well. Algorithms based on quaternion are very common in recent years. A pixel of a color image can be viewed as a quaternion number. So a color image can be considered as a quaternion matrix. If a color pixel is processed in a holistic manner, then the relationship of spectrum between the color channels will run throughout the processes of operation and processing. The color information will not be lost. But we must notice that, these kind of algorithms require much more operations. In addition, we also can construct a new real matrix with the components of a color image. In order to achieve the purpose of color image compression, we only need to deal with the real matrix. To some extent, it is not only keep the connection between the color channels, but also fully control the computational complexity.
Compression algorithms utilizing the Singular Value Decomposition(SVD) became more and more popular [5–11]. In , authors converted the RGB image into YCbCr format and then compressed the image by applying the SVD to each of the three components, brightness Y, blue chrominance Cb and red chrominance Cr. In , authors proposed an image compression technique based on the SVD and DCT. In [9, 10], the whole image was divided into several equal size of sub-blocks and the SVD was implemented on each sub-block. In , authors proposed a algorithm automatically select an appropriate number of singular values on each sub-block by studying the relationship between the required PSNR value and the number of singular values.
In this paper, we will propose the real SVD-based color compression scheme, named real compression scheme. We will compare this scheme with quaternion SVD-based scheme. In order to improve the speed of quaternion SVD, we adopt the real structure-preserving algorithm [12, 13]. We will compare the visual and quantitative results of these two color image compression schemes such as PSNR, CR, storage and computing speed. The rest of this paper is organized as follows. In Section 2, we present a brief overview regarding the SVD and quaternion representation of a color image. In Section 3, we introduce two kinds of SVD algorithms and compare their computing speed. In Section 4, we introduce two SVD-based color image compression scheme. The experimental results and analysis on speed, compression effect are presented in Section 5. Finally, our conclusion are stated in Section 6.
Throughout this paper, Let ℝ be the real number field, ℚ the quaternion skew-field. For any matrix A, AT and AH represent the transpose and conjugate transpose of A, respectively. ℝm×n and ℚm×n are the set of all m × n real matrices and the set of all m × n quaternion matrices. A(:, s), A(:, s:t) denote all the rows, the sth column and the columns from the sth to the tth of matrix A, respectively.
The SVD of an m × n matrix A is expressed as
where both Um × m and Vn × n are unitary matrices and
Σ1 = diag(σ1, σ2, …, σr), σ1 ≥ σ2 ≥ … ≥ σr > 0 are positive singular values of A, and r is the rank of matrix A. If A is a real matrix, then both Um × m and Vn × n are real orthogonal matrices and
The SVD of a quaternion matrix was theoretically derived in 1997 by Zhang . Now the SVD of a quaternion matrix is also widely used in color image processing. The main advantage of the SVD is that it localizes most of the energy content of the matrix into few singular values. As σ1 is the maximum value, its significance in describing image feature is highest. Values of the diagonal elements of Σ are decrease, and so also their significance in describing image features. The singular values of the matrix decrease quickly with the increasing rank. We can compress the matrix data by eliminating the small singular values with this property, and it will not significantly reduce the visual quality of the image.
First, we recall some basic properties about quaternion and quaternion matrices.
A quaternion q ∈ ℚ is constituted of one real part and three imaginary parts
where a, b, c, d ∈ ℝ, and three imaginary units i, j, k satisfy
When the real part a = 0, q is called pure imaginary quaternion. Quaternion are an extension of complex numbers from 2D plane to the 3D space or 4D space. The quaternion skew-field ℚ is an associative but non-commutative algebra of rank four over ℝ. Many scholars have carried on thorough and careful research in the quaternion theoretical area. For example, [12, 13, 16–20] discussed several different kinds of problems of quaternion matrices such as algorithms for qLS problem, Householder based transformations and qSVD, quaternion Hermitian eigenvalue problems, quaternion LU decomposition, quaternion matrix equations and etc.
In , Sangwine proposed to encode the three channel components of a RGB image on the three imaginary parts of a pure imaginary quaternion, that is
where r(x, y), g(x, y) and b(x, y) are the red, green and blue components of the pixel at position (x, y), respectively. Thus, a color image with m rows and n columns can be represented by a pure imaginary quaternion matrix
Since then, quaternion representation of color image has attracted great attention. Many researchers applied the quaternion matrix to study the problems of color image processing due to its capability to treat the three color channels holistically without losing color information.
For a quaternion matrix A ∈ ℚm×n of a color image, we can perform the quaternion SVD with different kinds of algorithms. For example, in , authors provided the function ‘svd’ in Matlab Toolbox using quaternion arithmetics. In [12, 13], authors proposed a real structure-preserving algorithm based on the following results.
The properties of AR are as follows.
Theorem 3.1.  Let A, B ∈ ℚm×n, C ∈ ℚn×s and a ∈ ℝ. Then
From (3.1) and Theorem 3.1, for the matrix AR, we only need to store the first column block of AR, denoted as
From this notation and Theorem 3.1, we have the following result.
THEOREM 3.2. Let A, B ∈ ℚm×n, C ∈ ℚn×s, q ∈ ℚm and a ∈ ℝ. Then
In addition, we have the following results about the SVD of a quaternion matrix and its real representation.
THEOREM 3.3. Let A ∈ ℚm×n. Then the singular values of AR appear in fours.
Therefore, if we want to compute the SVD of a m × n quaternion matrix A, then we can deal with the SVD of the 4m × 4n real representation matrix AR. In fact, under the orthogonal transformations, the real representation of a quaternion matrix have the standard form stated in the next theorem.
THEOREM 3.4.  Suppose that A ∈ ℚm×n and AR is the real representation of A. Then there exist orthogonal matrices U ∈ ℝ4m×4m and V ∈ ℝ4n×4n such that
where D ∈ ℝm×n is a bidiagonal matrix.
From Theorem 3.3 and 3.4, the SVD of AR can be obtained by computing the SVD of bidiagonal matrix D. So, we should first get bidiagonal matrix D using Householder based transformation. In , we listed three forms Householder based transformations appeared in literatures and proposed a new form of quaternion Householder based transformation. And then, we gave the real structure-preserving algorithms for these quaternion Householder based transformations. By comparison on computation amounts and assignment numbers, we obtained the most flexible and efficient one which is described as follows.
THEOREM 3.5. Suppose that 0 ≠ y ∈ ℚn is not a multiple of e1, denote , where
, and H = αM(I − 2uuH), then H maps y to |α|e1.
After the bidiagonal matrix D is calculated, we can perform a sequence of iterations using Givens rotations on it, then the SVD of quaternion matrix is obtained.
On the other hand, we can extract the three imaginary parts R, G and B of matrix A to rearrange as a new real rectangle matrix
then directly use the function ‘svd’ on the real matrix C.
REMARK 3.1. In Table 1 we list the numbers of real flops and assignment numbers for computing real SVD for C ∈ ℝ3m×n and quaternion SVD for A ∈ ℚm×n using real structure-preserving algorithm, where assignment numbers refer to call subroutines or perform matrix operations. In matrix operations, say, B = AX + Y, we adopt the assignment B = A * X + Y to utilize vector pipelining arithmetic operations rather than explicitly using triply-nested for-end loops, to speed up computations remarkably. Therefore, real arithmetic numbers as well as assignment numbers are important measures. See, e. g., Charter 1 of .
We now provide a numerical example to compare the efficiency of the three algorithms mentioned above. All these computation are performed on an Intel Core i5@ 2.20Ghz/8GB computer using MATLAB R2013a.
Example 3.1. For k = 1:50, m = 10 * k, A ∈ ℚm×m, we apply the above three different algorithms to compute the SVD. We compare the CPU times of three algorithms: qSVD in toolbox for A , the structure-preserving SVD for A and the real SVD for C.
In [12, 13], we have already shown that structure-preserving algorithm is superior to quaternion command ‘svd’ in Matlab. Fig 1 shows that the CPU time of the real SVD algorithm for C is the smallest. Especially, when the matrix is bigger, its superiority is more obvious.
From the above discussion and Fig 1, we see that the algorithm performing the SVD for C is most efficient. In next section, we will introduce two kinds of color image compression schemes based on the real SVD for C and quaternion SVD for A, respectively.
In this section, we describe two SVD-based color image compression schemes. Assume that original image A is a RGB color image of size N × N.
We can form a new real rectangle matrix composed by the red, green and blue components of color image, and accordingly we obtain the real compression scheme. The detail is described as follows.
Step1. Pre-processing on color image compression
First, the original RGB color image A is broken into its different constituent components by dimension reduction treatment. Then we obtain the 2-D component matrices R, G and B. Next, the R, G and B color components matrices are rearranged as a rectangle matrix of 3N × N.
Step2. Performing real SVD for C
We perform the real SVD for C: where ΣC = diag(σ1, , σN).
Step3. Color image compressing
Assume q is a integer and q < N, denote
By removing the small singular value data, we get a new matrix CC. We can extract the corresponding rows as the R, G and B components and form a 3-D color image again. Then a compressed image is constructed.
Except for the real compression scheme above mentioned, we can reconstruct a compressed color image by implementing quaternion SVD for A using real structure-preserving algorithm as follows.
Step1. Performing quaternion SVD for A using real structure-preserving algorithm
First, we form the real representation of A
and then take out the first column block of AR, denoted as We perform real structure-preserving algorithm to get the SVD of A: where ΣA = diag(σA1, , σAN).
Step2. Color image compressing
Assume q is a integer and q < N, denote
By removing the small singular value data, we get a new quaternion matrix AC. Since the quaternion matrix of a color image is pure imaginary, we modify the real part of AC as zero matrix to get a pure imaginary quaternion matrix , which is corresponding to the compressed color image.
In this section, we carry out four experiments with different original images  to evaluate the effectiveness of the above two compression schemes. All the computation are performed on an Intel Core i5@ 2.20Ghz/8GB computer using MATLAB R2013a.
Example 5.1. Color image Pepper of size 512 × 512 is taken as the original image, shown in (a) of Fig 2. The compressed images with q = 16, 32, 64, 128 using real compression scheme are shown in (b) − (e) of Fig 2. The corresponding images are shown in (f) − (i) of Fig 2 using quaternion compression scheme.
From Fig 2, we observe that the visual effect of compressed images are similar with the same q in these two compression schemes. We will use several different quantitative criteria to judge the effect of compression algorithm, PSNR, CR and speed.
The visual fidelity can be measured by calculating two types of parameters known as Mean Square Error(MSE) or Peak Signal to Noise Ratio(PSNR) [25, 26] between the original image A and the compressed image Mean Square Error(MSE) is defined as
and Peak Signal to Noise Ratio (PSNR) is defined as
where A is a matrix of size N × N, max A(x, y, k) represents the maximum pixel value of a color image, and here it is 255. A(x, y, k) and are the pixel values location at position (x, y, k) in the original image and the compressed image, respectively. In general, the lower MSE or the larger PSNR means better image quality.
Compression Ratio(CR) is a term that is being used to describe ratio of compressed image to the original image defined as
where K is the size of compressed image. We can use CR to judge how compression efficiency is, as higher CR means better compression.
Compression speed is influenced by computational complexity and size of storage. Computational complexity is an important factor that any commercial entity would take into consideration, particularly if the volume of images is significant.
Table 2 is showing the quantitative comparison and compression ratio of the two techniques with different q, the numbers of selected singular values. In all the following Tables, PSNR1, SIZE1, CR1 and CPU1 stand for the corresponding values of real compression scheme, PSNR2, SIZE2, CR2 and CPU2 stand for the corresponding values of quaternion compression scheme.
From Table 2, we observe PSNR values obtained by these two schemes have little difference when the numbers of selected singular values are same, while the real scheme is much faster than the quaternion one. This is one of the advantages of real compression scheme. In fact, assume that the SVD of C is as described in step 2 of real compression scheme in section 4, and the SVD of AR is as follows
Assume that the number of selected singular values are all q. Since C ∈ ℝ3N×N, we should store UC ∈ ℝ3N×q, diagonal matrix ΣC ∈ ℝq×q, and VC ∈ ℝN×q in the SVD of C, the storage is 4Nq + q, and In the real structure-preserving algorithm, the first column block, B, of AR is a 4N × N matrix. Since the real part of A is zero, then the storage of AR is also 3N2. While the storage is 8Nq + q in the SVD of AR in Eq (5.1), which is much bigger than that of SVD of C. Then we obtain . That is, CR1 is twice as large as CR2. Under the condition of same storage, the number of selected singular values of C can be twice as large as that of A to ensure good compression effect. The comparison of compression effect of two different schemes with the same storage will be presented in Table 3.
Assume the SVD of quaternion matrix A of color image Pepper is
In Fig 3, we compare the singular values of C and A. Because there is wide gap between the order of magnitude of the largest and smallest singular values, In order to facilitate comparison, we perform logarithmic transformation for all the singular values. As shown in Fig 3, we observe that the several largest singular values of A are larger than those of C. But the most smaller singular values of A are smaller than those of C. The reason is as follows.
We know, one of the most frequently used matrix norm in numerical linear algebra is the Frobenius norm, for a m × n matrix A, defined as
It has the following connections to the SVD of A,
For any quaternion matrix A = A1 + A2i + A3j + A4k, it is not difficult to verify that
then for a given pure imaginary quaternion matrix A of a color image, we have
On the other hand, for the real rectangle matrix C, we also have
i.e. the sum of square of all the singular values of A is equal to that of C. The order of magnitude of the largest singular values is the fifth or fourth power of ten, thus the gap of these singular values of A and C is very large. This lead to the most smaller singular values of A are smaller than those of C. When we select the same numbers of the singular values in the two algorithms, it seems that the performance of the quaternion compression scheme is better than the real compression scheme. But we notice that when using the quaternion compression scheme, the real part of the reconstructed quaternion matrix may not be zero matrix. We should set it to be zero. In this step, the error inevitably increase. Thus we see the approximate results of the two schemes are similar. But the advantage of the real compression scheme in speed is obvious.
Example 5.2. Color image Lena of 256 × 256 is taken as the original image. We provide the PSNR, CPU time with different numbers of selected singular values using the real compression scheme and quaternion compression scheme in Table 4, respectively.
In Example 5.3 and 5.4, we use 1024 × 1024 and 2048 × 2048 color image Butterfly as the original image, respectively, which are obtained by magnifying original image of 512 × 512 using the command ‘imresize’ in Matlab. The PSNR and CPU time in these two examples are all shown in Table 4. From Table 4, we observe the compression result in Example 5.2–5.4 consistent with Example 5.1. The PSNR of real compression scheme are a little bit smaller than those of quaternion one. This situation don’t change with the adjustment of image pixel. But as the image pixel is higher and higher, the gap of CPU time is becoming more and more big. Computation time of quaternion can reach 60 to 70 times of real compression scheme. Since speed is vital for problem of large image processing, it highlight the advantages of the real compression scheme.
Particularly, we compare the PSNR and computation time under the condition of the same compression ratio, i.e., the number of selected singular values of real compression scheme are twice of that of quaternion scheme. As shown in Table 3, the advantage of real compression scheme is not only reflected on the speed, the values of PSNR are much higher than those of quaternion compression scheme.
In this paper, we proposed a real SVD-based color image compression scheme. We formed a new real rectangle matrix C according to the red, green and blue components of the original color image and performed the real SVD for C. Then we selected several largest singular values and the corresponding vectors in the left and right unitary matrices to compress the color image. At the other hand, we viewed a color image as a quaternion matrix A. We performed quaternion SVD on A using the real structure-preserving algorithm to compress the original color image. We compared the two SVD-based color image compression schemes in terms of operation amount, assignment number and operation speed. We also compared their PSNR and CR. From numerical examples provided in Section 5, we observed that real compression scheme is more efficient with comprehensive consideration of various factors.
Supported by the National Natural Science Foundation of China under grants 11301247 and 11171226, the Natural Science Foundation of Shandong under grant ZR2012FQ005, ZR2014FM032, Science and Technology Project of Department of education, Shandong Province J15LI10, the science foundation of Liaocheng University under grants 31805, 318011318.
This work was supported by the National Natural Science Foundation of China under grants 11171226 and 11301247, the Natural Science Foundation of Shandong under grant ZR2012FQ005, ZR2014FM032, Science and Technology Project of Department of education, Shandong Province J15LI10, the science foundation of Liaocheng University under grants 31805, 318011318.
All relevant data are included with the paper and its Supporting Information files.