Dynamic programming is a popular optimization technique, developed in the 60’s and still widely used today in several fields for its ability to find global optimum. Dynamic Programming Algorithms (DPAs) can be developed in many dimension. However, it is known that if the DPA dimension is greater or equal to two, the algorithm is an NP complete problem. In this paper we present an approximation of the fully two- dimensional DPA (2D-DPA) with polynomial complexity. Then, we describe an implementation of the algorithm on a recent parallel device based on CUDA architecture. We show that our parallel implementation presents a speed-up of about 25 with respect to a sequential implementation on an Intel I7 CPU. In particular, our system allows a speed of about ten 2D-DPA executions per second for 85 × 85 pixels images. In the experimental Section of the paper we report some image warping examples performed with our CUDA-based 2D-DPA and speed-up figures.

An efficient CUDA-based approximate two-dimensional dynamic programming algorithm for advanced computer vision applications

CUZZOCREA, Alfredo Massimiliano;MUMOLO, ENZO;
2016

Abstract

Dynamic programming is a popular optimization technique, developed in the 60’s and still widely used today in several fields for its ability to find global optimum. Dynamic Programming Algorithms (DPAs) can be developed in many dimension. However, it is known that if the DPA dimension is greater or equal to two, the algorithm is an NP complete problem. In this paper we present an approximation of the fully two- dimensional DPA (2D-DPA) with polynomial complexity. Then, we describe an implementation of the algorithm on a recent parallel device based on CUDA architecture. We show that our parallel implementation presents a speed-up of about 25 with respect to a sequential implementation on an Intel I7 CPU. In particular, our system allows a speed of about ten 2D-DPA executions per second for 85 × 85 pixels images. In the experimental Section of the paper we report some image warping examples performed with our CUDA-based 2D-DPA and speed-up figures.
9781509018970
http://ieeexplore.ieee.org/document/7844899/
File in questo prodotto:
File Dimensione Formato  
IEEE_SMC2016.pdf

non disponibili

Tipologia: Documento in Versione Editoriale
Licenza: Digital Rights Management non definito
Dimensione 450.9 kB
Formato Adobe PDF
450.9 kB Adobe PDF   Visualizza/Apri   Richiedi una copia
2016 IEEE International Conference on Systems, Man, and Cybernetics.pdf

non disponibili

Descrizione: Table of contents
Tipologia: Documento in Versione Editoriale
Licenza: Digital Rights Management non definito
Dimensione 6.99 MB
Formato Adobe PDF
6.99 MB Adobe PDF   Visualizza/Apri   Richiedi una copia

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11368/2894358
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 2
  • ???jsp.display-item.citation.isi??? 0
social impact