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

168 Chapter 7. Reduced-Complexity Motion Estimation Techniques

more homogeneous block-motion )elds and a better representation of the true
motion in the frame [159]. The latter property is particularly important for
motion-compensated interpolation.

7.7 Fast Full-Search Techniques

All the preceding categories reduce the computational complexity of the
BMME process at the expense of a suboptimal prediction quality. This cate-
gory, however, reduces complexity without sacri)cing prediction quality. It is
interesting to note that algorithms in this category are usually based on ideas
borrowed from the )eld of fast codebook search for vector quantization (VQ).
An example of the algorithms in this category is the partial distortion
elimination (PDE) algorithm. Assume that during a full search, the minimum
BDM calculated so far is BDM(i m ;j m ) at search location (i m ;j m ). Then the
BDM calculation of any subsequent search location (i; j) is stopped as soon
as the accumulated distortion exceeds BDM(i m ;j m ). This idea is very simi-
lar to the fast-search VQ method reported in Ref. 161. Clearly, initializing the
search at a location with the lowest possible BDM(i m ;j m ), achieves the highest
possible reduction in computational complexity. As already shown in Section
4.6.7, the distribution of the best-match location is usually center-biased (i.e.,
the vector (0; 0) has the highest probability, and longer vectors are less proba-
ble). Thus, the PDE algorithm is usually combined with a spiral-ordered search
starting at the origin of the search space and going outward in a spiral fashion.
This combination is employed, for example, in Telenor’s H.263 codec [144].
Another algorithm in this category is the successive elimination algorithm
(SEA) [162]. Again, this algorithm has similarities with the fast-search VQ
algorithm reported in Ref. 163. The SEA algorithm is based on the triangular
mathematical inequality given by
� �
� �
� k �
k
� �
� a i� ≤ |a i |; (7.1)
� �
i=1 i=1
where a i are arbitrary real numbers. Extending this inequality to the SAD
equation gives
� �
� �
� � � �
� |f t (x; y)|− |f t−Mt (x − i; y − j)| �
� �
� (x; y)∈B (x; y)∈B �
�
≤ |f t (x; y) − f t−Mt (x − i; y − j)|: (7.2)
(x; y)∈B