Motion compensation

Visualized motion vectors of MPEG encoding over a still image from Elephants Dream . The movements of the various platforms and body parts of the figure are recognizable.

A number of algorithms are summarized under the generic term Motion Compensation or Motion Prediction , which are mainly used in video compression . The temporary relationships between adjacent individual images ("frames") are used to minimize the total amount of data to be compressed. Put simply, this means that image areas that look very similar across several individual images are not saved in a further copy, but only the change in their position compared to other images.

Simple compression processes only reduce unmoving parts of the image, for example the background in front of which a newsreader is sitting, or simple camera movements such as zoom , horizontal or vertical shift. Current video codecs , however, use more complex algorithms which can also compress moving image components accordingly. The direction of movement of an object is predicted and described by a movement or displacement vector . From then on, only the corresponding displacement vector has to be saved, which requires significantly less memory than the actual image data, which in some cases leads to enormous space savings.

In the end, only the first frame of the scene is completely saved. For the following individual images, only those image parts that were originally covered by the moving object then have to be newly stored. However, the complete image is usually re-saved at regular intervals in order to both increase the error tolerance and enable jumping back and forth within a video file .

functionality

Motion Compensation is based on the observation that a large part of the movement in images consists of a displacement of a picture element. The Motion Compensation takes every macroblock and compares it with all possible macroblocks that are formed by horizontal or vertical shifts in small steps. When the best match has been found, instructions are sent to the receiver to work with the contents of the macroblock and then move it to its new position using a motion vector. Instructions to the receiver instruct it to take the contents of a number of blocks in memory and move them to other places where a certain number of pixels are horizontally and vertically displaced.

The algorithm usually finds that the match of macroblocks is not perfect, so it encodes any changes and transmits them with the motion vector. It would not be enough to just move a picture element slightly horizontally and vertically if it rotates slightly. The difference between its previous pixels and its new pixels is encoded. In most cases this is only a small fraction of the total pixels. Most remain unchanged. The resulting instructions to the recipient include removing blocks from memory, modifying them slightly, and then moving blocks. When moved, parts will overlay other blocks and parts will be covered by other blocks. This information must also be transmitted. Holes in the image are created. They need to be filled. The different parts of the image can move in different directions by different amounts.

Motion compensation makes the encoder much more complex than the decoder, which is acceptable because there are many more decoding locations than coding locations.

Block Motion Compensation

Block Motion Compensation (BMC) is used in the MPEG-2 standard , among other things . In this method, each individual image is divided into n by n pixel blocks, which are compared with the previous image. If there is a similar image section, only the displacement vector around which this section moves is saved.

A block of pixels can also be interpreted as a matrix . Let B _{x, y} ∈ N ^{n × n be} a block of pixels of the current frame with the horizontal position n ⋅ x and the vertical position n ⋅ y. Let the matrix elements b _{i, j} be the pixels at the position (n ⋅ x + i, n ⋅ y + j), p _{i, j} corresponding to the pixels in the previous image. In order to find the displacement vector, one compares B _{x, y} with an image section in the previous image that has been shifted by the vector (u, v). An indicator for the difference d _{u, v} between the pixel block and the image section is the sum of the squared differences ("Sum of Squared Differences" or SSD):

${\ displaystyle d_ {u, v} = \ sum _ {i = 0} ^ {n-1} \ sum _ {j = 0} ^ {n-1} (b_ {i, j} -p_ {i, j}) ^ {2}}$

Other indicators would be, for example, the sum of absolute differences (SAD) or the cross-correlation . One calculates d _{u, v} for all displacements within a fixed neighborhood of B _{x, y} and chooses the vector (u, v) as the displacement vector , for which d _{u, v} ≤ d _max and is the minimum of all differences. If d _max = 0, then the original data stream can be completely reconstructed; if d _max > 0, the method no longer compresses without loss.

The BMC algorithm can be improved by using not only the previous one but also the following individual image to determine the displacement vector. In the meantime, further algorithms have been developed on the basis of "Block Motion Compensation" , some of which deliver significantly better results, for example Variable Block-Size Motion Compensation and Overlapped Block Motion Compensation .

Quarter Pixel Motion Compensation

The Quarter Pixel Motion Compensation (often only briefly Qpel , pixel Quarter or Q-Pel called) uses motion vectors of the accuracy of a quarter pixel . Qpel is used to better predict movements and thus produces better image quality or smaller file sizes.

Quarter Pixel Motion Compensation is part of the MPEG-4 ASP (optional) and AVC standard (mandatory) and is often used in conjunction with Global Motion Compensation ( ASP only ).

Global Motion Compensation (GMC)

Global Motion Compensation (GMC) is used in digital video compression , especially MPEG-4 (e.g. Xvid ). In contrast to block-based motion compensation , the movement between two individual images is described globally with an affine mapping . This means that movements that go beyond mere shifting, such as B. rotations or distortions are described. The goal of GMC is a better coding quality for fast moving scenes, such as B. Explosions. The use of GMC leads to a better image quality or a smaller file size, which, however, is paid for with a higher coding effort. GMC is a relatively new process that is not yet supported by all playback devices.

Individual evidence

^ ScienceDirect: Motion Compensation
^ Bernd Girod, Stanford University: Motion Compensated Coding

[1] ScienceDirect: Motion Compensation

[2] Bernd Girod, Stanford University: Motion Compensated Coding