Wavelet transform: definition, application, example

The advent of inexpensive digital cameras has led to the fact that a significant part of the inhabitants of our planet, regardless of age and sex, acquired the habit of capturing every step and putting the images on public display in social networks. In addition, if before the family photo archive was placed in one album, today it consists of hundreds of pictures. In order to facilitate their storage and transmission over networks, the weight of the digital image needs to be reduced. To this end, methods based on various algorithms, including wavelet transform, are applied. What is this, our article will tell.

What is a digital image

The visual information in the computer is represented as numbers. In simple terms, a photo taken by a digital camera is a table in which the color values of each of its pixels are inscribed. If we are talking about a monochrome image, then they are replaced by the luminance values from the interval [0, 1], where 0 is used to denote black color, and 1 is white. The remaining shades are specified in fractional numbers, but with them it is inconvenient to work, so the range is expanded and the values are chosen from the interval between 0 and 255. Why from this? It's simple! With this choice in the binary representation, every 1 pixel is required to encode the brightness exactly 1 byte. Obviously, storing even a small image requires quite a lot of memory. For example, a photo size of 256 x 256 pixels will take 8 KB.

A few words about methods of image compression

Surely everyone saw pictures of poor quality, where there are distortions in the form of rectangles of the same color, which are usually called artifacts. They arise as a result of so-called lossy compression. It can significantly reduce the weight of the image, but it inevitably affects its quality.

The lossy compression algorithms include:

• JPEG. At the moment this is one of the most popular algorithms. It is based on the application of a discrete cosine transform. To be fair, it should be noted that there are JPEG options that perform lossless compression. These include Lossless JPEG and JPEG-LS.
• JPEG 2000. The algorithm is used on mobile platforms and is based on applying a discrete wavelet transform.
• Fractal Compression Algorithm. In some cases, it allows you to obtain images of excellent quality, even with strong compression. However, because of problems with patenting, this method continues to be exotic.

Without loss, compression is performed by means of algorithms:

• RLE (used as the main method in the formats TIFF, BMP, TGA).
• LZW (used in the GIF format).
• LZ-Huffman (used for PNG format).

The Fourier transform

Before proceeding to the consideration of wavelets, it makes sense to study the function associated with them that describes the coefficients in the decomposition of the initial information into elementary components, that is, harmonic oscillations with different frequencies. In other words, the Fourier transform is a unique tool connecting discrete and continuous worlds.

It looks like this:

The inversion formula is written as follows:

What is a wavelet

Behind this name lies a mathematical function that allows you to analyze the various frequency components of the data under study. Its graph represents wave-like oscillations whose amplitude decreases to 0 far from the origin. Interestingly, the wavelet coefficients, determined by the integral signal transformation, are of interest.

Wavelet spectrograms differ from ordinary Fourier spectra, because they connect the spectrum of various signal features with their time component.

Wavelet transform

This way of converting the signal (function) allows you to translate it from the time to the time-frequency representation.

In order for the wavelet transform to be possible, the following conditions must be satisfied for the corresponding wavelet function:

• If for some function ψ (t) the Fourier transform has the form

Then the following condition must be satisfied:

Besides:

• The wavelet must have finite energy;
• It must be integrable, continuous, and have a compact carrier;
• The wavelet must be localized both in frequency and in time (in space).

Kinds

A continuous wavelet transform is used for the corresponding signals. Much greater interest is represented by its discrete analogue. After all, it can be used to process information in computers. However, this raises the problem that the formulas for a discrete DVP can not be obtained by simply sampling the corresponding DNP formulas.

The solution of this problem was found by I. Dobesi, who was able to select a method that allows constructing a series of such orthogonal wavelets, each of which is determined by a finite number of coefficients. Later, fast algorithms were created, for example Mall's algorithm. When used for decomposition or for recovery, it is required to perform the order of cN operations, where N is the length of the sample, and c is the number of coefficients.

Vaivlet Haara

In order to compress the image, it is necessary to find a certain pattern among its data, or even better, if it is a long chain of zeros. This is where the wavelet transform algorithm can come in handy. However, we continue the consideration of the method in order.

First you need to remember that the photos of the brightness of neighboring pixels, as a rule, differ by a small amount. Even if there are areas with sharp, contrasting brightness differences on real images, they occupy only a small part of the image. As an example, let's take Lenna's well-known test image in grayscale. If we take the matrix of brightness of its pixels, then the part of the first line will look like a sequence of numbers 154, 155, 156, 157, 157, 157, 158, 156.

To obtain zeros, the so-called delta method can be applied to it. To do this, only the first number is retained, but for the others only the differences of each number from the previous one with the sign "+" or "-" are taken.

The result is the sequence: 154,1,1,1,0,0,1, -2.

The disadvantage of delta coding is its non-locality. In other words, it is impossible to take only a piece of the sequence and find out which luminances are encoded in it, if all the values before it are not decoded.

In order to overcome this deficiency, the numbers are divided into pairs and for each one we find half the sum (a) and half the difference (volume d), that is, for (154.155), (156.157), (157.157), (158.156) we have (154.5, 0.5), (156.5.0.5), (157.0.0), (157, -1.0). In this case, at any time, you can find the value of both numbers in the pair.

In the general case, for the discrete wavelet transform of the signal S, we have:

This discrete method follows from the continuous case of the Haar wavelet transform and is widely used in various areas of information processing and compression.

Compression

As already mentioned, one of the applications of the wavelet transform is the JPEG 2000 algorithm. Compression using the Haar method is based on the translation of a vector of two pixels X and Y into a vector (X + Y) / 2 and (X - Y) / 2. To do this, it suffices to multiply the original vector by the matrix presented below.

If there are more points, then take a larger matrix with diagonal matrixes H. Thus, the original vector, regardless of its length, is processed in pairs.

Filters

The resulting "half-sums" are the average brightness values in the pixel pairs. That is, the values when converting to an image should give a copy thereof, reduced by a factor of 2. In this case, the half-sums average the brightness, ie, "filter out" random bursts of their values and play the role of frequency filters.

Now let's look at the differences. They "allocate" inter-pixel "bursts", eliminating the constant component, that is, "filtering" values with low frequencies.

Even from the above Haar wavelet transform for "dummies" it becomes obvious that it is a pair of filters that divide the signal into two components: high-frequency and low-frequency. To obtain the original signal, it is sufficient simply to re-combine these components.

Example

Let us want to compress the photo portrait (the Lenna test image). Consider an example of the wavelet transform of its pixel brightness matrix. The high-frequency component of the image is responsible for displaying small details and describes noise. As for the low-frequency, it carries information about the shape of the face and the smooth changes in brightness.

Features of human perception of photographs are such that the last component is more important. This means that during compression, a certain portion of the high-frequency data can be discarded. Moreover, it has smaller values and is coded more compactly.

To increase the compression ratio, you can apply the Haar transformation several times to low-frequency data.

Application to two-dimensional arrays

As already mentioned, a digital image in a computer is represented as a matrix of the values of the intensities of its pixels. Thus, we should be interested in the Haar two-dimensional wavelet transform. To implement it, you simply need to perform a one-dimensional conversion for each row and each column of the pixel intensity matrix of the image.

Values close to zero can be discarded without significant damage to the decoded pattern. Such a process is known as quantization. And it is at this stage that some of the information is lost. By the way, the number of nullable coefficients can be changed, thereby adjusting the compression ratio.

All described actions result in a matrix that contains a large number of 0. It should be written line by line to a text file and compressed by any archiver.

Decoding

The reverse transformation to the image is made according to the following algorithm:

• The archive is unpacked;
• The inverse Haar transformation is applied;
• The decoded matrix is converted into an image.

Advantages over JPEG

было сказано, что он основан на ДКП. When considering the algorithm of the Joint Photographic Experts Group , it was said that it is based on the DCT. This transformation is done block by block (8 x 8 pixels). As a result, if the compression is strong, then the block structure becomes noticeable on the restored image. When compressing using wavelets, this problem is absent. However, other types of distortions may appear, which look like ripples near sharp edges. It is believed that such artifacts are on average less noticeable than the "squares" that are created when applying the JPEG algorithm.

Now you know what wavelets are, what they are, and what practical application for them has been found in the processing and compression of digital images.