Experiments and Conclusions

Some block matching algorithms select better matches than others and thus the resultant frames are of higher quality. In order to find matching blocks, some algorithms evaluate more candidate blocks than others and so are more complex. One might expect that the more candidate blocks an algorithm considers, the higher the quality of the resulting frame, but, in reality, the relationship is not so simple.
As part of an Masters thesis for University College Cork, I carried out experiments on a number of block matching algorithms. The results of these expeiments are available on this site.

• Experimental Method
  Before using any of the results from these experiments you should find out how the experiments were conducted in order to understand the limitations of these methods.
• Block Matching Criteria
  Results of experiments on three distortion functions Mean Average Difference (MAD), Mean Suare Difference (MSE), and Pel Difference Classification (PDC) are available on this site. These expperiments investigated the behaviour of these functions.
• Comparison of Block Matching Algorithms
  The behavours of the following BMAs were investigated:
  
  • Exhaustive Search
  • 2-D Logarithmic (TDL) search
  • Three Step Search (TSS)
  • Orthogonal Search algorithm (OSA)
  • Cross Search Algorithm (CSA)
  • One at a Time Search (OTS) and
  • Greedy Algorithms - a - b - c - d - e - f
• Spatially and Temporally Depentant Algorithms
  In addition, spatially dependent and temporally dependent variations of some of these algorithms were tested to see if exploiting dependency improved their performance. Two types of spatial dependancy (Type A and Type C) were tested and one type of temporal dependancy.

A comparison of the performance of the algorithms relative to each other is also available at this site.

Conclusions

A number of conclusions can be drawn from the results of the experiments. The main lesson learned was that although the number of matching criteria evaluated by block matching algorithms is largely independent of the sequence coded, the success of the algorithms is heavily dependent on the sequence coded. The extent to which the conclusions drawn from the experiments can be applied generally to all video sequences is difficult to assess. Nevertheless a few points were sufficiently clear as to warrant highlighting and are likely to apply in general.

Matching Criteria

Use of the Mean Square Difference (MSD) matching criterion generates better quality sequences than the Mean Absolute Difference (MAD) criterion. The MAD matching criterion, in turn, produces better results than the Pel Difference Classification (PDC) criterion. The performance of the PDC criterion is heavily influenced by the choice of threshold.

Full Search

The exhaustive search is very computationally intensive and should only be used where

• the quality of the coded sequence is very important
• the search area is small
• processing power is not limited.

Matching Criteria Evaluations

The number of matching criteria evaluated by the algorithms (except for the OTS) is independent of the sequence coded. Most algorithms exhibit step behaviour, which should be exploited when choosing parameters for video coders.

Operative Range

Suboptimal algorithms have an operative range that depends on the data being coded. Beyond an algorithm’s operative range it fails to do productive work and this range can be vary between algorithms coding the same sequence. The size of the search area should not exceed the operative range.
The One at a Time Search can be used as an indicator of the operative range of other algorithms on the same sequence.

OTS

In addition, the (independent) OTS can safely be used beyond its operative range without affecting performance.

Cross Search
The Cross Search Algorithm works best with even displacement values. It produced sequences at costs and levels of quality that suggest it is of little use. That is, any sequence it produced could be generated either more cheaply or at higher quality by one of the other algorithms. It is impossible to say if this is generally the case.

Greedy Algorithms

Some of the Greedy Algorithms devised and tested offered competitive cost-quality performance and Greedy Algorithms warrant further investigation.
Using a small initial step size improved the performance of Greedy Algorithms. This might also improve the performance of some other block matching algorithms.
Greedy Algorithm E was the least successful of the Greedy algorithms.

Dependant Algorithms

Spatial Dependency (Type A) did not improve the performance of algorithms and in fact made most of them worse. Spatial Dependency (Type C) also failed to improve the algorithms’ performance but did not seriously hinder their performance. Temporal Dependency of the type tested failed to provide significant improvements in performance over the independent algorithms.

© Colin E. Manning 1996