Analiza złożoności efektywnych metod predykcyjnych stosowanych do bezstratnej kompresji obrazów

• Autorzy: Ulacha G.

Warianty tytułu

EN

Complexity analysis of the effective predictive methods for lossless image compression

• Języki publikacji: PL

Abstrakty

PL

W artykule przedstawiono analizę adaptacyjnych metod modelowania predykcyjnego stosowanych do bezstratnej kompresji obrazów. Skupiono się głównie na najefektywniejszych metodach OLS, WLS, AVE-WLS, które dla każdego kodowanego piksela wymagają wyznaczenia macierzy i rozwiązania równania macierzowego. Metody te przeanalizowano pod kątem efektywności i złożoności obliczeniowej, porównując je także do metod o znacznie mniejszej złożoności, takich jak RLS. Omówiono też zaletę kaskadowego łączenia modelowania predykcyjnego z blokiem NLMS.

EN

In the paper, it is presented an analysis of adaptive predictive modelling methods applied to lossless image compression. We focus on the most effective methods: OLS, WLS, AVE-WLS. which for each encoded pixel require constructing a matrix and solving a matrix equation. These methods are analysed with respect to their effectiveness and computational complexity; they are also compared with the methods of considerably lower complexity, such as RLS. The benefits of cascade merging of predictive modelling with the NLMS block are also discussed.

Słowa kluczowe

PL

bezstratna kompresja obrazu; predykcja liniowa; entropia źródła; LMS; WLS

EN

lossless image compression; linear prediction; source entropy; LM; WLS

• Wydawca: Wydawnictwo SIGMA-NOT
• Czasopismo: Elektronika : konstrukcje, technologie, zastosowania
• Rocznik: 2012
• Tom: Vol. 53, nr 4
• Strony: 60--66
• Opis fizyczny: Bibliografia 30 poz., tab., wykr.

Twórcy

autor

Ulacha G.

• Zachodniopomorski Uniwersytet Technologiczny w Szczecinie, Wydział Informatyki

Bibliografia

• [1] Andriani S., Calvagno G., Erseghe T., Mian G. A., Durigon M., Rinaldo R., Knee M., Waliand P., Koppetz M.: Comparison of lossy to lossless compression techniques for digital cinema. Proceedings of International Conference on Image Processing ICIP'04, 24-27 Oct. 2004, vol. 1, pp. 513-516.
• [2] Kassim A. A., Pingkun Yan, Wei Siong Lee, Sengupta K.: Motion compensated lossy-to-lossless compression of 4-D medical images using integer wavelet transforms. IEEE Transactions on Information Technology in Biomedicine, March 2005, vol. 9, no. 1, pp. 132-138.
• [3] Sanchez V., Nasiopoulos P., Abugharbieh R.: Efficient 4D motion compensated lossless compression of dynamic volumetric medical image data. IEEE International Conference on Acoustics, Speech and Signal Processing ICASSP 2008, Las Vegas, Nevada, USA, 31 March - 4 April 2008, pp. 549-552.
• [4] Scharcanski J.: Lossless and Near-Lossless Compression for Mammographic Digital Images. Proceedings of International Conference on Image Processing ICIP'06, Atlanta, GA, USA, 8-11 October 2006, pp. 2253-2256.
• [5] Strom J., Cosman P.: Medical image compression with lossless regions of interest. Signal Processing, June 1997, vol. 59, no. 2, pp. 155-171.
• [6] Xiang Xie, GuoLin Li, ZhiHua Wang: A Near-Lossless Image Compression Algorithm Suitable for Hardware Design in Wireless Endoscopy System. EURASIP Journal on Advances in Signal Processing, vol. 2007, pp. 48-61.
• [7] Chen X. et al.: Lossless Compression for Space Imagery in a Dynamically Reconfigurable Architecture. Proc. of International Workshop on Applied Reconfigurable Computing (ARC2008), LNCS 4943, s. 336-341, March 2008.
• [8] Lossless Data Compression. Recommendation for Space Data System Standards. CCSDS 120.1-G-1. Green Book. Issue 1. Washington, D.C.: CCSDS, June 2007.
• [9] Sayood K.: Introduction to Data Compression. 2nd edition, Morgan Kaufmann Publ., San Francisco, 2002.
• [10] Ulacha G., Stasiński R.: Context based lossless coder based on RLS predictor adaptation scheme. Proceedings of International Conference on Image Processing ICIP 2009, 7-11 November, Egypt, Cairo 2009, pp. 1917-1920.
• [11] Ye H., Deng G., Devlin J. C.: Adaptive linear prediction for lossless coding of greyscale images, in Proc. IEEE Int. Conf. on Image Processing (CDROM), Vancouver, Canada, September 2000.
• [12] Ye H., Deng G., Devlin J. C.: Least squares approach for lossless image coding. Proceedings of the Fifth International Signal Processing and its Applications ISSPA'99, 22-25 August 1999, Queensland, Australia, pp. 63-66.
• [13] Drozdek A.: Elements of Data Compression. Brooks-Cole, July 2001.
• [14] Hsieh F.-Y., Wang C.-M., Lee C.-C., Fan K.-C.: A Lossless Image Coder Integrating Predictors and Block-Adaptive Prediction. Journal of Information Science and Engineering, September 2008, vol. 24, no. 5, pp. 1579-1591.
• [15] Meyer B., Tischer P.: GLICBAWLS - Grey Level Image Compression by Adaptive Weighted Least Squares. Proceedings of Data Compression Conference 2001, p. 503.
• [16] Jakhetiya V., Jaiswal S. P., Tiwari A. K.: A novel predictor coefficient interpolation approach for lossless compression of images. Instrumentation and Measurement Technology Conference, Binjiang, China, 10-12 May 2011, pp. 1-4.
• [17] Ye H., Deng G., Devlin J. C.: A weighted least squares method for adaptive prediction in lossless image compression, in Proc. Picture Coding Symposium, Saint-Malo, France, 2003, pp. 489-493.
• [18] Wu X., Zhai G., Yang X., Zhang W.: Adaptive Sequential Prediction of Multidimensional Signals With Applications to Lossless Image Coding. IEEE Trans. on Image Processing, 2011, vol. 20, no. 1, pp. 36-42.
• [19] Deng G., Ye H., Marusic S., Tay D.: A method for predictive order adaptation based on model averaging. Proceedings IEEE International Conference on Image Processing ICIP'03, 14-17 Sept. 2003, vol. 2, pp. 189-192.
• [20] Lee W. S.: Edge-adaptive prediction for lossless image coding. Proceedings of Data Compression Conference DCC'99, 29-31 March 1999, pp. 483-490.
• [21] Schuller G., Bin Yu; Dawei Huang: Lossless coding of audio signals using cascaded prediction. Proceedings of the IEEE International Conference on Acoustics, Speech, and Signal Processing 2001, Salt Lake City, Utah, USA, 2001, vol. 5, pp. 3273-3276.
• [22] Deng G.: Adaptive predictor combination for lossless image coding. Proceedings of 10th European Conference on Signal Processing EUSIPCO, Tampere, Finland, Sept. 2000, pp. 1141-1144.
• [23] Strutz T.: Context-Based Adaptive Linear Prediction for Lossless Image Coding. 4th International ITG Conference on Source and Channel Coding, Berlin, Germany, 28-30 January, 2002, pp. 105-109.
• [24] Marusic S., Deng G.: Adaptive prediction for lossless image compression. Signal Processing: Image Communications, May 2002, vol. 17, pp. 363-372.
• [25] Huang H., Fränti P., Huang D., Rahardja S.: Cascaded RLS-LMS prediction in MPEG-4 lossless audio coding. IEEE Trans. on Audio, Speech and Language Processing, March 2008, vol. 16, no. 3, pp. 554-562.
• [26] Ulacha G., Stasiński R.: A Time-Effective Lossless Coder Based on Hierarchical Contexts and Adaptive Predictors. Proceedings of 14th IEEE Mediterranean Electrotechnical Conference MELECON'08, Ajaccio, France, 5-7 May 2008, pp. 829-834.
• [27] Motta G., Storer J. A., Carpentieri B.: Iproving the performance of adaptive linear prediction coding (ALPC) via least square minimization. Proceedings of 12th International Workshop on Systems, Signals & Image Processing - IWSSIP 2005, Chalkida, Greece 2005, pp. 335-338.
• [28] Meyer B., Tischer P.: TMWlego - An Object Oriented Image Modelling Framework. Proceedings of Data Compression Conference 2001, p. 504.
• [29] Matsuda I., Ozaki N., Umezu Y., Itoh S.: Lossless coding using Variable Blok-Size adaptive prediction optimized for each image. Proceedings of 13th European Signal Processing Conference EUSIPCO-05 CD, September 2005.
• [30] WuX., Barthel K. U.: Piecewise2D autoregression for predictive image coding. Proceedings of International Conference on Image Processing ICIP'98, Chicago, USA, 4-7 Oct. 1998, vol. 3, pp. 901-904.