Fine-grained parallel algorithm for normalized partial distortion search

doi:10.7523/j.issn.2095-6134.2013.06.015

Abstract

Abstract:

Serial motion estimation does not satisfy real-time requirements of video coding in mobile terminal. A divided-spiral-path parallel motion estimation based on normalized partial distortion search is proposed to make full use of multi-core computing power, and it retains low computational complexity of the serial algorithm. Experimental results show that the proposed algorithm achieves speedup ratios of 3.88-3.96 on a 4-core CPU platform while the cost of trivial computational effort increases by less than 1.2%.

Key words: video coding, motion estimation, partial distortion search, parallel computing

CLC Number:

TP37

YUAN Jing-Jie, ZHANG Qing-Yi, MA Yi-Ke, SONG Feng-Long. Fine-grained parallel algorithm for normalized partial distortion search[J]. , 2013, 30(6): 813-818.

References

[1] Schwalb M, Ewerth R, Freisleben B. Fast motion estimation on graphics hardware for H.264 video encoding[J]. IEEE Transactions on multimedia, 2009, 11(1): 1-10.

[2] Chen Y K, Li E Q,Zhou X S,et al. Implementation of H.264 encoder and decoder on personal computers[J]. IEEE Transactions on multimedia, 2006, 17(2): 509-532.

[3] Lin Y C, Li P L, Chang C H, et al. Multi-pass algorithm of motion estimation in video encoding for generic GPU[C]//Proc of IEEE International Symposium on Circuits and Systems (ISCAS). 2006: 1-4.

[4] Cheung N M, Fan X P, Au O C, et al. Video coding on multicore graphics processors[J]. IEEE Signal Processing Magazine, 2010, 27(2): 79-89.

[5] Momcilovic S, Sousa L. A parallel algorithm for advanced video motion estimation on multicore architectures[C]//Proc of International Conference on Complex, Intelligent and Software Intensive Systems (CISIS). 2008: 831-836.

[6] Kung M C, Au O C, Wong P H W, et al. Block based parallel motion estimation using programmable graphics hardware[C]//Proc of International Conference on Audio, Language and Image Processing (ICALIP). 2008: 599-603.

[7] Chen Y B, Li Z D, Guo L, et al. Architecture design of low-power motion estimation based on DHS-NPDS for H.264/AVC[J]. Science China Information Fi Science, 2012, 42(4): 527-536 (in Chinese). 陈运必,李正东,郭立,等. 基于DHS-NPDS 的低功耗运动估计硬件结构设计[J]. 中国科学F辑:信息科学,2012,42(4): 527-536.

[8] Chen T C, Chien S Y, Huang Y W, et al. Analysis and architecture design of an HDTV720p 30 frames/s H.264/AVC encoder[J]. IEEE Trans Circ Syst Vid, 2006(16): 673-688.

[9] Urhan O. Constrained one-bit transform based fast block motion estimation using adaptive search range[J]. IEEE Transactions on Consumer Electronics, 2010, 56(3): 1 868-1 871.

[10] Cheung C K, Po L M. Normalized partial distortion search algorithm for block motion estimation[J]. IEEE Transactions on Circuits and Systems for Video Technology, 2000, 10(3): 417-422.

[11] Yi X Q, Ling N. Improved normalized partial distortion search with dual-halfway-stop for rapid block motion estimation[J]. IEEE Transactions on Multimedia, 2007, 9(5): 995-1 003.

[12] Po L M, Ma W C. A novel four-step search algorithm for fast block motion estimation[J]. IEEE Transactions on Circuits and Systems for Video Technology, 1996, 6(6): 313-317.

[13] Chow K H K, Liou M L. Generic motion search algorithm for video compression[J]. IEEE Transactions on Circuits and Systems for Video Technology, 1993, 3(12): 440-445.