A Novel Hexagonal Search Algorithm for Fast Block Matching Motion Estimation
- PDF / 879,509 Bytes
- 6 Pages / 600 x 792 pts Page_size
- 48 Downloads / 188 Views
A Novel Hexagonal Search Algorithm for Fast Block Matching Motion Estimation Anastasios Hamosfakidis Department of Computer Science, Queen Mary, University of London, Mile End Road, E1-4NS, UK Email: [email protected]
Yakup Paker Department of Computer Science, Queen Mary, University of London, Mile End Road, E1-4NS, UK Email: [email protected] Received 26 July 2001 and in revised form 5 February 2002 Based on real-world image sequence characteristics of center-biased motion vector distribution, a Hexagonal (HS) algorithm with center-biased checking point pattern for fast block motion estimation is proposed. The HS is compared with full search (FS), four-step search (4SS), new three-step search (NTSS), and recently proposed diamond search (DS) methods. Experimental results show that the proposed technique provides competitive performance with reduced computational complexity. Keywords and phrases: fast motion estimation, hexagonal search pattern, center-biased motion vector estimation.
1.
INTRODUCTION
Motion compensated video coding, which predicts current frame from I and P frames, has been widely used to exploit the temporal redundancy between consecutive frames. Motion estimation plays an important role in such an interframe predictive video coding system. Among different types of motion estimation algorithms, the block matching technique has been adopted in many compression standards, such as H.261 [1], MPEG-1 [2], MPEG-2 [3], and MPEG4 [4]. In block matching, video data, frames, or video object planes (VOPs) are divided into blocks and one motion vector (MV) is associated with each block—A video object (VO) in MPEG-4 is an arbitrarily shape video segment that has a semantic meaning. A 2D snapshot of a VO at a particular time instant is called video object plane. For each block of the current frame/VOP, an MV is derived which points to the best matching block of the previous (reference) frame/VOP. Then the best match block is used as the predictor for the current block. The full search (FS) block matching algorithm is the simplest but the most compute-intensive solution as it provides the optimal solution by matching all the possible displaced blocks within a given search range in the reference frame/VOP. In order to speed up MV derivation, many fast block matching motion estimation (BMME) algorithms have been proposed such as three-step search (3SS) [5], one-ata-time search (OTS) [6], four-step search (4SS) [7], new three-step search (NTSS) [8], and diamond search (DS) [9].
The objective of these fast BMME algorithms is to find the MV that minimizes the image error by reducing the number of checking points within the search window. Of these, 3SS and OTS algorithms are known to have the tendency to be trapped into a local minimum, thereby degrading performance. Based on the analysis of the above-mentioned fast BMMEs and a study of MV distribution of real-world test video sequences, a new hexagonal search (HS) algorithm is proposed in this paper. In Section 2, we introduce the design motivation of the p
Data Loading...
