Fuzzy Logic Based Three Step Search Algorithm for Motion Vector Estimation

Full Text (PDF, 359KB), PP.37-43

Views: 0 Downloads: 0


Suvojit Acharjee 1,* Sheli Sinha Chaudhuri 1

1. Department of Electronics and Telecommunication Engineering, Jadavpur University Jadavpur, Kolkata, India

* Corresponding author.

DOI: https://doi.org/10.5815/ijigsp.2012.02.06

Received: 8 Dec. 2011 / Revised: 10 Jan. 2012 / Accepted: 7 Feb. 2012 / Published: 8 Mar. 2012

Index Terms

Three Step Search, Fuzzy logic based Three Step Search, Motion vector Estimation with Fuzzy, Fuzzy Block Matching Algorithm


Motion compensation process is the most computationally expensive operation in the entire video compression process. Fast motion estimation technique plays a very important role in video compression standard. In Block Matching Algorithm Full Search Algorithm produces the best result for motion vector estimation. But Full Search algorithm is a time consuming and computationally expensive process. The Challenge is to reduce the computational complexity of Full Search algorithm without losing too much quality at the output.
In this paper we propose to implement the fuzzy logic based Three Step Search algorithm. This Algorithm performs better than the Three Step Search(TSS), New Three Step Search(NTSS), Four Step Search(FSS) algorithm.

Cite This Paper

Suvojit Acharjee,Sheli Sinha Chaudhuri,"Fuzzy Logic Based Three Step Search Algorithm for Motion Vector Estimation", IJIGSP, vol.4, no.2, pp.37-43, 2012. DOI: 10.5815/ijigsp.2012.02.06 


[1]J. Jain and A. Jain, “Displacement measurement and its application in interframe image coding,” IEEE Trans. Commun., vol. COMM-29, pp.1799–1808, Dec. 1981.

[2]T. Koga, K. Iinuma, A. Hirano, Y. Iijima, andT. Ishiguro, “Motion compensated interframe coding for video conferencing,” in Proc. National Telecommunication. Conf., New Orleans, LA, Nov.29–Dec. 3 1981, pp. G5.3.1–.3.5.

[3]R. Li, B. Zeng, and M. L. Liou, “A new three step search algorithm for block motion estimation,” IEEE Trans. Circuits Syst. Video Technol., vol. 4, pp. 438–442, Aug. 1994.

[4]L. M. Po and W. C. Ma, “A novel four-step search algorithm for fast block motion estimation,” IEEE Trans. Circuits Syst. Video Technol., vol. 6, pp. 313–317, June 1996.

[5]L. K. Liu and E. Feig, “A block-based gradient descent search algorithm for block motion estimation in video coding,” IEEE Trans. Circuits System Video Technol., vol. 6, pp. 419–423, Aug. 1996

[6]Shan Zhu, and Kai-Kuang Ma, “ A New Diamond Search Algorithm for Fast Block-Matching Motion Estimation”, IEEE Trans. Image Processing, vol 9, no. 2, pp. 287-290, February 2000. [7]

Ce Zhu, Xiao Lin, and Lap-Lui Chau,”Hexagon based Search Pattern for Fast Block Motion Estimation ” , IEEE Trans. On circuits and systems for video technology, Vol.12, No.5,May 2002

[8]J.Y. Tham, S. Ranganath, M. Ranganath, A.A.Kassim, “A novel unrestricted centerbiased diamond search algorithm for block motion estimation”, IEEE Trans. Circuits Systems VideoTechnol. 8 (August 1998) 369–377.

[9]Y.Q.Shi and H Sun, “Image and Video Compression for Multimedia Engineering “

[10]Walker D.R., Rao.K.R. ”Improved Pel-Recursive Motion Compensation”, IEEE trans on Communications, vol com 32,no. 10, Oct. 1984, 1128-1134.

[11]A.N.Netravali and J.D.Robbins, “Motion compensated television coding-part1”, Bell syst. Tech.J., Vol.58,pp 631-670,Mar.1979

[12]Jianhua Lu amd Ming L.Liou “ A Simple and Efficient search algorithm for Block Matching Motion Estimation”, IEEE trans circuits And Systems for Video Technology, Vol 7,no,2,pp. 429-433 april 1997

[13]A Barjatya, “Block Matching Algorithms For Motion Estimation,” DIP 6620 Spring 2004 Final Project Paper

[14]H.C.Bergmann, “Displacement estimation based on the correlation of image”,IEEE proceedings of International conference on Image processing,York,England,july 1982,pp. 215-219.

[15]L.P.Chau and C.Zhu, “A fast octagon-based search algorithm for motion estimation”, Elsevier Science Signal processing 83,2003,pp. 671-675.

[16]Yao Nie and Kai Kuang Ma, “Adaptive Rood Pattern Search for Fast Block Matching Motion Estimation”, IEEE transaction on Image Processing,Vol 11,no. 12,1442-1448,December 2002.

[17]M. Ghanbari, “ The Cross Search Algorithm for motion Estimation”, IEEE Transaction on Communication vol. 38, pp. 950-953, july 1990.

[18]W. Li and E. Salari, “Successive elimination Algorithm for motion Estimation”, IEEE transaction on Image Processing ,Vol 4,no 1,pp. 105-107,January 1995.

[19]Y.C. Lin and S.C. Tai, “Fast Full Search Block matching algorithm for motion compensated video compression”, IEEE transactions on Communications, Vol 45, no. 5 pp. 527-531, May 1997