Алгоритмы эффективного "масштабирования" или "изменения размера" массива чисел (повторная выборка аудио)

Question

Выполнение обработки звука (хотя это может быть и обработка изображений) У меня есть одномерный массив чисел. (Это целые 16-разрядные числа со знаком, представляющие аудиосэмплы, этот вопрос может в равной степени относиться к числам с плавающей запятой или целым числам разных размеров.)

Чтобы согласовать звук с разными частотами (например, смешать сэмпл 44,1 кГц с сэмплом 22 кГц), мне нужно либо растянуть, либо сжать массив значений для соответствия определенной длине.

Половина массива проста: отбросьте каждый второй образец.

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

Удвоение ширины массива немного менее просто: удвойте каждую запись на месте (или при необходимости выполните некоторую интерполяцию между соседними «реальными» выборками).

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

Мне нужен эффективный, простой алгоритм, который обрабатывает любой коэффициент масштабирования и (в идеале) дополнительно поддерживает выполнение интерполяции того или иного вида в процессе.

В моем случае я использую массивы Ruby, но я с радостью отвечу на большинство языков и псевдокодов.

Answer 1

Математические функции массива / матрицы, которые вы ищете, обычно находятся в библиотеках "Scientific Computing". NArray может быть хорошим началом для Ruby.

Answer 2

Эта операция называется повышающей дискретизацией (при увеличении частоты дискретизации) или понижающей дискретизацией (когда снижается та же частота).Перед понижающей дискретизацией (или после повышающей дискретизации) необходимо применить фильтр сглаживания (или антиизображение), чтобы предотвратить искажение вашего аудиосигнала.Эти фильтры обычно реализуются как IIR фильтры.

Предлагаемые шаги для решения вашей проблемы:

1. Поиск / запись кода Ruby для реализации фильтра БИХ.
2. Найти / спроектировать коэффициенты БИХ-фильтра для реализации соответствующего фильтра (сглаживания / изображения)

Нетрудно реализовать БИХ-фильтр;Выход фильтра всегда является линейной комбинацией предыдущих N входов и предыдущих M выходов.Если есть библиотека Ruby DSP (цифровая обработка сигналов), она определенно будет иметь это.

Проектирование коэффициентов фильтра действительно связано с некоторыми тонкостями.

Понижающая дискретизация иногда называется децимацией и реализуется внекоторые языки как функция, называемая "decimate".Например, функция Matlab decimate выполняет как сглаживание, так и понижающую дискретизацию.Погуглив вокруг, я нашел реализацию Python;может быть, вы найдете реализацию Ruby.

Answer 3

Это то, что я бросил вместе за несколько минут, когда уходил с работы, а затем воссоздал после бокала вина после обеда:

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]]]

each_cons хорошо, потому что он проходит через массив, возвращая его фрагменты, что казалось полезным способом построения средних значений.

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

---

EDIT:

Мне нравится это лучше:

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]

Answer 4

В следующем проекте существует дешифрующий, интерполяционный, смешивающий FIR-фильтр вместе с алгоритмом Parks-McClellan для генерации отводов.

https://github.com/ham21/radio

Я не знаю ничего другого в Ruby, который будет выполнять запрошенные вами аудио функции.

Answer 5

Несмотря на то, что я нашел этот вопрос на год позже, я хочу в! Вот код Objective C, который я использовал для решения этой проблемы в Hexaphone .

Я использую его для предварительного расчета 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;

}

Answer 6

Для полноты вот функция сжатия / растяжения, которую я написал для Ruby Arrays в качестве первого прохода.Он не выполняет никакой интерполяции, просто удаляя или повторяя значения.Но это просто:)

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]

Answer 7

Обычный метод для достижения этой цели: фильтр All-Pass.

Вы создаете новые выборки с нулями, когда вы хотите интерполировать значения выборок, и с исходным неизмененным значением выборки, когдаконечно только в тех индексах, где у вас есть точное значение выборки из вашего источника).

Вы получите что-то вроде ...... | ...... | ...... | ..... | ..... | .... с.быть ноль и |некоторые из ваших исходных значений образцов.

Вы отправляете этот новый поток в фильтр All-Pass.Выход этого фильтра является интерполированной версией вашего потока выборки на новой частоте.Это результирующий звук, который вы хотите.

Преимущество этого метода в том, что он не вносит артефакты сглаживания в ваш звук, он не добавляет шума.

Answer 8

Другими словами, вы хотите повторно сэмплировать аудиопотоки.

Ваш план обоснован, хотя удержание последнего сэмпла не очень хороший интерполятор.