Experimental Method

This page describes the experiments on which the conclusions about BMAs are based.

Input Data

Because the performance of a video compression algorithm is heavily dependent on the video being coded three different sequences were used to test the algorithms. All the sequences were 8-bit monochrome images of 160 x 120 pixels per frame. The image sequences were subsamples of 720 x 486 interlaced sequences, known as Flower Garden, Table Tennis and Football.

"Garden" was a sequence of 99 images and was different from the other two in that the motion between frames was due to camera movement rather than motion of objects within the scene. As the camera tracked from right to left, a tree in the foreground appeared to move from left to right and in doing so occluded some areas and uncovered other areas of the background. Otherwise the scene was, for the most part, motionless. The Garden sequence also differed from the other two in that the image content was very detailed.

"Tennis" was a sequence of 39 images from a Table Tennis match. The sequence showed the arm and paddle of one player as the ball bounced off the paddle. There was relatively little motion, except for the movement of the ball in the air, and very little new data entered the scene from frame to frame. For the latter third of the sequence the camera zoomed out slowly.

"Football" was a sequence of 60 frames from an American football game in which the University of California at Berkeley played Washington State University (I think!). There was considerable motion in the sequence. Several players entered the scene from both sides and fell over each other. Individual frames exhibited some blurring where there was fast movement.

Sequence Coding

To quantitatively assess the block matching algorithms, each frame of the sequences (except the first frame) was reconstructed using only blocks that were copied from its immediate predecessor. Although coding of frames in this manner, known as pure block matching, is rarely used in practice, it is very useful for evaluating block matching algorithms since an algorithm’s performance can be examined in isolation from other factors. This technique was also used by other researchers. The number of times the performance criteria (e.g. MSD, MAD, PDC) was evaluated was recorded and used as a measure of complexity.

Analysis of Output

Each of the approximated frames was compared to the original frame in order to evaluate the quality of the approximation. There are a number of quantitative comparison criteria including Mean Square Error (MSE) and Signal to Noise Ratio (SNR). For these experiments MSE was used to evaluate the quality of the output
The MSE for a pair of images (F and G) of width p and height q pixels is defined as

where F[a,b] is the value of the pixel in the a^th column and b^th row of frame F. Thus the results provided a comparison of computational complexity versus quality.



Limitations of this Experimental Method
Block matching algorithms usually operate in conjunction with other compression techniques. Results obtained from the experiments provide only an indication of how a particular block matching algorithm works. The experiments do not reveal how a block matching algorithm will operate in conjunction with the other techniques as part of a complete video compression system.

In addition, the MSE is an adequate quantitative measure of image difference, but it cannot reflect the qualitative differences that human viewers perceive. The relationship between the MSE and perceived quality is complex. It can be used only as a relative measure of quality and not an absolute one. An image with twice the MSE of an other cannot be said to be "half as good" as another. It can only be said to be worse. This must be considered when comparing block matching algorithms. It is worth noting again that the images used were 160 pixels wide by 120 pixels high. This is quite smaller than the digital video used in most applications and so this size should be considered if applying the conclusion to other scenarios.


[Experiments and Results]

© Colin E. Manning 1996