Development and analysis of evolutionary algorithms for quantization table optimization in digital image compression

Abstract

Due to advancements in digital camera technology, the amount of data required to present an image of an acceptable quality is extremely large. Consequently, storage and transmission of digital image are a major problem. The number of images handled by or transmitted through the internet doubles every year. The availability and demand for images continue to outpace increases in network capacity. Hence the importance of compression is getting research focus. Image compression is a key technology, which reduces the size of the image data for storing and transmitting. Image transform coding is the most popular method used in image-coding applications. It is a form of block coding done in the transform domain. Joint Photographic Experts Group (JPEG), the image compression standard is the primary form of transform coding that uses Discrete Cosine Transformation (DCT). Quantization table used in JPEG plays a major role in the tradeoff between the compression and quality of the image. After many experiments, JPEG committee provides two default quantization tables; one for luminance and another for chrominance components and they are included in Annex K of the JPEG standard specification. Independent JPEG group (IJG) scales the default quantization table for different compression ratio / quality trade-off. Default quantization tables cannot provide the optimal performance because the compression ratio and quality are not both maximized. Hence the determination of optimal quantization table is a motivating research topic. In theory, an exhaustive search can be performed to determine the optimal quantization table in the set of possible quantization tables. However, the range of values for a quantization table varies between 1 and 255; in addition, no single uniform quantizer is permanent for each DCT coefficient. Thus, an exhaustive search has to be made among 25564 possible quantization tables which are impractical. Therefore, the key challenge in quantization table design lies in the ability to correctly identify the quantizer value for each DCT coefficient. Literature reveals evolutionary algorithms are appropriate for this type of high dimensional combinatorial problem. The major issues in using evolutionary algorithms are slow convergence speed, uncertainty in producing the feasible solutions and long computation time. Based on the investigation carried out on existing algorithms and considering the above research issues, attempts have been made to develop evolutionary algorithms for quantization table optimization in the JPEG baseline algorithm. The research work is realized in four parts. The first part proposes the evolutionary algorithms; Genetic Algorithm with (μ+λ)-selection and Differential Evolution for the quantization table optimization. The second part incorporates the application specific domain knowledge in the search process of proposed evolutionary algorithms to improve the convergence speed and reliability. Third part of the research presents an extensive performance analysis, among proposed algorithms in terms of their accuracy, search capability, convergence speed and reliability. In addition, it performs a statistical significance test (t-test) to confirm the interpretation of the empirical results. As the last part of the research, efforts have been taken to reduce the computation time of the evolutionary algorithm by using the surrogate model. The performance of the model is identified based on approximation error and evolutionary perspective and it is confirmed using statistical hypothesis tests such as Friedman’s ANOVA and Wilcoxon Signed Rank.