Abstract

In this study, a fast block matching search algorithm based on blocks' descriptors and multilevel blocks filtering is introduced. The used descriptors are the mean and a set of centralized low order moments. Hierarchal filtering and MAE similarity measure were adopted to nominate the best similar blocks lay within the pool of neighbor blocks. As next step to blocks nomination the similarity of the mean and moments is used to classify the nominated blocks and put them in one of three sub-pools, each one represents certain nomination priority level (i.e., most, less & least level). The main reason of the introducing nomination and classification steps is a significant reduction in the number of matching instances of the pixels belong to the compared blocks is achieved. Instead of pixels-wise comparisons a set of hierarchal similarity comparisons between few descriptors of the compared blocks is done. The computations of blocks descriptors have linear complexity, O(n) and small number of involved similarity comparisons is required. As final stage, the selected blocks as the best similar blocks according to their descriptors are only pushed to pixel-wise blocks comparison stage. The performance of the proposed system was tested for both cases: (i) without using prediction for assessing the initial motion vector and (ii) with using prediction that based on the determined motion vectors of already scanned neighbor blocks. The test results indicated that the introduced method for both cases (without/ with prediction) can lead to promising results in terms of time and error level; because there is reduction in search time and error level parameters in comparison with exhaustive search and three step search (TSS) algorithms.

Keywords:

Block Matching Algorithm, Descriptor, Exhaustive Search, Hierarchal Filtering, Moments, Predicted Motion Vector, Three Step Search (TSS),

References

1. Ahmed, Z., A.J. Hussain and D. Al-Jumeily, 2011. Fast computations of full search block matching motion estimation (FCFS). IEEE T. Commun., pp: 1-6.
   
2. Aziz, T. and D.R.J. Dolly, 2012. Motion estimation and motion compensated video compression using DCT and DWT. Int. J. Emerg. Technol. Adv. Eng., 2(12): 667-671. http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.414.5587&rep=rep1&type=pdf.
   Direct Link
3. Bhavsar, D.D. and R.N. Gonawala, 2014. Three step search method for block matching algorithm. Proceeding of IRF International Conference. Pune, India, pp: 101-104.
   
4. Jagiwala, D.D. and S.N. Shah, 2012. Analysis of block matching algorithms for motion estimation in H.264 Video CODEC. Int. J. Eng. Res. Appl. (IJERA), 2(6): 1396-1401. http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.415.4744&rep=rep1&type=pdf.
   Direct Link
5. Jie-Rong, G. and L. Chang-Qing, 2011. Application of an improved motion estimated three step search algorithm in infrared video. Proc. Eng., 15: 2624-2628. http://www.sciencedirect.com/science/article/pii/S1877705811019941.
   Direct Link
6. Khammar, M.R., 2012. Evaluation of different block matching algorithms to motion estimation. Int. J. VLSI Embed. Syst. (IJVES), 03(03): 148-153.
   
7. Kilthau, S.L., M.S. Drew and T. Möller, 2002. Full search content independent block matching based on the fast fourier transform. Proceeding of the IEEE International Conference on Image Processing, 1: 669-672.
   CrossRef    
8. Kiran, K.K. Sharma and S. Chauhan, 2014. A review on variants of block matching for motion detection in videos. Int. J. Res. Aspects Eng. Manage., 1(2): 73-75. http://emax.edu.in/journal/vol1-02/IJRAEM-01-02-21.pdf.
   
9. Kulkarni, S.M., D.S. Bormane and S.L. Nalbalwar, 2014. Coding of video sequences using block matching motion estimation three steps search algorithms. Int. J. Innov. Res. Electr. Electron. Instrum. Control Eng., 2(6): 1651-1655. http://ijireeice.com/upload/2014/june/IJIREEICE3E%20s%20shamsundar_Coding_of_video.pdf.
   Direct Link
10. Love, N.S. and C. Kamath, 2006. An empirical study of block matching techniques for the detection of moving objects. UCRL-TR-218038 Lawrence Livermore National Laboratory. https://e-reports-ext.llnl.gov/pdf/329054.pdf.
    Direct Link
11. Manikandan, L.C. and R.K. Selvakumar, 2014. A new survey on block matching algorithms in video coding. Int. J. Eng. Res., 3(2): 121-125. http://www.ijer.in/ijer/publication/v3s2/IJER_2014_218.pdf.
    Direct Link
12. Manjunatha, D.V. and Sainarayanan, 2011. Comparison and implementation of fast block matching motion estimation algorithms for video compresssion. Int. J. Eng. Sci. Technol. (IJEST), 3(10): 7608-7613. https: //www.idc-online.com/technical_references/ pdfs/electronic_engineering/COMPARISON%20AND%20IMPLEMENTATION%20OF%20FAST%20BLOCK%20MATCHING%20MOTION%20ESTIMATION%20ALGORITHMS%20FOR%20VIDEO%20COMPRESSSION.pdf.
    Direct Link
13. Reddy, V.S. and S. Sengupta, 2008. A fast predictive algorithm and architecture for block matching motion estimation. ICGST-GVIP J., 8(1): 9-16.
    
14. Vijay, B., G. Hegde and S. Sanju, 2014. Fast block-matching motion estimation using modified diamond search algorithm. Int. J. Adv. Comput. Eng. Communi. Technol. (IJACECT), 3(1): 1-6. http://www.irdindia.co.in/journal/journal_ijacect/pdf/vol3_iss1/1.pdf.
    Direct Link

Competing interests

The authors have no competing interests.

Open Access Policy

This article is distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made.

Copyright

The authors have no competing interests.