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. Experiments and case studies support our thesis.

An effective and efficient approximate two-dimensional dynamic programming algorithm for supporting advanced computer vision applications

Cuzzocrea, Alfredo
;
Mumolo, Enzo;Vercelli, Gianni
2017-01-01

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. Experiments and case studies support our thesis.
File in questo prodotto:
File Dimensione Formato  
JVLC2017.pdf

Open Access dal 03/08/2019

Descrizione: Articolo principale
Tipologia: Bozza finale post-referaggio (post-print)
Licenza: Digital Rights Management non definito
Dimensione 1.05 MB
Formato Adobe PDF
1.05 MB Adobe PDF Visualizza/Apri
1-s2.0-S1045926X17300046-main.pdf

Accesso chiuso

Tipologia: Documento in Versione Editoriale
Licenza: Copyright Editore
Dimensione 2.01 MB
Formato Adobe PDF
2.01 MB Adobe PDF   Visualizza/Apri   Richiedi una copia
Pubblicazioni consigliate

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: https://hdl.handle.net/11368/2928906
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 1
  • ???jsp.display-item.citation.isi??? 1
social impact