通过任意因子调整一维向量大小（重新缩放）的最快方法

Question

我有以下代码，它以与调整图像大小类似的方式使用最近邻插值调整一维向量的大小。另一个术语是重采样，但是这些术语似乎有很多混淆（重采样也是统计中的一种技术），所以我更喜欢描述性更好。

目前代码如下所示，我需要对其进行优化：

inline void resizeNearestNeighbor(const int16_t* current, uint32_t currentSize, int16_t* out, uint32_t newSize, uint32_t offset = 0u)
{
    if(currentSize == newSize)
    {
        return;
    }

    const float scaleFactor = static_cast<float>(currentSize) / static_cast<float>(newSize);
    for(uint32_t outIdx = 0; outIdx<newSize; ++outIdx)
    {
        const int currentIdx = static_cast<uint32_t>(outIdx * scaleFactor);
        out[outIdx] = current[(currentIdx + offset)%currentSize];
    }
}

这当然效率不高，因为通过向下转换获取浮点数的整数部分的操作非常昂贵，而且我认为在这种情况下它无法利用矢量化的任何好处。该平台是 Cortex M7，因此，如果您熟悉该平台上的任何矢量化技术，也将非常有帮助。

这段代码的用例是一种声音效果，它允许平滑地改变延迟线的长度（因此额外的偏移参数，因为它是一个环形缓冲区）。能够平滑地改变延迟线的长度听起来就像在磁带录音机中放慢或加快播放速度，只是它处于循环中。没有这种缩放，就会有很多点击噪音和伪影。目前，硬件与所有 DSP 和此之上的代码作斗争，它无法实时重新缩放长延迟线。

Answer 1

如果您查看 currentIdx，您会注意到每次 outIdx 递增 1 时它递增 scaleFactor。因此，您可以将 outIdx * scaleFactor 替换为 currentIdx += scaleFactor.

您会将 currentIdx 初始化为 offset，因此它也会从循环中提升。

%currentSize 也是一项昂贵的操作，而且似乎只存在于 non-zero 偏移情况下。您可能希望以不同的方式对待它，并将循环分成两个循环（before/after wrap-around 点）。

Answer 2

由于 Cortex-M 系列非常有限（即使 M7 中的浮点数也是可选的），我估计一个合理的 speed-up 来自使用 Bresenham 的中点线绘制算法。

此算法总是根据误差项的符号推进 N 或 N+1 个元素。模数不需要全长除法：计算 currentIdx += N + (delta < 0); if (currentIdx >= currentSize) currentIdx -= currentSize;

就足够了

也可以通过if (currentIdx + 64 * (N+1) < currentSize)的形式进行“试分”，保证接下来的64个元素不需要模归约。 M7 有一个乘法单元，但通过移位乘法仍然可能更快 micro-optimisation.

画线的Bresenham's algorithm形式为

plotLine(x0, y0, x1, y1)
   dx = x1 - x0
   dy = y1 - y0
   D = 2*dy - dx
   y = y0

   for x from x0 to x1
       plot(x,y)
       if D > 0
           y = y + 1
           D = D - 2*dx
       end if
       D = D + 2*dy

您的应用程序没有 x0,x1,y0,y1，而是直接有 dy = input_size、dx = output_size.

resample(dx, dy)
   N = dy/dx
   dy = dy % dx
   D = 2*dy - dx;
   y = offset;
   for x from 0 to dx-1
       out[x] = in[y]
       y += N
       if D > 0
          y = y + 1
          D = D - 2*dx
       end if
       D = D + 2*dy
       if (y >= currentSize)
           y -= currentSize

将 y 推进 N>0 步的关键修改是 dy = dy % dx 以获得正确的错误计算。

也可以使用精度稍低的定点 DDA 算法

int scale = 65536 * newSize / currentSize;
int y = offset << 16;
for (int x = 0; x < newSize; x++) {
    out[x] = in[y >> 16];
    y += scale;
    if (y >= (currentSize << 16))
        y -= (currentSize << 16);
}

通过任意因子调整一维向量大小（重新缩放）的最快方法

Fastest way of resizing (rescaling) a 1D vector by an arbitrary factor

c++

arm

signal-processing

cortex-m