A Fast Block Matching Motion Estimation Algorithm Based On Simplex Minimisation

Mohammed Al-Mualla, Nishan Canagarajah, David BullZenodo 1998 · DOI

TL;DR

This paper introduces a novel algorithm for motion estimation in video compression that significantly speeds up the process while maintaining high image quality. By adapting a general-purpose optimization technique called Simplex Minimization, the authors achieve a more efficient and robust motion tracking method compared to existing fast algorithms.

What Problem Does This Paper Address?

Video compression relies heavily on predicting future frames based on current ones. A key technique for this is motion estimation, where blocks of pixels in the current frame are matched to similar blocks in a reference frame. The goal is to find the "best match" block and record its displacement (motion vector). The most accurate method, Full Search (FS), exhaustively checks every possible location, which is computationally very expensive and impractical for real-time applications. Many "fast" algorithms have been developed to reduce this computational load, but they often rely on assumptions about the motion field that don't always hold true, leading them to get stuck in suboptimal "local minima" and degrade image quality. This paper aims to bridge this gap by proposing a fast motion estimation algorithm that is both computationally efficient and less prone to local minima.

Methods

The core of this paper is the application of Simplex Minimization (SM), a general-purpose optimization technique, to the problem of block matching motion estimation (BMME). SM is an iterative method that uses a geometric figure (a simplex) to explore a search space and find the minimum of a function.

The authors adapt SM for BMME by:

  • Initialisation Procedure: Instead of random starting points, they strategically choose the initial three points (vertices of the simplex in 2D) for the search. This leverages two key properties of typical video motion: the tendency for motion to be centered around zero displacement and the smoothness of motion between neighboring blocks. They use the motion vector of the current block (0,0), and the motion vectors of the blocks to the left and above (if available) as initial predictions. Further refinement is done by checking neighbors of the best initial prediction.
  • Termination Criterion: They propose a novel criterion that stops the search when the vertices of the simplex become "neighbors." This avoids relying on arbitrary thresholds that might not work across different video sequences and ensures the simplex remains non-degenerate.
  • Constraints: SM is an unconstrained optimization method, but BMME requires constraints. The authors ensure that all search points stay within the defined search window and are rounded to the required accuracy (e.g., full-pel).
  • Motion Vector Refinement: To mitigate the risk of converging to a suboptimal point, they add an optional refinement step where the algorithm searches the immediate neighbors of the point found by SM. This step is efficient as many of these neighbor's distortion values are often already computed during the SM search.

Datasets

The authors evaluated their algorithm using the luminance component of three standard QCIF video sequences:

  • FOREMAN (176x144 @ 25 fps)
  • TUNNEL (176x144 @ 25 fps)
  • TABLE TENNIS (176x120 @ 30 fps)

They used 300 frames for FOREMAN and TABLE TENNIS, and 250 frames for TUNNEL. The Block Distortion Measure (BDM) used was Sum of Absolute Differences (SAD), with a block size of 16x16 pels and a maximum motion displacement of ±15 pels.

Key Insights and Ideas

  • Simplex Minimization is a good fit for BMME: The paper demonstrates that a general optimization technique can be effectively tailored for a specific image processing problem like motion estimation.
  • Exploiting Video Properties for Initialization: The proposed initialization strategy, which considers the center-biased nature of motion and the smoothness of motion fields, significantly improves the starting point of the search.
  • Robust Termination: The neighbor-based termination criterion is more robust than threshold-dependent methods, adapting better to varying video content.
  • Reduced Risk of Local Minima: The reflection and expansion steps inherent in the Simplex method, combined with the refinement step, make the algorithm less susceptible to getting trapped in suboptimal solutions compared to many other fast search algorithms.

Key Results

The proposed Simplex Minimization (SM) algorithm demonstrated superior performance compared to Full Search (FS) and other fast algorithms like 2DL, CSA, and OTS.

  • Computational Complexity: SM achieved substantial savings in the number of searched locations per frame. For FOREMAN, it reduced searches by about 98.6% compared to FS.
  • Reconstruction Quality: SM offered a very small loss in reconstruction quality compared to FS. For FOREMAN, the loss was only 0.16 dB.
  • Motion Overhead: The algorithm also reduced the number of bits required to encode motion vectors. For FOREMAN, savings were about 27 bits/frame.
  • Comparison to 2DL: SM outperformed the well-known 2DL algorithm, providing a 0.23 dB improvement in reconstruction quality for FOREMAN, a reduction of 33 bits/frame in motion information, and approximately a 33% reduction in computational complexity.
  • Smoother Motion Field: The paper notes that SM generally produces a smoother motion field, which is easier to code and leads to better overall compression.

Limitations and Future Work

  • Suboptimal Convergence: While the refinement step helps, the paper acknowledges that the termination criterion is not strictly based on minimizing the BDM, and there's still a possibility of converging to a suboptimal point in some cases.
  • Parameter Tuning: Although the paper proposes specific parameters (e.g., step size s=p/3 for refinement), the optimal parameters might vary for different video sequences or applications.
  • Future Work: The authors suggest that further investigation into optimizing the initialization and termination criteria could lead to even better performance. The paper also implies that this approach could be extended to other optimization problems in video processing.

Summary updated

Abstract

Publication in the conference proceedings of EUSIPCO, Rhodes, Greece, 1998
BibTeX
@inproceedings{almualla1998fast,
  author = {Mohammed Al-Mualla and Nishan Canagarajah and David Bull},
  title = {{A Fast Block Matching Motion Estimation Algorithm Based On Simplex Minimisation}},
  booktitle = {Zenodo},
  year = {1998},
  doi = {10.5281/zenodo.36607},
}
Figure