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 gender, have acquired the habit of capturing every step they take and displaying the resulting images on public display on 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, a reduction in the weight of the digital image is required. For this purpose, methods based on various algorithms, including wavelet transform, are used. What is it, our article will tell.
What is a digital image?
Visual information on a computer is represented as numbers. In simple terms, a photo taken by a digital apparatus is a table whose cells contain the color values of each of its pixels. If we are talking about a monochrome image, then they are replaced by the brightness values from the interval [0, 1], where 0 is used to indicate black and 1 is white. The remaining shades are set by fractional numbers, but it is inconvenient to work with them, so the range is expanded and the values are selected from the interval between 0 and 255. Why exactly from this? Everything is simple! With this choice in binary representation, exactly 1 byte is required to encode the brightness of each pixel. Obviously, storing even a small image requires quite a bit of memory. For example, a 256 x 256 pixel photo takes 8 kB.
A few words about image compression techniques
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 the so-called lossy compression. It can significantly reduce the weight of the image, but inevitably affects its quality.
Lossy compression algorithms include:
- Jpeg. At the moment, this is one of the most popular algorithms. It is based on the use of discrete cosine transform. In fairness, 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 the use of discrete wavelet transform.
- Fractal compression algorithm. In some cases, it allows you to receive images of excellent quality even with strong compression. However, due to patent issues, this method continues to be exotic.
Without loss, compression is carried out through the following algorithms:
- RLE (used as the main method in TIFF, BMP, TGA formats).
- LZW (used in GIF format).
- LZ-Huffman (used for PNG format).
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, i.e., 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 appeal formula is written as follows:
What is a wavelet
Behind this name is a mathematical function that allows you to analyze various frequency components of the data under study. Its graph is a wave-like oscillations, the amplitude of which decreases to 0 far from the origin. In the general case, wavelet coefficients determined by the integral signal transformation are of interest.
Wavelet spectrograms differ from ordinary Fourier spectra, since they associate the spectrum of various signal features with their time component.
Wavelet transform
This method of converting a signal (function) allows you to translate it from time to 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 condition must be satisfied:
Moreover:
- a wavelet must have finite energy;
- It must be integrable, continuous and have a compact medium;
- the wavelet must be localized both in frequency and in time (in space).
Kinds
Continuous wavelet transform is used for the corresponding signals. Of much greater interest is its discrete counterpart. After all, it can be used to process information in computers. However, this raises the problem that formulas for a discrete fiberboard cannot be obtained by simply discretizing the corresponding formulas of a DNP.
The solution to this problem was found by I. Dobesi, who was able to choose a method that allows you to build a series of such orthogonal wavelets, of which each is determined by a finite number of coefficients. Later, fast algorithms were created, for example, the Mall algorithm. When using it for decomposition or for restoration, it is required to perform the order of cN operations, where N is the sample length and c is the number of coefficients.
Wavelet haara
In order to compress the image, you should find a certain regularity among its data, and even better if it is a long chain of zeros. This is where the wavelet transform algorithm comes in handy. However, we continue the consideration of the method in order.
First you need to remember that in photographs the brightness of neighboring pixels, as a rule, differs by a small amount. Even if real images contain areas with sharp, contrasting brightness differences, they occupy only a small part of the image. As an example, let's take the well-known Lenna test image in grayscale. If we take the brightness matrix of its pixels, then part of the first row 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. For this, only the first number is stored, and for the rest, they take only the differences of each number from the previous one with the “+” or “-” sign.
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 what brightnesses are encoded in it if all the values in front of it are not decoded.
To overcome this drawback, the numbers are divided into pairs and for each they find half-sum (vol. A) and half-difference (vol. D), i.e., 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 a pair.
In the general case, for a discrete wavelet transform of the signal S, we have:
Such a discrete method follows from the continuous case of the Haar wavelet transform and is widely used in various fields 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 from two pixels X and Y into a vector (X + Y) / 2 and (X - Y) / 2. To do this, just multiply the original vector by the matrix below.
If there are more points, then take a larger matrix, the diagonal of which is the matrix H. Thus, the original vector, regardless of its length, is processed in pairs.
Filters
The resulting “half sums” are the average brightness values in pairs of pixels. That is, the values when converting to an image should give a copy of it, reduced by 2 times. At the same time, half-sums average the brightnesses, that is, they “filter out” random bursts of their values and play the role of frequency filters.
Now let's figure out what the differences show. They “distinguish” inter-pixel “bursts”, eliminating the constant component, that is, they “filter out” values with low frequencies.
Even from the above Haar wavelet transform for Dummies, it becomes obvious that it is a pair of filters that separate the signal into two components: high-frequency and low-frequency. To obtain the original signal, it is enough to simply combine these components again.
Example
Suppose we want to compress a photo portrait (Lenna test image). Consider an example of a wavelet transform of its pixel brightness matrix. The high-frequency component of the image is responsible for displaying fine details and describes noise. As for the low-frequency, it carries information about the shape of the face and smooth differences in brightness.
The features of the human perception of photographs are such that the last component is more important. This means that during compression, a certain part of the high-frequency data can be discarded. Moreover, it has smaller values and is encoded more compactly.
To increase the compression ratio, you can apply the Haar transform 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 intensities of its pixels. Thus, we should be interested in the Haar two-dimensional wavelet transform. For its implementation, you just need to perform its one-dimensional transformation for each row and each column of the matrix of intensities of the image pixels.
Values close to zero can be discarded without significant damage to the decoded picture. 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 the described actions result in a matrix that contains a large number of 0. It should be written line-by-line into a text file and compressed by any archiver.
Decoding
Inverse conversion to image is performed according to the following algorithm:
- the archive is unpacked;
- the inverse Haar transform is applied;
- the decoded matrix is converted to an image.
Benefits over JPEG
When considering the Joint Photographic Experts Group algorithm, it was said that it is based on DCT. This conversion is carried out block by block (8 x 8 pixels). As a result, if the compression is strong, then the block structure becomes noticeable on the reconstructed image. There is no such problem with compression using wavelets. However, distortions of a different type may appear, which have the form of ripples near sharp boundaries. It is believed that such artifacts are on average less noticeable than the "squares" that are created using the JPEG algorithm.
Now you know what wavelets are, what they are and what practical application for them has been found in the field of processing and compression of digital images.