反转实值索引网格

OpenCV remap()使用实值索引网格使用双线性插值从图像中采样值网格,并将样本网格作为新图像返回.

确切地说,让:

A = an image 
X = a grid of real-valued X coords into the image. 
Y = a grid of real-valued Y coords into the image.
B = remap(A, X, Y)

那么对于所有像素坐标i,j,

B[i, j] = A(X[i, j], Y[i, j]) 

其中圆括号A(x, y)表示使用双线性插值来求解使用浮点数x和和的图像A的像素值y.

我的问题是:给定索引网格X,Y我如何生成"逆网格" X^-1,Y^-1这样:

X(X^-1[i, j], Y^-1[i, j]) = i
Y(X^-1[i, j], Y^-1[i, j]) = j

和

X^-1(X[i, j], Y[i, j]) = i
Y^-1(X[i, j], Y[i, j]) = j

对于所有整数像素坐标i, j？

FWIW,图像和索引图X和Y是相同的形状.然而,索引图X和Y没有先验结构.例如,它们不一定是仿射或刚性变换.它们甚至可能是不可逆的,例如,如果X, Y将多个像素映射A到B中的相同精确像素坐标.我正在寻找一种方法的想法,如果存在,将找到合理的逆映射.

解决方案不必是基于OpenCV的,因为我没有使用OpenCV,而是另一个具有remap()实现的库.虽然欢迎任何建议,但我特别热衷于"数学上正确"的事情,即如果我的地图M完全可逆,那么该方法应该在机器精度的一小部分范围内找到完美的反转.

好吧，我只需要自己解决此重新映射反转问题，然后我将概述解决方案。

给定X，Y对于remap()执行以下操作的函数：

B[i, j] = A(X[i, j], Y[i, j])   

我计算了Xinv，Yinv该remap()函数可以使用来反转过程：

A[x, y] = B(Xinv[x,y],Yinv[x,y])

首先，我为2D点集建立一个KD树，{(X[i,j],Y[i,j]}这样我就可以有效地找到N给定点的最近邻居，而(x,y).我使用欧几里得距离作为距离度量。我在GitHub上为KD-Trees找到了一个很棒的C ++头文件库。

然后，我遍历网格中的所有(x,y)值，A并在我的点集中找到N = 5最近的邻居{(X[i_k,j_k],Y[i_k,j_k]) | k = 0 .. N-1}。

如果距离d_k == 0对于一些k则Xinv[x,y] = i_k和Yinv[x,y] = j_k，否则......

使用反距离权重（IDW）计算插值：

让体重w_k = 1 / pow(d_k, p) （我用p = 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)

请注意，如果B是W x H图像，则X和Y是W x H浮点数数组。如果A是w x h图像，则Xinv和Yinv是w x h浮点数数组。重要的是要与图像和地图的尺寸​​保持一致。

奇迹般有效！我的第一个版本尝试使用强行强制搜索，甚至从未等待完成。我切换到KD-Tree，然后开始获得合理的运行时间。如果有时间，我想将其添加到OpenCV中。

下面的第二张图像remap()用于消除第一张图像中的镜头畸变。第三幅图像是逆过程的结果。