1. Introduction
We present a new image compression method based on the discrete direct and inverse F1-transform which is a generalization of the classical fuzzy transform [1] [2] identified as F0-transform (for brevity, F-transform).
The F-transform compression technique [3] is a lossy compression method used in image and video analysis [4] - [18] and in data analysis [19] - [25] as well. In [26] , the concept of the F-transform was extended to the cases with various types of fuzzy partitions. In [1] [27] , the Fs-transform (s ≥ 1), a generalization of the F-transform, was presented: in other terms, the constant components of the F-transform were replaced by polynomials in order to capture more information of the original function. In particular, the F1-transform was used for the edge detection problem [1] [2] . The aim of this paper is to improve the quality of the decoded images after their compression via the F1-transform-based method.
Strictly speaking, we divide images of sizes N × M into smaller images (called blocks) of sizes N(B) × M(B) and then we code each block into another one of sizes n(B) × m(B), where n(B) < N(B) and m(B) < M(B). The compression is performed by calculating the direct F1-transform components with first degree polynomials. Afterwards, we calculate the inverse F1-transform and obtain the corresponding decoded blocks, recomposed to obtain the final reconstructed image. In Figure 1, we describe this process in detail.
The compression rate is given by
. The quality of a decoded image is measured by the Peak Signal to Noise Ratio (PSNR) index.
In Section 2, we recall the definition of h-uniform generalized fuzzy partition and the concept of F1-transform. In Section 3, a F1-transform-based compression method is presented and it is applied to images considered as fuzzy relations: there every image is partitioned into smaller blocks and the direct and inverse F1-transforms are calculated for each block. Then the decoded blocks are recomposed and the PSNR index is calculated. In Section 4, tests are applied to grey image datasets and the results are compared with similar results obtained by using the classical F-transform compression method. Section 5 contains the conclusions.
2. Generalized Fuzzy Partition and F1-Transform
We recall the main concepts [2] that will be used in the sequel. We consider a set of points (called nodes)
of
such that
. We say that the fuzzy sets
form a generalized fuzzy partition of
, if for each
, there exist
such that
,
and the following constraints hold:
Figure 1. The F1-transform image compression method.
1) (locality)
if
and
if
,
2) (continuity) Ak is continuous in
,
3) (covering) for each
,
.
The fuzzy sets
are called basic functions. If the nodes
are equidistant, i.e.
for
, where
, if
and the following additional properties hold:
4)
,
and
for each
and
,
5)
and
for every
and
, then
is called an
-uniform generalized fuzzy partition. In this case we can find a function
, called generating function, which is assumed to be even, continuous and positive everywhere except on the boundaries, where it vanishes, in such a way we have that for
:
(1)
If
, then the
-uniform generalized fuzzy partition is said h-uniform generalized fuzzy partition. We can extend the notion of h-uniform generalized fuzzy partition from an interval to the rectangle
, so that we have the family of basic functions
, where
is the product of the corresponding functions from the h1-uniform generalized fuzzy partition
of
and from the h2-uniform generalized fuzzy partition
of
. Then we can say that
is an h-uniform generalized fuzzy partition of
, where
. In the sequel we consider only such h-uniform generalized fuzzy partitions.
Let
be a basic function of
and
be the Hilbert space of square integrable functions
(reals) with weighted inner product:
Likewise, we define the Hilbert space
of square integrable in two variables functions
with weighted inner product:
(2)
Two function
are orthogonal if
. Let
and
,
be two linear subspaces of
and
with orthogonal basis given by polynomials
and
, respectively.
We consider an integer
and all pairs of integers (i, j) such that
. We introduce a linear subspace
of
having as orthogonal basis the following:
(3)
where s is the maximum degree of polynomials
. For s = 1, the orthogonal basis of the linear space
is the following:
(4)
Let
be a set of functions
such that for
,
,
, where the function
is the restriction of f on
. Then the following theorem holds:
Theorem 1. ( [2] , lemma 5). Let
. Then the orthogonal projection of
on
,
, is the polynomial of degree s given by
(5)
for every
, where the coefficients
are given by
(6)
Following [2] , let
be an h-uniform generalized fuzzy partition of
and
. For s = 1, the orthogonal basis of the linear subspace
is given by the polynomials:
(7)
Let
be the orthogonal projection of
on
given point wise as
(8)
for every
, where the three coefficients
are defined by Theorem 1:
(9)
(10)
(11)
Then the matrix
, defined from (8), is called F1-transform of the function
with respect to the h-uniform generalized fuzzy partition
. We define the inverse F1-transform of the function
to be a function
as
(12)
For sake of completeness, we point out the utility of the concept of inverse F1-transform which stands in the approximation of the function
under certain suitable assumptions. For example, we have the following result:
Theorem 2. ( [2] , theorem 14). Let
be an h-uniform generalized fuzzy partition of
and
be the inverse F1-transform of
with respect to this fuzzy partition. Moreover let
be four times continuously differentiable on
and Ak (resp., Bl) be four times continuously differentiable on
(resp.,
). Then the following holds for every
:
(13)
In other words, the Equality (13) says that we can approximate a function in two variables, four times continuously differentiable on
, with the inverse F1-transform (12) unless to O (h2).
3. F1-Transform Image Compression Method
We are interested to the case discrete, i.e. we consider functions in two variables which assume a finite number of values in
like finite fuzzy relations. Indeed, let R be a grey image of sizes
,
,
being the normalized value of the pixel
, that is
if Nlev is the length of the grey scale. Let
and
be two h-uniform generalized fuzzy partitions of
and
, respectively, where
,
,
,
,
,
. Slightly modifying (8), then we can define the (discrete) F1-transform
of R the matrix whose entries are defined as
(14)
where
,
,
are given as (by rewriting the Equations (9), (10), (11) in the following form, slightly modified):
(15)
(16)
(17)
The Formula (14) is considered as a compressed image of the original image R.
can be decoded by using the following inverse (discrete) F1-transform
defined for every
as
(18)
We divide the image R of sizes
in sub-matrices RB of sizes
, called blocks ( [26] [28] ), each compressed to a block
of sizes
,
,
, via the discrete F1-transform, as Formula (14), of components
given by
(19)
We rewrite (15), (16), (17) as
(20)
(21)
(22)
The basic functions
and
form an h-uniform generalized uniform fuzzy partition of
and
, respectively. They are generated by the basic functions
and
, respectively. Then we have that
(23)
where
,
,
and
(24)
where
,
,
,
. In Figure 2, we show the basic functions (23) for N = 16 and n = 4.
The compressed block
is decoded to a block
of sizes
by using the inverse F1-transform defined for every
as
(25)
which approximates the original block RB. Making the union of all the decoded blocks R1B, we obtain a fuzzy relation (denoted with) R1 of sizes
. Then we measure the RMSE (Root Mean Square Error) given by
Figure 2. Cosine basic functions (N = 16, n = 4)
(26)
which implies that PSNR is the following:
(27)
4. Test Results
We compare our method with the classical F-transform compression method, but here no comparison is made with the one inspired to the Canny method used in [2] .
For our tests we have considered the CVG-UGR image database extracting grey images of sizes 256 × 256 (cfr., http://decsai.ugr.es/cvg/dbimagenes/). For brevity, we only give the results for three images as Lena, Einstein and Leopard whose sources are given in Figures 3(a)-(c), respectively.
In Table 1, we show the PSNR of the F-transform and F1-transform methods for some values of the compression rate in the image Lena.
We make the following remarks on Table 1:
− for weak compression rates the quality of the decoded image under the F1-transform method is better than the one obtained with the F-transform method;
− for strong compression rates the quality of the images decoded in the two methods is similar;
− the difference between the two PSNR’s in the two methods overcomes 0.1 for ρ > 0.25.
In Figure 4, we show the trend of the PSNR for the two methods.
In Figures 5(a)-(d) (resp., Figures 6(a)-(d)), we show the decoded images of Lena obtained by using the F-transform (resp., F1-transform) for ρ = 0.0.0625, 0.16, 0.284444 and 0.444444, respectively.
(a) (b) (c)
Figure 3. (a) Lena; (b) Einstein; (c) Leopard.
Figure 4. PSNR trend for the source image Lena.
Table 1. PSNR of the F-transform and F1-transform methods for some values of the compression rate in the image Lena.
In Table 2 and Figure 7, we show the PSNR obtained using the F-transform and F1-transform methods for some values of the compression rate in the image Einstein: this table confirms the same results obtained for the image Lena in Table 1.
In Figures 8(a)-(d) (resp., Figures 9(a)-(d)) we show the decoded images of Einstein obtained using the F-transform (resp., F1-transform) method for ρ = 0.0.0625, 0.16, 0.284444 and 0.444444, respectively.
In Table 3 we show the PSNR values obtained using the F-transform and F1-transform methods for some values of the compression rate in the image Leopard.
Figure 7. PSNR trend for the source image Einstein.
Table 2. PSNR results obtained for the source image Einstein.
Table 3 confirms the results obtained for the images Lena and Einstein: the quality of the decoded image obtained by using the F1-transform is better than the one obtained using the F-transform for weak compression rates. In Figure 10, we show the trend of the PSNR index obtained by using the two methods.
In Figures 11(a)-(d) (resp., Figures 12(a)-(d)), we show the decoded images of Leopard obtained by using the F-transform (resp., F1-transform) method for ρ = 0.0.0625, 0.16, 0.284444, 0.444444, respectively.
In Figure 13, we show the trend of the difference of PSNR by varying the compression rate for all the images in the dataset above considered.
Figure 10. PSNR trend for the source image Leopard.
Table 3. PSNR results obtained for the source image Leopard.
Figure 13. PSNR trend for all the images in the dataset considered.
Summarizing, we can say that the presence of the coefficients of the F1-transform is negated by noise introduced during the strong compressions, while this effect increases considerably using weak compressions rates.
5. Conclusion
We give an image compression method based on the direct and inverse F1-transform. The results show that the PSNR of the reconstructed images with the F1-transform-based compression method is better than the one obtained with the F-transform-based compression. In the tested dataset of images, we find that the difference between the two corresponding PSNR values is greater than 0.1 (resp., 0.25) for ρ = 0.25 (resp., ρ ≈ 0.5). In the next papers, we shall use the F1-transform in data analysis problems.
Acknowledgements
We also accomplish this research under the auspices of the INDAM-GCNS, Italy. The last author acknowledges a partial support from the European Regional Development Fund in the IT4Innovations Centre of Excellence project (CZ.1.05/ 1.1.00/02.0070).