Esta tese tem duas partes relativamente independentes. A primeira estuda o problema de construir uma curva suave (C1) que separa dois conjuntos de pontos do plano. Especificamente, a curva é definida por uma equação implícita F(x, y) = 0 onde F é uma spline polinomial de grau 2 com continuidade adequada. O objetivo é determinar uma única cônica se possível, senão uma curva que minimiza uma função quadrática de "energia". O problema é reduzido a um problema de minimização quadrática com restrições, que é resolvido por uma biblioteca existente (CGAL). A segunda parte descreve um algoritmo geral para determinar uma base de elementos finitos em um espaço de splines arbitrário, definido por exemplo por restrições lineares homogêneas de continuidade ou contorno. Neste caso o problema é caracterizado como o problema de encontrar uma base de peso máximo em um matróide e, portanto, pode ser resolvido pelo algoritmo guloso de Edmonds. Esse algoritmo tem custo exponencial no número n de células da malha. Entretanto, esta tese mostra que para casos de interesse - onde existe uma base de elementos finitos com suporte de k células, no máximo - o algoritmo pode ser melhorado de modo a terminar em tempo O(n km3), onde m é a dimensão do espaço (que é geralmente O(n)); This thesis has two relatively independent parts. The first part considers the problem of constructing a smooth (C1) curve separating two sets of points of the plane. Specifically...

Este trabalho apresenta um modelo fluido-dinamico para a simulação da dispersão continua de efluentes miscíveis em rios de geometria irregular. Devido a geometria irregular do rio, as equações de conservação de massa e de momentum são descritas em um sistema de coordenadas generalizadas. Utilizando pontos conhecidos de cada margem de rio, foi usado o Método Spline Cúbico para encontrar as funções mais suaves possíveis que passem por esses pontos. Estas funções tornaram possível a obtenção das linhas de corrente e, então, usando o principio da ortogonalidade, as linhas potenciais foram estimadas. Desta forma, a malha e formada pela intersecção entre as linhas potenciais e as linhas de corrente. Apesar da irregularidade da geometria, as variáveis não costumam apresentar altos gradientes e, por isso, não e necessário utilizar um complexo modelo de turbulência. Portanto, um modelo de turbulência de ordem zero foi escolhido para considerar a turbulência. As equações de conservação de massa e de momentum foram discretizadas através do Método dos Volumes Finitos. Os resultados mostram que o modelo e satisfatório na obtenção dos perfis de velocidade e concentração do efluente de seções de rio de geometria irregular. Alem disso...

Nesta tese, desenvolvemos algoritmos eficientes para a aproximação de funções que tem importantes detalhes de pequena escala confinados em pequenas região do domínio. Assumimos que a função objetivo é amostrada em um número finito de pontos dados, com densidade uniforme ou densidade não uniforme. Neste trabalho optamos por utilizar uma base multinível (ou multiresolução), em que os centros dos elementos em cada nível são um subconjunto de uma grade regular de centros, independentemente dos pontos de amostragem. As bases em questão têm estrutura multiescala semelhante à usada na análise wavelet em d dimensões. No entanto, os seus elementos são funções explícitas definidas pelo produto de d funções univariadas de suporte limitado (tais como pseudo-gaussianas modelada por polinômios truncados ou spline). Descrevemos um algoritmo incremental de aproximação, que procede do nível mais grosseiro para o mais detalhado, sendo que em cada nível são usados apenas os elementos da base localizados nas regiões onde a aproximação é ainda insuficientemente precisa. Em cada nível, usamos um processo iterativo com o método de mínimos quadrados que é projetado para ignorar dados discrepantes e detalhes que só podem ser aproximados em escalas menores.; I this thesis we develop efficient algorithms for the approximation of functions that have important small-scale details confined to small portions of their domain. We assume that the target function is sampled at a finite number of data points...

In this work we have elaborated a spline-based method of solution of inicial value problems involving ordinary differential equations, with emphasis on linear equations. The method can be seen as an alternative for the traditional solvers such as Runge-Kutta, and avoids root calculations in the linear time invariant case. The method is then applied on a central problem of control theory, namely, the step response problem for linear EDOs with possibly varying coefficients, where root calculations do not apply. We have implemented an efficient algorithm which uses exclusively matrix-vector operations. The working interval (till the settling time) was determined through a calculation of the least stable mode using a modified power method. Several variants of the method have been compared by simulation. For general linear problems with fine grid, the proposed method compares favorably with the Euler method. In the time invariant case, where the alternative is root calculation, we have indications that the proposed method is competitive for equations of sifficiently high order.; Coordenação de Aperfeiçoamento de Pessoal de Nível Superior; Neste trabalho desenlvolvemos um método de resolução de problemas de valor inicial com equações diferenciais ordinárias baseado em splines...

Métodos de deformação são importantes em áreas como modelagem geométrica e animação computacional. Na biologia, a modelagem de forma, crescimento, movimento e patologias de organismos microscópicos vivos ou células requerem deformações suaves, as quais são essencialmente 2D com poucas mudanças de profundidade. Nesta dissertação, apresentamos um método de deformação do espaço 2.5D suave. O modelo 3D do organismo é modificado deformando uma grade de controle formada por prismas que o envolve. A técnica de interpolação spline é usada para satisfazer o requisito de suavidade ('C POT. 1'). Implementamos esse método em um editor que torna possível definir e modificar a deformação de uma forma amigável usando o mouse. Os resultados experimentais mostram que o método é simples e efetivo; Shape deformation methods are important in such fields as geometric modeling and computer animation. In biology, the modeling of shape, growth, movement and pathologies of living microscopic organisms or cells requires smooth deformations, which are essentially 2D with little change in depth. In this master thesis, we present a smooth 2.5D space deformation method. The 3D model of the organism is modified by deforming an enclosing control grid of prisms. Spline interpolation is used to satisfy the smoothness ('C POT. 1') requirement. We implemented this method in an editor which makes it possible to define and modify the deformation with the mouse in a user-friendly way. The experimental results show that the method is simple and effective

Inspired by shape constrained estimation under general nonnegative derivative constraints, this paper considers the B-spline approximation of constrained functions and studies the asymptotic performance of the constrained B-spline estimator. By invoking a deep result in B-spline theory (known as de Boor's conjecture) first proved by A. Shardin as well as other new analytic techniques, we establish a critical uniform Lipschitz property of the B-spline estimator subject to arbitrary nonnegative derivative constraints under the $\ell_\infty$-norm with possibly non-equally spaced design points and knots. This property leads to important asymptotic analysis results of the B-spline estimator, e.g., the uniform convergence and consistency on the entire interval under consideration. The results developed in this paper not only recover the well-studied monotone and convex approximation and estimation as special cases, but also treat general nonnegative derivative constraints in a unified framework and open the door for the constrained B-spline approximation and estimation subject to a broader class of shape constraints.

In this paper, we present the development of a many-knot spline method derived to remove the statistical noise in the spectroscopic data. This method is an expansion of the B-spline method. Compared to the B-spline method, the many-knot spline method is significantly faster.; Comment: 3pages, 2 figures

In this paper, we propose a new semiparametric regression estimator by using a hybrid technique of a parametric approach and a nonparametric penalized spline method. The overall shape of the true regression function is captured by the parametric part, while its residual is consistently estimated by the nonparametric part. Asymptotic theory for the proposed semiparametric estimator is developed, showing that its behavior is dependent on the asymptotics for the nonparametric penalized spline estimator as well as on the discrepancy between the true regression function and the parametric part. As a naturally associated application of asymptotics, some criteria for the selection of parametric models are addressed. Numerical experiments show that the proposed estimator performs better than the existing kernel-based semiparametric estimator and the fully nonparametric estimator, and that the proposed criteria work well for choosing a reasonable parametric model.; Comment: 20 pages, 3 figures

In this paper, an approximation of the optimal compressor function using the quadratic spline functions has been presented. The coefficients of the quadratic spline functions are determined by minimizing the mean-square error (MSE). Based on the obtained approximative quadratic spline functions, the design for companding quantizer for Gaussian source is done. The support region of proposed companding quantizer is divided on segments of unequal size, where the optimal value of segment threshold is numerically determined depending on maximal value of the signal to quantization noise ratio (SQNR). It is shown that by the companding quantizer proposed in this paper, the SQNR that is very close to SQNR of nonlinear optimal companding quantizer is achieved.

In this paper, we give a causal solution to the problem of spline interpolation using H-infinity optimal approximation. Generally speaking, spline interpolation requires filtering the whole sampled data, the past and the future, to reconstruct the inter-sample values. This leads to non-causality of the filter, and this becomes a critical issue for real-time applications. Our objective here is to derive a causal system which approximates spline interpolation by H-infinity optimization for the filter. The advantage of H-infinity optimization is that it can address uncertainty in the input signals to be interpolated in design, and hence the optimized system has robustness property against signal uncertainty. We give a closed-form solution to the H-infinity optimization in the case of the cubic splines. For higher-order splines, the optimal filter can be effectively solved by a numerical computation. We also show that the optimal FIR (Finite Impulse Response) filter can be designed by an LMI (Linear Matrix Inequality), which can also be effectively solved numerically. A design example is presented to illustrate the result.

A new nonparametric approach for system identification has been recently proposed where the impulse response is seen as the realization of a zero--mean Gaussian process whose covariance, the so--called stable spline kernel, guarantees that the impulse response is almost surely stable. Maximum entropy properties of the stable spline kernel have been pointed out in the literature. In this paper we provide an independent proof that relies on the theory of matrix extension problems in the graphical model literature and leads to a closed form expression for the inverse of the first order stable spline kernel as well as to a new factorization in the form $UWU^\top$ with $U$ upper triangular and $W$ diagonal. Interestingly, all first--order stable spline kernels share the same factor $U$ and $W$ admits a closed form representation in terms of the kernel hyperparameter, making the factorization computationally inexpensive. Maximum likelihood properties of the stable spline kernel are also highlighted. These results can be applied both to improve the stability and to reduce the computational complexity associated with the computation of stable spline estimators.; Comment: 12 pages. In 2014 IEEE Multi-conference on Systems and Control. IEEE...

This paper is concerned with asymptotic theory for penalized spline estimator in bivariate additive model. The focus of this paper is put upon the penalized spline estimator obtained by the backfitting algorithm. The convergence of the algorithm as well as the uniqueness of its solution are shown. The asymptotic bias and variance of penalized spline estimator are derived by an efficient use of the asymptotic results for the penalized spline estimator in marginal univariate model. Asymptotic normality of estimator is also developed, by which an approximate confidence interval can be obtained. Some numerical experiments confirming theoretical results are provided.; Comment: 24 pages, 6 figures

In this paper the approximation of the optimal compressor function using the first-degree spline functions and quadratic spline functions is done. Coefficients on which we form approximative spline functions are determined by solving equation systems that are formed from treshold conditions. For Gaussian source at the input of the quantizer, using the obtained approximate spline functions a companding quantizer designing is done. On the basis of the comparison with the SQNR of the optimal compandor it can be noticed that the proposed companding quantizer based on approximate spline functions achieved SQNR arbitrary close to that of the optimal compandor.

Spline wavelet tight frames of Ron-Shen have been used widely in frame based image analysis and restorations. However, except for the tight frame property and the approximation order of the truncated series, there are few other properties of this family of spline wavelet tight frames to be known. This paper is to present a few new properties of this family that will provide further understanding of it and, hopefully, give some indications why it is efficient in image analysis and restorations. In particular, we present a recurrence formula of computing generators of higher order spline wavelet tight frames from the lower order ones. We also represent each generator of spline wavelet tight frames as certain order of derivative of some univariate box spline. With this, we further show that each generator of sufficiently high order spline wavelet tight frames is close to a right order of derivative of a properly scaled Gaussian function. This leads to the result that the wavelet system generated by a finitely many consecutive derivatives of a properly scaled Gaussian function forms a frame whose frame bounds can be almost tight.; Comment: 28 pages

One important area of Computer-Aided Geometric Design (CAGD) is concerned with the approximation and representation of the surfaces of solid objects. Accurately describing the shape of an object so that the description is useful to designers who must decide how to manipulate it is an important problem. B-spline techniques promise greater versatility in describing complex surfaces than other techniques, thus the B-spline surface is highlighted in the field of constructive solid geometric modeling. A method for drawing complex surfaces by using B-spline techniques is presented. The tensor product surface scheme is developed for constructing sculptured surfaces. Also, the basic principle of multivariate B-splines, i.e., nontensor product surfaces, the light of tomorrow in CAGD, is introduced.

A technique using least square cubic splines was developed to obtain an estimate of the MTF from edge response measurements. By making specific assumptions concerning the general nature of edges to be analyzed, an optimized procedure was developed to fit noise free cummulative gaussian edges. The procedure was evaluated using simulated data from various spread function shapes and levels of additive noise. The spline technique produced MTF estimates which had less bias and lower variance than the commonly used derivative - transform technique. Due to the various constraints which can be imposed on the spline, least square cubic splines actually comprise a class of edge analysis techniques which spans the range of characteristics from the derivative transform technique to the exact functional form fitting technique. Because of the nature of the spline calculation, the constrained, least square cubic spline can be thought of as a matched, yet adaptive nonlinear filter.

A brief review of curve fitting terminology is presented, and the cubic spline interpolation scheme is outlined. Parametric and non-parametric curve fitting techniques are compared. The technique to fit parametric cubic splines is derived using the Euler- Lagrange formulation. Previous work on splines in tension is identified. Employing the notion of splines in tension, a method is proposed to fit a parametric curve to a set of (n + 1) points in ^-dimension space satisfying a specified set of boundary conditions. The curve fitted will not have any inflection points within any span and will be invariant with respect to coordinate translation and rotation. Using Euler-Lagrange formulation, a system of linear equations in terms of the unknown second derivatives at knots is developed. Three kinds of boundary conditions are investigated. Software is developed in VAX Fortran to fit both parametric splines in tension and parametric cubic splines. Applications where splines in tension may find use are identified. Some examples of such applications are presented and comparison to cubic spline made. Splines in tension offer a better alternative than Fourier transform in describing boundary of shape in digital image processing application. Possible extensions to the numerical scheme developed and related investigations by other workers in this field are also listed.

B-Splines are a useful tool in signal processing, and are widely used in the analysis of two and three-dimensional images. B-Splines provide a continuous representation of the signal, image, or volume, which is useful for interpolation, resampling, noise removal, and differentiation - all important steps in many signal processing algorithms. These splines are defined entirely by an array of coefficients that is roughly the same size as the original signal and of values in the same order of magnitude, making storage and representation trivial. What is not trivial, however, is the quick calculation and processing of those coefficients, especially for very large data. As technology improves in fields such as medical imaging, algorithms that use B-Splines will need to process increasingly higher resolution images and voxel volumes. New implementations are needed to make use of modern parallel architectures to keep these algorithms practical. This thesis presents a library for performing many common B-Splines operations in CUDA, the parallel programming framework for NVIDIA GPUs, and analyzes the considerations necessary when implementing a large-scale parallel version of such a well-established sequential algorithm. This library is meant to be used both by C++ programs as well as algorithms implemented in MATLAB without requiring significant changes. Significant speedups are obtained using this library to perform various common B-Spline image processing operations (as much as 30x for some)...

The issue of vibration isolation challenges engineers' designs across the engineering spectrum. From an engineering standpoint, vibration control impacts the fields of transportation, manufacturing, construction and mechanical design. Dynamic systems produce vibrations for various reasons i.e. rotating unbalanced masses (high speed turbines); inertia of reciprocating components (internal combustion engines); irregular rolling contact (automobiles) or induced eddy current (locomotives) vibrations. In most cases, vibrations cause only physical discomfort and/or loss of accuracy. But in extreme cases, transmitted forces may cause a body to undergo high amplitude resonant vibrations, leading to high cyclic stresses and imminent fatigue failure resulting in a catastrophic occurrence and possible loss of life. Therefore, isolating the vibration's source from other system components becomes essential. Deploying a parallel underdamped spring-damper arrangement achieves this required isolation by suspending the component's mass. The frequency response function (FRF) of a second order under-damped suspension model suggests that for a given excitation frequency, suspensions with lower natural frequencies benefits vibration isolation. Lowering the natural frequency requires springs with low stiffness. Using soft springs is not always plausible as it significantly reduces the suspension's load carrying capacity. Therefore...

Engineers are researching solutions to resolve many of today's technical challenges. Numerical techniques are used to solve the mathematical models that arise in engineering problems. A numerical technique that is increasingly being used to solve mathematical models in engineering research is called the B-spline Collocation Method. The B-spline Collocation Method has a few distinct advantages over the Finite Element and Finite Difference Methods. The main advantage is that the B-spline Collocation Method efficiently provides a piecewise-continuous, closed form solution. Another advantage is that the B-spline Collocation Method procedure is very simple and easy to apply to many problems involving partial differential equations. The current research involves developing, and extensively documenting, a comprehensive, step-by-step procedure for applying the B-spline Collocation Method to the solution of Boundary Value problems. In addition, the current research involves applying the B-spline Collocation Method to solve the mathematical model that arises in the deflection of a geometrically nonlinear, cantilevered beam. The solution is then compared to a known solution found in the literature.