Image compression is a type of data compression applied to digital images, to reduce their cost for storage or transmission. Algorithms may take advantage of visual perception and the statistical properties of image data to provide superior results compared with generic data compression methods which are used for other digital data.
Lossy and lossless image compression
Image compression may be lossy or lossless. Lossless compression is preferred for archival purposes and often for medical imaging, technical drawings, clip art, or comics. Lossy compression methods, especially when used at low bit rates, introduce compression artifacts. Lossy methods are especially suitable for natural images such as photographs in applications where minor (sometimes imperceptible) loss of fidelity is acceptable to achieve a substantial reduction in bit rate. Lossy compression that produces negligible differences may be called visually lossless.
Methods for lossy compression:
- Transform coding – This is the most commonly used method.
- Discrete Cosine Transform (DCT) – The most widely used form of lossy compression. It is a type of Fourier-related transform, and was originally developed by Nasir Ahmed, T. Natarajan and K. R. Rao in 1974. The DCT is sometimes referred to as "DCT-II" in the context of a family of discrete cosine transforms (see discrete cosine transform). It is generally the most efficient form of image compression.
- The more recently developed wavelet transform is also used extensively, followed by quantization and entropy coding.
- Reducing the color space to the most common colors in the image. The selected colors are specified in the colour palette in the header of the compressed image. Each pixel just references the index of a color in the color palette, this method can be combined with dithering to avoid posterization.
- Chroma subsampling. This takes advantage of the fact that the human eye perceives spatial changes of brightness more sharply than those of color, by averaging or dropping some of the chrominance information in the image.
- Fractal compression.
Methods for lossless compression:
- Run-length encoding – used in default method in PCX and as one of possible in BMP, TGA, TIFF
- Area image compression
- Predictive coding – used in DPCM
- Entropy encoding – the two most common entropy encoding techniques are arithmetic coding and Huffman coding
- Adaptive dictionary algorithms such as LZW – used in GIF and TIFF
- DEFLATE – used in PNG, MNG, and TIFF
- Chain codes
The best image quality at a given compression rate (or bit rate) is the main goal of image compression, however, there are other important properties of image compression schemes:
Scalability generally refers to a quality reduction achieved by manipulation of the bitstream or file (without decompression and re-compression). Other names for scalability are progressive coding or embedded bitstreams. Despite its contrary nature, scalability also may be found in lossless codecs, usually in form of coarse-to-fine pixel scans. Scalability is especially useful for previewing images while downloading them (e.g., in a web browser) or for providing variable quality access to e.g., databases. There are several types of scalability:
- Quality progressive or layer progressive: The bitstream successively refines the reconstructed image.
- Resolution progressive: First encode a lower image resolution; then encode the difference to higher resolutions.
- Component progressive: First encode grey-scale version; then adding full color.
Region of interest coding. Certain parts of the image are encoded with higher quality than others. This may be combined with scalability (encode these parts first, others later).
Meta information. Compressed data may contain information about the image which may be used to categorize, search, or browse images. Such information may include color and texture statistics, small preview images, and author or copyright information.
Processing power. Compression algorithms require different amounts of processing power to encode and decode. Some high compression algorithms require high processing power.
The quality of a compression method often is measured by the peak signal-to-noise ratio. It measures the amount of noise introduced through a lossy compression of the image, however, the subjective judgment of the viewer also is regarded as an important measure, perhaps, being the most important measure.
Entropy coding started in the 1940s with the introduction of Shannon–Fano coding, the basis for Huffman coding which was developed in 1950. Transform coding dates back to the late 1960s, with the introduction of fast Fourier transform (FFT) coding in 1968 and the Hadamard transform in 1969.
An important development in image data compression was the discrete cosine transform (DCT), a lossy compression technique first proposed by Nasir Ahmed in 1972. DCT compression became the basis for JPEG, which was introduced by the Joint Photographic Experts Group (JPEG) in 1992. JPEG compresses images down to much smaller file sizes, and has become the most widely used image file format. Its highly efficient DCT compression algorithm was largely responsible for the wide proliferation of digital images and digital photos, with several billion JPEG images produced every day as of 2015.
Lempel–Ziv–Welch (LZW) is a lossless compression algorithm developed by Abraham Lempel, Jacob Ziv and Terry Welch in 1984. It is used in the GIF format, introduced in 1987. DEFLATE, a lossless compression algorithm developed by Phil Katz and specified in 1996, is used in the Portable Network Graphics (PNG) format.
Wavelet coding, the use of wavelet transforms in image compression, began after the development of DCT coding. The introduction of the DCT led to the development of wavelet coding, a variant of DCT coding that uses wavelets instead of DCT's block-based algorithm. The JPEG 2000 standard was developed from 1997 to 2000 by a JPEG committee chaired by Touradj Ebrahimi (later the JPEG president). In contrast to the DCT algorithm used by the original JPEG format, JPEG 2000 instead uses discrete wavelet transform (DWT) algorithms. It uses the CDF 9/7 wavelet transform (developed by Ingrid Daubechies in 1992) for its lossy compression algorithm, and the LeGall-Tabatabai (LGT) 5/3 wavelet transform (developed by Didier Le Gall and Ali J. Tabatabai in 1988) for its lossless compression algorithm. JPEG 2000 technology, which includes the Motion JPEG 2000 extension, was selected as the video coding standard for digital cinema in 2004.
Notes and references
- "Image Data Compression".
- Nasir Ahmed, T. Natarajan and K. R. Rao, "Discrete Cosine Transform," IEEE Trans. Computers, 90–93, Jan. 1974.
- Burt, P.; Adelson, E. (1 April 1983). "The Laplacian Pyramid as a Compact Image Code". IEEE Transactions on Communications. 31 (4): 532–540. CiteSeerX 10.1.1.54.299. doi:10.1109/TCOM.1983.1095851.
- Shao, Dan; Kropatsch, Walter G. (February 3–5, 2010). Špaček, Libor; Franc, Vojtěch (eds.). "Irregular Laplacian Graph Pyramid" (PDF). Computer Vision Winter Workshop 2010. Nové Hrady, Czech Republic: Czech Pattern Recognition Society.
- Claude Elwood Shannon (1948). Alcatel-Lucent (ed.). "A Mathematical Theory of Communication" (PDF). Bell System Technical Journal. 27 (3–4): 379–423, 623–656. doi:10.1002/j.1538-7305.1948.tb01338.x. hdl:11858/00-001M-0000-002C-4314-2. Retrieved 2019-04-21.
- David Albert Huffman (September 1952), "A method for the construction of minimum-redundancy codes" (PDF), Proceedings of the IRE, 40 (9), pp. 1098–1101, doi:10.1109/JRPROC.1952.273898
- William K. Pratt, Julius Kane, Harry C. Andrews: "Hadamard transform image coding", in Proceedings of the IEEE 57.1 (1969): Seiten 58–68
- Ahmed, Nasir (January 1991). "How I Came Up With the Discrete Cosine Transform". Digital Signal Processing. 1 (1): 4–5. doi:10.1016/1051-2004(91)90086-Z.
- "T.81 – DIGITAL COMPRESSION AND CODING OF CONTINUOUS-TONE STILL IMAGES – REQUIREMENTS AND GUIDELINES" (PDF). CCITT. September 1992. Retrieved 12 July 2019.
- "The JPEG image format explained". BT.com. BT Group. 31 May 2018. Retrieved 5 August 2019.
- "What Is a JPEG? The Invisible Object You See Every Day". The Atlantic. 24 September 2013. Retrieved 13 September 2019.
- Baraniuk, Chris (15 October 2015). "Copy protections could come to JPEGs". BBC News. BBC. Retrieved 13 September 2019.
- "The GIF Controversy: A Software Developer's Perspective". Retrieved 26 May 2015.
- L. Peter Deutsch (May 1996). DEFLATE Compressed Data Format Specification version 1.3. IETF. p. 1. sec. Abstract. doi:10.17487/RFC1951. RFC 1951. Retrieved 2014-04-23.
- Hoffman, Roy (2012). Data Compression in Digital Systems. Springer Science & Business Media. p. 124. ISBN 9781461560319.
Basically, wavelet coding is a variant on DCT-based transform coding that reduces or eliminates some of its limitations. (...) Another advantage is that rather than working with 8 × 8 blocks of pixels, as do JPEG and other block-based DCT techniques, wavelet coding can simultaneously compress the entire image.
- Taubman, David; Marcellin, Michael (2012). JPEG2000 Image Compression Fundamentals, Standards and Practice: Image Compression Fundamentals, Standards and Practice. Springer Science & Business Media. ISBN 9781461507994.
- Unser, M.; Blu, T. (2003). "Mathematical properties of the JPEG2000 wavelet filters" (PDF). IEEE Transactions on Image Processing. 12 (9): 1080–1090. Bibcode:2003ITIP...12.1080U. doi:10.1109/TIP.2003.812329. PMID 18237979. S2CID 2765169.
- Sullivan, Gary (8–12 December 2003). "General characteristics and design considerations for temporal subband video coding". ITU-T. Video Coding Experts Group. Retrieved 13 September 2019.
- Bovik, Alan C. (2009). The Essential Guide to Video Processing. Academic Press. p. 355. ISBN 9780080922508.
- Gall, Didier Le; Tabatabai, Ali J. (1988). "Sub-band coding of digital images using symmetric short kernel filters and arithmetic coding techniques". ICASSP-88., International Conference on Acoustics, Speech, and Signal Processing: 761–764 vol.2. doi:10.1109/ICASSP.1988.196696. S2CID 109186495.
- Swartz, Charles S. (2005). Understanding Digital Cinema: A Professional Handbook. Taylor & Francis. p. 147. ISBN 9780240806174.
- Image compression – lecture from MIT OpenCourseWare
- Image Coding Fundamentals
- A study about image compression – with basics, comparing different compression methods like JPEG2000, JPEG and JPEG XR / HD Photo
- Data Compression Basics – includes comparison of PNG, JPEG and JPEG-2000 formats
- FAQ:What is the state of the art in lossless image compression? from comp.compression
- IPRG – an open group related to image processing research resources