Skip to main content
SpringerLink
Log in

Fast motion estimation using modified orthogonal search algorithm for video compression

  • Original Paper
  • Published:
Signal, Image and Video Processing Aims and scope Submit manuscript

Abstract

This paper presents a novel method named as Modified Orthogonal Search Algorithm (MOSA) for the block based motion estimation. Recently fast search algorithm for video coding using Orthogonal Logarithmic Search Algorithm (OSA) has been proposed by Soongsathitanon et al. (IEEE Trans Consum Electron 51(2):552–559, 2005). We introduce the center biased search point pattern for the estimation of small motions and a half way stop technique to reduce the computational complexity in the existing OSA. This feature improves the speed performance of the algorithm by 80% as compared to the Full Search Algorithm, 50% over the Three Step Search algorithm and 2% faster than the OSA. However, the Mean Square Error and Signal to Noise Ratio did not show significant deviation from the orthogonal logarithmic search algorithm and the three step search algorithm. The experimental results based on the number of video sequences were presented to demonstrate the advantages of proposed motion estimation technique.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Soongsathitanon S., Woo W.L., Dlay S.S.: Fast search algorithms for video coding using orthogonal logarithmic search algorithm. IEEE Trans. Consum. Electron. 51(2), 552–559 (2005)

    Article  Google Scholar 

  2. ISO/IEC 11 172-2, Information technology-coding of moving pictures and associated audio for digital storage media at up to about 1.5 Mbit/s-part 2: Video [MPEGl Video] (1993)

  3. Koga, T., Iinuma, K., Hirano, A., Iijima, Y., Ishiguro, T.: Motion compensated interframe coding for video conferencing. In: Proc. Nat. Telecommun. Conf., New Orleans, LA, pp. G5.3.1–5.3.5, Nov 29–Dec 3 (1981)

  4. Srinivasan R., Rao K.R.: Predictive coding based on efficient motion estimation. IEEE Trans. Commun. COM-33(8), 888–896 (1985)

    Article  Google Scholar 

  5. Jain J., Jain A.: Displacement measurement and its application in interframe image coding. IEEE Trans. Commun. COM-29(12), 1799–1808 (1981)

    Article  Google Scholar 

  6. Yeong-Kang L.: A memory efficient motion estimator for three step search block-matching algorithm. IEEE Trans. Consum. Electron. USA 47(3), 644–651 (2001)

    Article  Google Scholar 

  7. Lai-Man P., Wing-Chung M.: A novel four-step search algorithm for fast block motion estimation. IEEE Trans. Circuits Syst. Video Technol. 6, 313–317 (1996)

    Article  Google Scholar 

  8. Reoxiang L., Bing Z., Liou M.L.: A new three-step search algorithm for block motion estimation. IEEE Trans. Circuits Syst. Video Technol. 4, 438–442 (1994)

    Article  Google Scholar 

  9. Nisar, H., Choi, T.S.: An advanced center biased three step search algorithm for motion estimation. In: IEEE International Conference on Multimedia and Expo. ICME2000, Part vol. 1, pp. 95–98, Piscataway, NJ (2000)

  10. Liu L.K., Feig E.: A block-based gradient descent search algorithm for block motion estimation in video coding. IEEE Trans. Circuits Syst. Video Technol. 6(4), 419–422 (1996)

    Article  Google Scholar 

  11. Tham J.Y., Ranganath S., Ranganath M., Kassim A.A.: A novel unrestricted center-biased diamond search algorithm for block motion estimation. IEEE Trans. Circuits Syst. Video Technol. 8(4), 369–377 (1998)

    Article  Google Scholar 

  12. Cheung C.H., Po L.M.: A novel cross-diamond search algorithm for fast block motion estimation. IEEE Trans. Circuits Syst. Video Technol. 12(12), 1168–1177 (2002)

    Article  Google Scholar 

  13. Zhu C., Lin X., Chau L.P.: Hexagon-based search pattern for fast block motion estimation. IEEE Trans. Circuits Syst. Video Technol. 12, 349–355 (2002)

    Article  Google Scholar 

  14. Lai-Man Po, Chi Wang Ting, Ka-Ho-Ng: New enhanced hexagon based search using point—oriented inner search for fast block motion estimation. Int. J. Signal Process. 3(3), 1304–4478 (2006)

    Google Scholar 

  15. Hong W.G., Oh T.M.: Sorting-based partial distortion search algorithm for motion estimation. Electron. Lett. 40, 113–115 (2004)

    Article  Google Scholar 

  16. Chau L.-P., Zhu C.: A fast octagon—based search algorithm for motion estimation. Signal Process. 83, 671–675 (2003)

    Article  MATH  Google Scholar 

  17. Zhu S., MA K.K.: A new diamond search algorithm for fast block matching motion estimation. IEEE Trans. Image Process. 9(2), 287–290 (2000)

    Article  MathSciNet  Google Scholar 

  18. Gharavi H., Mills M.: Block matching motion estimation algorithms—new results. IEEE Trans. Circuits Syst. 37, 649–651 (1990)

    Article  Google Scholar 

  19. Jar-Ferr Y., Shu-Sheng H., Wei-Yuan L.: Simplified block matching criteria for motion estimation. IEICE Trans. Inf. Syst. E83-D, 922–930 (2000)

    Google Scholar 

  20. Ahmad A., Khan N., Masud S., Maud M.A.: Efficient block size selection in H.264 video coding standard. Electron. Lett. 40, 19–21 (2004)

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. College of Engineering, An Autonomous Institute of Government of Maharashtra, Pune, India

    Shilpa P. Metkar

  2. SGGS Institute of Engineering and Technology, Nanded, Maharashtra, India

    Sanjay N. Talbar

Authors
  1. Shilpa P. Metkar
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Sanjay N. Talbar
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Shilpa P. Metkar.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Metkar, S.P., Talbar, S.N. Fast motion estimation using modified orthogonal search algorithm for video compression. SIViP 4, 123–128 (2010). https://doi.org/10.1007/s11760-009-0104-9

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11760-009-0104-9

Keywords

Search

Navigation