Пользователь
0,0
рейтинг
6 января 2015 в 16:33

Разработка → Преобразование Фурье в действии: точное определение частоты сигнала и выделение нот из песочницы

последняя редакция статьи доступна на сайте makeloft.xyz

Начнём с пианино. Очень упрощёно этот музыкальный инструмент представляет собой набор белых и чёрных клавиш, при нажатии на каждую из которых извлекается определённый звук заранее заданной частоты от низкого до высокого. Конечно, каждый клавишный инструмент имеет свою уникальную тембральную окраску звучания, благодаря которой мы можем отличить, например, аккордеон от фортепиано, но если грубо обобщить, то каждая клавиша представляет собой просто генератор синусоидальных акустических волн определённой частоты.

Когда музыкант играет композицию, то он поочерёдно или одновременно зажимает и отпускает клавиши, в результате чего несколько синусоидальных сигналов накладываются друг на друга образуя рисунок. Именно этот рисунок воспринимается нами как мелодия, благодаря чему мы без труда узнаём одно произведение, исполняемое на различных инструментах в разных жанрах или даже непрофессионально напеваемое человеком.

image


Наглядная иллюстрация нотного рисунка


Определение частоты (режим гитарного тюнера)
image

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

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

Ортогональность, в некотором роде, обозначает несмешиваемость функций. Например, если мы возьмём несколько кусочков цветного пластилина и склеим их, то потом всё же сможем разобрать, какие цвета были изначально, но если хорошенько перемешаем несколько баночек гуашевых красок, то точно восстановить исходные цвета без дополнительной информации уже будет невозможно.

(!) Важно понимать, когда мы берёмся анализировать реальный сигнал с помощью преобразования Фурье, мы идеализируем ситуацию и исходим из предположения, что он периодический на текущем временном интервале и состоит из элементарных синусоид. Зачастую это именно так, поскольку акустические сигналы, как правило, имеют гармоническую природу, но вообще возможны и более сложные случаи. Любые наши допущения о природе сигнала обычно ведут к частичным искажениям и погрешностям, но без этого выделить полезную информацию из него крайне сложно.

Теперь опишем весь процесс анализа более подробно:

1. Всё начинается с того, что звуковые волны колеблют мембрану микрофона, который преобразует их в аналоговые колебания электрического тока.

2. Затем происходит дискретизация аналогового электрического сигнала в цифровую форму. На этом моменте стоит остановиться подробно.

Поскольку аналоговый сигнал математически состоит из бесконечного непрерывного во времени множества точек-значений амплитуды, в процессе измерения мы можем выделить из него лишь конечный ряд значений в дискретные моменты времени, то есть, по сути, выполнить квантование по времени…

Как правило, значения-отсчёты берутся через небольшие равные временные промежутки, то есть с определённой частотой, например, 16000 или 22000 Гц. Однако в общем случае дискретные отсчёты могут идти и неравномерно, но это усложняет математический аппарат анализа, поэтому на практике обычно не применяется.

image

Существует важная теорема Котельникова-Найквиста-Шеннона, которая гласит, что аналоговый периодический сигнал, имеющий конечный (ограниченный по ширине) спектр, может быть однозначно восстановлен без искажений и потерь по своим отсчётам, взятым с частотой, большей или равной удвоенной верхней частоте спектра (называемой частотой дискретизации или Найквиста).

Для этого восстановления необходимо применить специальные интерполирующие функции, но проблема в том, что при использовании данных функций вычисления нужно выполнять на бесконечном временном интервале, что на практике невозможно. Поэтому в реальной жизни нельзя сколь угодно повысить частоту дискретизации искусственным образом без искажений даже если изначально она удовлетворяет теореме Котельникова-Найквиста-Шеннона. Для этой операции применяются фильтры Фарроу.

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

3. На следующем этапе происходит само дискретное прямое преобразование Фурье.

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

Существует также довольно простой трюк для увеличения разрешения по частоте — нужно исходный дискретный сигнал заполнить нулями между отсчётами. Однако в результате такого заполнения сильно искажается фазовый спектр, но зато увеличивается разрешение амплитудного. Также возможно применение фильтров Фарроу и искусственное увеличение частоты дискретизации, однако и оно вносит искажения в спектры.

Длительность кадра обычно составляет приблизительно от 30 мс до 1 с. Чем он короче, тем лучшее разрешение мы получаем по времени, но худшее по частоте, чем сэмпл длиннее, тем лучшее по частоте, но худшее по времени. Это очень напоминает принцип неопределённости Гейзенберга из квантовой механики..и не с проста, как гласит Википедия, соотношение неопределенностей в квантовой механике в математическом смысле есть прямое следствие свойств преобразования Фурье

Интересно и то, что в результате анализа сэмпла одиночного синусоидального сигнала амплитудный спектр очень напоминает дифракционную картинку…

Синусоидальный сигнал, ограниченный прямоугольным окном, и его «дифракция»
image
image

Дифракция световых волн
image

На практике это нежелательный эффект, затрудняющий анализ сигналов, поэтому его стараются понизить путём применения оконных функций. Таких функций придумано немало, ниже представлены реализации некоторых из них, а также сравнительное влияние на спектр одиночного синусоидального сигнала.

Применяется оконная функция ко входному кадру очень просто:

for (var i = 0; i < frameSize; i++)
{
    frame[i] *= Window.Gausse(i, frameSize);
}


using System;
using System.Numerics;

namespace Rainbow
{
    public class Window
    {
        private const double Q = 0.5;

        public static double Rectangle(double n, double frameSize)
        {
            return 1;
        }

        public static double Gausse(double n, double frameSize)
        {
            var a = (frameSize - 1)/2;
            var t = (n - a)/(Q*a);
            t = t*t;
            return Math.Exp(-t/2);
        }

        public static double Hamming(double n, double frameSize)
        {
            return 0.54 - 0.46*Math.Cos((2*Math.PI*n)/(frameSize - 1));
        }

        public static double Hann(double n, double frameSize)
        {
            return 0.5*(1 - Math.Cos((2*Math.PI*n)/(frameSize - 1)));
        }

        public static double BlackmannHarris(double n, double frameSize)
        {
            return 0.35875 - (0.48829*Math.Cos((2*Math.PI*n)/(frameSize - 1))) +
                   (0.14128*Math.Cos((4*Math.PI*n)/(frameSize - 1))) - (0.01168*Math.Cos((4*Math.PI*n)/(frameSize - 1)));
        }
    }
}


image

Что касается компьютеров, в своё время был разработан алгоритм быстрого преобразования Фурье, который минимизирует число математических операций, необходимых для его вычисления. Единственное требование алгоритма состоит в том, чтобы число отсчётов было кратно степени двойки (256, 512, 1024 и так далее).

Ниже его классическая рекурсивная реализация на языке C#.

using System;
using System.Numerics;

namespace Rainbow
{
    public static class Butterfly
    {
        public const double SinglePi = Math.PI;
        public const double DoublePi = 2*Math.PI;

        public static Complex[] DecimationInTime(Complex[] frame, bool direct)
        {
            if (frame.Length == 1) return frame;
            var frameHalfSize = frame.Length >> 1; // frame.Length/2
            var frameFullSize = frame.Length;

            var frameOdd = new Complex[frameHalfSize];
            var frameEven = new Complex[frameHalfSize];
            for (var i = 0; i < frameHalfSize; i++)
            {
                var j = i << 1; // i = 2*j;
                frameOdd[i] = frame[j + 1];
                frameEven[i] = frame[j];
            }

            var spectrumOdd = DecimationInTime(frameOdd, direct);
            var spectrumEven = DecimationInTime(frameEven, direct);

            var arg = direct ? -DoublePi/frameFullSize : DoublePi/frameFullSize;
            var omegaPowBase = new Complex(Math.Cos(arg), Math.Sin(arg));
            var omega = Complex.One;
            var spectrum = new Complex[frameFullSize];

            for (var j = 0; j < frameHalfSize; j++)
            {
                spectrum[j] = spectrumEven[j] + omega*spectrumOdd[j];
                spectrum[j + frameHalfSize] = spectrumEven[j] - omega*spectrumOdd[j];
                omega *= omegaPowBase;
            }

            return spectrum;
        }

        public static Complex[] DecimationInFrequency(Complex[] frame, bool direct)
        {
            if (frame.Length == 1) return frame;
            var halfSampleSize = frame.Length >> 1; // frame.Length/2
            var fullSampleSize = frame.Length;

            var arg = direct ? -DoublePi/fullSampleSize : DoublePi/fullSampleSize;
            var omegaPowBase = new Complex(Math.Cos(arg), Math.Sin(arg));
            var omega = Complex.One;
            var spectrum = new Complex[fullSampleSize];

            for (var j = 0; j < halfSampleSize; j++)
            {
                spectrum[j] = frame[j] + frame[j + halfSampleSize];
                spectrum[j + halfSampleSize] = omega*(frame[j] - frame[j + halfSampleSize]);
                omega *= omegaPowBase;
            }

            var yTop = new Complex[halfSampleSize];
            var yBottom = new Complex[halfSampleSize];
            for (var i = 0; i < halfSampleSize; i++)
            {
                yTop[i] = spectrum[i];
                yBottom[i] = spectrum[i + halfSampleSize];
            }

            yTop = DecimationInFrequency(yTop, direct);
            yBottom = DecimationInFrequency(yBottom, direct);
            for (var i = 0; i < halfSampleSize; i++)
            {
                var j = i << 1; // i = 2*j;
                spectrum[j] = yTop[i];
                spectrum[j + 1] = yBottom[i];
            }

            return spectrum;
        }
    }
}


Существует две разновидности алгоритма БПФ — с прореживанием по времени и по частоте, но оба дают идентичный результат. Функции принимают массив комплексных чисел, заполненный реальными значениями амплитуд сигнала во временной области, а после своего выполнения возвращают массив комплексных чисел, содержащий информацию об амплитудном и фазовом спектрах. Стоит помнить, что реальная и мнимая части комплексного числа — это далеко не то же самое, что его амплитуда и фаза!

magnitude = Math.Sqrt(x.Real*x.Real + x.Imaginary*x.Imaginary)
phase = Math.Atan2(x.Imaginary, x.Real)

Результирующий массив комплексных чисел заполнен полезной информацией ровно на половину, другая половина является лишь зеркальным отражением первой и спокойно может быть исключена из рассмотрения. Если вдуматься, то этот момент хорошо иллюстрирует теорему Котельникова-Найквиста-Шеннона, о том, что частота дискретизации должна быть не меньше максимальной удвоенной частоты сигнала…

Также существует разновидность алгоритма БПФ без рекурсии по Кули-Тьюки, которая часто применяется на практике, но она чуть более сложна для восприятия.

Сразу после вычисления преобразования Фурье удобно нормализовать амплитудный спектр:

var spectrum = Butterfly.DecimationInTime(frame, true);
for (var i = 0; i < frameSize; i++)  
{
	spectrum[i] /= frameSize;
}

Это приведёт к тому, что величина значений амплитуды получится одного порядка не зависимо от размеров сэмпла.

Вычислив амплитудный и частотный спектры, легко производить обработку сигнала, например, применять частотную фильтрацию или производить сжатие. По сути, таким образом можно сделать эквалайзер: выполнив прямое преобразование Фурье, легко увеличить или уменьшить амплитуду определённой области частот, после чего выполнить обратное преобразование Фурье (хотя работа настоящих эквалайзеров обычно основана на другом принципе — фазовом сдвиге сигнала). Да и сжать сигнал очень просто — нужно всего лишь сделать словарь, где ключом является частота, а значением соответствующее комплексное число. В словарь нужно занести лишь те частоты, амплитуда сигнала на которых превышает какой-то минимальный порог. Информация о «тихих» частотах, не слышимых ухом, будет потеряна, но получится ощутимое сжатие при сохранении приемлемого качества звучания. Отчасти этот принцип лежит в основе многих кодеков.

4. Точное определение частоты

Дискретное преобразование Фурье даёт нам дискретный спектр, где каждое значение амплитуды отстоит от соседних на равные промежутки по частоте. И если частота в сигнале кратна шагу равному (частота дискретизации)/(количество отсчётов), то мы получим выраженный остроконечный пик, но если частота сигнала лежит где-то между границами шага ближе к середине у нас выйдет пик со «срезанной» вершиной и нам будет затруднительно сказать, что же там за частота. Очень может быть что в сигнале присутствуют две частоты лежащие рядом друг с другом. В этом и заключается ограничение разрешения по частоте. Так же как на фотоснимке с низким разрешением мелкие предметы склеиваются и становятся неразличимы, так же и тонкие детали спектра могут теряться.

Но частоты музыкальных нот лежат далеко не на сетке шагов преобразования Фурье, а для повседневных задач настройки музыкальных инструментов и распознавания нот необходимо знать именно точную частоту. Более того, на низких октавах при разрешении от 1024 отсчётов и ниже сетка частот Фурье становится настолько редкой, что попросту на одном шаге начинают умещаться несколько нот и определить какая же на самом деле из них играет становится фактически невозможно.

Чтобы как-то обойти это ограничение иногда применяют аппроксимирующие функции, например, параболические.
www.ingelec.uns.edu.ar/pds2803/Materiales/Articulos/AnalisisFrecuencial/04205098.pdf
mgasior.web.cern.ch/mgasior/pap/biw2004_poster.pdf
Но всё это искусственные меры, которые улучшая одни показатели могут давать искажения в других.

Существует ли более естественный путь для точного определения частоты?
Да, и скрыт он как раз-таки в использовании фазового спектра сигнала, которым часто пренебрегают.
Данный метод уточнения частоты сигнала, основан на вычислении задержки фаз у спектров двух кадров, наложенных друг на друга, но немного сдвинутых во времени.

Подробно прочитать о нём можно по ссылкам:
www.guitarpitchshifter.com/algorithm.html
www.dspdimension.com/admin/pitch-shifting-using-the-ft (+ примеры кода)
eudl.eu/pdf/10.1007/978-3-642-29157-9_43
ctuner.googlecode.com (примеры использования алгоритма на C++ и Java)

На C# реализация метода выглядит довольно просто:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Numerics;

namespace Rainbow
{
    //  Δ∂ωπ
    public static class Filters
    {
        public const double SinglePi = Math.PI;
        public const double DoublePi = 2*Math.PI;

        public static Dictionary<double, double> GetJoinedSpectrum(
            IList<Complex> spectrum0, IList<Complex> spectrum1,
            double shiftsPerFrame, double sampleRate)
        {
            var frameSize = spectrum0.Count;
            var frameTime = frameSize/sampleRate;
            var shiftTime = frameTime/shiftsPerFrame;
            var binToFrequancy = sampleRate/frameSize;
            var dictionary = new Dictionary<double, double>();

            for (var bin = 0; bin < frameSize; bin++)
            {
                var omegaExpected = DoublePi*(bin*binToFrequancy); // ω=2πf
                var omegaActual = (spectrum1[bin].Phase - spectrum0[bin].Phase)/shiftTime; // ω=∂φ/∂t
                var omegaDelta = Align(omegaActual - omegaExpected, DoublePi); // Δω=(∂ω + π)%2π - π
                var binDelta = omegaDelta/(DoublePi*binToFrequancy);
                var frequancyActual = (bin + binDelta)*binToFrequancy;
                var magnitude = spectrum1[bin].Magnitude + spectrum0[bin].Magnitude;
                dictionary.Add(frequancyActual, magnitude*(0.5 + Math.Abs(binDelta)));
            }

            return dictionary;
        }

        public static double Align(double angle, double period)
        {
            var qpd = (int) (angle/period);
            if (qpd >= 0) qpd += qpd & 1;
            else qpd -= qpd & 1;
            angle -= period*qpd;
            return angle;
        }
	}
}

Применение также несложное:

                        var spectrum0 = Butterfly.DecimationInTime(frame0, true);
                        var spectrum1 = Butterfly.DecimationInTime(frame1, true);
                        for (var i = 0; i < frameSize; i++)
                        {
                            spectrum0[i] /= frameSize;
                            spectrum1[i] /= frameSize;
                        }

                        var spectrum = Filters.GetJoinedSpectrum(spectrum0, spectrum1, ShiftsPerFrame, Device.SampleRate);

Обычно исходные кадры сдвинуты на 1/16 или 1/32 своей длины, то есть ShiftsPerFrame равно 16 или 32.

В результате мы получим словарь частота-амплитуда, где значения частот будут довольно близки к реальным. Однако «срезанные пики» всё ещё будут наблюдаться, хоть и менее выражено. Чтобы устранить этот недостаток, можно просто «дорисовать» их.



using System;
using System.Collections.Generic;
using System.Linq;
using System.Numerics;

namespace Rainbow
{
    public static class Filters
    {
        public static Dictionary<double, double> Antialiasing(Dictionary<double, double> spectrum)
        {
            var result = new Dictionary<double, double>();
            var data = spectrum.ToList();
            for (var j = 0; j < spectrum.Count - 4; j++)
            {
                var i = j;
                var x0 = data[i].Key;
                var x1 = data[i + 1].Key;
                var y0 = data[i].Value;
                var y1 = data[i + 1].Value;

                var a = (y1 - y0)/(x1 - x0);
                var b = y0 - a*x0;

                i += 2;
                var u0 = data[i].Key;
                var u1 = data[i + 1].Key;
                var v0 = data[i].Value;
                var v1 = data[i + 1].Value;

                var c = (v1 - v0)/(u1 - u0);
                var d = v0 - c*u0;

                var x = (d - b)/(a - c);
                var y = (a*d - b*c)/(a - c);

                if (y > y0 && y > y1 && y > v0 && y > v1 &&
                    x > x0 && x > x1 && x < u0 && x < u1)
                {
                    result.Add(x1, y1);
                    result.Add(x, y);
                }
                else
                {
                    result.Add(x1, y1);
                }
            }

            return result;
        }
    }
}


Перспективы

Нотный анализ музыкальных произведений открывает ряд интересных возможностей. Ведь имея в наличии готовый нотный рисунок, можно осуществлять поиск других музыкальных композиций со схожим рисунком.

Например, одно и то же произведение может быть исполнено на другом инструменте, в различной манере, с другим тембром, либо транспонировано по октавам, однако нотный рисунок останется похожим, что позволит найти различные варианты исполнения одного и того же произведения. Это очень напоминает игру «угадай мелодию».

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

Итоги

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

P.S. Радужный фреймворк (Rainbow Framework) содержащий все вышеизложенные примеры кода можно скачать с Кодплекса.

P.P.S. Возможно, эта статья когда-нибудь серьёзно пригодится вам в профессиональной деятельности и поможет сохранить уйму времени и сил, поэтому если вы желаете отблагодарить автора за труд, то можете сделать пожертвование, купить приложение (бесплатная версия с рекламой), благодаря которому статья возникла, либо просто выразить благодарность добрым словом.

Литература

1. Основы спектрального анализа звуков pandia.org/text/77/481/644.php

2. Алгоритм Кули-Тьюки www.codeproject.com/Articles/32172/FFT-Guitar-Tuner

3. Передискретизация (ресэмплинг)
www.dsplib.ru/forum/viewtopic.php?f=5&t=11
www.dsplib.ru/content/farrow/farrow.html

4. Коррекция частоты по смещению фазы
www.guitarpitchshifter.com/algorithm.html
www.dspdimension.com/admin/pitch-shifting-using-the-ft (+ примеры кода)
eudl.eu/pdf/10.1007/978-3-642-29157-9_43
ctuner.googlecode.com (примеры использования алгоритма на C++ и Java)
@Makeman
карма
28,0
рейтинг 0,0
Пользователь
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Спецпроект

Самое читаемое Разработка

Комментарии (47)

  • –1
    > соотношение неопределенностей в квантовой механике в математическом смысле есть прямое следствие свойств преобразования Фурье…

    Странное какое-то утверждение. Вообще-то соотношение неопределенности имеет в своей основе то, что координата и импульс не являются независимыми переменными — и, как следствие, их операторы некоммутативны.
    • +4
      О связи преобразования Фурье с принципом неопределённости Гейзенберга можно подробнее прочитать по ссылкам:
      ru.wikipedia.org/wiki/Принцип_неопределённости
      pandia.org/text/77/481/644.php
    • 0
      Применительно к квантовой механике сразу возникает вопрос, что же первично — математический факт или конкретная физическая особенность нашего мира. Аккуратнее надо, а то философы набегут (у меня-то кандидатский по ней на тройку едва сдан, так что не страшно).
      • 0
        Насколько мне удалось понять, в квантовой механике особый взгляд на природу времени, в рамках которого понятия первично и вторично теряют привычный смысл, поэтому вопрос будет некорректен :)
        • +1
          Нет в классической квантовой теории особого понимания времени. Оно есть в релятивистской теории, в том числе и в квантовой, но вроде бы не об этом речь.

          А вопрос «что первично — теория или эксперимент» (как изначально ставилось) — очень философский, спорный и сложный, потому, что квантовые эксперименты всё равно все сейчас непрямые, а значит — обсчитываются через теорию. Но вообще «теория первична» — это идеалистический взгляд на мир, а «эксперимент первичен» — материалистический.
      • +3
        Тут нет смысла говорить о первичности. Присутствует и то, и другое. Физическая особенность мира проявляется в том, что частицы в квантовой механике описываются волнами вероятности, а для волн верен математический факт, численно выражающийся в соотношении неопределенностей.

        Кстати, соотношение неопределенностей Гейзенберга легко иллюстрируется следующим рассуждением в предположении о волновой природе частиц.
        1. Пусть у нас есть волновой цуг (фрагмент волны) длины L. Неопределенность положения частицы Δx совпадает с L.
        2. На волновом цуге укладывается L/λ «горбов» и «впадин», где λ — длина волны (расстояние между соседними горбами). При этом мы можем посчитать количество горбов лишь с точностью до 1, то есть Δ(L/λ) ~ 1.
        3. В квантовой механике длина волны связана с импульсом частицы: p = h/λ.
        4. Из пунктов 2 и 3: Δ(Lp/h) = L Δp/h ~ 1, или Δx Δp ~ h.

        Физика здесь в третьем пункте, математика осталась во втором.
  • +2
    Очень смущают на первом графике несколько точек квантования в отдельно взятую единицу времени. Мне казалось, что график должен выглядить примерно так, с одним измеренным значением в каждый отдельный момент: image
    • +2
      Спасибо! Вы абсолютно правы, иллюстрации брал из интернета и не обратил внимания на эту ошибку. Постараюсь исправить в ближайшее время.
  • +3
    Если вдуматься, то этот момент хорошо иллюстрирует теорему Котельникова-Найквиста-Шеннона, о том, что частота дискретизации должна быть не меньше максимальной удвоенной частоты сигнала…


    Этот момент — нет. Этот момент хорошо иллюстрирует только свойства преобразования Фурье для входных данных являющихся действительными числами :)

    Дискретное преобразование Фурье даёт нам дискретный спектр, где каждое значение амплитуды отстоит от соседних на равные промежутки по частоте. И если частота в сигнале кратна шагу равному (частота дискретизации)/(количество отсчётов), то мы получим выраженный остроконечный пик, но если частота сигнала лежит где-то между границами шага ближе к середине у нас выйдет пик со «срезанной» вершиной и нам будет затруднительно сказать, что же там за частота

    Чтобы как-то обойти это ограничение иногда применяют аппроксимирующие функции, например, параболические.


    Гораздо проще просто дописать нулей во входные данные (как собственно и упоминается выше по тексту). Это не оптимально по скорости, но часто удобно
  • 0
    А в целом метод определения центра гармоники очень интересный, спасибо за ссылочки :)
    Работает конечно только для сигналов которые можно разложить в несколько сильно разнесенных по частоте синусоид, но зато быстро, эффективно и не зависит от выбора оконной функции
  • +1
    Существует ли более естественный путь для точного определения частоты?
    Да, и скрыт он как раз-таки в использовании фазового спектра сигнала, которым часто пренебрегают.
    Данный метод уточнения частоты сигнала, основан на вычислении задержки фаз у спектров двух кадров, наложенных друг на друга, но немного сдвинутых во времени.

    То есть, использовать информацию из нескольких окон подряд? Практически то же самое, что и использовать окно большего размера.

    Вообще очень хорошо понимать, что «принцип неопределённости» в данном случае звучит как «если имеем хорошее разрешение по частоте, то плохое разрешение по времени», и наоборот. Хорошо знаем момент времени (узкое окно) — плохо (грубо) знаем частоту. Хорошо знаем частоту — плохо знаем в какой момент времени это было (широкое окно).
    • +2
      Там идея в том что если есть чистая синусоида, то её спектр — это фактически просто спектр оконной функции (свернутый пару раз с собой, но при упоминающемся в исходных ссылках грамотном выборе оконной функции это не вносит существенных искажений). Точно определив этот спектр (а для этого достаточно и нескольких отсчетов поскольку функция параметризуется всего двумя параметрами) можно определить и исходный гармонический сигнал. Работает это естественно только для чистых синусоид или хотя бы синусоид разнесенных по частоте достаточно для того чтобы спектры их свертки с окном существенно не перекрывались. Ну а метод с перекрытием, собственно, просто позволяет удобно определять положение центральной частоты у спектра окна причем независимо от выбранной оконной функции просто за счет наблюдения что сдвиг окна не меняет его амплитудную характеристику, но по строго определенному закону зависящему от центральной частоты меняет фазовую.

      Сам по себе этот метод идеологически не отличается от подхода «добить выборку кучей нулей, а затем найти максимум в спектре» — хотя сам спектр довольно широк, но если исходный сигнал чисто синусоидальный, то этот максимум тоже точно дает нужную частоту. Просто его вычислять куда быстрее, да и по-своему удобнее. Различить две синусоиды с близкими частотами он не позволит, а вот найти точную частоту одной синусоиды когда мы точно знаем что она одна — вполне.
      • 0
        Да, действительно. Вот это объяснение конечно не укладывается по стилю в статью, но там его не хватает.
    • +1
      То есть, использовать информацию из нескольких окон подряд? Практически то же самое, что и использовать окно большего размера.

      Не совсем так. Как мне показалось, фазовый метод корректирует частоту точнее, чем простое увеличение размера окна в два раза, к тому же он не ограничен дискретной сеткой, а это важно, например, для тюнеров. Конечно, можно попробовать добавить ещё больше нулей, но анализ слишком больших кадров уже начинает сказываться на производительности, что заметно на мобильных устройствах.
  • +1
    Кстати, простой и очень быстрый тюнер можно сделать на триггере Шмитта.
    На странице http://forum.cockos.com/showthread.php?t=79185 парень по имени Mich очень хорошо и наглядно объяснил, как это работает.
    • 0
      Спасибо! Пока ещё детально не разобрался, но меня заинтересовал подход.
      • 0
        Я делал тюнер и так, и на быстром преобразовании Фурье. Думаю, большинство современных железных девайсов для настройки работают на триггере Шмитта (могу ошибаться, не изучал вопрос).
  • 0
    Большое спасибо за статью! Кажется, вы хорошо разбираетесь в теме.

    У меня вопрос.

    Я долгое время думаю вот над чем — классические алгоритмы во всех известных мне программах и устройствах (начиная от тюнеров/дисторшенов, заканчивая автотюнами, pitch'ами и shimmer'ами) оперируют набором буферов по «сколько то там» семплов. Если сравнить со, скажем, душевой, то сначала вода закачивается в какой-нибудь бойлер, там её, скажем подогревают, потом расходуют, и затем повторяют процесс заново. Вопрос в том, существуют ли алгоритмы (может, на базе функционального программирования), которые ориентируются на «буфер» размером в 1 (ОДИН) семпл и, скажем, хранение какого-нибудь предшествующего состояния? Чтобы как проточный водонагреватель работало?

    Зачем это нужно? Например, чтобы добиться 0-latency в аудио-плагинах/приборах. Например, алгоритм питчера или дилея, который получает семпл на вход, выполняет алгоритм (который может динамически перестраиваться, в зависимости от времени/некоего количества предыдущих семплов) и тут же рисует сэмпл на выходе, ориентируясь только на этот входящий семпл и хранение некоего вычисленного предыдущего состояния. Чтобы можно было весь алгоритм сократить до функции с «памятью», когда на вход подаётся сэмпл и, скажем, временная отметка, а на выходе имеем обработанный сэмпл, который получился бы и с помощью «классической» offline-обработки. На самом деле, профита намного больше, но хотел бы узнать, существуют ли такие наработки? И есть ли такие наработки для подобия FFT, чтобы каждый раз получая новый семпл, уточнять «мгновенный» спектр сигнала, а не вычислять его из буфера (что актуально, скажем, для 0-latency питчеров для бас-гитар, т.к. там период ноты может быть до 50ms)?
    • +1
      Вы в общем-то описали импульсные фильтры. Именно так, как вы описали, и устроены всевозможные цифровые эквалайзеры, дилеи/реверы, ресемплеры и тому подобное. Чаще всего используются фильтры с конечным откликом, т.к. с ними проще, нет проблем с устойчивостью (КИХ, FIR-фильтры), но иногда используются фильтры с бесконечным откликом за счёт обратной связи — у них сложнее с устойчивостью, но они быстрее потому, что «буфер» меньше (БИХ, IIR-фильтры).

      А анализ данных с использованием FIR-фильтров называется polyphase filter bank.

      А размеры буферов в программах ограничены снизу скорее производительностью и непредсказуемостью x86-архитектры.
    • +1
      Такие методы есть. Но все они имеют конечную задержку математической природы. Образно говоря, чем точнее нужно измерить частоту — тем больше на это требуется времени.

      Скажем, если вы возьмете простой резонансный фильтр второго порядка H(z)=1/(1 + a1*z^(-1) + a2*z^(-2)) — подбирая значения a1 и a2, можно получить пик на АЧХ такого фильтра, т.е. настроить этот фильтр на конкретную частоту, чтобы он как бы детектировал ее во входном сигнале. Чем у'же пик АЧХ — тем более точно ваш фильтр будет детектировать в сигнале нужную частоту. Но если построить частотную характеристику группового времени задержки такого фильтра — то окажется, что чем острее пик АЧХ — тем острее будет пик и на ГВЗ, то есть фильтр будет быстро пропускать волновые пакеты далеко от своей резонансной частоты (он как бы может быстро определить, что сигнал находится вдали от резонанса), но задерживать сигналы вблизи частоты резонанса (ведь там фильтр должен точно измерить частоту сигнала чтобы определить, должен он ее пропускать или нет).
    • +1
      Да, методы такого рода есть. И не только различные линейные фильтры, о которых написали вам выше, но и разнообразные (нелинейные) адаптивные методы и методы идентификации. Упрощенно, исходному сигналу ставится в соответствие некоторая математическая модель генератора с неизвестными и переменными параметрами, определяющими частоты. С получением каждого нового отсчета оценки этих параметров (частот) адаптивно подстраиваются и, если все хорошо, то оценки сходятся к истинным значениям.
      Такие адаптивные методы очень широко применяются в подавлении механических возмущений и вибраций, в акустике для устранении шумов и эха, и вообще во всей широкой области Adaptice Regulation/ Adaptive Disturbance Attenuation. Применяются они, например, и в морских задачах, для определения параметров качки.

      Вообще, адаптивное подавление возмущений — моя профессиональная область, так что если интересно, то могу ответить на вопросы или написать подробнее. :)
  • +1
    Нотный анализ музыкальных произведений открывает ряд интересных возможностей. Ведь имея в наличии готовый нотный рисунок, можно осуществлять поиск других музыкальных композиций со схожим рисунком.


    Я бы посмотрел на алгоритм, который бы бы родил сносное midi, например, к этому:

    (Я прекрасно понимаю, что midi к аппассионате найти вообще не составляет проблем, но есть куча потрясной музыки, к которой не то, что миди — нот-то не найдёшь… Я вот, например, один квартет у Риса уже остыл искать)

    С простыми-то вещами даже тот же chordify справлялся неплохо (кстати, на чём он?) — но мы-то тут про готовый нотный рисунок?
    • 0
      Кстати, раз уж про нотные рисунки – есть ли какие-то подвижки в области непосредственно анализа музыки с применением описанных алгоритмов? Планируются ли? Будет ли это утилитка, сайт вроде chordify, или оба сразу?

      Если были эксперименты – с удовольствием прочел бы детали — насколько хорошо проходит анализ, скажем, чижика-пыжика, чижика-пыжика с фоном, смогли ли отличить трезвучие Am от септаккорда A7?
      • 0
        А в чём проблема отличить Am от A7? Интервальные структуры [1 3- 5] и [1 3 5 7] заметно отличаются друг от друга. Уже давно есть софт, который мажорный аккорд может минорным сделать, тот же melodyne в режиме polyphonic/DNA: www.youtube.com/watch?v=I4YEebBN2ok#t=110 (со второй минуты).
        Кстати, тот же melodyne умеет midi рисовать по композиции: www.youtube.com/watch?v=-ojHdfhl_iw
        И делает это неплохо, даже с фоном: www.youtube.com/watch?v=9FScFKuXXM0#t=49
        • 0
          Обалдел от melodyne. С ума сойти. Я, впрочем, имел в виду, что именно fft ли тут для этого?
          • 0
            Посмотрел обучающие видеозаписи по Melodyne, и меня они очень впечатлили, вот что значит профессиональный инструмент обработки аудио. Думаю, он стоит своих денег. Предполагаю, что тут как раз таки активно используются фазовые методы коррекции аудиосигналов, как, например, по этой ссылке www.guitarpitchshifter.com/algorithm.html.
        • 0
          В общем, натравил я мелодайн на фортепианный квартет Риса (Fm, ор.13), т.к. очень давно и совсем безрезультатно ищу к нему ноты. Не, он, конечно, кое-что распознал… но далеко не всё. -_-. Видимо, я слишком многого хочу.
      • 0
        На текущий момент у меня подобных наработок нету, хотя, возможно, кто-то этим уже занимается. Разработка подобных алгоритмов требует огромного труда и ресурсов, а эта статья, как и мобильное приложение к ней, написаны на энтузиазме :)

        Не знаю точно, получится ли дальнейшее развитие в этом направлении. Увидим…
      • 0
        Проблема хорошего распознавания midi, а уж тем более нотных записей также как и распознавание текста, речи, предметов решится после того, как разработают сильный ИИ. Потому как для того, чтобы распознать вышеупомянутую композицию, нужно использовать не только простое определение частот (этого будет недостаточно из-за неидельного звучания), но и теорию музыки, гармонию, шаблоны и, возможно, инструменты, имеющие к музыке очень косвенное отношение.
    • +1
      Попробуйте Akoff Music Composer.
      Правда, он платный, но 10 секунд можно преобразовать бесплатно :)
  • +2
    когда я пытался подобрать мелодию, использовал научный спектрометр, но вот по пикам частот выявлял ноты сам.
    image
    • +3
      Существует также хорошая программа для подбора нот — Transcribe!.
      Только она работает не в реальном времени с потоковым аудиосигналом, а с готовым треком.

      image

      image
      • 0
        спасибо, правда с набега разобраться в ней что-то не получилось
  • +2
    Кстати, ещё один очень простой способ точно определить частоту сигнала, если известно, что он состоит из небольшого числа гармоник: сначала вычисляем FFT с низким разрешением, находим два соседних отсчета с высоким уровнем амплитуды, скажем f1 и f2. Искомый сигнал где-то между ними. Теперь просто сворачиваем сигнал с десятком sin и cos с частотами, распределенными от f1 до f2 и опять находим максимум. Тем самым повышаем разрешение в 10 раз. Можно применить технику бинарного поиска, чтобы оптимизировать процесс. Но смысл думаю понятен.
  • +1
    Спасибо за статью, возник один вопрос. А что насчет извлечения партии отдельного инструмента из записи? Например, насколько реально, с технической точки зрения, извлечь партию альта или, скажем, барабанов из Sing, Sing, Sing Бенни Гудмэна? Я понимаю, что спектры частот некоторых инструментов существенно пересекаются, но все же.
    • +1
      Хороший вопрос.

      Извлечь партии инструментов, слабо пересекающихся спектрально, технически можно уже сейчас. Нужно просто применить эквалайзер и заглушить ненужные частоты. Однако на практике как раз таки сложнее всего раскладывать по нотам низкочастотные звуки, поскольку в области басов ноты расположены ближе друг к другу по частоте, поэтому нужно применять более длинные кадры, что ведёт к низкому временному разрешению.

      С инструментами, имеющими близкие спектры, дело обстоит намного интереснее. Ведь их мы распознаём именно по тембральной окраске, восприятие которой во многом имеет псюхо-аккустическую природу. Поскольку человек с помощью своего слухового аппарата может выполнить эту задачу, то, теоретически, это доступно и компьютеру… Но для этого нужна, как минимум, специально обученная нейронная сеть. Обучением этой сети, как раз-таки и занимаются люди слушая звуки мира, различную музыку, музицируя…

      Одному человеку, как говорят, медведь на ухо наступил, а другой способен различить разницу в неколько герц. И дело здесь скорее не в особенностях строения уха, а именно в обученности нейронной сети, котороя, к слову, начинает закладываться в раннем детстве, вероятно даже, ещё в утробе матери… Учёные проводили эксперимент, только что родившемуся котёнку, заклеивали один глаз, а спустя пару недель повязку снимали, но котёнок на всю жизнь оставался слеп на этот один глаз, хотя физиологически всё было здорово… То есть способность к зрению закладывается именно в самом раннем детстве, а потом её уже так просто не восстановишь. Поэтому, когда мама и папа поют или разговаривает с ещё не родившимся малышом, то это совершенно не пустое занятие, как может показаться прагматичному человеку.

      Вспомните, как звучит для вас иностранный язык, которого вы не знаете. Это просто набор слитных звуков, непонятная аброкадабра. Но когда вы начали его изучать, вдруг, вы обнаруживаете способность выхватывать отдельные слова, сочетания, предложения… А если овладели языком в совершенстве, то даже в шумной обстановке по обрывкам фраз можете восстановить то, что сказал собеседник.

      То же самое и с музыкой, когда вы слушаете её много, то начинаете различать оттенки, вибрато, вдруг в старых композициях находите для себя новые звуки, которые почему-то раньше не замечали.
      • 0
        Поскольку человек с помощью своего слухового аппарата может выполнить эту задачу, то, теоретически, это доступно и компьютеру… Но для этого нужна, как минимум, специально обученная нейронная сеть. Обучением этой сети, как раз-таки и занимаются люди слушая звуки мира, различную музыку, музицируя…


        А вы не знаете, задействован кто-либо в этой области, есть ли какие наработки?
        • 0
          Думаю, что в области разработки ИИ и компьютерного слуха в мире задействовано много учёных, но, к сожалению, ничего более конкретного рассказать не могу, и на данный момент у меня таких наработок нет.

          По сути, на предварительном этапе слуховая система преобразует акустический сигнал в спектральную форму. Причём, согласно недавним исследованиям, учитывается не только амплитуда, но и фаза сигнала(!), благодаря чему мозг по разности фаз и амплитуд между обоими ушами способен точнее определять направление источника звука.
  • +1
    Стоит отметить, что для определения частоты основного тона (ЧОТ) сигнала можно использовать не только методы, работающие в частотном пространстве (преобразование Фурье), но и методы, работающие во временном пространстве (автокорреляция). Однако и те и другие обладают своими достоинствами и недостатками. Автокорреляция, например, довольно медленная и неточная для высоких частот.

    Под .NET есть следующая либа для определения ЧОТ в реальном времени: pitchtracker.codeplex.com
    Как пишет автор, его алгоритм, основанный на автокорреляции, обладает следующими достоинствами:
    • Быстрота. Возможность определять до 3000 частот в секунду.
    • Точность. Отклонение от правильной частоты в пределах +-0.02%
    • Высокая точность для сигналов любой громкости (от -40db до 0dB)
    • Высокая точность для широкого диапазона частот (от 50 Hz до 1.6 kHz)
    • Высокая точность для сигнала любой формы. Возможность определять ЧОТ для женского, мужского голосов и всеразличных инструментов.
    • Независимость от предыдущих результатов.

    Более подробно об алгоритме написано в документации.
    • +1
      Оу, большое спасибо за ссылку! Проверил, алгоритм работает!
      Бьюсь об заклад, что многие гитарные тюнеры, виденные мной, используют именно его.
      Отклик быстрее, чем у преобразования Фурье с окном 2048 при сравнимой точности.
      Но алгоритм распознаёт лишь один пик, поэтому применение его ограничено, однако если использовать в связке с преобразованием Фурье, то, вероятно, можно достичь весьма интересных результатов…

      Чтобы пример по ссылке заработал с реальным сигналом с микрофона, добавьте в проект ссылку Microsoft.Xna.Framework, затем закомментируйте строчки
                  m_timer = new DispatcherTimer();
                  m_timer.Interval = TimeSpan.FromMilliseconds(m_timeInterval);
                  m_timer.Tick += OnTimerTick;
                  m_timer.Start();
      

      и вместо них допишите
                  var timer = new DispatcherTimer();
                  timer.Tick += (sender, args) => FrameworkDispatcher.Update();
                  timer.Start();
      
                  var device = Microphone.Default;
                  device.BufferDuration = TimeSpan.FromMilliseconds(100);
                  var bufferSize = device.GetSampleSizeInBytes(device.BufferDuration) / 2;
                  var sampleBytes = new byte[2 * bufferSize];
      
                  device.BufferReady += (sender, args) =>
                  {
                      var sampleSizeInBytes = device.GetData(sampleBytes);
                      var sampleSize = sampleSizeInBytes / 2;
                      var sample = new double[sampleSize];
                      for (var i = 0; i < sampleSize; i++)
                      {
                          sample[i] = Convert.ToDouble(BitConverter.ToInt16(sampleBytes, 2 * i));
                      }
                      m_pitchTracker.ProcessBuffer(sample.Select(t=>(float)t).ToArray());
      
                      UpdateDisplay();
                  };
      
                  FrameworkDispatcher.Update();
                  device.Start();
      

      Скомпилируйте.

      А теперь настраивайте гитару!
      • 0
        Для захвата звука с микрофона лучше все же использовать библиотеку NAudio, потому что она специально предназначена для обработки звука и не имеет зависимостей. NAudio поддерживает работу с разными форматами, потоки в реальном времени, преобразование Фурье и другие вещи. На сайте есть множество демонстрационных приложений, в том числе и для захвата звука. А XNA не у каждого установлен, да и это игровой фреймворк.

        Но это так, технические моменты :)
        • 0
          Есть опыт работы с обоими библиотеками. XNA-фреймворк установлен по умолчанию со студией, а NAudio нужно доплнительно загружать, хотя это не проблема. XNA родной и мультиплатформенный (Win Desktop, Win RT, Win Phone), а также проще в освоении и использовании, по крайней мере, что касается звука. NAudio не мультиплатформенный и более сложный, но охватывает круг аудиозадач более широкий нежели первый собрат.

          Думаю, для простого захвата сигнала с микрофона и его анализа, всё-таки легче использовать первый вариант.
          • 0
            XNA-фреймворк установлен по умолчанию со студией

            Странно, у меня не установился.
      • 0
        Кстати, насчет тюнеров. Есть еще такая реализация, с БПФ: FFT-Guitar-Tuner. Здесь захват данных уже реализован с помощью Microsoft.DirectX.DirectSound.

        В ней, насколько я понял, алгоритмом ищутся максимумы в спектре, а затем, на основе индексов максимумов, анализируется сигнал во временной области с помощью разновидности корреляции.
  • 0
    Наткнулся на интервью с создателем программы Melodyne, о которой упоминалось выше в комментариях.
    Видео получасовое и на английском, но понять кое-что можно, даже если смотреть перематывая.
    Возможно, кто-то отыщет для себя новое…

  • +3
    Учась на 4 курсе, в качестве диплома написал спектральный анализатор «певческого таланта» для Новосибирского фониатрического центра. Моя только реализация, сама теория резонанса пения создана В. Морозовым. Вкратце, суть такова: в спектре находим 3-ю форманту, берем от нее интеграл, и делим на интеграл от всего спектра. Получается коэффициент (чаще выражаемый в процентах), характеризующий долю голосовой энергии, сосредоточенной в 3-й форманте (той части спектра, которая является своего рода референтом резонансных процессов). Чем выше коэффициент, тем более звучащим, живым, объемным мы воспринимаем голос певца, это своего рода математическое выражение красоты пения.

    Было любопытно, что этот самый процент у «попсовых» певцов был около 10 (примерно, пишу по памяти), у хороших певцов ближе к 20, у великих оперных певцов за 30. Самое любопытное, кому принадлежал наивысший (по моим данным) процент, т.е. кто владел техникой резонансного пения в совершенстве, оставив далеко позади величайших теноров мирового класса. Этот человек не поет на сцене, а помогает тысячам людей восстановить (после операций и пр.) или развить голос, пожилой врач фониатрического центра, выдающийся специалист в этой области.

    Ах да, я вот о чем: у меня в спектре первым отсчетом шло очень большой значение (постоянная составляющая сигнала). Не помню уже подробностей, как правильно с этим бороться (она сильно растягивала график по вертикали), я просто ее занулял за ненадобностью.
  • 0
    На CodeEval недавно была задача по этой теме: The Frequency

Только зарегистрированные пользователи могут оставлять комментарии. Войдите, пожалуйста.