next >

To determine if exploiting redundancy in this way was useful each of the three sequences were coded using spatially dependent variations of the 2-D Logarithmic (TDL) search (variation N), Cross Search Algorithm (CSA), the Three Step Search (TSS-H), Greedy Algorithms C, E and F, the Orthogonal Search Algorithm (OSA), and One-at-a-Time Search (OTS). Each of these algorithms was implemented as before, except that instead of beginning the search at the centre of the search area, each algorithm began at the position predicted using spatial dependency. This prediction was calculated by taking the average of the motion vector of the block above the target block and the vector of the block immediately to the left of the target block.

The hraph above compares algorithm performance with and without using Spatial Dependency Type A. The two dependent algorithms that appear to be successful are the Greedy Algorithms F (left) and C (right).

For the most part, exploiting spatial dependency using technique A caused algorithms to evaluate more matching criteria in order to match blocks. From this it can be concluded that the predictions provided by this technique were more often incorrect than correct. This increased complexity could be forgiven if the resultant matches were of higher quality. It is afterall the quality per cost ratio that is important. Spatial Dependency of this type not only caused the algorithms to do more work, but resulted in matches of poorer quality. The failure of the dependent algorithms to cross the cost-performance barrier of the independent algorithms can be seen in the graph above and in this graph:

Performance of algorithms with and without using Spatial Dependency Type A.

There were a few exceptions however. Using spatial dependency in this fashion allowed some algorithms to find matches with fewer criteria evaluations. Although the MSE values in these circumstances were very high it does suggest that this technique might be useful where resources (processing power or time) are very limited and quality is not of primary importance.

The TSS achieved better cost-quality performance with the assistance of the spatial dependency and some dependent Greedy Algorithms performed well when coding the Garden sequence.

The behaviour exhibited by the OTS in these circumstances is also interesting. For both the Football and Tennis sequences the OTS did not level out at a particular point as it did when operating independently. In both cases the error and number of criteria evaluations increased with the displacement after initial lows. Thus it had an operative range when working despondently. For the Football sequence the dependent OTS outperformed the independent algorithm. This was not the case for the dependent algorithm operating on the Tennis sequence and the dependency caused the algorithm to perform worse. The spatially dependent OTS stabilised at a particular cost-quality level when coding the Garden sequence. It matched blocks more quickly than the independent OTS, but the matches were of lower quality. The performance of the dependent OTS compared to the independent algorithm is illustrated in the following two graphs.

Performance of OTS on Football sequence operating independently (IND) and using Spatial Dependency Type A (SDA).

Performance of OTS on Garden sequence operating independently (IND) and using Spatial Dependency Type A (SDA).

The graph below shows that for the most part the spatial dependency (Type A) did not improve performance when coding the Football sequence. At MSE values of about 450 the dependent algorithms did achieve a slight improvement over the independent algorithms. Figure 5.46 shows this region of the cost-quality curve in more detail. The spatially dependent OTS offered a slight improvement over the dependent OTS and the dependent Greedy Algorithms C and F offered cost-quality performance comparable to the independent Greedy Algorithms.

Performance of Independent and Spatially Dependent (Type A) Algorithms that coded the Football sequence.

When coding the Garden sequence, the dependent OTS required fewer matching criteria evaluations than the independent OTS but resulted in lower quality images. The performance of the Three Step Search was also improved by exploiting spatial redundancy when coding this sequence. For most of the algorithms however the spatial dependency not only failed to reduce the number of criteria evaluations required to match blocks but also resulted in lower quality images. One must conclude that although there were a few specific improvements, in general the spatial dependency failed to improve the performance of the algorithms and in fact made them perform worse. If the blocks were smaller relative to the moving objects, then exploiting spatial redundancy in this fashion might have been more successful.

Performance of spatially dependent and independent algorithms used to code Football sequence. (Detail of the graph above.)

[Return to Experiments and Conclusions]

© Colin E. Manning 1996