Algorithms and Parallel Computing

16.2 FBMAS

Figure 16.1 shows the main aspects of motion estimation. An intermediate image frame is divided into B × B macroblocks. Usually, B = 8 or 16. We choose a system of coordinates such that the i-axis points to the right and gives the pixel position in a line, and the j-axis points downward and gives the position of the line in the video frame. In a sequence of frames, the current frame is predicted from a previous frame, known as the reference frame. The block to be matched in the current frame is referred to as the current block. The current block is compared with other reference blocks in the reference frame using a search area (window) with size (2P + B) × (2P + B), where typically, P = 8 or 16 pixels. Once a good match is found, the difference information is coded along with a motion vector that describes the offset of the best match with respect to the block being encoded.

Figure 16.1 The reference block (gray) and the current block (white) in the current frame. The extent of the search area and the motion vector is indicated.

The full-search algorithm is generally preferred for motion estimation since it is simple, although it requires a prohibitive amount of computations. The required number of operations per second can be calculated as follows: (1) the number of blocks per frame is (W/B) × (H/B), where W and H are the frame width and height in pixels, respectively; ...