Why Shape Coding? Asymptotic Analysis of the Entropy Rate for Digital Images

Gangtao Xin; Pingyi Fan; Khaled B Letaief

doi:10.3390/e25010048

Why Shape Coding? Asymptotic Analysis of the Entropy Rate for Digital Images

Entropy (Basel). 2022 Dec 27;25(1):48. doi: 10.3390/e25010048.

Authors

Gangtao Xin^{1

2}, Pingyi Fan^{1

2}, Khaled B Letaief³

Affiliations

¹ Department of Electronic Engineering, Tsinghua University, Beijing 100084, China.
² Beijing National Research Center for Information Science and Technology, Tsinghua University, Beijing 100084, China.
³ Department of Electrical and Computer Engineering, Hong Kong University of Science and Technology (HKUST), Hong Kong.

Abstract

This paper focuses on the ultimate limit theory of image compression. It proves that for an image source, there exists a coding method with shapes that can achieve the entropy rate under a certain condition where the shape-pixel ratio in the encoder/decoder is O(1/logt). Based on the new finding, an image coding framework with shapes is proposed and proved to be asymptotically optimal for stationary and ergodic processes. Moreover, the condition O(1/logt) of shape-pixel ratio in the encoder/decoder has been confirmed in the image database MNIST, which illustrates the soft compression with shape coding is a near-optimal scheme for lossless compression of images.

Keywords: asymptotic bounds; entropy rate; image compression; information theory; limit theorem.

Grants and funding

This work was supported by the National Key Research and Development Program of China (Grant NO. 2021.YFA1000500(4)).