next >

Exhaustive Search

If every possible candidate block within the search area is compared to the original target block, the distortion function is evaluated a total of (2dx+1)(2dy+1) times where dx and dy are the maximum displacements in the horizontal and vertical directions.
The maximum displacement d was used for both directions and an exhaustive search used to code all three sequences. The number of matching criteria evaluated was the same for each frame, but because some target blocks were close to the edge of the frame they had smaller search areas. Thus the average number of criteria evaluations per block is less than (2d + 1)2. As graph below illustrates, the number of criteria evaluations nonetheless increased dramatically as the maximum displacement increased.

Number of criteria evaluations per frame for exhaustive search as the maximum displacement increases.

However, this dramatic increase in complexity was not matched by a similar increase in image quality. The below shows the how the MSE for each sequence decreased as the maximum permissible displacement was increased.
As the search area widened more candidate blocks became available. The return from increasing the search area size diminished quickly and the decrease in the error slowed after an initial drop. This was most noticeable for the football sequence. Allowing objects to move only four pixels between frames was restrictive and resulted in high error. As the displacement increased, the ability of the BMA to track fast moving objects resulted in lower error. Beyond a certain point the better matches were not likely to be the result of tracking actual motion.

MSE of approximated frames generated by exhaustive search using various displacements.

The exhaustive search behaved very much as expected and little new knowledge was gleaned from these experiments. The MSE values for each displacement are very useful as best cases, by which to compare the quality resulting for other BMAs operating on the same sequence and search area.

[return to Experiments and Conclusions]

© Colin E. Manning 1996