What is the cause/use/reason for the blocks that show up in high compression videos?

Question

Be patient since I haven't worked with compression algorithms much so this may be obvious to some of you. Something I've always noticed when some streaming video starts to lag. I only realized I was curious when looking over this question:

http://stackoverflow.com/questions/891643/twitter-image-encoding-challenge/929360#929360

I'm not talking about the pixels themselves but rather the grid like layout that results from the compression. What sort of algorithm or technique is this indicative of? What can you tell me about it?

Answer 1

It's called Macroblocking.

Answer 2

Take a look at this Wikipedia article on MPEG-2. To quote a part of it:

Briefly, the raw frame is divided into 8 pixel by 8 pixel blocks. The data in each block is transformed by a discrete cosine transform. The result is an 8 by 8 matrix of coefficients. The transform converts spatial variations into frequency variations, but it does not change the information in the block; the original block can be recreated exactly by applying the inverse cosine transform.

In other words, the grid-like structure you see is a direct effect of this DCT being applied to the 8x8 blocks of pixels.

Answer 3

The rationale for blocks is linked to the location/frequency trade off. The image is divided into blocks before the compression in the spectral domain (DCT) so that the artefacts due to the compression are more localized. In standard JPEG, the blocks are of constant size on the whole picture. For more recent formats like JPEG2000, the blocks are adapted to the picture, using wavelets. I am not familiar with video formats details, but the rationale is the same.

This is the same phenomenon for audio coding (mp3): instead of computing the spectrum on the whole audio file, you split the file into some sections of a few samples (a few hundred generally for 44.1 kHz signals). And similarly, if there is corruption of the compressed data (network, corrupted file), you will hear noises which are due to missing windows.