PE2-2.3 Stochastic Modelling & Compression

What this is and why it exists

Real signals are predictable. Not perfectly, but a sample is usually similar to the one before it, and a pixel is usually similar to its neighbours.

That predictability is what compression exploits. This topic builds the models that measure it, then turns those models into ways of sending less.

The vocabulary

• AR-1 process — the simplest model where each sample depends on the previous one plus noise.
• Yule-Walker equations — the linear system recovering model coefficients from measured correlation.
• Markov chain — a process moving between states, where the next state depends only on the present one.
• Quantisation — replacing a continuous value with one of a fixed set.
• Distortion — a measure of how much a compressed version differs from the original.
• K-means — an algorithm that groups data by nearness, used here to place quantisation levels.
• Predictive coding — sending the error of a prediction instead of the value.
• Transform coding — compressing in a transformed domain where energy concentrates.
• Multiresolution coding — coding at several scales, so a coarse version arrives first.

The mental model

The simplest useful model has one parameter. Each sample is that parameter times the previous sample, plus a fresh random input. Simulate it and the parameter's meaning becomes obvious without any algebra. Near zero, successive samples are nearly independent and the path looks like noise. Near one, the path wanders slowly, because each value inherits most of the last.

The Yule-Walker equations are the practical payoff. Measure the autocorrelation of some real data, put those numbers in, and the model coefficients come out by solving a linear system. Measurements in, model out, with no iteration and no guessing. That is exactly why this family of models dominates in practice.

Markov chains generalise the idea to states rather than values. The next state depends on the present one and on nothing earlier. That single restriction makes an enormous range of processes tractable, and these chains reappear in the coding and speech material.

Conversion to digital returns here as a source coding problem rather than a circuit one. Rounding a value to the nearest level introduces an error, and here that error is a distortion measure rather than a noise voltage. The question becomes where to put the levels so the distortion is least.

That is a grouping problem, and one algorithm answers it. Place some levels, assign every sample to its nearest, move each level to the centre of the samples assigned to it, and repeat. That is K-means, and it is the same algorithm used for grouping in machine learning. Noticing the connection is worth more than either use on its own.

Predictive coding is the idea underneath most compression. Predict the next value from what you have already sent, then transmit only the difference between the prediction and the truth. Because the signal is correlated, that difference is small, so it needs fewer bits. It is also less correlated than the original, which means there is less left to exploit, and that is the sign of a good prediction.

Images make it two-dimensional. A pixel is correlated with the ones above and to the left, so the same idea applies with a two-dimensional prediction.

Transform coding takes a different route to the same goal. Transform a block of the image into a domain where most of the energy lands in a few coefficients. The rest are small, so they can be represented coarsely or discarded entirely. That concentration is what actual image standards exploit, and seeing it derived rather than described is what stops image compression being a black box.

Multiresolution coding codes the image at several scales at once. A coarse version is sent first, then successive layers of detail. A viewer sees something immediately and it improves, rather than waiting for everything. It also means one encoded file serves a small screen and a large one.

What you should now be able to explain or do

Simulate the simplest correlated model and read its parameter from the sample path. Recover model coefficients from measured autocorrelation with the Yule-Walker equations. State the restriction that defines a Markov chain. Use K-means to place quantisation levels, and connect it to its other use. Explain predictive, transform and multiresolution coding, and say what each exploits.

Check yourself