Abstract
A simple, adaptive, computationally efficient and robust scheme for multi pattern block motion estimation has been proposed. A combination of spatial and temporal predictors has been used for multiple initial search center prediction, determination of magnitude of motion and multiple search pattern selection. The multiple initial predictors help to identify the absolute zero motion blocks and true location of global minimum based on the characteristic of unimodal error surfaces. Hence the final predictive search center selected is closer to the global minimum thus decreases the effect of monotonic error surface assumption and its impact on the motion field. This also increases the computation speed. Further computational speed up has been obtained by considering half stop technique and threshold for minimum distortion point. The computational complexity of the proposed algorithm is drastically decreased (average speedup ~ 43%) whereas the image quality measured in terms of PSNR also shows results close to Full Search algorithm.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
LeGall, D.: MPEG: A video compression standard for multimedia. Commun. ACM 34(4), 47–58 (1991)
CCITT SG XV, Recommendation H.261 video codec for audiovisual services at p*64 kbits/sec, Tech. Rep. COMXVR37-E (August 1990)
Wiegand, T., Sullivan, G., Luthra, A.: Draft ITU-T Recommendation and Final Draft International Standard of Joint Video Specification (ITU-T Rec. H.264| ISO/IEC 14496-10 AVC) (May 2003)
Puri, H.M.H., Schilling, D.L.: An efficient block matching algorithm for motion compensated coding. In: Proc. IEEE Int. Conf. Acoust., Speech, and Signal Proc., pp. 1063–1066 (1987)
Nisar, H., Choi, T.-S.: Fast Motion Estimation Algorithm based on spatio-temporal correlation and direction of motion vectors. Electronics Letters 42(24), 1384–1385 (2006)
Jain, J.R., Jain, A.K.: Displacement measurement and its application in interframe image coding. IEEE Trans. on Communications COM-29(12), 1799–1808 (1981)
Li, R., Zeng, B., Liou, M.L.: A new three step search algorithm for block motion estimation. IEEE Trans. on Circuits and Systems for Video Technology 4(4), 438–442 (1994)
Chow, K.H.K., Liou, M.L.: Generic motion search algorithm for video compression. IEEE Trans. on Circuits and Systems for Video Technology 3, 148–157 (1993)
Po, L.M., Ma, W.C.: A novel four-step search algorithm for fast block motion estimation. IEEE Trans. on Circuits and Systems for Video Technology 6(3), 313–317 (1996)
Koga, T., Iinuma, K., Hirano, A., Iijima, Y., Ishiguro, T.: Motion compensated interframe coding for video conferencing. In: Pro. Nat. Telecommun. Conf., New Orleans, pp.G5.3.1–G3.5 (November 1981)
Po, L.M., Ma, W.C.: New center biased search algorithm for block motion estimation. In: Proc. of International Conference on Image Processing, USA, vol. 1, pp. 410–413 (1995)
Namuduri, K.R.: Motion estimation using spatio-temporal contextual information. IEEE Transactions On Circuits And Systems For Video Technology 14(8) (August 2004)
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)
MPEG-4 Video Verification Model (Version 14.0), ISO/IEC JTC1/SC29/WG11 N2932 (October 1999)
Nisar, H., Choi, T.-S.: An Adaptive block motion estimation algorithm based on spatio temporal correlation. In: Digest of Technical papers. International Conference on Consumer Electronic, January 7-11, 2006, pp. 393–394 (2006)
Lee, Y., Kossentini, F., Smith, M., Ward, R.: Predictive RD Constrained Motion Estimation for very low bit rate video coding. IEEE J. Select Areas Commun. 15, 1752–1763 (1997)
Turga, D., Chen, T.: Estimation and Mode Decision for Spatially correlated motion sequences. IEEE transactions on CSVT 11(10), 1098–1107 (2001)
Lu, J., Liou, M.L.: A simple and efficient search algorithm for block matching motion estimation. IEEE Trans. on Circuits and Systems for Video Technology 7(2), 429–433 (1997)
Chung, P.-C., Huang, C.-L., Chen, E.-L.: A region-based selective optical flow back-projection for genuine motion vector estimation. Pattern Recognition 40(3), 1066–1077 (2007)
Kim, B.-G., Song, S.-K., Mah, P.-S.: Enhanced block motion estimation based on distortion-directional search patterns. Pattern Recognition Letters 27(12), 1325–1335 (2006)
Nie, Y., Ma, K.-K.: Adaptive rood pattern search for fast block-matching motion estimation. IEEE Trans. on Image Processing 11(12), 1442–1449 (2002)
Joint Video Team Reference Software, Version 12.2, http://iphome.hhi.de/suehring/tml/download
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Nisar, H., Choi, TS. (2008). An Adaptive Multi Pattern Scheme for Fast Block Motion Estimation. In: Gervasi, O., Murgante, B., Laganà, A., Taniar, D., Mun, Y., Gavrilova, M.L. (eds) Computational Science and Its Applications – ICCSA 2008. ICCSA 2008. Lecture Notes in Computer Science, vol 5073. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-69848-7_80
Download citation
DOI: https://doi.org/10.1007/978-3-540-69848-7_80
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-69840-1
Online ISBN: 978-3-540-69848-7
eBook Packages: Computer ScienceComputer Science (R0)