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?
When (not how or why) to calculate Big O of an algorithm
Plagiarism or not?
iPad being using in wall mount battery swollen
How badly should I try to prevent a user from XSSing themselves?
Arrow those variables!
Why doesn't using multiple commands with a || or && conditional work?
Personal Teleportation: From Rags to Riches
Is there a hemisphere-neutral way of specifying a season?
ssTTsSTtRrriinInnnnNNNIiinngg
What exploit Are these user agents trying to use?
Should I tell management that I intend to leave due to bad software development practices?
Can my sorcerer use a spellbook only to collect spells and scribe scrolls, not cast?
Does the Idaho Potato Commission associate potato skins with healthy eating?
Can I run a new neutral wire to repair a broken circuit?
How seriously should I take size and weight limits of hand luggage?
CAST throwing error when run in stored procedure but not when run as raw query
How do I handle a potential work/personal life conflict as the manager of one of my friends?
What is the idiomatic way to say "clothing fits"?
Method Does Not Exist error message
Why no variance term in Bayesian logistic regression?
What about the virus in 12 Monkeys?
Why was the shrinking from 8″ made only to 5.25″ and not smaller (4″ or less)?
Is it logically or scientifically possible to artificially send energy to the body?
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
