How does a predictive coding aid in lossless compression?Lossless Video Compression PipelineCompressing normally distributed dataHow can GIF compression be lossless if the maximum # of colors is 256?Hash for verifying both compressed and uncompressed data?Can random suitless $52$ playing card data be compressed to approach, match, or even beat entropy encoding storage? If so, how?Arithmetic coding and “the optimal compression ratio”How does adaptative Huffman coding (Vitter algorithm) work?Universal Lossless Compression?Is von Neumann's randomness in sin quote no longer applicable?Algorithm for estimating lossless compression factor
What's the in-universe reasoning behind sorcerers needing material components?
Forgetting the musical notes while performing in concert
Why do bosons tend to occupy the same state?
Why no variance term in Bayesian logistic regression?
Why didn't Boeing produce its own regional jet?
Is "remove commented out code" correct English?
How does a predictive coding aid in lossless compression?
Is it possible to create a QR code using text?
Why can't we play rap on piano?
Do UK voters know if their MP will be the Speaker of the House?
Can I run a new neutral wire to repair a broken circuit?
Plagiarism or not?
How do I handle a potential work/personal life conflict as the manager of one of my friends?
Arrow those variables!
Assassin's bullet with mercury
How do I gain back my faith in my PhD degree?
I would say: "You are another teacher", but she is a woman and I am a man
Alternative to sending password over mail?
How can saying a song's name be a copyright violation?
How to prevent "they're falling in love" trope
Is this a hacking script in function.php?
Forming a German sentence with/without the verb at the end
How can I deal with my CEO asking me to hire someone with a higher salary than me, a co-founder?
Could the museum Saturn V's be refitted for one more flight?
How does a predictive coding aid in lossless compression?
Lossless Video Compression PipelineCompressing normally distributed dataHow can GIF compression be lossless if the maximum # of colors is 256?Hash for verifying both compressed and uncompressed data?Can random suitless $52$ playing card data be compressed to approach, match, or even beat entropy encoding storage? If so, how?Arithmetic coding and “the optimal compression ratio”How does adaptative Huffman coding (Vitter algorithm) work?Universal Lossless Compression?Is von Neumann's randomness in sin quote no longer applicable?Algorithm for estimating lossless compression factor
$begingroup$
I'm working on this lab where we need to apply a lossless predictive coding to an image before compressing it (with Huffman, or some other lossless compression algorithm).
From the example seen below, it's pretty clear that by pre-processing the image with predictive coding, we've modified its histogram and concentrated all of its grey levels around 0. But why exactly does this aid compression?
Is there maybe a formula to determine the compression rate of Huffman, knowing the standard deviation and entropy of the original image? Otherwise, why would the compression ratio be any different; it's not like the range of values has changed between the original image and pre-processed image.
Thank you in advance,
Liam.
image-processing data-compression huffman-coding
asked 1 hour ago
Liam F-ALiam F-A
211
$endgroup$
add a comment |
$begingroup$
I'm working on this lab where we need to apply a lossless predictive coding to an image before compressing it (with Huffman, or some other lossless compression algorithm).
From the example seen below, it's pretty clear that by pre-processing the image with predictive coding, we've modified its histogram and concentrated all of its grey levels around 0. But why exactly does this aid compression?
Is there maybe a formula to determine the compression rate of Huffman, knowing the standard deviation and entropy of the original image? Otherwise, why would the compression ratio be any different; it's not like the range of values has changed between the original image and pre-processed image.
Thank you in advance,
Liam.
image-processing data-compression huffman-coding
asked 1 hour ago
Liam F-ALiam F-A
211
$endgroup$
add a comment |
$begingroup$
I'm working on this lab where we need to apply a lossless predictive coding to an image before compressing it (with Huffman, or some other lossless compression algorithm).
From the example seen below, it's pretty clear that by pre-processing the image with predictive coding, we've modified its histogram and concentrated all of its grey levels around 0. But why exactly does this aid compression?
Is there maybe a formula to determine the compression rate of Huffman, knowing the standard deviation and entropy of the original image? Otherwise, why would the compression ratio be any different; it's not like the range of values has changed between the original image and pre-processed image.
Thank you in advance,
Liam.
image-processing data-compression huffman-coding
asked 1 hour ago
Liam F-ALiam F-A
211
$endgroup$
I'm working on this lab where we need to apply a lossless predictive coding to an image before compressing it (with Huffman, or some other lossless compression algorithm).
From the example seen below, it's pretty clear that by pre-processing the image with predictive coding, we've modified its histogram and concentrated all of its grey levels around 0. But why exactly does this aid compression?
Is there maybe a formula to determine the compression rate of Huffman, knowing the standard deviation and entropy of the original image? Otherwise, why would the compression ratio be any different; it's not like the range of values has changed between the original image and pre-processed image.
Thank you in advance,
Liam.
image-processing data-compression huffman-coding
image-processing data-compression huffman-coding
asked 1 hour ago
Liam F-ALiam F-A
211
asked 1 hour ago
Liam F-ALiam F-A
211
asked 1 hour ago
Liam F-ALiam F-A
211
asked 1 hour ago
Liam F-ALiam F-A
211
asked 1 hour ago
Liam F-ALiam F-A
211
211
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
Huffman coding, as usually applied, only considers the distribution of singletons. If $X$ is the distribution of a random singleton, then Huffman coding uses between $H(X)$ and $H(X)+1$ bits per singleton, where $H(cdot)$ is the (log 2) entropy function.
In contrast, predictive coding can take into account correlations across data points. As a simple example, consider the following sequence:
$$
0,1,2,ldots,255,0,1,2,ldots,255,ldots
$$
Huffman coding would use 8 bits per unit of data, whereas with predictive coding we could get potentially to $O(log n)$ bits for the entire sequence.
answered 1 hour ago
Yuval FilmusYuval Filmus
196k15184349
$endgroup$
add a comment |
Your Answer
StackExchange.ifUsing("editor", function ()
return StackExchange.using("mathjaxEditing", function ()
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
);
);
, "mathjax-editing");
StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "419"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);
else
createEditor();
);
function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader:
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
,
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);
);
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcs.stackexchange.com%2fquestions%2f106450%2fhow-does-a-predictive-coding-aid-in-lossless-compression%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Huffman coding, as usually applied, only considers the distribution of singletons. If $X$ is the distribution of a random singleton, then Huffman coding uses between $H(X)$ and $H(X)+1$ bits per singleton, where $H(cdot)$ is the (log 2) entropy function.
In contrast, predictive coding can take into account correlations across data points. As a simple example, consider the following sequence:
$$
0,1,2,ldots,255,0,1,2,ldots,255,ldots
$$
Huffman coding would use 8 bits per unit of data, whereas with predictive coding we could get potentially to $O(log n)$ bits for the entire sequence.
answered 1 hour ago
Yuval FilmusYuval Filmus
196k15184349
$endgroup$
add a comment |
$begingroup$
Huffman coding, as usually applied, only considers the distribution of singletons. If $X$ is the distribution of a random singleton, then Huffman coding uses between $H(X)$ and $H(X)+1$ bits per singleton, where $H(cdot)$ is the (log 2) entropy function.
In contrast, predictive coding can take into account correlations across data points. As a simple example, consider the following sequence:
$$
0,1,2,ldots,255,0,1,2,ldots,255,ldots
$$
Huffman coding would use 8 bits per unit of data, whereas with predictive coding we could get potentially to $O(log n)$ bits for the entire sequence.
answered 1 hour ago
Yuval FilmusYuval Filmus
196k15184349
$endgroup$
add a comment |
$begingroup$
Huffman coding, as usually applied, only considers the distribution of singletons. If $X$ is the distribution of a random singleton, then Huffman coding uses between $H(X)$ and $H(X)+1$ bits per singleton, where $H(cdot)$ is the (log 2) entropy function.
In contrast, predictive coding can take into account correlations across data points. As a simple example, consider the following sequence:
$$
0,1,2,ldots,255,0,1,2,ldots,255,ldots
$$
Huffman coding would use 8 bits per unit of data, whereas with predictive coding we could get potentially to $O(log n)$ bits for the entire sequence.
answered 1 hour ago
Yuval FilmusYuval Filmus
196k15184349
$endgroup$
Huffman coding, as usually applied, only considers the distribution of singletons. If $X$ is the distribution of a random singleton, then Huffman coding uses between $H(X)$ and $H(X)+1$ bits per singleton, where $H(cdot)$ is the (log 2) entropy function.
In contrast, predictive coding can take into account correlations across data points. As a simple example, consider the following sequence:
$$
0,1,2,ldots,255,0,1,2,ldots,255,ldots
$$
Huffman coding would use 8 bits per unit of data, whereas with predictive coding we could get potentially to $O(log n)$ bits for the entire sequence.
answered 1 hour ago
Yuval FilmusYuval Filmus
196k15184349
answered 1 hour ago
Yuval FilmusYuval Filmus
196k15184349
answered 1 hour ago
Yuval FilmusYuval Filmus
196k15184349
answered 1 hour ago
Yuval FilmusYuval Filmus
196k15184349
196k15184349
add a comment |
add a comment |
Thanks for contributing an answer to Computer Science Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcs.stackexchange.com%2fquestions%2f106450%2fhow-does-a-predictive-coding-aid-in-lossless-compression%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
