Evolution and Advancement of Arithmetic Coding over Four Decades
DOI:
https://doi.org/10.31580/ojst.v3i3.1664Keywords:
Arithmetic Coding, Adaptive Arithmetic Coding, Data Compression, Entropy, Huffman Coding, Lossless CompressionAbstract
Arithmetic Coding (AC) is a form of entropy encoding used in lossless data compression. It is a well-known, state of the art technique, in which the frequently seen symbols are encoded with fewer bits than rarely seen symbols. It has been widely used since last four decades. Many researchers worked on it to improve its performance and they successfully experimented with it. This technique has also been in use in combination with other techniques to gain surprising results. In this survey paper, an effort is made to recap a number of accomplishments from 1976 to 2017 regarding Arithmetic Coding. This study provides an insight for new researchers to know how this technique evolved with time and how major achievements were made using this technique. This paper gives a comparison of AC with another well-known technique named Huffman Coding. Comparison with its contemporary counterparts shows that it is better in performance almost in every situation.
References
Rissanen JJ. Generalized Kraft inequality and arithmetic coding. IBM Journal of research and development. 1976;20(3):198-203.
Pasco RC. Source coding algorithms for fast data compression: Stanford University CA; 1976.
Rissanen J, Langdon GG. Arithmetic coding. IBM Journal of research and development. 1979;23(2):149-62.
Langdon GG. An introduction to arithmetic coding. IBM Journal of Research and Development. 1984;28(2):135-49.
Seabrook G, editor Arithmetic coding-an alternative VLC strategy for video coding. Third International Conference on Image Processing and its Applications, 1989; 1989: IET.
Ghanbari M. Arithmetic coding with limited past history. Electronics letters. 1991;27(13):1157-9.
Howard PG, Vitter JS, editors. Parallel lossless image compression using Huffman and arithmetic coding. Data Compression Conference, 1992; 1992: IEEE.
Tong P, Ang P, editors. A JBIG arithmetic coder-decoder chip. [1992] Proceedings Fifth Annual IEEE International ASIC Conference and Exhibit; 1992: IEEE.
Pennebaker WB, Mitchell JL, Langdon GG, Arps RB. An overview of the basic principles of the Q-coder adaptive binary arithmetic coder. IBM Journal of research and development. 1988;32(6):717-26 %@ 0018-8646.
Howard PG, Vitter JS. Practical implementations of arithmetic coding. Image and text compression: Springer; 1992. p. 85-112.
Howard PG, Vitter JS. Arithmetic coding for data compression. Proceedings of the IEEE. 1994;82(6):857-65.
Fu B, Parhi KK, editors. Generalized multiplication free arithmetic codes. Proceedings of ISCAS'95-International Symposium on Circuits and Systems; 1995: IEEE.
Fu B, Parhi KK. Generalized multiplication-free arithmetic codes. IEEE transactions on communications. 1997;45(5):497-501.
Peon M, Osorio RR, Bruguera JD, editors. A VLSI implementation of an arithmetic coder for image compression. EUROMICRO 97 Proceedings of the 23rd EUROMICRO Conference: New Frontiers of Information Technology (Cat No 97TB100167); 1997: IEEE.
Jou JM, Chen P-Y, editors. An adaptive arithmetic coding method using fuzzy logic and Gray theory. ISCAS'98 Proceedings of the 1998 IEEE International Symposium on Circuits and Systems (Cat No 98CH36187); 1998: IEEE.
Zhu B, Yang E-h, Tewfik AH. Arithmetic coding with dual symbol sets and its performance analysis. IEEE transactions on Image Processing. 1999;8(12):1667-76.
Gong D, He Y, editors. An efficient architecture for real-time content-based arithmetic coding. 2000 IEEE International Symposium on Circuits and Systems Emerging Technologies for the 21st Century Proceedings (IEEE Cat No 00CH36353); 2000: IEEE.
Triantafyllidis GA, Strintzis MG, editors. A least squares algorithm for efficient context-based adaptive arithmetic coding. ISCAS 2001 The 2001 IEEE International Symposium on Circuits and Systems (Cat No 01CH37196); 2001: IEEE.
Guionnet T, Guillemot C, editors. Robust decoding of arithmetic codes for image transmission over error-prone channels. Proceedings 2003 International Conference on Image Processing (Cat No 03CH37429); 2003: IEEE.
Mahapatra S, Singh K, editors. A parallel scheme for implementing multialphabet arithmetic coding in high-speed programmable hardware. International Conference on Information Technology: Coding and Computing (ITCC'05)-Volume II; 2005: IEEE.
Hong D, Eleftheriadis A, editors. Memory-efficient semi-quasi-arithmetic coding. IEEE International Conference on Image Processing 2005; 2005: IEEE.
Belyaev E, Gilmutdinov M, Turlikov A, editors. Binary Arithmetic Coding System with Adaptive Probability Estimation by" Virtual Sliding Window". 2006 IEEE International Symposium on Consumer Electronics; 2006: IEEE.
Kim H, Wen J, Villasenor JD. Secure arithmetic coding. IEEE Transactions on Signal processing. 2007;55(5):2263-72.
Apparaju R, Agarwal S, editors. An arithmetic coding scheme by converting the multisymbol alphabet to m-ary alphabet. International Conference on Computational Intelligence and Multimedia Applications (ICCIMA 2007); 2007: IEEE.
Ezhilarasan M, Thambidurai P, Praveena K, Srinivasan S, Sumathi N, editors. A new entropy encoding technique for multimedia data compression. International Conference on Computational Intelligence and Multimedia Applications (ICCIMA 2007); 2007: IEEE.
Coq G, Olivier C, Alata O, Arnaudon M, editors. Information criteria and arithmetic codings: an illustration on raw images. 2007 15th European Signal Processing Conference; 2007: IEEE.
Wu J, Wang M, Jeong J, Jiao L, editors. Adaptive-distributed arithmetic coding for lossless compression. 2010 2nd IEEE InternationalConference on Network Infrastructure and Digital Content; 2010: IEEE.
Xu D-l, Yan C, editors. Application research of Arithmetic Coding. The 2nd International Conference on Information Science and Engineering; 2010: IEEE.
Wensong L, En Z, Ye L, Lei S, Jun L, editors. Design of JPEG2000 arithmetic coder using optimized renormalization procedure. 2011 International Conference on Multimedia and Signal Processing; 2011: IEEE.
Huang Y-M, Liang Y-C, editors. A secure arithmetic coding algorithm based on integer implementation. 2011 11th International Symposium on Communications & Information Technologies (ISCIT); 2011: IEEE.
Singh R, Srivastava V, editors. Performance comparison of arithmetic and huffman coder applied to ezw codec. 2012 2nd International Conference on Power, Control and Embedded Systems; 2012: IEEE.
Doshi J, Gandhi S, editors. Enhanced arithmetic coding using total frequency in power of 2 & processing multi-bits at a time. 2013 Sixth International Conference on Contemporary Computing (IC3); 2013: IEEE.
Bartrina-Rapesta J, Blanes I, Aulí-Llinàs F, Serra-Sagristà J, Sanchez V, Marcellin MW. A lightweight contextual arithmetic coder for on-board remote sensing data compression. IEEE Transactions on Geoscience and Remote Sensing. 2017;55(8):4825-35.
Ding J-J, Wang I-H, Chen H-Y. Improved efficiency on adaptive arithmetic coding for data compression using range-adjusting scheme, increasingly adjusting step, and mutual-learning scheme. IEEE Transactions on Circuits and Systems for Video Technology. 2018;28(12):3412-23.
Vincent J, editor Application of arithmetic coding to Laplacian pyramid coding. Third International Conference on Image Processing and its Applications, 1989; 1989: IET.
Martucci SA, editor Reversible compression of HDTV images using median adaptive prediction and arithmetic coding. IEEE international symposium on circuits and systems; 1990: IEEE.
Howard PG, Vitter JS. New methods for lossless image compression using arithmetic coding. Information processing & management. 1992;28(6):765-79.
Takamura S, Takagi M, editors. Lossless image compression with lossy image using adaptive prediction and arithmetic coding. Proceedings of IEEE Data Compression Conference (DCC'94); 1994: IEEE.
Mandyam G, Ahmed N, Stearns SD, editors. A two-stage scheme for lossless compression of images. Proceedings of ISCAS'95-International Symposium on Circuits and Systems; 1995: IEEE.
Muller F, Illgner K, Menser B, editors. Embedded Laplacian pyramid image coding using conditional arithmetic coding. Proceedings of 3rd IEEE International Conference on Image Processing; 1996: IEEE.
Labelle L, Lauzon D, Konrad J, Dubois E, editors. Arithmetic coding of a lossless contour based representation of label images. Proceedings 1998 International Conference on Image Processing ICIP98 (Cat No 98CB36269); 1998: IEEE.
Frydrych M, Toivanen P. Arithmetic coding with sliding window for control-point based image compression. 1999.
You K-S, Han D-S, Jang ES, Jang S-Y, Lee S-K, Kwak H-S, editors. Ranked image generation for arithmetic coding in indexed color image. Proceedings of 7th International Workshop on Enterprise networking and Computing in Healthcare Industry, 2005 HEALTHCOM 2005; 2005: IEEE.
Islam MR, Baki A-A, Palash MSH, editors. A new image compression scheme using repeat reduction and arithmetic coding. 2009 12th International Conference on Computers and Information Technology; 2009: IEEE.
Pande A, Zambreno J, Mohapatra P, editors. Joint video compression and encryption using arithmetic coding and chaos. 2010 IEEE 4th International Conference on Internet Multimedia Services Architecture and Application; 2010: IEEE.
Vermeirsch K, Barbarien J, Lambert P, Van de Walle R, editors. Region-adaptive probability model selection for the arithmetic coding of video texture. 2011 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP); 2011: IEEE.
Chuang C-P, Chen G-X, Liao Y-T, Lin C-C, editors. A lossless color image compression algorithm with adaptive arithmetic coding based on adjacent data probability. 2012 International Symposium on Computer, Consumer and Control; 2012: IEEE.
Masmoudi A, Masmoudi A, Puech W, editors. An efficient adaptive arithmetic coding for block-based lossless image compression using mixture models. 2014 IEEE International Conference on Image Processing (ICIP); 2014: IEEE.
Liu Y-R, Kau L-J, editors. Scalable face image compression based on Principal Component Analysis and arithmetic Coding. 2017 IEEE International Conference on Consumer Electronics-Taiwan (ICCE-TW); 2017: IEEE.
Passariello G, Gavidia L, Rodriguez F, Condado J, Ruesta V, Roux C, et al., editors. Arithmetic coding for ECG data compression. [1991] Proceedings Computers in Cardiology; 1991: IEEE.
Jiang W, Kiang S-Z, Hakim N, Meadows H, editors. Lossless compression for medical imaging systems using linear/nonlinear prediction and arithmetic coding. 1993 IEEE International Symposium on Circuits and Systems; 1993: IEEE.
Chen K, Ramabadran TV. Near-lossless compression of medical images through entropy-coded DPCM. IEEE Transactions on Medical Imaging. 1994;13(3):538-48.
Abu-Hajar A, Sankar R, editors. Wavelet based lossless image compression using partial SPIHT and bit plane based arithmetic coding. 2002 IEEE International Conference on Acoustics, Speech, and Signal Processing; 2002: IEEE.
Chikouche D, Benzid R, Bentoumi M, editors. Application of the DCT and arithmetic coding to medical image compression. 2008 3rd International Conference on Information and Communication Technologies: From Theory to Applications; 2008: IEEE.
Wenna L, Yang G, Yufeng Y, Liqun G, editors. Medical image coding based on wavelet transform and distributed arithmetic coding. 2011 Chinese Control and Decision Conference (CCDC); 2011: IEEE.
Weinlich A, Rehm J, Amon P, Hutter A, Kaup A, editors. Massively parallel lossless compression of medical images using least-squares prediction and arithmetic coding. 2013 IEEE International Conference on Image Processing; 2013: IEEE.
Zishan Y, editor Arithmetic coding data compression codec for newspaper facsimile. Proceedings of TENCON'93 IEEE Region 10 International Conference on Computers, Communications and Automation; 1993: IEEE.
Kozintsev I, Chou J, Ramchandran K, editors. Image transmission using arithmetic coding based continuous error detection. Proceedings DCC'98 Data Compression Conference (Cat No 98TB100225); 1998: IEEE.
Chou J, Ramchandran K. Arithmetic coding-based continuous error detection for efficient ARQ-based image transmission. IEEE Journal on Selected Areas in Communications. 2000;18(6):861-7.
Sodagar I, Chai B-B, Wus J, editors. A new error resilience technique for image compression using arithmetic coding. 2000 IEEE International Conference on Acoustics, Speech, and Signal Processing Proceedings (Cat No 00CH37100); 2000: IEEE.
Kim J-K, Yang KH, Lee CW. Binary subband decomposition and concatenated arithmetic coding. IEEE transactions on circuits and systems for video technology. 2000;10(7):1059-67.
Demiroglu C, Hoffman MW, Sayood K, editors. Joint source channel coding using arithmetic codes and trellis coded modulation. Proceedings DCC 2001 Data Compression Conference; 2001: IEEE.
Cheng Z-Q, Li B, Xu K, Wang Y-Z, Dang G, Jin S-Y, editors. An Error-Resilient Arithmetic Coding Algorithm for Compressed Meshes. 2008 International Conference on Cyberworlds; 2008: IEEE.
Zribi A, Zaibi S, Pyndiah R, Bouallegue A, editors. Chase-like decoding of arithmetic codes with image transmission applications. 2009 Fifth International Conference on Signal Image Technology and Internet Based Systems; 2009: IEEE.
Gomathymeenakshi M, Sruti S, Karthikeyan B, Nayana M, editors. An efficient arithmetic coding data compression with steganography. 2013 IEEE International Conference ON Emerging Trends in Computing, Communication and Nanotechnology (ICECCN); 2013: IEEE.
El-Arsh HY, Mohasseb YZ, editors. A new light-weight jpeg2000 encryption technique based on arithmetic coding. MILCOM 2013-2013 IEEE Military Communications Conference; 2013: IEEE.
