Применение преобразования Фурье для создания гитарного тюнера на Android. Часть 1 +14

- такой же как Forbes, только лучше.


В основе спектрального анализа звуковых данных лежит алгоритм, который носит название преобразование Фурье. При раскладывании исходного звукового сигнала на частотные составляющие, отдельные частоты называются гармониками. Основная гармоника определяет высоту звучания, а второстепенные гармоники определяют его тембр. Есть достаточно много мобильных приложений, которые используют преобразование Фурье для того, чтобы отобразить весь спектр частот (гармоник). Так же, есть мобильные приложения, которые служат для настройки гитар. Они работают по принципу: основная гармоника находится по самому высокому значению амплитуды в спектре. Такое утверждение не совсем верно, потому что основная гармоника определяется самой наименьшей из всех кратных этой гармонике, либо шагом между гармониками. Возникает необходимость найти способ, который позволит отобразить значение основной гармоники в спектре звукового сигнала.

В первой части статьи мы рассмотрим принцип работы дискретного преобразование Фурье, а также возможность записывать звуковые данные с Android устройства с помощью класса AudioRecord.

ДПФ, БПФ. Библиотека JTransforms.


Звуковые данные, записанные в виде импульсно-кодовой модуляции (PCM), показывают амплитуду звуковой волны в конкретный момент времени. В 19-м веке Жан Батист Фурье доказал, что любой периодический сигнал можно представить, как сумму бесконечного ряда простых синусоидальных сигналов. Из чего следует, что наш исходный звуковой сигнал, можно представить в виде суммы, упорядоченных по частоте, простых синусоидальных сигналов с собственными амплитудами. Тем самым перейти от одной зависимости (амплитуда-время) к другой (амплитуда-частота). Такое преобразование называется преобразованием Фурье.

Для вычисления преобразования Фурье на компьютерах ввели понятие дискретное преобразование Фурье (ДПФ), которое требует в качестве входа дискретную функцию.

Рассмотрим принцип работы дискретного преобразования Фурье в среде программирования Java. Для начала, опишем некоторую функцию, которая будет представлять сумму двух гармоник (косинусов) с частотами 100 Гц и 880 Гц соответственно.

private double someFun(int index, int sampleRate) {
    final int amplitudeOfFirstHarmonic = 15;
    final int amplitudeOfSecondHarmonic = 1;
    final int frequencyOfFirstHarmonic = 100;
    final int frequencyOfSecondHarmonic = 880;

    return amplitudeOfFirstHarmonic * Math.cos((frequencyOfFirstHarmonic * 2 * Math.PI  * index ) / sampleRate)
            + amplitudeOfSecondHarmonic *Math.cos((frequencyOfSecondHarmonic * 2 * Math.PI  * index) / sampleRate);
}

В качестве частоты дискретизации возьмём значение 8000 Гц и заполним массив из 8000 элементов данными, вызывая функцию someFunc() в цикле

final int sampleRate = 8000;
final int someFuncSize = 8000;
double[] someFunc = new double[someFuncSize];
for (int i = 0; i < someFunc.length; i++) {
    someFunc[i] = someFun(i, sampleRate);
}

В результате чего, получим массив значений, который определяет дискретное представление нашей функции. Для визуального представления полученных данных, выведем, полученные значения, из массива в файл .csv и построим график в программе Excel


Как видно из диаграммы, гармоника с частотой 100 Гц имеет амплитуду 15, значение которой и было указано в константе amplitudeOfFirstHarmonic. Поверх первой гармоники с частотой 100 Гц и амплитудой 15, рисуется вторая гармоника с частотой 880 Гц и амплитудой равной единице.
По такому же принципу создадим две базисные функции косинуса и синуса. Только теперь, мы будем передавать значение частоты в параметры методов наших базисных функций

private double cos(int index, int frequency, int sampleRate) {
    return Math.cos((2 * Math.PI * frequency * index) / sampleRate);
}
private double sin(int index, int frequency, int sampleRate) {
    return Math.sin((2 * Math.PI * frequency * index) / sampleRate);
}

Теперь, определим метод, который будет выполнять дискретное преобразование Фурье. В качестве параметров метода, передадим массив значений исходной дискретной функции, состоящей из суммы простых косинусов, и частоту дискретизации этой функции.

private double[] dft(double[] frame, int sampleRate) {
    final int resultSize = sampleRate / 2;
    double[] result = new double[resultSize * 2];
    for (int i = 0; i < result.length / 2; i++) {
        int frequency = i;
        for (int j = 0; j < frame.length; j++) {
            result[2*i] +=frame[j] * cos(j, frequency, sampleRate);
            result[2*i + 1] +=frame[j] * sin(j, frequency, sampleRate);
        }
        result[2*i] =result[2*i] / resultSize;
        result[2*i + 1] = result[2*i + 1] / resultSize;
    }

    return result;
}

После выполнения преобразования Фурье, полученные значения, определяют проекции всех векторов, упорядоченных по частоте, на оси косинусов и синусов. Для того, чтобы найти длину такого вектора, необходимо применить теорему Пифагора $inline$A=\sqrt{a^2+b^2}$inline$.

double[] result;
long start = System.currentTimeMillis();
result = dft(someFunc, sampleRate);
long finish = System.currentTimeMillis();
long timeConsumedMillis = finish - start;
System.out.println("Time's dft: " + timeConsumedMillis);
double[] amplitude = new double[sampleRate/2];
for (int i = 0; i < result.length / 2; i++) {
    amplitude[i] = Math.sqrt(result[2*i]*result[2*i] + result[2*i+1]*result[2*i+1]);
    System.out.println(i + ": " + "Projection on cos: " + result[2*i] + " Projection on sin: " + result[2*i + 1]
            + " amplitude: "+ amplitude[i] + "\n");
}

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

Таким образом, для гармоник с частотами 100 Гц и 880 Гц, значения амплитуд, будут соответствовать тем значениям, которые были указаны в константах amplitudeOfFirstHarmonic и amplitudeOfSecondHarmonic метода someFunc(). А для остальных гармоник, которых остаётся ровно 3998, значения амплитуд будут приближены к нулю, потому что, остальные гармоники не были определены в исходной дискретной функции someFunc(), которая передавалась на дискретное преобразование Фурье.




Выведем значения амплитуд, полученных после преобразования Фурье функции someFunc(), в файл .csv и построим график в программе Excel. В результате преобразования Фурье, мы получили спектр исходного сигнала



Алгоритм дискретного преобразования Фурье на компьютере выполняется за время $inline$O(n^2)$inline$, что является слишком медленным процессом. Для быстрых вычислений дискретного преобразования Фурье, придумали быстрое преобразование Фурье (БПФ). Алгоритм БПФ, производит вычисления, используя рекурсивный подход, благодаря которому, время выполнения алгоритма уменьшается до $inline$O(n*\lg{n})$inline$. Существует готовая реализация алгоритма БПФ в среде программирования Java, которая представлена в виде библиотеки JTransforms.

Запись данных с микрофона. AudioRecord


За получения звуковых данных в формате PCM с мобильного устройства на платформе Android отвечает класс AudioRecord.
Для создания экземпляра класса AudioRecord, в конструкторе класса AudioRecord, необходимо указать такие параметры как:
  • audioSource — источник, откуда ведётся запись.
  • sampleRateInHz — частота дискретизации в Герцах.
  • channelConfig — тип аудио канала.
  • audioFormat — формат кодирования данных.
  • minBufferSize — минимальный размер буфера.

После создания экземпляра класса AudioRecord, необходимо вызвать метод startReading(), который начнёт запись с мобильного устройства. Записанные звуковые данные будут храниться во внутреннем буфере класса AudioRecord в размере порции, указанной в параметре minBufferSize при создании экземпляра класса. Из внутреннего буфера класса AudioRecord, необходимо периодически забирать записанные данные с помощью вызова метода read() класса AudioRecord.
Для примера, запишем звуковые данные с мобильного устройства, а затем выведем, эти данные, в текстовый файл .csv и построим график полученных звуковых данных, используя программу Excel


При создании экземпляра класса AudioRecord, используем частоту дискретизации равной 8000 Гц и размер буфера равный 1024.

Если эта часть статьи была интересна, то во второй части статьи мы займёмся созданием гитарного тюнера на Android.

Теги:



Комментарии (5):

  1. lzb_j77
    /#10316014

    Из графика сумм гармоник вовсе не следует, что там есть гармоника с частотой 880 герц и амплитудой 1.

  2. alex8turantsev
    /#10316124

    Была бы интересна вторая часть. Спасибо!

  3. slavae
    /#10317714

    Такую программу я написал одной из первых на Delphi 2 на Win95 )))
    Первый поток писал звук в память, второй делал БПФ, а третий отображал результаты в виде лучшей частоты, ближайшей ноты и куда двигать звук — вверх или вниз. Лет 20 прошло, во дела.

    • ByArt
      /#10317720

      А как вы выбирали основную частоту из спектра сигнала? По наибольшей амплитуде?

      • slavae
        /#10318414

        Кажется, да, просто брал самый большой столбик.