WAVELET video compression algorithm.

Any image entered into a computer is digitized and stored in it in the form of a so-called bitmap or, in other words, a matrix, each element of which describes the color of a point on the original image.

The number of matrix elements (image points) depends on the resolution selected during digitization.

However, storing it in this form is not profitable due to the use of a large amount of computer memory.

Therefore, numerous bitmap encoding (compression) algorithms have been developed at present, the efficiency of which depends on the properties of the image (obviously, to store a «black square» it is not at all necessary to store a matrix of black dots, but it is quite sufficient to store three numbers: width, height and color).

All these algorithms are divided into two groups: lossless coding (when the original bitmap is completely restored as a result of the decoding procedure) and with loss of information. In a broader application, the algorithms of the first group are often called data archiving.

Let's consider in more detail the algorithm for image compression with loss of information.

The loss of information in this case means that the reconstructed image will not be an exact match for the original, but the differences will be virtually unnoticeable to the human eye (in such cases, the «compression quality» is usually specified by a parameter with possible values ​​from 0 to 100, where 100 means minimal compression, i.e. the best quality, and the reconstructed image is virtually indistinguishable from the original, while 0 means maximal compression, at which the reconstructed image can still discern the main details of the original).

Currently, most continuous-tone images (images containing many slightly different colors) stored on computers are encoded using the JPEG algorithm.

The main stages of this algorithm are as follows. The image is divided into 8×8 dot patterns.

A discrete cosine transform is performed for each pattern (matrix). Then, the most significant frequencies for visual perception are selected from the resulting frequencies using a special weight table.

This procedure is called quantization and is the only stage at which information is lost.

Next, the matrix of selected frequencies is represented in a compact way and encoded by the so-called entropy method (Huffman or arithmetic).

The difference of our algorithm is that it uses WAVELET instead of discrete cosine transform, and also applies the transform to the full image, not to an 8×8 template.

So what is WAVELET?

The word «WAVELET» means a small wave.

By small we mean that this function has a finite length.

Wave reflects the fact that the WAVELET function oscillates.

WAVELET is a family of functions that are local in time and frequency, and in which all functions are obtained from one by shifting and stretching it along the time axis (so that they «follow each other»), which makes it possible to analyze the signal at all points.

Mathematicians sometimes call WAVELETs bursts, which characterizes them in a certain way.

The first feature of WAVELETs is that they have the property of simultaneous locality in frequency and time.

It is this property that made them so suitable for use.

And WAVELETs became most popular when another of their properties was discovered — the presence of a fast conversion algorithm.

In terms of implementation, the WAVELET transform is a type of subband coding and is implemented by filtering the signal with a tree-like filter bank.

It is no exaggeration to say that WAVELET has revolutionized the theory and practice of processing non-stationary signals.

Currently, WAVELET has found application in the following areas:

• digital signal processing — image compression, signal denoising, time-frequency analysis of signals, local property extraction, signal recognition and classification, medical applications;
• communication — signal combining and splitting, multiple access, hidden communication, multiplexers, joint source and channel coding, signal extraction from noise;
• statistics — trend extraction, local property extraction, time series prediction, interpolation, approximation, nonparametric estimation of random processes;
• mathematics, physics, astronomy …

The practice of using WAVELET has been especially developed for solving problems of compression and processing of images that are non-stationary in nature.

In this area, the use of WAVELET transformations has made it possible to simultaneously reduce the complexity and increase the efficiency of coders.

The following figures show the original image and the image restored after compression using the JPEG algorithm and the WAVELET algorithm.

It is easy to notice that with practically identical sizes of encoded files, the quality of the «WAVELET image» is significantly higher.

The requirement of uniformity imposed on the image quality leads to a gain in size of 1.5-2 times.

The figures show the characteristic concentrated selectivity of WAVELET during compression. Note the car number and the contours of the roses.

This phenomenon is explained by the features of WAVELET transformations, briefly indicated above.

Based on the Heisenberg uncertainty principle, which determines the impossibility of obtaining an arbitrarily precise frequency-time representation of a signal, we can only compromise, i.e., if we need precise time values, we have to sacrifice frequency information, and vice versa, if we need to know the frequency values, we will not be able to obtain precise values ​​of time counts.

Unlike the windowed Fourier transform, which up to a certain point was the only means of obtaining a somewhat truthful time-frequency representation of the signal, the WAVELET transform allows us to adjust the «dimensions» of the scanning window, thus allowing us to adjust to the signal, thereby solving the so-called resolution problem.

WAVELET transforms on the time-frequency plane can be represented as rectangles of different widths and heights, having the same area.

Each rectangle makes an equal contribution to the time-frequency plane, but with different shares of frequency and time.

In the case of the windowed Fourier transform, the window width is chosen once and for all for analyzing the entire signal. This is the main disadvantage of this type of transformation, which the WAVELET transformation is completely free of.

Based on the Internet search on the topic of Wavelet — transformation