The article is devoted to the development of a digital image compression algorithm. Image compression is a type of data compression applied to digital 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 compression ratio with the same quality of compressed images.
Multimedia standards for video compression for personalized television, high definition 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 image 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.
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 depending 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 however programs out there that rotate a JPG losslessly. 2
Literature Analysis and Problem Statement
Transform coding – This is the most commonly used method. Discrete Cosine Transform (DCT) – The most widely used form of lossy compression. It is a type of Fourier-related transform [2]. The DCT is sometimes referred 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 entropy 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 perceives spatial changes of brightness more sharply than those of color, by averaging 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 analytical 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 considered. 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 representation at different levels of decomposition is to separate the approximation functions of the signal into two groups: approximate - rough (with sufficiently slow time dynamics 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
The sequences of two rows of the matrix of the same color component of the
digital image are represented by counts:
y1(t) y1(
and
y2 (t) y2 (
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 ~x r j 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 (including). According to the formulation of the problem, the grids coincide, that is, on each section of the grid r there may be several points, which will determine the behavior of the desired dependency. N і r does not ent derivatives values at the knots of the grid r . By analogy, we take as an approximate value of the first derivative at the point
h j h j 1 and as an approximate value of the second derivative
aj 2a~xj1 , ~xj , ~xj1 . aj j a j a j 1 j a j 1 a j ,
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: xi0 1X i2I x ~x2 2X i1I x ~x1 , i 1, m , 2 xi11X i3I x ~x3 2X i2I x ~x2 3X i1I x ~x1 , i 1, m3 , xij 1X ij 2 I x ~xj 2 2X ij 1I x ~xj 1 3X ij I x ~xj 4X ij 1I x ~xj 1 , j 2, r 2 , i 1 m1, mr 2 , xir12X i r I x ~xr 3X i r 1I x ~xr 1 4X i r 2 , i 1 mr 3, m , r xir 3X
I ~x 4X i r x r
~ i r 1I x (xr 1) , i 1 mr 2 , mr 1 where Ix ~xj 0 if if x ~xj ~xj ~xj1 x ~xj , j 1, r; h 2j xij 1 xij 2 h j 1h j 1 h j h j xi2j 1 xij h j xij 1 xij 2 X ij 1 xij h j h j1 h j1 , j 2, r 1, i 1 m j 1, m ; j 3
X ij xij
j i2j 1 x h x
ij h j 1 h j xij 1 xij 2
h j 1 h j 2 X ir 1 xir hr xir 1 xir , i 1 mr 1, m ; 2 r 3
X i1 xi1 1 i211 x h x i1 , i 1, m ;
1 hr1 h2 , j 2, r 1, i 1 m j 1, m ; j h 2j xi2j 1 xij
hr 1 hr 3 X ir xir hr xir 1 xir , i 1 mr 1, m ; 2 r 4 X ij
h j1 h j h j1 , j 1, r 1, i 1 m j 1, m j ; xij xi ~xj 1 ; h j ~xj ~xj 1 ; j 1, r ;
h j xi ~xj1 , ~xj ,
j 1, r 1 ; xi ~xr 1, ~xr ; m j uj 1 Ku , j 1, r ; m1 m0 0 ; mr N ; 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 approximate 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 , i1 i1 j1 where: S1(t) XA1 and S2 (t) XA2 - cubic Hermitian splines that approximate image lines y1(t) and y2 (t) ; X - scheduling matrix;
r
A = { a j }j=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 calculated by the formula:
S( ) = a j-1 1 x( )+ a j 2 x( )+ a j+1 3 x( )+ a j+2 4 x( ) for [ u j ,u j+1 ] , where
k x( ) - local functions of shape, k 1 4 , 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: a1 j a2 j 0,
j 1, r ; 0,
j 1, r.
It is more expedient to solve this system in matrix form. Then the requirements of the least-squares method (LSM):
(Y PA)T (Y PA) min , where:
Y1 Y Y2 ,
Y1 [ y1(
Y2 [ y2 (
X P X , X – block-diagonal scheduling matrices whose columns X vuz X vuz
k x(t), are local spline functions scheduling matrices whose columns are local spline functions thinned twice k 1...4 [3, 4], X vuz – block-diagonal for the number of knots N ; O – is a zero matrix of dimension N * r .
2 Dimension of the matrix P – (2,5N * 2r) .
Here is the classic LSM solution:
A (PT P)1 PT Y , and S1 XA1 , S2 XA2 – splines that have already been constructed to allow for the "linked" connection between the knots where these splines "glue". 4
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 absolute 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);
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 deviations (SLE) from the original of the images reconstructed after compression by these two methods (Fig. 3, Fig. 4).
The aim of this paper is not to develop a complete method for two-dimensional
compression of digital images. One-dimensional line compression revealed the advantages
of approximation by cubic Hermitian splines, taking into account the "bonded"
connection 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
conclusion that this approach is perspective for further development.
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 (
p. 355. ISBN 9780080922508.
20. Gall, Didier Le; Tabatabai, Ali J. (1988). "Sub-band coding of digital images using
symmetric 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
Handbook. 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 (