Global elimination algorithm and architecture design for fast block matching motion estimation
Journal
IEEE Transactions on Circuits and Systems for Video Technology
Journal Volume
14
Journal Issue
6
Pages
898-907
Date Issued
2004
Author(s)
Abstract
This paper presents a new block matching motion estimation algorithm and its VLSI architecture design. The proposed global elimination algorithm (GEA) was derived from successive elimination algorithm (SEA), which can skip unnecessary sum of absolute difference (SAD) calculation by comparing minimum SAD with subsampled SAD (SSAD). Our basic idea is to separate the decision of early termination and SAD calculation for each candidate block to make data flow more regular and suitable for hardware. In short, we first compare the rough characteristics of all candidate blocks with the current block (SSAD). In turn, we select several best roughly matched candidate blocks to re-compare them with the current block by using detailed characteristics (SAD). Other features of GEA include fixed processing cycles, no initial guess, and high video quality (almost the same as full search). Unlike other fast algorithms, the mapping of GEA to hardware is very simple. We proposed an architecture that is composed of a systolic part to efficiently compute SSAD, an adder tree to support both SSAD and SAD calculations, and a comparator tree to avoid expensive sorting circuits. Simulation results show that our design is much more area efficient than many full-search architectures while maintaining high video quality and processing capability.
Subjects
Block matching; Global elimination algorithm (GEA); Motion estimation (ME); Successive elimination algorithm (SEA)
SDGs
Other Subjects
Block matching; Global elimination algorithm (GEA); Motion estimation (ME); Successive elimination algorithm (SEA); Algorithms; Computational methods; Computer simulation; Image coding; Image quality; Signal to noise ratio; Standards; Systolic arrays; VLSI circuits; Motion estimation
Type
journal article
File(s)![Thumbnail Image]()
Loading...
Name
25.pdf
Size
541.51 KB
Format
Adobe PDF
Checksum
(MD5):4a7e96f56a684a522bf2e0eb073beb3e