A new efficient predictor blending lossless image coder

Authors

  • Grzegorz Ulacha West Pomeranian University of Technology
  • Ryszard Stasinski Poznan University of Technology

Abstract

In the paper a highly efficient algorithm for lossless image coding is described. The algorithm is a predictor blending one, a sample estimate is computed as a weighted sum of estimates given by subpredictors, here 27 ones, hence the name Blend-2. Data compaction performance of Blend-27 is compared to that of numerous other lossless image coding algorithms, including the best currently existing ones. The compared methods are "classical" ones, as well as those based on Artificial Neural Networks. Performance of Blend-27 as a near-lossless coder is also evaluated. Its computational complexity is lower than that of majority of its direct competitors. The new algorithm appears to be currently the most efficient technique for lossless coding of natural images.

References

M.J. Weinberger, G. Seroussi, and G. Sapiro. The LOCO-I lossless

image compression algorithm: principles and standardization into JPEGLS.

IEEE Transactions on Image Processing, 9(8):1309–1324, 2000.

M.W. Marcellin, M.J. Gormish, A. Bilgin, and M.P. Boliek. An

overview of JPEG-2000. In Proceedings DCC 2000. Data Compression

Conference, pages 523–541, 2000.

CodecWebP 1.3. https://storage.googleapis.com/downloads.webmproject.org

/releases/webp/libwebp-1.3.0-windows-x64.zip, loaded 2023-04-08.

Xiaolin Wu and N. Memon. CALIC - a context based adaptive lossless

image codec. In 1996 IEEE International Conference on Acoustics,

Speech, and Signal Processing Conference Proceedings, volume 4, pages

–1893 vol. 4, 1996.

B. Meyer and P. Tischer. TMW – a new method for lossless image

compression. In Proceedings of International Picture Coding Symposium

(PCS97), pages 533–538, 1997.

B. Meyer and P. Tischer. TMWLego - an object oriented image modeling

framework. In Proceedings of Data Compression Conference, page 504,

H. Ye, G. Deng, and J.C. Devlin. A weighted least squares method for

adaptive prediction in lossless image compression. In Picture Coding

Symp. PCS’03, pages 489–493, 2003.

I. Matsuda, N. Ozaki, Y. Umezu, and S. Itoh. Lossless coding using

variable blok-size adaptive prediction optimized for each image. In

Proceedings of 13th European Signal Processing Conference EUSIPCO-

CD, 2005.

F.-Y. Hsieh, C.-M. Wang, C.-C. Lee, and K.-C. Fan. A lossless image

coder integrating predictors and block-adaptive prediction. Journal of

Information Science and Engineering, 24(5):1579–1591, 2008.

X. Wu, G. Zhai, X. Yang, and W. Zhang. Adaptive sequential prediction

of multidimensional signals with applications to lossless image coding.

IEEE Trans. on Image Proces., 20(1):36–42, 2011.

W. Dai and H. Xiong. Gaussian process regression based prediction for

lossless image coding. In Proceedings of Data Compression Conference,

pages 93–102, 2014.

Wenrui Dai, Hongkai Xiong, Jia Wang, and Y.F. Zheng. Large discriminative

structured set prediction modeling with max-margin markov

network for lossless image coding. IEEE Transactions on Image

Processing, 23(2):541–554, 2014.

I. Matsuda, N. Ozaki, Y. Umezu, and S. Itoh. A lossless image coding

method based on probability model optimization. In 36th Int. Conf.

Acoustics, Speech and Signal Proces. ICASSP’11, pages 156–160, 2018.

K. Unno, Y. Kameda, I. Matsuda, S. Itoh, and S. Naito. Lossless

image coding exploiting local and non-local information via probability

model optimization. In 27th European Signal Processing Conference

(EUSIPCO), pages 1–5, 2019.

H. Kojima et al. Improved probability modeling for lossless image

coding using example search and adaptive prediction. In IWAIT2022,

Grzegorz Ulacha, Ryszard Stasinski, and Cezary Wernik. Extended multi

WLS method for lossless image coding. Entropy, 22(9), 2020.

Tilo Strutz. Context-based adaptive linear prediction for lossless image

coding. In Proceedings of the 4th International ITG Conference on

Source and Channel Coding, pages 105–109, Berlin, Germany, jan 2002.

B. Meyer and P. Tischer. GLICBAWLS - grey level image compression

by adaptive weighted least squares. In Proceedings of Data Compression

Conference, page 503, 2000.

L.-J Kau, Yuan-Pei Lin, and C.-T Lin. Lossless image coding using

adaptive, switching algorithm with automatic fuzzy context modelling.

Vision, Image and Signal Processing, IEE Proceedings -, 153:684 – 694,

2006.

G. Ulacha and R. Stasi´nski. Performance optimized predictor blending

technique for lossless image coding. In 36th Int. Conf. Acoustics, Speech

and Signal Proces. ICASSP’11, pages 1541–1544, 2011.

S. Marusic and G. Deng. A neural network based adaptive non-linear

lossless predictive coding technique. In ISSPA ’99. Proceedings of the

Fifth International Symposium on Signal Processing and its Applications

(IEEE Cat. No.99EX359), volume 2, pages 653–656 vol.2, 1999.

Slaven Marusic and Guang Deng. Adaptive prediction for lossless image

compression. Signal Processing: Image Communication, 17(5):363–372,

Keisuke Takizawa, Seiya Takenouchi, Hisashi Aomori, Tsuyoshi Otake,

Mamoru Tanaka, Ichiro Matsuda, and Susumu Itoh. Lossless image

coding by cellular neural networks with minimum coding rate learning.

In 2011 20th European Conference on Circuit Theory and Design

(ECCTD), pages 33–36, 2011.

G. Ulacha and R. Stasi´nski. Improving neural network approach to

lossless image coding. In Proceedings of The 29th Picture Coding

Symposium PCS’12, pages 173–176, 2012.

T. Salimans, A. Karpathy, X. Chen, and D. P. Kingma. Improving

the PixelCNN with discretized logistic mixture likelihood and other

modifications. In Proc. 5th International Conference on Learning

Representations (ICLR 2017), 2017.

Hiroki Kojima, Yusuke Kameda, Yasuyo Kita, Ichiro Matsuda, and

Susumu Itoh. Probability model adjustment for the CNN-based lossless

image coding method. In Proc. SPIE 11766, International Workshop on

Advanced Imaging Technology (IWAIT) 2021, 2021

S. Zhang, C. Zhang, N. Kang, and Z. Li. iVPF: Numerical invertible

volume preserving flow for efficient lossless compression. In 2021

IEEE/CVF Conference on Computer Vision and Pattern Recognition

(CVPR), pages 1–10, 2021.

Yuanchao Bai, Xianming Liu, Kai Wang, Xiangyang Ji, Xiaolin Wu,

and Wen Gao. Deep lossy plus residual coding for lossless and nearlossless

image compression. arXiv - CS - Computer Vision and Pattern

Recognition, 2022.

Grzegorz Ulacha and Ryszard Stasinski. High performance predictor

blending lossless image coder. In Data Compression Conference 2023

(DCC), page 366, 2023.

H. Hartenstein, R. Herz, and D. Saupe. A comparative study of L1-

distortion limited image compression algorithms. In Proceedings of

International Conference on Image Processing ICIP’03, pages 1–5,

R. Iordache, I. Tabus, and J. Astola. Fixed-slope near-lossless contextbased

image compression. In Proceedings of 1998 International Conference

on Image Processing, volume 1, pages 512–515, 1998.

A. Krivoulets. A method for progressive near-lossless image compression.

In Proceedings of Picture Coding Symposium, volume 2, pages

–188, 1997.

Xiang Xie, GuoLin Li, DongMei Li, Chun Zhang, and Zhi Hua Wang.

A new near-lossless image compression algorithm suitable for hardware

design in wireless endoscopy system. In IEEE International Conference

on Image Processing 2005, volume 1, pages I–1125, 2005.

Xiaohui Xue. Prediction based on backward adaptive recognition of local

texture orientation and poisson statistical model for lossless/near-lossless

image compression. In Proceedings of IEEE International Conference

on Acoustics, Speech, and Signal Processing, volume 6, pages 3137–

, 1999.

Jacob Str¨om and Pamela C. Cosman. Medical image compression with

lossless regions of interest. Signal Processing, 59(2):155–171, 1997.

Biomedical Imaging.

Y. Kuroki, Y. Ueshige, and T. Ohta. An estimation of the predictors

implemented by shift operation, addition, and/or substraction. In

Proceedings of International Conference on Image Processing 2001,

pages 474–477, 2001.

Khalid Sayood, editor. Introduction to Data Compression. Morgan

Kaufmann, 5th edition, 2018.

Jianmin Jiang and Christos Grecos. Towards an improvement on

prediction accuracy in JPEG-LS. Optical Engineering, 41(2):335 – 341,

Huiyuan Wang and David Zhang. A linear edge model and its application

in lossless image coding. Signal Processing: Image Communication,

(10):955–958, 2004.

G Ulacha and R. Stasinski. On context-based predictive techniques

for lossless image compression. IWSSIP 2005 - Proceedings of 12th

International Workshop on Systems, Signals and Image Processing,

pages 345–348, 11 2005.

Aleksej Avramovi´c. Lossless compression of medical images based

on gradient edge detection. In 2011 19thTelecommunications Forum

(TELFOR) Proceedings of Papers, pages 1199–1202, 2011.

A. Attar, R. M. Rad, and A. Shahbahrami. An accurate gradient-based

predictive algorithm for image compression. In MoMM ’10: Proceedings

of the 8th International Conference on Advances in Mobile Computing

and Multimedia, page 374–377, 2010.

C.-C Chang and G.-I Chen. Enhancement algorithm for nonlinear

context-based predictors. Vision, Image and Signal Processing, IEE

Proceedings -, 150:15–19, 03 2003.

Amir Seyed Danesh, Reza Moradi Rad, and Abdolrahman Attar. A

novel predictor function for lossless image compression. In 2010 2nd

International Conference on Advanced Computer Control, volume 2,

pages 527–531, 2010.

D.D. Estrakh, H.B. Mitchell, P.A. Schaefer, Y. Mann, and Y. Peretz.

“Soft” median adaptive predictor for lossless picture compression. Signal

Processing, 81(9):1985–1989, 2001.

Abdul Itani and Manohar Das. Adaptive switching linear predictor for

lossless image compression. In George Bebis, Richard Boyle, Darko

Koracin, and Bahram Parvin, editors, Advances in Visual Computing,

pages 718–722, Berlin, Heidelberg, 2005. Springer Berlin Heidelberg.

Nader Karimi, Shadrokh Samavi, and Shahram Shirani. Lossless

compression of high-throughput RNAi images. In Proceedings of the

th IEEE International Conference on Information Technology and

Applications in Biomedicine, pages 1–4, 2010.

Cihan Topal and O¨ mer Nezih Gerek. Pdf sharpening for multichannel

predictive coders. In 2006 14th European Signal Processing Conference,

pages 1–4, 2006.

Grzegorz Ulacha and Ryszard Stasinski. A new fast multi-context

method for lossless image coding. In Proceedings of the 2018 International

Conference on Sensors, Signal and Image Processing, SSIP 2018,

page 69–72, New York, NY, USA, 2018. Association for Computing

Machinery.

N. D. Memon and K. Sayood. An asymmetric lossless image compression

technique. In Proceedings of the 1995 International Conference on

Image Processing, volume 3, pages 97–100, 1995.

F. Golchin and K. K. Paliwal. Classified adaptive prediction and entropy

coding for lossless coding of images. In Proceedings of International

Conference on Image Processing, pages 110–113, 1997.

B. Aiazzi, S. Baronti, and L. Alparone. Near-lossless image compression

by relaxation-labeled prediction. Signal Processing, 82(11):1619–1631,

Mehrdad Salami, Masaya Iwata, and Tetsuya Higuchi. Lossless image

compression by evolvable hardware. In Fourth European Conference on

Artificial Life, pages 407–416, Brighton, UK, 1997.

Seishi Takamura, Masaaki Matsumura, and Yoshiyuki Yashima. A study

on an evolutionary pixel predictor and its properties. In Proceedings of

the 16th IEEE International Conference on Image Processing, ICIP’09,

page 1901–1904. IEEE Press, 2009.

Yung-Gi Wu. Differential pulse code modulation predictor design

procedure using a genetic algorithm. Optical Engineering, 42(6):1649

– 1655, 2003.

Yoshihiko Hashidume and Yoshitaka Morikawa. Lossless image coding

based on minimum mean absolute error predictors. In SICE Annual

Conference 2007, pages 2832–2836, 2007.

G. Ulacha and M. Łazoryszczak. Lossless image coding using nonmmse

algorithms to calculate linear prediction coefficients. Entropy,

(1):1–19, 2023.

N.V. Boulgouris, S. Zaharos, and M.G. Strintzis. Adaptive decorrelation

and entropy coding for context-based lossless image compression. In

st Balkan Conference on Signal Processing, Communications, Circuits,

and Systems. Istanbul, Turkey, 2000.

T. Strutz. Context-based predictor blending for lossless colour image

compression. IEEE Transactions on Circuits and Systems for Video

Technology, 26(4):687–695, 2016.

G. Ulacha and R. Stasi´nski. A time-effective lossless coder based on hierarchical

contexts and adaptive predictors. In 14th IEEE Mediterranean

Electrotech. Conf. MELECON’08, pages 829–834, 2008.

G. Ulacha and R. Stasi´nski. New context-based adaptive linear prediction

algorithm for lossless image coding. In Proceedings of Int. Conf.

on Signals and Electronic Systems (ICSES’14), pages 1–4, 2014.

Grzegorz Ulacha and Ryszard Stasinski. Context based lossless coder

based on rls predictor adaption scheme. In 2009 16th IEEE International

Conference on Image Processing (ICIP), pages 1917–1920, 2009.

Xiaolin Wu, E.U. Barthel, and Wenhan Zhang. Piecewise 2D autoregression

for predictive image coding. In Proceedings 1998 International

Conference on Image Processing. ICIP98 (Cat. No.98CB36269), pages

–904 vol.3, 1998.

H. Ye, G. Deng, and J.C. Devlin. Adaptive linear prediction for

lossless coding of greyscale images. In Proceedings 2000 International

Conference on Image Processing (Cat. No.00CH37101), volume 1,

pages 128–131 vol.1, 2000.

H. Ye, G. Deng, and J.C. Devlin. Least squares approach for lossless

image coding. In ISSPA ’99. Proceedings of the Fifth International

Symposium on Signal Processing and its Applications (IEEE Cat.

No.99EX359), volume 1, pages 63–66 vol.1, 1999.

F. Mentzer, L. van Gool, and M. Tschannen. Learning better lossless

compression using lossy compression. In 2020 IEEE/CVF Conference

on Computer Vision and Pattern Recognition (CVPR), pages 6637–6646,

Hochang Rhee, Yeong Il Jang, Seyun Kim, and Nam Ik Cho. LC-FDNet:

Learned lossless image compression with frequency decomposition

network. In 2022 IEEE/CVF Conference on Computer Vision and

Pattern Recognition (CVPR), pages 6023–6032, 2022.

H. Rhee, Y. I. Jang, S. Kim, and N. I. Cho. Lossless image compression

by joint prediction of pixel and context using duplex neural networks.

IEEE Access, 9:86632–86645, 2021.

Emiel Hoogeboom, Jorn W.T. Peters, Rianne van den Berg, and Max

Welling. Integer discrete flows and lossless compression. In Conference

on Neural Information Processing Systems (2019), 2019.

H. Huang, P. Fr¨anti, D. Huang, and S. Rahardja. Cascaded RLS-LMS

prediction in MPEG-4 lossless audio coding. IEEE Trans. on Audio,

Speech and Language Proces., 16(3):554–562, 2008.

Guang Deng. Transform domain LMS-based adaptive prediction for

lossless image coding. Signal Processing: Image Communication,

(2):219–229, 2002.

Torsten Seemann and Peter Tischer. Generalized locally adaptive DPCM.

Department of Computer Science Technical Report CS97/301, pages 1–

, 1997.

L.-J. Kau and Y.-P. Lin. Lossless image coding using a switching

predictor with run-length encodings. In IEEE Int. Conf. on Multimedia

and Expo, pages 1155–1158, 2004.

G. Ulacha and R. Stasi´nski. Highly effective predictor blending method

for lossless image coding. In 15th IEEE Mediterranean Electrotech.

Conf. MELECON’10, pages 1099–1104, 2010.

G. Ulacha and R. Stasi´nski. Enhanced lossless image coding methods

based on adaptive predictors. In Int. Conf. on Systems, Signals and

Image Proces. IWSSIP 2010, pages 312–315, 2010.

W. S. Lee. Edge-adaptive prediction for lossless image coding. In Data

Compression Conf. DCC’99, pages 483–490, 1999.

G. Ulacha and R. Stasi´nski. Improved predictor blending technique for

lossless image coding. In Int. Conf. on Signals and Electronic Systems

ICSES’10, pages 115–118, 2010.

G. Schuller, Bin Yu, and Dawei Huang. Lossless coding of audio

signals using cascaded prediction. In Proceedings of IEEE International

Conference on Acoustics, Speech, and Signal Processing, volume 5,

pages 3273–3276, 2001.

J. Knezovic and M. Kovac. Gradient based selective weighting of neighboring

pixels for predictive lossless image coding. In Proceedings of

the 25th International Conference on Information Technology Interfaces,

ITI 2003., pages 483–488, 2003.

G. Ulacha and R. Stasi´nski. Texture matching method for lossless image

coding. In International Conference on Systems, Signals and Image

Processing IWSSIP’07, pages 135–138, 2007.

B. Meyer and P. Tischer. Extending TMW for near lossless compression

of greyscale images. In Proceedings of Data Compression Conference

, pages 458–470, 1998.

Khalid Sayood. Lossless Compression Handbook. Communications,

Networking and Multimedia. Elsevier Science, 2002.

Torsten Seemann, Peter Tischer, and Bernd Meyer. History-based

blending of image sub-predictors. In Proc. Picture Coding Symposium,

pages 147–151, 1997.

G. Motta, J. A. Storer, and B. Carpentieri. Improving the performance of

adaptive linear prediction coding (ALPC) via least square minimization.

In Proceedings of 12th International Workshop on Systems, Signals and

Image Processing - IWSSIP 2005, pages 335–338, 2005.

A. Martchenko and G. Deng. Bayesian predictor combination for

lossless image compression. IEEE Transactions on Image Processing,

(12):5263–5270, 2013.

A. Weinlich, P. Amon, A. Hutter, and A. Kaup. Probability distribution

estimation for autoregressive pixel-predictive image coding. IEEE

Transactions on Image Processing, 25(3):1382–1395, 2016.

Additional Files

Published

2024-07-18

Issue

Section

Image Processing