رویکرد تکاملی چند هدفه به تجارت کردن تصویر با کیفیت / فشرده سازی در الگوریتم پایه JPEG

The JPEG algorithm is one of the most used tools for compressing images. The main factor affecting the performance of the JPEG compression is the quantization process, which exploits the values contained in two tables, called quantization tables. The compression ratio and the quality of the decoded images are determined by these values. Thus, the correct choice of the quantization tables is crucial to the performance of the JPEG algorithm. In this paper, a two-objective evolutionary algorithm is applied to generate a family of optimal quantization tables which produce different trade-offs between image compression and quality. Compression is measured in terms of difference in percentage between the sizes of the original and compressed images, whereas quality is computed as mean squared error between the reconstructed and the original images. We discuss the application of the proposed approach to well-known benchmark images and show how the quantization tables determined by our method improve the performance of the JPEG algorithm with respect to the default tables suggested in Annex K of the JPEG standard.

JPEG is an acronym for “Joint Photographic Experts Group” [1]. This group has been working under the auspices of three major international standards organizations (ISO, CCITT and IEC) for the purpose of developing a standard for colour image compression. As the standard evolved and implementers started deploying it, the name quite naturally became attached in an informal way to the standard itself. JPEG uses the Discrete Cosine Transform (DCT) for its baseline coding technique. The DCT was first applied to image compression in [3]: in this pioneering work the authors showed that DCT is very similar to the KLH (Karhunen–Loeve–Hotelling) transform that performs a decorrelation process so as to produce uncorrelated coefficients. Decorrelation is very important for compression, because each coefficient can be treated independently without losing compression efficiency. Essentially, the n × n 2-D version of DCT decomposes an n × n block of an image into a set of waveforms, each with a particular spatial frequency; thanks to this decomposition, we can separate the image structure the eye can see from the structure that is imperceptible. The JPEG baseline coding algorithm can be summarised as follows: the original uncompressed image is represented in the YCbCr colour space, where Y, Cb and Cr denote luminance, and blue and red chrominance components, respectively; each component is treated separately. For the sake of simplicity we will refer only to the luminance component Y. Anyway, a lot of considerations discussed in this paper can be generalised to manage the other two components. The component Y of the image is segmented into 8 × 8 blocks; each block is transformed independently. The 8 × 8 blocks are zero-shifted by subtracting 128 from the data before applying DCT. Each transformed block is therefore quantized. Quantization introduces an accuracy loss due to the coarse-grained representation of the DCT coefficients. In JPEG coding the accuracy loss occurs entirely in quantization, and much of the compression is gained by run-length coding of coefficients which quantize to zero. After quantization, each block can be efficiently entropy encoded: in this step no information loss occurs. We provide a detailed description of the entire encoding/decoding process in Section 2. As briefly mentioned above, the quantization process is central to the compression/accuracy performance of the JPEG algorithm. The JPEG standard does not specify a quantization table, although two possible tables, namely the Default Luminance Quantization Table (DLQT) and the Default Chrominance Quantization Table (DCQT), are suggested as examples in Annex K. These tables are used for quantizing all the DCT coefficient blocks of luminance and chrominance components, respectively. Unfortunately, it is very difficult to find a quantization table suitable for all images because the coefficient statistics are different from an image to another. In the last recent years, a lot of work has been done in the attempt of determining optimal quantization tables which guarantee the best trade-off between image quality and compression ratio for specific classes of images (natural images, medical images, etc.). To this aim, several optimization methods have been applied. We can coarsely classify them into the following classes: 1. Statistics methods: these methods are based on statistical analysis of the distributions of DCT coefficients for sets of images [5], [8], [9], [13], [14], [17], [20], [22] and [28]. 2. Adaptive methods: these methods start from criticizing the use of a unique quantization table for not only all images, but also for all blocks of a particular image. Thus, they propose an image-dependent approach that makes the JPEG algorithm locally adaptive. These approaches exploit the local frequency content of the image to provide finer control of the DCT coefficients quantization process [4], [24] and [25]. 3. Standard optimization methods: these methods adopt standard optimization techniques, such as gradient method [11] and simulated annealing [16] and [21]. 4. Direct search based methods: these methods exploit single-objective evolutionary algorithms (SOEAs) to search for a quantization table which allows obtaining an optimal compression/accuracy trade-off for specific types of images [6] and [27]. These classes of methods provide a unique solution independently of the particular context in which the compression is required: in some contexts compression could be more relevant than image quality and vice versa. Unfortunately, these methods fix the context before performing optimization: typically, they adopt fitness functions which weight differently the objectives. Once fixed the weights, the methods search the best solution for these weights. Often, it would be preferable to have a family of solutions with different optimal trade-offs between image quality and compression and select the most suitable trade-off for the specific context when necessary. To this aim, we adopt a multi-objective evolutionary algorithm (MOEA) based approach. MOEAs generate a family of equally valid solutions, where each solution tends to satisfy an objective to a higher extent than another. In our case, each solution represents a different quantization table and the two objectives are, respectively, the difference in percentage between the sizes of the original and compressed images, and the mean squared error between the reconstructed and the original images. Thus, the choice of the best solution for the specific context can be delayed to the time in which the compression has to be performed. The use of an MOEA rather than an SOEA is generally preferred when the objectives to be satisfied are in competition and therefore cannot be optimised concurrently. Though the problem of determining optimal quantization tables for classes of images is inherently multi-objective, to the best of our knowledge this problem has been never tackled by using MOEAs. In this paper, we adopt one of most popular MOEAs, the NSGA-II algorithm proposed in [7]. We first apply NSGA-II to three well-known image processing benchmarks, namely, Barbara, Lena and Boat images and discuss how the quantization tables determined by NSGA-II allow achieving remarkable trade-offs between image quality and compression. Then, we show how some of these quantization tables achieve both a higher compression ratio and a better quality than the DLQT. Finally, we replace the DLQT with three of these tables in the free library for JPEG image compression proposed by the Independent JPEG Group (IJG) [2]. We show that the three quantization tables allow producing better trade-offs between image quality and compression than the DLQT with respect to variations of the quality switch, provided in the library to change the quality/compression trade-off. The paper is organized as follows. We first briefly review JPEG image compression baseline algorithm in Section 2. Then, in Section 3 we discuss the quality/compression trade-off issue. In Section 4, we introduce our approach. Finally, in Section 5 we discuss the experimental results.

We have shown how an MOEA can be used to control the trade-off between image compression and quality in JPEG baseline coding algorithm. Here, loss occurs entirely in the quantization step and depends on the values of a quantization table: different quantization tables provide different trade-offs between image compression and quality. We have adopted the well-known and popular NSGA-II algorithm as MOEA. We have performed two different experiments. In the first experiment, we have shown that the NSGA-II allows generating wide Pareto optimal fronts composed of quantization tables which permit achieving considerable trade-offs between image quality and compression for specific images. Further, we have compared these fronts to those obtained by using the DLQT and by varying the quality parameter in the IJG baseline software. We have shown that the fronts generated by NSGA-II dominate the other fronts for all the three images used as benchmark. In the second experiment, we have shown that the DLQT can be replaced by other tables which allow achieving better quality/compression trade-offs. We have selected these tables among the solutions which dominate the DLQT in the three images. We have shown that the fronts generated by using these tables and by varying the quality parameter in the IJG baseline software compare favourably with the fronts generated by using the DLQT, thus attesting that our approach can be also used to search for quantization tables which guarantee high performance for groups of images.