Well I just had to solve this remap inversion problem myself and I’ll outline my solution.
Given X
, Y
for the remap()
function that does the following:
B[i, j] = A(X[i, j], Y[i, j])
I computed Xinv
, Yinv
that can be used by the remap()
function to invert the process:
A[x, y] = B(Xinv[x,y],Yinv[x,y])
First I build a KD-Tree for the 2D point set {(X[i,j],Y[i,j]}
so I can efficiently find the N
nearest neighbors to a given point (x,y).
I use Euclidian distance for my distance metric. I found a great C++ header lib for KD-Trees on GitHub.
Then I loop thru all the (x,y)
values in A
‘s grid and find the N = 5
nearest neighbors {(X[i_k,j_k],Y[i_k,j_k]) | k = 0 .. N-1}
in my point set.
-
If distance
d_k == 0
for somek
thenXinv[x,y] = i_k
andYinv[x,y] = j_k
, otherwise… -
Use Inverse Distance Weighting (IDW) to compute an interpolated value:
- let weight
w_k = 1 / pow(d_k, p)
(I usep = 2
) Xinv[x,y] = (sum_k w_k * i_k)/(sum_k w_k)
Yinv[x,y] = (sum_k w_k * j_k)/(sum_k w_k)
- let weight
Note that if B
is a W x H
image then X
and Y
are W x H
arrays of floats. If A
is a w x h
image then Xinv
and Yinv
are w x h
arrays for floats. It is important that you are consistent with image and map sizing.
Works like a charm! My first version I tried brute forcing the search and I never even waited for it to finish. I switched to a KD-Tree then I started to get reasonable run times. I f I ever get time I would like to add this to OpenCV.
The second image below is use remap()
to remove the lens distortion from the first image. The third image is a result of inverting the process.