有效地“缩放”或“调整大小”数字数组的算法（音频重采样）

Question

我在进行音频处理时（虽然也可以是图像处理），有一个一维的数字数组。（它们恰好是表示音频样本的16位带符号整数，但是这个问题同样适用于不同大小的浮点数或整数。）

为了匹配具有不同频率的音频（例如将44.1kHz样本与22kHz样本混合），我需要拉伸或压缩值的数组以满足特定长度。

将数组减半很简单：放弃每个其他样本。

[231, 8143, 16341, 2000, -9352, ...] => [231, 16341, -9352, ...]

将数组宽度加倍略微复杂：在原地将每个条目加倍（或选择在相邻的“真实”样本之间执行一些插值）。

[231, 8143, 16341, 2000, -9352, ...] => [231, 4187, 8143, 12242, 16341, ...]

我想要的是一个高效、简单的算法，可以处理任何缩放因子，并（理想情况下）支持在此过程中执行某种插值。

我的用例恰好是使用Ruby数组，但我也可以接受大多数任何语言或伪代码的答案。

- Phrogz

---

通常情况下，为了减少可能的混叠效应，您需要在丢弃采样之前低通滤波以对数组进行折半操作。 - lijie

Answer 1

你要寻找的数组/矩阵数学功能通常在“科学计算”库中找到。对于Ruby来说，NArray可能是一个不错的起点。

- Brad Mace

---

我本来想发表一个关于算法和库的讽刺性评论，但是当我真正看到NArray时，发现它确实有“reshape”，这可能正是我想要的。+1 强迫我更仔细地看它 :) - Phrogz

在Python中，似乎每个人都知道NumPy，并且很多东西都依赖于它。NArray在Ruby中就像一个黑暗的秘密。+1向更多人展示它。 - Jamison Dance

Answer 2

这是我在下班前匆忙做出来的东西，只花了几分钟时间，晚饭后喝完一杯葡萄酒后重新制作：

sample = [231, 8143, 16341, 2000, -9352]
new_sample = []
sample.zip([] * sample.size).each_cons(2) do |a,b|
  a[1] = (a[0] + b[0]).to_f / 2 # <-- simple average could be replaced with something smarter
  new_sample << a
end
new_sample.flatten!
new_sample[-1] = new_sample[-2]
new_sample # => [231, 4187.0, 8143, 12242.0, 16341, 9170.5, 2000, 2000]

我认为这是一个开始，但显然还没有完成，因为-9352没有传播到最终数组中。我没有费心将浮点数转换为整数；我觉得你知道如何做。 :-)

我想找到一种更好的方法来迭代each_cons。我宁愿使用map而不是each*，但这个方法也可以工作。

以下是循环迭代的内容：

asdf = sample.zip([] * sample.size).each_cons(2).to_a 
asdf # => [[[231, nil], [8143, nil]], [[8143, nil], [16341, nil]], [[16341, nil], [2000, nil]], [[2000, nil], [-9352, nil]]]

< p > each_cons 很不错，因为它可以遍历数组并返回它的片段，这似乎是一种构建平均数的有用方法。

[0,1,2,3].each_cons(2).to_a # => [[0, 1], [1, 2], [2, 3]]

---

编辑：

我更喜欢这个版本：

sample = [231, 8143, 16341, 2000, -9352]

samples = sample.zip([] * sample.size).each_cons(2).to_a 
new_sample = samples.map { |a,b|
  a[1] = (a[0] + b[0]).to_f / 2
  a
}.flatten
new_sample << sample[-1]
new_sample # => [231, 4187.0, 8143, 12242.0, 16341, 9170.5, 2000, -3676.0, -9352]

- the Tin Man

---

我非常喜欢使用each_cons进行插值的想法，谢谢！ - Phrogz

谢谢。我刚准备离开，看到了你的问题，想着怎样让数组翻倍并提供新值的插槽，然后 zip 和 each_cons 就浮现在脑海中。虽然我不太高兴坐在桌子前而不是回家，但如果这有所帮助，那就值得了。 :-) - the Tin Man

我希望它是一瓶红酒，也许是一瓶不错的西拉子。 - mu is too short

当时它是霞多丽葡萄酒，现在它会是西拉子葡萄酒。 :-) - the Tin Man

Answer 3

这个操作被称为上采样（当采样率增加时）或下采样（当采样率降低时）。在下采样（或上采样）之前，需要应用抗混叠（或抗图像）滤波器来防止音频信号的损坏。这些滤波器通常实现为IIR滤波器。

解决问题的建议步骤：

1. 查找/编写Ruby代码以实现IIR滤波器。
2. 查找/设计IIR滤波器系数以实现适当的抗（混叠/图像）滤波器。

实现IIR滤波器并不难；滤波器在所有时间的输出都是前N个输入和前M个输出的线性组合。如果有一个Ruby DSP（数字信号处理）库，它肯定会有这个功能。

设计滤波器系数确实涉及一些微妙的问题。

降采样有时被称为抽取，某些语言中实现为名为“decimate”的函数。例如，Matlab的decimate函数既执行抗混叠又进行降采样。我在网上搜索到了一个Python实现，也许你可以找到一个Ruby实现。

- nibot

---

libsamplerate 是一种带有抗混叠和插值的任意重采样比率的[开源]音频标准。我不知道你是否能在 Ruby 中找到它的绑定。 - Matthew Hall

Answer 4

为了完整起见，这是我为 Ruby 数组编写的压缩/拉伸函数的第一次尝试。它不执行任何插值操作，只是删除或重复值。但它很简单 :)

class Array
  def stretch( factor=1.0 )
    factor = factor.to_f
    Array.new (length*factor).ceil do |i|
      self[(i/factor).floor]
    end
  end
end

a = (0..9).to_a
p a
#=> [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

(0.2).step( 3.0, 0.2 ) do |factor|
  p a.stretch(factor)
end
#=> [0, 5]
#=> [0, 2, 5, 7]
#=> [0, 1, 3, 4, 6, 8, 9]
#=> [0, 1, 2, 3, 5, 6, 7, 8]
#=> [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
#=> [0, 0, 1, 2, 3, 4, 5, 5, 6, 7, 8, 9]
#=> [0, 0, 1, 2, 2, 3, 4, 4, 5, 6, 7, 7, 8, 9, 9]
#=> [0, 0, 1, 1, 2, 3, 3, 4, 5, 5, 6, 6, 7, 8, 8, 9]
#=> [0, 0, 1, 1, 2, 2, 3, 3, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9]
#=> [0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9]
#=> [0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9]
#=> [0, 0, 0, 1, 1, 2, 2, 2, 3, 3, 4, 4, 4, 5, 5, 6, 6, 7, 7, 7, 8, 8, 9, 9, 9]
#=> [0, 0, 0, 1, 1, 1, 2, 2, 3, 3, 3, 4, 4, 4, 5, 5, 6, 6, 6, 7, 7, 8, 8, 8, 9, 9, 9]
#=> [0, 0, 0, 1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4, 5, 5, 6, 6, 6, 7, 7, 7, 8, 8, 8, 9, 9, 9]
#=> [0, 0, 0, 0, 1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4, 5, 5, 5, 6, 6, 6, 7, 7, 7, 8, 8, 8, 9, 9, 9]

- Phrogz

Answer 5

虽然我发现这个问题已经晚了一年，但我还是想参与！以下是我在Hexaphone中用来解决这个问题的Objective-C代码。

我使用它来预先计算一个或多个样本的31个半音偏移量 - 分别对应键盘上31个音符中的每一个。这些样本旨在在按住键时不断循环播放。

#define kBytesPerFrame 2
-(SInt16*) createTransposedBufferFrom:(SInt16*)sourceBuffer sourceFrameCount:(UInt32)sourceFrameCount destFrameCount:(UInt32)destFrameCount {

    // half step up:  1.05946;
    // half step down: .94387
    Float32 frequencyMultiplier = (Float32) sourceFrameCount / (Float32) destFrameCount;

    SInt16 *destBuffer = malloc(destFrameCount * kBytesPerFrame);

    Float32 idxTarget; // the extrapolated, floating-point index for the target value
    UInt16 idxPrevNeighbor, idxNextNeighbor; // the indicies of the two "nearest neighbors" to the target value
    Float32 nextNeighborBias; // to what degree we should weight one neighbor over the other (out of 100%)
    Float32 prevNeighborBias; // 100% - nextNeighborBias;  included for readability - could just divide by next for a performance improvement

    // for each desired frame for the destination buffer:
    for(int idxDest=0; idxDest<destFrameCount; idxDest++) {

        idxTarget = idxDest * frequencyMultiplier;
        idxPrevNeighbor = floor(idxTarget);
        idxNextNeighbor = ceil(idxTarget);

        if(idxNextNeighbor >= sourceFrameCount) {
            // loop around - don't overflow!
            idxNextNeighbor = 0;
        }

        // if target index is [4.78], use [4] (prev) with a 22% weighting, and [5] (next) with a 78% weighting
        nextNeighborBias = idxTarget - idxPrevNeighbor;  
        prevNeighborBias = 1.0 - nextNeighborBias; 


        Float32 interpolatedValue = sourceBuffer[idxPrevNeighbor] * prevNeighborBias 
                                  + sourceBuffer[idxNextNeighbor] * nextNeighborBias;
        destBuffer[idxDest] = round(interpolatedValue); // convert to int, store

    } 

    return destBuffer;

}

- Glenn Barnett

Answer 6

在下面的项目中，有一个消减、插值、混合FIR滤波器以及Parks-McClellan算法用于生成滤波器系数。

https://github.com/ham21/radio

我不知道 Ruby 中还有什么可以执行您请求的音频功能。

- David Turnbull

Answer 7

换句话说，您想要重新采样音频流。

您的计划听起来不错，尽管保持在最后一个采样点不是一个很好的插值算法。

- ephemient

---

是的，那就是我想做的；我在标题中加入了“重新采样”一词以使其更清晰。我理解所涉及的概念。我要找的不仅仅是维基百科链接：实际算法、库、白皮书或（最好的）提供良好重新采样的个人经验建议。 - Phrogz

Answer 8

常用技术是使用全通滤波器来实现。

当你想要插值样本值时，创建新的样本并用零填充，当你知道原始未修改的样本值（当然只有在源数据中确切地找到该样本值时）时，使用原始样本值填充。

你会得到类似于......|......|......|.....|.....|.... 的东西，其中 . 代表零， | 代表某些原始样本值。

将这个新流发送到全通滤波器中。此滤波器的输出是您的新频率的样本流的插值版本。它是您想要的结果声音。

这种技术的优点是它不会在您的声音中引入混叠伪像，也不会添加噪音。

- Stephane Rolland

---

“全通滤波器”绝对是错误的术语。您需要将流通过一个“低通”滤波器。一个非平凡的“全通滤波器”会改变不同频率之间的相位（因为它不能做其他任何事情 - 它具有单位幅度响应），这几乎肯定不是所需的。实际上，您正在描述带限插值。 - lijie

“使用多相递归全通滤波器设计和实现高效的重采样滤波器”是一篇非常出色的文章，详细解释了这种技术。据我所知，这种技术至少在九十年代末期被应用于音乐数字信号处理领域（数字合成器）……” - Stephane Rolland

这项技术非常微妙，简单来说：新的流....|....|....|....是原始源的扭曲版本。峰值...|...包含极高的频率，远超过新采样频率的处理能力！！！因此，当通过数字全通滤波器（我坚持这一点）时，只会输出可能的频率，因为我们的数字全通滤波器是设计用于有限样本历史记录的......因此，产生的输出是平滑的重新采样声音。唯一需要付出的代价就是一些相位失真。 - Stephane Rolland

“远超过新采样频率所能处理的”这个说法是非常不准确的。我们总可以从采样信号中重建出一些带限信号（在奈奎斯特界限内）。如果说法是“超过原始采样频率所能处理的”，那么就可以接受。 - lijie