1. Optimal Piecewise Linear Function Approximation for GPU-based Applications
- Author
-
Daniel Berjón, Narciso Garcia, Guillermo Gallego, Francisco Morán, and Carlos Cuevas
- Subjects
Optimal design ,FOS: Computer and information sciences ,Mathematical optimization ,Matemáticas ,Computer Vision and Pattern Recognition (cs.CV) ,Computer Science - Computer Vision and Pattern Recognition ,02 engineering and technology ,Systems and Control (eess.SY) ,Piecewise linear function ,symbols.namesake ,Approximation error ,0202 electrical engineering, electronic engineering, information engineering ,Gaussian function ,FOS: Mathematics ,FOS: Electrical engineering, electronic engineering, information engineering ,Electrical and Electronic Engineering ,Graphics ,Mathematics - Optimization and Control ,Mathematics ,Informática ,Telecomunicaciones ,Computer Science - Numerical Analysis ,020206 networking & telecommunications ,Numerical Analysis (math.NA) ,Computer Science Applications ,Human-Computer Interaction ,Function approximation ,Computer Science - Distributed, Parallel, and Cluster Computing ,Control and Systems Engineering ,Optimization and Control (math.OC) ,symbols ,Computer Science - Systems and Control ,020201 artificial intelligence & image processing ,Linear approximation ,Distributed, Parallel, and Cluster Computing (cs.DC) ,Software ,Information Systems ,Interpolation - 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., Comment: 12 pages, 12 figures, post-print, IEEE Transactions on Cybernetics, Oct. 2015
- Published
- 2015