Printer Friendly

POSITIVE MODIFIED QUADRATIC SHEPARD LEAST-SQUARE-FIT CURVES.

Byline: M.R.Asim and M.Nadeem

ABSTRACT

In this paper, we constrain the Modified Quadratic Shepard interpolant to preserve positivity in one-dimensional interpolation such that the constrained interpolant also retains the least-squares fit to data. We preserved positivity by obtaining control over the extremum point of the basis functions of the Modified Quadratic Shepard interpolant. The constraining process destroyed the least-squares fitting character of the Modified Quadratic Shepard method. We insert an extra knot to convert each basis function into a spline and use the resultant freedom to make the provision for least-squares fit. Since each basis function is a positive spline which interpolates its respective data point being the least-square fit to other, the consequent Modified Quadratic Shepard interpolant is positive as well as a least-squares fit.

Key words: Constrained curve, positivity, least-square fit, interpolant, Shepard curve

INTRODUCTION

Generally in computer graphics and particularly in CAD (Computer Aided Design) and / or CAGD (Computer Aided Geometric Design) environments a user is usually in need of a visualizing scientific data, through a curve representation, that possesses certain shape characteristics inherent in data. As such the preservation of shapes, inherent in the data, by the interpolants has always been an important matter and positivity is one such shape. The significance of Positivity lies in the fact that sometimes it does not make any sense to talk of some of the quantities to be negative, for example a negative amount of a particular bacteria in a specimen tissue from a human body or the probability of a rainfall or a snowfall in a given area has no meaning if negative.

In this paper we focus on one-dimensional interpolation, constructing a curve through a set of positive data. The work contained in this paper also includes work in Asim (2000). The earlier work related to shape preservation can be found in Hussain et al. (2007) and the papers mentioned therein. Hussain and Sarfraz (2008) starts with a positive rational cubic curve through 1D positive data and it also extends it to an economical positive rational bicubic for a 2D data arranged over a rectangular grid. A C1 curve interpolation scheme is discussed in Hussain et al. (2008). Their scheme is also flexible due to the provision of a free parameter.

However, piecewise cubic approach does not extend so easily to higher dimensions when the data is scattered and is G1 continuous only. Consequently the authors developed a method (Asim, 2000) which is C1 and cheaper than the original modified Shepard interpolant but loses least -square fit to data.

This idea has already been extended to 2D and surface through scattered data is constructed (Asim and Nadeem, 2008).However this paper too has a drawback of loss of least- squares fit. The loss of least-squares fit property affects the visual appearance some what adversely (Figure 1). Also the least-squares fit property is the key characteristic of the modified quadratic Shepard interpolant. So the development of constrained modified Shepard interpolant which retains both C1 continuity and least-square fit properties, and is also extendible to higher dimensions easily is justified. The slope preserving 1D positive method Asim and Sajid, 2007 is another version of the series of quadratic Shepard interpolants starting with (Asim, 2000).

The Shepard family of interpolants is a famous approach (Shepard, 1968). The Shepard interpolants are a distance-weighted average of basis functions defined for each data point. Each basis function interpolated its respective data point and is the best weighted least-square fit to others. The modified quadratic Shepard interpolant, with basis functions that are quadratic, is the most popular version in this family (Nielson, 1993). The Shepard methods have C 1 continuity (Lancaster and Salkauskas, 1990) and are applicable to a space of any dimension for data of any distribution. However, to their disadvantage they do not preserve any of the local shapes implied by the data (Nielson, 1993). Recent work on Shepard methods have focused on reducing the computational cost by limiting the least-squares fitting process to a local subset of the data. Shepard method is widely used for 2D and 3D data, but is equally applicable to a curve interpolation technique.

In this paper we show how it can be constrained so as to generate positive 1D interpolants from positive data without losing its least-square fit property.

In section 2 we develop a constrained interpolant that retains the least-squares fit characteristic. Each quadratic basis function is replaced by a spline which is not only a least-squares fit to positive data but also positive over the interpolation interval. This provides us with the Shepard interpolant which itself is not only a least-squares fit to positive data but also positive. The boundedness of the interpolant developed by us in this paper is discussed in section 3. Section 4 elaborates conclusion and future research.

Constrained Least-Squares Fit for Curve Drawing:

Let (x1, f1), (x2, f2), (xN, fN) be given data points, where the f-values are samples of some functions f(x) which is non-negative for every x Ie [x1, xN] and x1 < x2 < . . . < xN .

The modified quadratic Shepard curve F(x) is defined as

(Equaton)

is related to data point (xi, fi). By definition Qi(xi) = fi and the coefficients ai an bi are Chosen so that Qi is a best distance-weighted least-squares approximation to the other data points. In (Asim, 2000), the quadratic basis functions Qi, were fully defined by three conditions, namely

* Interpolation at x = xi,

* value fixed at x = xs equal to zero for convex and yc for concave.

* derivative at x = xs, equal to zero.

So the least-squares approximation was lost. In order to retain the condition of best least-squares approximation to other data points, we need to relax the stipulation that the basis function be a quadratic.

Somewhat similar to the idea of (Schumaker, 1983) we use instead a quadratic spline, with a single knot, to give us the extra flexibility in a convex case. For a concave case too, we construct a quadratic spline using freedom in the choice of the y-coordinate of the maximum point to give the flexibility. The two cases are discussed separately.(Equation)

Convex Case: Suppose first that xi less than xs, so the interpolation point lies to the left of the minimum of the original basis function. We shall define a quadratic spline, Qi (x), with quadratic pieces S1 and S2 joined at a not (x knot, f knot) where x knot is the mid-point of [xi, xs]. The value f knot of the spline at x knot gives the extra degree of freedom required.

However, to ensure positivity, it is necessary to include a constraint that the spline is convex. More precisely, the constrained basis function is a quadratic spline, Where (omitting subscript i for simplicity of notation) S1(x) = f knot + b knot (x - x knot) + a knot (x - x knot )2 (3) and S2 (x) = as (x - xs)2 (4) The definition of S2 ensures that the spline has zero value and derivative at x = xs.

For interpolation at x = xi we require: S1(xi) = fi (5) while for C1 continuity of the spline we require S1(x knot) = S2(x knot), (6) S'1(x knot) = S'2(x knot). (7) Finally to ensure convexity, and hence positivity, we require as greater than 0 and knot greater than 0. The equation (6) and (7) respectively give us fknot = as(x knot - xs)2 and b knot = 2as(x knot - xs). Hence from (3), S1(x) = as(x knot - xs)2 + 2as(x knot - xs) (x - x knot) + a knot (x - x knot)2. (8) Then, from the interpolation condition (5), we have: fi = as(x knot - xs)2 + 2as(x knot - xs) (xi - x knot) 2 2 2 2 + a knot (xi - x knot) Th fi = ash +2ash + aknoth Th fi = (3as + a knot)h 2

other data points, with the restriction that Qi(x) be convex. Thus we need to minimize:

with a k, b k given by (15), (16), (17) and (18). If as less than 0, then we set as = 0 in which case if xi greater than xs, that is when minimum is on the left side of the data point, we proceed in the same way as we did in case xi less than xs except that: quadratics S1 and S2 swap their domains of definition. x knot Ie [xs, xi].

The graph (corresponding to the data in Table 1) thus obtained is in Figure 2 whose visual appearance is much better than the one in Figure 1. The noisy behavior of the data has been tackled successfully but at a cost higher than that of the original modified quadratic Shepard method. The discussion so far has dealt with the convex case. Now let us consider the concave case.

Concave Case: In the case where Qi(x) is concave (Asim, 2000), the

focus changes from raising the minimum value to zero, to raising the value at one or both end-points to zero. The addition of a least-squares fitting condition again requires extra flexibility, which we get by using a quadratic spline with one knot. In fact this case is slightly simpler because we can place the knot at xs (we could not do this in convex case because the value at xs was fixed, and therefore placing a knot there did not provide the extra flexibility required).

Table 2: Data that provides concave basis function.

x 1 2 4 6 7

y 0 0.06 3.5 0.06 0

Suppose xi less than xs, and suppose the original basis function is negative at xN. We create a constrained basis function which is a quadratic spline, with S1 interpolating (xi, fi) and S2 interpolating (xN, 0). This gives us:

(Equation)

subject to Qi(x1) [greater than or equal to] 0. That is we need to minimize

(Equation)

Then as in (21), the minimum is achieved when:

(Equation)

This value of ys when put in to (23) and (24) gives a quadratic spline which interpolates (x N, 0) and (xi, fi), and is a best least- squares fit to the other data points. To guarantee that S1 and S2 are both concave we restrict ys greater than fi. In addition we need Qi(xi) greater than 0 which requires: S1(x1) greater than 0.

(Equation)

words finally we need to restrict

Finally, consider the case (xi, fi) = (xs, ys), that is both the data point and the maximum coincide with each other. Since ys in this case cannot be changed, the only freedom available is that of a change in curvature. We avail this freedom to fit a spline

It may be mentioned here that if x1 and xN are equidistant from xs, then only one quadratic covers both sides. For xs in a close neighbourhood of xi, we take x s = xi and proceed as above. The graph thus obtained is shown in Figure 3. We may observe that the visual appearance of the curve due to the original constrained Shepard interpolant has been maintained by the one drawn by the constrained least-square fit Shepard interpolant in Figure 3. We may mention that we carried out a lot of experimentation and figures given here are only a specimen of the results obtained.

Extension of Constrained Least-square Fit to a Linear constraint: The idea of positive least-square fit based interpolation is extendible to the more general constraint so as to keep the interpolant greater than some linear function of the independent variable. For this we need to reframe the above problem as follows.

Consider data points (x1, f1), (x2, f2), (xN, fN), and the linear function given by y = mx + c with xN and fi [greater than or equal to] mx i + c " i. x1 less than x2 less than . . .

to seek a basis quadratic Qi(x) such that Q i(xi) = fi and Qi(x) [greater than or equal to] mx +c " x Ie [x1, xN].We construct a basis quadratic Li(x) such thatLi(x) = Qi(x) - mx - c Or Li(x) = ai(x - xi) 2 + (bi - m) (x - xi) - mxi - c + f i or Li(x) = ai(x - xi) 2 + (bi - m) (x - xi) + gi For = f i - mx i - c, with Li(x i) = fi - mxi - c and Li(x) [greater than or equal to] 0 " x Ie [x1, xN].

It transforms the problem to that of preservation of positivity while retaining the least-squares fit. As such the technique laid down for the constrained Modified Quadratic Shepard method to be a least-square fit in section 4 is now applicable to Li. This discussion has just covered the curve bounded below, and the similar argument works for the one bounded above.

The authors are confident that the same applies to the boundedness by a higher degree curve such as quadratic as well.

Conclusion: This paper shows how the modified quadratic Shepards method can be extended in order to provide a constrained least-square fit to a 1D data. As mentioned in section 3 constraint can be any linear or non-linear function. But we have restricted the practical implementation to the extensively used special case of positive interpolant through positive data. The flexibility required for the least-squares fit is provided by inserting a knot. The essential idea is to ensure that each individual quadratic basis function is obtained by the constrained least-squares fit to the data. This in turn gives rise to a constrained interpolant which is the least-square fit to the data as whole. The further work in the area is to obtain the least-squares fit based constrained modified quadratic Shepards interpolant in higher dimensions. Also there is an interest in looking at the similar work in the areas of monotonicity and convexity.

REFERENCES

Asim, M. R. Visualization of Data Subject to Positivity Constraint. PhD. Thesis, School of Computer Studies, University of Leeds, Leeds. England, 29-32 (2000).

Asim, M.R. and L.R. Sajid. Slope Preserving Positive Modified Quadratic Shepherd Curves, Journal of Scientific Research, University of the Punjab, Lahore, XXXVII(2):25-32 (2007).

Asim, M.R. and M.Nadeem. Positive Modified Quadratics Shepard Surface, Pakistan Journal of Science, 60(3-4): 34-39 (2008).

Hussain, M.Z. and M. Sarfraz. Positivity-preserving interpolation of positive data by rational cubics, Journal of Computational and Appl. Maths 218: 446-458 (2008).

Hussain, M.Z., M. Hussain and Shamaila. Visualization of Shaped Data by Ratioanl Quartic Spline, Int. Journal. Appl. Maths. Stat, 13; J08; 34-46 (2008).

Hussain, M.Z., N. Ayuab and M. Irshad. Visualisation of 2D data by rational quadratic functions. Journal of Information and Computing Science, 2(1), 17-26 (2007).

Lancaster, P. and K. Salkauskas. Curve And Surface Fitting An Introduction , Academic Press, Academic Press LTD 24-28 London NW1 7DX, third edition (1990).

Nielson, G. M. Scatted data modeling, IEEE Computer Graphics and Applications, 13(1): 60-70 (1993).

Schumaker, L. L. On shape preserving quadratic spline interpolation, SIAM J. Numer. Anal., 20(4):854-864 (1983).

Shepard, D. A two-dimensional function for irregularly spaced data, Proc. ACM Nat. Conf., 517-524 (1968).

Department of Computer Science, COMSATS Institute of Information Technology Lahore, Pakistan.
COPYRIGHT 2010 Asianet-Pakistan
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2010 Gale, Cengage Learning. All rights reserved.

Article Details
Printer friendly Cite/link Email Feedback
Publication:Pakistan Journal of Science
Article Type:Report
Geographic Code:9PAKI
Date:Dec 31, 2010
Words:2512
Previous Article:EVALUATION OF SOME PROMISING SUGARCANE GENOTYPES FOR CANE YIELD, QUALITY AND BORER COMPLEX INFESTATION.
Next Article:TRUST DEVIATION MONITORING AND PERFORMANCE EVALUATION OF AN ACADEMIC VERSION OF "ACENET" MULTIAGENT SYSTEM.
Topics:

Terms of use | Privacy policy | Copyright © 2021 Farlex, Inc. | Feedback | For webmasters |