The JPEG algorithm is a lossy data compression algorithm

The good old JPEG, despite a lot of undeniable advantages, still has significant limitations. Was called upon to remove them new method image compression, which has been in development for a long time. Now that JPEG2000 has become an officially recognized format, this should serve as the beginning of its active support by various software manufacturers.

Surely many who work with graphics on a computer are interested in the question: how can an image that occupies a very impressive amount of space in the PC memory be squeezed into a much smaller size on the disk? I remember that at the dawn of my publishing career, the word “compression” was so mysterious and surprising for me... In fact, how does image compression occur - after all, without it it is now unthinkable to imagine either the Web, or digital photography, or color printing?

So, compression. It may or may not lead to a loss of quality. The last case is methods such as RLE (Run Length Encoding, encoding run lengths, which results in pairs like ( skip, value, Where skip is the number of consecutive zeros, and value- the value following them) and LZW (compression using the Lempel-Ziff-Welch method), implemented in PSD formats, GIF and TIFF. They are also widely used by archivers such as RAR and ZIP. The average degree of lossless compression is 2-3 times.

If you need to compress an image more, you cannot do without losing quality. What are the principles? Firstly, any image contains a certain redundancy, the removal of which will not lead to a noticeable change in the quality of the image. Secondly, the human eye is more sensitive to changes in brightness than color. Therefore, different degrees of compression are applied to different image channels - information is lost, but this is not visually noticeable. In addition, the eye's sensitivity to small image elements is low, which makes it possible to remove them without compromising quality. This way you can compress the image (even if the deterioration in quality is already noticeable) up to an acceptable threshold. The degree of quality degradation is determined for each specific case. For printing, only minimal distortions are allowed, but for posting on the Internet (depending on the purpose) - much more.

The most popular among lossy compression methods is JPEG, which, even with thirtyfold compression, retains sufficient image quality. By the way, most modern data compression methods (for example, Layer-4, known as mp3, as well as MPEG) implement mechanisms similar to JPEG. Let's take a closer look at this format, especially since not so long ago its newest implementation, JPEG2000, was finally approved, which included all the additions made to JPEG/MPEG over ten years of its development.

JPEG

The name of the compression algorithm is an abbreviation for the Joint Photographic Expert Group, an initiative group formed from experts from the ITU (International Telecommunication Union) and ISO (International Organization for Standardization). That is why its name contains the prefix Joint. In 1992, JPEG was declared the international standard for graphics.

When compressing using the JPEG method, quality is always lost. In this case, there is always a choice: to give preference to quality at the expense of volume (the file size will be compressed by approximately three times) or, on the contrary, to achieve a minimum image size at which it will still remain recognizable (the degree of compression can reach 100). Compression, in which the difference in quality between the resulting image and the original is still unnoticeable, results in a 10-20 times reduction in file size.

Scope of application

JPEG is the best compressor for photographic-quality full-color and monochrome images. If you want to save an image with an index palette, it is first converted to full color. When compressing using the JPEG method, you need to keep in mind that everything depends on the nature of the images: much less volume will be occupied by those where the color changes are insignificant and there are no sharp color transitions. JPEG is used wherever photographic images need to be stored: in digital cameras, printing (EPS DCS 2.0), and the Internet is unthinkable without it.

There are several types of JPEG compression, but we will consider only two of them, used in the standard package for working with raster images Adobe Photoshop, — baseline And progressive. The other two methods - ariphmetic and loseless - are exotic, and for a number of reasons have not become widespread.

How does compression occur?

1. The first stage is color model conversion images (usually RGB) into a model where the brightness and color components are separated (for example, YCbCr or YUV), which allows for an optimal approach to the choice of compression levels for each channel (taking into account the characteristics of eye perception). The conversion occurs as follows:

Y = 0.299xR+0.587*G+0.114xB Cb = (B-Y)/0.866/2+128 Cr = (R-Y)/0.701/2+128

2. At the next stage, the so-called prefiltration, in which neighboring pixels separately in each of the channels Cb and Cr are grouped in pairs in the horizontal and vertical directions, and the brightness channel Y is left unchanged. After this, the entire group of four pixels receives the average value of the corresponding Cb and Cr components. For brevity, such a scheme can be designated as 4:1:1 (the same form of representation is adopted in DRAW - the jpeg export window). Taking into account the fact that each pixel is encoded by 3 bytes (256 levels for each of the three channels), as a result, the amount of data is automatically reduced by 2 times (instead of 12 bytes to transfer 4 pixels, it is enough to transfer only 4+1+1 = 6 bytes) . From a mathematical point of view, such a transformation leads to a significant loss of information, but the human eye does not perceive the loss, since there is significant redundancy in ordinary photographic images.

3. The received information, which has passed the stage of primary “cleaning”, is separately grouped in each channel again into blocks, but already 8x8 in size, after which basic compression is applied to them - the so-called. discrete cosine transform, for short - DCT (discrete cosine transform). As a result, information about distribution pixel brightness is converted to another form, where it is described by a distribution based on frequency of occurrence one or another pixel brightness. DCT has a number of advantages over other transforms (for example, the Fourier transform), providing better recovery information.

Instead of an array of 64 values ​​(8x8 pixels) for each block that makes up the image, we get an array of 64 frequencies. Let's look at how DCT works using an example. Let's say the brightness of the pixels in one block of our image has the form shown in Fig. 1 on the left, then the result of the transformation will be as shown on the right.

Despite significant accuracy, some loss of information does occur at this stage - this is why JPEG always leads to loss of quality. The main purpose of the transformation is to find out big picture distribution of large (top left in the figure) and small (bottom right) objects, which will be useful later when eliminating unimportant information.

4. The next stage is removing information that is barely noticeable to the eye from the block, or quantization(quantization). All components are divided into various coefficients that determine the significance of each of them for high-quality restoration of the original image, and the result rounded up up to an integer value. It is this procedure that introduces the greatest loss of quality, reducing the final volume of the image. High-frequency components are quantized roughly, while low-frequency components are quantized more precisely, since they are most noticeable. In order to somewhat smooth out the decrease in quality, the luminance channel uses smaller division factors than the chrominance channels. But more often (this is done to speed up calculations), instead of specially selected values, only one is taken - the one entered by the user when choosing the degree of compression.

Here, for example, is what the Photoshop window looks like when saving an image using the Save for web operation, where the Quality parameter (or rather, a derivative of it) is the same rounding factor(Fig. 2).

As a result of quantization, a set of components is obtained, from which the original image is reconstructed with a given accuracy (Fig. 3).

4

In Fig. Figure 4 shows the result of reconstructing a black and white square using one, four and fifteen components, respectively.

5. After the main work of image compression has been completed, further transformations are reduced to secondary tasks: the remaining components are collected in sequence in such a way that those responsible for large parts are located first, and then for all the smaller ones. If you look at the picture, the movement of the encoder looks like a zigzag line. This stage is called ZigZag (Fig. 5).

5

Then the resulting sequence is compressed: first with the usual RLE, then with the Huffman method.

6. And finally, clean technical stage— the data is enclosed in a shell and provided with a header, which indicates all the compression parameters so that the image can be restored. However, sometimes this information is not included in the headers, which gives additional benefits in compression, but in this case you need to be sure that the application that will read the file knows about them.

That, in general, is all the transformation. Now let's calculate what compression was achieved in our example. We received 7 values ​​from which the original 8x8 image will be restored. So, the compression from the use of DCT conversion in both color channels was 8x8/7 9 times. Let's allocate not seven, but 11 coefficients to the brightness channel, which will give 8x8/11 6. For all three channels it will be (9+9+6)/3=8 times. The reduction in quality during the “thinning” of the image, which occurred at the second stage, gives an additional double increase (the 4-1-1 scheme, taking into account the peculiarities of encoding the brightness component), which will give a final result of 16 times. This is a rough calculation that does not take into account some aspects, but reflects the real picture. To get a thirty-fold reduction in file size, you need to leave only 3-4 components.

The image restoration process proceeds in reverse order: first, the components are multiplied by the values ​​​​from the quantization table, and approximate coefficients for the inverse cosine transform are obtained. The better the quality selected during compression, the higher the degree of approximation to the original coefficients, which means the image will be restored more accurately. There is only one action left to add: just before completion, make some adjustments (noise) to the boundary pixels from neighboring blocks in order to remove sharp differences between them.

Disadvantages of JPEG

1. Inability to achieve high compression ratios due to block size restrictions (8x8 only).
2. Blocky structure at high levels of compression.
3. Rounding sharp corners and blurring of subtle elements in an image.
4. Only RGB images are supported (JPEG for CMYK images can only be used in EPS format via DCS).
5. The image cannot be displayed until it has completely loaded.

It's been ten years since JPEG was approved as a standard. During this time, groups of researchers proposed a number of significant additions to the original version, which resulted in the emergence of a new standard at the end of last year.

JPEG2000

Since 1997, work began aimed at creating a universal encoding system that would remove all the limitations imposed by JPEG and could effectively work with all types of images: black and white, grayscale, full color and multi-component, regardless of content ( whether these will be photographs, fairly small text, or even drawings). Along with international standardizing organizations, such industry giants as Agfa, Canon, Fujifilm, Hewlett-Packard, Kodak, LuraTech, Motorola, Ricoh, Sony and others took part in its development.

Since the new algorithm claimed to be universal, it was additionally tasked with using various methods of data transmission (in real time and with a narrow bandwidth), which is especially critical in multimedia applications, for example, in real-time broadcasts over the Internet.

Basic requirements for the JPEG2000 format:

1. Achieving a higher degree of compression compared to JPEG.
2. Supports monochrome images, which will allow you to use it to compress images with text.
3. Possibility of compression without loss at all.
4. Outputs images with gradual improvement in detail (as in progressive GIF).
5. The use of priority areas in the image, for which the quality can be set higher than the rest of the image.
6. Decoding in real time (no delays).

Compression principle

The main compression mechanism in JPEG2000, unlike JPEG, uses wavelet transformation - a system of filters applied to the entire image. Without going into details of compression, we will only note the main points.

6

For example, the image obtained after low-pass filtering by rows and rows (top left) carries the greatest amount of information, and the image obtained after high-pass filtering contains the least. The information content of images obtained after low-pass filtering of rows and high-pass filtering of columns (and vice versa) is average. The most informative image is again filtered, and the resulting components, as with jpeg compression, are quantized. This happens several times: for lossless compression the cycle is usually repeated 3 times, with losses - 10 iterations are considered a reasonable compromise between size, quality and decompression speed. The result is one small image and a set of pictures with small details, which sequentially and with a certain accuracy restore it to normal size. Obviously, the highest degree of compression is obtained on large images, since a larger number of cycles can be set.

Practical implementation

Since the foundations of JPEG2000 compression were laid, a number of companies have developed fairly effective algorithms for its implementation.

Among the major software developers, Corel can be noted (by the way, it was one of the first to introduce into its packages support for the wi format, based on wave transformations, for which it is honored and praised) - all images are supplied on CDs with the CorelDRAW package up to the ninth version , were compressed in exactly this way.

Later, Adobe joined in. Some of the ideas contained in JPEG2000 were applied by the developers of Photoshop 6 in the form of advanced options when saving an image in the JPEG format (regular, based on the cosine transform). Among them is progressive JPEG (the Progressive parameter in the Save window for Web). This algorithm is intended primarily for real-time systems and works exactly the same as progressive GIF. First, a rough copy of the image appears, consisting of only a few blocks large size, and over time, when the remaining data is loaded, the structure begins to be viewed more and more clearly, until, finally, the final image is completely restored. Unlike GIF, this algorithm places a greater burden on the viewer, since it will have to complete the entire transformation cycle for each version transmitted.

Other additions include the inclusion of several JPEGs in the file. compressed images with different degrees of compression, resolution and even color models. Accordingly, in Photoshop 6 it became possible to select individual areas in an image and apply different compression settings to them ( Region-Of-Interest, such a mechanism was first proposed back in 1995), using lower values ​​in the quantization table. To do this, set the required area (for example, in the form of a new channel in the image) and click the mask icon next to the Quality item. In the window that appears, you can experiment with the image by moving the sliders - the finished result is displayed on the screen, allowing you to quickly find the necessary compromise between quality and size.

Specialized converters and viewers

Since the standard does not stipulate specific implementations of compression/decompression methods, this gives scope to third-party developers of compression algorithms. In fact, you can use either a simplified wave conversion algorithm and thereby speed up the compression process, or, conversely, use a more complex one and, accordingly, requiring large system resources.

Customized solutions from other companies are available as commercial designs. Some are implemented as separate programs (JPEG 2000 developed by Aware), others - as additional modules for the most common raster editors (ImagePress JPEG2000 developed by Pegasus Imaging and the LEAD JPEG2000 module from LEAD Technologies). The company LuraTech, which has been working on this issue for a long time, stands out against their background. It promotes its LuraWave technology in the self-contained product LuraWave SmartCompress (the third version is already available) and offers modules for Photoshop, Paintshop, Photopaint. Distinctive feature- more high speed work (almost instant conversion) even with images several megabytes in size. Accordingly, the price of this module is the highest - $79.

To view JPEG2000 images in browsers, you need to install a special viewer module (all developers offer it for free). Inserting an image into an HTML document, like any plug-in, comes down to using the EMBED construct (with additional parameters). For example, means that a progressive image transmission method will be used. That is, in our example (a file of 139 KB in size), first only 250 bytes are transferred, on the basis of which a rough image will be built, then, after loading 500 bytes, the image is updated (this continues until the LIMIT value is reached).

If you want to get a better image, you need to select the Improve item from the menu that pops up using the right button (Fig. 9). In four downloads, the entire image will be downloaded completely.

9

Conclusions

So, JPEG2000 objectively shows better results than JPEG only at high compression levels. With compression of 10-20 times, there is not much difference. Will it be able to displace or simply compete with the widespread format? In the near future - it’s unlikely; in most cases, the quality/size ratio provided by JPEG is quite acceptable. And those 10-20% additional compression that JPEG2000 provides with visually the same quality are unlikely to lead to an increase in its popularity.

But digital camera manufacturing companies are showing keen interest in the new format, since the size of light-sensitive matrices is steadily increasing every year, and it is becoming increasingly difficult to store images in memory. And then the new format will become more widespread, and who knows, perhaps after some time JPEG2000 will become equal to JPEG. In any case, Analog Micro Devices recently released a specialized chip in which compression/decompression using the new technology is implemented at the hardware level, and the US Department of Defense is already actively using the new format for recording photographs obtained from spy satellites.

Facts and speculation

1. JPEG loses quality when opening and resaving the file.

Not true. Quality is only lost when a compression level less than the one with which the image was saved is selected.

2. JPEG loses quality when editing the file.

Is it true. When you save the modified file, all transformations are performed again - so avoid frequent image editing. This only applies when the file is closed; if the file remains open, there is no cause for concern.

3. The result of compression with the same parameters in different programs will be the same.

Not true. Different programs interpret user input differently. For example, in one program the quality of the saved image is indicated (as, for example, in Photoshop), in another - the degree of its compression (the inverse value).

4. When setting the maximum quality, the image is saved without any loss of quality.

Not true. JPEG always compresses with losses. But setting, for example, 90% quality instead of 100% results in a reduction in file size greater than the deterioration in quality perceived by the eye.

5. Any JPEG file can be opened in any editor that understands the JPEG format.

Not true. This type of JPEG, called progressive JPEG, is not understood by some editors.

6. JPEG does not support transparency.

Is it true. Sometimes it may seem that some part of the image is transparent, but in fact its color is simply chosen to match the background color in the html page.

7. JPEG compresses better than GIF.

Not true. They have different areas of application. In general, a typical “GIF” image after conversion to JPEG will have a larger volume.

JPEG2000 vs JPEG

2. With higher compression, the quality of JPEG2000 is significantly higher than that of JPEG, which allows you to compress up to 50 times without any losses, and with some losses (we are talking about images for the Internet) - up to 100 and even up to 200.

3. At high levels of compression in those areas where a smooth color change occurs, the image does not acquire the block structure characteristic of a simple JPEG. JPEG2000 also somewhat smears and rounds out sharp edges - see photographs (Fig. 7 and 8).

It shows the results of compression of a test file with different degrees of compression (on the left - saved in Photoshop in JPG format, on the right - in JPEG2000 format). For the image in Fig. 7 compression levels were selected: 20, 40, 70 and 145 (they can be explicitly specified when saving in JPEG2000), the degree JPG compression was chosen so that the file size was the same as after JPEG2000 compression. As they say, the results are obvious. For clarity, a second experiment was carried out on an image with sharper details (with compression levels of 10, 20, 40 and 80). The advantage is again on the side of JPEG2000 (Fig. 8).

8

4. Since, in fact, copies with different resolutions are stored in one JPEG2000 file

I mean, for those who make image galleries on the Internet, there is no need to create thumbnails for them.

5. Of particular interest is compression without distortion (loseless mode). Thus, the test file with LZW compression from Photoshop took 827 KB, and the compressed JPEG2000 took 473 KB.

6. Compared to JPEG, its more advanced namesake consumes significantly more system resources. But the power of computers, which has increased significantly over the past couple of years, makes it possible to successfully solve image compression problems using a new method.

7. Lack of JPEG2000 support in browsers. To view such images, you need to download a fairly large additional module(1.2 MB).

8. Lack of free software for saving images in the new format.

Magazines are freely available.

On the same topic:

Scope of application

The JPEG algorithm is most suitable for compressing photographs and paintings containing realistic scenes with smooth transitions of brightness and color. JPEG is most widespread in digital photography and for storing and transmitting images using the Internet.

On the other hand, JPEG is unsuitable for compressing drawings, text and character graphics, where the sharp contrast between adjacent pixels leads to noticeable artifacts. It is advisable to save such images in lossless formats such as TIFF, GIF or PNG.

JPEG (like other distortion compression methods) is not suitable for compressing images during multi-stage processing, since distortions will be introduced into the images each time intermediate processing results are saved.

JPEG should not be used in cases where even minimal losses are unacceptable, for example, when compressing astronomical or medical images. In such cases, the Lossless JPEG compression mode provided by the JPEG standard (which, however, is not supported by most popular codecs) or the JPEG-LS compression standard may be recommended.

Compression

Compression converts the image from the RGB color space to YCbCr (YUV). It should be noted that the JPEG standard (ISO/IEC 10918-1) does not in any way regulate the choice of YCbCr, allowing other types of conversion (for example, with a number of components other than three), and compression without conversion (directly to RGB), however, the specification JFIF (JPEG File Interchange Format, proposed in 1991 by specialists from C-Cube Microsystems, and which has now become a de facto standard) involves the use of the RGB->YCbCr conversion.

After the RGB->YCbCr conversion for the image channels Cb and Cr, which are responsible for color, “subsampling” can be performed, which consists in the fact that each block of 4 pixels (2x2) of the brightness channel Y is assigned the average values ​​of Cb and Cr (thinning scheme “4:2:0”). Moreover, for each 2x2 block, instead of 12 values ​​(4 Y, 4 Cb and 4 Cr), only 6 are used (4 Y and one averaged Cb and Cr each). If increased demands are placed on the quality of the image restored after compression, thinning can be performed only in one direction - vertically (“4:4:0” scheme) or horizontally (“4:2:2”), or not performed at all (“4:4:4”).

The standard also allows decimation with averaging of Cb and Cr not for a 2x2 block, but for four pixels located sequentially (vertically or horizontally), that is, for blocks 1x4, 4x1 (“4:1:1” scheme), as well as 2x4 and 4x2 (scheme “4:1:0”). It is also possible to use various types thinning for Cb and Cr, but in practice such schemes are used extremely rarely.

Next, the brightness component Y and the color components Cb and Cr are divided into blocks of 8x8 pixels. Each such block is subjected to a discrete cosine transform (DCT). The resulting DCT coefficients are quantized (different quantization matrices are generally used for Y, Cb and Cr) and packed using run and Huffman coding. The JPEG standard also allows for the use of much more efficient arithmetic encoding, however, due to patent restrictions (the patent for the arithmetic QM encoder described in the JPEG standard belongs to IBM), it is rarely used in practice. To the popular libjpeg library latest versions Support for arithmetic encoding is included, but viewing images compressed using this method may be problematic because many viewers do not support decoding them.

The matrices used to quantize the DCT coefficients are stored in the header part of the JPEG file. They are usually constructed so that high-frequency coefficients are subject to stronger quantization than low-frequency ones. This results in coarsening of small details in the image. The higher the compression ratio, the more strongly all coefficients are quantized.

When saving an image as a JPEG file, a quality parameter is specified in some arbitrary unit, for example, from 1 to 100 or from 1 to 10. A higher number usually corresponds to better quality (and larger size compressed file). However, even when using highest quality(corresponding to a quantization matrix consisting of only ones), the reconstructed image will not exactly coincide with the original one, which is associated both with the finite accuracy of DCT implementation and with the need to round the values ​​of Y, Cb, Cr and DCT coefficients to the nearest integer. The Lossless JPEG compression mode, which does not use DCT, provides an exact match between the restored and the original images, but its low efficiency (the compression ratio rarely exceeds 2) and the lack of support from software developers have not contributed to the popularity of Lossless JPEG.

Varieties of JPEG compression schemes

The JPEG standard provides two main ways to represent encoded data.

The most common, supported by most available codecs, is the sequential JPEG data representation, which involves sequential traversal of the encoded image block by block from left to right, from top to bottom. The operations described above are performed on each encoded image block, and the encoding results are placed in the output stream in the form of a single “scan,” that is, an array of encoded data corresponding to the sequentially passed (“scanned”) image. The main or "baseline" encoding mode allows only this representation. Extended mode, along with sequential mode, also allows progressive JPEG data presentation.

In the case of progressive JPEG, the compressed data is written to the output stream as a set of scans, each of which describes the entire image with an increasing degree of detail. This is achieved either by recording in each scan not the full set of DCT coefficients, but only some part of them: first - low-frequency ones, in subsequent scans - high-frequency ones (the “spectral selection” method, that is, spectral samples), or by sequential, from scan to scan, refinement of DCT coefficients (method of “successive approximation”, that is, successive approximations). This progressive representation of data is especially useful when transmitting compressed images using low-speed communication channels, since it allows you to get an overview of the entire image after only a small part of the JPEG file has been transmitted.

Both described schemes (both sequential and progressive JPEG) are based on DCT and fundamentally do not allow obtaining a reconstructed image absolutely identical to the original one. However, the standard also allows compression that does not use DCT, but is built on the basis of a linear predictor (lossless, that is, “lossless”, JPEG), guaranteeing a complete, bit-for-bit, match of the original and restored images. At the same time, the compression ratio for photographic images rarely reaches 2, but the guaranteed absence of distortion in some cases is in demand. Noticeably large degrees compression can be obtained using the JPEG-LS compression method, which, despite the similarity in names, is not directly related to the JPEG ISO/IEC 10918-1 (ITU T.81 Recommendation) standard, described by the ISO/IEC 14495-1 (ITU T .87 Recommendation).

Syntax and structure

The JPEG file contains the sequence markers, each of which begins with byte 0xFF, indicating the beginning of the marker, and an identifier byte. Some markers consist of just this pair of bytes, while others contain additional data consisting of a two-byte field with the length of the information part of the marker (including the length of this field, but minus the two bytes of the beginning of the marker, that is, 0xFF and the identifier) ​​and the data itself. This file structure allows you to quickly find a marker with the necessary data (for example, line length, number of lines and number of color components of the compressed image).

Advantages and disadvantages

The disadvantages of compression according to the JPEG standard include the appearance of characteristic artifacts in restored images at high compression rates: the image is scattered into blocks of 8x8 pixels (this effect is especially noticeable in image areas with smooth changes in brightness), in areas with high spatial frequency (for example, contrast contours and image boundaries), artifacts appear in the form of noise halos. It should be noted that the JPEG standard (ISO/IEC 10918-1, Annex K, clause K.8) provides for the use of special filters to suppress blocking artifacts, but in practice such filters, despite their high efficiency, are practically not used. However, despite its shortcomings, JPEG has become very widespread due to its fairly high (relative to alternatives that existed at the time of its appearance) compression ratio, support for compression of full-color images, and relatively low computational complexity.

JPEG compression performance

To speed up the compression process according to the JPEG standard, parallelization of calculations is traditionally used, in particular when calculating DCT. Historically, one of the first attempts to speed up the compression process using this approach is described in a paper published in 1993 by Kasperovich and Babkin, which proposed an original DCT approximation that makes it possible to efficiently parallelize calculations using 32-bit registers general purpose Intel 80386 processors. More efficient computing circuits that appeared later used SIMD extensions of the instruction set of x86 processors. Significantly best results make it possible to achieve schemes that use the computing capabilities of graphics accelerators (NVIDIA CUDA and AMD FireStream technologies) to organize parallel computing not only DCT, but also other stages of JPEG compression (color space conversion, run-level, statistical coding, etc.), and for each 8x8 block of encoded or decoded image. The article was for the first time [ source?] presents an implementation of parallelization of all stages of the JPEG algorithm using CUDA technology, which significantly accelerated the performance of compression and decoding using the JPEG standard.

In 2010, scientists from the PLANETS project placed instructions for reading the JPEG format in a special capsule, which was placed in a special bunker in the Swiss Alps. This was done with the aim of preserving for posterity information about digital formats popular at the beginning of the 21st century.

See also

Notes

Links

• JFIF Specification 1.02 (text file)
• JPEG optimization. Part 1, Part 2, Part 3.

(pronounced "japeg" Joint Photographic Experts Group, after the name of the development organization) is one of the popular graphic formats used for storing photographs and similar images. Files containing JPEG data typically have the extensions .jpeg, .jfif, .jpg, .JPG, or .JPE. However, of these, .jpg is the most popular extension on all platforms.

1. Joint Group of Experts in the Field of Photography;

2. An image compression method developed by this group and the corresponding graphic format, often used on the WWW. It is characterized by compactness of files and, accordingly, fast transfer, as well as “loss” of image quality. It is used primarily for photographs, since for them the loss of quality is less critical. Stores color parameters in the RGB color model.

JPEG(pronounced " jpeg", English Joint Photographic Experts Group, by the name of the developer organization) is one of the popular graphic formats used for storing photographs and similar images. Files containing JPEG data usually have the extension .jpeg, .jfif, .jpg, .JPG, or .JPE. However, of these .jpg the most popular extension on all platforms. The MIME type is image/jpeg.

The JPEG algorithm is a lossy data compression algorithm.

Scope of application

The JPEG algorithm is most suitable for compressing photographs and paintings containing realistic scenes with smooth transitions of brightness and color. JPEG is most widely used in digital photography and for storing and transmitting images using the Internet.

On the other hand, JPEG is unsuitable for compressing drawings, text and character graphics, where the sharp contrast between adjacent pixels leads to noticeable artifacts. It is advisable to save such images in lossless formats such as TIFF, GIF, PNG or RAW.

JPEG (like other distortion compression methods) is not suitable for compressing images during multi-stage processing, since distortions will be introduced into the images each time intermediate processing results are saved.

JPEG should not be used in cases where even minimal losses are unacceptable, for example, when compressing astronomical or medical images. In such cases, the Lossless JPEG compression mode provided by the JPEG standard (which, unfortunately, is not supported by most popular codecs) or the JPEG-LS compression standard may be recommended.

Compression

Compression converts the image from the RGB color space to YCbCr (YUV). It should be noted that the JPEG standard (ISO/IEC 10918-1) does not in any way regulate the choice of YCbCr, allowing other types of conversion (for example, with a number of components other than three), and compression without conversion (directly to RGB), but the specification JFIF (JPEG File Interchange Format, proposed in 1991 by specialists from C-Cube Microsystems, and which has now become a de facto standard) involves the use of the RGB->YCbCr conversion.

After the RGB->YCbCr conversion, “subsampling” can be performed for the image channels Cb and Cr, which are responsible for color, which consists of assigning average values ​​of Cb and Cr (thinning scheme “4:2:0”). Moreover, for each 2x2 block, instead of 12 values ​​(4 Y, 4 Cb and 4 Cr), only 6 are used (4 Y and one averaged Cb and Cr each). If increased demands are placed on the quality of the image restored after compression, thinning can be performed only in one direction - vertically (“4:4:0” scheme) or horizontally (“4:2:2”), or not performed at all (“4:4:4”).

The standard also allows decimation with averaging of Cb and Cr not for a 2x2 block, but for four pixels located sequentially (vertically or horizontally), that is, for blocks 1x4, 4x1 (“4:1:1” scheme), as well as 2x4 and 4x2. It is also possible to use different types of thinning for Cb and Cr, but in practice such schemes are used extremely rarely.

Next, the brightness component Y and the color components Cb and Cr are divided into blocks of 8x8 pixels. Each such block is subjected to a discrete cosine transform (DCT). The resulting DCT coefficients are quantized (in general, different quantization matrices are used for Y, Cb and Cr) and packed using Huffman codes. The JPEG standard also allows for the use of much more efficient arithmetic encoding, however, due to patent restrictions (the patent for the arithmetic QM encoder described in the JPEG standard belongs to IBM), it is not used in practice.

The matrices used to quantize the DCT coefficients are stored in the header part of the JPEG file. They are usually constructed so that high-frequency coefficients are subject to stronger quantization than low-frequency ones. This results in coarsening of small details in the image. The higher the compression ratio, the more strongly all coefficients are quantized.

When you save an image as a JPEG file, you specify a quality setting that is specified in some arbitrary unit, such as 1 to 100 or 1 to 10. A higher number usually means better quality (and a larger compressed file size). However, even when using the highest quality (corresponding to a quantization matrix consisting of only ones), the reconstructed image will not exactly match the original one, which is associated both with the final accuracy of the DCT and with the need to round off the values ​​of Y, Cb, Cr and coefficients DCT to the nearest integer. The Lossless JPEG compression mode, which does not use DCT, provides an exact match between the restored and the original images, however, its low efficiency (the compression ratio rarely exceeds 2) and the lack of support from software developers have not contributed to the popularity of Lossless JPEG.

Varieties of JPEG compression schemes

The JPEG standard provides two main ways to represent encoded data.

The most common, supported by most available codecs, is the sequential JPEG data representation, which involves sequential traversal of the encoded image block by block from left to right, from top to bottom. The operations described above are performed on each encoded image block, and the encoding results are placed in the output stream in the form of a single “scan”, i.e. an array of encoded data corresponding to a sequentially passed (“scanned”) image. The main or "baseline" encoding mode allows only this representation. Extended mode, along with sequential mode, also allows progressive JPEG data representation.

In the case of progressive JPEG, the compressed data is written to the output stream as a set of scans, each of which describes the entire image with an increasing degree of detail. This is achieved either by recording in each scan not the full set of DCT coefficients, but only some part of them: first - low-frequency ones, in subsequent scans - high-frequency ones (the “spectral selection” method, i.e. spectral samples), or by sequentially, from scan to scan, refinement of DCT coefficients (method of “successive approximation”, i.e. successive approximations). This progressive representation of data is especially useful when transmitting compressed images using low-speed communication channels, since it allows you to get an overview of the entire image after only a small part of the JPEG file has been transmitted.

Both described schemes (both sequential and progressive JPEG) are based on DCT and fundamentally do not allow obtaining a reconstructed image absolutely identical to the original one. However, the standard also allows compression that does not use DCT, but is built on the basis of a linear predictor (lossless, i.e., “lossless”, JPEG), guaranteeing a complete, bit-for-bit, match of the original and restored images. At the same time, the compression ratio for photographic images rarely reaches 2, but the guaranteed absence of distortion in some cases is in demand. Noticeably higher compression ratios can be obtained using the JPEG-LS compression method, which, despite the similarity in names, is not directly related to the JPEG ISO/IEC 10918-1 (ITU T.81 Recommendation) standard, described by the ISO/IEC 14495-1 standard (ITU T.87 Recommendation).

JPEG format syntax and structure

The JPEG file contains the sequence markers, each of which begins with byte 0xFF, indicating the beginning of the marker, and an identifier byte. Some markers consist of only this pair of bytes, while others contain additional data consisting of a two-byte field with the length of the information part of the marker (including the length of this field, but minus the two bytes of the beginning of the marker, i.e. 0xFF and the identifier) ​​and the data itself.

JPEG compression digital image

One of the most comprehensive and popular image compression standards is the JPEG standard.

The compression process itself consists of three successive steps:

a) Calculation of the discrete cosine transform (DCT) for matrices of 8*8 blocks obtained after standard partitioning of the CI matrix;

b) quantization of DCT coefficients;

c) coding with an uneven code.

First, the digital data is divided into separate blocks of 8*8 elements, which are processed sequentially from left to right and top to bottom. The processing of each block begins with a shift in brightness of the values ​​of all its 64 elements, which is achieved by subtracting the value , where is the maximum number of brightness levels. Then the two-dimensional DCT of the block elements is calculated. The obtained coefficient values ​​are quantized in accordance with the formula:

,

where is the result of quantization of the value of the DCT coefficient, and is the corresponding element of the quantization coefficient matrix:

.

(It should be noted that before the quantized DCT coefficients can be subjected to inverse DCT to reconstruct an image block, they must be multiplied by:

. (2.5)

Obviously, the inverse transformation of the obtained values ​​will result in an approximation of the reconstructed image block.)

The quantized values ​​of the coefficients are reordered by a zigzag transformation according to:

where the order in which the coefficients are selected is shown. The result is a one-dimensional sequence of quantized coefficients.

The one-dimensional array obtained after the zigzag transformation is ordered by increasing spatial frequency, which, as a rule, produces long sequences of zeros, which is effectively used by the JPEG encoding procedure. The recommended JPEG quantization matrix is ​​as follows:

Example. Sequential JPEG encoding and decoding. Consider compressing and decompressing the following block of 8*8 elements according to the sequential JPEG encoding standard:

The source pixels can have 256 or 2 8 brightness levels, so the encoding process begins by shifting the range of values ​​- subtracting 2 7 or 128 from the pixel values. The result is an array:

which after direct DCT will look like:

If the above quantization matrix is ​​used to quantize the received data, then after quantization the coefficients will take the form:

The quantization procedure produces a significant number of zero elements. After the coefficients are reordered according to the zigzag transformation, the following array is obtained:

(-26 -31 -3 -2 -6 2 -4 1 -4 1 1 5 0 2 0 0 -1 2 0 0 0 0 0 -1 -1 KB)

The code word KB means the end of the block, indicating that all remaining coefficients in the reordered sequence are equal to 0. To encode the resulting array, standard codes Huffman, which convert the array into a continuous stream of bits.

When reconstructing a compressed JPEG block, the decoder must first recreate the quantized DCT coefficients from a continuous bit stream. Since the binary Huffman code sequence is uniquely decodable, this step is easily implemented using a table transform. After multiplying by quantization coefficients, according to (2.5), we obtain the array:

A completely restored block is obtained after performing the inverse DCT of the resulting array:

and reverse shift of the range of values ​​by +2 7 =+128. As a result we get:

All differences in the values ​​of the elements of the original and restored blocks arise due to the very nature of lossy compression, which is the essence of the JPEG compression and recovery procedures. In this example, the recovery errors range from -14 to 11 and are distributed as follows:

Characteristic features of singular numbers of digital image matrix blocks with JPEG compression . Let the original DI in grayscale, stored in some lossless format, for example, in the TIF format, the matrix of which has dimensions, is divided in a standard way into blocks. If for each DI block we determine the set of all VLFs (singular spectrum), then it turns out that on average only 2.40% of the total number of blocks (ONB) have zero VLFs.

This fact not accidental. The rank of any matrix is ​​determined by the number of its non-zero SLFs, which means the presence of zeros in the singular spectrum will indicate that the number of its linearly independent rows (columns) is less than its size. However, for an arbitrary real DI, even taking into account the correlation of pixel brightness values, the probability that the rows (columns) of the next block will turn out to be linearly dependent is small.

Quantization of DCT coefficients, which occurs during the process of saving DI in JPEG format (with losses), is an irreversible procedure and leads to some features of the disturbances of VLF blocks.

Let the original digital data be subjected to JPEG compression. Let us perform a partial recovery operation (PR) for it, which includes: 1) entropy decoding; 2) multiplying the obtained coefficients by the corresponding elements of the normalization array (quantization matrix); 3) application of inverse DCT, but without subsequent rounding.

In the resulting matrix, almost all blocks contain zero VLFs, and there will be quite a lot of such values ​​in the blocks (Table 2.1). This situation is natural. After quantizing and rounding the coefficients of the DCT blocks, many of them, corresponding to high and medium frequencies, will be reset to zero, remaining zero after the frequency wave, which, taking into account the correspondence between the coefficients of the discrete Fourier transform and the singular triplets of the image matrix, where is the VLF and the corresponding left and right SNV, respectively , will lead to zeroing of the smallest (and possibly medium-sized) VLF block matrices.

Table 2.1. Results of singular value decomposition of blocks of partially reconstructed images

Note that the fewer zero VLFs in the block under consideration, the more contour lines it contains. Indeed, the presence of contours in a block indicates a significant high-frequency component in the signal corresponding to this block. Then the DCT coefficients corresponding to high and medium frequencies will be relatively large and may remain non-zero after quantization and FM, and therefore will contribute not only to the maximum VLF.

To visualize the validity of the above, consider the CELL.TIF image (Fig. 2.5(a)). Figure 2.5(b) shows a matrix of zero VLF blocks (MNSNB) of the dimension of the HF image, each element of which is equal to the number of zero VLF blocks in the corresponding block. The figure highlights the elements that have the smallest values, which allows you to clearly see the correspondence between the contours of the original DI and the blocks containing the smallest number of zero VLFs.

Let the original JPEG-compressed image be completely restored. This means that after the frequency response, all pixel brightness values ​​are rounded to whole numbers and entered into the range. This action will disturb the image matrix obtained after the frequency wave, and the number of zero VLFs in the blocks will change in a certain way (Table 2.2). Where after the CV there were no elements significantly less than 0 or greater than 255, the perturbation of the matrix will be small. According to the ratio

, (2.6)

taking place for an arbitrary matrix, where is the VLF of the original and perturbed matrices, respectively, is the perturbation matrix of the block, is the spectral matrix norm, the VLF are insensitive to disturbing influences. If some of the zero VLF blocks of the FM image matrix become non-zero after complete reconstruction (FRT), then their values ​​will be comparable to the rounding error, which is not typical for blocks of the original DI.

Fig.2.5. Original image CELL.TIF (a); MNSChB after ChV (b); MNSChB after full recovery (c)

The most noticeable difference between the aggregated original image and the fully restored one after JPEG compression will be when comparing their MNSCHB. A typical picture is shown in Fig. 2.5(c), with the MNSChB for CELL.TIF having only zero values.

Table 2.2. Results of singular value decomposition of blocks of fully reconstructed images

Questions

1. What does data compression mean? What is data redundancy?
2. Main types of data redundancy.
3. How is compression implemented through quantization?
4. What is low-rank image approximation? How is compression implemented using low-rank image approximations?
5. What is singular value decomposition of a matrix?
6. What is spectral decomposition of a matrix?
7. Correspondence between digital image parameters in spatial and frequency domains.
8. Basic steps JPEG is digital image compression. Quantization matrices.
9. Characteristic features of singular numbers of digital image matrix blocks in JPEG compression.
10. Partial and full recovery digital image after compression.

Literature

1. Kobozeva A.A. Analysis of information security / A.A.Kobozeva, V.A.Khoroshko. – K.: Ed. GUIKT, 2009. – 251 p.
2. Demmel J. Computational linear algebra / J. Demmel; translated from English Kh.D.Ikramova. - M.: Mir, 2001. - 430 p.
3. Bakhvalov N.S. Numerical methods / N.S.Bakhvalov, N.P.Zhidkov, G.M.Kobelkov. - M.: BINOM. Knowledge Laboratory, 2006. - 636 p.
4. Gonzalez R. Digital processing images / R. Gonzalez, R. Woods; lane from English edited by P.A.Ciochia. - M.: Tekhnosphere, 2005. - 1072 p.
5. Kahaner D. Numerical methods and software/ D. Kahaner, K. Mouler, S. Nash; lane from English Kh.D.Ikramova. - M.: Mir, 2001. - 575 p.
6. Gantmakher F.R. Theory of matrices / F.R. Gantmakher. - M.: Nauka, 1988. - 552 p.
7. Voevodin V.V. Computational Basics linear algebra/ V.V. Voevodin. - M.: Science. Chief editor of physical and mathematical lit., 1977. - 304 p.

It is easy to calculate that an uncompressed full-color image with a size of 2000 * 1000 pixels will have a size of about 6 megabytes. If we talk about images obtained from professional cameras or high-resolution scanners, their size can be even larger. Despite the rapid growth in the capacity of storage devices, various image compression algorithms are still very relevant.
All existing algorithms can be divided into two large classes:

• Lossless compression algorithms;
• Lossy compression algorithms.

Lossless compression algorithms

RLE algorithm

Dictionary algorithms

This table exists both on the side of the one who compresses the information and on the side of the one who decompresses it. Now we will look at the compression process.

The table shows the process of filling out the dictionary. It is easy to calculate that the resulting compressed code takes 105 bits, and the original text (assuming that we spend 4 bits encoding one character) takes 116 bits.
In essence, the decoding process comes down to direct decoding of codes, and it is important that the table is initialized in the same way as during encoding. Now let's look at the decoding algorithm.


We can fully determine the string added to the dictionary at the i-th step only at i+1. Obviously, the i-th line must end with the first character of the i+1 line. That. We just figured out how to restore a dictionary. Of some interest is the situation when a sequence of the form cScSc is encoded, where c is one character and S is a string, and the word cS is already in the dictionary. At first glance it may seem that the decoder will not be able to resolve this situation, but in fact all lines of this type must always end with the same character with which they begin.

Statistical coding algorithms

Huffman algorithm

1. The characters of the input alphabet form a list of free nodes. Each sheet has a weight that is equal to the frequency of occurrence of the symbol
2. Two free tree nodes with the smallest weights are selected
3. Their parent is created with a weight equal to their total weight
4. The parent is added to the list of free nodes, and its two children are removed from this list
5. One arc leaving the parent is assigned bit 1, the other is assigned bit 0
6. Steps starting from the second are repeated until only one free node remains in the list of free nodes. This will be considered the root of the tree.

Arithmetic coding