next >

Greedy Block Matching Algorithms

Greedy algorithms attempt to reduce the number of matching criteria evaluations by shifting the centre of a search pattern immediately on finding a vector with a distortion lower than the current centre. Rather than progressively refining approximations of motion vectors by proceeding in the direction of minimum distortion, greedy algorithms proceed in a direction of less distortion. The step size is reduced when the minimum distortion is found to be the centre of the pattern. Because greedy algorithms are free to 'roam' around the search window their behaviour can be unpredictable. Greedy algorithms are less ambitious than non-greedy algorithms in that they continuously look for a better position rather than the best position. If the quadrant monotonic assumption applies to the data then greedy algorithms come to rest at the point of minimum distortion.
A selection of greedy algorithms are described here. They were tested to see how well they work. The results of these experiments are available on this site also.

Greedy Algorithm A

This algorithm begins with a step size equal to one half the maximum displacement permissible (s := (d+1) div 2 ). The position at the centre of the search [0,0] area is tested first, followed by the position s pixels to the right [+s, 0]. If the candidate block at this position has a lower distortion than that at the centre then this position becomes the new centre of attention.
If the candidate block does not have a lower distortion value than the centre then the candidate block at position [0, +s] is examined. The algorithm proceeds in this manner in an anticlockwise direction. If the block at the centre of attention proves to be the minimum then the step size is halved (s := (s+1) div 2) and the algorithm examines the position to the right of the centre.

Greedy Algorithm B

Greedy Algorithm B is similar to Algorithm A, except that at the initial step size is one quarter (s := d div 4) of the maximum permissible displacement. It is however halved during the subsequent stages as in Algorithm A.

Greedy Algorithm C

This algorithm is similar to A and B. The initial step size is one quarter (rounded up) of the maximum displacement (s := (d +3) div 4), and is quartered rather than halved when the minimum distortion is at the centre ( s := (s + 3) div 4).

Greedy Algorithms A, B, and C have a peculiar property. Whenever one of these algorithms finds a direction of lesser distortion it moves in that direction an amount equal to the stepsize. The search direction cycles regardless and so the next candidate block examined is in a different direction. It might be more efficient to continue looking in the same direction for a candidate block with lower distortion. Greedy Algorithms D and E do this.

Greedy Algorithm D

Algorithm D starts with a stepsize one quarter of the maximum allowable displacement (s := (d +3) div 4). As usual, the distortion function is evaluated for the block at the centre [0,0] of the search area. Next, the block to the right of the centre [+s, 0] is examined.
If the distortion value for this block is less than that for the centre then the position [+s, 0] becomes the focus of the algorithm’s attention. It is at this point Greedy Algorithm D differs from A, B, and C. The next position considered is that to the right [+2s, 0]. Algorithm C, for example, would have considered the position above the new centre [+s, +s] next. Greedy Algorithm D continues in this manner and changes direction only when the current direction proves unfruitful.
If the distortion at the position to the right of the centre [+s, 0] was greater than the distortion at the centre then the position above [0, +s] would be considered next and the search direction cycles anti-clockwise.
If the distortion at the points in all four directions is greater than that at the current position, then the step size is quartered (s := (s+3) div 4).

Greedy Algorithm E

This algorithm is similar to algorithm D in that it exhausts a direction of lower distortion before changing to another direction. The initial stepsize is one half the maximum permissible displacement (s := (d+1) div 2) and whenever the current centre is the point of minimum distortion the stepsize is halved (s:= (s+1) div 2) rather than quartered. As with all the other algorithms the directions are tested in an anticlockwise order starting with right, then up, left and down. That is, 3, 12, 9, and 6 O' clock respectively.

Greedy Algorithm F

The order in which the directions are pursued can have an impact on the performance of greedy algorithms. If all the motion in a scene is from right to left then the all the algorithms described above would be expected to perform well, since they check the positions to the right of the centre first. If all of the motion was from bottom to top however, they might not perform as well as they might had they checked the positions under the centre first.
This property could be exploited to produce a more efficient algorithm if it was known that motion from a particular direction was more common. It has been suggested that motion in a scene is more likely in a horizontal direction than a vertical [Chan94]. For this reason, Greedy Algorithm F examines vectors to the right and then vectors to the left and leaves those related to vertical motion (i.e. 6 O' clock and 12 O' clock) until last. The initial step size is one quarter the maximum displacement (s := (d +3) div 4) and is quartered when the minimum distortion is at the centre ( s := (s + 3) div 4).

Adaptive Greedy Algorithms

Given the importance of the preference for different directions it might be worthwhile to devise adaptive algorithms for which the preferred direction is determined dynamically. The preferred direction could be determined by experience of previous blocks and frames, and change as new data is encountered.

[return to sub-optimal BMAs part 2]

[Advanced Block Matching Algorithms]

© Colin E. Manning 1996