Skip to main content
Erschienen in: Microsystem Technologies 6/2018

10.11.2017 | Technical Paper

Performance analysis of diamond search algorithm over full search algorithm

verfasst von: Rahul Priyadarshi, Surender Kumar Soni, Rampal Bhadu, Vijay Nath

Erschienen in: Microsystem Technologies | Ausgabe 6/2018

Einloggen

Aktivieren Sie unsere intelligente Suche um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

Motion estimation is a progression used to estimate motion vectors between two or more images with a high degree of temporal redundancy. It is commonly used in video compression to attain high compression ratios as well as used in several applications for object tracking. In this paper a novel approach for diamond search algorithm has been recommended to overcome the problem encountered by several existing block matching algorithms especially with full search algorithm in reference of peak signal-to-noise ratio, required number of examine or search points as well as computational complexity. Simulation results reflect that recommended algorithm acting well compared to all existing algorithms. Experimentally 88–99% of the motion vectors are found inside the circle which has radius of 3-pixel unit and fixed on the place of zero motion. The proposed algorithm is used to implement various standards examples such as MPEG1 and MPEG4.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Literatur
Zurück zum Zitat Barjatya A (2004) Block matching algorithms for motion estimation. IEEE Trans Evol Comput 8(3):225–229CrossRef Barjatya A (2004) Block matching algorithms for motion estimation. IEEE Trans Evol Comput 8(3):225–229CrossRef
Zurück zum Zitat Bergen JR, Anandan P, Hanna KJ, Hingorani R (1992) Hierarchical model-based motion estimation. In: Lecture notes in computer science (including subseries lecture notes in artificial intelligence and lecture notes in bioinformatics), LNCS 588:237–252 Bergen JR, Anandan P, Hanna KJ, Hingorani R (1992) Hierarchical model-based motion estimation. In: Lecture notes in computer science (including subseries lecture notes in artificial intelligence and lecture notes in bioinformatics), LNCS 588:237–252
Zurück zum Zitat Brünig M, Niehsen W (2001) Fast full-search block matching. IEEE Trans Circuits Syst Video Technol 11(2):241–247CrossRef Brünig M, Niehsen W (2001) Fast full-search block matching. IEEE Trans Circuits Syst Video Technol 11(2):241–247CrossRef
Zurück zum Zitat Cai J, David Pan W (2012) On fast and accurate block-based motion estimation algorithms using particle swarm optimization. Inf Sci (Ny) 197:53–64CrossRef Cai J, David Pan W (2012) On fast and accurate block-based motion estimation algorithms using particle swarm optimization. Inf Sci (Ny) 197:53–64CrossRef
Zurück zum Zitat Dikbas S, Altunbasak Y (2013) Novel true-motion estimation algorithm and its application to motion-compensated temporal frame interpolation. IEEE Trans Image Process 22(8):2931–2945MathSciNetCrossRefMATH Dikbas S, Altunbasak Y (2013) Novel true-motion estimation algorithm and its application to motion-compensated temporal frame interpolation. IEEE Trans Image Process 22(8):2931–2945MathSciNetCrossRefMATH
Zurück zum Zitat Ertürk S (2007) A new perspective to block motion estimation for video compression: high-frequency component matching. IEEE Signal Process Lett 14(2):113–116CrossRef Ertürk S (2007) A new perspective to block motion estimation for video compression: high-frequency component matching. IEEE Signal Process Lett 14(2):113–116CrossRef
Zurück zum Zitat Farsiu S, Robinson MD, Elad M, Milanfar P (2004) Fast and robust multiframe super resolution. IEEE Trans Image Process 13(10):1327–1344CrossRef Farsiu S, Robinson MD, Elad M, Milanfar P (2004) Fast and robust multiframe super resolution. IEEE Trans Image Process 13(10):1327–1344CrossRef
Zurück zum Zitat Feghali R (2005) Multi-frame simultaneous motion estimation and segmentation. IEEE Trans Consum Electron 51(1):245–248CrossRef Feghali R (2005) Multi-frame simultaneous motion estimation and segmentation. IEEE Trans Consum Electron 51(1):245–248CrossRef
Zurück zum Zitat Gao XQ, Duanmu CJ, Zou CR (2000) A multilevel successive elimination algorithm for block matching motion estimation. IEEE Trans Image Process 9(3):501–504CrossRef Gao XQ, Duanmu CJ, Zou CR (2000) A multilevel successive elimination algorithm for block matching motion estimation. IEEE Trans Image Process 9(3):501–504CrossRef
Zurück zum Zitat Jing X, Chau LP (2004) An efficient three-step search algorithm for block motion estimation. IEEE Trans. Multimed 6(3):435–438CrossRef Jing X, Chau LP (2004) An efficient three-step search algorithm for block motion estimation. IEEE Trans. Multimed 6(3):435–438CrossRef
Zurück zum Zitat Jung H, Ye JC (2010) Motion estimated and compensated compressed sensing dynamic magnetic resonance imaging: what we can learn from video compression techniques. Int J Imaging Syst Technol 20(2):81–98CrossRef Jung H, Ye JC (2010) Motion estimated and compensated compressed sensing dynamic magnetic resonance imaging: what we can learn from video compression techniques. Int J Imaging Syst Technol 20(2):81–98CrossRef
Zurück zum Zitat Karunakar AK, Pai MMM (2009) Motion-compensated temporal filtering with optimized motion estimation. J Real-Time Image Process 4(4):329–338CrossRef Karunakar AK, Pai MMM (2009) Motion-compensated temporal filtering with optimized motion estimation. J Real-Time Image Process 4(4):329–338CrossRef
Zurück zum Zitat Kim M (2005) A fast VLSI architecture for full-search variable block size motion estimation in MPEG-4 AVC/H.264. Proc. ASP-DAC 2005. Asia South Pacific Des Autom Conf 1:631–634 Kim M (2005) A fast VLSI architecture for full-search variable block size motion estimation in MPEG-4 AVC/H.264. Proc. ASP-DAC 2005. Asia South Pacific Des Autom Conf 1:631–634
Zurück zum Zitat Kim JN, Choi TS (1998) A fast three-step search algorithm with minimum checking points using unimodal error surface assumption. IEEE Trans Consum Electron 44(3):638–648CrossRef Kim JN, Choi TS (1998) A fast three-step search algorithm with minimum checking points using unimodal error surface assumption. IEEE Trans Consum Electron 44(3):638–648CrossRef
Zurück zum Zitat Li R, Zeng B, Liou ML (1994) A new three-step search algorithm for block motion estimation. IEEE Trans Circuits Syst Video Technol 4(4):438–442CrossRef Li R, Zeng B, Liou ML (1994) A new three-step search algorithm for block motion estimation. IEEE Trans Circuits Syst Video Technol 4(4):438–442CrossRef
Zurück zum Zitat Lin YC, Tai SC (1997) Fast full-search block-matching algorithm for motion-compensated video compression. IEEE Trans Commun 45(5):527–531CrossRef Lin YC, Tai SC (1997) Fast full-search block-matching algorithm for motion-compensated video compression. IEEE Trans Commun 45(5):527–531CrossRef
Zurück zum Zitat Luo J, Konofagou E (2010) A fast normalized cross-correlation calculation method for motion estimation. IEEE Trans Ultrason Ferroelectr Freq Control 57(6):1347–1357CrossRef Luo J, Konofagou E (2010) A fast normalized cross-correlation calculation method for motion estimation. IEEE Trans Ultrason Ferroelectr Freq Control 57(6):1347–1357CrossRef
Zurück zum Zitat Luo J, Ahmad I, Liang Y, Swaminathan V (2008) Motion estimation for content adaptive video compression. IEEE Trans Circuits Syst Video Technol 18(7):900–909CrossRef Luo J, Ahmad I, Liang Y, Swaminathan V (2008) Motion estimation for content adaptive video compression. IEEE Trans Circuits Syst Video Technol 18(7):900–909CrossRef
Zurück zum Zitat Niitsuma H, Maruyama T (2010) Sum of absolute difference implementations for image processing on FPGAs. In: Proceedings—2010 international conference on field programmable logic and applications, FPL 2010, pp 167–170 Niitsuma H, Maruyama T (2010) Sum of absolute difference implementations for image processing on FPGAs. In: Proceedings—2010 international conference on field programmable logic and applications, FPL 2010, pp 167–170
Zurück zum Zitat Nisar H, Choi T-S (2000) Fast four step search algorithm using UESA and quadrant selection approach for motion estimation. In: Proceedings of SPIE—the international society for optical engineering, vol. 3974 Nisar H, Choi T-S (2000) Fast four step search algorithm using UESA and quadrant selection approach for motion estimation. In: Proceedings of SPIE—the international society for optical engineering, vol. 3974
Zurück zum Zitat Ouyang W, Tombari F, Mattoccia S, Di Stefano L, Cham WK (2012) Performance evaluation of full search equivalent Pattern matching algorithms. IEEE Trans Pattern Anal Mach Intell 34(1):127–143CrossRef Ouyang W, Tombari F, Mattoccia S, Di Stefano L, Cham WK (2012) Performance evaluation of full search equivalent Pattern matching algorithms. IEEE Trans Pattern Anal Mach Intell 34(1):127–143CrossRef
Zurück zum Zitat Pal M (2015) An optimized block matching algorithm for motion estimation using logical image. Int Conf Comput Commun Autom ICCCA 2015:1138–1142 Pal M (2015) An optimized block matching algorithm for motion estimation using logical image. Int Conf Comput Commun Autom ICCCA 2015:1138–1142
Zurück zum Zitat Po Lai-man, Ma Wing-chung (1996a) A novel four-step search algorithm for fast block motion estimation. IEEE Trans Circuits Syst Video Technol 6(3):313–317CrossRef Po Lai-man, Ma Wing-chung (1996a) A novel four-step search algorithm for fast block motion estimation. IEEE Trans Circuits Syst Video Technol 6(3):313–317CrossRef
Zurück zum Zitat Po L, Ma W (1996b) A novel four-step search algorithm for fast block motion estimation. Circuits Syst Video Technol 6(3):313–317CrossRef Po L, Ma W (1996b) A novel four-step search algorithm for fast block motion estimation. Circuits Syst Video Technol 6(3):313–317CrossRef
Zurück zum Zitat Sullivan GJ, Wiegand T (2005) Video compression-from concepts to the H.264/AVC standard. Proc IEEE 93(1):18–31CrossRef Sullivan GJ, Wiegand T (2005) Video compression-from concepts to the H.264/AVC standard. Proc IEEE 93(1):18–31CrossRef
Zurück zum Zitat Sullivan GJ, Ohm JR, Han WJ, Wiegand T (2012) Overview of the high efficiency video coding (HEVC) standard. IEEE Trans Circuits Syst Video Technol 22(12):1649–1668CrossRef Sullivan GJ, Ohm JR, Han WJ, Wiegand T (2012) Overview of the high efficiency video coding (HEVC) standard. IEEE Trans Circuits Syst Video Technol 22(12):1649–1668CrossRef
Zurück zum Zitat Sun NN, Fan C, Xia X (2009) An effective three-step search algorithm for motion estimation. In: ITME2009—proceedings 2009 IEEE international symposium on IT in medicine and education, pp 400–403 Sun NN, Fan C, Xia X (2009) An effective three-step search algorithm for motion estimation. In: ITME2009—proceedings 2009 IEEE international symposium on IT in medicine and education, pp 400–403
Zurück zum Zitat Vassiliadis S, Hakkennes EA, Wong JSSM, Pechanek GG (1998) The sum-absolute-difference motion estimation accelerator. In: Proceedings. 24th EUROMICRO Conf. (Cat. No.98EX204), vol. 2 Vassiliadis S, Hakkennes EA, Wong JSSM, Pechanek GG (1998) The sum-absolute-difference motion estimation accelerator. In: Proceedings. 24th EUROMICRO Conf. (Cat. No.98EX204), vol. 2
Zurück zum Zitat Wiegand T (2003) Overview of the H.264/AVC video coding standard. Syst Video 13(7):560–576CrossRef Wiegand T (2003) Overview of the H.264/AVC video coding standard. Syst Video 13(7):560–576CrossRef
Zurück zum Zitat Yaakob R, Aryanfar A, Halin AA, Sulaiman N (2013) A comparison of different block matching algorithms for motion estimation. Procedia Technol 11(Iceei):199–205CrossRef Yaakob R, Aryanfar A, Halin AA, Sulaiman N (2013) A comparison of different block matching algorithms for motion estimation. Procedia Technol 11(Iceei):199–205CrossRef
Metadaten
Titel
Performance analysis of diamond search algorithm over full search algorithm
verfasst von
Rahul Priyadarshi
Surender Kumar Soni
Rampal Bhadu
Vijay Nath
Publikationsdatum
10.11.2017
Verlag
Springer Berlin Heidelberg
Erschienen in
Microsystem Technologies / Ausgabe 6/2018
Print ISSN: 0946-7076
Elektronische ISSN: 1432-1858
DOI
https://doi.org/10.1007/s00542-017-3625-0

Weitere Artikel der Ausgabe 6/2018

Microsystem Technologies 6/2018 Zur Ausgabe

Neuer Inhalt