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

170 Chapter 7. Reduced-Complexity Motion Estimation Techniques

in faster rejection of more candidates and consequently will achieve higher
speed-up ratios. However, the partitions must be chosen carefully to minimize
the overhead calculations. In Ref. 164 two partitions are proposed. For an
N × N block, the )rst partition produces N subsets, each being one of the N
rows of the block, whereas the second partition produces N subsets, each be-
ing one of the N columns of the block. Again, this algorithm has similarities
with the fast-search VQ algorithm presented in Ref. 47.

7.8 A Comparative Study

This section presents the results of a study comparing the categories of reduced-
complexity motion estimation techniques discussed in Sections 7.3–7.7. The
main aim of this study is to provide the reader with a feel of the relative
performance of the discussed categories. Particular attention is given to the
tradeo- between computational complexity and prediction quality.
In this study, one representative of each category was chosen. All simulated
algorithms use 16 × 16 blocks, SAD as the distortion measure, ± 15 maximum
displacement, full-pel accuracy, restricted motion vectors, and original refer-
ence frames. The simulated algorithms are:

FSA This is a full-search algorithm.
TDL This is the two-dimensional logarithmic search of Jain and Jain [54].
The algorithm is discussed in Section 7.3 and described in detail in the
appendix, Section A.2.
SDM This algorithm uses a 4:1 subsampling of the matched blocks to reduce
the complexity of calculating the distortion measure. The subsampling
pattern used corresponds to pattern A described in Section 7.4. This pat-
tern consists of all pels labeled a in Figure 7.2(a).
SMF This is the subsampled motion )eld algorithm of Liu and Zaccarin [157].
The algorithm is discussed in Section 7.5.
HME This is a three-level hierarchical motion estimation algorithm. The
algorithm is described in Section 7.6 and illustrated using Figure 7.4.
PDE This is the partial distortion elimination algorithm described in Section
7.7. In order to reduce the overhead of logical operations, the condition to
reject a given candidate is tested after accumulating the BDM of each row
of the block (rather than after each pel of the block). The algorithm is
supported with a spiral-ordered search starting at (0; 0) and going outward
toward longer motion vectors.