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.
The 2-D logarithmic (TDL) search converging on a position of minimum distortion. The points [0,+4], [+4,+4], [+6,+4] are the minima at each stage and finally [+7,+4] is chosen as the matching block. Numbers indicate the stage during which a candidate block is first evaluated.
Variations
Since the publication of Jain & Jain’s algorithm, it has been described differently by various authors. They differ in the way the step size is reduced. Nelson, among others, suggests that the step size should be halved after each stage of the algorithm [Nels93]. Netravali, on the other hand, describes the algorithm as requiring the step size to be halved only when the minimum is found at centre location (as per Jain & Jain) or at the edge of the search area (not used by Jain & Jain) [Netr88]. Both of these modifications cause the algorithm to converge on the matching block more quickly, by narrowing the search more frequently. Decreasing the search area when the minimum is found at the boundary of the search area can be shown to sometimes fail to find as good a match as the unmodified form would. This can happen even when a perfect quadrant monotonic data set is assumed.
[return to sub-optimal BMAs part 2]
[Three Step Search (TSS)]