How do the motion vectors work in predictive coding for MPEG?

Question

In MPEG, there is a process where an image is broken up into macroblocks and a motion vector is computed for each of those macro blocks. You then transmit these vectors, along with the prediction errors, to reconstruct the next image in the video sequence.

I'm trying to get a firm grasp on how this works. Each macroblock has a motion vector associated with it, which (if vector is [1,0]), says all the pixels in this block move 1 in the x direction and 0 in the y direction for the next frame. If all the motion vectors don't align correctly, won't this leave areas of the image unaccounted for (like the area where that macroblock was in the first place)?

For example, I have the following question I found.

Consider the following image at time t:

7   7   7   7           
7   7   5   5        
7   5   5   8         
8   8   8   8           
9   9   9   9       
9   9   9   9

This image was broken up into 2x2 macroblocks and the following motion vectors were sent along to recreate it:

(0,0)  (0,0)  (0,1)  (-1,1)  (0,0)  (0,0)

The image at the previous time step, t - 1, looked like this:

7   7   7   7           
7   7   5   4        
7   7   7   7         
7   5   8   8           
8   9   8   9       
9   9   9   9   

What were the errors transmitted?

How would you solve this?

Answer 1

To simplify your confusion - there two processes :

1. Motion estimation
2. Motion compensation

Before we talk about the estimation, we should talk about the Motion compensation.

Let say, the $ Image_{t}(x,y) $ is split in block $ Blocks_{t}[k](x',y') $.

The task of Motion compensation is to produce $ Blocks_{t}[k](x',y') $ from any region of $ Image_{t-1}(x,y) $.

Hence another block not necessarily aligned at 16x16 boundary is a best possible match $ Blocks_{t-1}[k](x'+mx,y'+my) $

Here, $ mx, my $ is called motion vectors.

We can calculate the error between the target and reference as

$$ Err_{t}[k](x,y) = Blocks_{t}[k](x',y') - Blocks_{t-1}[k](x'+mx,y'+my) $$

So now, the encoder basically transmits $Err_{t}[k](x,y)$ (with DCT and quantization) and $ {( mx, my) }[k] $ for each block,.

So encoder has 2 work to do:

1. Motion Estimation
The process or estimating $ { mx, my }[k] $ for every $ k $ such that $ Err_{t}[k](x,y) $ is minimized is called Motion estimation.

2. Generation of error image after Motion Compensation
The process of constructing $ Blocks_{t}[k](x',y') $ from $I_{t}$ image pixels and $ { (mx, my) }[k] $ is called Motion compensation. The error image is what gets transmitted.

Finally, decoder can re-do motion compensation on its' own using moiton vectors and the error image to make final re-construction of the image.

Now we realize a few points:

1. Best Motion estimation helps minimize the energy that is required to be transmitted and hence optimizes the bits for a given quality.

2. However, even if $ { (mx, my) }[k] $ is not ideal or if the scene has significant change over last picture, the $ Err_{t}[k](x,y) $ is always transmitted to receiver - hence the reconstruction is always perfect (modulo the loss created by the quantization). Hence, even if you have suboptimal motion vector or redundancy is not much, the reconstruction is still always perfect albeit with more bits!

3. Every block $ Blocks_{t}[k](x',y') $ is motion compensated on its own right - hence even if the actual motion vectors of any neighboring blocks has no effect in the construction. Hence, it is not necessary to have motion vectors perfectly aligned for perfect reconstruction to be possible.

4. Albeit algorithm exists who are smart enough to guess that if $Blocks_{t}[k]$ has motion vector $( mx ,my )[k]$ the guess for $Blocks_{t}[k+1]$ might just be closer to that only.

5. Finally suppose the next picture is completely different it is possible that energy for $$ Energy (Err_{t}[k](x,y)) > Energy ( Blocks_{t}[k](x',y') ) $$.

In such cases, it might be more advisable to transmit block directly without prediction than to send the difference. This is also possible in the encoder by a provision called INTRA block.

Answer 2

No, it won't leave holes, because the vector is from an unknown frame (P or B), to a known frame (I-frame). It reminds a little bit of how ot compute an image transformation - you use a backward transform to avoid holes/

Answer 3

As is the case with many standard signal processing routines, it's quite straightforward on paper and a little tricky in practice. You separated your image into six blocks $B(i,j)$ with $i = \{0,1,2\}$ and $j = \{0,1\}$. each of this blocks has coordinates at $(2i, 2j)$ (we consider top left corner of each to identify its location). We, therefore, now have six blocks at

(0,0) (0,2)
(2,0) (2,2)
(4,0) (4,2)

Your calculated motion vectors $M(i,j)$ for each block are

(0,0) (0,0)
(0,1) (-1,1)
(0,0) (0,0)

Now, to calculate the resulting image, we must first know where every block moved. To do that, we simply add the above coordinate matrix to its motion matrix: $B'(i,j)=B(i,j)+M(i,j)$. We get

(0,0) (0,2)
(2,1) (1,3)
(4,0) (4,2)

In order to avoid "holes" as you said, we don't simply move blocks of the original frame around to get the new one, we take the original one as a reference and inject the newly calculated blocks. To do this, we first make a copy of the original frame. We then take every $B'(i,j)$ and replace it with pixels of corresponding $B(i,j)$.

Note: We are not protected from any kind of overlapping of block "in motion" (two blocks are moved to overlapping locations). There are ways to handle that, but it's beyond the scope of this response. For now, we're just going to rewrite any pixels with a block we're moving to their location, so that even if there were blocks moved there previously, they will get overwritten.

Now, going block by block in the order you had in your question, we replace every $B'(i,j)$ by its corresponding $B(i,j)$. We get the followinf estimated frame $F_e$

7   7   7   7
7   7   5   7
7   7   7   8
7   5   5   8
8   9   8   9
9   9   9   9

The error $E$ is found between estimated frame $F_e$ and the one we're trying to predict $F$ is found by $E=F-F_e$ which we calculate to be

0   0   0   0           
0   0   0  -3        
0   0   0  -1         
0   0   3   0           
0   0   0   0       
0   0   0   0