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

186 Chapter 8. The Simplex Minimization Search

Table 8.1: Initialization, termination, and re:nement tests
AKIYO FOREMAN TABLE TENNIS
PSNR (dB) Locations PSNR (dB) Locations PSNR (dB) Locations
Initialization test:
Random 45.93 1,634 31.32 1,890 31.28 1,647
Proposed 45.93 684 32.04 1,073 31.71 831
Termination test:
Threshold 45.93 904 32.06 1,396 31.73 1,082
Proposed 45.93 684 32.04 1,073 31.71 831
Re1nement test:
No re:nement 45.93 683 31.97 999 31.53 794
Proposed 45.93 684 32.04 1,073 31.71 831

3. Re1nement Test: Two cases were tested.
(a) Proposed Re!nement: The motion vector produced by SMis
re:ned by searching its eight nearest neighbors, as described in
Section 8.4.4.
(b) No Re!nement: No re:nement is performed.
Table 8.1 summarizes the results of the preceding tests. The results are
averaged over each sequence with a frame skip of 1. Prediction quality is
given in terms of average luma PSNR (dB), and computational complexity
is given in terms of average searched locations per frame. The results clearly
justify the use of the proposed initialization procedure, termination criterion,
and re:nement step.

8.5.1.3 Performance Evaluation
In addition to the SMS algorithm, :ve BMME algorithms were simulated:
the full-search (FS) algorithm, the two-dimensional logarithmic search (TDL)
[54], the cross-search algorithm (CSA) [147], the one-at-a-time search (OTS)
1
[146], and the N -steps search (NSS), which is the general form of the three-
steps search (TSS) [145]. In this case the number of steps in the NSS search
is set to N = 4 to give a maximum displacement of ± 15 pels. A detailed
description of these fast BMME algorithms is given in the Appendix.

1 The three-steps search starts with ± 4 pels in the :rst step, then ± 2 pels in the second step,
and ± 1 pel in the third step. This gives a maximum allowed displacement of ± 4 ± 2 ± 1= ± 7
pels. For larger search windows the number of steps must be increased. This is called the N -steps
search. For example, when N = 4, the search has 4 steps and the :rst step starts with ± 8 pels,
giving a maximum allowed displacement of ± 15 pels.