# pointwise cross-correlation, finding offset in same signals

Problem:

I want to find the correlation between two signals from point to point. That means that if they share y values then I want to know the x offset between them.

This is what I want in mathematical terms:
Given $$a(x)$$ and $$b(x) = a(x+c(x))$$, find $$c(x)$$.

$$c(x)$$ is always positive
$$c(x)$$ is always below some constant k which is known

Why I want to solve this:

For stereo photogrammetry, meaning that you have two cameras pointing in the same direction and you find depth. Given the pixel offset for each individual pixel in each row I can find the depth.

My first idea:

Only looking at a row of pixels the problem becomes 1-D, let's call the x position of each pixel the x value and the magnitude of each pixel in greyscale the y value.

We could try to approximate our pixels as a polynomial, like $$y=ax^2+bx+c$$.

Subtracting one polynomial from another polynomial won't really help us, however if we rotate the polynomial 90 degrees, $$x = ay^2+by+c$$ then we could approximate c(x) by a simple subtraction.

Problems with my solution:

• The order of the polynomial would have to be insane, in the hundreds, this isn't really feasible as the numbers will become ridiculously huge.
• Multiple x values corresponds to the same y value, in order to get rid of this we would have to split everything up into blocks every time the derivative crosses 0. Splitting the wave into blocks would however allow us to reduce the degree of the polynomial to something more sane.
• All points will be defined, so there are no undefined points which is good, however in real life parts of one wave would be out of reach for the other wave meaning that it would be undefined. This is more of an observation.

Am I trying to re-invent the wheel? Is there some word I should look up or some transform that exists that does exactly what I want?

I feel like it's cross-correlation but for each individual element, surely this must exist already.

• Do some searching on depth-map and stereo image disparity. – Max Apr 7 at 6:21