11may: Motion Estimation

This page details the 3rd homework on motion estimation

Algorithm

The basic algorithm used for motion estimation is:

For each block of size bxb in the image

for each row within a window of width wxw of the block

for each column within a window of width wxw of the block

Match the candidate block

if (error < minerr) store this candidate as best match

find motion vector of the best match

Complexity

Let the image be NxM. Let us consider blocks of size bxb and windows of size wxw. Then there are (N/b)x(M/b) blocks in the image. We search wxw locations for the best match. Therefore for each block we do O(w²) amount of computations.

Therefore the total number of computations is: O(w²NM/b²). In general w is larger than b by a factor f, that is w = fb. Then the computations become of order O(NMf²).

Results

For block size = 16 and window size = 64 and frame number 2 in the football sequence:

The image below shows frames 2 and 1. We wish to encode frame 2 based on frame 1.

These images show the motion vectors and the predicted image

The image below shows the error for the motion compensated case and the simple difference case. Clearly the motion compensated image has less error, especially in the regions of boundaries of moving objects

For block size = 16 and window size = 64 and frame number 2 in the foreman sequence:

The image below shows frames 2 and 1. We wish to encode frame 2 based on frame 1.

These images show the motion vectors and the predicted image. Notice that the motion vectors are large near the face, as it has movement. Also the predicted image is quite blocky, but that is fine as it minimizes error.

The image below shows the error for the motion compensated case and the simple difference case. Clearly the motion compensated image has less error, especially in the face region which is moving

Analysis of results

As discussed earlier time taken for motion compensation depends on O(f²), where f = w/b.

Also we plot the MSE error wrt f²

Thus we see a linear relationship between time and f² as expected from the discussion earlier. Also error decreases with increase in f (as we expect error to decrease as window size grows, which in turn causes f to increase)