-Lossy image compression algorithm based on fractal discrete cosine transform is proposed in this paper. The created algorithm is compared to an algorithm based on twodimensional experimentally discrete cosine transform.
(1), as image
which
Discrete
discrete orthogonal transforms (DOTs) are
cosine
transform
(DCT),
namely,
its
used.
twodimensional variation, is widely used in the field of image
processing. Since two-dimensional DCT is defined on a
square region, the resulting artifacts in compression have a
very noticeable mesh structure. To eliminate this effect, one
can use the classical one-dimensional DCT applied to the
sweep generated by some canonical number system (CNS)
[
II.
This section provides brief theoretical information about
the CNS in imaginary quadratic fields [
Let (√ ) is a quadratic field: (√ ) = { = + ; , ∈ }, d is an integer, free of squares. Then the field element ∈ (√ ) is called a whole algebraic field element if its norm and trace are integers
( ) = ( + √ )( − √ ), ( ) = ( + √ ) + ( − √ ).
The whole algebraic element ∈ (√ ) is the basis of the CNS in the ring of integer elements (√ ), if any whole element of this field is uniquely representable in the form of a finite sum [2].
Copyright © 2020 for this paper by its authors. = ∑ =0 , ∈ = {0,1, . . , | ( )| − 1} (1)
CNS in the field (√ ) is called a pair {α, N} , kfundamental domain is the set of algebraic elements of the field (√ ), created by k-membered sum of a formula = {∑ =−01 , ∈ }. (2) Let COS ( , ) = ( )Im( ) ) , where parameter β is set for the reason of orthogonality: ∑ ∈ COS ( , )⋅ COS ( , ) = 0, ≠ ,
( ) = 2 parameter β is calculated = +1−2 +1. 2( −1) Then FDCT over is called a transformation ( ) = ( )∑ ∈ ( ) ( , ), where
∈ , and ( ) is FDCT.
Reverse FDCT (RFDCT) is called
( ) = ∑ ∈ ( ) ( ) ( , ),
where ∈ , and ( ) is the normalizing coefficient of
The normalizing coefficient of FDCT and RFDCT is equal and is calculated using the following equation: ( ) = √
√ { 1 2 ( ), 2 ( ), 2 ≡ 0( ≠ 0( ) ) . orthogonality of the basis functions:
The field is found algorithmically for the reasons of ∑ COS ( , )⋅ COS ( , ) = 0;
∈ ; , ∈ ; ≠ ∑ COS ( , )⋅ COS ( , ) ≠ 0;
∈ ; , ∈ ; = The algorithm for calculating this region is described in
Two-dimensional DCT is called the transformation ∑ 1−1 ∑ 22=−01 ( 1, 2) 1=0 ( 1, 2 ) = 1 brightness), is the size of the i-th side of the block, and ( 1, 2) is the resulting spectrum of the source signal.
Then the inverse two-dimensional DCT is called the transformation where ( ) is a normalizing coefficient calculated as ( ) = { √ √ 1 , = 0 2 , ≠ 0 .
following steps:
The studied compression algorithm consists of the splitting the image into blocks; calculating the DOT for each of the blocks; quantization of the obtained frequency domain (lossy compression); packing of quantized
spectral components for subsequent lossless compression. where is i-th component of the quantization vector (or matrix), is i-th component of the mean squared error is the maximum value of the standard deviation for all components, Q is the algorithm parameter, which is the image compression ratio setting. The meaning of this formula is to give more quantization levels to a component with a larger standard deviation. For example, for FDCT = −1 + , = 3, the quantization vector at = 1 is equal to The quantized values of the spectral components are sequentially, 2 bytes were allocated to each III.
The comparison was carried out on 10 halftone images 512×512 in size from the
were compressed by algorithms using two-dimensional DCT on blocks 4 х 4 and 8 х 8 and FDCT with parameters =
As a comparative measure of visual quality, PSNR, or the ratio of peak signal to noise, and MSSIM, or a measure of structural similarity averaged over the image, were chosen.
PSNR is calculated by the formula 10 1
10 1 2 ( , ) = 20 where x and y are the compared grayscale images, 1, 2 are image width and height respectively; PSNR value is measured in decibels. The higher the PSNR value, the less the image has changed compared to the original.
MSSIM is calculated as the average SSIM for disjoint 88 blocks : where x and y are grayscale images being compared, M is the number of 88 blocks, 1 = 2.55 , 2 = 7.65 . MSSIM values range from -1 to 1, the higher value corresponds to a better visual similarity of two images [7].
To assess the degree of compression, informational entropy was used. Information entropy shows how much information the spectral component carries on average after compression [8], and describes the theoretical limit of sequence compression. Accordingly, the lower the value of entropy, the greater the compression ratio can be achieved by compressing this sequence. Entropy was calculated from a sequence of quantized spectral components by the formula = − ∑65535 =0 2 , where – is the probability of occurrence of the value of i in the sequence.
As a result of the study, it turned out that for most images for equal values of entropy, algorithms based on twodimensional DCT show the best values of comparative measures of visual quality compared to algorithms based on FDCT (Fig. 2), but the following can be noted: firstly, when the entropy is one and a half bits per sample and higher, the MSSIM value for FDCT-based algorithms differ no more than by 1%, which means that the difference is almost imperceptible.
Secondly, starting from a certain value of entropy, the visual quality of images compressed by the FDCT algorithm is superior to the visual quality of images compressed by the algorithm based on two-dimensional DCT. This can also be seen from the graphs in Fig. 2. Such a property can be useful in image transmission systems for which low PSNR values (about 20 dB) are acceptable.
Moreover, Fig. 3 shows the nature of the distortions introduced by the FDCT fractal blocks. Compared to the square blocks of two-dimensional DCT, the fractal structure is less noticeable, and the boundaries of the objects in the image are sharper, although more noisy.
Finally, it can be noted that in experiments on images consisting of text, FDCT-based algorithms showed themselves better than algorithms based on two-dimensional DCT, which makes great practical sense when working with scanned documents and books. An example of the operation of algorithms in images containing text is shown in Fig. 4.
In this paper, a lossy image compression algorithm based on a fractal discrete cosine transform was implemented and studied. The implemented algorithm was compared with the algorithm based on two-dimensional DCT. As a result, it turned out that FDCT has a completely different character of distortions introduced into the image during compression: an image compressed by the FDCT algorithm has sharper but more noisy object boundaries compared to two-dimensional DCT; the structure of fractal blocks is less noticeable than the structure of a square block of two-dimensional DCT. Despite the fact that FDCT does not show the best numerical characteristics of visual quality with an equal value of entropy compared to two-dimensional DCT, the actual visual quality differs insignificantly for some values of entropy, which can be used in a number of image processing areas.
Actual problems associated with the FDCT-based compression algorithm are the synthesis of fast FDCT algorithms, the study of FDCT-based algorithms in other kfundamental areas, as well as the synthesis of the algorithm for reducing the noise introduced by compression when using FDCT.
M.S. Kasparyan, “Fractal discrete cosine transformations on prefractal areas associated with the fundamental areas of canonical number systems,” Computer Optics, vol. 38, no. 1, pp. 148-153, 2014.