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

Image Analyst
on 5 Oct 2012

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);

Opportunities for recent engineering grads.

## 2 Comments

## Matt J (view profile)

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?

## Jim Hokanson (view profile)

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?