Two-D Logartihmic Search
The Two Dimensional Logarithmic search (TDL), introduced by Jain & Jain in 1981, was the first block matching algorithm to exploit the quadrant monotonic model to match blocks [Jain81]. The multi-stage search is accomplished by successively reducing the search area during each stage until the search area is trivially small. The TDL has several stages.Stage 1
If the maximum displacement allowable is d, then the step size s is equal to
, where 
is the smallest integer less than x. The block at the centre of the search area and the four candidate blocks a distance s from the centre on the x and y axes are compared to the target block to determine which is the best match. The five positions form a pattern similar to the five points of a Greek cross (+). Thus if the centre of the search area is at position [0,0] then the candidate blocks at position [0,0], [0,+s], [0,-s], [-s,0], and [+s,0] are examined.Stage 2
If the position of the best match is at the centre [cx,cy] then the step size s is halved. If the best match is in one of the four outer positions, then that position becomes the centre point of the next stage. That is [cx,cy] := [a,b] where [a,b] is the position of the best match.
Stage 3
If the step size s is equal to one then all nine blocks around the centre position are examined and the best match of these is determined to be the best match for the target block. That is [cx-1,cy-1], [cx-1,cy], [cx-1,cy+1], [cx,cy-1, [cx,cy], [cx,cy+1], [cx+1,cy-1], [cx+1,cy], and [cx+1,cy+1] are examined, and the algorithm halts.
Otherwise (step size greater than one) the candidate blocks at positions [cx,cy], [cx+s,cy], [cx-s,cy], [cx,cy+s], and [cx,cy-s] are compared. The algorithm goes to stage 2.
All blocks outside the search area are deemed to have distortion function values of +infinity, and thus are never chosen.
