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

198 Chapter 8. The Simplex Minimization Search

(Section 8.3). Algorithm MR-3DSM, however, is based on a three-dimen-
sional version (N = 3 in Figure 8.2). A 3-D version of SMmust be
initialized with four locations de:ning an initial simplex in the search
space. For the MR-3DSM algorithm, this is achieved as follows. For
each block in the current frame, the initialization procedure described in
Section 8.4.1 is applied individually to each frame in the multiframe mem-
ory. This will generate three initial vertices from each frame. The best
four vertices, in terms of BDMvalue, are selected from this set of 3M
vertices. A procedure similar to that described in Section 8.4.1 is used to
ensure that the four vertices form a nondegenerate simplex. This simplex
is used to initialize the 3-D version of SM, where the third dimension
here is the temporal displacement. The same criterion described in Sec-
tion 8.4.3 is used to terminate the algorithm, with the added condition
that the four vertices of the !nal simplex must have the same temporal
displacement.

8.6.2 Simulation Results

The multiple-reference SMS algorithms were tested using the luma compo-
nents of the three QSIF sequences AKIYO,FOREMAN, and TABLE TENNIS with
full-pel accuracy, blocks of 16 × 16 pels, a maximum allowed displacement of
± 15 pels, SAD as the distortion measure, restricted motion vectors, and orig-
inal reference frames. In addition to the multiple-reference SMS algorithms,
the single-reference full-search (SR-FS) and the multiple-reference full-search
(MR-FS) algorithms were also simulated. For the multiple-reference algo-
rithms, sliding-window control was used to maintain a long-term memory of
size M = 50 frames.
Tables 8.8 and 8.9 compare the performance of the simulated algorithms.
All results are averages over sequences with a frame skip of 1. Table 8.8 com-
pares the prediction quality in terms of average luma PSNR in decibels. The
7
di+erence in PSNR between each algorithm and the MR-FS algorithm is also
shown. Table 8.9, on the other hand, compares the computational complexity
in terms of average searched locations per frame. It also shows the speed-up
8
ratio of each algorithm with reference to the MR-FS algorithm.
It is immediately evident that the multiple-reference SMS algorithms pro-
vide signi:cant reductions in computational complexity compared to the MR-
FS algorithm. The SMS algorithms represent di+erent degrees of compromise
between prediction quality and computational complexity. At one extreme is

7 7PSNR = PSNR of fast algorithm − PSNR of MR-FS algorithm.
Searched locations for MR-FS algorithm
8 Speed-up = .
Searched locations for fast algorithm