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

Section 5.2. Warping-Based Methods: A Review 131

combination of backward tracking and (xed meshes, the use of the former is
not justi(ed, due to the huge increase in computational complexity [116].

5.2.6 Node-Tracking Algorithm
A simple method to estimate the motion of a node is to use a BMA-type
algorithm which minimizes the translational prediction error in a block centered
around the node. NiewFeg lowski et al. [111] use a modi(ed BMA with a large
block (21 × 21) centered around the node and a distortion measure designed
to give more weight to pels closer to the node. To reduce complexity, the
block is subsampled by a factor of 2:1 in both directions.
Although BMA-type algorithms are simple, they provide suboptimal per-
formance. First, they assume that the motion of a node is independent of the
motion of other nodes, and second, they assume that minimizing the transla-
tional prediction error minimizes the true prediction error. In practice, however,
both assumptions are not true. A node is a common vertex between more than
one patch. Consequently, the displacement of a node will a>ect all patches
connected to it. For example, with quadrilateral patches, the displacement of a
node a>ects the prediction quality within four patches connected to it. It fol-
lows that the choice of the motion vector of one node will a>ect the choice of
the motion vectors of other nodes. In addition, the true prediction error is the
error between the current frame and its warped prediction from the reference
frame. This is not equal to the translational prediction error.
Brusewitz [128] uses a BMA-type algorithm to provide coarse approxi-
mations for nodal motion vectors. An iterative gradient-based approach that
minimizes the true prediction error is then used to re(ne all nodal motion vec-
tors simultaneously. The computational complexity of the method is extremely
high. For example, if there are 100 nodes in the frame, the method requires
the inversion of a 200 × 200 matrix.
To reduce complexity, Sullivan and Baker [108] estimate the motion of one
node at a time. However, to take into account the interdependence between
motion vectors, an iterative approach is employed. In each iteration, the nodes
are processed sequentially. The motion vector of a node is estimated using
a local search around the motion vector from the previous iteration while
holding constant the motion vectors of its surrounding nodes. During the local
search, the quality of a candidate motion vector is measured by calculating
the distortion measure between all patches connected to the node and their
warped predictions from the reference frame. The local search is applied to
a node only if its motion vector, or the motion vector of at least one of its
surrounding nodes, was changed in the previous iteration.
Nakaya and Harashima [114] use a hexagonal matching algorithm (HMA).
The name is due to the use of triangular patches for which each node is a