MATLAB and Simulink resources for Arduino, LEGO, and Raspberry Pi

Learn moreOpportunities for recent engineering grads.

Apply Today
Asked by Jim Hokanson on 4 Oct 2012

I have a 3d set of evenly spaced points, at which I would like to evaluate some function. Evaluation of the function is costly. I am using a binary search to find the value of the function at each point, but my ability to bound the value (obviously?) impacts the speed in which I can find a sufficiently accurate answer. The function values are relatively smooth in my space, which means that I can try and bound the evaluation of a particular value by using values in the local neighborhood. Any suggestions?

For example I might have the following values, spaced evenly as such (in 2d for simplicity):

1 2 3 4 5 6 7 8 x

What function could I use to evaluate x?

Alternatively I might have

1 2 3 4 4 5 6 7 8 9 x

Which is similar to above, but just goes to point out that I might not always be dealing with a corner.

Thanks! Jim

*No products are associated with this question.*

Answer by Image Analyst on 5 Oct 2012

Edited by Image Analyst on 5 Oct 2012

Well in 1D, like your example, I'd use **sgolay**() - the Savitzky Golay filter. But in 3D, I don't know.

So to make sure I understand the situation let me try to visualize an example. Let's say you have a 3D volumetric array, like a CT or MRI image of a skull. You have an X, a Y, and a Z coordinate and the array at that location has a value. But let's say you had only half a skull and you want to **extrapolate based on the curvature of the existing half skull to complete the skull in 3D**. So you'd have all the x,y,z coordinates and values for all those coordinates. Maybe it's not a medical image but it's *some sort* of 3D array. So is that basically what you're wanting to do?

Jim Hokanson on 5 Oct 2012

In this case I am running a neural model and trying to determine threshold in a 3d space. At any given new point I am trying to find threshold, and the closer I am to the answer when I start, the less halving I need to do.

Image Analyst on 5 Oct 2012

What are you starting with? Do you have a 3D array of numbers, or an analytical formula F(x,y,z)? Or both? If you have the function, just plug in the extrapolated coordinates. If you have an empirical, experimentally measured numerical array but no underlying analytical formula then you basically have to make some kind of educated guess at what the values would be, or maybe first what the formula would be so you can then guess at the values.

Answer by Matt J on 5 Oct 2012

Edited by Matt J on 5 Oct 2012

If you're trying to grow the array by extrapolation, a linear algebraic cubic spline extrapolation approach is given below. It employs a couple of my FEX files

And now the code:

N=10; %array dimension;

%% In 1D

fakedata=(1:N).'; %to be extrapolated

spline_samples=[1 4 1]/6;

E=interpMatrix(spline_samples,'max',N+2); %extrapolation operator E(:,2)=E(:,1)+E(:,2); E(:,end-1)=E(:,end)+E(:,end-1); E(:,[1,end])=[];

F=E(2:end-1,:); %fitting operator

extrapolated1D=E*(F\fakedata),

%% Generalization to 3D

fakedata=rand(N,N,N);

F3=KronProd({F},[1 1 1]); E3=KronProd({E},[1 1 1]);

extrapolated3D=E3*(F3\fakedata);

## 2 Comments

Direct link to this comment:http://www.mathworks.com/matlabcentral/answers/49921#comment_103185

Wouldn't we have to study the specific form of your function in order to derive a valid bound for it?

Direct link to this comment:http://www.mathworks.com/matlabcentral/answers/49921#comment_103279

My question was more so aimed at existing, generic methods, for extrapolating in 3d, given some assumptions about smoothness. In 1d interp1 will extrapolate. In 2d, I can use the fit function from the curve fitting toolbox. I could also use interp2 but it wouldn't be able to take advantage of neighboring information such as is presented in my examples.

What about in 3d?