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

132 Chapter 5. Warping-Based Motion Estimation Techniques

common vertex between six patches forming a hexagon. The algorithm is
almost identical to that of Sullivan and Baker (described earlier). In this case,
however, a BMA-type algorithm is (rst used to provide a coarse estimate
of the motion (eld, and the iterative approach is then used to re(ne this
estimate. In addition to the exhaustive local search, they also propose a faster
but suboptimal gradient-based local search. Similar gradient-based approaches
have also been used by Wang et al. [123, 126] and Dudon et al. [124].
Altunbasak and Tekalp [125] (rst estimate a dense (eld of motion displace-
ments. Then they use a least squares method to estimate the nodal motion
vectors subject to the constraint of preserving the connectivity of the mesh.
They show that the performance of this algorithm is comparable to that of
HMA, with the advantage of reduced computational complexity.
When estimating a nodal motion vector, it is very important to ensure
that the estimate does not cause any patch connected to the node to become
degenerate (i.e., with obtuse angles and=or Dipover nodes). To accomplish this,
Wang et al. [123, 126] limit the search range to a diamond region de(ned
by the four surrounding nodes, whereas Altunbasak and Tekalp [125] use a
postprocessing stage where an invalid estimate is replaced by a valid estimate
interpolated from surrounding nodal motion vectors.
All the foregoing algorithms assume a continuous motion (eld. Ghanbari
et al. [119, 120, 115, 117] use quadrilateral patches with a discontinuous
motion (eld. In this case, the four vertices of each regular patch in the current
frame are displaced combinatorially (i.e., perturbed) to (nd the best-match
deformed patch in the reference frame. The computational complexity of this
8
algorithm is extremely high since there are (2d m +1) possible deformed
patches in the reference frame. In addition, each possible patch must (rst be
warped to calculate the distortion measure. To reduce complexity, they propose
to use a fast-search algorithm, e.g. Ref. 129.

5.2.7 Motion Compensation Method
Having obtained nodal motion vectors, there are two methods of performing
motion compensation.
In the (rst method, for each patch in the current frame, the coordinates of
its vertices and those of the matching patch in the reference frame are used
to set up a number of simultaneous equations. This set is then solved for the
motion parameters {a i } of the underlying motion model. For example, assume
a mesh of quadrilateral patches and a bilinear motion model. If the spatial
coordinates of the top-left, top-right, bottom-left, and bottom-right vertices of
the patch in the current frame are (x A ;y A ), (x B ;y B ), (x C ;y C ), and (x D ;y D ),
respectively, and the corresponding estimated motion vectors are d A , d B , d C ,
and d D , respectively, then the spatial coordinates of the matching vertices in