Universiẗat, Diss., 2000--Dortmund. / Dateiformat: PDF.

Thesis (Ph. D.)--University of Delaware, 2005. / Principal faculty advisor: Tobin A. Driscoll, Dept. of Mathematical Sciences. Includes bibliographical references.

Thesis (Ph. D. in Mathematics)--Vanderbilt University, Aug. 2006. / Title from title screen. Includes bibliographical references.

Universiẗat, Diss., 2000--Göttingen.

Universiẗat, Diss., 2004--Bremen.

This thesis discusses several topics related to interpolation and how it is used in numerical analysis. It begins with an overview of the aspects of interpolation theory that are relevant to the discussion at hand before presenting three new contributions to the field. The first new result is a detailed error analysis of the barycentric formula for trigonometric interpolation in equally-spaced points. We show that, unlike the barycentric formula for polynomial interpolation in Chebyshev points (and contrary to the main view in the literature), this formula is not always stable. We demonstrate how to correct this instability via a rewriting of the formula and establish the forward stability of the resulting algorithm. Second, we consider the problem of trigonometric interpolation in grids that are perturbations of equally-spaced grids in which each point is allowed to move by at most a fixed fraction of the grid spacing. We prove that the Lebesgue constant for these grids grows at a rate that is at most algebraic in the number of points, thus answering questions put forth by Trefethen and Weideman about the robustness of numerical methods based on trigonometric interpolation in points that are uniformly distributed but not equally-spaced. We use this bound to derive theorems about the convergence rate of trigonometric interpolation in these grids and also discuss the related question of quadrature. Specifically, we prove that if a function has V ≥ 1 derivatives, the Vth of which is Hölder continuous (with a Hölder exponent that depends on the size of the maximum allowable perturbation), then the interpolants converge uniformly to the function at an algebraic rate; larger values of V lead to more rapid convergence. A similar statement holds for the corresponding quadrature rule. We also consider what analogue, if any, there is for trigonometric interpolation of the famous 1/4 theorem of Kadec from sampling theory that restricts the size of the perturbations one can make to the integers and still be guaranteed to have a set of stable sampling for the Paley-Wiener space. We present numerical evidence suggesting that in the discrete case, the 1/4 threshold takes the form of a threshold for the boundedness of a "2-norm Lebesgue constant" and does not appear to have much significance in practice. We believe that these are the first results regarding this problem to appear in the literature. While we do not believe the results we establish are the best possible quantitatively, they do (rigorously) capture the main features of trigonometric interpolation in perturbations of equally-spaced grids. We make several conjectures as to what the optimal results may be, backed by extensive numerical results. Finally, we consider a new application of interpolation to numerical linear algebra. We show that recently developed methods for computing the eigenvalues of a matrix by dis- cretizing contour integrals of its resolvent are equivalent to computing a rational interpolant to the resolvent and finding its poles. Using this observation as the foundation, we develop a method for computing the eigenvalues of real symmetric matrices that enjoys the same advantages as contour integral methods with respect to parallelism but employs only real arithmetic, thereby cutting the computational cost and storage requirements in half.

abstract: Video deinterlacing is a key technique in digital video processing, particularly with the widespread usage of LCD and plasma TVs. This thesis proposes a novel spatio-temporal, non-linear video deinterlacing technique that adaptively chooses between the results from one dimensional control grid interpolation (1DCGI), vertical temporal filter (VTF) and temporal line averaging (LA). The proposed method performs better than several popular benchmarking methods in terms of both visual quality and peak signal to noise ratio (PSNR). The algorithm performs better than existing approaches like edge-based line averaging (ELA) and spatio-temporal edge-based median filtering (STELA) on fine moving edges and semi-static regions of videos, which are recognized as particularly challenging deinterlacing cases. The proposed approach also performs better than the state-of-the-art content adaptive vertical temporal filtering (CAVTF) approach. Along with the main approach several spin-off approaches are also proposed each with its own characteristics. / Dissertation/Thesis / M.S. Electrical Engineering 2012

Este trabalho apresenta um estudo sobre métodos utilizados para realizar metamorfose entre imagens digitais. Segundo esses métodos é possível estabelecer uma imagem fonte, uma destino e, através de operações de mapeamento de texturas, realizar uma seqüência de imagens intermediárias. Essas imagens intermediárias apresentam-se como deformações sobre a imagem fonte ou como etapas de transição entre as imagens originais, efeito produzido pela inserção de um processo de fusão de imagens. O processo de deformação varia segundo o método empregado e influencia diretamente nos resultados por ele gerado. Assim, dois métodos com características diferentes para deformação de imagens foram escolhidos, dentre os encontrados, para um estudo mais aprofundado e são referenciados como o Método das Malhas e o Método dos Campos de Influência. Esses métodos são apresentados, seus funcionamentos discutidos e resultados gerados para se estabelecer uma análise entre os mesmos. A análise é efetuada segundo os aspectos de tempo de processamento, consumo de minoria e atribuição de correspondências entre as imagens, sendo que esta última característica leva em consideração o tempo total gasto para se estabelecer as correspondências necessárias entre a imagem fonte e a destino. Neste ponto também é estabelecido um quadro comparativo entre os métodos escolhidos, destacando-se vantagens e desvantagens. Os resultados da aplicação dos métodos analisados encontram-se distribuídos ao longo do texto sob a forma de imagens e tabelas, são utilizados para provar a eficiência desses métodos e foram gerados por um sistema de testes implementado. O sistema de testes desenvolvido possibilita a geração de imagens, segundo o método escolhido, informa os tempos utilizados no processamento e exibe essas imagens seqüencialmente sob a forma de uma animação. Por fim o trabalho apresenta conclusões sobre o estudo, salientando aspectos considerados relevantes quando do estudo e implementação dos métodos, e indica futuras extensões que podem ser efetuadas a fim de tornar o sistema de testes mais flexível e completo. / This work presents a study on methods used to make digital images metamorphosis. According to these methods it is possible to establish a source image, a destination image and also to generate a sequence of intermediate images through operations of texture mapping. These intermediate images appears as deformations of the source image or as transition steps between the original images which are produced by the insertion of a cross-dissolve process. The warping process varies according to the method which is used and it influences directly its results. Thus, two methods for image warping with different characteristics were chosen, among the available ones, for a more detailed study and are refered as the Mesh Method and as the Fields of Influence Method. These two methods are presented, their functioning is discussed and results are generated to allow comparative analyses. The analysis concerns aspects of processing time, memory allocation and correspondence establishment, which take into account the time waisted in order to establish the correspondences between the images. At this point it is also established a comparative table between the chosen methods highlighting advantages and disadvantages. The results of the application of the analysed methods are distributed throughout the text as images and tables, which are used to prove the efficiency of them and were generated by a test system implemented. The system developed provides the generation of images, according to the choosen method, informs the time waisted on processing and shows those images sequentially as an animation. Finally this work presents conclusions about the study and indicates future extensions that can be done in order to make the developed system more flexible and complete.

Este trabalho apresenta um estudo sobre métodos utilizados para realizar metamorfose entre imagens digitais. Segundo esses métodos é possível estabelecer uma imagem fonte, uma destino e, através de operações de mapeamento de texturas, realizar uma seqüência de imagens intermediárias. Essas imagens intermediárias apresentam-se como deformações sobre a imagem fonte ou como etapas de transição entre as imagens originais, efeito produzido pela inserção de um processo de fusão de imagens. O processo de deformação varia segundo o método empregado e influencia diretamente nos resultados por ele gerado. Assim, dois métodos com características diferentes para deformação de imagens foram escolhidos, dentre os encontrados, para um estudo mais aprofundado e são referenciados como o Método das Malhas e o Método dos Campos de Influência. Esses métodos são apresentados, seus funcionamentos discutidos e resultados gerados para se estabelecer uma análise entre os mesmos. A análise é efetuada segundo os aspectos de tempo de processamento, consumo de minoria e atribuição de correspondências entre as imagens, sendo que esta última característica leva em consideração o tempo total gasto para se estabelecer as correspondências necessárias entre a imagem fonte e a destino. Neste ponto também é estabelecido um quadro comparativo entre os métodos escolhidos, destacando-se vantagens e desvantagens. Os resultados da aplicação dos métodos analisados encontram-se distribuídos ao longo do texto sob a forma de imagens e tabelas, são utilizados para provar a eficiência desses métodos e foram gerados por um sistema de testes implementado. O sistema de testes desenvolvido possibilita a geração de imagens, segundo o método escolhido, informa os tempos utilizados no processamento e exibe essas imagens seqüencialmente sob a forma de uma animação. Por fim o trabalho apresenta conclusões sobre o estudo, salientando aspectos considerados relevantes quando do estudo e implementação dos métodos, e indica futuras extensões que podem ser efetuadas a fim de tornar o sistema de testes mais flexível e completo. / This work presents a study on methods used to make digital images metamorphosis. According to these methods it is possible to establish a source image, a destination image and also to generate a sequence of intermediate images through operations of texture mapping. These intermediate images appears as deformations of the source image or as transition steps between the original images which are produced by the insertion of a cross-dissolve process. The warping process varies according to the method which is used and it influences directly its results. Thus, two methods for image warping with different characteristics were chosen, among the available ones, for a more detailed study and are refered as the Mesh Method and as the Fields of Influence Method. These two methods are presented, their functioning is discussed and results are generated to allow comparative analyses. The analysis concerns aspects of processing time, memory allocation and correspondence establishment, which take into account the time waisted in order to establish the correspondences between the images. At this point it is also established a comparative table between the chosen methods highlighting advantages and disadvantages. The results of the application of the analysed methods are distributed throughout the text as images and tables, which are used to prove the efficiency of them and were generated by a test system implemented. The system developed provides the generation of images, according to the choosen method, informs the time waisted on processing and shows those images sequentially as an animation. Finally this work presents conclusions about the study and indicates future extensions that can be done in order to make the developed system more flexible and complete.

Orientador: Lucio Tunes dos Santos / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Computação Cientifica / Made available in DSpace on 2018-08-06T01:09:38Z (GMT). No. of bitstreams: 1 Camargo_AnaCarolina_M.pdf: 3666219 bytes, checksum: 1c8c0d68b9fefa425dbd20b478818406 (MD5) Previous issue date: 2006 / Resumo: É comum ser preciso reconstruir funções cujas amostras não estão numa grade igualmente espaçada. Isto é devido ao fato que alguns dos algoritmos mais usados requerem amostras em uma grade Cartesiana regular (uniforme). Portanto, é necessário fazer uma reamostragem uniforme, i.e., interpolar as amostras não uniformes em um conjunto de pontos igualmente espaçados. Neste trabalho, primeiro mostramos que o problema de reamostragem pode ser formulado como um problema de resolver um sistema de equações lineares. Uma solução para este sistema pode ser encontrada utilizando a matriz pseudoinversa, um processo que é impraticável para um número grande de variáveis. A partir de características do problema, é possível desenvolver um algoritmo melhor, o qual usa apenas um número limitado de amostras para calcular cada amostra uniforme, transformando o problema original numa seqüência de sistemas lineares com menos variáveis. O resultado final pode ser visto como ótimo e computacionalmente eficiente. Aplicações são apresentadas para demonstrar a eficiência deste método / Abstract: Its common to be needed to reconstruct functions which samples falls on a nonequally spaced grid. This is due to the fact that some of the most used algorithms require samples in a regular (uniform) Cartesian grid. Therefore, it is necessary to make an uniform resampling, i.e., to interpolate the nonuniform samples in a set of equally spaced points. In this work, it is first shown that the resampling problem can be formulated as a problem of solving a system of linear equations. A solution for this system can be found using the pseudoinverse matrix, a process that is impractical for a large number of variables. From particular characteristics of the problem, it is possible to develop a better algorithm, which only uses a limited number of samples to calculate each uniform sample, transforming the original problem into a sequence of linear systems with less variables. The final result can be viewed as both optimal and computationally efficient. Applications are presented to demonstrate the efficiency of the method / Mestrado / Mestre em Matemática Aplicada