C++ - 最快的双线性插值方法？

Question

C++ - 最快的双线性插值方法？

performancec++11profilingeigen

3

我希望加快我的C++双线性插值代码。

设置如下：从灰度图像img中，我想在位置cent提取一个矩形补丁pat，单位间距，无上/下采样。 由于cent通常不是整数，因此我必须对提取的补丁进行双线性插值。

图像img、提取的补丁pat和位置cent都存储为浮点数。补丁的大小为[2 * pad + 1]，其中pad是位置cent左右的填充量。

当前的解决方案如下：

void function(Eigen::Matrix<float, Eigen::Dynamic, 1>* pat, 
              const float* img, 
              const Eigen::Vector2f* cent)
{

  Eigen::Vector4f we; // bilinear weight vector
  // ... [CROPPED: compute bilinear weights]

  float *pat_it = pat->data();
  for (y=cent[1]-pad; y <= cent[1]+pad; ++y)    
  {
    int postmp_a = y        * image_width;
    int postmp_b = (y-1)    * image_width;

    for (x=cent[0]-pad; x <= cent[0]+pad; ++x, ++pat_it)    
    {

          (*pat_it)     = we[0] * img[ x    +  postmp_a] +  
                          we[1] * img[x-1   +  postmp_a] +
                          we[2] * img[ x    +  postmp_b] +
                          we[3] * img[x-1   +  postmp_b]; 
    }
  }
}

这个函数还有没有更快的方法？在实时信号处理管道中，该函数将被调用数百万次。没有内存限制。
也许有特定于Eigen的函数吗？
由于这是代码中最关键的瓶颈，我也愿意考虑将代码移植到不同的编程语言/架构（汇编，CUDA等）。您对此有何想法/提示？
更普遍地说，您如何系统地进行分析以进行性能分析？

一些细节：该代码使用“-Ofast -std=c ++ 11”进行编译，并已使用OpenMP并行运行。图像大小为约1000x1200像素，pad之间的距离为5-10像素。

编辑

通过直接使用指向4个相应图像位置的指针，我已成功获得了约6％的加速。

...
for (x=cent[0]-pad; x <= cent[0]+pad; ++x,++pat_it,
     ++img_a,++img_b,++img_c,++img_d)    
{

      (*pat_it)   = we[0] * (*img_a) +  
                    we[1] * (*img_b) +
                    we[2] * (*img_c) +
                    we[3] * (*img_d); 
}
...

- user834985

如果您想使用CUDA，那么http://devblogs.nvidia.com/parallelforall/lerp-faster-cuda/可能会有所帮助。 - Jez

1

仅仅看它，那个内部循环迫切需要使用指针和展开循环，我肯定不会指望编译器的优化器来想出这一点。唯一一个分析工具能告诉你的是是否还有其他地方可以找到加速。 - Mike Dunlavey

1

在将其移植到CUDA之前，我建议使用SIMD指令集重写内部循环。这是x86架构，对吗？但是，如果您可以或需要并行处理多个，则CUDA可能是更好的选择。 - ChocoBilly

你的时间安排是什么，你想要或需要什么样的时间安排？ - Avi Ginsburg

@Mike Dunlavey：由于管道的重大变化，我可以在编译时知道pad和image_width。我模拟了这个过程，并将运行时间从0.19微秒减少到了0.165。这似乎是值得的。如果您将您的评论提升为答案，并概述您将如何编写它，我将接受这个答案。 - user834985

显示剩余5条评论

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Avi Ginsburg · Accepted Answer

你可以尝试使用Eigen来简化一些内容，例如：

void function(Eigen::VectorXf* pat, 
              const float* img, 
              const Eigen::Vector2f* cent)
{
...
  for (y=cent[1]-pad; y <= cent[1]+pad; ++y)    
  {
    ...
    Eigen::Map<Eigen::Array4f, 0, Eigen::OuterStride<>> mp(img + cent[0]-pad -1 +  postmp_b, 4, Eigen::OuterStride<>(image_width));
    for (x=cent[0]-pad; x <= cent[0]+pad; ++x, ++pat_it)    
    {
      new (&mp) Eigen::Map<Eigen::Array4f>(img + x-1 +  postmp_b, 4, Eigen::OuterStride<>(image_width));
      (*pat_it) = (mp * we.array()).sum();
...

注意：您可能需要重新排列we以匹配img元素的新顺序。

您可以尝试更好地完成任务，而不是创建一堆映射，而是创建一个单独的大型映射：

void function(Eigen::VectorXf* pat, 
              const float* img, 
              const Eigen::Vector2f* cent)
{
  ...
  Eigen::Map<Eigen::ArrayXXf, 0, Eigen::OuterStride<>> mp(img, image_width, image_height, Eigen::OuterStride<>(image_width));
  for (y=cent[1]-pad; y <= cent[1]+pad; ++y)    
  {
    ...
    for (x=cent[0]-pad; x <= cent[0]+pad; ++x, ++pat_it)    
    {
      (*pat_it) = (mp.block<2,2>(x,y) * we.array()).sum();
...

我没有测试过，你可能会做得更好。这也导致了以下免责声明：我没有测试过这个程序。这意味着你可能需要改变InnerStride和OuterStride，以及image_width和image_height等等。

如果这对你有帮助，我很想知道它能提高多少速度。