=Paper=
{{Paper
|id=Vol-2654/paper16
|storemode=property
|title=Analytical Links in the Tasks of Digital Content Compression
|pdfUrl=https://ceur-ws.org/Vol-2654/paper16.pdf
|volume=Vol-2654
|authors=Olena Kolganova,Viktoriia Kravchenko,Lidiia Tereshchenko,Volodymyr Shutko,Mykola Shutko,Yevhen Vasiliu
|dblpUrl=https://dblp.org/rec/conf/cybhyg/KolganovaKTSSV19
}}
==Analytical Links in the Tasks of Digital Content Compression==
https://ceur-ws.org/Vol-2654/paper16.pdf
Analytical Links in the Tasks of Digital Content
Compression
Olena Kolganova 1[0000-0002-1301-9611], Viktoriia Kravchenko 1[0000-0003-0399-7013],
Lidiia Tereshchenko 1[0000-0001-8183-9016], Volodymyr Shutko 1[0000-0002-9761-5583]
and Mykola Shutko 1[0000-0002-3531-7724], Yevhen Vasiliu 2[0000-0002-8582-285X]
1
National Aviation University, Kyiv, Ukraine
2
O.S.Popov Odessa National Academy of Telecommunication, Odessa, Ukraine
kolganova@nau.edu.ua, vnshutko@nau.edu.ua
Abstract. The article is devoted to the development of a digital image compres-
sion algorithm. Image compression is a type of data compression applied to dig-
ital images, to reduce their cost for storage or transmission. Algorithms may
take advantage of visual perception and the statistical properties of image data.
We will consider a lossy compression algorithm. The new algorithm is based on
multiscale decomposition with a spline as a basis function. In the process of
multiscale analysis, when constructing a spline, we should take into account
analytical links. The application of this approach give an increase in the com-
pression ratio with the same quality of compressed images.
Keywords: Digital Image Compression, Analytical Links, Hermitian Spline,
Multiscale Analysis.
1 Introduction
Multimedia standards for video compression for personalized television, high defini-
tion digital television (HDTV), and image / video database maintenance use close
motion and encoding methods. Three basic standards - MPEG-1, MPEG-2 and
MPEG-4 were developed by the Moving Picture Experts Group (MPEG), under the
auspices of the ISO and the International Telegraph and Telephone Consultative
Committee (was renamed the International Telegraph Union (ITU). A typical MPEG
encoder uses redundancy both within the frame and between adjacent frames, the
uniformity of movements between frames, and the psychophysical properties of the
human visual system. Each frame is compressed as a digital image [1].
Image compression is when you remove or group together certain parts of an im-
age file in order to reduce its size. Here are a few reasons.
For website optimization. Sites with uncompressed images can take longer to
load, and can cause your visitors to bounce because of this.
For sending and uploading images. Uploading an uncompressed image can take
a while, and some email servers have a file size limit.
For reducing the storage impact on your hard drive.
Copyright © 2020 for this paper by its authors. Use permitted under Creative Commons Li-
cense Attribution 4.0 International (CC BY 4.0). CybHyg-2019: International Workshop on
Cyber Hygiene, Kyiv, Ukraine, November 30, 2019.
Image compression is useful for a variety of reasons and it is dependent upon the
image size reduction you aim to achieve along with the quality level you plan to keep
that will determine which form of compression you should use.
There are two kinds of image compression methods - lossless and lossy.
Lossy compression methods, especially when used at low bit rates, introduce
compression artifacts. Lossy methods are especially suitable for natural images such
as photographs in applications.
JPEG, this format gets rid of bits and pieces of a photo that you may notice de-
pending upon the level of compression you apply. A normal amount of compression
will not be noticeable, while extreme compression may be obvious. If you rotate the
JPG too much, you’ll notice a difference in quality. This is because the photo has to
recompress itself with every rotation, losing some data in the process. There are how-
ever programs out there that rotate a JPG losslessly.
2 Literature Analysis and Problem Statement
Methods for lossy compression:
Transform coding – This is the most commonly used method.
Discrete Cosine Transform (DCT) – The most widely used form of lossy com-
pression. It is a type of Fourier-related transform [2]. The DCT is sometimes re-
ferred to as "DCT-II" in the context of a family of discrete cosine transforms. It
is generally the most efficient form of image compression.DCT is used in
JPEG, the most popular lossy format.
Wavelet transform is also used extensively, followed by quantization and en-
tropy coding.
Reducing the color space to the most common colors in the image. The selected
colors are specified in the colour palette in the header of the compressed image.
Each pixel just references the index of a color in the color palette, this method
can be combined with dithering to avoid posterization.
Chroma subsampling. This takes advantage of the fact that the human eye per-
ceives spatial changes of brightness more sharply than those of color, by aver-
aging or dropping some of the chrominance information in the image.
Fractal compression.
An important development in image data compression was the discrete cosine
transform (DCT), a lossy compression technique first proposed by Nasir Ahmed in
1972.[8] DCT compression became the basis for JPEG, which was introduced by the
Joint Photographic Experts Group (JPEG) in 1992.[9] JPEG compresses images down
to much smaller file sizes, and has become the most widely used image file format
[10]. Its highly efficient DCT compression algorithm was largely responsible for the
wide proliferation of digital images and digital photos [11], with several billion JPEG
images produced every day as of 2015 [12].
We propose to use spline multiscale analysis with the imposition of analytical
links instead DCT or wavelet decomposition in the compression process.
In [22] the problem of reconciliation of flight data with the use of a priori analyti-
cal excess, which is in kinematic ratios and equations of motion of the center of mass,
which are expressed due to overload (acceleration) in the center of mass, is consid-
ered. Other a priori links between the measured parameters are also possible. This
article discusses various model problems of smoothing two or more time series in the
presence of linear and nonlinear a priori analytical relations between the measured
values. It is natural to use such a priori connections, both when systematic errors are
estimated and to improve the accuracy of data processing in the presence of random
errors. Articles [25,26] show that taking into account the analytic coupling reduces
the root mean square deviation of the constructed spline from its deterministic basis,
so decreases the error value.
The use of wavelet signal processing in MPEG-4 provides the ability to effectively
compress and recover signals with low quality loss, as well as to solve signal filtering
problems. One of the main and especially productive ideas of wavelet signal represen-
tation at different levels of decomposition is to separate the approximation functions
of the signal into two groups: approximate - rough (with sufficiently slow time dy-
namics of changes), and detailing (with local and fast dynamics of changes against the
background of smooth dynamics), with their further fragmentation and detailing at
other levels of signal decomposition (multiscale analysis).
It is interesting to consider analytic communication in the process of multiscale
analysis with the spline functions used to compress graphical data.
3 Spline approximation of analytically linked image lines
Consider the problem in this formulation.
The sequences of two rows of the matrix of the same color component of the digi-
tal image are represented by counts:
y1 (t ) y1 (1), y1 (2),..., y1 ( N )
and
y2 (t ) y2 (1), y2 (2),..., y2 ( N ).
Consider the procedure for building a spline.
Let on the segment [a, b] in the points X = xi iN1 the values Y = yi iN1 of some
smooth function are given.
You need to find a grid r ~
xj
r
j 0 r N , where you can build a spline
S ( x ) Cka , b , K 1,2,... , that has continuous derivatives up to kth order (includ-
ing). According to the formulation of the problem, the grids N і r does not
coincide, that is, on each section of the grid r there may be several points, which
will determine the behavior of the desired dependency.
Fig.1. The example of a smooth function
Consider the construction of third- and fifth-degree Hermitian splines with differ-
ent derivatives values at the knots of the grid r . By analogy, we take as an approx-
imate value of the first derivative at the point
a j a j 1 a j 1 a j ,
aj j j
hj h j 1
and as an approximate value of the second derivative
a j 2a ~
x j 1 , ~
xj,~
x j 1 .
Taking into account the above relations in the construction of the Hermitian cubic
spline the elements of the planning matrix X will be determined by the formulas:
xi 0 1X i 2 I x ~
x2 2X i1I x ~
x1 , i 1, m2 ,
xi1 1X I ~ x 2X I ~
i3 x 3 x 3X I ~
i2 x x , i 1, m ,
2 i1 x 1 3
x ij X ij 2 I x ~
1
x j 2 2X ij 1 I x ~
x j 1 3X ij I x ~
x j 4X ij 1 I x ~
x j 1 ,
j 2, r 2 , i 1 m1 , mr 2 ,
x ir 1 X i r I x ~
2
xr 3X i r 1I x ~
xr 1 4X i r 2 , i 1 mr 3 , mr ,
x ir 3X I ~ i r x
x 4X r I (~ x ), i 1 m ,m
i r 1 x r 1 r 2 r
1 if x ~
xj ~xj ~ x j 1
where I x ~
xj
0
if x ~
x , j 1, r;
j
1
X ij
h 2j xij 1 xij , j 2, r , i 1 m , m ;
2
h j 1 h j 1 h j
j 1 j
h1 xi21 1 xi1 i 1, m
2
X i1 1 xi1 , 1 ;
h1 h2
h j xij2 1 xij h j xij 1 xij
2
X ij 1 xij , j 2, r 1 , i 1 m j 1 , m j ;
h h
2
j j 1 h j 1
hr xir 1 xir
2
2
X ir 1 xir , i 1 mr 1 , mr ;
hr 1
h x 2 1 xi1
3
X i1 xi1 1 i1 , i 1, m1 ;
h2
h j xij2 1 xij h j xij 1 xij
2
3
X ij xij , j 2, r 1 , i 1 m j 1 , m j ;
h j 1 h j 1 h j
h x 1 xir i 1 m , m ;
2
X ir xir r ir
3
, r 1 r
hr 1 hr
h 2j xij2 1 xij
4
X ij , j 1, r 1 , i 1 m j 1 , m j ;
h j 1 h j h j 1
xi ~
x j 1
xij ; hj ~
xj ~
x j 1 ; j 1, r ;
hj
xi ~
x j 1 , ~
xj , j 1, r 1 ; xi ~ xr ;
xr 1 , ~
m j u 1 K u , j 1, r ; m1 m0 0 ; mr N ;
j
where K u is the amount of the counting on the u-th segment.
We approximate these rows by cubic Hermitian splines so that there is a "bonded"
connection between the joints of the splines of these splines, which would approxi-
mate the sum of the image counts at the corresponding points. To do this, we add the
following functional in the form:
N N r
[ y1 (i) S1 (ti )]2 [ y2 (i) S2 (ti )]2 [ y1 ( j ) y2 ( j ) S1 (t j ) S2 (t j )]2 ,
i 1 i 1 j 1
where: S1 (t ) XA1 and S 2 (t ) XA2 - cubic Hermitian splines that approxi-
mate image lines y1 (t ) and y2 (t ) ;
X - scheduling matrix;
A = { a j }rj=1 - vectors of estimated parameters (ordinates of points where
spline fragments "gluing"), in this case weight 1.
The value of the local Hermitian cubic spline at an arbitrary point is calcu-
lated by the formula:
S( ) = a j -1 x( )+ a j x( )+ a j+1 x( )+ a j+2 x( )
1 2 3 4
for [ u j ,u j+1 ] , where x( ) - local functions of shape, k 1 4 ,
k
a j – the values of the knots’ ordinates, j 1,2,..., r .
We will require the least squares (the least-squares method) condition to be
satisfied: min . This requires a solution of the system of 2r equations:
0, j 1, r ;
a1 j
0, j 1, r.
a2 j
It is more expedient to solve this system in matrix form. Then the require-
ments of the least-squares method (LSM):
(Y PA)T (Y PA) min ,
where:
Y1
Y Y2 , Y1 [ y1 (1), y1 (2),..., y1 ( N )] , Y2 [ y2 (1), y2 (2),..., y2 ( N )] –
T T
D
vectors of initial time sequences;
D [ y1 (1) y2 (1), y1 (3) y2 (3),..., y1 ( N 1) y2 ( N 1)]T , dimension ( N *1) ;
2
A1
A , A1 [a11 , a12 ,..., a1r ]T , A2 [a21 , a22 ,..., a2 r ]T – vectors of ordi-
A2
nates of knots, where spline fragments "gluing";
X
P X , X – block-diagonal scheduling matrices whose columns
X vuz X vuz
are local spline functions x(t), k 1...4 [3, 4], X vuz – block-diagonal
k
scheduling matrices whose columns are local spline functions thinned twice
N
for the number of knots ; O – is a zero matrix of dimension N * r .
2
Dimension of the matrix P – ( 2,5 N * 2r ) .
Here is the classic LSM solution:
A ( P T P) 1 P T Y ,
and S1 XA1 , S2 XA2 – splines that have already been constructed to al-
low for the "linked" connection between the knots where these splines "glue".
4 Comparative analysis
We will carry out the comparative analysis as follows:
1) we approximate the rows of the matrices of all the color components of
the digital image presented below (Fig. 1) by cubic Hermitian splines with the
number of “gluing” knots N ;
2
2) we calculate the difference R1 between the lines of the original image
and the resulting splines;
3) we assign zero values to the R1 coefficients which are less by the abso-
lute value of a certain threshold;
4) we store non-zero values in the computer memory;
5) repeat the above steps, taking as the initial ordinates the knots of
splines, approximating the rows of the matrices of all the color components of
the digital image (Fig. 2);
Fig.2. An example of a color digital image
6) the same algorithm will be applied to the method proposed in this paper,
where splines are already constructed taking into account the "bonded" link
between the knots of these splines, which approximates the sum of the frames
of images at the appropriate points;
7) we compare the compression coefficients at the same standard devia-
tions (SLE) from the original of the images reconstructed after compression
by these two methods (Fig. 3, Fig. 4).
Fig.3. Image restored after compression by cubic Hermitian splines and calculating
detail coefficients.
Fig.4. Image restored after compression by cubic Hermitian splines with a "wish on"
link between the knots where "gluing" these splines and calculating the detail
coefficients [26-27.
5 Conclusion
The aim of this paper is not to develop a complete method for two-dimensional com-
pression of digital images. One-dimensional line compression revealed the advantages
of approximation by cubic Hermitian splines, taking into account the "bonded" con-
nection between the knots of these splines (Fig. 3) compared to the approximation
without taking into account such a connection (Fig. 2). We can come to the conclu-
sion that this approach is perspective for further development.
References
1. "Image Data Compression".
http://user.engineering.uiowa.edu/~dip/lecture/DataCompression.html
2. Nasir Ahmed, T. Natarajan and K. R. Rao, "Discrete Cosine Transform," IEEE Trans.
Computers, 90–93, Jan. 1974.
3. Burt, P.; Adelson, E. (1 April 1983). "The Laplacian Pyramid as a Compact Image
Code". IEEE Transactions on Communications. 31 (4): 532–540. CiteSeerX 10.1.1.54.299.
doi:10.1109/TCOM.1983.1095851.
4. Shao, Dan; Kropatsch, Walter G. (February 3–5, 2010). Špaček, Libor; Franc, Vojtěch
(eds.). "Irregular Laplacian Graph Pyramid" (PDF). Computer Vision Winter Workshop
2010. Nové Hrady, Czech Republic: Czech Pattern Recognition Society.
5. Claude Elwood Shannon (1948). Alcatel-Lucent (ed.). "A Mathematical Theory of Com-
munication" (PDF). Bell System Technical Journal. 27 (3–4): 379–423, 623–656. Re-
trieved 2019-04-21.
6. David Albert Huffman (September 1952), "A method for the construction of minimum-
redundancy codes" (PDF), Proceedings of the IRE, 40 (9), pp. 1098–
1101, doi:10.1109/JRPROC.1952.273898
7. William K. Pratt, Julius Kane, Harry C. Andrews: "Hadamard transform image coding", in
Proceedings of the IEEE 57.1 (1969): Seiten 58–68
8. Ahmed, Nasir (January 1991). "How I Came Up With the Discrete Cosine Trans-
form". Digital Signal Processing. 1 (1): 4–5. doi:10.1016/1051-2004(91)90086-Z.
9. "T.81 – Digital compression and coding of continuous-tone still images – requirements
and guidelines". CCITT. September 1992. Retrieved 12 July 2019.
10. "The JPEG image format explained". BT.com. BT Group. 31 May 2018. Retrieved 5 Au-
gust 2019.
11. "What Is a JPEG? The Invisible Object You See Every Day". The Atlantic. 24 September
2013. Retrieved 13 September 2019.
12. Baraniuk, Chris (15 October 2015). "Copy protections could come to JPEGs". BBC
News. BBC. Retrieved 13 September 2019.
13. "The GIF Controversy: A Software Developer's Perspective". Retrieved 26 May2015.
14. L. Peter Deutsch (May 1996). DEFLATE Compressed Data Format Specification version
1.3. IETF. p. 1. sec. Abstract. doi:10.17487/RFC1951. RFC 1951. Retrieved 2014-04-23.
15. Hoffman, Roy (2012). Data Compression in Digital Systems. Springer Science & Business
Media. p. 124. ISBN 9781461560319.
16. Taubman, David; Marcellin, Michael (2012). JPEG2000 Image Compression Fundamen-
tals, Standards and Practice: Image Compression Fundamentals, Standards and Prac-
tice. Springer Science & Business Media. ISBN 9781461507994.
17. Jump up to:a b Unser, M.; Blu, T. (2003). "Mathematical properties of the JPEG2000
wavelet filters" (PDF). IEEE Transactions on Image Processing. 12 (9): 1080–
1090. doi:10.1109/TIP.2003.812329.
18. Sullivan, Gary (8–12 December 2003). "General characteristics and design considerations
for temporal subband video coding". ITU-T. Video Coding Experts Group. Retrieved 13
September 2019.
19. Bovik, Alan C. (2009). The Essential Guide to Video Processing. Academic Press.
p. 355. ISBN 9780080922508.
20. Gall, Didier Le; Tabatabai, Ali J. (1988). "Sub-band coding of digital images using sym-
metric short kernel filters and arithmetic coding techniques". ICASSP-88., International
Conference on Acoustics, Speech, and Signal Processing: 761–764
vol.2. doi:10.1109/ICASSP.1988.196696.
21. Swartz, Charles S. (2005). Understanding Digital Cinema: A Professional Hand-
book. Taylor & Francis. p. 147. ISBN 9780240806174.
22. Kasianov V. The Flight Modelling: Monography. –Kyiv: NAU, 2004.
23. Shutko M. Methods and means of increasing the reliability of measurement information
processing and control of parameters of radio-electronic systems for air traffic control //
Author's abstract. Diss. Dr. Tech. Sciences: 05.22.14 / KIIGA. - K., 1991.
24. Kasyanov V., Shutko V., Shelevitsky I. Spline approximation of analytically bound time
series.Vis. Nauk. - K .: NAU, 2001, No. 4 (11), pp. 117 - 120.
25. Shutko V. Spline approximation of estimates of correlation sequences of harmonic signals
// Visn. NAU, Kyiv, NAU, 2002, No. 1 (12), P. 73 - 77.
26. Odarchenko R., Abakumova A., Polihenko O., Gnatyuk S. Traffic offload improved meth-
od for 4G/5G mobile network operator, Proceedings of 14th International Conference on
Advanced Trends in Radioelectronics, Telecommunications and Computer Engineering
(TCSET-2018), pp. 1051-1054, 2018.
27. M. Zaliskyi, R. Odarchenko, S. Gnatyuk, Yu. Petrova. A. Chaplits, Method of traffic
monitoring for DDoS attacks detection in e-health systems and networks, CEUR Work-
shop Proceedings, Vol. 2255, pp. 193-204, 2018.