Ph.D Thesis

Ph.D StudentLevi Yoni
SubjectConstrained Function Approximation Using Energy
Minimization with Integral Constraints
DepartmentDepartment of Electrical and Computer Engineering
Supervisors PROF. Irad Yavneh
PROF. Lihi Zelnik-Manor


The use of energy methods and variational principles is widespread in many fields of engineering, curve design and surface design being two prominent examples. In particular, the minimization of Dirichlet's Energy is a widely used regularizer for approximating smooth functions.

In this work we develop three highly efficient (linear time complexity) algorithms for the interpolation and upscaling of data points. Adopting a variational approach, we address these problems through the minimization of different energy terms, which are similar or identical to the Dirichlet Energy, subject to integral constraints. First, we develop a robust iterative solver for curve interpolation subject to upper and lower bounds on the first order derivative. We call this approach interpolation by Speed-Limit Quasi-Splines (SLQS). Then, we construct a monotonicity-preserving interpolation procedure we call Monotonicity-Preserving Quasi-Splines (MPQS), suitable also for non-monotonic data. Finally, we suggest a simple iterative procedure for general $d$-dimensional signal upscaling, which we embed in an efficient multigrid procedure for the application of 1D, 2D and 3D image upscaling.

Additionally, based on our SLQS curve-interpolation method, we develop a new approach for the recovery of smooth object boundaries with sub-pixel accuracy, given the object area in each boundary pixel.