Orthogonal Search Algorithm
The Orthogonal Search Algorithm (OSA) is an attempted hybrid of the 2-D logarithmic (TDL) search and three step search (TSS) [
Puri87]. The OSA has both a vertical and a horizontal stage, as illustrated in Figure 3.10. After the step size
s has been initialised to
(d+1) div 2, where
d is the maximum displacement, the centre block and two candidate blocks on either side of the x axis are compared to the target block. The position of minimum distortion becomes the centre of the vertical stage. During the vertical stage two points above and below the new centre are examined and the values of the distortion function at these three positions are compared. The position with the minimum distortion becomes the centre of the next stage. After one horizontal and vertical iteration the step size is halved if it is greater than one and the algorithm proceeds with another horizontal and vertical iteration. Otherwise it halts and declares one of the positions from the vertical stage the best match for the target block.
The orthogonal search algorithm (OSA) converging on a position of minimum distortion at [+6,+4]
[ return to sub-optimal BMAs
part 2]
[ One at a Time Search (
OTS)]
© Colin E. Manning 1996
