| |
Hardware Efficient Double Diamond Search Block Matching Algorithm for Fast Video Motion Estimation
- 作者:Nehal N. Shah ; Upena D. Dalal
- 关键词:Motion estimation (ME) ; Block matching algorithm (BMA) ; Hardware efficient double diamond search (HEDDS) ; Sum of absolute difference (SAD) ; Search iterations
- 刊名:The Journal of VLSI Signal Processing
- 出版年:2016
- 出版时间:January 2016
- 年:2016
- 卷:82
- 期:1
- 页码:115-135
- 全文大小:4,770 KB
- 参考文献:1.Kim, J., & Choi, T. (1998). A fast Three-step search algorithm with minimum checking points unimodal error surface assumption. IEEE Transactions on Consumer Electronics, 44(3), 638–648.CrossRef
2.Lai-Man Po, W.-C. M. (1996). A novel Four-step search algorithm for fast block Motion Estimation. IEEE Transactions on Circuits and Systems for Video Technology, 6(3), 313–317.CrossRef 3.Feig, E. (1996). A block-based gradient descent search algorithm for block motion estimation in video coding. IEEE Transactions on Circuits and Systems for Video Technology, 6(4). 4.Zhu, S., & Ma, K.K. (2000). A new diamond search algorithm for fast block-matching motion estimation. IEEE Transactions on Image Processing, 9(2), 287–90.MathSciNet CrossRef 5.Zhu, C., Lin, X., & Chau, L. (2002). Hexagon-based search pattern for fast block motion estimation. IEEE Transactions on Circuits and Systems for Video Technology, 12(5), 349–355.CrossRef 6.Cheung, C., & Po, L. (2002). A novel cross-diamond search algorithm for fast block motion estimation. IEEE Transactions on Circuits and Systems for Video Technology, 12(12), 1168–1177.CrossRef 7.Jia, H., & Zhang, L. (2003). Directional diamond search pattern for fast block motion estimation. Electronics Letters, 39(22), 2–3.CrossRef 8.Cheung, C., & Po, L. (2005). Novel cross-diamond-hexagonal search algorithms for fast block motion estimation. IEEE Transactions on Circuits and Systems, 7(1), 16–22. 9.Tsai, T., & Pan, Y. (2006). A novel 3-D predict hexagon search algorithm for fast block motion estimation on h.264 video coding. IEEE Transactions on Circuits and Systems for Video Technology, 16(12), 1542–1549.CrossRef 10.Jing, X., Chau, L., & Member, S. (2004). An efficient three-step search algorithm for block motion estimation. IEEE Transactions on Multimedia, 6(3), 435–438.CrossRef 11.Yan, Y., & Meng, S. (2011). A new hybrid search scheme for video motion estimation. Journal of Convergence Information Technology, 6(3), 106–112.CrossRef 12.Huang, S., Cho, C., & Wang, J. (2005). Adaptive fast block-matching algorithm by switching search patterns for sequences with wide-range motion content. IEEE Transactions on Circuits and Systems for Video Technology, 15 (11), 1373–1384.CrossRef 13.Ng, K., Po, L., Wong, K., Ting, C., & Cheung, K. (2009). A search patterns switching algorithm for block motion estimation. IEEE Transactions on Circuits and Systems for Video Technology, 19(5), 753–759.CrossRef 14.Chen, Z., Zhou, P., & He, Y. (2002). Fast integer Pel and fractional Pel motion estimation for JVT, joint video team ISO/IEC MPEG ITU-T VCEG, 6th meet. Japan: Awaji Island. 15.Chen, Z., Xu, J., He, Y., & Zheng, J. (2006). Fast integer-pel and fractional-pel motion estimation for H.264/AVC. Journal of Visual Communication and Image Representation, 17(2), 264–290.CrossRef 16.Hsieh, H. J., Lin, C. C., & Lin, Y. (2009). Multi-direction search algorithm for block motion estimation in H.264/AVC. IET Image Processing, 3(2), 88–99.CrossRef 17.Yi, X., Zhang, J., Ling, N., & Shang, W. Improved and simplified fast motion estimation for JM. Joint Video Team (JVT) of ISO / IEC MPEG & ITU-T VCEG, 16th Meeting: Poznan, Poland,24-29 July, 2005,JVT-P021. 18.Po, L., Ng, K., Cheung, K., Wong, K., & Ting, C. (2009). Novel directional gradient descent searches for fast block motion estimation. IEEE Transactions on Circuits and Systems for Video Technology, 19(8), 1189–1195.CrossRef 19.Tai, S., Chen, Y., & Chen, Y. (2007). Small-diamond-based search algorithm for fast block motion estimation. Signal Processing: Image Communication, 22, 877–890. 20.Hsu, W., Yu, T., & Guo, J. (2010). Enhanced block motion estimation based on threshold-aware two-path search method. Journal of Convergence Information Technology, 5(5), 99–110.CrossRef 21.Po, L.-M., Ting, C.-W., Wong, K.-M., & Ng, K.-H. (2007). Novel point-oriented inner searches for fast block motion estimation. IEEE Transactions on Multimedia, 9(1), 9–15.CrossRef 22.Shah, N. N., Agarwal, K. R., & Singapuri, H.M. (2013). Implementation of sum of absolute difference using optimized partial summation term reduction. In International Conference on Advanced Electronic Systems (ICAES), (pp. 192–196). 23.Porto, M., Silva, A., Almeida, S., Costa, E., & Bampi, S. (2010). Motion estimation architecture using efficient adder-compressors for HDTV video coding. Journal Integrated Circuits and Systems, 5(1), 78–88. 24.Sanchez, G., Noble, D., Porto, M., & Agostini, L. (2011). High efficient motion estimation architecture with integrated motion compensation and FME support. In IEEE Second Latin American Symposium on Circuits and Systems (LASCAS), (pp. 6–9). 25.Tsai, T.-H., & Pan, Y.-N. (2011). High Efficiency Architecture Design of Real-Time QFHD for H.264/AVC Block Motion Estimation. IEEE Transactions on Circuits and Systems for Video Technology, 21(11), 1646–1658.CrossRef 26.Vanne, J., Aho, E., & Kuusilinna, K. (2009). A configurable motion estimation architecture for block-matching algorithms. IEEE Transactions on Circuits and Systems for Video Technology, 19(4), 466–476.CrossRef 27.Ndili, O., & Ogunfunmi, T. (2011). Algorithm and architecture co-design of hardware-oriented, modified diamond search for fast motion estimation in H.264/AVC. IEEE Transactions on Circuits and Systems for Video Technology, 21(9), 1214–1227.CrossRef 28.Kthiri, M., Loukil, H., Werda, I., Ben Atitallah, A., Samet, A., & Masmoudi, N. (2009). Hardware implementation of fast block matching algorithm in FPGA for H.264/AVC, in international multi-conference on systems. Signals and Devices, 1–4. 29.Wang, Z., Bovik, A. C., Sheikh, H. R., & Simoncelli, E. P. (2004). Image quality assessment: from error visibility to structural similarity. IEEE Transactions on Image Processing, 13(4), 600–612.CrossRef 30.Bjontegaard, G. (2001). Calculation of average PSNR differences between RD-curves, document VCEG-M33, VCEG contribution, Austin, TX. 31.Sanchez, G., Sampaio, F., Porto, M., Bampi, S., & Agostini, L. (2012). DMPDS: a fast motion estimation algorithm targeting high resolution videos and its FPGA implementation. International Journal of Reconfigurable Computing, 1–12. 32.YUV. video repository. Retrieved from http://media.xiph.org/video/derf/ .
- 作者单位:Nehal N. Shah (1)
Upena D. Dalal (2)
1. Sarvajanik College of Engineering and Technology, Surat, India 2. S. V. National Institute of Technology, Surat, India
- 刊物类别:Engineering
- 刊物主题:Electrical Engineering
Circuits and Systems Computer Imaging, Vision, Pattern Recognition and Graphics Computer Systems Organization and Communication Networks Signal,Image and Speech Processing Mathematics of Computing
- 出版者:Springer New York
- ISSN:1939-8115
文摘
Application of video in multimedia communication has become feasible due to efficient block matching algorithm (BMA) based motion estimation (ME) and motion compensation (MC) methods, that facilitate high data compression. To sustain visual quality of video, large amount of computation is involved in ME which can be reduced by fast search BMA and making fast search faster by various means like predicting initial search center (ISC) and early search termination. But more challenging work is to design an architecture which performs computation hungry search process in fewer clock cycles which will actually make fast search rapid for real time encoding. Implementations are available for matching multiple macroblocks in single clock cycle, but bottleneck is accessing macroblocks from memory while following sequential irregular search patterns of most of fast search algorithms. This paper proposes a novel, Hardware Efficient Double Diamond Search (HEDDS) algorithm which reaches far in search window more rapidly to identify best match and minimizes number of iterations of search pattern and hence diminish required clock cycles to read macroblocks from memory. From implementation perspective, HEDDS is up to 7.5 % to 33 % faster than existing BMAs and also offers reasonably good quality of encoding. With variable block size, HEDDS demonstrate average BD-PSNR improvement of 0.381, 0.088, 0.87 and 0.233 dB at BD-bitrate drop of 12.994 %, 2.499 %, 25.599 %, 6.887 % in comparison of HS, HMDS, LDPS and UMHS correspondingly. Proposed HEDDS architecture can process 259 HD frames per second in average case for fixed block size which is promising figure for real time encoding on devices having inadequate computational resources.
| |
NGLC 2004-2010.National Geological Library of China All Rights Reserved.
Add:29 Xueyuan Rd,Haidian District,Beijing,PRC. Mail Add: 8324 mailbox 100083
For exchange or info please contact us via email.
| |