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; (2) the number of match operations to be performed for each block is(2P + 1)2; (3) the number of point operations per match operation is B2; and (4) frame rate is f frames per second. Thus, the number of operations per second is (W/B) × (H/B) × (2P + 1)2 × B2 × f = W × H × (2P + 1)2 × f. For example, consider a video transmission with parameters: W = 720 pixels, H = 576 pixels, B = 16, P = 8, and f = 30 frames/second. Such moderate settings require 3.6 billion operations each second.