Lossless Compression of Grayscale Images via Representation of Bit Planes as Minimized Boolean Functions

International Journal of Electrical and Electronics Engineering

© 2025 by SSRG - IJEEE Journal

Volume 12 Issue 4

Year of Publication : 2025

Authors : M. Swathi Pai, Shyam P. Joy, Jacob Augustine

10.14445/23488379/IJEEE-V12I4P115

How to Cite?

M. Swathi Pai, Shyam P. Joy, Jacob Augustine, "Lossless Compression of Grayscale Images via Representation of Bit Planes as Minimized Boolean Functions," SSRG International Journal of Electrical and Electronics Engineering, vol. 12,  no. 4, pp. 210-221, 2025. Crossref, https://doi.org/10.14445/23488379/IJEEE-V12I4P115

Abstract:

Electronic Design Automation (EDA) research has made great strides owing to the industrial growth in the VLSI domain. Boolean function minimization is an important area in this domain. Many engineering problems can be formulated as logic functions, and the tools available in this domain can be applied to solve them. Image compression is formulated as a logic minimization problem by converting blocks of the bit planes of the grayscale image into Boolean functions and representing them in minimal form. An encoding scheme called logic coding was developed by this approach, which extended the block coding scheme. In this paper, we provide a comprehensive survey of research work that happened in this direction. A Python implementation of the basic logic coding scheme is also presented. Experimental results reveal that there are many blocks in the bit planes that are not compressible by these techniques. This data motivates us to explore options not tried by other researchers, although it is not a very active area of research. Lossless compression of images is an important area for medical images, and there is scope for further research. Medical images are an area where lossless compression is mandated; hence, it is still a relevant problem to research. This exploration is done with the intention to enhance existing logic coding techniques by applying other Boolean function representation schemes and a combination of various techniques to achieve better compression. Also, in areas such as deep learning and Natural Language Processing where binary multi-dimensional space is used, Boolean function representation could open further possibilities.

Keywords:

Logic minimization, Boolean functions, Lossless image compression, PyEDA, Block coding.

References:

[1] Eugene Ageenko, and Pasi Fränti, “Lossless Compression of Large Binary Images in Digital Spatial Libraries,” Computers and Graphics, vol. 24, no. 1, pp. 91-98, 2000.
[CrossRef] [Google Scholar] [Publisher Link]
[2] Pasi Fränti, and Olli Nevalainen, “Compression of Binary Images by Composite Methods Based on Block Coding,” Journal of Visual Communication and Image Representation, vol. 6, no. 4, pp. 366-377, 1995.
[CrossRef] [Google Scholar] [Publisher Link]
[3] David A. Clunie, “Lossless Compression of Grayscale Medical Images: Effectiveness of Traditional and State-of-the-Art Approaches,” Medical Imaging 2000: PACS Design and Evaluation: Engineering and Clinical Issues, vol. 3980, pp. 74-84, 2000.
[CrossRef] [Google Scholar] [Publisher Link]
[4] Khalid Sayood, Introduction to Data Compression, 5th ed., Morgan Kaufmann, 2017.
[Google Scholar] [Publisher Link]
[5] M.J. Weinberger, G. Seroussi, and G. Sapiro, “From Logoi to the JPEG-LS Standard,” Proceedings International Conference on Image Processing (Cat. 99CH36348), Kobe, Japan, 1999.
[CrossRef] [Google Scholar] [Publisher Link]
[6] Rafael C. Gonzalez, Digital Image Processing, Pearson Education India, 2nd ed., 2009.
[Google Scholar]
[7] B.J. Falkowski, and Lip-San Lim, “Gray Scale Image Compression Based on Multiple-Valued Input Binary Functions, Walsh and Reed Muller Spectra,” Proceedings 30th IEEE International Symposium on Multiple-Valued Logic, Portland, USA, pp. 279-284, 2000.
[CrossRef] [Google Scholar] [Publisher Link]
[8] Majid Rabbani, and Paul W. Jones, Digital Image Compression Techniques, SPIE Press, vol. 7, 1991.
[CrossRef] [Google Scholar] [Publisher Link]
[9] Shahriar Akramullah, Digital Video Concepts, Methods, and Metrics: Quality, Compression, Performance, and Power Trade-off Analysis, 1st ed., Apress Berkeley, CA, 2014.
[CrossRef] [Google Scholar] [Publisher Link]
[10] J. Mitchell, “Digital Compression and Coding of Continuous Tone Still Images: Requirements and Guidelines,” ITU-T Recommendation, 1992.
[Google Scholar] [Publisher Link]
[11] Abd Abrahim Mosslah, Reyadh Hazim Mahdi, and Hind Khalil Abrahem, “Efficient JPEG-LS for Lossless Compression of Rib Cage with Visual Quality Preservation,” Proceedings of the World Congress on Engineering, IAENG, London, U.K, 2021.
[Google Scholar] [Publisher Link]
[12] Murat Kunt, and O. Johnsen, “Block Coding of Graphics: A Tutorial Review,” Proceedings of the IEEE, vol. 68, no. 7, pp. 770-786, 1980.
[CrossRef] [Google Scholar] [Publisher Link]
[13] S.A. Mohamed, and M.M. Fahmy, “Binary Image Compression using Efficient Partitioning into Rectangular Regions,” IEEE Transactions on Communications, vol. 43, no. 5, pp. 1888- 1893, 1995.
[CrossRef] [Google Scholar] [Publisher Link]
[14] Nripendra N. Biswas, Logic Design Theory, Prentice-Hall, Inc, 1993.
[Google Scholar] [Publisher Link]
[15] Robert K. Brayton et al., Logic Minimization Algorithms for VLSI Synthesis, 1st ed., Springer, New York, 1984.
[CrossRef] [Google Scholar] [Publisher Link]
[16] Robert K. Brayton et al., “MIS: A Multiple-Level Logic Optimization System,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 6, no. 6, pp. 1062-1081, 1987.
[CrossRef] [Google Scholar] [Publisher Link]
[17] Randal E. Bryant, “Symbolic Boolean Manipulation with Ordered Binary-Decision Diagrams,” ACM Computing Surveys, vol. 24, no. 3, pp. 293-318, 1992.
[CrossRef] [Google Scholar] [Publisher Link]
[18] Heh-Tyan Liaw, and Chen-Shang Lin, “On the OBDD-Representation of General Boolean Functions,” IEEE Transactions on Computers, vol. 41, no. 6, pp. 661-664, 1992.
[CrossRef] [Google Scholar] [Publisher Link]
[19] Hanan Samet, “Data Structures for Quadtree Approximation and Compression,” Communications of the ACM, vol. 28, no. 9, pp. 973-993, 1985.
[CrossRef] [Google Scholar] [Publisher Link]
[20] S. Agaian, T. Baran, and K. Panetta, “The Application of Logical Transforms to Lossless Image Compression using Boolean Minimization,” Proceedings, GSPx and International Signal Processing Conference, pp. 13-31, 2003.
[Google Scholar] [Publisher Link]
[21] Jeehong Yang, Serap A. Savari, and Oskar Mencercv, “Lossless Compression using Two-Level and Multilevel Boolean Minimization,” IEEE Workshop on Signal Processing Systems Design and Implementation, Banff, AB, Canada, pp. 148-152, 2006.
[CrossRef] [Google Scholar] [Publisher Link]
[22] Mike Starkey, Randy Bryant, and Y. Bryant, “Using Ordered Binary Decision Diagrams for Compressing Images and Image Sequences,” Carnegie-Mellon University, Department of Computer Science, 1995.
[Google Scholar] [Publisher Link]
[23] P. Mateu-Villarroya, and J. Prades-Nebot, “Lossless Image Compression using Ordered Binary-Decision Diagrams,” Electronics Letters, vol. 37, no. 3, 2001.
[CrossRef] [Google Scholar] [Publisher Link]
[24] P. Mateu-Villarroya, and J. Prades-Nebot, “Sequential Logic Compression of Images,” Proceedings International Conference on Image Processing (Cat. No. 01CH37205), Thessaloniki, Greece, 2001.
[CrossRef] [Google Scholar] [Publisher Link]
[25] Luca Amarú et al., “Data Compression via Logic Synthesis,” 19th Asia and South Pacific Design Automation Conference, Singapore, vol. 207, pp. 628-633, 2014.
[CrossRef] [Google Scholar] [Publisher Link]
[26] Bogdan J. Falkowski, “Lossless Binary Image Compression using Logic Functions and Spectra,” Computers and Electrical Engineering, vol. 30, no. 1, pp. 17-43, 2004.
[CrossRef] [Google Scholar] [Publisher Link]
[27] Bogdan J. Falkowski, “Compact Representations of Logic Functions for Lossless Compression of Grey-Scale Images,” IEEE Proceedings Computers and Digital Techniques, vol. 151, no. 3, pp. 221- 230, 2004.
[CrossRef] [Google Scholar] [Publisher Link]
[28] X. Wu, and Nasir Memon, “Context-Based, Adaptive, Lossless Image Coding,” IEEE Transactions on Communications, vol. 45, no. 4, pp. 437-444, 1997.
[CrossRef] [Google Scholar] [Publisher Link]
[29] Behrouz Zolfaghari, Hamed Sheidaeian, and Saadat Pour Mozaffari, “Yalmic: Yet another Logic Minimization Based Image Compressor,” 2nd International Conference on Computer Engineering and Technology, Chengdu, China, vol. 44, pp. 90-95, 2010.
[CrossRef] [Google Scholar] [Publisher Link]
[30] Narendra Kumar, and Sachin Gupta, “Use of Local Minimization for Lossless Gray Image Compression,” International Journal of Computer Science and Information Technologies, vol. 1, no. 4, pp. 203-207, 2010.
[Google Scholar] [Publisher Link]
[31] Nasir Memon, and X. Wu, “Recent Developments in Context-Based Predictive Techniques for Lossless Image Compression,” The Computer Journal, vol. 40, no. 2 and 3, pp. 127-136, 1997.
[CrossRef] [Google Scholar] [Publisher Link]
[32] JPE Group, Jpeg Standard for Image Compression, 2024. [Online]. Available: https://jpeg.org/jpeg/ [33] Eyas El Qawasmeh, Pit Pichappan, and Arif Alfitiani, “Development and Investigation of a New Compression Technique using Boolean Minimizations,” 2nd International Conference on the Applications of Digital Information and Web Technologies, London, UK, pp. 505 511, 2009.
[CrossRef] [Google Scholar] [Publisher Link]