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

172 Chapter 7. Reduced-Complexity Motion Estimation Techniques

Table 7.4: Comparison between di-erent fast block-matching algorithms when applied to QSIF
TABLE TENNIS at 30 frames=s
Prediction quality Computational complexity
PSNR MPSNR ME time Speed-up
(dB) (dB) (ms=frame) ratio
FSA 32.17 0.00 1049.11 1.00
PDE 32.17 0.00 125.02 8.39
SDM 31.99 −0.18 287.73 3.65
SMF 31.44 −0.73 529.00 1.98
TDL 31.63 −0.54 28.66 36.61
HME 31.85 −0.32 21.62 48.54

should be taken when interpreting the results because the motion estimation
time can vary with implementation and the underlying hardware platform. The
speed-up ratio of each algorithm with reference to the FSA is also shown. 6
As expected the FSA provides the best prediction quality, but at the expense
of a high computational complexity.
The PDE algorithm provides an identical prediction quality to FSA, with
a moderate speed-up ratio. Note that the computational complexity of PDE is
highly dependent on the type of sequence and the motion content. For example,
most blocks in the AKIYO sequence are stationary or quasi-stationary. Since
PDE is initialized at (0; 0), this will lead to a very low starting minimum
value BDM(i m ;j m ). This will result in faster rejection of more candidates and,
consequently, will lead to a relatively high speed-up ratio.
The SDM provides the next-best prediction quality. However, its 4:1 sub-
sampling pattern limits its speed-up ratio to about 4. Similarly, the 2:1 )eld
subsampling pattern of SMF limits its speed-up ratio to about 2. Note that the
prediction quality of SMF is dependent on the amount of correlation between
the motion vectors of neighboring blocks. This may explain the relatively high
loss of prediction quality for the TABLE TENNIS sequence.
The TDL and HME algorithms provide the highest speed-up ratios, with
moderate losses in prediction quality. In general, however, the HME algo-
rithm outperforms the TDL algorithm in terms of both prediction quality and
computational complexity.

ME time for FSA
6 Speed-up = .
ME time for fast algorithm