  In information theory, lossless compression of general data is based on an
explicit assumption of a stochastic generative model on target data. However,
in lossless image compression, the researchers have mainly focused on the
coding procedure that outputs the coded sequence from the input image, and the
assumption of the stochastic generative model is implicit. In these studies,
there is a difficulty in confirming the information-theoretical optimality of
the coding procedure to the stochastic generative model. Hence, in this paper,
we propose a novel stochastic generative model of images by redefining the
implicit stochastic generative model in a previous coding procedure. That is
based on the quadtree so that our model effectively represents the variable
block size segmentation of images. Then, we construct the Bayes code optimal
for the proposed stochastic generative model. In general, the computational
cost to calculate the posterior distribution required in the Bayes code
increases exponentially for the image size. However, we introduce an efficient
algorithm to calculate it in the polynomial order of the image size without
loss of the optimality. Some experiments are performed to confirm the
flexibility of the proposed stochastic model and the efficiency of the
introduced algorithm.
