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

Section 8.6. Simplex Minimization for Multiple-Reference Motion Estimation 199

Table 8.8: Comparison between di+erent block-matching algorithms in terms of prediction quality
(average PSNR Y in dB) with a multiframe memory of M = 50 frames and a frame skip of 1

AKIYO FOREMAN TABLE TENNIS
PSNR 7PSNR PSNR 7PSNR PSNR 7PSNR

SR-FS 45.93 −0:62 32.20 −1:77 32.17 −0:70
MR-FS 46.55 0.00 33.97 0.00 32.87 0.00
MR-FS=SMS 46.55 0.00 33.92 −0:05 32.80 −0:07
MR-SMS 46.55 0.00 33.87 −0:10 32.67 −0:20
MR-3DSM 46.55 0.00 33.51 −0:46 32.46 −0:41

Table 8.9: Comparison between di+erent block-matching algorithms in terms of computational
complexity (average searched locations=frame) with a multiframe memory of size M = 50 frames
and a frame skip of 1

AKIYO FOREMAN TABLE TENNIS
Locations Speed-up Locations Speed-up Locations Speed-up
SR-FS 65,621 45.90 77,439 45.90 65,621 45.90
MR-FS 3,012,200 1.00 3,554,700 1.00 3,012,200 1.00
MR-FS=SMS 103,820 29.01 183,240 19.40 134,270 22.43
MR-SMS 38,880 77.47 106,830 33.27 69,443 43.38
MR-3DSM 35,867 83.98 66,357 53.57 45,518 66.18

the MR-3DSM algorithm. Compared to MR-FS, the MR-3DSM algorithm pro-
vides signi:cant reductions in computational complexity (a speed-up ratio of
about 54 –84) at the expense of a moderate reduction in prediction quality
9
(about 0.41– 0:46 dB loss ). At the other extreme is the MR-FS=SMS algo-
rithm. It uses full search on the most recent reference frame in memory to
provide a prediction quality that is almost identical to that of MR-FS (about
0.05– 0:07 dB loss) and still achieves moderate reductions in computational
complexity (a speed-up ratio of about 22–29). Between the two extremes is
the MR-SMS algorithm. Compared to MR-FS, it achieves reasonable reduc-
tions in computational complexity (a speed-up ratio of about 33–77) with only
a slight loss in prediction quality (about 0.1– 0:2 dB loss). These observations
are further emphasized using Figure 8.11, which compares the performance of
the di+erent algorithms when applied to FOREMAN at di+erent frame skips.
A very interesting point to note (from Tables 8.8 and 8.9 and also
from Figure 8.11) is that the computational complexity of the multiple-
reference SMS algorithms is comparable to (and in some cases less than) that

9 This excludes the result for AKIYO where 7PSNR = 0.