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

188 Chapter 8. The Simplex Minimization Search

Table 8.4: Comparison between di+erent block-matching algorithms in terms of motion overhead
AKIYO FOREMAN TABLE TENNIS
Motion bits 7Bits Motion bits 7Bits Motion bits 7Bits
FS 177 0 388 0 279 0
SMS 177 0 358 −30 247 −32
NSS 177 0 457 +69 290 +11
TDL 177 0 394 +6 269 −10
CSA 177 0 461 +73 281 +2
OTS 177 0 388 0 246 −33

speed-up ratios, but their prediction quality deteriorates for sequences with
medium to high movement content. In the second class, the NSS and the
TDL algorithms provide better prediction quality than CSA and OTS, but
at the expense of a higher computational complexity. In the third class, the
SMS algorithm provides the best compromise between prediction quality and
computational complexity. Its prediction quality is the closest to that of FS
and yet its computational complexity is between those of the other two classes.
Note that the SMS algorithm achieves the highest percentage of :nding the
global minimum. This clearly indicates that the SMS algorithm is the most
resilient to the local minimum problem. Note also that the SMS algorithm
adapts better to the movement content of sequences. Thus, for low-movement
sequences it uses fewer locations and for high-movement sequences it uses
more locations. In addition, because the motion estimation process is matched
to the motion coding process (through the initialization procedure), the SMS
algorithm has the lowest motion overhead.
One of the disadvantages of fast BMME algorithms is that their prediction
quality deteriorates for higher amounts of motion and larger search windows
(as, for example, in HDTV applications). This is clear from Table 8.2 when
moving from AKIYO to FOREMAN and TABLE TENNIS. To investigate this e+ect
further, the FOREMAN sequence was temporally subsampled to 25; 12:5; 8:33,
and 6:25 frames= s (this corresponds to frame skips of 1, 2, 3, and 4, respec-
tively). The corresponding maximum allowed displacements, d m , were set to
± 7; ± 15; ± 31, and ± 63 pels, respectively. Figure 8.6 shows the results of
this simulation. It is immediately evident that the SMS algorithm is the most
robust fast algorithm to the above e+ect, and yet it has the second-lowest
computational complexity.

8.5.2 Results Within an H.263-like Codec

The SMS algorithm along with the other :ve BMME algorithms have also
been tested within a hybrid H.263-like codec. As in previous simulations,