3
$\begingroup$

I have a grid of values, sampled at certain locations. I'd like to translate grid by some offset and resample it. The questions is: what should be the resampling and interpolation formulas such that interpolation at the same location would be consistent between the original and the translated grid?

Here is an example to show that linear interpolation wouldn't do:

Suppose that the original grid is 1D, sampled at locations 1, 5, 10, 15, with the corresponding values 0, 1, 1, 0 at those locations.

Now I translate the grid by offset 3 and linearly interpolate, so that the grid is now sampled at locations 3, 8, 13, 18, with the corresponding values 0.6, 1, 1, 0.4.

Now interpolate the value at location 7. Linear interpolation according to the original grid would yield value 1; linear interpolation according to the translated grid would yield the value 0.92.

I'd like to minimize such inconsistencies by replacing linear interpolation with another form of sampling.

EDIT: an explanation why shifting of the grid is necessary for my application.

The application has to do with semiconductor manufacturing. Quite often one has to print a small 2D pattern in numerous locations across the microchip. The intensity of pixels of the small 2D pattern are accurately computed; that is the "original grid". Then one translates many times the small pattern by certain offsets and prints it on the chip; those are the "translated grids".

Because of the enormous size of the chip in comparison to feature sizes, as well as because of finite resolution of equipment, the grid cannot be sampled very frequently, so the step $h$ between grid points has to be very much finite; it's completely invalid to make assumptions such as $h\to 0$.

In order to predict the quality of the chip one needs to estimate intensity at random points that are not aligned with the grid; that is the "interpolation". Thus the question is about the best method to evaluate intensity on the chip ("interpolation using translated grid") by analyzing the pattern to be shifted and printed ("interpolation using original grid").

I'm sure though that this particular application is very far from being the only one where the problem described above has practical implications...

$\endgroup$
1
$\begingroup$

Consider you have sampled a continues twice differentiable function $f(x)$ (with bounded second derivative) on an uniform grid $x_i=x_0+i h, h=\frac{|x_0-x_n|}n$. Now you do a piecewise linear interpolation for a $y_0\in[x_i,x_{i+1}]$, which is you draw a line $\ell(x)$ between $f(x_i)$ and $f(x_{i+1})$ and take a value $\ell(y_0)$ as an approximation of $f(y_0)$. The error will be $E=|\ell(y_0)-f(y_0)|\le |f''(c)|\frac{h^2}4, c\in[x_i,x_{i+1}]$.

Now you take $\ell_0(y_0)$, $y_0\in[x_i,x_{i+1}]$ and $\ell_1(y_1)$, $y_1\in[x_{i+1},x_{i+2}]$ and draw a line $\tilde\ell(x)$ between them to estimate $f(z), z\in[y_0,y_1]$. $$E =|\tilde\ell(z)-f(z)|]= \left|\frac{y_0-z}{y_0-y_1}\ell_1(y_1)+\frac{y_1-z}{y_1-y_0}\ell_0(y_0)-f(z)\right|= \left|\frac{y_0-z}{y_0-y_1}(f(y_1)+|f''(c)|\frac{h^2}4)+\frac{y_1-z}{y_1-y_0}(f(y_0)+|f''(d)|\frac{h^2}4)-f(z)\right|\le \left|\frac{y_0-z}{y_0-y_1}f(y_1)+\frac{y_1-z}{y_1-y_0}f(y_0)-f(z)\right|+\left|\frac{y_0-z}{y_0-y_1}|f''(c)|+\frac{y_1-z}{y_1-y_0}|f''(d)|\right|\frac{h^2}4 \le |f''(e)|\frac{h^2}4+\frac{|f''(c)|+|f''(d)|}{2}\frac{h^2}4 $$ Not too bad (given all assumptions above).

Well, if you have many points and your shift is not too big, and do not extrapolate, i.e. drop points exceeding the original grid (unless it is very close) you should be fine. Although, I would consider cubic spline. In addition, consider Chebyshev grid points.

ps: Can you explain why do you need that shift?

$\endgroup$
  • $\begingroup$ Added an explanation why the shift needed to the original question. $\endgroup$ – Michael Oct 30 '15 at 16:56
  • $\begingroup$ after reading about your application I think, that you don't have to interpolate after the shift. you have $(x,y,f(x,y))$ and you shift to $(x+h,y+h),f(x+h,y+h))$ but you should have $f(x,y)=f(x+h,y+h)$. Anyway, linear interpolation isn't the simplest and fastest, but not the best you can do. $\endgroup$ – Michael Medvinsky Oct 31 '15 at 4:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.