Methods Of Blending Rational Interpolation And Their Applications In Graphics And Images

The problem of constructing a continuously defined function from given discrete data is unavoidable whenever one wishes to manipulate the data in a way that requires information not included explicitly in the data. In this age of ever-increasing digitization in the storage, processing, analysis, and communication of information, it is not difficult to find examples of applications where this problem occurs. The relatively easiest and in many applications often most desired approach to solve the problem is interpolation, where an approximating function is constructed in such a way as to agree perfectly with the usually unknown original function at the given measurement points. Polynomial interpolants are used as the basic means of approximation in nearly all areas of numerical analysis. They are used in the solution of equations and in the approximation of functions, of integrals and derivatives, of solutions of integral and differential equations, etc. Polynomial interpolants owe this popularity to their simple structure, which makes it easy to construct effective approximations and then make use of them. Examples of meromorphic functions for which the polynomial interpolant does not converge uniformly were given by Meray and later Runge — especially the latter has become well known and can be found in most modern books on the topic. These findings revealed the "inflexibility" of algebraic polynomials and their limited applicability to interpolation. On the other hand, a most powerful interpolation is the one using rational functions. The main advantage of rational functions over polynomials is their ability to model functions with nonlinear characters (such as poles or other singularity), their fast convergence makes one achieve full accuracy for approximation. There is an instable problem of computation for Thiele-type continued fractions interpolants, which means there are inverse differences being infinite or there are some unattainable points.For these reasons, this dissertation focuses on the study of various blending rational interpolation.The main contributions are as follows:First of all, a successive algorithm for Newton-Thiele's rational interpolation over rectangular grids is presented. The proposed successive interpolation algorithm can carry on the existing intermediate computations if new points are added to the grid. Numerical examples are given to show the effectiveness of our recursive algorithms.Secondly, to deal with the problem of instability of computation for Thiele-type continued fractions interpolants, which means there are inverse differences being infinite or there are some unattainable points when we compute the rational interpolants based on Thiele's continued fractions, modified Thiele-type blending continued fraction interpolation via Newton's interpolating polynomial is presented. Modified Newton-Thiele's rational interpolation is discussed. The proposed modified method for interpolation using rational functions can be valid all the same if some inverse differences don't exist or some unattainable points occur. Numerical examples are given to show the effectiveness of our algorithms.Thirdly, in this dissertation, we extend the point based interpolation to the block based interpolation. Inspired by the idea of the modern architectural design, we first divide the original set of support points into some subsets (blocks), then construct each block by using whatever interpolation means, linear or rational and finally assemble these blocks by Newton's method, Lagrange's method, or Thiele's method to shape the whole interpolation scheme. The algorithms for these interpolants are presented and the error estimations are given. Our method offers many flexible interpolation schemes for choices which include the classical Newton's polynomial interpolation or Thiele-type continued fraction interpolation as its special case. Each bivariate analogy is also discussed and numerical examples are given to show the effectiveness of our method.Fourthly, in this dissertation, we adopt the idea of the Lagrange's interpolation to construct a kind of blending rational interpolants via Pade approximation. For a given formal power series at every interpolation node, we build a Pade approximant and then blend them by means of the Lagrange interpolating basis functions to form a new blending rational interpolation—generalized Lagrange blending rational interpolation. There are many choices to make to determine the initial Pade approximant at every interpolation node, our method offers many flexible interpolation schemes for choices which include the classical Lagrange's polynomial interpolation as its special case. Pade-type approximation based blending rational interpolation and perturbed Pade approximation based blending rational interpolation are also studied for accurate interpolation. Numerical examples are given to show the effectiveness of our method.Fifthly, in order to obtain an interpolated image with a superior quality, this dissertation presents an efficient image interpolation technique using many-knot spline basis function with compact support ( see [79]). The one-dimensional many-knot splines interpolation algorithm is extended to the case in of two dimensions, which is applied to image processing. Then the accuracy of approximation, regularity of many-knot splines interpolation method and frequency property of the interpolation kernel are worked out for comparison. It can be shown that the approach is superior to other methods, such as cubic convolution. The experiment results are presented to show that the algorithm produces a reconstructed image with a superior quality. Moreover, this dissertation presents a new C2 cubic many-knot spline interpolation kernel function with compact support (- 2,2). The interpolation formula is constructed via degrees of freedom from inserting knots. The approximation order of the interpolation with the appropriate boundary conditions and constraints is analyzed. The one-dimensional many-knot splines interpolation algorithm is extended to that of two dimensions, which is also applied to image processing. An adaptive interpolation method is presented based on applying an inverse gradient to the above interpolation formula. The experiment results are presented to show that the adaptive interpolation algorithm produces a reconstructed image with a superior quality in terms of error and PSNR.Finally, interactive CAGD systems produce faster and more accurate curve and surface analysis and design by means of geometric or algebraic interpolation algorithms. In thisdissertation, a new kind of rational interpolation curves and surfaces are presented based on the above new C2 cubic many-knot spline basis function. The properties of the cubic rational many-knot spline interpolation curves and surfaces are discussed. What follows are the main results achieved in this dissertation.1. Inspired by the idea of the modern architectural design, we first divide the original set of support points into some subsets (blocks), then construct each block by using whatever interpolation means, linear or rational and finally assemble these blocks by Newton's method, Lagrange's method, or Thiele's method to shape the whole interpolation scheme. The algorithms for these interpolants are presented and the error estimations are given.2. We adopt the idea of the Lagrange's interpolation to construct a kind of blending rational interpolants via Pade approximation. For a given formal power series at every interpolation node, we build a Pade approximant and then blend them by means of the Lagrange interpolating basis functions to form a new blending rational interpolation—generalized Lagrange blending rational interpolation. There are many choices to make to determine the initial Pade approximant at every interpolation node, our method offers many flexible interpolation schemes for choices which include the classical Lagrange's polynomial interpolation as its special case. Pade-type approximation based blending rational interpolation and perturbed Pade approximation based blending rational interpolation are also studied for accurate interpolation.3. We present a new C2 cubic many-knot spline interpolation kernel function with compact support (- 2, 2). The interpolation formula is constructed via degrees of freedom from inserting knots. The approximation order of the interpolation with the appropriate boundary conditions and constraints is analyzed. The one-dimensional many-knot splines interpolation algorithm is extended to that of two dimensions, which is applied to image processing. An adaptive interpolation method is presented based on applying an inverse gradient to the above interpolation formula. Moreover, a new kind of rational interpolation curves and surfaces are presented based on the cubic many-knot spline function. The properties of the cubic rational many-knot spline interpolation curves and surfaces are discussed.