Editing Lossy compression

{{Short description|Data compression approach that reduces data size while discarding or changing some of it}}
[[File:Comparison of JPEG and PNG.png|thumb|Composite image showing JPG and PNG image compression. Left side of the image is from a low-quality JPEG image, showing lossy artefacts; the right side is from a PNG image.]]

In [[information technology]], '''lossy compression''' or '''irreversible compression''' is the class of [[data compression]] methods that uses inexact approximations and partial data discarding to represent the content. These techniques are used to reduce data size for storing, handling, and transmitting content. Higher degrees of approximation create coarser images as more details are removed. This is opposed to [[Lossless compression|lossless data compression]] (reversible data compression) which does not degrade the data. The amount of data reduction possible using lossy compression is much higher than using lossless techniques.

Well-designed lossy compression technology often reduces file sizes significantly before degradation is noticed by the end-user. Even when noticeable by the user, further data reduction may be desirable (e.g., for real-time communication or to reduce transmission times or storage needs). The most widely used lossy compression algorithm is the [[discrete cosine transform]] (DCT), first published by [[N. Ahmed|Nasir Ahmed]], T. Natarajan and [[K. R. Rao]] in 1974.

Lossy compression is most commonly used to compress [[multimedia]] data ([[Sound recording and reproduction|audio]], [[video]], and [[image]]s), especially in applications such as [[streaming media]] and [[VOIP|internet telephony]]. By contrast, lossless compression is typically required for text and data files, such as bank records and text articles. It can be advantageous to make a [[Master recording|master lossless file]] which can then be used to produce additional copies from. This allows one to avoid basing new compressed copies on a lossy source file, which would yield additional artifacts and further unnecessary [[Lossy compression#Information loss|information loss]].

==Types==
It is possible to compress many types of digital data in a way that reduces the size of a [[computer file]] needed to store it, or the [[Bandwidth (computing)|bandwidth]] needed to transmit it, with no loss of the full information contained in the original file. A picture, for example, is converted to a digital file by considering it to be an array of dots and specifying the color and brightness of each dot. If the picture contains an area of the same color, it can be compressed without loss by saying "200 red dots" instead of "red dot, red dot, ...(197 more times)..., red dot."

The original data contains a certain amount of information, and there is a lower bound to the size of a file that can still carry all the information. Basic [[information theory]] says that there is an absolute limit in reducing the size of this data. When data is compressed, its [[Entropy (information theory)|entropy]] increases, and it cannot increase indefinitely. For example, a compressed [[ZIP (file format)|ZIP]] file is smaller than its original, but repeatedly compressing the same file will not reduce the size to nothing. Most compression algorithms can recognize when further compression would be pointless and would in fact increase the size of the data.

In many cases, files or data streams contain more information than is needed. For example, a picture may have more detail than the eye can distinguish when reproduced at the largest size intended; likewise, an audio file does not need a lot of fine detail during a very loud passage. Developing lossy compression techniques as closely matched to human perception as possible is a complex task. Sometimes the ideal is a file that provides exactly the same perception as the original, with as much digital information as possible removed; other times, perceptible loss of quality is considered a valid tradeoff.

The terms "irreversible" and "reversible" are preferred over "lossy" and "lossless" respectively for some applications, such as medical image compression, to circumvent the negative implications of "loss". The type and amount of loss can affect the utility of the images. Artifacts or undesirable effects of compression may be clearly discernible yet the result still useful for the intended purpose. Or lossy compressed images may be '[[visually lossless]]', or in the case of medical images, so-called [[diagnostically acceptable irreversible compression]] (DAIC)<ref>{{cite journal|last=European Society of Radiology|title=Usability of irreversible image compression in radiological imaging. A position paper by the European Society of Radiology (ESR)|date=2011|pmc=3259360|pmid=22347940|doi=10.1007/s13244-011-0071-x|volume=2|issue=2|journal=Insights Imaging|pages=103–115}}</ref> may have been applied.

== Transform coding ==
{{main|Transform coding}}

Some forms of lossy compression can be thought of as an application of [[transform coding]], which is a type of data compression used for [[digital images]], [[digital audio]] [[Signal (information theory)|signals]], and [[digital video]]. The transformation is typically used to enable better (more targeted) [[quantization (signal processing)|quantization]]. Knowledge of the application is used to choose information to discard, thereby lowering its [[Bandwidth (computing)|bandwidth]]. The remaining information can then be compressed via a variety of methods. When the output is decoded, the result may not be identical to the original input, but is expected to be close enough for the purpose of the application.

The most common form of lossy compression is a transform coding method, the [[discrete cosine transform]] (DCT),<ref>{{cite web |title=Data compression |url=https://www.britannica.com/technology/data-compression |website=[[Encyclopedia Britannica]] |access-date=13 August 2019 }}</ref> which was first published by [[N. Ahmed|Nasir Ahmed]], T. Natarajan and [[K. R. Rao]] in 1974.<ref name="pubDCT">{{Citation |first1=Nasir |last1=Ahmed |author1-link=N. Ahmed |first2=T. |last2=Natarajan |first3=K. R. |last3=Rao |author3-link=K. R. Rao |title=Discrete Cosine Transform |journal=IEEE Transactions on Computers |date=January 1974 |volume=C-23 |issue=1 |pages=90–93 |doi=10.1109/T-C.1974.223784|s2cid=149806273 }}</ref> DCT is the most widely used form of lossy compression, for popular [[image compression]] formats (such as [[JPEG]]),<ref>{{cite web|url=https://www.w3.org/Graphics/JPEG/itu-t81.pdf|title=T.81 – DIGITAL COMPRESSION AND CODING OF CONTINUOUS-TONE STILL IMAGES – REQUIREMENTS AND GUIDELINES|date=September 1992|publisher=CCITT|access-date=12 July 2019}}</ref> [[video coding standards]] (such as [[MPEG]] and [[H.264/AVC]]) and [[audio compression (data)|audio compression]] formats (such as [[MP3]] and [[Advanced Audio Codec|AAC]]).

In the case of audio data, a popular form of transform coding is [[perceptual coding]], which transforms the raw data to a domain that more accurately reflects the information content. For example, rather than expressing a sound file as the amplitude levels over time, one may express it as the frequency spectrum over time, which corresponds more accurately to human audio perception. While data reduction (compression, be it lossy or lossless) is a main goal of transform coding, it also allows other goals: one may represent data more accurately for the original amount of space<ref>“Although one main goal of digital audio perceptual coders is data reduction, this is not a necessary characteristic. As we shall see, perceptual coding can be used to improve the representation of digital audio through advanced bit allocation.” [http://www.noisebetweenstations.com/personal/essays/audio_on_the_internet/MaskingPaper.html Masking and Perceptual Coding], Victor Lombardi, noisebetweenstations.com</ref> – for example, in principle, if one starts with an analog or high-resolution [[digital master]], an [[MP3]] file of a given size should provide a better representation than a raw uncompressed audio in [[WAV]] or [[Audio Interchange File Format|AIFF]] file of the same size. This is because uncompressed audio can only reduce file size by lowering bit rate or depth, whereas compressing audio can reduce size while maintaining bit rate and depth. This compression becomes a selective loss of the least significant data, rather than losing data across the board. Further, a transform coding may provide a better domain for manipulating or otherwise editing the data – for example, [[Equalization (audio)|equalization]] of audio is most naturally expressed in the frequency domain (boost the bass, for instance) rather than in the raw time domain.

From this point of view, perceptual encoding is not essentially about ''discarding'' data, but rather about a ''better representation'' of data. Another use is for [[backward compatibility]] and [[graceful degradation]]: in color television, encoding color via a [[Luminance (video)|luminance]]-[[chrominance]] transform domain (such as [[YUV]]) means that black-and-white sets display the luminance, while ignoring the color information. Another example is [[chroma subsampling]]: the use of [[color space]]s such as [[YIQ]], used in [[NTSC]], allow one to reduce the resolution on the components to accord with human perception – humans have highest resolution for black-and-white (luma), lower resolution for mid-spectrum colors like yellow and green, and lowest for red and blues – thus NTSC displays approximately 350 pixels of luma per [[scanline]], 150 pixels of yellow vs. green, and 50 pixels of blue vs. red, which are proportional to human sensitivity to each component.

== Information loss ==
Lossy compression formats suffer from [[generation loss]]: repeatedly compressing and decompressing the file will cause it to progressively lose quality. This is in contrast with [[lossless data compression]], where data will not be lost via the use of such a procedure. [[information theory|Information-theoretical]] foundations for lossy data compression are provided by [[rate-distortion theory]].  Much like the use of [[probability]] in optimal [[coding theory]], rate-distortion theory heavily draws on [[Bayesian theory|Bayesian]] [[estimation theory|estimation]] and [[decision theory]] in order to model perceptual distortion and even [[aesthetic]] judgment.

There are two basic lossy compression schemes:

* In ''lossy transform [[codec]]s'', samples of picture or sound are taken, chopped into small segments, transformed into a new [[Basis (linear algebra)|basis space]], and [[Quantization (signal processing)|quantized]]. The resulting quantized values are then [[Entropy encoding|entropy coded]].
* In ''lossy predictive codecs'', previous and/or subsequent decoded data is used to predict the current sound sample or image frame. The error between the predicted data and the real data, together with any extra information needed to reproduce the prediction, is then [[Quantization (signal processing)|quantized]] and coded.

In some systems the two techniques are combined, with transform codecs being used to compress the error signals generated by the predictive stage.

==Comparison==

The advantage of lossy methods over [[Lossless compression|lossless]] methods is that in some cases a lossy method can produce a much smaller compressed file than any lossless method, while still meeting the requirements of the application. Lossy methods are most often used for compressing sound, images or videos. This is because these types of data are intended for human interpretation where the mind can easily "fill in the blanks" or see past very minor errors or inconsistencies – ideally lossy compression is [[Transparency (data compression)|transparent]] (imperceptible), which can be verified via an [[ABX test]]. Data files using lossy compression are smaller in size and thus cost less to store and to transmit over the Internet, a crucial consideration for [[streaming video]] services such as [[Netflix]] and [[streaming audio]] services such as [[Spotify]].

===Transparency===
{{further|Transparency (data compression)}}
When a user acquires a lossily compressed file, (for example, to reduce download time) the retrieved file can be quite different from the original at the [[bit]] level while being indistinguishable to the human ear or eye for most practical purposes. Many compression methods focus on the idiosyncrasies of [[human physiology]], taking into account, for instance, that the human eye can see only certain wavelengths of light. The [[psychoacoustic model]] describes how sound can be highly compressed without degrading perceived quality. Flaws caused by lossy compression that are noticeable to the human eye or ear are known as [[compression artifact]]s.

===Compression ratio===
The [[data compression ratio|compression ratio]] (that is, the size of the compressed file compared to that of the uncompressed file) of lossy video codecs is nearly always far superior to that of the audio and still-image equivalents.

* Video can be compressed immensely (e.g., 100:1) with little visible quality loss
* Audio can often be compressed at 10:1 with almost imperceptible loss of quality
* Still images are often lossily compressed at 10:1, as with audio, but the quality loss is more noticeable, especially on closer inspection.

==Transcoding and editing==
{{further|Transcoding}}

An important caveat about lossy compression (formally transcoding), is that editing lossily compressed files causes [[digital generation loss]] from the re-encoding. This can be avoided by only producing lossy files from (lossless) originals and only editing (copies of) original files, such as images in [[raw image format]] instead of [[JPEG]]. If data which has been compressed lossily is decoded and compressed losslessly, the size of the result can be comparable with the size of the data before lossy compression, but the data already lost cannot be recovered. When deciding to use lossy conversion without keeping the original, format conversion may be needed in the future to achieve compatibility with software or devices ([[format shifting]]), or to avoid paying [[Software patent|patent royalties]] for decoding or distribution of compressed files.

===Editing of lossy files===
{{see also|commons:Commons:Software#JPEG|commons:Commons:Software#Ogg Vorbis (audio)}}
By modifying the compressed data directly without decoding and re-encoding, some editing of lossily compressed files without degradation of quality is possible. Editing which reduces the file size as if it had been compressed to a greater degree, but without more loss than this, is sometimes also possible.

====JPEG====
The primary programs for lossless editing of JPEGs are <code>[[jpegtran]]</code>, and the derived <code>exiftran</code> (which also preserves [[Exif]] information), and [http://sylvana.net/jpegcrop/ Jpegcrop] (which provides a Windows interface).

These allow the image to be [[Cropping (image)|cropped]], rotated, [[flipped image|flipped]], and [[flopped image|flopped]], or even converted to [[grayscale]] (by dropping the [[chrominance]] channel). While unwanted information is destroyed, the quality of the remaining portion is unchanged.

Some other transforms are possible to some extent, such as joining images with the same encoding (composing side by side, as on a grid) or pasting images such as logos onto existing images (both via [http://sylvana.net/jpegcrop/jpegjoin/ Jpegjoin]), or scaling.<ref>{{Cite web|url=http://sylvana.net/jpegcrop/jpegtran/|title=New jpegtran features|website=sylvana.net|access-date=2019-09-20}}</ref>

Some changes can be made to the compression without re-encoding:
* Optimizing the compression (to reduce size without change to the decoded image)
* Converting between progressive and non-progressive encoding.

The freeware Windows-only [[IrfanView]] has some lossless JPEG operations in its <code>JPG_TRANSFORM</code> [[Plug-in (computing)|plugin]].

====Metadata====
Metadata, such as [[ID3 tag]]s, [[Vorbis comment]]s, or [[Exif]] information, can usually be modified or removed without modifying the underlying data.

====Downsampling/compressed representation scalability====
One may wish to [[downsample]] or otherwise decrease the resolution of the represented source signal and the quantity of data used for its compressed representation without re-encoding, as in [[bitrate peeling]], but this functionality is not supported in all designs, as not all codecs encode data in a form that allows less important detail to simply be dropped. Some well-known designs that have this capability include [[JPEG 2000]] for still images and [[H.264/MPEG-4 AVC]] based [[Scalable Video Coding]] for video.  Such schemes have also been standardized for older designs as well, such as [[JPEG]] images with progressive encoding, and [[MPEG-2]] and [[MPEG-4 Part 2]] video, although those prior schemes had limited success in terms of adoption into real-world common usage. Without this capacity, which is often the case in practice, to produce a representation with lower resolution or lower fidelity than a given one, one needs to start with the original source signal and encode, or start with a compressed representation and then decompress and re-encode it ([[transcoding]]), though the latter tends to cause [[digital generation loss]].

Another approach is to encode the original signal at several different bitrates, and then either choose which to use (as when streaming over the internet – as in [[RealNetworks]]' "[[SureStream]]" – or offering varying downloads, as at Apple's [[iTunes Store]]), or broadcast several, where the best that is successfully received is used, as in various implementations of [[hierarchical modulation]]. Similar techniques are used in [[mipmap]]s, [[pyramid (image processing)|pyramid representation]]s, and more sophisticated [[scale space]] methods. Some audio formats feature a combination of a lossy format and a lossless correction which when combined reproduce the original signal; the correction can be stripped, leaving a smaller, lossily compressed, file. Such formats include [[MPEG-4 SLS]] (Scalable to Lossless), [[WavPack]], [[OptimFROG DualStream]], and [[DTS-HD Master Audio|DTS-HD Master Audio in lossless (XLL) mode]]).

==Methods==

===Graphics===

====Image====
{{further|Image compression}}

* [[Discrete cosine transform]] (DCT)
** [[JPEG]]<ref name="Stankovic">{{cite journal |last1=Stanković |first1=Radomir S. |last2=Astola |first2=Jaakko T. |title=Reminiscences of the Early Work in DCT: Interview with K.R. Rao |journal=Reprints from the Early Days of Information Sciences |date=2012 |volume=60 |url=http://ticsp.cs.tut.fi/reports/ticsp-report-60-reprint-rao-corrected.pdf |access-date=13 October 2019}}</ref>
** [[WebP]] (high-density lossless or lossy compression of RGB and RGBA images)
** [[High Efficiency Image Format]] (HEIF)
** [[Better Portable Graphics]] (BPG) (lossless or lossy compression)
** [[JPEG XR]], a successor of JPEG with support for [[high-dynamic-range imaging|high-dynamic range]], wide [[gamut]] pixel formats (lossless or lossy compression)
* [[Wavelet compression]]
** [[JPEG 2000]], JPEG's successor format that uses [[wavelets]] (lossless or lossy compression)
** [[DjVu]]
** [[ICER (file format)|ICER]], used by the Mars Rovers, related to [[JPEG 2000]] in its use of wavelets
** [[Progressive Graphics File|PGF]], Progressive Graphics File (lossless or lossy compression)
* [[Cartesian Perceptual Compression]], also known as CPC
* [[Fractal compression]]
* [[JBIG2]] (lossless or lossy compression)
* [[S3TC]] [[Texture mapping|texture]] compression for [[GPU|3D computer graphics hardware]]

====3D computer graphics====
* [[glTF]]

====Video====
{{further|Video coding format|Video compression}}

* [[Discrete cosine transform]] (DCT)
** [[H.261]]<ref name="Stankovic"/>
** [[Motion JPEG]]<ref name="Stankovic"/>
** [[MPEG-1 Part 2]]<ref name="Rao">K. R. Rao and J. J. Hwang, ''Techniques and Standards for Image, Video, and Audio Coding'', Prentice Hall, 1996; JPEG: Chapter 8; H.261: Chapter 9; MPEG-1: Chapter 10;  MPEG-2: Chapter 11.</ref>
** [[MPEG-2 Part 2]] (H.262)<ref name="Rao"/>
** [[MPEG-4 Part 2]] ([[H.263]])<ref name="Stankovic"/>
** [[Advanced Video Coding]] (AVC / H.264 / [[MPEG-4]] AVC)<ref name="Stankovic"/> (may also be lossless, even in certain video sections)
** [[High Efficiency Video Coding]] (HEVC / H.265)<ref name="Stankovic"/>
** [[Ogg]] [[Theora]] (noted for its lack of patent restrictions)
** [[VC-1]]
* [[Wavelet compression]]
** [[Motion JPEG 2000]]
** [[Dirac codec|Dirac]]
* [[Sorenson codec|Sorenson video codec]]

===Audio===
{{further|Audio coding format|Audio data compression}}

====General====
* [[Modified discrete cosine transform]] (MDCT)
** [[Dolby Digital]] (AC-3)
** [[Adaptive Transform Acoustic Coding]] (ATRAC)
** [[MPEG Layer III]] (MP3)<ref name="Guckert">{{cite web |last1=Guckert |first1=John |title=The Use of FFT and MDCT in MP3 Audio Compression |url=http://www.math.utah.edu/~gustafso/s2012/2270/web-projects/Guckert-audio-compression-svd-mdct-MP3.pdf |website=[[University of Utah]] |date=Spring 2012 |access-date=14 July 2019}}</ref>
** [[Advanced Audio Coding]] (AAC / [[MP4]] Audio)<ref name=brandenburg>{{cite web|url=http://graphics.ethz.ch/teaching/mmcom12/slides/mp3_and_aac_brandenburg.pdf|title=MP3 and AAC Explained|last=Brandenburg|first=Karlheinz|year=1999|url-status=live|archive-url=https://web.archive.org/web/20170213191747/https://graphics.ethz.ch/teaching/mmcom12/slides/mp3_and_aac_brandenburg.pdf|archive-date=2017-02-13}}</ref>
** [[Vorbis]]
** [[Windows Media Audio]] (WMA) (Standard and Pro profiles are lossy. WMA Lossless is also available.)
** [[LDAC (codec)|LDAC]]<ref name="Darko 2017">{{cite web | last=Darko | first=John H. | title=The inconvenient truth about Bluetooth audio | website=DAR__KO | date=2017-03-29 | url=http://www.digitalaudioreview.net/2017/03/the-inconvenient-truth-about-bluetooth-audio/ | access-date=2018-01-13 | archive-url=https://web.archive.org/web/20180114020200/http://www.digitalaudioreview.net/2017/03/the-inconvenient-truth-about-bluetooth-audio/ | archive-date=2018-01-14 | url-status=dead }}</ref><ref name="AVHub 2015">{{cite web|url=http://www.avhub.com.au/news/sound-image/what-is-sony-ldac-and-how-does-it-do-it-408285|title=What is Sony LDAC, and how does it do it?|last=Ford|first=Jez|date=2015-08-24|website=AVHub|access-date=2018-01-13}}</ref>
** [[Opus (codec)|Opus]] (Notable for lack of patent restrictions, low delay, and high quality speech and general audio.)
* [[Adaptive differential pulse-code modulation]] (ADPCM)
** [[Master Quality Authenticated]] (MQA)
* [[MPEG-1 Audio Layer II]] (MP2)
* [[Musepack]] (based on Musicam)
* [[AptX|aptX/ aptX-HD]]<ref name="AVHub 2016">{{cite web|url=http://www.avhub.com.au/news/sound-image/aptx-hd---lossless-or-lossy-442124|title=aptX HD - lossless or lossy?|last=Ford|first=Jez|date=2016-11-22|website=AVHub|access-date=2018-01-13}}</ref>

====Speech====
{{further|Speech encoding}}
* [[Linear predictive coding]] (LPC)
** [[Adaptive predictive coding]] (APC)
** [[Code-excited linear prediction]] (CELP)
** [[Algebraic code-excited linear prediction]] (ACELP)
** [[Relaxed code-excited linear prediction]] (RCELP)
** [[Low-delay CELP]] (LD-CELP)
** [[Adaptive Multi-Rate audio codec|Adaptive Multi-Rate]] (used in [[GSM]] and [[3GPP]])
** [[Codec2]] (noted for its lack of patent restrictions)
** [[Speex]] (noted for its lack of patent restrictions)
* [[Modified discrete cosine transform]] (MDCT)
** [[AAC-LD]]
** [[Constrained Energy Lapped Transform]] (CELT)
** [[Opus (codec)|Opus]] (mostly for real-time applications)
<!-- ===Geometry data=== -->

===Other data===
Researchers have performed lossy compression on text by either using a [[thesaurus]] to substitute short words for long ones, or [[Natural language generation|generative text]] techniques,<ref>{{cite web|url=http://compression.ru/download/articles/text/witten_1994cj_lossy_text_compression.pdf|title=Semantic and Generative Models for Lossy Text Compression|author=I. H. WITTEN|publisher=The Computer Journal|access-date=2007-10-13|display-authors=etal}}</ref> although these sometimes fall into the related category of [[lossy data conversion]].

== Lowering resolution ==
A general kind of lossy compression is to lower the resolution of an image, as in [[image scaling]], particularly [[Decimation (signal processing)|decimation]]. One may also remove less "lower information" parts of an image, such as by [[seam carving]]. Many media transforms, such as [[Gaussian blur]], are, like lossy compression, irreversible: the original signal cannot be reconstructed from the transformed signal. However, in general these will have the same size as the original, and are not a form of compression. Lowering resolution has practical uses, as the [[NASA]] [[New Horizons]] craft transmitted [[thumbnail]]s of its encounter with Pluto-Charon before it sent the higher resolution images. Another solution for slow connections is the usage of [[Interlacing (bitmaps)|Image interlacing]] which progressively defines the image. Thus a partial transmission is enough to preview the final image, in a lower resolution version, without creating a scaled and a full version too.{{citation needed|date=November 2019}}

==See also==
* [[Compression artifact]]
* [[Data compression]]
* [[Image scaling]]
* [[Lenna]]
* [[List of codecs]]
* [[Lossless compression]]
* [[Rate–distortion theory]]
* [[Seam carving]]
* [[Transcoding]]

==Notes==
<references/>

==External links==
* [http://www.bobulous.org.uk/misc/lossy_audio_2006.html Lossy audio formats], comparing the speed and compression strength of five lossy audio formats.
* [http://dvd-hq.info/data_compression.php Data compression basics], including chapters on lossy compression of images, audio and video.
* {{Webarchive|url=https://web.archive.org/web/20051003204116/http://membled.com/work/apps/lossy_png/|title=Lossy PNG image compression|date=2005-10-03}}
* [http://www.websiteoptimization.com/speed/tweak/lossy/ Using lossy GIF/PNG compression for the web (article)]
* [http://www.wfu.edu/~matthews/misc/jpg_vs_gif/JpgCompTest/JpgForArchive.html JPG for Archiving], comparing the suitability of JPG and lossless compression for image archives
* [http://www.mbreducer.com/ JPG Image Compression], Jpg, Png compressor tool 
{{Compression Methods}}

{{DEFAULTSORT:Lossy Compression}}
[[Category:Data compression]]
[[Category:Lossy compression algorithms|Lossy compression algorithms]]

[[fr:Compression de données#Compression avec pertes]]