Vector Quantized Codebook Optimization Using Modified Genetic Algorithm

Abstract

Vector Quantization (VQ) is lossy data compression technique and has various applications. Key to VQ is a good codebook. Once the codebook size is fixed, then the mean square error (MSE) reaches a value, beyond which it cannot be reduced by using codebook generation algorithms. In this paper, we are proposing modified genetic algorithm giving the optimal value, but it depends on the initial selection of the codevectors. Hence, it takes extremely huge time to give optimal value. For demonstration, we have used codebooks obtained from Linde Buzo and Gray (LBG) and Kekre’s Fast Codebook Generation (KFCG) algorithms. It is observed that the optimal error obtained from both LBG and KFCG is almost the same, indicating that they have converged to an optimal value. From the results, it is obvious that KFCG codebook gives slightly less minimized error as compared to LBG, indicating that KFCG codebook is closer to the optimum. The proposed method is general and can be applied to any clustering algorithm.

Keywords:

• Codebook
• Data compression
• Genetic algorithm
• Optimization
• Vector quantization

Additional information

Notes on contributors

H. B. Kekre

H. B. Kekre has received the degrees of B.E. (Hons.) in Telecomm. Engineering from Jabalpur University in 1958, M.Tech. (Industrial Electronics) from IIT Bombay in 1960, M.S. Engg. (Electrical Engg.) from University of Ottawa in 1965 and Ph.D. (System Identification) from IIT Bombay in 1970. He has worked as Faculty of Electrical Engg. and then HOD Computer Science and Engg. at IIT Bombay. For 13 years, he worked as a Professor and Head in the Department of Computer Engg. at Thadomal Shahani Engineering College, Mumbai. Now, he is a Senior Professor at MPSTME, SVKM’s NMIMS University. He has guided 17 Ph.D.s, more than 100 M.E./M.Tech. and several B.E./B.Tech. projects. His areas of interest are Digital Signal processing, Image Processing and Computer Networking. He has more than 250 papers in national/international conferences and journals to his credit. He was a Senior Member of IEEE. Presently, he is a Fellow of IETE and Life Member of ISTE. Recently, six students working under his guidance have received best paper awards. Currently, 10 research scholars are pursuing Ph.D. program under his guidance. E-mail: [email protected]

Tanuja K. Sarode

Tanuja K. Sarode has received the degrees of B.Sc. (Mathematics) from Mumbai University in 1996, B.Sc. Tech. (Computer Technology) from Mumbai University in 1999, M.E. (Computer Engineering) degree from Mumbai University in 2004, and she is currently pursuing Ph.D. from Mukesh Patel School of Technology, Management and Engineering, SVKM’s NMIMS University, Vile-Parle (W), Mumbai, India. She has more than 10 years of experience in teaching. Currently, she is working as an Assistant Professor in Dept. of Computer Engineering at Thadomal Shahani Engineering College, Mumbai. She is a life member of IETE, member of International Association of Engineers (IAENG) and International Association of Computer Science and Information Technology (IACSIT), Singapore. Her areas of interest are Image Processing, Signal Processing and Computer Graphics. She has 52 papers in National/International conferences/journals to her credit. E-mail: [email protected]