Bicubic 2d interpolation on an unregular grid

advanced
#1

i moved this http://alaska-kamtchatka.blogspot.ca/2012/06/2d-interpolation-part-4-argb.html great processing code to OF to do 2d bicubic interpolation.

here is the code:

it outputs an image like this when clicking the mouse a few times.

but it needs a regular grid of color data to interpolate.

does anyone know how to do this kind of 2d interpolation of 1d data (color) in an unregular grid. in other words at a random x/y location i want to add a new color and have the interpolation adjust accordingly.

thanks for any help.

#2

Hello,
I did similar things last year, the purpose was to interpolate randomly scattered anemometer’s value. The basic idea is TIN (Triangulated Irregular Network).
So

  • triangulate each xy position
  • divide it’s member side
  • then make contour line to get interpolated value
    it is difficult to explain the code but there is repo
    https://github.com/Akira-Hayasaka/InterpScatterdVectorField
    The app is on oF084, depends on ofxDelaunay & ofxMSACore & ofxMSAInterpolator.

scrn.png4064Ă—768 610 KB

Hope this helps.

1 Like
#3

will definitely take a look at this.

i also wonder if @elliotwoods addon https://github.com/elliotwoods/ofxPolyfit can be used for something similar.

i found this interesting thread about Scattered Data Interpolation, which ideally what i would need. Collect random points on a grid, give them a Z value that represents for example a temperature value and have the rest of the data be interpolated.


1 Like
#4

hey all
yes this type of usage is exactly suited to ofxPolyFit

  1. Initialise a training dataset (in this case input is 2D, output is 1D) pfitDataSetf
  2. Initialise a polynomial fit (2D input, 1D output, bicubic would be order = 3) ofxPolyFit
  3. Fill your dataset with your points
  4. Perform correlate on your ofxPolyFit
  5. Use that correlation to evaluate new 1D outputs given 2D inputs (this can be performed on a grid of 2D points if you want to create a height graph like above)
#5

thanks so much.

you says

polynomial fit (2D input, 1D output, bicubic would be order = 3) ofxPolyFit

but init asks for 4 values. i guess i am missing the order info?
///allocate local data ofxPolyFit
void init(int order, int dimensionsIn, int dimensionsOut, pfitBasisType basisType = BASIS_SHAPE_TRIANGLE);

thx

#6

ok i made some progress.

i am able to pass 2d points at a 1d value, evaluate and get data back.
the data i get back does not seem to make much sense if the input data is not even.

@elliotwoods it would be so great if you could take a quick look. if i get this to work in the next couple of days than things would become so much more interesting.
here my code:

or the full project:


thanks,
stephan.

#7

hey Stephan!

I tried out your demo (thanks for putting that together)
it seems to work for me fine. For example:

Pasted image1716Ă—732 228 KB

You’re doing a 3rd order fit (i.e. a cubic fit)
But your data input is random
So you’re trying to fit a curve surface which is only defined by 10 numbers (triangular bases, 3rd order, 2 inputs) to 25 random points. It just won’t be a good fit in that case.

If your points follow a smooth curve like in the image you posted before, then the fit will follow accurately.

You might be looking for something more like a B-Spline mesh which makes itself more complicated as you add more control points. A polyfit is more about finding a global pattern (which then can be defined simply mathematically).

#8

@elliotwoods great thanks for that.

i thought that might be the case, that my random values are the reason for the non-matching output.

i am planning to fit pan+tilt angles for an axis PTZ camera to x/y locations seen by a wide angle USB camera.
so, i think the relation between x/y and angles will be less random and nPolyfit will give me better results.

next step collect this data and see. :smile:

#9

ah ok. yes then this should be a pretty good approximation
really interested to see how it goes, i’m really interested in using PTZ cameras as high res camera devices

as long as your training data is pretty good, then you’ll also be able to up the order of the polynomial fit (e.g. 4th order)

for Lit Tree, I did a 4D input -> 3D output triangular basis polyfit with ofxPolyfit, to create a stereo (2 points in 2D space of 2 cameras) to 3D point in world space, which worked pretty well.

If you need to go for a better fit, you’ll need to use something like ofxNonLinearFit. You can see how I use ofxNonLinearFit to fit the pan-tilt values of a moving head to 3D points in space here : https://github.com/elliotwoods/ofxRulr/blob/master/Nodes/src/ofxRulr/Nodes/Procedure/Calibrate/MovingHeadToWorld.cpp

best of luck! I hope this helps

#10

about this part of your reply:

you mean i can get pan and tilt as outputs from the same nPolyfit?
i thought i will have to do 2 separate nPolyfits one for x/y input and pan output and and other one for x/y input and tilt output.

it sounds like your ofxNonLinearFit code already does what i am planning todo, only that i am feeding it 2d data while you are feeding it 3d data. cool. will have to poke around it.

#11

ok. now that i have real life data the pan and tilt angles seem to give me better nPolyfit results.

i am noticing that sometimes no fitting is being found or performed. even if i do not change the code, a restart of the app can result in proper fitting values or no fitting at all.

next test is trying the 4th order thing you mentioned; i.e. pan and tilt angles as a 2d output. ?

Screen Shot 2015-10-16 at 8.02.28 PM.png2563Ă—1435 30.4 KB

Screen Shot 2015-10-16 at 8.01.50 PM.png2560Ă—1444 33.1 KB

#12

Have only skimmed over the thread, for the triangulation part look at the delaunay alrorithm:

There are definitely implementations in CGAL and PCL
http://www.cgal.org/
http://www.pointclouds.org/

For the scattered data approximation part, you might have a look into RBF interpolation, that works well even for very sparse / clustered data:


Time to get some breakfast…

Random shape gradient
#13

interesting. sounds like some kind of bad initialization in the code (i.e. likely in the addon not your code), if it’s returning different fits each time.

3rd order = using terms in x^3, x^2, x, y^3, y^2, y and combinations of these
4th order = using terms in x^4, x^3, x^2, x, y^4, y^3, y^2, y and combinations of these

(i.e. it doesn’t change the dimensionality of the inputs or outputs, but changes how complex the model is which goes between the inputs and outputs)

if you just call fit multiple times in the same session what happens?

#14

if i just call this while the code is running not thing happens

  polynomial_fit_bicubic.correlate(training_dataSet);

if i re-initialsie everything again a couple of times it crashes. see attached screenshot

void ofApp::initialiseData(){

//2d x/y points input and 2d pan/tilt values output
training_dataSet.init(2, 2, referencePointSize);

//2d+2d makes a 4th order fit
polynomial_fit_bicubic.init(4, 2, 2,BASIS_SHAPE_TRIANGLE);

//prepare source data arrays
DataType *my_p = training_dataSet.getInput();
DataType *my_Z = training_dataSet.getOutput();

int panList_size = (sizeof(panList)/sizeof(*panList));
int tiltList_size = (sizeof(tiltList)/sizeof(*tiltList));

//fill source data arrays
for(int i=0; i<tiltList_size/3; i++){
    my_p[i*2] = (int)tiltList[i*3+0];
    my_p[i*2+1] = (int)tiltList[i*3+1];
    
    my_Z[i*2] = panList[i*3+2];
    my_Z[i*2+1] = tiltList[i*3+2];
}
polynomial_fit_bicubic.correlate(training_dataSet);

}

Screen Shot 2015-10-18 at 8.04.08 AM.png2496Ă—1570 386 KB

my workaround so far is to get one good fit and then generate a look-up-table.
here is the latest code: https://github.com/antimodular/ofxPolyFit-scattered