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

Section 5.4. Discussion 139

The WBA requires about 118.83 seconds=frame. This is a huge increase
over both the BMA and the BMA-HO algorithms. This increase is due mainly
to the iterative procedure used to re(ne the initial nodal vector estimates.
Remember that in each iteration, for a single node to be re(ned, spatial trans-
formation and bilinear interpolation have to be used to compensate the four
patches connected to the node. There are a number of methods that can be
used to alleviate this complexity. Examples are the use of fewer iterations per
1
frame, the use of a line-scanning technique to perform the spatial transfor-
mation, the use of a simpler interpolation method (e.g., nearest neighbor) or
the use of a noniterative motion estimation algorithm, e.g. Ref. 130. Most of
these methods, however, reduce the computational complexity at the expense
of a reduced prediction quality.

5.4 Discussion

Block matching methods have always been criticized because of their sim-
ple uniform translational model. The argument against this model is that, in
practice, a block can contain multiple moving objects and the motion is usu-
ally more complex than simple translation. The shortcomings of this model
may appear as poor prediction quality for objects with nontranslational motion
and also as blocking artefacts within motion-compensated frames. Warping-
based methods employing higher-order motion models have been proposed in
the literature as alternatives to block-matching methods. This chapter inves-
tigated the performance of warping-based methods and compared it to that
of block-matching methods. The results of this comparison have shown that
despite their improvements over basic block-matching methods, the use of
warping-based methods in applications like mobile video communication may
not be justi(able, due to the huge increase in computational complexity. In
fact, similar (if not better) improvements can be obtained, at a fraction of
the complexity, by simply augmenting basic block-matching methods with ad-
vanced techniques like subpel accuracy and overlapped motion compensation.
One can argue that warping-based methods can also bene(t from subpel accu-
racy and overlapped motion compensation, as shown in Refs. 113 and 117, but
again this will further increase complexity. In addition to their high computa-
tional complexity, warping-based methods can su>er from warping artefacts,

1 Once the motion vector of a pel (x; y) within a patch is interpolated from the four nodal
vectors at the vertices of the patch, it can be shown that the motion vectors of the next pel in
the line (x +1;y) and the next pel in the column (x; y + 1) can be obtained by adding a simple
update term. This is known as line scanning [107].