Аdaptive combined image coding with prediction of arithmetic code volume

The problem of increasing the efficiency of coding of halftone images in the space of bit planes of differences in pixel values obtained using differential coding (DPCM – Differential pulse-code modulation) is considered. For a compact representation of DPCM pixel values, it is proposed to use a combined compression encoder that implements arithmetic coding and run-length coding. An arithmetic encoder provides high compression ratios, but has high computational complexity and significant encoding overhead. This makes it effective primarily for compressing the mean-value bit-planes of DPCM pixel values. Run-length coding is extremely simple and outperforms arithmetic coding in compressing long sequences of repetitive symbols that often occur in the upper bit planes of DPCM pixel values. For DPCM bit planes of pixel values of any image, a combination of simple run length coders and complex arithmetic coders can be selected that provides the maximum compression ratio for each bit plane and all planes in general with the least computational complexity. As a result, each image has its own effective combined encoder structure, which depends on the distribution of bits in the bit planes of the DPCM pixel values. To adapt the structure of the combined encoder to the distribution of bits in the bit planes of DPCM pixel values, the article proposes to use prediction of the volume of arithmetic code based on entropy and comparison of the obtained predicted value with the volume of run length code. The entropy is calculated based on the values of the number of repetitions of ones and zero symbols, which are obtained as intermediate results of the run length encoding. This does not require additional computational costs. It was found that in comparison with the adaptation of the combined encoder structure using direct determination of the arithmetic code volume of each bit plane of DPCM pixel values, the proposed encoder structure provides a significant reduction in computational complexity while maintaining high image compression ratios.

1. Marcellin M.W., Gormish M.J., Bilgin A., Boliek M.P. An Overview of JPEG-2000. Proc. of IEEE Data Compression Conference. 2000;523-541. DOI: 10.1109/DCC.2000.838192.

2. Xue S., Xu Y., Oelmann B. Hybrid Golomb codes for a group of quantised GG sources. IEEE Proc. – Vision, Image and Signal Processing. 2003;150(4):256-260. DOI: 10.1049/ip-vis:20030510.

3. Su C., Hsin H., Lin S. Wavelet tree classification and hybrid coding for image compression. IEEE Proc. – Vision, Image and Signal Processing. 2005;152(6):752-756. DOI: 10.1049/ip-vis:20050004.

4. Mukherjee D. Parameter Selection for Wyner-Ziv Coding of Laplacian Sources with Additive Laplacian or Gaussian Innovation. IEEE Trans. on Signal Processing. 2009;57(8):3208-3225.

5. Banerjee A., Halder A. An efficient image compression algorithm for almost dual-color image based on k-means clustering, bit-map generation and RLE. 2010 International Conference on Computer and Communication Technology (ICCCT), Allahabad, Uttar Pradesh. 2010:201-205. DOI: 10.1109/ICCCT.2010.5640529.

6. Salman N.H., Rafea S. The Arithmetic Coding and Hybrid Discrete Wavelet and Cosine Transform Approaches in Image Compression. Journal of Southwest Jiaotong University. 2020;55(1):9.

7. Gahalot D., Mehra R. Huffman coding algorithm and DCT implementation for hybrid image compression on Matlab platform. Pramana Research Journal. 2019;9(11):53-61.

8. Xu C., Ye Y., Hu Z., Zou Y., Shen L., Liu X., Lu J. A primal-dual algorithm for robust fractal image coding. Fractals. 2019;27(7):14. DOI: 10.1142/S0218348X19501196.

9. Nag S. Vector quantization using the improved differential evolution algorithm for image compression. Genetic Programming and Evolvable Machines. 2019;20:187-212. DOI: 10.1007/s10710-019-09342-8.

10. Weinberger M.J., Seroussi G., Sapiro G. The LOCO-I lossless image compression algorithm: principles and standardization into JPEG-LS. IEEE Transactions on Image Processing. 2000;9(8):1309-1324.

11. Birajdar A., Agarwal H., Bolia M., Gupte V. Image Compression using Run Length Encoding and its Optimisation. 2019 Global Conference for Advancement in Technology (GCAT), Bangaluru, India. 2019: 1-6.

12. Alias B., Mehra A., Harsha P. Hardware implementation and testing of effective DPCM image compression technique using multiple-LUT. 2014 International Conference on Advances in Electronics Computers and Communications, Bangalore. 2014:1-4. DOI: 10.1109/ICAECC.2014.7002433.

13. Al-Bahadily H.K., Altaay A.A.J., Tsviatkou V.U., Kanapelka V.K. New modified RLE algorithms to compress grayscale images with lossy and lossless compression. International Journal of Advanced Computer Science and Applications. 2016;7(7):250-255. DOI: 10.14569/IJACSA.2016.070734.