Averaging linear and cubic interpolated values = ?
in [Matlab]
|
From: hank scorpio on 17 Apr 2010 06:11 Hello all, I've been playing about with interpolating data (self generated, no implicit function) using the interp3 command (the data was so dimensioned)... I can see how linear works mathematically but don't have the knowledge to grasp cubic interpolation yet. Looking at the output data I can see each has its own tendencies and characteristic 'failures' (certainly once you chuck in worst case data sets and visualise the data somehow) ... I thought upon looking at the data, why not just use the mean value of a linear interp and a cube interp outputs ? Kind of a hedge your bets methodology... Perhaps this just a redundant operation which could be achieved within one cubic interpolation itself ? (some sort of internal fiddle or what not of the algorithm). Maybe I'm creating a contradictory system with even worse artefacts ?
From: John D'Errico on 17 Apr 2010 06:56 "hank scorpio" <breakbeak(a)hotmail.com> wrote in message <hqc1fq$gdo$1(a)fred.mathworks.com>... > Hello all, > > I've been playing about with interpolating data (self generated, no implicit function) using the interp3 command (the data was so dimensioned)... > > I can see how linear works mathematically but don't have the knowledge to grasp cubic interpolation yet. Looking at the output data I can see each has its own tendencies and characteristic 'failures' (certainly once you chuck in worst case data sets and visualise the data somehow) ... > > I thought upon looking at the data, why not just use the mean value of a linear interp and a cube interp outputs ? > > Kind of a hedge your bets methodology... > > Perhaps this just a redundant operation which could be achieved within one cubic interpolation itself ? (some sort of internal fiddle or what not of the algorithm). Maybe I'm creating a contradictory system with even worse artefacts ? You are creating DIFFERENT artifacts, with a new interpolant that has the faults of both methods, yet the good aspects of neither method. The 'linear' interpolant in three dimensions is sometimes called trilinear interpolation when used by those in some parts of the world. Personally, I think the phrase tensor product linear interpolation is a better descriptor. Regardless, this "linear" interpolant is not even truly linear in all aspects. I'll talk about this later on some more. The linear (versus cubic) interpolants for interp3 have different properties. The linear interpolant is not a differentiable function as you cross from one cube to the next, merely a continuous function across these breaks. One might call the linear interpolant a C0 function, because it is a continuous function, but zero times differentiable across these internal boundaries. Compare this to the cubic interpolant. When used with an equally spaced grid, I seem to recall it is a C1 interpolant. That is, it is both continuous, and differentiable once across the breaks, but not twice differentiable. This is done for efficiency, compared to the 'spline' method for interp3, which should generally be C2. Now, suppose that you take the mean of these two results? Sorry, but it will be again a C0 function in general. You lose that extra order of differentiability. Next, compare the behavior of the linear versus cubic interpolants in another aspect. Within the cube of eight points that contain any single point to interpolate, the linear method will yield a result that is ALWAYS contained within the limits of these eight values. You could call it a convex combination of those numbers. Thus the linear interpolant is never less than the smallest of those values, nor greater than the largest. This is not true about a cubic (or spline) interpolant on this same grid. Those methods can easily enough exhibit ringing behavior, so you will often get oscillations in some parts of the space. One way to think of these oscillations is that new extrema are generated where none existed in your data. It is a behavior not infrequently seen in many variants of cubic splines, even in one dimension. (Note that while pchip was created to eliminate this problem, that method is not employed inside interp3.) Taking the average of the two results will only dampen out the ringing, but NOT eliminate it. So when you take the average of the two methods you get an interpolant that is still C0, but it will still exhibit ringing. I talked before about the linear interpolant (trilinear) being not even truly linear in all aspects. If you look at this linear method along a path from one corner of a cube from the point [0 0 0] to [1 1 1], you will see that it actually can look like a cubic polynomial! (Within limits.) HTH, John
From: Rune Allnor on 17 Apr 2010 07:22 On 17 apr, 12:11, "hank scorpio" <breakb...(a)hotmail.com> wrote: > Hello all, > > I've been playing about with interpolating data (self generated, no implicit function) using the interp3 command (the data was so dimensioned)... > > I can see how linear works mathematically but don't have the knowledge to grasp cubic interpolation yet. Looking at the output data I can see each has its own tendencies and characteristic 'failures' (certainly once you chuck in worst case data sets and visualise the data somehow) ... Play with simpler data sets. Plot the 'raw' data points and the various interpolated functions, and see how they vary. > I thought upon looking at the data, why not just use the mean value of a linear interp and a cube interp outputs ? > > Kind of a hedge your bets methodology... > > Perhaps this just a redundant operation which could be achieved within one cubic interpolation itself ? (some sort of internal fiddle or what not of the algorithm). Maybe I'm creating a contradictory system with even worse artefacts ? You are using different interpolation methods on the same data. When choosing what interpolation method in any given situation, you need to make an informed choise between the plague and cholera: 1) Which method is computationally faster? 2) Which method produces the smoother curve? 3) Which method can include points as they become available? 4) Which method requires all the points to be available before computing the interpolant? 5) Which method balances amplitude of deviations against number of terms in the interpolant? and so on and so forth. Do note that a number of these factors are strongly interconnected: Splines produce very smooth interpolating curves, but require all the data to be available and are computationally expensive. Once you understand what tradeoffs are involved, the properties of the various interpolation methods, and what factors are important in any one situation, you can start making informed decisions about what method to use where, when and why. Rune
From: hank scorpio on 17 Apr 2010 16:01 thanks all - kind of confirmed what I thought, but I didn't want to assume ... Rune: 1) Which method is computationally faster? >>Linear I imagine ? 2) Which method produces the smoother curve? >>define 'smoother' - mathematically smoother ? visually smoother ? I'm working with images a lot so these might not be the same thing (?). 3) Which method can include points as they become available? 4) Which method requires all the points to be available before computing the interpolant? >>The use of my interp is on a complete data set that is established at runtime and wont change... The points to be interpolated in that data are generated in a loop 5) Which method balances amplitude of deviations against number of terms in the interpolant? >>no idea ! But back to question number2 - Certainly ringing isn't 'smooth' and out of range interpolated values will have to be tamed after the fact if they are to fit back into uint8 RGB data for instance. But then linear has that banding/bunching issue around grid data axes (it creates visual 'stars'). The edges of data sets needs consideration also, rounding gave the original data (ok), linear give 0's (yuck) cubic NaN (yuckier yet). Maybe I could create gradients or at least boundaries within a grid, round here (nearest neighbour boundaries), mostly or completely linear here (for speed across the bulk of data), more or all cubic here (for when linear fails)... Visual data is an odd ball - whatever looks best wins ;)
From: Bruno Luong on 17 Apr 2010 16:54
"hank scorpio" <breakbeak(a)hotmail.com> wrote in message <hqd424$rhb$1(a)fred.mathworks.com>... > But back to question number2 - Certainly ringing isn't 'smooth' and out of range interpolated values will have to be tamed after the fact if they are to fit back into uint8 RGB data for instance. Ringing IS actually *very* smooth, mathematically speaking. The ringing happens often spline interpolant of function that has relatively rapid change of the derivative(s) on a fix step grid (to see it, please experiment the fit to a Gaussian - an infinity smooth function - by spline on regular grid). Ringing could be partly suppressed, for example when the knots (locations of interpolation data) are appropriately chosen to cope with the rapid change of the derivative. The boundary conditions selected by the interpolant can also affected the ringing - in a lesser extend. Various Matlab INTERPN use the so called not-a-knot boundary conditions, which is not very robust for the ringing issue, IMO. > But then linear has that banding/bunching issue around grid data axes (it creates visual 'stars'). Yeap, because the tensorial linear function is not differentiable, and the jump of the derivative is usually large at the corner, where eight functions are patched together (in 3D). Bruno |