Low complexity separable matching pursuits [video coding applications]

Y. Yuan, A. N. Evans, D. M. Monro

Research output: Contribution to conferencePaper

2 Citations (SciVal)


Methods of reducing the complexity of the matching pursuits algorithm with minimal loss of fidelity when coding displaced frame difference (DFD) images in video compression are investigated. A full search using 2D basis functions is used as a benchmark. The use of separable 1D bases greatly reduces the complexity, and significant further reductions are achieved by using only a 1D inner product search to locate the atom position, followed by a further 1D inner product search in the opposite direction to identify the second 1D basis function. To avoid ignoring significant structures orthogonal to the search direction, it is proposed to alternate the initial search direction between horizontal and vertical scanning. This produces a modest increase in distortion compared to the full 2D search, with a complexity reduction in excess of an order of magnitude.
Original languageEnglish
Pagesiii-725-8 vol.3
Publication statusPublished - 2004
EventAcoustics, Speech, and Signal Processing, 2004. Proceedings. (ICASSP '04). IEEE International Conference on -
Duration: 1 Jan 2004 → …


ConferenceAcoustics, Speech, and Signal Processing, 2004. Proceedings. (ICASSP '04). IEEE International Conference on
Period1/01/04 → …


  • video compression
  • low complexity separable matching pursuits
  • inner product search
  • fidelity loss minimization
  • separable 1D bases
  • horizontal scanning
  • vertical scanning
  • alternating search direction
  • displaced frame difference images
  • distortion
  • 2D basis function full search
  • video coding
  • computational complexity


Dive into the research topics of 'Low complexity separable matching pursuits [video coding applications]'. Together they form a unique fingerprint.

Cite this