Vinoth Kumar BALASUBRAMANIAN, Karpagam MANAVALAN

Knowledge-based genetic algorithm approach to quantization table generation for the JPEG baseline algorithm

JPEG has played an important role in the image compression field for the past two decades. Quantization tables in the JPEG scheme is a key factor that is responsible for compression/quality trade-off. Finding the optimal quantization table is an open research problem. Studies recommend the genetic algorithm to generate the optimal solution. Recent reports revealed optimal quantization table generation based on a classical genetic algorithm (CGA). Although the CGA produces better results, it shows inefficiency in terms of convergence speed and productivity of feasible solutions. This paper proposes a knowledge-based genetic algorithm (KBGA), which combines the image characteristics and knowledge about image compressibility with CGA operators such as initialization, selection, crossover, and mutation for searching for the optimal quantization table. The experimental results show that the optimal quantization table generated using the proposed KBGA outperforms the default JPEG quantization table in terms of mean square error (MSE) and peak signal-to-noise ratio (PSNR) for target bits per pixel. The KBGA was also tested on a variety of images in three different bits values per pixel to show its strength. The proposed KBGA produces an average PSNR gain of 3.3% and average MSE gain of 20.6% over the default JPEG quantization table. The performance measures such as average unfitness value, likelihood of evolution leap, and likelihood of optimality are used to validate the efficacy of the proposed KBGA. The novelty of the KBGA lies in the number of generations used to attain an optimal solution as compared to the CGA. The validation results show that this proposed KBGA guarantees feasible solutions with better quality at faster convergence rates.

PDF

___

[1] Jayaraman S, Esakkirajan S, Veerakumar T. Digital Image Processing. 1st ed. New Delhi, India: Tata McGraw Hill, 2009.
[2] Russotti P, Anderson R. Digital Photography Best Practices and Workflow Handbook. 1st ed. Burlington, MA, USA: Elsevier, 2010.
[3] Ra MR, Govindan R, Ortega A. Toward privacy-preserving photo sharing. In: USENIX 2013 Networked Systems Design and Implementation Symposium; 25 April 2013; Lombard, IL, USA. Berkeley, CA, USA: USENIX. pp.515-528.
[4] Wallace G. The JPEG still picture compression standard. IEEE T Consum Electr 1992; 38: 18-34.
[5] Lazzerini B, Marcelloni F, Vecchio M. A multi-objective evolutionary approach to image quality/compression ratio trade-off in JPEG baseline algorithm. Appl Soft Comput 2010; 10: 548-561.
[6] Fung HT, Parker KJ. Design of image adaptive quantization tables for JPEG. J Electron Imaging 1995; 4: 144-150.
[7] Fong WC, Chan SC, Ho KL. Designing JPEG quantization matrix using rate-distortion approach and human visual system model. In: IEEE 1997 Communications Conference; 812 June 1997; Montreal, Canada. New York, NY,USA: IEEE. pp. 1659-1663.
[8] Long WC, Ching YW, Shiuh ML. Designing JPEG quantization tables based on human visual system. In: IEEE 1999 Image Processing Conference; 2428 October 1999; Kobe, Japan. New York, NY, USA: IEEE. pp. 376-380.
[9] Viresh R, Livny M. An efficient algorithm for optimizing dct quantization. IEEE T Image Process 2000; 9: 267-270.
[10] Battiato S, Mancuso M, Bosco A, Guarnera M. Psychovisual and statistical optimization of quantization tables for DCT compression engines. In: IEEE 2001 Image Analysis and Processing Conference; 2628 September 2001; Palermo, Italy. New York, NY, USA: IEEE. pp. 602-606.
[11] Zaid AO, Olivier C, Alata O, Marmoiton F. Transform image coding with global thresholding application to baseline JPEG. In: IEEE 2001 Computer Graphics and Image Processing XIV Brazilian Symposium; 1518 October 2001; Florianopolis, Brazil. New York, NY, USA: IEEE. pp. 164-171.
[12] Abu NA, Ernawan F, Suryana N. A generic psycho visual error threshold for the quantization table generation on jpeg image compression. In: IEEE 2013 Signal Processing and Its Applications Colloquium; 810 March 2013; Kuala Lumpur, Malaysia. New York, NY, USA: IEEE. pp. 39-43.
[13] Jianshu C, Hu C, Eckehard S. On the design of a novel JPEG quantization table for improved feature detection performance. In: IEEE 2013 Image Processing Conference; 1518 September 2013; Melbourne, Australia. New York,NY, USA: IEEE. pp. 1675-1679.
[14] Sherlock B, Nagpal A, Monro D. A model for JPEG quantization. In: IEEE 1994 Speech, Image Processing and Neural Networks Conference; 1316 April 1994; Hong Kong, China. New York, NY, USA: IEEE. pp. 176-179.
[15] Jiang Y. JPEG image compression using quantization table optimization based on perceptual image quality assessment. In: IEEE 2011 Signals, Systems and Computers Conference; 6-9 November 2011; Pacific Grove, CA. New York, NY, USA: IEEE. pp. 225-229.
[16] Wu YG. GA-based DCT quantization table design procedure for medical images. IEE P Vis Image Sign 2004; 151:353-359.
[17] Costa LF, Veiga ACP. Identification of the best quantization table using genetic algorithms. In: IEEE 2005 Communications, Computers and Signal Processing Pacific Rim Conference; 2426 August 2005; Victoria, Canada. New York, NY, USA: IEEE. pp. 570-573.
[18] Bonyadi MR, Dehghani E, Moghaddam ME. A non-uniform image compression using genetic algorithm. In: IEEE 2008 Systems, Signals and Image Processing Conference; 2528 June 2008; Bratislava, Slovakia. New York, NY,USA: IEEE. pp. 315-318.
[19] Chen S, An T, Hao L. Discrete cosine transforms image compression based on genetic algorithm. In: IEEE 2009 Information Engineering and Computer Science Conference; 1920 December 2009; Wuhan, China. New York, NY,USA: IEEE. pp. 1-3.
[20] Konrad M, Stogner H, Uhl A. Evolutionary optimization of jpeg quantization tables for compressing iris Polar images in iris recognition systems. In: IEEE 2009 Image and Signal Processing and Analysis Symposium; 1618 September 2009; Salzburg, Austria. New York, NY, USA: IEEE. pp. 534-539.
[21] Guo SM, Tsai JSH, Chang WH, Wu BH, Guo SJ. Chaos evolutionary programming based jpeg quantization table generation scheme. In: IEEE 2007 Informatics and Systems Conference; 2426 March 2007; Cairo, Egypt. New York, NY, USA: IEEE. pp. 1-7.
[22] Ma H, Zhang Q. Research on cultural-based multi-objective particle swarm optimization in image compression quality assessment. Optik 2013; 124: 957-961.
[23] Bakirtzis AG, Biskas PN, Zoumas CE, Vasilios P. Optimal power flow by enhanced genetic algorithm. IEEE T Power Syst 2002; 17: 229-236.
[24] Angelova M, Melo-Pinto P, Pencheva T. Modified simple genetic algorithms improving convergence time for the purposes of fermentation process parameter identification. Ele Com Eng 2012; 11: 256-267.
[25] Prakash A, Chan FTS, Deshmukh SG. FMS scheduling with knowledge based genetic algorithm approach. Expert Syst Appl 2011; 38: 3161-3171.
[26] Prakash A, Chan FTS, Liao H, Deshmukh SG. Network optimization in supply chain - a KBGA approach. Decis Support Syst 2012; 52: 528-538.
[27] Thompson M, Pimentel AD. Exploiting domain knowledge in system-level MPSoC design space exploration. J Syst Architect 2013; 59: 351-360.
[28] Goldberg DE. Genetic Algorithms in Search, Optimization, and Machine Learning. 1st ed. London, UK: AddisonWesley, 1999.
[29] Vivek KG. Theoretical foundations of transform coding. IEEE Signal Proc Mag 2001; 1: 9-21.
[30] Razali NM, Geraghty J. Genetic algorithm performance with different selection strategies in solving TSP. In: WCE 2011 World Congress on Engineering Conference; 68 July 2011; London, UK. Hong Kong: IAENG. pp. 1134-1139.
[31] Kanungo T, Mount DM, Netanyahu NS, Piatko CD, Silverman R, Wu AY. An efficient k-means clustering algorithm analysis and implementation. IEEE T Pattern Anal 2002; 24: 881-892.
[32] Pena JM, Lozano JM, Larranaga P. An empirical comparison of four initialization methods for the k-means algorithm. Pattern Recogn Lett 1999; 20: 1027-1040.
[33] Celebi ME, Kingravi HA, Vela PA. A comparative study of efficient initialization methods for the k-means clustering algorithm. Expert Syst Appl 2013; 40: 200-210.
[34] Jung SH. Selective mutation for genetic algorithms. World Academy of Science, Engineering and Technology 2009; 32: 478-481.
[35] Kazuo S. Measures for performance evaluations of genetic algorithms. In: 1997 Information Sciences Conference; 15 March 1997; Research Triangle Park, NC, USA. pp. 153-156.
[36] Scrucca L. GA - a package for genetic algorithms in R. J Stat Softw 2013; 4: 1-37.