Bitrate and blocks

[cheyrn]

I'm reading Compression for great video and audio by Bill Waggoner and I am missing some key bit of the puzzle and apparently can't describe what I am confused about very well.

In the chapter about H264 it says that 4x4 blocks being available allow for edges to pass through fewer blocks and thus require less bitrate to encode a video signal.

The 2 parts I know I am confused about are block size and bitrate.

About blocks:

Does the picture of a path through the elements of a block mean that the driver or encoder "physically" puts values in those areas of a block, in that order, sort of analogous to blit of bits into a video buffer, but not left to right and top to bottom for some reason? If so, there are additional things I am confused about.

Does a block physically appear in a video buffer. So, for example, the "top left" of the video buffer would contain pixels matching a block in that location?

If it does map directly to a buffer or a rendering surface, wouldn't a smaller block mean that edges pass through more, not fewer, blocks?

About bitrate:

I can picture a sequence of frames fitting within a frame rate. What is bit rate? It's the number of bits used within some period of time. But, used how? How does bit rate relate to blocks? How does a smaller block mean that less bit rate is required for a similar rendering? Can you describe how (in what way) fewer bits within a period of time map differently to a block than more bits within a period of time?

[LoRd_MuldeR]

Simply put, and leaving P- and B-Frames aside for now, video compression works like this: First the frame will be broken down into blocks (e.g. 8×8 pixel), then each of these blocks is transformed into the frequency domain (using DCT (http://en.wikipedia.org/wiki/Discrete_cosine_transform) or a similar transform), then the resulting frequency coefficients of each block will be subject to quantization (http://en.wikipedia.org/wiki/Quantization_%28image_processing%29), and finally the quantized values are subject to entropy coding (e.g. Huffmann (http://en.wikipedia.org/wiki/Huffman_coding) or arithmetic coding (http://en.wikipedia.org/wiki/Arithmetic_coding)). For decompression, the inverse of these steps is performed, in reverse order. Note that, after the entropy coding stage, you end up with a certain number of bits, for each frame. The "bit rate" is simply the total number of bits of all frames within a certain time period - usually one second.

Now, why are we doing all this? The goal is to store the frames with as few bits as possible, i.e. the goal is to get the best possible compression. Or, equivalently, given a certain pre-defined bit rate, we want to retain as much quality as possible. Using those block-based transforms is advantageous in image and video compression, because an N×N pixel block requires N² distinct pixel values in the spatial domain, but in frequency domain it can usually be described with only a small number of (non-zero) frequency coefficients. Or in other words, after the transform into the frequency domain, you will usually notice that most energy is concentrated in a few frequencies, while all the other frequencies are zero, or at least very close to zero. That's why most frequency coefficients can safely be discarded (i.e. truncated to zero) without hurting the image quality too much. And that is where you actually save bits in image/video compression!

Last but not least, larger blocks are generally more efficient if the image is "flat", while smaller blocks are beneficial if the image contains a lot of "detail" or "edges". You can think of it like this: A "flat" region can easily be described by one large block. Transmitting several smaller blocks would be inefficient in this case. But as soon as we have a highly "detailed" region, describing the whole thing with a single block becomes too difficult. Now it is more efficient to split this region into several smaller blocks and transmit them separately. Note that modern video formats can choose between different block sizes - even within one frame - so each area of the frame can be encoded as efficiently as possible (with the most suitable block size).


http://img.tomshardware.com/us/1999/09/24/video_guide_part_3/dct.gif

[cheyrn]

I take it that a block is like a block of pixels.

Does "frequency domain" mean movement? For example, change within some region of the image? As opposed to a spatial dimension of something with that region?

How does smaller block size being available to the encoder mean that a lower bitrate is required?

What do you think the book I referred to means when it says that edges have to pass through fewer blocks when 4x4 blocks are available?

[Sharc]

Does "frequency domain" mean movement? .......

No. A signal can be described in the "time domain" (signal amplitude versus time) or in the "frequency domain" as a sum of sinusoids with their magnitudes and phase angles, for example. The two domains are related by a "transform". A well known transform is the Fourier Transform, for example.
http://en.wikipedia.org/wiki/Frequency_domain

Or applied to 2D image/video compression:
http://en.wikipedia.org/wiki/Discrete_cosine_transform

[LoRd_MuldeR]

Does "frequency domain" mean movement? For example, change within some region of the image? As opposed to a spatial dimension of something with that region?

Nope. The exactly same information can be represented either in the spatial/temporal domain, or in the frequency (spectral) domain. The information is exactly same, simply expressed in a different way. However, the frequency representation is usually advantageous for compressing the data. That's why pretty much all (lossy) audio, image and video compression algorithms operates in frequency domain. I think this is more easy to understand for audio data, because everybody has an idea what a "frequency" means for an audio signal. Here is a nice animation that shows how an audio signal, from temporal domain, is decomposed into its frequency spectrum:

http://i.stack.imgur.com/27HVo.gif"]http://i.stack.imgur.com/27HVo.gif


But this works with 2D image data (and even 3D data) just as well! Each N×N pixel block, which consists of N² distinct pixel values in spatial domain, can be expressed as a linear combination (http://en.wikipedia.org/wiki/Linear_combination) of certain base functions in frequency domain. You can think of each of these base functions as a particular "pattern" that covers the whole N×N block. All of these patterns will then be "blent" together in order to form the final N×N block. And each pattern has a corresponding frequency coefficient (or "weight"), which describes how much the individual pattern contributes to the overall result. It probably becomes more clear with an example, so here are 8×8 DCT base functions (or "patterns") use by JPEG:

http://upload.wikimedia.org/wikipedia/commons/2/23/Dctjpeg.png

Every possible 8×8 pixel block that may exist in an image can be represented as linear combination of the 64 patterns shown above. If you determine the coefficient (weight) for each pattern, you get the block's frequency spectrum.

See also:
http://en.wikipedia.org/wiki/Discrete_cosine_transform#Example_of_IDCT


How does smaller block size being available to the encoder mean that a lower bitrate is required?

As said before, large blocks are good for "flat" images. That's because you can describe a large region of the image with only a single block. Still, because the image is "flat", the energy will be concentrated in only a few frequency coefficients. But this no longer works well, as soon as the image contains a lot of "detail" or "edges". In this particular case, a large block will simply be too "coarse" to efficiently describe the image content. So, in this particular case, it will be more efficient to break down the image into several small blocks. An here "more efficient" means that you will end up with more zero (or close-to-zero) coefficients. Which ultimately means that you will end up with fewer bits - after the entropy coding (http://en.wikipedia.org/wiki/Entropy_encoding) stage.

[cheyrn]

... it will be more efficient to break down the image into several small blocks. An here "more efficient" means that you will end up with more zero (or close-to-zero) coefficients. Which ultimately means that you will end up with fewer bits - after the entropy coding (http://en.wikipedia.org/wiki/Entropy_encoding) stage.

So, given randomish video noise, after entropy encoding, the total number of bits required to encode all blocks within one frame will be less with a smaller block size than with a larger block size because more coefficients will be redundant and can be discarded?

Then within a rate that means a lower bitrate is required.

[LoRd_MuldeR]

So, given randomish video noise, after entropy encoding, the total number of bits required to encode all blocks within one frame will be less with a smaller block size than with a larger block size because more coefficients will be redundant and can be discarded?

If your video was just random (e.g. "white") noise, then after the frequency transform, there would be equal energy (more or less) in all the frequencies. That's why noisy video is generally very "difficult" to compress - which means you will need to spend a large number bits to retain the information. Fortunately, "real" video is not just random noise, but much more "friendly". Anyway, applying a denoise filter prior to encoding saves bits. (or more precisely: it improves compression).


Then within a rate that means a lower bitrate is required.

Keep in mind that video encoding is always a trade-off between quality and bitrate. You can always lower the bitrate as much as you want - simply by discarding more information in the quantization stage - but that unavoidably hurts quality! So "better compression" means that you can either get away with fewer bits at the same quality, or, equivalently, that you can retain better quality at the same number of bits. Therefore it's all about improving compression as much as possible.

(And, depending on the image content, "smaller" or "larger" blocks may be the better choice with respect to compression efficiency)