Stochastic Model of Block Segmentation Based on Improper Quadtree and Optimal Code under the Bayes Criterion

Yuta Nakahara*, Toshiyasu Matsushima

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Citation (Scopus)


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.

Original languageEnglish
Title of host publicationProceedings - DCC 2022
Subtitle of host publication2022 Data Compression Conference
EditorsAli Bilgin, Michael W. Marcellin, Joan Serra-Sagrista, James A. Storer
PublisherInstitute of Electrical and Electronics Engineers Inc.
Number of pages10
ISBN (Electronic)9781665478939
Publication statusPublished - 2022
Event2022 Data Compression Conference, DCC 2022 - Snowbird, United States
Duration: 2022 Mar 222022 Mar 25

Publication series

NameData Compression Conference Proceedings
ISSN (Print)1068-0314


Conference2022 Data Compression Conference, DCC 2022
Country/TerritoryUnited States


  • bayes code
  • lossless image compression
  • quadtree
  • stochastic generative model

ASJC Scopus subject areas

  • Computer Networks and Communications


Dive into the research topics of 'Stochastic Model of Block Segmentation Based on Improper Quadtree and Optimal Code under the Bayes Criterion'. Together they form a unique fingerprint.

Cite this