Kdtyjb

Is there a hemisphere-neutral way of specifying a season?

How do I gain back my faith in my PhD degree?

Which is the best way to check return result?

What does “the session was packed” mean in this context?

How do conventional missiles fly?

Madden-Julian Oscillation (MJO) - How to interpret the index?

How do I handle a potential work/personal life conflict as the manager of one of my friends?

One verb to replace 'be a member of' a club

Can my sorcerer use a spellbook only to collect spells and scribe scrolls, not cast?

Examples of smooth manifolds admitting inbetween one and a continuum of complex structures

Is this a hacking script in function.php?

How could indestructible materials be used in power generation?

Expand and Contract

How does a predictive coding aid in lossless compression?

Am I breaking OOP practice with this architecture?

How would I stat a creature to be immune to everything but the Magic Missile spell? (just for fun)

Alternative to sending password over mail?

How badly should I try to prevent a user from XSSing themselves?

iPad being using in wall mount battery swollen

What exploit Are these user agents trying to use?

Why is this clock signal connected to a capacitor to gnd?

Should I tell management that I intend to leave due to bad software development practices?

How do I deal with an unproductive colleague in a small company?

ssTTsSTtRrriinInnnnNNNIiinngg

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

2

$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

share|cite|improve this question

asked 1 hour ago

Liam F-ALiam F-A

161

$endgroup$

add a comment | 

2

$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

share|cite|improve this question

asked 1 hour ago

Liam F-ALiam F-A

161

$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

share|cite|improve this question

asked 1 hour ago

Liam F-ALiam F-A

161

$endgroup$

share|cite|improve this question

asked 1 hour ago

Liam F-ALiam F-A

161

share|cite|improve this question

asked 1 hour ago

Liam F-ALiam F-A

161

asked 1 hour ago

Liam F-ALiam F-A

161

asked 1 hour ago

Liam F-ALiam F-A

161

1 Answer
1

active

oldest

votes

3

$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.

share|cite|improve this answer

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
});


}
});

draft saved

draft discarded

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

Name

Email

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

Name

Email

Required, but never shown

3

$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.

share|cite|improve this answer

answered 1 hour ago

Yuval FilmusYuval Filmus

196k15184349

$endgroup$

add a comment | 

3

$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.

share|cite|improve this answer

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.

share|cite|improve this answer

answered 1 hour ago

Yuval FilmusYuval Filmus

196k15184349

$endgroup$

share|cite|improve this answer

answered 1 hour ago

Yuval FilmusYuval Filmus

196k15184349

answered 1 hour ago

Yuval FilmusYuval Filmus

196k15184349

answered 1 hour ago

Yuval FilmusYuval Filmus

196k15184349