phoffric
asked on
Given a set of XYZ points , interpolate points to estimate a finer surface.
I will be given a set of X/Y points and their corresponding Z values. Z = f(X, Y), but I do not know the function f. The points will be clustered together and I don't expect pathological conditions. The local maximums and minimums will have extra sample points to help make the interpolation better. The goal is to come up with a smooth surface that represents the function f as close as possible.
The analyst providing me with the set of points of known XYZ points will also give me an XY rectangular grid; and at all the intersection points of horizontal and vertical lines, I need to provide a z-value.
One thought I had was to consider a point and look at 4 quadrants, and take the closest point in each quadrant, and using those 4 points or more to try to interpolate. Prefer to be able to use a curved surface to get the results rather than linear planes. One rule is that the final results will match the given XYZ points . The given points are known as anchor points or knots.
I am just looking for something functional. I am not interested in speed.
I am not allowed to use binaries, so I will have to build from source code in Linux or Windows.
Thanks in advance.
Paul
The analyst providing me with the set of points of known XYZ points will also give me an XY rectangular grid; and at all the intersection points of horizontal and vertical lines, I need to provide a z-value.
One thought I had was to consider a point and look at 4 quadrants, and take the closest point in each quadrant, and using those 4 points or more to try to interpolate. Prefer to be able to use a curved surface to get the results rather than linear planes. One rule is that the final results will match the given XYZ points . The given points are known as anchor points or knots.
I am just looking for something functional. I am not interested in speed.
I am not allowed to use binaries, so I will have to build from source code in Linux or Windows.
Thanks in advance.
Paul
SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
ASKER
>> You're given a set of X,Y coordinates and a Z value for each XY pair? Does that mean you're really working in 3 dimensions and you're given X,Y,Z for each point but don't know the shape of the surface?
Going out now but let me see if I can clarify one point. The problem is to find a 2d surface . The simplest example is consider a plane that is parallel to the XY axis one unit high in the Z direction . So yes, I am working in three dimensions but the surface is just a two dimensional surface . That is there is no volume. To continue with this example , suppose that the domain of X and Y are +1 or -1. That gives us a square in the XY plane for the domain . In this case the function F is just Z equals F equals 1. In this example, I will be giving a set of points (x,y,1) where X and Y are in that square and of course the Z value is 1. The XY values will not lie on any nice grid . When it does lie on the grid I have already solved that problem using a bicubic interpolation. If I were given a set of points as described above , then I would expect a bilinear interpolation and even a bicubic interpolation to give me a flat plane , Z equals F equals 1.
Hope this helps to clarify the geometry and what the interpolation is supposed to do. Thanks for responding . That's all I have time for tonight and have a good evening .
Going out now but let me see if I can clarify one point. The problem is to find a 2d surface . The simplest example is consider a plane that is parallel to the XY axis one unit high in the Z direction . So yes, I am working in three dimensions but the surface is just a two dimensional surface . That is there is no volume. To continue with this example , suppose that the domain of X and Y are +1 or -1. That gives us a square in the XY plane for the domain . In this case the function F is just Z equals F equals 1. In this example, I will be giving a set of points (x,y,1) where X and Y are in that square and of course the Z value is 1. The XY values will not lie on any nice grid . When it does lie on the grid I have already solved that problem using a bicubic interpolation. If I were given a set of points as described above , then I would expect a bilinear interpolation and even a bicubic interpolation to give me a flat plane , Z equals F equals 1.
Hope this helps to clarify the geometry and what the interpolation is supposed to do. Thanks for responding . That's all I have time for tonight and have a good evening .
Better, but I'm still missing something.
Any 3 random points define a plane. Are all the points on a single plane? Are you trying to find the plane with the most points? Are you "averaging" the points to come up with a plane that follows the "general direction" of the points?
Any 3 random points define a plane. Are all the points on a single plane? Are you trying to find the plane with the most points? Are you "averaging" the points to come up with a plane that follows the "general direction" of the points?
It appears that this is a classical problem in approximation theory.
You want to find a function that approximates the given points according to some approximation goodness criterion.
But, you didn't say what that that goodness criterion is.
As Kent Olsen suggests, 3 random pints define a plane.
But what if you have 100 points and will approximate them all optimally with a plane?
Then you could compute a least-squares fit to all the given points.
And what if you want a minimax approximation, and again a plane, to the given points?
Then you could compute a minimax approximation.
... and so forth.
Then you could do the same with 2nd order expressions.
Then you could do the same with 3rd order expressions.
... and so forth.
This isn't THE answer but it will lead you into the correct discussions I should think.
A "smooth surface" is fine but what are the approximation criteria regarding the errors in the approximation?
Also, you didn't say if the approximant must identically MATCH all the given points or, more reasonably, approximate them with a minimum error.
Obviously, anything in between the given points is fair game...
You want to find a function that approximates the given points according to some approximation goodness criterion.
But, you didn't say what that that goodness criterion is.
As Kent Olsen suggests, 3 random pints define a plane.
But what if you have 100 points and will approximate them all optimally with a plane?
Then you could compute a least-squares fit to all the given points.
And what if you want a minimax approximation, and again a plane, to the given points?
Then you could compute a minimax approximation.
... and so forth.
Then you could do the same with 2nd order expressions.
Then you could do the same with 3rd order expressions.
... and so forth.
This isn't THE answer but it will lead you into the correct discussions I should think.
A "smooth surface" is fine but what are the approximation criteria regarding the errors in the approximation?
Also, you didn't say if the approximant must identically MATCH all the given points or, more reasonably, approximate them with a minimum error.
Obviously, anything in between the given points is fair game...
SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
ASKER
I have added to the OP the following EDIT:
The analyst providing me with the set of points of known XYZ points will also give me an XY rectangular grid; and at all the intersection points of horizontal and vertical lines, I need to provide a z-value.
==========================
Hi Kent,
I'm a little confused at the wording. You're given a set of X,Y coordinates and a Z value for each XY pair?
- Yes, for each XY pair, I am given a Z value. Or, we can think of it as being given a set of (x,y,z) points, where the z-values define a nice, non-pathological 2d surface function. That is, for a given XY, there is only one value of Z.
Does that mean you're really working in 3 dimensions
- Yes, working in 3D, but surface is 2D: Z = f(x,y), but I don't know f(x,y).
and you're given X,Y,Z for each point but don't know the shape of the surface?
- I don't know the shape of the surface. However, we know the surface is smooth and curved. However, to simplify matters, I don't think we will have to force continuity of the 2nd partial derivatives (as in finite differences) as we move from one section of the domain to another.
How many points are you given?
- Varies. Every case is different. From a few dozen to a few million.
Is a solution unique?
- Approximations are not unique. Each different interpolation method results in a different solution.
Is the resulting surface "regular"? i.e. the edge of a uniform solid such as a sphere or cone?
- I am not sure of your meaning. What would an irregular surface be?
I believe that I'd start by selecting up to 6 points. Those with the smallest and largest values along the 3 axis. Build up from there.
- I will be given a set of known (x,y,z) points where the z-values represent a surface. Not sure which 6 points I should pick and why? Not sure how to "build up"
- Do any of the other points share a common X, Y, or Z coordinate with the 6 selected?
- Every (x,y,z) point will be unique; but, most likely, the x will not be unique; nor will the y or z be unique. Then again, it is possible that all three coordinates will be unique.
- Do any of the points seem like outliers?
No
- Are there multiple clusters of points?
- No.
Tricky problem
- Yes
==========================
Hi aburr,
Pick a point, any point,. Go to a nearby known point. Take the average.
- I'll go to a nearby known point; but take the average of what?
midpoint of the line between your two selected points.
- But, so far, I've only gone to a nearby known point. Or did you want me to go to the two nearest known XY points? Keep in mind that the XY point may not be colinear with the two nearest known XY points.
You can now construct a parabloa
- When I did the bilinear and bicubic interpolation where the known points all fell on a nice rectangular grid in the XY plane, then the literature did not indicate parabolic curves as a solution. I think that was to get desired finite 1st and 2nd partial derivatives at all the KNOTS to be the same from one rectangle to its adjacent rectangles. But, since I am not starting with a nice rectangular XY grid, I am certainly willing to try other avenues. Now to get a parabolic surface, I guess I will need more than 3 XYZ points. I'll certainly be thinking about your averaging approach on piecewise sections of the XY plane, but at the moment, it is a little tricky to define those sections. In my stated previous interpolations, the piecewise sections were every rectangle that were defined by 4 known points.
==========================
Hi Kent,
Are all the points on a single plane?
- With my example, I did give the simplest surface I could think of; namely all the points are on a single plane that is parallel to the XY plane. But, no, I don't expect anything like that. Sorry to cause some confusion with my example.
Are you trying to find the plane with the most points?
I am definitely not trying to find a single plane for the whole solution. Possibly I will consider tiny planes around nearby set of three XYZ points. But one problem is that when I add a 4th nearby point and combine that with two of the used 3 points, then I get a different plane that would somehow have to be reconciled with the first plane. Also, if one of the points that I have to find a z-value has an XY coordinate that is part of the known points, then the rule is that the z-value I come up with must be the same as the given z-value. I am not sure how that will be done using planes.
Are you "averaging" the points to come up with a plane that follows the "general direction" of the points?
-For my previous bilinear surface where I was given a grid of XY values, there was a weighted averaging of two horizontal points for the top and bottom sides of the rectangle; and then from those two 1d linear interpolations, I did another 1d linear weighted average vertically to get the z value at any arbitrary point within the rectangle.
- How to do this where I don't have a rectangular grid of known z-values and even how to identify piecewise sections is part of the problem I am facing.
==========================
Hi Fred,
classical problem in approximation theory
- This is good to know because now I have hope that there is a classical solution for me to understand. I have access to Safari books online. So, if you can point me to a chapter in a book that deals with this problem, that would help me a lot.
You want to find a function that approximates the given points according to some approximation goodness criterion.
But, you didn't say what that that goodness criterion is.
- You bring up an important point in judging the algorithms. Here is how we compared interpolation algorithms in the rectangular grid case. The analyst made up a known function, z=f(x,y); and did not tell us what it is. He then sampled the function in a square domain such that he tried to give us extra points at the humps and valleys. He told us what interpolating rectangular grid he wanted us to find z-values. We submitted our results and then he computed the errors between our submission and his secret function. He showed us a number of heat maps for us to visualize the errors (highest errors were red; no errors were blue). We saw visually that bicubic was superior to bilinear - no surprise, since that is what the literature generally said.
Then you could compute a least-squares fit to all the given points.
- Not sure how to get this to match the known points.
And what if you want a minimax approximation, and again a plane, to the given points?
- I don't know about minimax. In light of my above answers, if this is viable, I would be interested in learning more about it.
A "smooth surface" is fine but what are the approximation criteria regarding the errors in the approximation?
- I think this is again the verification issue you brought up. The analyst also brought up two interpolations and we could visually see how the bicubic more closely approximated his secret f(x,y) than the bilinear. And he will give us the exact worst-case errors for differnt sections of the domain so that we can figure out which algorithm (e.g., there are variations on bicubic) gives the better results.
==========================
Hi Andy,
- I can see how a 2d fourier analysis would be a viable candidate were it not for the rule that the interpolation must match the known values. I wonder if that would be the case. Time permitting, I'll think about it. I'll also have to think about using 2d fourier analysis on a set of non-rectangular XY points.
==========================
Hi aburr,
"One rule is that the final results will match the given XYZ points
- Thanks for helping out.
==========================
The analyst providing me with the set of points of known XYZ points will also give me an XY rectangular grid; and at all the intersection points of horizontal and vertical lines, I need to provide a z-value.
==========================
Hi Kent,
I'm a little confused at the wording. You're given a set of X,Y coordinates and a Z value for each XY pair?
- Yes, for each XY pair, I am given a Z value. Or, we can think of it as being given a set of (x,y,z) points, where the z-values define a nice, non-pathological 2d surface function. That is, for a given XY, there is only one value of Z.
Does that mean you're really working in 3 dimensions
- Yes, working in 3D, but surface is 2D: Z = f(x,y), but I don't know f(x,y).
and you're given X,Y,Z for each point but don't know the shape of the surface?
- I don't know the shape of the surface. However, we know the surface is smooth and curved. However, to simplify matters, I don't think we will have to force continuity of the 2nd partial derivatives (as in finite differences) as we move from one section of the domain to another.
How many points are you given?
- Varies. Every case is different. From a few dozen to a few million.
Is a solution unique?
- Approximations are not unique. Each different interpolation method results in a different solution.
Is the resulting surface "regular"? i.e. the edge of a uniform solid such as a sphere or cone?
- I am not sure of your meaning. What would an irregular surface be?
I believe that I'd start by selecting up to 6 points. Those with the smallest and largest values along the 3 axis. Build up from there.
- I will be given a set of known (x,y,z) points where the z-values represent a surface. Not sure which 6 points I should pick and why? Not sure how to "build up"
- Do any of the other points share a common X, Y, or Z coordinate with the 6 selected?
- Every (x,y,z) point will be unique; but, most likely, the x will not be unique; nor will the y or z be unique. Then again, it is possible that all three coordinates will be unique.
- Do any of the points seem like outliers?
No
- Are there multiple clusters of points?
- No.
Tricky problem
- Yes
==========================
Hi aburr,
Pick a point, any point,. Go to a nearby known point. Take the average.
- I'll go to a nearby known point; but take the average of what?
midpoint of the line between your two selected points.
- But, so far, I've only gone to a nearby known point. Or did you want me to go to the two nearest known XY points? Keep in mind that the XY point may not be colinear with the two nearest known XY points.
You can now construct a parabloa
- When I did the bilinear and bicubic interpolation where the known points all fell on a nice rectangular grid in the XY plane, then the literature did not indicate parabolic curves as a solution. I think that was to get desired finite 1st and 2nd partial derivatives at all the KNOTS to be the same from one rectangle to its adjacent rectangles. But, since I am not starting with a nice rectangular XY grid, I am certainly willing to try other avenues. Now to get a parabolic surface, I guess I will need more than 3 XYZ points. I'll certainly be thinking about your averaging approach on piecewise sections of the XY plane, but at the moment, it is a little tricky to define those sections. In my stated previous interpolations, the piecewise sections were every rectangle that were defined by 4 known points.
==========================
Hi Kent,
Are all the points on a single plane?
- With my example, I did give the simplest surface I could think of; namely all the points are on a single plane that is parallel to the XY plane. But, no, I don't expect anything like that. Sorry to cause some confusion with my example.
Are you trying to find the plane with the most points?
I am definitely not trying to find a single plane for the whole solution. Possibly I will consider tiny planes around nearby set of three XYZ points. But one problem is that when I add a 4th nearby point and combine that with two of the used 3 points, then I get a different plane that would somehow have to be reconciled with the first plane. Also, if one of the points that I have to find a z-value has an XY coordinate that is part of the known points, then the rule is that the z-value I come up with must be the same as the given z-value. I am not sure how that will be done using planes.
Are you "averaging" the points to come up with a plane that follows the "general direction" of the points?
-For my previous bilinear surface where I was given a grid of XY values, there was a weighted averaging of two horizontal points for the top and bottom sides of the rectangle; and then from those two 1d linear interpolations, I did another 1d linear weighted average vertically to get the z value at any arbitrary point within the rectangle.
- How to do this where I don't have a rectangular grid of known z-values and even how to identify piecewise sections is part of the problem I am facing.
==========================
Hi Fred,
classical problem in approximation theory
- This is good to know because now I have hope that there is a classical solution for me to understand. I have access to Safari books online. So, if you can point me to a chapter in a book that deals with this problem, that would help me a lot.
You want to find a function that approximates the given points according to some approximation goodness criterion.
But, you didn't say what that that goodness criterion is.
- You bring up an important point in judging the algorithms. Here is how we compared interpolation algorithms in the rectangular grid case. The analyst made up a known function, z=f(x,y); and did not tell us what it is. He then sampled the function in a square domain such that he tried to give us extra points at the humps and valleys. He told us what interpolating rectangular grid he wanted us to find z-values. We submitted our results and then he computed the errors between our submission and his secret function. He showed us a number of heat maps for us to visualize the errors (highest errors were red; no errors were blue). We saw visually that bicubic was superior to bilinear - no surprise, since that is what the literature generally said.
Then you could compute a least-squares fit to all the given points.
- Not sure how to get this to match the known points.
And what if you want a minimax approximation, and again a plane, to the given points?
- I don't know about minimax. In light of my above answers, if this is viable, I would be interested in learning more about it.
A "smooth surface" is fine but what are the approximation criteria regarding the errors in the approximation?
- I think this is again the verification issue you brought up. The analyst also brought up two interpolations and we could visually see how the bicubic more closely approximated his secret f(x,y) than the bilinear. And he will give us the exact worst-case errors for differnt sections of the domain so that we can figure out which algorithm (e.g., there are variations on bicubic) gives the better results.
==========================
Hi Andy,
- I can see how a 2d fourier analysis would be a viable candidate were it not for the rule that the interpolation must match the known values. I wonder if that would be the case. Time permitting, I'll think about it. I'll also have to think about using 2d fourier analysis on a set of non-rectangular XY points.
==========================
Hi aburr,
"One rule is that the final results will match the given XYZ points
- Thanks for helping out.
==========================
SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Hi aburr,
Pick a point, any point,. Go to a nearby known point. Take the average.
- I'll go to a nearby known point; but take the average of what? The two z values
midpoint of the line between your two selected points. The initial point and the nearest (or any other) point
- But, so far, I've only gone to a nearby known point. Or did you want me to go to the two nearest known XY points? Keep in mind that the XY point may not be colinear with the two nearest known XY points.
Good point. My ideas will not give you a function. It will just give you a z value for as many x,y values as you want to calculate. I do not think that is what you want, but it is the best I can give, so listen to the other guys.
You can now construct a parablola. forget it
Pick a point, any point,. Go to a nearby known point. Take the average.
- I'll go to a nearby known point; but take the average of what? The two z values
midpoint of the line between your two selected points. The initial point and the nearest (or any other) point
- But, so far, I've only gone to a nearby known point. Or did you want me to go to the two nearest known XY points? Keep in mind that the XY point may not be colinear with the two nearest known XY points.
Good point. My ideas will not give you a function. It will just give you a z value for as many x,y values as you want to calculate. I do not think that is what you want, but it is the best I can give, so listen to the other guys.
You can now construct a parablola. forget it
ASKER
>> Is MATLAB source code acceptable?
If you know of Matlab source code that does this, I can convert it to c our c++. Of course built in matlab functions with no source code will not help much if the function is complicated.
>> opens the question of "what is smooth" and to what degree?
Smooth is what we expect under perfect knowledge of the surface to infinite degree. After interpolation using a primitive algorithm I would be satisfied at the first attempt to have discontinuity at the first partial derivatives.
>> LOTS of good information to be found there.
Ok, sounds like you understand the problem. If you could provide one link that helps me understand one approach, I'll give it a try.
If you know of Matlab source code that does this, I can convert it to c our c++. Of course built in matlab functions with no source code will not help much if the function is complicated.
>> opens the question of "what is smooth" and to what degree?
Smooth is what we expect under perfect knowledge of the surface to infinite degree. After interpolation using a primitive algorithm I would be satisfied at the first attempt to have discontinuity at the first partial derivatives.
>> LOTS of good information to be found there.
Ok, sounds like you understand the problem. If you could provide one link that helps me understand one approach, I'll give it a try.
SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Hi Paul,
I'm still struggling with the basic rules as a couple of comments seem to conflict.
-Does that mean you're really working in 3 dimensions
-- Yes, working in 3D, but surface is 2D: Z = f(x,y), but I don't know f(x,y).
Suggesting that you're looking for Z for each X,Y that results in all of the points (or as many as possible) on a single plane.
-and you're given X,Y,Z for each point but don't know the shape of the surface?
-- I don't know the shape of the surface. However, we know the surface is smooth and curved. However, to simplify matters, I don't think we will have to force continuity of the 2nd partial derivatives (as in finite differences) as we move from one section of the domain to another.
If the surface is curved, it's not planar (2 dimensional).
- Is the resulting surface "regular"? i.e. the edge of a uniform solid such as a sphere or cone?
-- I am not sure of your meaning. What would an irregular surface be?
A merging of multiple shapes. Say a half sphere rising from a plane or a 3 sphere snowman, etc. If so, are the edges where the shapes meet smoothed or do the objects juxtapose?
I'm still struggling with the basic rules as a couple of comments seem to conflict.
-Does that mean you're really working in 3 dimensions
-- Yes, working in 3D, but surface is 2D: Z = f(x,y), but I don't know f(x,y).
Suggesting that you're looking for Z for each X,Y that results in all of the points (or as many as possible) on a single plane.
-and you're given X,Y,Z for each point but don't know the shape of the surface?
-- I don't know the shape of the surface. However, we know the surface is smooth and curved. However, to simplify matters, I don't think we will have to force continuity of the 2nd partial derivatives (as in finite differences) as we move from one section of the domain to another.
If the surface is curved, it's not planar (2 dimensional).
- Is the resulting surface "regular"? i.e. the edge of a uniform solid such as a sphere or cone?
-- I am not sure of your meaning. What would an irregular surface be?
A merging of multiple shapes. Say a half sphere rising from a plane or a 3 sphere snowman, etc. If so, are the edges where the shapes meet smoothed or do the objects juxtapose?
I will have to build from source code in Linux or Windowsnow this appears to be "C" or "C++" which is more restrictive. OK.
My suggestion to Google "interpolation of surfaces" was because there are a number of hits and some may strike you as more interesting, underststandable, etc. That's not something that anyone can do for you. But here's one that looks interesting to ME:
https://en.wikipedia.org/wiki/Bicubic_interpolation
ASKER
Hi Andy,
>> Or put another ways are the values you are supplied with the result of a calculation?
Sometimes yes, from a 3rd party program.
Sometimes no with possible errors, but these measurements are considered to be the best known values.
We do not want to add to any measured errors.
Hi Fred,
>> now this appears to be "C" or "C++" which is more restrictive.
Any language will do, and I will translate. But if the language has a built-in algorithm, then there is nothing to translate. An algorithm in pseudo-code will do, and I'll translate that too if I understand it.
>> https://en.wikipedia.org/wiki/Bicubic_interpolation
Good link that I used for regular grids for my bicubic interpolation that I discussed above. See restriction.
" bicubic interpolation is an extension of cubic interpolation for interpolating data points on a two-dimensional regular grid."
https://en.wikipedia.org/wiki/Regular_grid
Hi Kent,
It seems to me that I should have given a link to my previous work on bicubic interpolation.
https://en.wikipedia.org/wiki/Bicubic_interpolation
Take a look at the bicubic and bilinear drawings. See if that answers your question about my description. Those pictures show XY points that lie in a rectangular regular grid. My new problem is that I am given a set of XY points that do not lie in a rectangular regular grid.
>> Or put another ways are the values you are supplied with the result of a calculation?
Sometimes yes, from a 3rd party program.
Sometimes no with possible errors, but these measurements are considered to be the best known values.
We do not want to add to any measured errors.
Hi Fred,
>> now this appears to be "C" or "C++" which is more restrictive.
Any language will do, and I will translate. But if the language has a built-in algorithm, then there is nothing to translate. An algorithm in pseudo-code will do, and I'll translate that too if I understand it.
>> https://en.wikipedia.org/wiki/Bicubic_interpolation
Good link that I used for regular grids for my bicubic interpolation that I discussed above. See restriction.
" bicubic interpolation is an extension of cubic interpolation for interpolating data points on a two-dimensional regular grid."
https://en.wikipedia.org/wiki/Regular_grid
Hi Kent,
It seems to me that I should have given a link to my previous work on bicubic interpolation.
https://en.wikipedia.org/wiki/Bicubic_interpolation
Take a look at the bicubic and bilinear drawings. See if that answers your question about my description. Those pictures show XY points that lie in a rectangular regular grid. My new problem is that I am given a set of XY points that do not lie in a rectangular regular grid.
ASKER CERTIFIED SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
ASKER
Hi Fred,
0. Thanks for your input. As I mentioned earlier, a high level matlab function that solves the problem completely may not be useful for converting to C++ since the formula may not be transparent. However, lower level functions such as fft2 which show easy formula in the matlab documentation are useful. Once I understand better your matlab algorithm, I can establish a baseline in matlab and after converting the program to C++, I'll be able to compare results. So, since you mentioned matlab, if you would be able to show me the sequence of matlab code (or just explanations), then I can try to put together a matlab example to demonstrate the results; and then proceed with the C++ conversion. If you are comfortable with matlab, and provided a skeleton of code (or more), then perhaps many of the following questions will go away, since I should be able to then map your comments to the actual matlab code.
1. >> Assign them to this finer grid and use methods that require a regular grid.
If I were working in a sampled 1D time domain with {t_i, y_i = f(t_i)}, then if t_i is uniform, I could take the fft(f(t)), and get Y(w) = F(w). But if t_i is not uniform, then I don't know how to take a fft of f(t_i). Likewise, for the 2D case, I don't follow how to get a regular grid of (XYZ) values given a irregular set of points. If I draw a horizontal and vertical line through every point, then each horizontal line will likely have a different number of points. So, I am still unclear how to get a regular grid of XY coordinates and their corresponding pseudo-known Z-values.
2. >> slight misalignment
Given that the analyst plans on providing me with points that are concentrated at the peaks and valleys to help get a good interpolation, it seems that the alignment might be large. This point may go away once I understand the setup in item 1.
3. >> Often, people don't quantize things in their heads ... resulting distribution has meaning.
Sorry, I didn't understand this paragraph. But, again, maybe if I better understand your algorithm in items 1 and 4, this will become clearer.
4. >> using the Discrete (Fast) Fourier Transform
I like the idea using a FFT to interpolate.
5. >> Select the convolution kernel (something akin to a lowpass filter sinc function).
(a) Is the lowpass filter strictly needed for anti-aliasing?
(b) How do I create a 2d sinc function?
(c) Do I take a rectangle of height 1 in the spatial domain, and do a fft2 of it?
(d) How do I know the dimensions of the rectangle; or how do I know the distance between zeros in the sinc function in the frequency domain?
6. >> Make the kernel array of some appropriate number of samples.
Is this what you mean by appropriate: Suppose I had a regular square NxN 2D grid of XY coordinates that represented the sinc function, and I wanted to interpolate to a 2D grid having twice the number of X values, and twice the number of Y values. Then "appropriate" would be (2Nx2N) grid points. And to do this, would zero-pad to the right, on top, and northeast of the original NxN sinc function.
7. >> Select TWO periods of the frequency record and lowpass filter around the new fs/2.
Not sure how to determine fs given a set of XYZ known values from the analyst.
8. >> Repeat for as many times as you need.
Not understanding "repeat" and "need".
9. >> Just because MATLAB has a bunch of built-in library functions, there's no reason one has to use them.
Actually, if you can answer the questions using lower level matlab functions such as fft2, etc., that may work out just fine. If you actually showed a template of code, I could even run it in matlab. If I understand the documentation to the functions, I can convert to C++.
0. Thanks for your input. As I mentioned earlier, a high level matlab function that solves the problem completely may not be useful for converting to C++ since the formula may not be transparent. However, lower level functions such as fft2 which show easy formula in the matlab documentation are useful. Once I understand better your matlab algorithm, I can establish a baseline in matlab and after converting the program to C++, I'll be able to compare results. So, since you mentioned matlab, if you would be able to show me the sequence of matlab code (or just explanations), then I can try to put together a matlab example to demonstrate the results; and then proceed with the C++ conversion. If you are comfortable with matlab, and provided a skeleton of code (or more), then perhaps many of the following questions will go away, since I should be able to then map your comments to the actual matlab code.
1. >> Assign them to this finer grid and use methods that require a regular grid.
If I were working in a sampled 1D time domain with {t_i, y_i = f(t_i)}, then if t_i is uniform, I could take the fft(f(t)), and get Y(w) = F(w). But if t_i is not uniform, then I don't know how to take a fft of f(t_i). Likewise, for the 2D case, I don't follow how to get a regular grid of (XYZ) values given a irregular set of points. If I draw a horizontal and vertical line through every point, then each horizontal line will likely have a different number of points. So, I am still unclear how to get a regular grid of XY coordinates and their corresponding pseudo-known Z-values.
2. >> slight misalignment
Given that the analyst plans on providing me with points that are concentrated at the peaks and valleys to help get a good interpolation, it seems that the alignment might be large. This point may go away once I understand the setup in item 1.
3. >> Often, people don't quantize things in their heads ... resulting distribution has meaning.
Sorry, I didn't understand this paragraph. But, again, maybe if I better understand your algorithm in items 1 and 4, this will become clearer.
4. >> using the Discrete (Fast) Fourier Transform
I like the idea using a FFT to interpolate.
5. >> Select the convolution kernel (something akin to a lowpass filter sinc function).
(a) Is the lowpass filter strictly needed for anti-aliasing?
(b) How do I create a 2d sinc function?
(c) Do I take a rectangle of height 1 in the spatial domain, and do a fft2 of it?
(d) How do I know the dimensions of the rectangle; or how do I know the distance between zeros in the sinc function in the frequency domain?
6. >> Make the kernel array of some appropriate number of samples.
Is this what you mean by appropriate: Suppose I had a regular square NxN 2D grid of XY coordinates that represented the sinc function, and I wanted to interpolate to a 2D grid having twice the number of X values, and twice the number of Y values. Then "appropriate" would be (2Nx2N) grid points. And to do this, would zero-pad to the right, on top, and northeast of the original NxN sinc function.
7. >> Select TWO periods of the frequency record and lowpass filter around the new fs/2.
Not sure how to determine fs given a set of XYZ known values from the analyst.
8. >> Repeat for as many times as you need.
Not understanding "repeat" and "need".
9. >> Just because MATLAB has a bunch of built-in library functions, there's no reason one has to use them.
Actually, if you can answer the questions using lower level matlab functions such as fft2, etc., that may work out just fine. If you actually showed a template of code, I could even run it in matlab. If I understand the documentation to the functions, I can convert to C++.
SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
ASKER
Hi Kent,
Let me know if I understand you correctly. You compute a regular grid and fill in rectangles where a known value exists within that rectangle . These known values are used to fill in the unknown rectangles by a smoothing process.
From my previous experience, if I have 4 known values that form a rectangle then a bilinear interpolation is doable. And if I have 16 known values in a Nice regular form, then I can do a bicubic interpolation to smooth out the innermost unknown rectangle.
Question I have is how to do this smoothing operation when the known values in the grid do not form a nice rectangle.
Let me know if I understand you correctly. You compute a regular grid and fill in rectangles where a known value exists within that rectangle . These known values are used to fill in the unknown rectangles by a smoothing process.
From my previous experience, if I have 4 known values that form a rectangle then a bilinear interpolation is doable. And if I have 16 known values in a Nice regular form, then I can do a bicubic interpolation to smooth out the innermost unknown rectangle.
Question I have is how to do this smoothing operation when the known values in the grid do not form a nice rectangle.
ASKER
I am tempted to consider aburr's approach.
ASKER
I will be mulling over Fred's approach with some co-workers to see whether we understand it and can live with what appears to be introducing some errors to the known values. My experience has been mostly sampled data at regular delta time, and am new to interpolation; and this 2d problem is harder than what I did last month.
The requirement that interpolation have the exact value at the anchor known value points comes from the lead who will be back next year. So varying from that rule seems like a non starter for me.
The requirement that interpolation have the exact value at the anchor known value points comes from the lead who will be back next year. So varying from that rule seems like a non starter for me.
SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
ASKER
Hi Kent,
In OP: Prefer to be able to use a curved surface to get the results rather than linear planes.
You are suggesting a linear approach.
But maybe I'll have to give up that goal unless I can use the fft.
Keep in mind that there may be a known point that has no other known point in either the horizontal or vertical direction. So then you suggest for all the unknown points we look elsewhere to find known points that influence the value.
>> What if bound by a 1 in the cell to the North and 100 two cells North and 1 East? Direction, magnitude, and value all come into play.
I realize this and these questions you pose are the crux of the problem. There is no linear approach (that is a plane) that works for these points in your example and which will pass through the anchor (knot) points. Any ideas?
In OP: Prefer to be able to use a curved surface to get the results rather than linear planes.
You are suggesting a linear approach.
But maybe I'll have to give up that goal unless I can use the fft.
Keep in mind that there may be a known point that has no other known point in either the horizontal or vertical direction. So then you suggest for all the unknown points we look elsewhere to find known points that influence the value.
>> What if bound by a 1 in the cell to the North and 100 two cells North and 1 East? Direction, magnitude, and value all come into play.
I realize this and these questions you pose are the crux of the problem. There is no linear approach (that is a plane) that works for these points in your example and which will pass through the anchor (knot) points. Any ideas?
ASKER
Hi Fred,
I think I need to understand answers to 5a-d about sinc. (Not to say that I won't have other questions, but this one is one of the critical items.)
I think I need to understand answers to 5a-d about sinc. (Not to say that I won't have other questions, but this one is one of the critical items.)
SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
ASKER
Thanks for clarifying about the sinc function. I'll ask the lead when he gets back next year about all those good system engineering questions you asked. I'll see if I can find a systems engineer who has time to discuss them.
>> I'm not sure any method will solve the problem
Not even the fft approach? If I am given a 2d matrix whose entries represent a function that is half a sphere's surface, that is not a solid object. Depending on how I view that surface, I may be able to see all of it from a top view or just half of it from a side view that obscures the other half. I don't see why this should prevent an interpolation.
>> I'm not sure any method will solve the problem
Not even the fft approach? If I am given a 2d matrix whose entries represent a function that is half a sphere's surface, that is not a solid object. Depending on how I view that surface, I may be able to see all of it from a top view or just half of it from a side view that obscures the other half. I don't see why this should prevent an interpolation.
SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
ASKER
>> It appears that the intent here is a surface over a 2D coordinate system.
Yes.
>> If I am given a 2d matrix whose entries represent a function
If given a 2D matrix where the two indices in the matrix represent x and y coordinates, then the entry in the matrix is just a single z value. The matrix has to be a surface that represents a function that doesn't wrap around going above or below itself (since then, a matrix entry would have to have two values in it). For a given (x,y) coordinate, there is only one value of z.
Yes.
>> If I am given a 2d matrix whose entries represent a function
If given a 2D matrix where the two indices in the matrix represent x and y coordinates, then the entry in the matrix is just a single z value. The matrix has to be a surface that represents a function that doesn't wrap around going above or below itself (since then, a matrix entry would have to have two values in it). For a given (x,y) coordinate, there is only one value of z.
Right. That's what I tried to say.
And, what's more, we can't readily talk about a "matrix" without some rules about the coordinates. This suggests a regular grid on X,Y.
Otherwise, with arbitrary coordinates in X,Y, one must create an array of triplets with X,Y,F(x,y).
And, as I mentioned earlier, if the surface isn't single-valued then at least an array of quadruplets X,Y,Z,F(x,y,z).
In these latter two cases the array of triplets or quadruplets isn't (certainly need not be) in a "matrix" with regular spacing implied.
It just becomes a list with no meaning to the physical positioning of the entries - such as the order of the entries.
That doesn't mean the list can't be sorted but there is still no "distance" between entries unless somehow defined and noted.
You might conclude that talking about a matrix is to talk about a discretized space - lacking any more descriptive notation.
And, what's more, we can't readily talk about a "matrix" without some rules about the coordinates. This suggests a regular grid on X,Y.
Otherwise, with arbitrary coordinates in X,Y, one must create an array of triplets with X,Y,F(x,y).
And, as I mentioned earlier, if the surface isn't single-valued then at least an array of quadruplets X,Y,Z,F(x,y,z).
In these latter two cases the array of triplets or quadruplets isn't (certainly need not be) in a "matrix" with regular spacing implied.
It just becomes a list with no meaning to the physical positioning of the entries - such as the order of the entries.
That doesn't mean the list can't be sorted but there is still no "distance" between entries unless somehow defined and noted.
You might conclude that talking about a matrix is to talk about a discretized space - lacking any more descriptive notation.
ASKER
Hello all!
I got a new set of irregular data, and in the limited amount of time this week, I am going to take a stab using my own approach based on specific knowledge about how the original dataset was decimated. Although the data is irregular, it doesn't fall into a truly "scattered" category. Because of the special decimation process to get more peaks and valleys, I will transform that semi-scattered data set into a regular grid, and then apply my Regular Bicubic Interpolation algorithm, and see what pops out. (And this setup will also lend itself to a FFT test using Fred's principles, if I can find a short FFT C/C++ routine; if not, I'll just do a DFT.)
I do have some questions on some of your comments.
===================
@Fred,
1. Now you can still use convolution (or some other approach). You can convolve a regularly-spaced FIR filter with non-uniform data but the math is just slightly more tedious.
-- Could you point me in the right direction for this "non-uniform data" data case where the math is more tedious by a bit.
2. In your response to: (a) Is the lowpass filter strictly needed for anti-aliasing?
I thought I understand the first picture, pretty sure I follow the 2nd, but not the 3rd.
So, maybe I don't even understand the first.
Maybe if explained in terms of block diagrams starting with spatial input and output, and fft and low pass filtering in between, I will follow your words better. In the first picture, just to be sure I am on the same page, where does Original FFT Samples show up in the block diagram?
Or maybe we can just start with where zero's from 16-48 came from starting with the first picture which only has zero's from 16-18.
===================
@Kent,
I know I must not have been clear about the nature of the data. I hope my previous comments helped to clarify that I am not dealing with either solid objects or with surfaces that wrap around. That is, in my model, a given (x,y) coordinate will have exactly one z-value.
>> Find the 2 closest anchor points to our target point.
I have some ideas on how to identify the closest anchor points, and would like to hear what kind of data structure you suggest to do this.
>> Average (scaled by distance) the two anchor points.
I have some ideas on how to average (scaled by distance) the two anchor points, and would like to hear what specific kind of averaging you had in mind. Also, should it just be two anchor points. How about 3 or 4?
I have concocted a simple example of some data points. Notice that for Y-index=4 (which corresponds to Y==5.0), there is only one point available; namely, at X-index=2 (which corresponds to X==0.5). Thus, the single anchor point on that row is (0.5, 5.0, 6.0)
I threw in 3 query points, x, y, z. I was wondering if you could show me what you had in mind to get the z-values at those locations.
The below plot shows X- and Y-index #'s and z-values. Below this plot are the corresponding X- and Y-coordinate values associated with these indices.
I got a new set of irregular data, and in the limited amount of time this week, I am going to take a stab using my own approach based on specific knowledge about how the original dataset was decimated. Although the data is irregular, it doesn't fall into a truly "scattered" category. Because of the special decimation process to get more peaks and valleys, I will transform that semi-scattered data set into a regular grid, and then apply my Regular Bicubic Interpolation algorithm, and see what pops out. (And this setup will also lend itself to a FFT test using Fred's principles, if I can find a short FFT C/C++ routine; if not, I'll just do a DFT.)
I do have some questions on some of your comments.
===================
@Fred,
1. Now you can still use convolution (or some other approach). You can convolve a regularly-spaced FIR filter with non-uniform data but the math is just slightly more tedious.
-- Could you point me in the right direction for this "non-uniform data" data case where the math is more tedious by a bit.
2. In your response to: (a) Is the lowpass filter strictly needed for anti-aliasing?
I thought I understand the first picture, pretty sure I follow the 2nd, but not the 3rd.
So, maybe I don't even understand the first.
Maybe if explained in terms of block diagrams starting with spatial input and output, and fft and low pass filtering in between, I will follow your words better. In the first picture, just to be sure I am on the same page, where does Original FFT Samples show up in the block diagram?
Or maybe we can just start with where zero's from 16-48 came from starting with the first picture which only has zero's from 16-18.
===================
@Kent,
I know I must not have been clear about the nature of the data. I hope my previous comments helped to clarify that I am not dealing with either solid objects or with surfaces that wrap around. That is, in my model, a given (x,y) coordinate will have exactly one z-value.
>> Find the 2 closest anchor points to our target point.
I have some ideas on how to identify the closest anchor points, and would like to hear what kind of data structure you suggest to do this.
>> Average (scaled by distance) the two anchor points.
I have some ideas on how to average (scaled by distance) the two anchor points, and would like to hear what specific kind of averaging you had in mind. Also, should it just be two anchor points. How about 3 or 4?
I have concocted a simple example of some data points. Notice that for Y-index=4 (which corresponds to Y==5.0), there is only one point available; namely, at X-index=2 (which corresponds to X==0.5). Thus, the single anchor point on that row is (0.5, 5.0, 6.0)
I threw in 3 query points, x, y, z. I was wondering if you could show me what you had in mind to get the z-values at those locations.
The below plot shows X- and Y-index #'s and z-values. Below this plot are the corresponding X- and Y-coordinate values associated with these indices.
Row#
5| 5 9
4| 6 x
3| y 7 8
2| 4 z
1| 6
--------------------
Col#: 1 2
12345678901234567890
Where Row# 1-5 ~ Y index having values of:
1: 0.0
2: 1.0
3: 3.0
4: 5.0
5: 6.0
Where Col# 1-20 ~ X index having values of:
1: 0.0
2: 0.5
3: 1.0
4: 1.5
5: 2.5
6: 3.0
7: 3.5
8: 4.5
9: 5.5
10: 7.0
11: 7.5
12: 8.0
13: 9.0
14: 9.5
15: 10.0
16: 10.5
17: 11.0
18: 11.5
19: 12.0
20: 13.5SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
I'm with Fred. The more I think I know what's going on, the less I understand. I'm having flashbacks to the military bases of my relative youth....
I interpret the first item as:
location (14,1) has a Z value of 6. (10,3) has a Z value of 7. etc... I have no idea what the x and y designations in the matrix are.
I interpret the first item as:
Row#
5| 5 9
4| 6 x
3| y 7 8
2| 4 z
1| 6
--------------------
Col#: 1 2
12345678901234567890location (14,1) has a Z value of 6. (10,3) has a Z value of 7. etc... I have no idea what the x and y designations in the matrix are.
ASKER
In the car ready to drive home from work let me answer the easy part first.
@Kent,
Your interpretation of that small sample problem is correct. The value of x is unknown but we sort of have an idea of what it might be intuitively. The position designated by X is close to two known values, 7 and 9. So from those two points, I might think that X should take on a z value of 8. I thought that was what you were trying to tell me. However the X is also a little further away from Z values of 5 and 6 which in a curved surface might pull down that initial estimate of 8 to maybe 7 plus or minus 0.5. I am simply looking for an algorithm that can take some known values and make a reasonable estimate.
HTH
@Kent,
Your interpretation of that small sample problem is correct. The value of x is unknown but we sort of have an idea of what it might be intuitively. The position designated by X is close to two known values, 7 and 9. So from those two points, I might think that X should take on a z value of 8. I thought that was what you were trying to tell me. However the X is also a little further away from Z values of 5 and 6 which in a curved surface might pull down that initial estimate of 8 to maybe 7 plus or minus 0.5. I am simply looking for an algorithm that can take some known values and make a reasonable estimate.
HTH
SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
ASKER
For the non-continuous case, then I take it that the little extra work you are talking about is forcing a uniform grid on the non-uniform data, and filling in the blanks with zeros. And, if the uniform grid doesn't fit nicely, then just move the data points to fit on the uniform grid. Does that sound like a wrap?
SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
It was my understanding that you were waiting for your internal customer or experts to return after the first of the year.
Has that happened?
Has that happened?
ASKER
He is swamped at the moment having been away for 3 weeks.
ASKER
A bit frustrating for me since the lead put this in the backburner and I won't be getting back to this subject possibly for a few months.
But the discussion has been useful; and I hope to do some experiments at home. Thanks again.
But the discussion has been useful; and I hope to do some experiments at home. Thanks again.
I'm a little confused at the wording. You're given a set of X,Y coordinates and a Z value for each XY pair? Does that mean you're really working in 3 dimensions and you're given X,Y,Z for each point but don't know the shape of the surface?
How many points are you given? Is a solution unique? Is the resulting surface "regular"? i.e. the edge of a uniform solid such as a sphere or cone?
I believe that I'd start by selecting up to 6 points. Those with the smallest and largest values along the 3 axis. Build up from there.
- Do any of the other points share a common X, Y, or Z coordinate with the 6 selected?
- Do any of the points seem like outliers?
- Are there multiple clusters of points?
Tricky problem!!!!!
Kent