Color PCA Eigenimages
and Their Application to Compression and Watermarking
Arash Abadpour and Shohreh Kasaei
Mathematics Science Department, Sharif University of Technology, Tehran, Iran
Computer Engineering Department, Sharif University of Technology, Tehran, Iran
Abstract
From the birth of multispectral imaging techniques, there has been a tendency to consider and process this new type of data as a set of parallel grayscale images, instead of an ensemble of an nD realization. However, it has been proved that using vectorbased tools leads to a more appropriate understanding of color images and thus more efficient algorithms for processing them. Such tools are able to take into consideration the high correlation of the color components and thus to successfully carry out energy compaction. In this paper, a novel method is proposed to utilize the principal component analysis in the neighborhoods of an image in order to extract the corresponding eigenimages. These eigenimages exhibit high levels of energy compaction and thus are appropriate for such operations as compression and watermarking. Subsequently, two such methods are proposed in this paper and their comparison with available approaches is presented.
Color is one of the most important tools for object discrimination by human observers, but it is overlooked in the past [1]. Discarding the intrinsic characteristics of color images, as vector geometries [2], some researchers have considered them as parallel grayscale
components [3,4,5]. However, it has been proved that the application of principal component analysis (PCA) leads to appropriate descriptors for natural color images [6,7]. These descriptors work in vector domains and take into consideration the statistical dependence of the components of the color images taken from the nature [8].
In this paper, we use a PCAbased distance function and the related homogeneity criterion. This criterion will be used in a tree decomposition method which splits a given image into homogeneous patches. The patches will be further analyzed using PCA to provide energy compaction through a proposed eigenimage extraction method. These eigenimages are then used in order to provide color image processing tools such as compression and watermarking.
The rest of this paper is organized as follows. First, Section 2 briefly reviews the related literature. Then, Section 3 discusses the tools used in this paper and follows with introducing the proposed method. The paper continues with Section 4 which contains the experimental results and discussions. Finally, Section 5 concludes the paper.
This section briefly reviews the related literature. First, in Section 2.1, a few distance functions and their application to color image processing are discussed. This section also looks at PCAbased color image processing and its implications. Then, Section 2.2, 2.3 and 2.4 look at the key issues in color image decomposition, compression and watermarking.
2.1 Distance Functions and PCABased Color Image Processing
The Euclidean distance is generally assumed to be a proper distance function in color applications [1,9,10,11,12,13,14]. Accordingly, it has been applied in different color spaces (e.g. CIELab [15]). However, research has shown that, although being very convenient to use, this measure is not a proper color descriptor [16].
A theoretical analysis of highlights in color images was presented in a classical paper published by Klinker, Shafer and Kanade In 1988 [6]. In that work, the light reflected from an arbitrary point of a dielectric object was modeled. In 1990, the same group applied their approach to color image understanding [16]. These developments were left mostly untouched by the research community, till more than a decade later, in 2003, without paying too much attention to the
theoretical aspects, Cheng and Hsia used the PCA for color image processing [7]. Then, in 2004, Nikolaev and Nikolayev started the work back from the theory and proved that PCA is a proper tool for color image processing [17]. The next necessary step had been introduced in 1991, when Turk and Pentland had proposed their eigenface method [18], in a completely different context. There, they developed a novel idea which connected the eigenproblems in the color domain and the spatial domain, together. Although, there is this rich theoretical background for the linear local models of color, it is quite common to see research procedures which are based on the old color space paradigm, even published in 2007 (see [19] for example). For a more comprehensive discussion of this topic refer to [20].
Aside from the theoretical evidence for the superiority of PCAbased color descriptors, an extensive empirical analysis, given in [21], shows that a certain PCAbased color distance produces more appropriate results, compared to the conventional Euclidean and Mahalanobis distances. The latter one is included in the analysis because some researchers tend to use weighted Euclidean distance, which when tuned well converges to the wellknown Mahalanobis distance (e.g. [22]). Here, we will briefly introduce the utilized PCAbased distance function. The interested reader is referred to [21] for details about the two others as well as a comprehensive comparison between the three. The chosen distance function will be used in a homogeneity criterion for the utilized tree decomposition, discussed next.
Quadtree decomposition is the wellknown method for splitting an image into homogeneous subblocks, resulting in a very coarse, but fast, segmentation [23]. Defining the whole image as a single block, the method is performed according to a problemspecific homogeneity criterion. Generalizations of quadtree include work on dimension [24] and shape [25] of the blocks. In conventional quadtree decomposition, a nonhomogeneous block is split into four subblocks. The onesplittofour rule has been optimized by using a novel onesplittotwo rule, resulting in a method called bitree decomposition [26].
The early approach to color image compression is based on decorrelating the color components using a linear or nonlinear invertible coordinate transformation (e.g., YC_{b}C_{r} [27], YIQ [28] and YUV [29]). Then, one of the standard grayscale compression methods (such as differential pulse code modulation (DPCM) [30] or transform coding [31]) will be applied on each component, separately (see also [32]).
This approach is inefficient, because none of the available color spaces is able to completely decorrelate the color components in a real image [6]. In [33], using the PCA approach in the neighboring pixels, the author discusses the idea of separating the spatial and the spectral compression stages. As the paper proves, the maximum theoretical compression ratio for an ideal spectral compression method is 1:3. The main shortcoming of the method introduced in [33] is neglecting the fact that in nonhomogeneous patches, PCA does not perform energy compaction [9]. In [9], the author combines the spatial and spectral information to reach a higher compression ratio. Although, that method is based on expensive computation, the peak signal to noise ratio (PSNR) results are desperate.
Ease of copy and transfer of digital files has made the urge for effective watermarking schemes to protect the fidelity of the media [34]. On top of the generalpurpose data watermarking approaches (e.g. [35,36]), there is an extensive literature for watermarking Images. The main concern in this field is to locate spots in an image, in different domains, where data can be added without being perceptible by human observers. The early approaches taken in this regard use the redundancy of the natural images in the spatial domain [34,37]. With the introduction of color imaging, some of these grayscale watermarking techniques have been exported to color images. For example, in [36], the authors embed the watermark in the blue component. In another work [38], the CIELab coordinates are quantized and then the watermark is copied into the least important bits. As mentioned by the authors in [39], most available color image watermarking approaches work on the luminance or independent color components. This ignores the correlation between color components, and the regarding opportunity for effective embedding of information in color images.
In [40], the authors proposed to use the error made by neglecting the two least important principal components (the second and the third) as a distance function, called the linear partial reconstruction error (LPRE),
t_{r}
æ è
®
c
ö ø
=
®
v
T r
æ è
®
c

®
h
r
ö ø
®
v
r

æ è
®
c

®
h
r
ö ø
.
(1)
Here, [(v)\vec]_{r} denotes the direction of the first principal component of C_{r}, the covariance matrix of the color vectors of the patch r,
C_{r}=E_{[(c)\vec] Î r}
ì í
î
æ è
®
x
i

®
h
ö ø
æ è
®
x
i

®
h
ö ø
T
ü ý
þ
.
(2)
Also, · is the Euclidean norm and [(x)\vec]^{T} denotes transposition. Furthermore, [(h)\vec]_{r} is the expectation vector of r, [(h)\vec]_{r}=E_{[(c)\vec] Î r}{[(c)\vec]}. With these definitions, t_{r}([(c)\vec]) is the distance from the arbitrary color vector [(c)\vec] to the given set r. Comparison of this measure with other conventional ones can be found in [21].
Having defined a proper distance function, a related homogeneity criterion can be derived by defining,
t_{r}=E_{[(c)\vec] Î r}
ì í
î
t_{r}
æ è
®
c
ö ø
ü ý
þ
.
(3)
This way, the LPREbased homogeneity criterion is defined. As mentioned in Section 2.1, empirical analysis carried out in [21] shows that, compared to the Euclidean and Mahalanobis distances, LPRE performs three primitive tasks more efficiently. First, it yields a more appropriate classification of pixels into relevant and irrelevant ones, in regards to a given homogeneous patch. Furthermore, when asked to decide whether or not a patch is homogeneous, LPRE's results comply better with the human perception. Finally, in the existence of outliers, LPRE shows more robustness than both the Euclidean and the Mahalanobis distances [21] (also see [41]).
As discussed in Section 2.2, having chosen a proper homogeneity criterion, an image can be decomposed into homogeneous regions (here, based on t_{r}). Starting with the entire image, the tree is produced by splitting nonhomogeneous regions (the ones for which t_{r} > e_{1}, where e_{1} Î [1,10] is a threshold). In a W×H image, the depth of a w×h block r is defined as,
r_{r}=
max
ì í
î
log_{2}
W
w
,log_{2}
H
h
ü ý
þ
,
(4)
and no block is permitted to reach the depth more than a preselected marginal tree depth r Î [1,5].
Figure 1: The bitree decomposition method.
Here, we use a novel tree decomposition method called bitree [26]. In bitree, if the block r is not homogeneous enough, rather than the deterministic choice of the subblocks in quadtree, r is divided either horizontally or vertically (see Figure 1). This is accomplished in the way that the total nonhomogeneity of the output gets the least possible. Extensive empirical comparison of bitree with quadtree, given in [26], shows that bitree produces fewer blocks, with a more uniform distribution of block sizes. On the contrary, quadtree splits the image more and produces a more scattered pattern of block sizes. The total homogeneity of the resulting blocks are almost the same in both methods. The achievements of bitree have the cost of demanding about four times more computational resources than the quadtree. As the proposed method works better when blocks have similar sizes, we use bitree in this paper.
There is a manipulated form of the wellknown Euler angles that relates any rightrotating orthonormal matrix with three angles, in a onetoone revertible
transformation [42]. As such, for the matrix V, with its ith column denoted as [(v)\vec]_{i}, we write V ~ (q,f,y) when,
ì ï í
ï î
q = Ð([(v)\vec]_{1}^{xy},[1,0]^{T})
f = Ð((R_{q}^{xy}[(v)\vec]_{1})^{xz},[1,0]^{T})
y = Ð((R_{f}^{xz}R_{q}^{xy}[(v)\vec]_{2})^{yz},[1,0]^{T})
(5)
Here, Ð([(v)\vec],[(u)\vec]) is the angle between the two vectors [(v)\vec],[(u)\vec] Î R^{2} and [(v)\vec]_{p} denotes the project of the vector v on the plane p. Also, R_{a}^{p} is the 3×3 matrix of a radians counterclockwise rotation in the p plane:
ì ï ï ï ï ï ï ï ï í
ï ï ï ï ï ï ï ï î
R_{q}^{xy}=
é ê ê
ê ë
cosq
sinq
0
sinq
cosq
0
0
0
1
ù ú ú
ú û
R_{f}^{xz}=
é ê ê
ê ë
cosf
0
sinf
0
1
0
sinf
0
cosf
ù ú ú
ú û
R_{y}^{yz}=
é ê ê
ê ë
0
cosy
siny
1
0
0
0
siny
cosy
ù ú ú
ú û
.
(6)
It can be proved that to produce V out of the triple (q,f,y) one may use [43],
V=R_{q}^{xy}R_{f}^{xz}R_{y}^{yz}.
(7)
Note that (R^{p}_{a})^{1}=R^{p}_{a}. While equation (5) computes the three angles q, f and y out of V, equation (7) reconstructs V from q, f and y. These methods are called polarization and depolarization of a rightrotating orthonormal matrix, respectively [42].
Consider a partition of the H×W square as a set of rectangular regions {r_{i}i=1,¼, n}, while the values of {l_{i}i=1,¼, n} are given, satisfying,
f(
®
c
) @ l_{i}, "i, "
®
c
Î r_{i},
(8)
for an unknown function f:\mathbbR^{2}® \mathbbR. The problem is to properly approximate f as [f\tilde]. We address this problem as blockwise interpolation of the set {(r_{i};l_{i})i=1,¼, n}.
Note that, for a conventional rectangular grid as the partition, the problem reduces to an ordinary 2D interpolation task. Here, we use a reformulated version of the wellknown lowpass Butterworth filter, as the interpolation kernel, to carry out the interpolation in the more general case.
ì ï ï í
ï ï î
B_{t,N}(x)=(1+ ([ x/(t)] )^{2N})^{1/2}
ì ï í
ï î
N=rnd(log_{a/b}([(bÖ{1 a^{2}})/(aÖ{1b^{2}})]))
t = a^{2N}Ö{[(a^{2})/(1a^{2})]}
(9)
Here, a, b, a and b are given and the function B_{t,N}(·) satisfies B_{t,N}(a)=a and B_{t,N}(b)=b. The 2D version of this function can be defined as, B_{t,N}^{w,h}(x,y)=B_{wt,N}(x)B_{ht,N}(y), where w and h control the spread of the function in the x and y directions, respectively. Figure 2 shows the typical shape of the function B_{t,N}^{w,h}(x,y) with a=0.9, a = 0.7, b=1, b = 0.5 and w=h=16.
Figure 2: The typical shape of the proposed interpolation kernel,
B_{t,N}^{w,h}(x,y).
Assuming that the region r_{i} is centered at (x_{i},y_{i}), while its height and width are w_{i} and h_{i}, respectively, we propose the function [f\tilde] to be defined as,
~
f
(x,y)=
N å
i=1
l_{i}B_{t,N}^{[(wi)/2],[(hi)/2]}(xx_{i},yy_{i})
N å
i=1
B_{t,N}^{[(wi)/2],[(hi)/2]}(xx_{i},yy_{i})
.
(10)
Note that, [f\tilde] is a smooth version of the staircase function f.
As the generalization of the blockwise interpolation problem, assume that the set of regions and the corresponding l_{ij}s are given as {(r_{i};l_{i1},¼,l_{im})i=1,¼, n}, satisfying, f_{j}([(c)\vec]) @ l_{ij}, "i, j, [(c)\vec] Î r_{i}, for a set of m unknown functions f_{j}:\mathbbR^{2}® \mathbbR. To solve this problem, in a way similar to (10), we calculate,
Here, because the set of base regions for all [f\tilde]_{j}s are the same, the total performance is increased by computing the kernel just once, for each value of i. Then, the problem reduces to m times computation of a weighted average.
When working in the polar coordinates, ordinary algebraic operations on the variables lead to spurious results, because of the 2p discontinuity. To overcome this problem, rather than directly solving {(r_{i};q_{i})i=1,¼, n}, we solve the problem {(r_{i};cosq_{i},sinq_{i})i=1,¼, n} and
then find q_{i} using ordinary trigonometric methods.
Consider the PCA matrix, V_{r} and the expectation vector, [(h)\vec]_{r}, corresponding to the homogeneous set r. For the arbitrary color vector [(c)\vec], which belongs to r, the PCA coordinates are calculated as, [(c)\vec]¢=V_{r}^{1}([(c)\vec][(h)\vec]_{r}) [44]. Assume that there exists a method for finding an appropriate color set r_{[(c)\vec]} for each color vector [(c)\vec]. Here, r_{[(c)\vec]} describes the color content of [(c)\vec], in the sense that,
®
c
¢
=V_{r[(c)\vec]}^{1}
æ è
®
c

®
h
r_{[(c)\vec]}
ö ø
,
(12)
satisfies,
s_{c¢1} >> s_{c¢2} >> s_{c¢3},
(13)
where, [(c)\vec]¢=[c¢_{1},c¢_{2},c¢_{3}]^{T}. We call the c¢_{1}, c¢_{2} and c¢_{3} components as the pc_{1}, pc_{2} and pc_{3}, principal components, respectively. The original image can be perfectly reconstructed using these three components, except for numerical errors, as,
®
c
@
®
c
3
=V_{r[(c)\vec]}
®
c
¢
+
®
h
r_{[(c)\vec]}
.
(14)
It is proved in [6], theoretically, and in [40], empirically, that for homogeneous swatches, neglecting pc_{3} (or even both pc_{2} and pc_{3}), gives good approximation of the original image. These are called partial reconstructions. Note that the perfect reconstruction scheme of (14) does not rely on (13), while the properness of the partial reconstructions defined as,
®
c
2
=V_{r[(c)\vec]}
é ê ê
ê ë
c¢_{1}
c¢_{2}
0
ù ú ú
ú û
+
®
h
r_{[(c)\vec]}
.
(15)
and,
®
c
1
=V_{r[(c)\vec]}
é ê ê
ê ë
c¢_{1}
0
0
ù ú ú
ú û
+
®
h
r_{[(c)\vec]}
,
(16)
do rely on (13).
Now, the goal is to devise an efficient method for calculating, and storing, V_{r[(c)\vec]} and [(h)\vec]_{r[(c)\vec]} for all the pixels in an image. In the following, a method for doing this task is proposed.
After feeding an image I into the bitree method, The output is the matrix U which contains the coordinates of r_{i} along with the expectation matrix [(h)\vec]_{i} and the polarized version of the PCA matrix (q_{i},f_{i},y_{i}). Now, consider solving the problem {(r_{i};x_{i})i=1,¼, n} using the blockwise
interpolation, where x_{i} is the row vector containing h_{i1}, h_{i2}, h_{i3}, q_{i}, f_{i} and y_{i}. The solution will be the functions [(h)\tilde]_{1}, [(h)\tilde]_{2}, [(h)\tilde]_{3}, [(q)\tilde], [(f)\tilde], [(y)\tilde]: \mathbbR^{2}®\mathbbR. Now, we compute the functions [([(h)\vec])\tilde]:\mathbbR^{2}® \mathbbR^{3} (expectation map, Emap) and [(V)\tilde]:\mathbbR^{2}® \mathbbR^{9} (rotation map, Rmap), as the expectation vector and the PCA matrix in each pixel, respectively. This leads to the computation of the three eigenimages pc_{1}, pc_{2} and pc_{3} (using (12)).
It can be shown that [45],
Consider the image I and its corresponding eigenimages pc_{1}, pc_{2} and pc_{3}. Due to the energy compaction condition, given in (19), this scheme can lead to a spectral compression of an image. As such, reconstructing the image using just one or two eigenimage(s) gives the compression ratios of ^{3}/_{2}:1 and 3:1, respectively. To add spatial compression to the this scheme, we use the PUPLVQ grayscale image compression technique [46] for each eigenimage, independently, with different compression ratios. This leads to the color image compression method proposed in Figure 3.
(a)
(b)
Figure 3: Flowchart of the proposed color image compression method. (a) Compression. (b) Decompression.
As Figure 3a shows, the transmitted information consists of the compressed versions of pc_{1}, pc_{2} and pc_{3}, along with U, a, a, b and b. Assume that the compression is to be applied on an H×W image, decomposed into n blocks by the bitree method. The total amount of information to be sent equals 10n bytes for storing x_{i1}, x_{i2}, y_{i1}, y_{i2}, h_{i1}, h_{i2}, h_{i3}, q_{i}, f_{i} and y_{i} plus WH(l_{1}^{1}+l_{2}^{1}+l_{3}^{1}) bytes for storing pc_{1}, pc_{2} and pc_{3} eigenimages compressed with compression ratios of l_{1}, l_{2} and l_{3}, respectively (where l_{1} > l_{2} > l_{3}). Thus, the total compression ratio equals,
l @
3
l_{1}^{1}+l_{2}^{1}+l_{3}^{1}+
10n
WH
(20)
Picking the values of l_{2}=l_{1} and l_{3}=¥ leads to l @ 1.5l_{1}. Note that using a pure spatial compression approach, all three color components must be compressed with almost the same compression ratios, resulting in a total compression ratio of l_{1}. Thus, in the worst case, the proposed method multiples the compression ratio by at least 1.5.
As shown in Figure 3b, in the decompression process, first, the Emap and the Rmap are computed. Using this information, along with the decoded versions of pc_{1}, pc_{2} and pc_{3}, the original image is then reconstructed.
Consider the image I with the three corresponding eigenimages of pc_{1}, pc_{2} and pc_{3}. Although, there is no orthogonality constraint in the eigenimage theory, the eigenimage approach can be adapted for watermarking purposes. Assume that the grayscale watermark image W is to be embedded into I. Also, assume that I and W are of the same size (H×W). First, the dynamic range of W is fitted into that of pc_{3}, as,
~
W
=
s_{pc3}
s_{W}
(Wh_{W}).
(21)
Now, replacing pc_{3} with the scaled version of the watermark signal, [(W)\tilde], the watermarked image, I¢, is constructed.
The process of extracting the watermark is through computation of the eigenimages corresponding to I¢, which we call pc_{1}¢, pc_{2}¢ and pc_{3}¢. Now, pc_{3}¢, when normalized, contains the reconstructed watermark signal,
The proposed algorithms are developed in MATLAB 6.5, on an 1100 MHz Pentium III personal computer with 256MB of RAM. For a typical 512×512 image it takes 8.3 seconds to extract the eigenimages. Then, another 4.6 seconds are needed to reconstruct the image. Adding the less than one second needed to do the spatial compression, the total operation takes slightly less than 16 seconds for a typical image. It takes a similar amount of time to embed a watermark in a 512×512 image and about 9 seconds to extract it. Note that these values are measured using MATLAB code and can be reduced drastically if the code is implemented using a higherlevel programming language.
A database of color images which includes the standard images of Lena, Mandrill, Peppers and Couple as well as some professional color photographs [47], a total of 140 images, is used in this research. All images are of the size 512×512, in RGB color space, and are compressed using standard JPEG with qualities above 95. Prior to the operation, all the images are converted to the standard BMP format.
Figure 4: Proposed blockwise interpolation. (a) Sample problem. (b) The solution provided by the proposed blockwise interpolation (SNR > 22dB).
To illustrate the results of the proposed blockwise Interpolation method, a sample problem is given in Figure 4a, with the associated outcome in Figure 4b, at the Signal to Noise Ratio (SNR) of more than 22dB.
Figure 5: The process of extracting the eigenimages from an arbitrary image. (a) Original image adopted from [47]. (b) Outcome of the bitree decomposition method. (c) Emap. (d) Rmap. (e) pc_{1}. (f) pc_{2}. (g) pc_{3}. (h) Histograms of the eigenimages. (i) Reconstruction using all eigenimages (PSNR=60dB). (j) Ignoring one eigenimage (PSNR=38dB). (k) Ignoring two eigenimages (PSNR=31dB).
Figure 5 shows the process of extracting the eigenimages corresponding to the image shown in Figure 5a, using the proposed method. First, using the bitree method with the parameters e_{1}=5 and r = 5, the image is split into 91 blocks (see Figure 5b). These blocks are then used to generate the EMap and the RMap, as shown in Figures 5c and (d), respectively. Subsequently, the eigenimages, as shown in Figures 5e, f and g, are extracted. Notice that the dynamic ranges of all eigenimages are exaggerated to give a better visualization. The stochastic distributions of the eigenimages are investigated in Figure 5h. These histograms show the compaction of the energy as discussed next. Using numerical measures, the standard deviations of the eigenimages are computed as, s_{pc1}=52, s_{pc2}=12 and s_{pc3}=6. This results in k_{1}=94%, k_{2}=5%, and k_{3}=1%, a clear compaction of the energy in the first eigenimage.
Figure 5i shows the result of reconstructing the image shown in Figure 5a using all three eigenimages. Similarly, Figures 5j and k show the results of ignoring pc_{3} and both pc_{3} and pc_{2}, respectively. The resulting PSNR values are
60dB, 38dB and 31dB, respectively. Note that PSNR of 60dB (instead of infinity), for reconstructing the image using all eigenimages, is caused by numerical errors, while the two other PSNR values (38dB, 31dB) show some loss of information. In the literature, PSNR values of above 38dB are considered visually satisfactory even for professionals [48].
(a)
(b)
(c)
Figure 6: Distribution of energy between the three eigenimages, for different values of e_{1} and r. (a)k_{1}. (b)k_{2}. (c)k_{3}.
Figures 6a, b and c show the values of k_{1}, k_{2} and k_{3} for the image shown in Figure 5a, at different values of e_{1} and r. Note that, except for the trivial cases of r £ 2 and e_{1} > 9, which are never used in practice, more than 90% of the image energy is stored in pc_{1}, while pc_{2} and pc_{3} hold about 9% and 1% of the energy, respectively. Having in mind that in the original image k_{r}=38%, k_{g}=32% and k_{b}=30%, the energy compaction of the eigenimages are considerable.
(a)
(b)
(c)
Figure 7: PSNR values corresponding to partiallyreconstructed images, for different values of e_{1} and r. (a) Using three eigenimages. (b) Using two eigenimages. (c) Using only one eigenimage.
Figure 7 shows the PSNR values obtained by reconstructing the image shown in Figure 5a using all three eigenimages (Figure 7a), two eigenimages (Figure 7b), and only one eigenimage (Figure 7c), for different values of e_{1} and r. Note that, for values of e_{1} £ 8 and r ³ 3, reconstructing the image using all eigenimages gives the high PSNR value of about 60dB, while neglecting one and two eigenimages results in PSNR ³ 35dB and PSNR ³ 28dB, respectively.
Figure 8 shows the results of the proposed compression method, with the associated numerical values mentioned in Table 1. These results are acquired using e_{1}=5 and r = 5. To compare the compressed images with the original ones, the exaggerated differences are carried in Figure 9. Note the high compression ratio of about 70:1 in all cases, while the PSNR is mostly above 25dB.
Among other regionbased coding approaches, the method by Carveicet. al. is one of the best [9]. In that work, the authors mixed the color and texture information into a single vector and then performed the coding using a massively computationallyexpensive algorithm. However, the final results show PSNR values of about 40dB for compression ratios of about 20:1. In [33], the researchers separate the compression in the two disjoint domains of spectral and spatial redundancy, by using a PCA neural network. They reach the compression ratio of 3.7:1 with PSNR of around 25dB, while almost all test samples are homogeneous. In [49], the method gives the compression ratio of about 14.5:1 but with the same range of PSNR as ours. As a more recent approach, we compare the PSNR of 31.93dB reported in [19] for Lena at 1.17bpp with the results of the proposed method in which PSNR of 33.6dB is achieved at 0.33bpp.
Table 1 also compares the proposed algorithm with JPEG and JPEG2000. To do this comparison, each sample image is compressed using each one of these algorithms with the exact compression ratio acquired from the proposed method. As expected, Table 1 shows that JPEG2000 is always giving a better result compared to JPEG. Comparing the proposed method with JPEG2000, we understand that, except for the case of Figure 8f, the proposed method is giving a higher PSNR than both others. Numerically, the proposed method is 14% and 7% better than JPEG and JPEG2000, respectively, in terms of PSNR. This means more than 3.6dB and 1.9dB increase in the quality when comparing the results of the proposed method with JPEG and JPEG2000, respectively.
Figure 10: Results of the proposed watermarking method performed on the image shown in Figure 5a. (a) Watermark data. (b) Watermarked image at PSNR=35dB. (c) Exaggerated difference between the original image and the watermarked image. (d) Extracted watermark data.
To demonstrate the utilization of the proposed method in embeding a watermark in an image, we use the example shown in Figure 10. Here, Figure 10b shows the results of embedding the watermark data shown in Figure 10a into the image shown in Figure 5a. The resulting PSNR of this operation is 35dB. Figure 10c shows the exaggerated difference between the original image and the watermarked image, and Figure 10d shows the extracted watermark. Investigating Figure 10c shows where the proposed method hides the data; at each pixel, the direction of the third principal component shows the direction in which data can be put such that it does not affect the visual perception of the image.
Figure 11: Sample watermark.
(a)
(b)
(c)
(d)
(e)
(f)
(g)
(h)
(i)
(j)
(k)
(l)
Figure 12: Some attacked watermarked images, corresponding items in
Table 2 are: (a):1, (b):2, (c):3, (d):5, (e):9, (f):11,
(g):12, (h):13, (i):14, (j):23, (k):28, and (l):29
(a)
(b)
(c)
(d)
(e)
(f)
(g)
(h)
(i)
(j)
(k)
(l)
Figure 13: Extracted watermarks from attacked images shown in Figure 12.
Table 2: Some of the attacks performed on the watermarked images to analyze the robustness of the proposed watermarking method.
index
Attack
0

1
Enhancement
2
Scaling and trimming
3
Rotation, scaling and trimming
47
Nonlinear Geomtrical
8
Gaussian Lowpass
9,10
Scratch
11,12
Local brightening/darkening
13
Text
14
Motion Blur
15
Radial Blur
1622
Geometrical Distortion
23
Uniform Color Noise
24
Gaussian Color Noise
25
Uniform Gray Noise
26
Gaussian Gray Noise
27
Median
28
Artistic Lens Flare
29
Lossy Compression
To test the robustness of the proposed watermarking method against invasive attacks, the watermark shown in Figure 11 is embedded in the sample image shown in Figure 5a. Then, the watermarked image is attacked, using Adobe Photoshop 6.0, as stated in Table 2. Figure 12 shows some of the attacked watermarked images and Figure 13 show the corresponding extracted watermark data. Investigating Figure 13 shows that the proposed watermarking method is robust against linear and nonlinear geometrical transformations, including rotation, scaling, trimming, and other geometrical distortions. Also, it is robust against occlusion, artistic effects, noise, enhancement operations such as brightening and increasing contrast (even when performed locally), and also lossy compression for ratios up to 15:1.
Table 3: Comparison of different watermarking approaches with the proposed method, all used in a 512×512 image. : Not Resistant. ~ : Partially Resistant. Ö: Completely Resistant. [Abbreviations: G: Grayscale, SCC: Single Color Component, CV: Color Vector, LG: Linear Geometrical Transformation, NLG: Nonlinear Geometrical Transformation, LPO: Linear Point Operations, NLPO:Nonlinear Point Operations, SO: Spatial Domain Operations, EO: Editing Operations, CMP: JPEG Compression].
Table 3 compares the proposed watermarking method with some of the approaches available in the literature. The table lists the watermark capacity of each method when embedding to a 512×512 color image along with the domain in which the data is embedded. Also, the attack resistance of different approaches is compared here.
It is observed in different experiments that the standard deviation of pc_{3} in a typical image is more than 4. Thus, using the proposed watermarking method on a 512×512 color image, at least a samesized 2bpp image can be used as the watermark signal. This makes the watermark capacity of the proposed method equal to 64KB. This is four times more than the highest capacity of the best available approach [53]. It is worth to mention that only the approaches discussed in [38,58] use color vectors and that only [38] exhibits levels of resistance to linear point operations such as brightening and contrast enhancement. It must be emphasized that that method's resistance is limited to global operations, while the method proposed in this paper is resistant even to local linear point operations (see Figures 12f and g). Unfortunately, in the literature, minor attention is paid to nonlinear geometrical operations, such as elastic and perspective transformation, and image editing processes, such as adding text, artistic effects, occlusion and so on, whilst the copyrighted images can be used in books, posters and websites where they appear in manipulated forms.
In this paper, a PCAbased distance function and the corresponding homogeneity criterion are utilized within a tree decomposition method. The resulting decomposition is then used in order to extract the eigenimages associated with a given image. The proposed eigenimage extraction method is proved to be highly efficient in compacting the image energy as well as in providing proper partial reconstructions of color images. The eigenimages are then used in a color image compression method. Furthermore, the fact that manipulating the third eigenimage has minor effect on the quality of an image is used in a novel watermarking method. Both methods are compared with the available literature. Comparison shows that the proposed compression method is superior to the available approaches (in average 1.9dB more than JPEG2000 in PSNR for the samples used in this paper). The analysis of the proposed watermarking method shows that it is resistant to local alterations as well as to the manipulations performed in publications and websites, such as adding text and nonlinear geometrical distortions. No other watermarking approach in the literature is found to claim similar resistance.
Acknowledgement
We wish to thank the respected referees for their constructive suggestions. The first author wishes to thank Ms. Azadeh Yadollahi for her encouragement and invaluable ideas. We also thank the photographers Ms. Shohreh Tabatabaii Seifi and Mr. Ali Qanavati for allowing us to use their rich digital image archive.
N. Papamarkos, C. Strouthopoulos, I. Andreadis, Multithresholding of color and
graylevel images through a neural network technique, Image and Vision
Computing 18 (2000) 213222.
L. Lucchese, S. Mitra, Colour segmentation based on separate anisotropic
diffusion of chromatic and achromatic channels, Vision, Image, and Signal
Processing 148(3) (2001) 141150.
S.C. Cheng, S.C. Hsia, Fast algorithms for color image processing by
principal component analysis, Journal of Visual Communication and Image
Representation 14 (2003) 184203.
J. Limb, C. Rubinstein, Statistical dependence between components of a
differentially quantized color signal, IEEE Transactions on Communications 20
(1971) 890899.
F. Masulli, A. Massone, A. Schenone, Fuzzy clustering methods for the
segmentation of multimodal medical volumes (invited), in: P. Szczepaniak,
P. Lisboa, S. Tsumoto (Eds.), Fuzzy Systems in Medicine. Series Studies in
Fuzziness and Soft Computing, editor J. Kacprzyk, SpringerVerlag,
Heidelberg (Germany), 2000, pp. 335350.
L. Lucchese, S. Mitra, Color image segmentation: A stateoftheart survey
(invited paper), Image Processing, Vision, and Pattern Recognition, Proc. of
the Indian National Science Academy (INSAA) 67, A, No. 2 (2001) pp.
207221.
K.K. Ma, J. Wang, Color distance histogram: A novel descriptor for color image
segmentation, in: Seventh International Conference on Control, Automation,
Robotics, and Vision (ICARCV'02), Singapore, 2002, pp. 12281232.
B. C. Dharaa, B. Chanda, Color image compression based on block truncation
coding using pattern fitting principle, Pattern Recognition 40 (2007)
24082417.
A. Abadpour, Color image processing using principal component analysis,
Master's thesis, Sharif University of Technology, Mathematical Sciences
Department, Tehran, Iran (June 2005).
A. Abadpour, S. Kasaei, Performance analysis of three likelihood measures for
color image processing, in: IPM Workshop on Computer Vision, Tehran, Iran,
2004.
Q. Ye, W. Gao, W. Zeng, Color image segmentation using densitybased
clustering, in: Proceedings of 2003 IEEE International Conference on Acoustic
and Signal Processing, Hog Kong, 2003, pp. 401404.
C. Faloutsos, H. Jagadish, , Y. Manolopoulos, Analysis of the ndimensional
quadtree decomposition for arbitrary hyperrectangles, IEEE Transaction on
Knowledge and Data Engineering 9, No. 3 (1997) 373383.
ITUR Recommendation BT6015: Studio Encoding Parameters of Digital
Television for Standard 4:3 and Widescreen 16:9 Aspect Ratios, www.itu.ch/,
Geneva, 1994.
M. Swanson, M. Kobayashi, A. Tewfik, Multimedia dataembedding and
watermarking technologies, in: Proceedings of the IEEE, Vol. 86(6), 1998, pp.
10641087.
E. Shahinfard, S. Kasaei, Digital image watermarking using wavelet transform,
in: Iranian Conference of Mechatronics Engineering, ICME, Qazvin, Iran, 2003,
pp. 363370.
A. Abadpour, S. Kasaei, A new parametric linear adaptive color space and its
PCAbased implementation, in: The 9th Annual CSI Computer Conference,
CSICC, Tehran, Iran, 2004, pp. 125132.
A. Abadpour, S. Kasaei, A new principle component analysis based colorizing
method, in: Proceedings of the 12th Iranian Conference on Electrical
Engineering (ICEE2004), Mashhad, Iran, 2004.
A. Abadpour, S. Kasaei, A new PCAbased robust color image watermarking
method, in: The 2nd IEEE Conference on Advancing Technology in the GCC:
Challenges, and Solutions, Manama, Bahrain, 2004.
S. Kasaei, M. Dericher, B. Biashash, A novel fingerprint image compression
technique using wavelet packets and pyramid lattice vector quantization, IEEE
Transactions on Image Processing 11(12) (2002) 13651378.
J. Ruanaidh, W. Dowling, F. Boland, Watermarking digital images for copyright
protection, IEE Proceedings on Vision, Signal and Image Processing 143(4)
(1996) 250256.
A. Nikoladis, I. Pitas, Robust watermarking of facial images based on salient
geometric pattern matching, IEEE Transaction on Multimedia 2(3) (2000)
172184.
M. Barni, F. Bartolini, A. Piva, Multichannel watermarking of color images,
IEEE Transaction on Circuits and Systems for Video Technology 12(3) (2002)
142156.
X. Kang, J. Huang, Y. Q. Shi, Y. Lin, A dwtdft composite watermarking scheme
robust to both affine transform and jpeg compression, IEEE Transactions on
Circuits and Systems for Video Technology 13(8) (2003) 776786.