next >

Matching Criteria

The choice of matching criteria is important since block matching might require the distortion function to be evaluated many thousands of times. Block matching algorithms vary in complexity. The MSD, for example, requires many multiplications whereas the MAD primarily uses additions. While multiplication might not have too great an impact on a software coder, a hardware coder using MSE could be significantly more expensive than a hardware implementation of the MAD function.

If all matching criteria resulted in compressed video of the same quality then, of course, the least complex of these would always be used for block matching. However matching criteria often differ on the choice of substitute for the target block, with consequent variation in the quality of the coded frame.

The football sequence was used to compare matching criteria. MAD, MSD and PDC (with a variety of thresholds ranging from 1 to 90) were used as matching criteria to produce motion compensated approximations of each frame using the experimental method described. Each of the approximations was then compared to its counterpart in the actual sequence and the Mean Square Error calculated.


The results of the experiments, illustrated here, show different MSE values for approximated frames from the Football sequence produced by the MSD, MAD, PDC (thresholds of 20, 25, and 30) matching. Some frames proved more difficult to code than others. Perhaps this was because good matches for the target blocks in these frames were not available in the frames' predecessors and so less than ideal blocks were used to build each frame's approximation. It is noteworthy that all the matching criteria had problems with the same frames, but some matching criteria produced better approximated frames.
It is clear that the MSD has the best matching capabilities and that the MAD is superior to the PDC criterion.


Above: PDC threshold versus MSE of Compressed Football Sequence

The graph above shows the results for all the thresholds tested with PDC. Of thresholds tested, 20 and 25 were the best choices. It is possible that some value between these was optimal, but the mean square errors for these values was so close that further investigation was unwarranted.
The choice of threshold has a great impact on the effectiveness of the Pel Difference Classification distortion function, but the best threshold for one sequence is not necessarily optimal for another sequence. Nelson tested a variety of thresholds on three sequences and found 5, 15, and 25 were optimal depending on the sequence [Nels93]. Chan et al. experimented with this PDC and found its performance varied depending on the type of motion in the video sequence. They suggested that smaller threshold values perform better than larger ones where the motion in the sequence is slow and that the inverse is also true [Chan94].

Gharavi & Mills found that PDC performed marginally worse than MSD, but significantly outperformed MAD [Ghar90]. The results from the experiments conducted for this thesis did not bear this out. This could be the result of a number of factors. Firstly every sequence is different and can produce different results. The two sequences used by Gharavi & Mills produced quite different results, although PDC outperformed MAD in both cases. Gharavi & Mills’ results are based on images of sizes 360x288 and 256x240, whereas the football sequence is of size 160x120 pixels. The two most significant factors however are threshold and block size. Since Gharavi & Mills did not provide a mechanism for determining the optimal threshold t their results are difficult to reproduce. As Figure 5.4 shows, the value of t cannot be arbitrary. The difficulties PDC has in distinguishing good matches from bad are compounded by small block sizes. Block size is perhaps the most significant difference between the experiments using the football sequence (with block size of 8x8) and Gharavi & Mills’ sequences (compressed using blocks of 16x16 pixels). The MAD and MSD matching criteria are not sensitive to the block size in the same way.

[Experiments and Conclusions]

© Colin E. Manning 1996