ArTS Archivio della ricerca di Trieste
ArTS è il sistema di gestione integrata dei dati della ricerca adottato dall' Università degli Studi di Trieste
EnglishDynamic 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.
| Titolo: | An effective and efficient approximate two-dimensional dynamic programming algorithm for supporting advanced computer vision applications |
| Autori: | |
| Data di pubblicazione: | 2017 |
| Stato di pubblicazione: | Pubblicato |
| Rivista: | |
| 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. |
| Handle: | http://hdl.handle.net/11368/2928906 |
| Digital Object Identifier (DOI): | http://dx.doi.org/10.1016/j.jvlc.2017.07.002 |
| URL: | https://www.sciencedirect.com/science/article/pii/S1045926X17300046 |
| Appare nelle tipologie: | 1.1 Articolo in Rivista |
File in questo prodotto:
| File | Descrizione | Tipologia | Licenza | |
|---|---|---|---|---|
| JVLC2017.pdf | Articolo principale | Bozza finale post-referaggio (post-print) | Digital Rights Management non definito | Open Access Visualizza/Apri |
| 1-s2.0-S1045926X17300046-main.pdf | Documento in Versione Editoriale | Copyright Editore | Administrator Richiedi una copia |
http://hdl.handle.net/11368/2928906
