In our earlier article, we have described the basic details about data compression. Also, we have pointed out that lossless compression is when the compressed data can be used to extract exactly the original data. This is necessary, for example, when compressing executable program files. Examples are:
In the case of lossy compression or irrelevance reduction, the original data can usually no longer be recovered exactly from the compressed data, i.e. part of the information is lost; the algorithms try to omit only “unimportant” information as much as possible. Such methods are often used for image or video compression and audio data compression. Examples include:
- Images: JPEG
- Video: MPEG, AVC, HEVC
- Audio: MP3, AAC
Characteristic of Lossy Compression
Lossy compression, as described above, is always possible – the threshold of what counts as “redundant” can be raised until only 1 bit remains. The boundaries are fluid and are determined by the use case: for example, “The house is big” could be compressed to “The house is gr”; If the reader wants to know “what is the property of the house?”, it is no longer possible to distinguish whether it is “grey”, “green” or “large”. If the reader wants to know “was something said about a house?”, the answer can still be clearly yes.
---
With lossy image compression, details are increasingly lost/blurred, eventually “everything blurs” into a surface with uniform color; an audio recording usually becomes duller and more indistinct, it would only have a simple sine wave tone with most algorithms after the greatest possible compression.
Characteristic of Lossless Compression
Lossless compression has much tighter limits, as it must be ensured that the compressed file can be transformed back into the original file. The number 100000000 could be compressed as “10^8” or “1e8”, in which case the reader must be aware of the recovery method, namely the power notation. However, if a string does not have any recognizable structure/special features, then compression is not possible – the instructions would have to contain the unchanged original data.
Another reason for the uncompressibility of some data is the so-called dovecote principle: If there are fewer nesting places for pigeons than there are pigeons in the loft, two or more pigeons will inevitably have to share a nesting place. On an n-bit space you can store one of 2 possible pieces of information, and on a space that is one bit smaller, you can store only one of half as much possible information. This would mean, according to the dovecote principle, that each storage space would have to contain two different compressed files at the same time. However, since lossless compression requires a reversibly unambiguous assignment between compressed and uncompressed files, this is not possible.
If the dovecote principle did not apply, and if there were an algorithm that could compress any given file by at least one bit, it could be applied recursively to the respective compressed file – any information could be reduced to 0 bits. In practice, data that has already been compressed can only be compressed again if a not 100% efficient algorithm was used in the previous run, which has not yet completely removed the redundancy (e.g. a very large file full of zeros is compressed twice with gzip). These two facts lead to the conclusion that purely random data is (most likely) uncompressible (since it usually has no structure), and that many, but not all, of the data can be compressed.
Technology Behind Lossy Compression
Lossy compression removes irrelevant information, also known as irrelevance reduction. In the process, some of the information from the original data is lost, so that the original can no longer be reconstructed from the compressed data.
A model is needed that decides what proportion of the information is dispensable for the recipient. Lossy compression is mostly used in image, video and audio transmission. The model is based on human perception. A popular example is the MP3 audio format, which removes frequency patterns that humans hear poorly or not at all.
The theoretical basis is the rate distortion theory. It describes the minimum data transfer rate required to transmit information of a certain quality.
Sound, image and film are areas of application for lossy compression. Otherwise, the often enormous amounts of data would be very difficult to handle. Even the recording devices limit the data volume. The reduction of the stored data is based on the physiological perceptual properties of humans. Compression by algorithms typically uses the conversion of signal curves from sample signals into a frequency representation.
In the acoustic perception of humans, frequencies above approx. 20 kHz are no longer perceived and can already be trimmed in the recording system. Likewise, existing, quiet secondary tones in a sound mixture are difficult to perceive if very loud sounds occur at exactly the same time, so that the inaudible frequency components can be removed from the data compression system without this being perceived as disturbing by the listener. When digitized acoustic events (music, speech, sounds) are reduced to values of around 192 kbit/s (as is the case with many Internet downloads), humans can hardly or not at all detect any differences in quality compared to the uncompressed source material (as in the case of a CD).
In the optical perception of humans, colors are resolved less strongly than changes in brightness, from which the YUV-422 reduction is derived, which is already known in analogue color television. Edges, on the other hand, are more significant, and there is a biological contrast enhancement (Mach stripes). With moderate low-pass filtering for color reduction, such as the DCT transform-based JPEG algorithm or the newer wavelet-transform-based JPEG2000 algorithm, the amount of data can usually be reduced to 10% or less of the original amount of data, without significant quality reductions.
Moving images (films) consist of successive individual images. The first approach was to compress each image individually according to the JPeg algorithm. The resulting format is Motion JPEG (equivalent to MPEG-1 if it contains only I-frames). Today’s much higher compression rates are only achievable if the similarity of adjacent images (frames) is taken into account when encoding. To do this, the image is broken down into smaller boxes (typical sizes are between 4×4 and 16×16 pixels) and similar boxes are searched for in already transferred images and used as templates. The savings result from the fact that instead of the entire image content, only the differences of the intrinsically similar boxes have to be transferred. In addition, the changes from the previous to the current image indicate in which direction the image content has shifted and to what extent; only one displacement vector is stored for the corresponding area.
Technology Behind Lossless Compression
With lossless compression, the original data can be restored exactly from the compressed data. No information is lost. Essentially, lossless compression methods exploit the redundancy of data, also referred to as redundancy reduction.
The theoretical basis is information theory (related to algorithmic information theory). Due to the information content, it specifies a minimum number of bits that are needed to encode a symbol. Lossless compression methods now try to encode messages in such a way that they approximate their entropy as closely as possible.
Texts, as long as they consist of letters or are stored as strings, and thus not as images (raster graphics, typically an image file after scanning a book), take up comparatively little storage space. This can be reduced to 20% to 10% of the original space required by a lossless compression process.
Conclusion
Compression artifacts are signal interference caused by lossy compression. However, we need to use lossy compression for limitation of storage space, network speed etc with a balance with:
- storage/delivery requirements
- loading times (e.g. on the web)
- image/sound quality
Sensory perceptions are filtered, which is also a type of compression, or more precisely, lossy compression, since only currently relevant information is perceived. If necessary, what is missing is unconsciously replaced. For example, human eyes only see sharply in a small area (fovea centralis), outside of this narrow field of vision, missing information is unconsciously replaced by patterns. Similarly, the human eye can perceive differences in brightness much better than differences in hue – the YCbCr color model used in JPEG images takes advantage of this fact and stores the color value with much less precision.
