{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,7]],"date-time":"2026-03-07T14:17:24Z","timestamp":1772893044735,"version":"3.50.1"},"reference-count":33,"publisher":"MDPI AG","issue":"8","license":[{"start":{"date-parts":[[2021,7,30]],"date-time":"2021-07-30T00:00:00Z","timestamp":1627603200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"publisher","award":["JP17K06446"],"award-info":[{"award-number":["JP17K06446"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"publisher","award":["JP19K04914"],"award-info":[{"award-number":["JP19K04914"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Entropy"],"abstract":"<jats:p>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, 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 discussing the difference between the expected code length and the entropy of the stochastic generative model. We solve this difficulty for a class of images, in which they have non-stationarity among segments. In this paper, we propose a novel stochastic generative model of images by redefining the implicit stochastic generative model in a previous coding procedure. Our model is based on the quadtree so that it effectively represents the variable block size segmentation of images. Then, we construct the Bayes code optimal for the proposed stochastic generative model. It requires the summation of all possible quadtrees weighted by their posterior. In general, its computational cost 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 optimality. As a result, the derived algorithm has a better average coding rate than that of JBIG.<\/jats:p>","DOI":"10.3390\/e23080991","type":"journal-article","created":{"date-parts":[[2021,7,30]],"date-time":"2021-07-30T12:59:24Z","timestamp":1627649964000},"page":"991","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":10,"title":["A Stochastic Model for Block Segmentation of Images Based on the Quadtree and the Bayes Code for It"],"prefix":"10.3390","volume":"23","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0553-7910","authenticated-orcid":false,"given":"Yuta","family":"Nakahara","sequence":"first","affiliation":[{"name":"Center for Data Science, Waseda University, 1\u20136\u20131 Nisniwaseda, Shinjuku-ku, Tokyo 169-8050, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Toshiyasu","family":"Matsushima","sequence":"additional","affiliation":[{"name":"Department of Pure and Applied Mathematics, Waseda University, 3\u20134\u20131 Okubo, Shinjuku-ku, Tokyo 169-8555, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2021,7,30]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"379","DOI":"10.1002\/j.1538-7305.1948.tb01338.x","article-title":"A mathematical theory of communication","volume":"27","author":"Shannon","year":"1948","journal-title":"Bell Syst. Tech. J."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"1098","DOI":"10.1109\/JRPROC.1952.273898","article-title":"A Method for the Construction of Minimum-Redundancy Codes","volume":"40","author":"Huffman","year":"1952","journal-title":"Proc. IRE"},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"12","DOI":"10.1109\/TIT.1981.1056282","article-title":"Universal modeling and coding","volume":"27","author":"Rissanen","year":"1981","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"337","DOI":"10.1109\/TIT.1977.1055714","article-title":"A universal algorithm for sequential data compression","volume":"23","author":"Ziv","year":"1977","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"530","DOI":"10.1109\/TIT.1978.1055934","article-title":"Compression of individual sequences via variable-rate coding","volume":"24","author":"Ziv","year":"1978","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"783","DOI":"10.1109\/TIT.1973.1055092","article-title":"Universal noiseless coding","volume":"19","author":"Davisson","year":"1973","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1109\/TIT.1973.1054929","article-title":"Enumerative source encoding","volume":"19","author":"Cover","year":"1973","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_8","doi-asserted-by":"crossref","unstructured":"Matsushima, T., and Hirasawa, S. (July, January 28). Reducing the space complexity of a Bayes coding algorithm using an expanded context tree. Proceedings of the 2009 IEEE International Symposium on Information Theory, Seoul, Korea.","DOI":"10.1109\/ISIT.2009.5205677"},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"653","DOI":"10.1109\/18.382012","article-title":"The context-tree weighting method: Basic properties","volume":"41","author":"Willems","year":"1995","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_10","unstructured":"Kontoyiannis, I., Mertzanis, L., Panotopoulou, A., Papageorgiou, I., and Skoularidou, M. (2020). Bayesian Context Trees: Modelling and exact inference for discrete time series. arXiv."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"1309","DOI":"10.1109\/83.855427","article-title":"The LOCO-I lossless image compression algorithm: Principles and standardization into JPEG-LS","volume":"9","author":"Weinberger","year":"2000","journal-title":"IEEE Trans. Image Process."},{"key":"ref_12","first-page":"882","article-title":"Lossless image compression by two-dimensional linear prediction with variable coefficients","volume":"75","author":"Kuroki","year":"1992","journal-title":"IEICE Trans. Fund. Electron. Commun. Comput. Sci."},{"key":"ref_13","unstructured":"Wu, X., Barthel, E., and Zhang, W. (1998, January 7). Piecewise 2D autoregression for predictive image coding. Proceedings of the 1998 International Conference on Image Processing. ICIP98 (Cat. No.98CB36269), Chicago, IL, USA."},{"key":"ref_14","unstructured":"Meyer, B., and Tischer, P. (2001). Glicbawls\u2014Grey Level Image Compression by Adaptive Weighted Least Squares. Data Compression Conference, IEEE Computer Society."},{"key":"ref_15","unstructured":"Ye, H., Deng, G., and Devlin, J.C. (2003, January 23\u201325). A weighted least squares method for adaptive prediction in lossless image compression. Proceedings of the Picture Coding Symposium, Saint-Malo, France."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"5519","DOI":"10.1109\/TIP.2014.2365698","article-title":"Lossless Predictive Coding for Images With Bayesian Treatment","volume":"23","author":"Liu","year":"2014","journal-title":"IEEE Trans. Image Process."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"1382","DOI":"10.1109\/TIP.2016.2522339","article-title":"Probability Distribution Estimation for Autoregressive Pixel-Predictive Image Coding","volume":"25","author":"Weinlich","year":"2016","journal-title":"IEEE Trans. Image Process."},{"key":"ref_18","unstructured":"Meyer, B., and Tischer, P. (1997, January 10\u201312). TMW\u2014A new method for lossless image compression. Proceedings of the 1997 Picture Coding Symposium (PCS\u201997), Berlin, Germany."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"5263","DOI":"10.1109\/TIP.2013.2284067","article-title":"Bayesian Predictor Combination for Lossless Image Compression","volume":"22","author":"Martchenko","year":"2013","journal-title":"IEEE Trans. Image Process."},{"key":"ref_20","unstructured":"Matsuda, I., Ozaki, N., Umezu, Y., and Itoh, S. (2005, January 4\u20138). Lossless coding using variable block-size adaptive prediction optimized for each image. Proceedings of the 2005 13th European Signal Processing Conference, Antalya, Turkey."},{"key":"ref_21","doi-asserted-by":"crossref","unstructured":"Ulacha, G., Stasi\u0144ski, R., and Wernik, C. (2020). Extended Multi WLS Method for Lossless Image Coding. Entropy, 22.","DOI":"10.3390\/e22090919"},{"key":"ref_22","doi-asserted-by":"crossref","unstructured":"Mentzer, F., Agustsson, E., Tschannen, M., Timofte, R., and Van Gool, L. (2019, January 15\u201321). Practical Full Resolution Learned Lossless Image Compression. Proceedings of the 2019 IEEE\/CVF Conference on Computer Vision and Pattern Recognition (CVPR), Long Beach, CA, USA.","DOI":"10.1109\/CVPR.2019.01088"},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"437","DOI":"10.1109\/26.585919","article-title":"Context-based, adaptive, lossless image coding","volume":"45","author":"Wu","year":"1997","journal-title":"IEEE Trans. Commun."},{"key":"ref_24","unstructured":"Nakahara, Y., and Matsushima, T. (2020, January 24\u201327). Autoregressive Image Generative Models with Normal and t-distributed Noise and the Bayes Codes for Them. Proceedings of the 2020 International Symposium on Information Theory and Its Applications (ISITA), Kapolei, HI, USA."},{"key":"ref_25","first-page":"330","article-title":"Bayes code for two-dimensional auto-regressive hidden Markov model and its application to lossless image compression","volume":"Volume 11515","author":"Nakahara","year":"2020","journal-title":"Proceedings of the International Workshop on Advanced Imaging Technology (IWAIT) 2020"},{"key":"ref_26","doi-asserted-by":"crossref","unstructured":"Nakahara, Y., and Matsushima, T. (2020, January 24\u201327). A Stochastic Model of Block Segmentation Based on the Quadtree and the Bayes Code for It. Proceedings of the 2020 Data Compression Conference (DCC), Snowbird, UT, USA.","DOI":"10.1109\/DCC47342.2020.00037"},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"1649","DOI":"10.1109\/TCSVT.2012.2221191","article-title":"Overview of the High Efficiency Video Coding (HEVC) Standard","volume":"22","author":"Sullivan","year":"2012","journal-title":"IEEE Trans. Circuits Syst. Video Technol."},{"key":"ref_28","doi-asserted-by":"crossref","unstructured":"Dobashi, N., Saito, S., Nakahara, Y., and Matsushima, T. (2021). Meta-Tree Random Forest: Probabilistic Data-Generative Model and Bayes Optimal Prediction. Entropy, 23.","DOI":"10.3390\/e23060768"},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"1288","DOI":"10.1109\/18.133247","article-title":"A class of distortionless codes designed by Bayes decision theory","volume":"37","author":"Matsushima","year":"1991","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"453","DOI":"10.1109\/18.54897","article-title":"Information-theoretic asymptotics of Bayes methods","volume":"36","author":"Clarke","year":"1990","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_31","unstructured":"Mart\u00edn, G. (1979, January 24\u201327). Range encoding: An algorithm for removing redundancy from a digitised message. Proceedings of the Video and Data Recording Conference, Southampton, UK."},{"key":"ref_32","unstructured":"Kuhn, M. (2021, July 30). JBIG-KIT. Available online: https:\/\/www.cl.cam.ac.uk\/~mgk25\/jbigkit\/."},{"key":"ref_33","unstructured":"(2021, July 30). Image Repository of the University of Waterloo. Available online: http:\/\/links.uwaterloo.ca\/Repository.html."}],"container-title":["Entropy"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1099-4300\/23\/8\/991\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T06:37:55Z","timestamp":1760164675000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1099-4300\/23\/8\/991"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,7,30]]},"references-count":33,"journal-issue":{"issue":"8","published-online":{"date-parts":[[2021,8]]}},"alternative-id":["e23080991"],"URL":"https:\/\/doi.org\/10.3390\/e23080991","relation":{},"ISSN":["1099-4300"],"issn-type":[{"value":"1099-4300","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,7,30]]}}}