Fast full search in motion estimation by hierarchical use of Minkowski's inequality (HUMI)

Jing Yi Lu, Kuang Shyr Wu, Chih_Ching Lin*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

33 Scopus citations


In this paper, we extend the idea of successive elimination algorithm (SEA) to obtain a fast full search (FS) algorithm accelerating the block matching procedure of motion estimation. Based on the monotonie relation between the accumulated absolution distortions (AAD) obtained for distinct layers of a pyramid structure, the proposed method successfully rejects many impossible candidates considered in the FS. The derivation of the monotonicity relation repeatedly uses in a four-dimensional vector space the l1-version of Minkowski's inequality, an inequality which is quite well-known in the field of mathematics. Simulation results show that the processing speed is faster than that of several well-known fast full search methods, including the SEA that uses just once the Minkowski's inequality (in a vector space of 256 dimension when the block size is 16 × 16). The processing speed of the proposed method is also competitive with that of the three-step search (TSS), which is often used for block matching in interframe video coding, although the visual quality performance of TSS is usually a little poorer than that of the FS.

Original languageEnglish
Pages (from-to)945-952
Number of pages8
JournalPattern Recognition
Issue number7
StatePublished - 31 Jul 1998


  • Accumulated absolute distortion
  • Block matching
  • l-norm
  • Minkowski's inequality
  • Motion estimation
  • Motion vector
  • Position vector

Fingerprint Dive into the research topics of 'Fast full search in motion estimation by hierarchical use of Minkowski's inequality (HUMI)'. Together they form a unique fingerprint.

Cite this