Page 186 - Video Coding for Mobile Communications Efficiency, Complexity, and Resilience

Section 7.4. Techniques Based on a Reduced-Complexity Block Distortion Measure 163

the distance between the search locations gives a step size of 1, this indicates
that this is the )nal step in the search. In this )nal step, BDM is evaluated at
the minimum from the previous step and also at its eight nearest neighbors.
In the given example, the )nal motion vector is (+2; −3).
Since the introduction of the TDL search, a large number of similar algo-
rithms have been proposed. Examples are the three-step search (TSS) [145],
the one-at-a-time search (OTS) [146], the conjugate-directions search (CDS)
[146], the cross-search algorithm (CSA) [147], the genetic motion search
(GMS) [148], and the diamond search (DS) [149–151], to mention a few.
The appendix gives a detailed description of some of these algorithms.
Compared to other techniques, this category of techniques provides a rela-
tively high speed-up ratio and has, therefore, received most of the attention.
However, as is shown later, the unimodal error surface assumption does not
always hold true, and such algorithms can easily be trapped in local minima,
resulting in a suboptimal prediction quality.

7.4 Techniques Based on a Reduced-Complexity
Block Distortion Measure

In this category, reduced-complexity is achieved by employing a reduced-
complexity BDM. As already discussed in Chapter 4 (Section 4.6.1), most
implementations prefer the SAD measure, due to its reduced-complexity and
good prediction quality. A number of other reduced-complexity BDMs have
also been proposed in the literature. Examples are the pel di*erence classi-
+cation (PDC) [152], the minimized maximum (MiniMax) error [153], the
reduced-bits mean absolute di*erence (RBMAD) [154], integral projections
[155], and one-bit=pixel [156], to mention a few. Most of these measures were
designed speci)cally for e cient hardware and VLSI implementation, but their
prediction quality is not as good as the SSD or the SAD measures.
Another type of algorithms in this category reduces the complexity of the
BDM by subsampling the matched blocks. Obviously, since only a fraction of
the pels is used in the matching process, this category does not guarantee to
)nd the best match, even when combined with full search. Koga et al. [145]
subsample the matched blocks by a factor of 2 both horizontally and vertically
(i.e. 4:1 subsampling), reducing the complexity of the BDM by a factor of 4.
Instead of using a uniform subsampling pattern, Liu and Zaccarin [157] use
alternating subsampling patterns. The patterns are alternated over the searched
locations in such a way that e-ectively all pels of a block contribute to the
matching process. This method is illustrated in Figure 7.2. Figure 7.2(a) shows
an 8 × 8 block of pels. Four 4:1 subsampling patterns are de)ned in this block.
For example, subsampling pattern A consists of all pels labeled a in the block.