Optimal Piecewise Linear Function Approximation for GPU-based Applications

Berjón Díez, Daniel and Gallego Bonet, Guillermo and Cuevas Rodríguez, Carlos and Morán Burgos, Francisco and García Santos, Narciso (2015). Optimal Piecewise Linear Function Approximation for GPU-based Applications. "IEEE Transactions on Cybernetics" ; pp. 1-12. ISSN 2168-2267. https://doi.org/10.1109/TCYB.2015.2482365.

Description

Title: Optimal Piecewise Linear Function Approximation for GPU-based Applications
Author/s:
  • Berjón Díez, Daniel
  • Gallego Bonet, Guillermo
  • Cuevas Rodríguez, Carlos
  • Morán Burgos, Francisco
  • García Santos, Narciso
Item Type: Article
Título de Revista/Publicación: IEEE Transactions on Cybernetics
Date: 9 October 2015
ISSN: 2168-2267
Subjects:
Freetext Keywords: computer vision, image processing, numerical approximation and analysis, error equalization, orthogonal projection, parallel processing, piecewise linearization, system linearization, error bounds, graphics processing units, Gaussian function, Lorentzian function, Bessel function
Faculty: E.T.S.I. Telecomunicación (UPM)
Department: Señales, Sistemas y Radiocomunicaciones
UPM's Research Group: Tratamiento de Imágenes GTI
Creative Commons Licenses: Recognition - No derivative works - Non commercial

Full text

[img]
Preview
PDF - Requires a PDF viewer, such as GSview, Xpdf or Adobe Acrobat Reader
Download (730kB) | Preview

Abstract

Many computer vision and human-computer interaction applications developed in recent years need evaluating complex and continuous mathematical functions as an essential step toward proper operation. However, rigorous evaluation of this kind of functions often implies a very high computational cost, unacceptable in real-time applications. To alleviate this problem, functions are commonly approximated by simpler piecewise-polynomial representations. Following this idea, we propose a novel, efficient, and practical technique to evaluate complex and continuous functions using a nearly optimal design of two types of piecewise linear approximations in the case of a large budget of evaluation subintervals. To this end, we develop a thorough error analysis that yields asymptotically tight bounds to accurately quantify the approximation performance of both representations. It provides an improvement upon previous error estimates and allows the user to control the trade-off between the approximation error and the number of evaluation subintervals. To guarantee real-time operation, the method is suitable for, but not limited to, an efficient implementation in modern Graphics Processing Units (GPUs), where it outperforms previous alternative approaches by exploiting the fixed-function interpolation routines present in their texture units. The proposed technique is a perfect match for any application requiring the evaluation of continuous functions, we have measured in detail its quality and efficiency on several functions, and, in particular, the Gaussian function because it is extensively used in many areas of computer vision and cybernetics, and it is expensive to evaluate.

Funding Projects

TypeCodeAcronymLeaderTitle
Government of SpainTEC2013-48453MR-UHDTVUnspecifiedMixed Reality over Ultra High Definition Television
FP7610691BRIDGETUnspecifiedBridging the Gap for Enhanced Broadcast

More information

Item ID: 38077
DC Identifier: http://oa.upm.es/38077/
OAI Identifier: oai:oa.upm.es:38077
DOI: 10.1109/TCYB.2015.2482365
Official URL: https://ieeexplore.ieee.org/document/7295573
Deposited by: Dr Guillermo Gallego Bonet
Deposited on: 13 Oct 2015 08:12
Last Modified: 03 Jun 2019 14:08
  • Logo InvestigaM (UPM)
  • Logo GEOUP4
  • Logo Open Access
  • Open Access
  • Logo Sherpa/Romeo
    Check whether the anglo-saxon journal in which you have published an article allows you to also publish it under open access.
  • Logo Dulcinea
    Check whether the spanish journal in which you have published an article allows you to also publish it under open access.
  • Logo de Recolecta
  • Logo del Observatorio I+D+i UPM
  • Logo de OpenCourseWare UPM