Your browser does not support JavaScript!
http://iet.metastore.ingenta.com
1887

access icon free Fast motion estimation algorithm using multilevel distortion search in Walsh–Hadamard domain

© The Institution of Engineering and Technology
Received 13/06/2016, Accepted 28/07/2016, Published 24/08/2016

Block-matching motion estimation (BME) can efficiently reduce the temporal redundancy between the successive video sequences in video compression coding system. In this study, a fast BME algorithm using multilevel distortion search in Walsh–Hadamard domain is proposed to reduce the computational burden and speed up coding process. First, the proposed algorithm divides the block into several sub-blocks. Then, the Walsh–Hadamard transform is applied to these sub-blocks. Finally, the proposed algorithm calculates the partial block matching distortion by utilising a novel back diagonal search scheme which can quickly reject unnecessary candidate block in a multilevel manner. Experimental results show that the proposed algorithm effectively reduces the number of operations in block distortion calculation meanwhile maintains the best motion estimation matching quality. Compared with the full search, the proposed algorithm can reduce 87.19% computational complexity without any degradation of the peak signal to noise ratio. In addition, compared with the partial distortion search algorithm, successive elimination algorithm, multilevel successive elimination algorithm and the transform-domain successive elimination algorithm, the proposed algorithm can also save 68.27, 70.09, 37.81 and 37.44% computational complexity, respectively. Moreover, the proposed algorithm can also be easily incorporated into any block-based template search motion estimation algorithm.

Inspec keywords: Hadamard transforms; image matching; motion estimation; search problems; video signal processing; image sequences

Other keywords: coding process; Walsh-Hadamard domain; block-matching motion estimation; template search motion estimation algorithm; temporal redundancy; fast motion estimation algorithm; multilevel distortion search; video compression coding system; partial block matching distortion; peak signal to noise ratio; computational complexity; BME; partial distortion search algorithm; subblocks; video sequences

Subjects: Optimisation techniques; Integral transforms; Integral transforms; Combinatorial mathematics; Video signal processing; Optimisation techniques; Combinatorial mathematics; Computer vision and image processing techniques; Optical, image and video signal processing

References

    1. 1)
      • 10. Xuan, J., Chau, L.P.: ‘Partial distortion search algorithm using predictive search area for fast full-search motion estimation’, IEEE Signal Process. Lett., 2007, 14, (11), pp. 840–843.
    2. 2)
      • 2. Jain, J., Jain, A.: ‘Displacement measurement and its application in interframe image coding’, IEEE Trans. Commun., 1981, 29, (12), pp. 1799–1808.
    3. 3)
      • 19. Paramkusam, A.V., Reddy, V.S.K.: ‘Two-layer motion estimation algorithm for video coding’, Electron. Lett., 2014, 50, (4), pp. 276–278.
    4. 4)
      • 20. Sanggu, L., Gwanggil, J., Jechang, J.: ‘Fast motion estimation based on enhanced constrained one-bit transform’, Electron. Lett., 2014, 50, (10), pp. 746–748.
    5. 5)
      • 13. Chao-Cing, Y., Gwo-Long, L., Ming-Chieh, C., et al: ‘Prediction error prioritizing strategy for fast normalized partial distortion motion estimation algorithm’, IEEE Trans. Circuits Syst. Video Technol., 2010, 20, (8), pp. 1150–1155.
    6. 6)
      • 17. Tae Gyoung, A., Yong Ho, M., Jae Ho, K.: ‘Fast full-search motion estimation based on multilevel successive elimination algorithm’, IEEE Trans. Circuits Syst. Video Technol., 2004, 14, (11), pp. 1265–1269.
    7. 7)
      • 6. Ce, Z., Xiao, L., Chau, L.P.: ‘Hexagon-based search pattern for fast block motion estimation’, IEEE Trans. Circuits Syst. Video Technol., 2002, 12, (5), pp. 349–355.
    8. 8)
      • 23. Zhaoqing, P., Jianjun, L., Yun, Z., et al: ‘Fast motion estimation based on content property for low-complexity H.265/HEVC encoder’. IEEE Trans. Broadcast., 2016, 62, (3), pp. 675–684.
    9. 9)
      • 3. Renxiang, L., Bing, Z., Liou, M.L.: ‘A new three-step search algorithm for block motion estimation’, IEEE Trans. Circuits Syst. Video Technol., 1994, 4, (4), pp. 438–442.
    10. 10)
      • 21. Cuevas, E., Zaldívar, D., Pérez-Cisneros, M., et al: ‘Block matching algorithm for motion estimation based on artificial bee colony (Abc)’, Appl. Soft Comput., 2013, 13, (6), pp. 3047–3059.
    11. 11)
      • 16. Gao, X.Q., Duanmu, C.J., Zou, C.R.: ‘A multilevel successive elimination algorithm for block matching motion estimation’, IEEE Trans. Image Process., 2000, 9, (3), pp. 501–504.
    12. 12)
      • 18. Chun-Su, P.: ‘Multilevel motion estimation based on distortion measure in transform domain’, Electron. Lett., 2013, 49, (14), pp. 880–882.
    13. 13)
      • 22. Lins, R., Henriques, D.B., Lima, E., et al: ‘Quasi-random search algorithm for fast motion estimation’. 2013 IEEE Int. Conf. on Acoustics, Speech and Signal Processing (ICASSP), 2013.
    14. 14)
      • 5. Shan, Z., Kai-Kuang, M.: ‘A new diamond search algorithm for fast block-matching motion estimation’, IEEE Trans. Image Process., 2000, 9, (2), pp. 287–290.
    15. 15)
      • 8. Nie, Y., Kai-Kuang, M.: ‘Adaptive rood pattern search for fast block-matching motion estimation’, IEEE Trans. Image Process., 2002, 11, (12), pp. 1442–1449.
    16. 16)
      • 14. Xiaoquan, Y., Nam, L.: ‘Improved normalized partial distortion search with dual-halfway-stop for rapid block motion estimation’, IEEE Trans. Multimed., 2007, 9, (5), pp. 995–1003.
    17. 17)
      • 7. Lai-Man, P., Ka-Ho, N., Kwok-Wai, C., et al: ‘Novel directional gradient descent searches for fast block motion estimation’, IEEE Trans. Circuits Syst. Video Technol., 2009, 19, (8), pp. 1189–1195.
    18. 18)
      • 4. Lai-Man, P., Wing-Chung, M.: ‘A novel four-step search algorithm for fast block motion estimation’, IEEE Trans. Circuits Syst. Video Technol., 1996, 6, (3), pp. 313–317.
    19. 19)
      • 15. Li, W., Salari, E.: ‘Successive elimination algorithm for motion estimation’, IEEE Trans. Image Process., 1995, 4, (1), pp. 105–107.
    20. 20)
      • 9. Kai-Kuang, M., Gang, Q.: ‘An improved adaptive rood pattern search for fast block-matching motion estimation in Jvt/H.26l’. Proc. of the 2003 Int. Symp. on Circuits and Systems, 2003. ISCAS '03.2003.
    21. 21)
      • 12. Chun-Ho, C., Lai-Man, P.: ‘Adjustable partial distortion search algorithm for fast block motion estimation’, IEEE Trans. Circuits Syst. Video Technol., 2003, 13, (1), pp. 100–110.
    22. 22)
      • 11. Chok-Kwan, C., Lai-Man, P.: ‘Normalized partial distortion search algorithm for block motion estimation’, IEEE Trans. Circuits Syst. Video Technol., 2000, 10, (3), pp. 417–422.
    23. 23)
      • 1. Wiegand, T., Sullivan, G.J., Bjontegaard, G., et al: ‘Overview of the H.264/Avc Video Coding Standard’, IEEE Trans. Circuits Syst. Video Technol., 2003, 13, (7), pp. 560–576.
http://iet.metastore.ingenta.com/content/journals/10.1049/iet-ipr.2016.0453
Loading

Related content

content/journals/10.1049/iet-ipr.2016.0453
pub_keyword,iet_inspecKeyword,pub_concept
6
6
Loading
Print this page
This is a required field
Please enter a valid email address