If the position of the best match is at the centre

If the step size

Otherwise (step size greater than one) the candidate blocks at positions

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)]

[return to sub-optimal BMAs part 2]

[Three Step Search (TSS)]

© Colin E. Manning 1996