TY - GEN
T1 - Stochastic Model of Block Segmentation Based on Improper Quadtree and Optimal Code under the Bayes Criterion
AU - Nakahara, Yuta
AU - Matsushima, Toshiyasu
N1 - Funding Information:
supported by JSPS KAKENHI Grant Numbers JP17K06446 and
Funding Information:
This work was supported by JSPS KAKENHI Grant Numbers JP17K06446 and JP19K04914.
Publisher Copyright:
© 2022 IEEE.
PY - 2022
Y1 - 2022
N2 - Most previous studies on lossless image compression have focused on improving preprocessing functions to reduce the redundancy of pixel values in real images. However, we assumed stochastic generative models directly on pixel values and focused on achieving the theoretical limit of the assumed models. In this study, we proposed a stochastic model based on improper quadtrees. We theoretically derive the optimal code for the proposed model under the Bayes criterion. In general, Bayes-optimal codes require an exponential order of calculation with respect to the data lengths. However, we propose an efficient algorithm that takes a polynomial order of calculation without losing optimality by assuming a novel prior distribution.
AB - Most previous studies on lossless image compression have focused on improving preprocessing functions to reduce the redundancy of pixel values in real images. However, we assumed stochastic generative models directly on pixel values and focused on achieving the theoretical limit of the assumed models. In this study, we proposed a stochastic model based on improper quadtrees. We theoretically derive the optimal code for the proposed model under the Bayes criterion. In general, Bayes-optimal codes require an exponential order of calculation with respect to the data lengths. However, we propose an efficient algorithm that takes a polynomial order of calculation without losing optimality by assuming a novel prior distribution.
KW - bayes code
KW - lossless image compression
KW - quadtree
KW - stochastic generative model
UR - http://www.scopus.com/inward/record.url?scp=85134376254&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85134376254&partnerID=8YFLogxK
U2 - 10.1109/DCC52660.2022.00023
DO - 10.1109/DCC52660.2022.00023
M3 - Conference contribution
AN - SCOPUS:85134376254
T3 - Data Compression Conference Proceedings
SP - 153
EP - 162
BT - Proceedings - DCC 2022
A2 - Bilgin, Ali
A2 - Marcellin, Michael W.
A2 - Serra-Sagrista, Joan
A2 - Storer, James A.
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 2022 Data Compression Conference, DCC 2022
Y2 - 22 March 2022 through 25 March 2022
ER -