Video compression is applied for reducing the requirement of hardware, bandwidth, hard drives and power consumption for storing and processing an excessive amount of data generated by videos. The computationally intensive and most time-consuming segment of video compression is known as motion estimation (ME). ME process can be regarded as an optimization problem where search is carried out in a predefined search area of the target frame to locate the identical macroblock (MB) corresponding to each MB in anchor frame by minimizing the objective function cum search criterion as minimum value of search criterion identifies the location of the best matching MB. Since the efficiency of ME decides the efficiency of Video compression, a rich number of fast block matching algorithms (BMAs) were reported to maintain the tradeoff between the computational complexity and visual experience of video during the ME process. Investigation reveals that most of the pattern-based BMAs are prone to the local optimum and stuck in sub-optimal results. Due to the emergence of various nature-inspired algorithms (NIA) like particle swarm optimization (PSO), genetic algorithm (GA), evolutionary algorithm, etc. and their application in optimizing all types of day to day problems has opened a new era in the field of ME. Our investigation focuses on the application of all types of NIA reported to date for optimizing the ME process in terms of speed, accuracy, and quality. This investigation will analyze all the NIAs and their methodologies through an extensive study of their accompanying publications and will enable us to do a detailed comparison to highlight the competitive advantage of soft computing techniques over existing pattern-based algorithms.
JainJ. and JainA., Displacement measurement and its application in interframe image coding, IEEE Transactions on communications1981, 1799–1808.
2.
ChanM.H., YuY.B. and ConstantinidesA.G., Variable size block matching motion compensation with applications to video coding, Proceedings of IEEE (Communications, Speech, and Vision)1990, 205–212.
3.
KogaT., Motion-compensated interframe coding for video-conferencing,, New Orleans, LA, G5.3.1–5.3, Proceedings of National Telecommunication Conference1981, 5.
4.
LiR., ZengB. and LiouM.L., A new three-step search algorithm for block motion estimation, }(4), IEEE transactions on circuits and systems for video technology4 (1994, 438–442.
5.
PoL.M. and MaW.C., A novel four-step search algorithm for fast block motion estimation, IEEE transactions on circuits and systems for video technology1996, 313–317.
6.
ZhuS. and MaK.K., A new diamond search algorithm for fast block-matching motion estimation, IEEE transactions on Image Processing2000, 287–90.
7.
ZhuC., LinX. and ChauL.P., Hexagon-based search pattern for fast block motion estimation, IEEE transactions on circuits and systems for video technology2002, 349–55.
8.
CheungC.H. and PoL.M., A novel cross-diamond search algorithm for fast block motion estimation, IEEE transactions on Circuits and Systems for Video Technology2002, 1168–77.
9.
JiaH. and ZhangL., A new cross diamond search algorithm for block motion estimation., iii-, Proceedings of IEEE International Conference on Acoustics, Speech, and Signal Processing2004, 357–360.
10.
CheungC.-H. and PoL.-M., A novel small-cross-diamond search algorithm for fast video coding and videoconferencing applications, Proceedings of International Conference on Image Processing2002, 681–684.
11.
ChoiW.I., JeonB. and JeongJ., Fast motion estimation with the modified diamond search for variable motion block sizes, Proceedings of International Conference on Image Processing2003, II-371–374.
CheungC.-H. and PoL.-M., Novel cross-diamond-hexagonal search algorithms for fast block motion estimation, IEEE Transactions on Multimedia7(1) (2005, 16–22.
14.
HashadA., SadekR. and MandourS., A novel reduced diamond search algorithm with early termination for fast motion estimation, International Journal of Video & Image Process. and Network Security (IJVIPNS)2010, 14–22.
15.
HsiehC.H., LuP.C., ShynJ.S. and LuE.H., Motion estimation algorithm using inter-block correlation, Electronics Letters26(5) (1990, 276–277.
16.
TsaiJ.C., HsiehC.H., WengS.K. and LaiM.F., Block-matching motion estimation using a correlation search algorithm, Signal Processing: Image Communication13(2) (1998, 119–33.
17.
AlkanhalM., TuragaD. and ChenT., Correlation-based search algorithms for motion estimation, In Picture Coding Symposium1999, 99–102.
18.
NieY. and MaK.K., Adaptive rood pattern search for fast block-matching motion estimation, IEEE Transactions on Image processing2002, 1442–1449.
19.
ChoudhuryH.A. and SaikiaM., Comparative study of block matching algorithm for motion estimation, Proceedings of International Conference on Advanced Computer Science and Information Technology2013, 73–78.
20.
ChoudhuryH.A. and SaikiaM., Block Matching Algorithms for Motion Estimation: A Performance-Based Study, Lecture series on Advances in Communication and Computing, Springer, 2015, 149–160.
21.
FisterI.Jr, YangX.S., FisterI., BrestI. and FisterD., A brief review of nature-inspired algorithms for optimization, arXiv preprint arXiv:1307.41862013, 178–187.
22.
SiddiqueN. and AdeliH., Nature-inspired computing: an overview and some future directions, Cognitive Computation2015, 706–714.
23.
HollandJ., Adaption in Natural and Artificial Systems. University of Michigan Press, 1975.
24.
YueleiX., DuyanB. and BaixinM., A genetic search algorithm for motion estimation.” Proceedings of 5th International Conference on Signal Processing Proceedings and 16th World Computer Congress, 2000, 1058–1061.
25.
Hung-Kei ChowK. and LiouM.L., Genetic Motion Search Algorithm for Video Compression, IEEE Transactions on Circuits and System for Video Technology1993, 440–445.
26.
MoscheniF. and VesinJ.-M., A genetic algorithm for motion estimation,15° Colloquesur le traitement du signal et des images, FRA, GRETSI, Grouped’ Etudes du Traitement du Signal et des Images, 1995.
27.
El OuaaziziA., ZaimM. and BenslimaneR., A genetic algorithm for motion estimation, International Journal of Computer Science and Network Security (IJCSNS)2011, 165–172.
28.
LinC.-H. and WuJ.-L., Genetic Block Matching Algorithm for Video Coding, Proceeding of Multimedia1996, 544–547.
29.
DavisT.E. and PrincipeC.J., A simulated annealing-like convergence theory for the simple genetic algorithm, In, 174–181, Belez and Booker1991).
GorpuniP., Development of Fast Motion Estimation Algorithms for Video Compression. Diss, 2009.
32.
SoM.F. and WuA., Four-step genetic search for block motion estimation, Proceedings of the IEEE International Conference on Acoustics, Speech and Signal Processing1998, 1393–1396.
33.
ImmanuelS., PandianA. and GeorgeB.A., A study on block matching algorithms for motion estimation, (2011, 34–43.
34.
LinC.-I. and WuJ.-L., A lightweight genetic block-matching algorithm for video coding, }(4), IEEE Transactions on Circuits and Systems for Video Technology8 (1998, 386–392.
35.
RoanY.-T. and ChenP.-Y., A fuzzy search algorithm for the estimation of motion vectors, , IEEE transactions on broadcasting46 (2000, 121–127.
36.
ChenP.-Y. and JouJ.M., An efficient blocking-matching algorithm based on fuzzy reasoning, (2), IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics)31 (2001, 253–259.
37.
TsaiJ.J. and HangH.M., A genetic rhombus pattern search for block motion estimation., Proceedings of IEEE International Symposium on Circuits and Systems2007, 3655–3658.
38.
TsaiJ.J. and HangH.M., On the design of pattern-based block motion estimation algorithms, IEEE Transactions on Circuits and Systems for Video Technology2010, 136–143.
39.
PoL.-M., TingC.-W., WongK.-M. and NgK.-H., Novel point oriented inner searches for fast block motion estimation, IEEE Trans. Multimedia2007, 9–15.
40.
TsaiJ.J. and HangH.M., On adaptive pattern selection for block motion estimation algorithms,, ICASSP, I-, Proceedings of IEEE International Conference on Acoustics, Speech and Signal Processing2007, 1173–1176.
41.
TanY. and XiaoZ.M., Clonal particle swarm optimization and its applications, Proceedings of IEEE Congress on Evolutionary Computation2007, 2303–2309.
42.
TsaiJ.J. and HangH.M., On modeling genetic pattern search for block motion estimation,, ICIP, Proceedings of 15th IEEE International Conference on Image Processing2008, 1980–1983.
43.
KennedyJ., Particle swarm optimization, In Encyclopedia of machine learning, Springer, Boston, MA, 2011, 760–766.
44.
DuG.Y., HuangT.S., SongL.X. and ZhaoB.J., A novel fast motion estimation method based on particle swarm optimization, Proceedings of International Conference on Machine Learning and Cybernetics2005, 5038–5042.
45.
YuanX. and ShenX., Block matching algorithm based on particle swarm optimization for motion estimation, Proceedings of International Conference on Embedded Software and Systems (ICESS)2008, 191–195.
46.
BakwadK.M., PattnaikS.S., SohiB.S., DeviS., GollapudiS.V., SagarC.V. and PatraP.K., Small population-based modified parallel particle swarm optimization for motion estimation, Proceedings of 16th International Conference on Advanced Computing and Communications (ADCOM)2008, 367–373.
47.
DamodharanK. and MuthusamyT., Analysis of particle swarm optimization in block matching algorithms for video coding, Scientific Journal of Circuit System and Signal Processing2014, 17–23.
48.
ThamaraiM. and ShanmugalakshmiR., Video coding using Directed Particle Swarm Optimization, CiiT International Journal of Digital Image Processing, 2010.
49.
NagpalP. and BaghlaS., Video compression by the memetic algorithm, International Journal of Advanced Computer Science and Applications (IJACSA)2011, 142–145.
50.
ZhangP., WeiP., YuH.Y. and FeiC., A novel search algorithm based on particle swarm optimization and simplex method for block motion estimation, International Journal of Digital Content Technology and its Applications2011, 207–216.
51.
ZhangP., WeiP., YuH. and WangZ., Simplex particle swarm optimization for block matching algorithm, Proceedings of International Symposium on Intelligent Signal Processing and Communication Systems (ISPACS)2010, 1–4.
52.
ShiZ., FernandoW.A.C., KondozA. and de Sales Guerra TsuzukiM., Simulated annealing for fast motion estimation algorithm in H. 264/AVC, Simulated Annealing-Single and Multiple Objective Problems2012, 978–953.
53.
CuevasE., ZaldivarD., Pérez-CisnerosM. and OlivaD., Block-matching algorithm based on differential evolution for motion estimation, Engineering Applications of Artificial Intelligence2013, 488–498.
54.
CuevasE., ZaldívarD., Pérez-CisnerosM., SossaH. and OsunaV., Block matching algorithm for motion estimation based on Artificial Bee Colony (ABC), Applied Soft Computing2013, 3047–3059.
55.
JalloulM.K., A novel parallel computing approach for motion estimation based on particle swarm optimization, Proceedings of the International Conference on Engineering of Recon Fig.urable Systems and Algorithms (ERSA), 2013.
56.
CuevasE., Block-matching algorithm based on harmony search optimization for motion estimation, Applied intelligence2013, 165–83.
57.
KungC.M., ChengW.S. and JengJ.H., Application of genetic algorithm to hexagon-based motion estimation, The Scientific World Journal2014, 1–12.
58.
HadiI. and SabahM., A novel block matching algorithm based on cat swarm optimization for efficient motion estimation, International Journal of Digital Content Technology and its Applications2014, 33–38.
59.
HadiI. and SabahM., Improvement cat swarm optimization for efficient motion estimation, International Journal of Hybrid Inf. Technology, 2015, 279–94.
60.
BhattacharjeeK. and KumarS., A novel block matching algorithm based on Cuckoo search, Proceedings of 2nd International Conference on Telecommunication and Networks (TEL-NET)2017, 1–5.
61.
WorasucheepC., An opposition-based hybrid Artificial Bee Colony with differential evolution, IEEE Congress on Evolutionary Computation (CEC)2015, 2611–2618.
62.
ChakrabortyP., RoyG.G., DasS., JainD. and AbrahamA., An improved harmony search algorithm with differential mutation operator, Fundamental Informaticae2009, 401–426.
63.
BhattacharjeeK., KumarS., PandeyH.M., PantM., WindridgeD. and ChaudharyA., An improved block matching algorithm for motion estimation in video sequences and application in robotics, Computers & Electrical Engineering2018, 92–106.
64.
MoreV.N., Prashant BartakkeP. and SutaoneM.S., Accelerating motion estimation by genetic algorithm approach in x265, Journal of Electronic Imaging27 (2018), 1–13.
65.
BetkaA., TerkiN., ToumiA. and DahmaniH., Grey wolf optimizer-based learning automata for solving block matching problem, Signal, Image and Video Processing (2019), 1–9.
66.
AmirpourH., GhanbariM., PinheiroA. and PereiraM., Motion estimation with chessboard pattern prediction strategy, Multimedia Tools and Applications2019, 1–20.
