更快的双线性插值方法

Question

我正在用C 编写一个程序，以从一组投影的2D图像中重建一个3D对象，这是计算中最密集的部分，其中涉及通过双线性插值放大和转移每个图像。我目前有一对函数用于此任务；" blnsetup"定义了循环外的少数参数，然后"双线性"在循环中逐点应用插值：

（注意：'i'是一个1D阵列，包含图像数据的有序行）

//Pre-definition structure (in header)
struct blnData{
    float* X;
    float* Y;
    int* I;
    float X0;
    float Y0;
    float delX;
    float delY;
};
//Pre-definition function (outside the FOR loop)
extern inline blnData blnSetup(float* X, float* Y, int* I)
{
    blnData bln;
    //Create pointers to X, Y, and I vectors
    bln.X = X;
    bln.Y = Y;
    bln.I = I;
    //Store offset and step values for X and Y
    bln.X0 = X[0];
    bln.delX = X[1] - X[0];
    bln.Y0 = Y[0];
    bln.delY = Y[1] - Y[0];
    return bln;
}
//Main interpolation function (inside the FOR loop)
extern inline float bilinear(float x, float y, blnData bln)
{
    float Ixy;
    //Return -1 if the target point is outside the image matrix
    if (x < bln.X[0] || x > bln.X[-1] || y < bln.Y[0] || y > bln.Y[-1])
        Ixy = 0;
    //Otherwise, apply bilinear interpolation
    else
    {
        //Define known image width
        int W = 200;
        //Find nearest indices for interpolation
        int i = floor((x - bln.X0) / bln.delX);
        int j = floor((y - bln.Y0) / bln.delY);
        //Interpolate I at (xi, yj)
        Ixy = 1 / ((bln.X[i + 1] - bln.X[i])*(bln.Y[j + 1] - bln.Y[j])) *
            (
            bln.I[W*j + i] * (bln.X[i + 1] - x) * (bln.Y[j + 1] - y) +
            bln.I[W*j + i + 1] * (x - bln.X[i]) * (bln.Y[j + 1] - y) +
            bln.I[W*(j + 1) + i] * (bln.X[i + 1] - x) * (y - bln.Y[j]) +
            bln.I[W*(j + 1) + i + 1] * (x - bln.X[i]) * (y - bln.Y[j])
            );
    }
    return Ixy;
}

编辑：函数调用在下面。'Flat.imgdata'是包含输入映像数据的std ::向量，'proj.imgdata'是一个std :: vector，其中包含转换的图像。

int Xs = flat.dim[0];
int Ys = flat.dim[1];
int* Iarr = flat.imgdata.data();
float II, x, y;
bln = blnSetup(X, Y, Iarr);
for (int j = 0; j < flat.imgdata.size(); j++)
{
    x = 1.2*X[j % Xs];
    y = 1.2*Y[j / Xs];
    II = bilinear(x, y, bln);
    proj.imgdata[j] = (int)II;
}

自从我开始优化以来，我能够通过从std ::矢量转换为插值功能中的C数组来减少〜50x（！），另外2倍左右，通过清理冗余计算/typecastrations/等等，但是假设o（n）是n是处理过的像素的总数，则完整的重建（〜7E10像素）仍应花40分钟左右 - 比我的目标更长的数量级。p>根据Visual Studio的性能分析器，插值函数调用（" II =双线性（x，y，bln）;"）毫不奇怪地仍然是我的大部分计算负载。我找不到快速多次插值的任何线性代数方法，所以我的问题是：这基本上是与我的代码所获得的那样快，没有在任务中应用更多或更快的CPU？还是有其他方法可能会加快速度？

P.S。我也只在C 中编码大约一个月，因此请随时指出我可能会犯的任何初学者错误。

Answer 1

我写了一个很长的答案，建议查看opencv（opencv.org）或使用halide（http://halide-lang.org/），并进入图像翘曲的方式优化，但我认为较短的答案可能会更好。如果您真的只是在扩展和翻译整个图像，那么OpenCV具有代码可以做到这一点，我们也有一个示例可以在Halide中进行调整（https://github.com/halide/halide/halide/halide/blob/blob/master/master/apps/resize/resize/resize/Resize/Resize.cpp）。

如果您确实有一种算法需要使用浮点坐标来索引图像，该计算无法将其转换为整数坐标上适度简单函数，那么您真的希望在一个上使用过滤的纹理采样GPU。在CPU上进行优化的大多数技术都依赖于在算法中利用一些常规的访问模式，并删除浮点以从地址中进行整数转换。（为了调整大小，一个使用两个整数变量，一个变量索引图像的像素坐标，另一个是坐标的分数部分，并且会索引重量的核。在CPU上。OPENCV确实提供了相当普遍的重新映射支持，但可能并不是那么快。

可能适用的两个优化正在尝试将边界条件移出循环，并使用两个通过方法将水平和垂直尺寸分开处理。后者可能会或可能不会获胜，如果图像非常大，则需要铺平数据以适合缓存。通常，瓷砖对于大图像非常重要，但尚不清楚这是这里的第一阶性能问题，并且根据输入中的值，缓存行为可能不够规律。

Answer 2

"矢量50x比数组慢"。那是您处于调试模式的死赠品，其中vector::operator[]没有被嵌入。仅通过切换到发布模式，您可能会获得必要的速度，还有更多。

作为奖励，vector具有.back()方法，因此您可以正确替换该[-1]。指针到阵列的开始不包含数组大小，因此您找不到那样的阵列的背面。