patternMinor
Are there lossless data compression techniques that do not exploit repetitive patterns?
Viewed 0 times
losslessarecompressionpatternsrepetitivethatexploittheredatatechniques
Problem
Lossless Data compression (source coding) algorithms heavily rely on repetitive pattern (redundancy).
Is there a Lossless Data compression method/algorithm that is independent of repetitive pattern (redundancy)?
Note:
Most lossless compression programs do two things in sequence: the first step generates a statistical model for the input data, and the second step uses this model to map input data to bit sequences in such a way that "probable" (e.g. frequently encountered) data will produce shorter output than "improbable" data.
Techniques take advantage of the specific characteristics of images such as the common phenomenon of contiguous 2-D areas of similar tones. Every pixel but the first is replaced by the difference to its left neighbor. This leads to small values having a much higher probability than large values. This is often also applied to sound files, and can compress files that contain mostly low frequencies and low volumes. For images, this step can be repeated by taking the difference to the top pixel, and then in videos, the difference to the pixel in the next frame can be taken.
A hierarchical version of this technique takes neighboring pairs of data points, stores their difference and sum, and on a higher level with lower resolution continues with the sums. This is called discrete wavelet transform.
Is there a Lossless Data compression method/algorithm that is independent of repetitive pattern (redundancy)?
Note:
Most lossless compression programs do two things in sequence: the first step generates a statistical model for the input data, and the second step uses this model to map input data to bit sequences in such a way that "probable" (e.g. frequently encountered) data will produce shorter output than "improbable" data.
Techniques take advantage of the specific characteristics of images such as the common phenomenon of contiguous 2-D areas of similar tones. Every pixel but the first is replaced by the difference to its left neighbor. This leads to small values having a much higher probability than large values. This is often also applied to sound files, and can compress files that contain mostly low frequencies and low volumes. For images, this step can be repeated by taking the difference to the top pixel, and then in videos, the difference to the pixel in the next frame can be taken.
A hierarchical version of this technique takes neighboring pairs of data points, stores their difference and sum, and on a higher level with lower resolution continues with the sums. This is called discrete wavelet transform.
Solution
An interesting lossless compression algorithm for JPEG images was open-sourced this summer by Dropbox. The algorithm is called "Lepton" and achieves compression by "predicting coefficients in JPEG blocks and feeding those predictions as context into an arithmetic coder." The differences between the predictions and the actual coefficients are stored and these differences consume less space than the coefficients themselves. The algorithm takes advantage of the fact that real image data is rarely random and that gradients are smooth across blocks of pixels on average.
Context
StackExchange Computer Science Q#65096, answer score: 4
Revisions (0)
No revisions yet.