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

138 Chapter 5. Warping-Based Motion Estimation Techniques

uncovered background. In fact, poor compensation of covered and uncovered
objects is one of the main disadvantages of the continuous warping-based
method. In particular, the method performs poorly whenever there are objects
disappearing from the scene because it can deform objects but cannot easily
remove them completely [111].
Another obvious disadvantage of the continuous warping-based method is
the lack of motion (eld segmentation. A number of methods have been pro-
posed to overcome this problem. For example, NiewFeg lowski and Haavisto [110]
use adaptive motion (eld interpolation to introduce discontinuities within the
nodal motion (eld. Adaptivity is achieved by switching between bilinear inter-
polation and nearest-neighbor interpolation of the nodal vectors at the vertices
of a patch. The latter interpolation method e>ectively splits the motion (eld
within the patch into four quadrants. A similar e>ect can be achieved by using a
hierarchical (e.g., quad-tree) motion-based adaptive mesh [109, 120, 115, 123].
It is interesting at this point to compare the computational complexity of the
preceding three algorithms. Table 5.2 compares the complexity of the three
algorithms in terms of encoding time per frame. The results were obtained
using the pro(ler of the Visual C++ 5.0compiler run on a PC with Pentium
100-MHz processor, 64 MB of RAM, and a Windows 98 operating system.
The results were averaged over 10runs, where each run was used to encode
the 8.33-frames=sFOREMAN sequence. Care should be taken when interpreting
the results as they depend heavily on the implementation and the hardware
platform.
The BMA requires about 2.16 seconds=frame. Most of this time (about
1.76 seconds) is consumed by the full-pel full-search block-matching motion
estimation process.
The BMA-HO algorithm requires about 3.56 seconds=frame. This increase
of about 1.4 seconds over the BMA is due mainly to two reasons. The half-pel
re(nement stage and the associated bilinear interpolation process increase the
motion estimation time by about 0.98 seconds. In addition, the overlapping
process increases the motion compensation time by about 0.42 seconds.

Table 5.2: Comparison between BMA and WBA in terms of computational complexity
CPU time (in seconds) per frame
when encoding FOREMAN at 8.33 f.p.s
BMA BMA-HO WBA
BMA motion estimation 1.76 2.74 1.86
WBA iterative re(nement 0.00 0.00 116.00
Motion compensation 0.01 0.43 0.60
Others 0.39 0.38 0.37
Total 2.16 3.56 118.83