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

202 Chapter 8. The Simplex Minimization Search

8.7 Discussion

There are many techniques for reduced-complexity BMME. The most widely
used approach employs a reduced set of motion vector candidates. Algorithms
in this category are usually based on a unimodal error surface assumption.In
most cases, however, this assumption does not hold true, and such algorithms
can easily get trapped in local minima, giving a suboptimal prediction quality.
The main aim of this chapter was to develop a reduced-complexity BMME
that adopts the same approach of reducing the set of motion vector candidates
but, at the same time, avoids the local minimum problem.
Thus, the chapter formulated block-matching motion estimation as a two-
dimensional constrained minimization problem. It was then proposed to solve
this problem, with reduced complexity, using an optimization method called the
simplex minimization (SM) optimization method. The resulting solution was
called the simplex minimization search (SMS). The initialization procedure,
termination criterion, and constraints on the independent variables of the search
were designed to take into account the basic properties of the BMME problem.
Simulation results within an isolated test environment showed that the SMS
algorithm outperforms other reduced-complexity BMME algorithms, providing
better prediction quality, smoother motion :eld, and higher speed-up ratio. In
particular, the SMS algorithm is very resilient to the local minimum problem.
This superior performance was also con:rmed within an H.263-like codec and
an object-based MPEG-4 codec.
It was also noted that the superior performance of the LTM-MCP (discussed
in Chapter 6) is achieved at the expense of a signi:cant increase in computa-
tional complexity. To reduce complexity, the chapter extended the SMS algo-
rithm to the multiple-reference case. Three di+erent extensions (or algorithms)
were presented, each representing a di+erent degree of compromise between
prediction quality and computational complexity. Simulation results showed
that the multiple-reference SMS algorithms provide signi:cant reductions in
computational complexity compared to the multiple-reference full-search. With
a multiframe memory of size M = 50, the computational complexity of the
SMS algorithms is comparable to (and in some cases less than) that of single-
reference full-search, and yet they still maintain the improved prediction gain
of multiple-reference motion estimation.