Editing Image compression

{{Short description|Reduction of image size to save storage and transmission costs
}}
{{Use American English|date=January 2019}}{{more footnotes needed|date=April 2010}} 
'''Image compression''' is a type of [[data compression]] applied to [[digital image]]s, to reduce their cost for [[computer data storage|storage]] or [[data transmission|transmission]]. [[Algorithm]]s 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.<ref>{{cite web|url=http://user.engineering.uiowa.edu/~dip/lecture/DataCompression.html|title=Image Data Compression}}</ref>
[[Image:Quality comparison jpg vs saveforweb.jpg|thumb|250px|Comparison of [[JPEG]] images saved by Adobe Photoshop at different quality levels and with or without "save for web"]]

== Lossy and lossless image compression ==
Image compression may be [[lossy compression|lossy]] or [[lossless compression|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 rate]]s, introduce [[compression artifact]]s.  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 [[List of Fourier-related transforms|Fourier-related transform]], and was originally developed by [[N. Ahmed|Nasir Ahmed]], T. Natarajan and [[K. R. Rao]] in 1974.<ref>{{cite journal|doi=10.1109/T-C.1974.223784|url=http://dasan.sejong.ac.kr/~dihan/dip/p5_DCT.pdf | title=Discrete Cosine Transform|date=1974 |archive-url=https://web.archive.org/web/20111125071212/http://dasan.sejong.ac.kr/~dihan/dip/p5_DCT.pdf |archive-date=2011-11-25 |last1=Ahmed |first1=N. |last2=Natarajan |first2=T. |last3=Rao |first3=K.R. |journal=IEEE Transactions on Computers |pages=90–93 |s2cid=149806273 }}</ref> 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.
*** DCT is used in [[JPEG]], the most popular lossy format, and the more recent [[HEIF]].
** The more recently developed [[wavelet transform]] is also used extensively, followed by [[Quantization (image processing)|quantization]] and [[entropy coding]].
* [[Color quantization]] - Reducing the [[color space encoding|color space]] to a few "representative" colors in the image. The selected colors are specified in the color [[palette (computing)|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]].
** Whole-image palette, typically 256 colors, used in GIF and PNG file formats.
** block palette, typically 2 or 4 colors for each block of 4x4 pixels, used in [[Block Truncation Coding|BTC]], [[Color Cell Compression|CCC]], [[S2TC]], and [[S3 Texture Compression|S3TC]].
* [[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]].
* More recently, methods based on [[Machine Learning]] were applied, using [[Multilayer perceptron]]s, [[Convolutional neural network]]s, [[Generative adversarial network]]s<ref>{{cite web |author1=Gilad David Maayan |title=AI-Based Image Compression: The State of the Art |url=https://towardsdatascience.com/ai-based-image-compression-the-state-of-the-art-fb5aa6042bfa |website=Towards Data Science |access-date=6 April 2023 |date=Nov 24, 2021}}</ref> and [[Diffusion model]]s.<ref>{{Cite web |last=Bühlmann |first=Matthias |date=2022-09-28 |title=Stable Diffusion Based Image Compression |url=https://pub.towardsai.net/stable-diffusion-based-image-compresssion-6f1f0a399202 |access-date=2022-11-02 |website=Medium |language=en}}</ref> Implementations are available in [[OpenCV]], [[TensorFlow]], [[MATLAB]]'s Image Processing Toolbox (IPT), and the High-Fidelity Generative Image Compression (HiFiC) open source project.<ref>{{cite web |title=High-Fidelity Generative Image Compression |url=https://hific.github.io/ |access-date=6 April 2023}}</ref>

Methods for [[lossless compression]]:

* [[Run-length encoding]] – used in default method in [[PCX]] and as one of possible in [[BMP file format|BMP]], [[.tga|TGA]], [[TIFF]]
* 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 [[Graphics Interchange Format|GIF]] and [[TIFF]]
* [[DEFLATE]] – used in [[Portable Network Graphics|PNG]], [[Multiple-image Network Graphics|MNG]], and [[TIFF]]
* [[Chain code]]s

== Other properties ==
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.<ref>{{cite journal|last1=Burt|first1=P.|last2=Adelson|first2=E.|title=The Laplacian Pyramid as a Compact Image Code|journal=IEEE Transactions on Communications|date=1 April 1983|volume=31|issue=4|pages=532–540|doi=10.1109/TCOM.1983.1095851|citeseerx=10.1.1.54.299|s2cid=8018433 }}</ref><ref>{{cite journal |last1=Shao |first1=Dan |first2=Walter G. |last2=Kropatsch |title=Irregular Laplacian Graph Pyramid |journal=Computer Vision Winter Workshop 2010|date=February 3–5, 2010|editor1-first=Libor |editor1-last=Špaček |editor2-first=Vojtěch |editor2-last=Franc |publisher=Czech Pattern Recognition Society |location=Nové Hrady, Czech Republic |url=http://www.prip.tuwien.ac.at/twist/docs/irregularLaplacian.pdf |archive-url=https://web.archive.org/web/20130527045502/http://www.prip.tuwien.ac.at/twist/docs/irregularLaplacian.pdf |archive-date=2013-05-27 |url-status=live}}</ref>
* '''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 (computing)|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.

== History ==
[[Entropy coding]] started in the late 1940s with the introduction of [[Shannon–Fano coding]],<ref name="Shannon">{{cite journal|author1=Claude Elwood Shannon|editor-surname1= Alcatel-Lucent|journal=Bell System Technical Journal|title=A Mathematical Theory of Communication |volume=27 |issue=3–4 |date=1948 |pages=379–423, 623–656 |doi= 10.1002/j.1538-7305.1948.tb01338.x|hdl= 11858/00-001M-0000-002C-4314-2|url=http://www.math.harvard.edu/~ctm/home/text/others/shannon/entropy/entropy.pdf |archive-url=https://web.archive.org/web/20110524064232/http://math.harvard.edu/~ctm/home/text/others/shannon/entropy/entropy.pdf |archive-date=2011-05-24 |url-status=live |access-date=2019-04-21 |author1-link= Claude Elwood Shannon|hdl-access=free }}</ref> the basis for [[Huffman coding]] which was published in 1952.<ref name="Huffman">{{citation |surname1=[[David Albert Huffman]] |periodical=[[Proceedings of the IRE]] |title=A method for the construction of minimum-redundancy codes |volume=40 |issue=9 |pages=1098–1101 |date=September 1952 |doi=10.1109/JRPROC.1952.273898 |url=http://compression.ru/download/articles/huff/huffman_1952_minimum-redundancy-codes.pdf |archive-url=https://web.archive.org/web/20051008115257/http://compression.ru/download/articles/huff/huffman_1952_minimum-redundancy-codes.pdf |archive-date=2005-10-08 |url-status=live}}</ref> [[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.<ref name="Hadamard">{{cite journal|doi=10.1109/PROC.1969.6869 |title=Hadamard transform image coding |date=1969 |last1=Pratt |first1=W.K. |last2=Kane |first2=J. |last3=Andrews |first3=H.C. |journal=Proceedings of the IEEE |volume=57 |pages=58–68 }}</ref>

An important development in image [[data compression]] was the [[discrete cosine transform]] (DCT), a [[lossy compression]] technique first proposed by [[N. Ahmed|Nasir Ahmed]], T. Natarajan and [[K. R. Rao]] in 1973.<ref name="Ahmed">{{cite journal |last=Ahmed |first=Nasir |author-link=N. Ahmed |title=How I Came Up With the Discrete Cosine Transform |journal=[[Digital Signal Processing (journal)|Digital Signal Processing]] |date=January 1991 |volume=1 |issue=1 |pages=4–5 |doi=10.1016/1051-2004(91)90086-Z |bibcode=1991DSP.....1....4A |url=https://www.scribd.com/doc/52879771/DCT-History-How-I-Came-Up-with-the-Discrete-Cosine-Transform|url-access=subscription }}</ref> [[JPEG]] was introduced by the [[Joint Photographic Experts Group]] (JPEG) in 1992.<ref name="t81">{{cite web |title=T.81 – DIGITAL COMPRESSION AND CODING OF CONTINUOUS-TONE STILL IMAGES – REQUIREMENTS AND GUIDELINES |url=https://www.w3.org/Graphics/JPEG/itu-t81.pdf |archive-url=https://web.archive.org/web/20000818020219/http://www.w3.org/Graphics/JPEG/itu-t81.pdf |archive-date=2000-08-18 |url-status=live |publisher=[[CCITT]] |date=September 1992 |access-date=12 July 2019}}</ref> JPEG compresses images down to much smaller file sizes, and has become the most widely used [[image file format]].<ref>{{cite web |title=The JPEG image format explained |url=https://home.bt.com/tech-gadgets/photography/what-is-a-jpeg-11364206889349 |website=[[BT.com]] |publisher=[[BT Group]] |access-date=5 August 2019 |date=31 May 2018}}</ref> JPEG was largely responsible for the wide proliferation of [[digital images]] and [[digital photo]]s,<ref name="Atlantic">{{cite web |title=What Is a JPEG? The Invisible Object You See Every Day |url=https://www.theatlantic.com/technology/archive/2013/09/what-is-a-jpeg-the-invisible-object-you-see-every-day/279954/ |access-date=13 September 2019 |website=[[The Atlantic]] |date=24 September 2013}}</ref> with several billion JPEG images produced every day as of 2015.<ref>{{cite news |last1=Baraniuk |first1=Chris |title=Copy protections could come to JPEGs |url=https://www.bbc.co.uk/news/technology-34538705 |access-date=13 September 2019 |work=[[BBC News]] |agency=[[BBC]] |date=15 October 2015}}</ref>

[[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.<ref name="cloanto">{{cite web |url=https://mike.pub/19950127-gif-lzw|title=The GIF Controversy: A Software Developer's Perspective |date=27 January 1995 |access-date=26 May 2015}}</ref> [[DEFLATE]], a lossless compression algorithm developed by [[Phil Katz]] and specified in 1996, is used in the [[Portable Network Graphics]] (PNG) format.<ref name="IETF">{{cite IETF |title=DEFLATE Compressed Data Format Specification version 1.3 |rfc=1951 |section=Abstract |page=1 |author=L. Peter Deutsch |author-link=L. Peter Deutsch |date=May 1996 |publisher=[[Internet Engineering Task Force|IETF]] |access-date=2014-04-23}}</ref>

The [[JPEG 2000]] standard was developed from 1997 to 2000 by a JPEG committee chaired by Touradj Ebrahimi (later the JPEG president).<ref>{{cite book |last1=Taubman |first1=David |last2=Marcellin |first2=Michael |title=JPEG2000 Image Compression Fundamentals, Standards and Practice: Image Compression Fundamentals, Standards and Practice |date=2012 |publisher=[[Springer Science & Business Media]] |isbn=9781461507994 |url=https://books.google.com/books?id=y7HeBwAAQBAJ&pg=PA402}}</ref> In contrast to the DCT algorithm used by the original JPEG format, JPEG 2000 instead uses [[discrete wavelet transform]] (DWT) algorithms. It uses the [[Cohen-Daubechies-Feauveau wavelet|CDF]] 9/7 wavelet transform (developed by [[Ingrid Daubechies]] in 1992) for its lossy compression algorithm,<ref name="Unser">{{cite journal |last1=Unser |first1=M. |last2=Blu |first2=T. |title=Mathematical properties of the JPEG2000 wavelet filters |journal=IEEE Transactions on Image Processing |date=2003 |volume=12 |issue=9 |pages=1080–1090 |doi=10.1109/TIP.2003.812329 |pmid=18237979 |bibcode=2003ITIP...12.1080U |s2cid=2765169 |url=https://pdfs.semanticscholar.org/6ed4/dece8b364416d9c390ba53df913bca7fb9a6.pdf |archive-url=https://web.archive.org/web/20191013222932/https://pdfs.semanticscholar.org/6ed4/dece8b364416d9c390ba53df913bca7fb9a6.pdf |url-status=dead |archive-date=2019-10-13 }}</ref> and the Le Gall–Tabatabai (LGT) 5/3 wavelet transform<ref>{{cite web |last1=Sullivan |first1=Gary |title=General characteristics and design considerations for temporal subband video coding |publisher=[[Video Coding Experts Group]] |website=[[ITU-T]] |date=8–12 December 2003 |url=https://www.itu.int/wftp3/av-arch/video-site/0312_Wai/VCEG-U06.doc |access-date=13 September 2019}}</ref><ref>{{cite book |last1=Bovik |first1=Alan C. |title=The Essential Guide to Video Processing |date=2009 |publisher=[[Academic Press]] |isbn=9780080922508 |page=355 |url=https://books.google.com/books?id=wXmSPPB_c_0C&pg=PA355}}</ref> (developed by Didier Le Gall and Ali J. Tabatabai in 1988)<ref>{{cite book |last1=Le Gall |first1=Didier |last2=Tabatabai |first2=Ali J. |title=ICASSP-88., International Conference on Acoustics, Speech, and Signal Processing |chapter=Sub-band coding of digital images using symmetric short kernel filters and arithmetic coding techniques |date=1988 |pages=761–764 vol.2 |doi=10.1109/ICASSP.1988.196696 |s2cid=109186495}}</ref> for its lossless compression algorithm.<ref name="Unser"/> [[JPEG 2000]] technology, which includes the [[Motion JPEG 2000]] extension, was selected as the [[video coding standard]] for [[digital cinema]] in 2004.<ref>{{cite book |last1=Swartz |first1=Charles S. |title=Understanding Digital Cinema: A Professional Handbook |date=2005 |publisher=[[Taylor & Francis]] |isbn=9780240806174 |page=147 |url=https://books.google.com/books?id=tYw3ehoBnjkC&pg=PA147}}</ref>

The evolution of image compression technologies has led to continuous improvements in both efficiency and quality. From the early developments in entropy coding and transform coding to the introduction of JPEG and JPEG 2000, these innovations have significantly impacted the way digital images are stored, transmitted, and processed. Modern compression methods allow users to optimize image files for faster loading times and better storage utilization, while maintaining high image quality. As compression technologies advance, these methods continue to play a crucial role in various fields, including web development, digital media, and content management.

== Huffman Coding ==
Huffman coding is a fundamental technique used in image compression algorithms to achieve efficient data representation. Named after its inventor David A. Huffman, this method is widely employed in various image compression standards such as JPEG and PNG.

=== Principle of Huffman Coding ===
Huffman coding is a form of entropy encoding that assigns variable-length codes to input symbols based on their frequencies of occurrence. The basic principle is to assign shorter codes to more frequently occurring symbols and longer codes to less frequent symbols, thereby reducing the average code length compared to fixed-length codes.

=== Application in Image Compression ===
In image compression, Huffman coding is typically applied after other transformations like Discrete Cosine Transform (DCT) in the case of JPEG compression. After transforming the image data into a frequency domain representation, Huffman coding is used to encode the transformed coefficients efficiently.

=== Steps in Huffman Coding for Image Compression ===
# Frequency Analysis: Calculate the frequency of occurrence of each symbol or symbol combination in the transformed image data.
# Constructing the Huffman Tree: Build a Huffman tree based on the symbol frequencies. The tree is constructed recursively by combining the nodes with the lowest frequencies until a single root node is formed.
# Assigning Codewords: Traverse the Huffman tree to assign variable-length codewords to each symbol, with shorter codewords assigned to more frequent symbols.
# Encoding: Replace the original symbols in the image data with their corresponding Huffman codewords to generate the compressed data stream.

=== Benefits of Huffman Coding in Image Compression ===
* Lossless Compression: Huffman coding can be used in both lossy and lossless image compression techniques, providing flexibility in balancing between compression ratio and image quality.
* Efficiency: By assigning shorter codes to frequently occurring symbols, Huffman coding reduces the average code length, resulting in efficient data representation and reduced storage requirements.
* Compatibility: Huffman coding is widely supported and can be seamlessly integrated into existing image compression standards and algorithms.

=== Conclusion ===
Huffman coding plays a crucial role in image compression by efficiently encoding image data into a compact representation. Its ability to adaptively assign variable-length codewords based on symbol frequencies makes it an essential component in modern image compression techniques, contributing to the reduction of storage space and transmission bandwidth while maintaining image quality.

== Notes and references ==
{{reflist}}{{Compression methods}}
{{Compression formats}}

[[Category:Image compression| ]]
[[Category:Data compression]]