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

194 Chapter 8. The Simplex Minimization Search

They are provided here to show the performance of the SMS algorithm within
an object-based video codec.
Before proceeding to present the results, a description of object-based
motion estimation in the MPEG-4 veri:cation model [176] is in order. To
account for arbitrarily shaped objects, the standard block-matching algorithm
is extended to polygon matching. Macroblock-based repetitive padding is used
for the reference visual object plane (VOP). In other words, macroblocks that
lie on the VOP boundary are padded so that pels from inside the VOP are
extrapolated to the outside. For each 16 × 16 macroblock in the current VOP,
full-pel full search is used to :nd the motion vector that minimizes the SAD.
The SAD of the motion vector (0; 0) is reduced by a preset threshold to favor
this vector. A reduced search of ± 2 pels centered around the 16 × 16 motion
vector is used to :nd one motion vector for each of the four 8 × 8 blocks
within the MB. A decision is then made whether to use one motion vector or
four motion vectors per MB. A decision is also made whether to encode the
MB in INTRA or INTER mode. If INTER mode is chosen, the 16 × 16 (or
the four 8 × 8) vector(s) is=are re:ned to half-pel accuracy using a reduced
± 1=2-pel search centered around the full-pel vector. Motion vectors are re-
stricted within the bounding box of the VOP unless the unrestricted mode is
chosen. In this mode, the reference VOP is extended by repetitive padding in
all directions by the number of pels which equals the search range. Overlapped
motion compensation is similar to that of H.263.
In this set of simulations, four algorithms were tested: FS, SMS, NSS,
and diamond search (DS) [149, 150, 151] (which is adopted in the MPEG-
4 veri:cation model [176]). To ensure that the global minimum is found,
the threshold that favors the (0; 0) vector in the FS algorithm was set to
zero. The four algorithms were used only for the full-pel search. All other
operations (e.g., 8 × 8 ME, half-pel re:nement) remained the same. Original
reference VOPs were used instead of reconstructed VOPs. The unrestricted
motion vector mode was switched on. Table 8.5 gives more details about the
test conditions and the test sequences.
Table 8.6 shows the prediction quality in terms of mean absolute error per
pel (MAE=pel), whereas Table 8.7 shows the computational complexity in
6
terms of average searched locations per macroblock (locations=MB). Again,
the superior performance of the SMS algorithm is evident. Compared to NSS
and DS, the SMS algorithm provides the closest MAE=pel to that of FS, and
yet it has the least number of searched locations=MB.

6 The MAE=pel measure was calculated as follows. The minimum SADs over the whole VOP
were summed and then divided by the number of opaque pels in the VOP. The minimum SADs
in this case are those produced by the full-pel search.