A Hierarchical$N$-Queen Decimation Lattice and Hardware Architecture for Motion Estimation
Authors:
- Shin-Wei YangSYShin-Wei Yang
- Chi-Min LiuCLChi-Min Liu
- Tihao ChiangTCTihao Chiang
- 5 April 2004
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Circuits and Systems for Video Technology
- Vol. 14 (4) , 429-440
Abstract
A subsampling structure, an N-Queen lattice, for spatially decimating a block of pixels is presented. Despite its use for many applications, we demonstrate that the N-Queen lattice can be used to speed up motion estimation with nominal loss of coding efficiency. With a simple construction, the N-Queen lattice characterizes the spatial features in the vertical, horizontal, and diagonal directions for both texture and edge areas. Especially in the 4-Queen case, every skipped pixel has the minimal and equal distance of unity to the selected pixel. It can be hierarchically organized for variable nonsquare block-size motion estimation. Despite the randomized lattice, we design compact data storage architecture for efficient memory access and simple hardware implementation. Our simulations show that the N-Queen lattice is superior to several existing sampling techniques with improvement in speed by about N times and small loss in peak SNR (PSNR). The loss in PSNR is negligible for slow-motion video sequences and is less than 0.45 dB at worst for high-motion estimation sequences.Keywords
This publication has 11 references indexed in Scilit:
- A hierarchical decimation lattice based on N-queen with an application for motion estimationIEEE Signal Processing Letters, 2003
- Optimizing the MPEG-4 encoder-advanced diamond zonal search2002
- Fast Motion Estimation Using N-Queen Pixel DecimationLecture Notes in Computer Science, 2001
- A Novel Fast Block Motion Estimation Algorithm Based on Combined Subsamplings on Pixels and Search CandidatesJournal of Visual Communication and Image Representation, 2001
- Probabilistic partial-distance fast matching algorithms for motion estimationIEEE Transactions on Circuits and Systems for Video Technology, 2001
- A globally adaptive pixel-decimation algorithm for block-motion estimationIEEE Transactions on Circuits and Systems for Video Technology, 2000
- A new diamond search algorithm for fast block-matching motion estimationIEEE Transactions on Image Processing, 2000
- New adaptive pixel decimation for block motion vector estimationIEEE Transactions on Circuits and Systems for Video Technology, 1996
- A new fast motion estimation algorithm using hexagonal subsampling pattern and multiple candidates search1996
- New fast algorithms for the estimation of block motion vectorsIEEE Transactions on Circuits and Systems for Video Technology, 1993