Дискретное преобразование Фурье

Захотелось мне сделать такой вот визулизатор звука, как на картинке. Причем в рилтайме и на микропроцессоре.

Покумеков, я понял, что можно такое дело запросто забацать на проце фирмы ATMEL - какой-нибудь ATMEG-е.

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

В принципе, все просто - бери учебник, сдувай с него пыль, вспоминай алгоритм бабочки и реализуй - но мне мешало одно и имя ему ЛЕНЬ :)

Что делают в таких ситуациях? Прально - лезут в гугль, наверняка кто-нибудь уже что-то подобное делал. Так оно и есть, библиотек море, есть даже популярные вроде такого или такого. Есть даже очень точные, есть 16-битные, 8-битные и т.д., есть даже очень хорошее объяснение всего мат. аппарата.

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

Точность тут вообще никуда не уперлось - мы же не частотомер делаем. Хотелось простецкого алгоритма, пусть и выдающего лишь приближенные результаты. И на выходе нам требуется лишь амплитуда, мнимые и действительные части не нужны. Амплитуда считается как sqrt( мнимое2 + действительное2 ).

После достаточно длительных поисков я наконец нашел идеальный вариант для меня на pastebin-е.
Очень простой алгоритм, делающий все, что мне нужно было, привожу его псевдокод на JavaScript:

var FFT = ( function( size ) {	
	var m = size + ( size % 2 ); //размер выходного буфера должен быть четным
	var out = new Array( m );
 
	return function( data, len ) {
		var pid = ( 2.0 * Math.PI ) / len;
 
		var r, i, w, t;
 
		//высчитываем среднее значение по всему интервалу
		//для последующей нормализации
		var mv = 0;
		for ( t = 0; t < len; t++ ) mv += data[t];
		mv = mv / len;
 
		for ( w = 0; w < m; w++ ) {
			var a = w * pid;
			r = 0;
			i = 0;
			for ( t = 0; t < len; t++ ) {
				//нормализация значения из интервала
				var v = data[t] - mv;
				var ta = a * t;
				r += v * Math.cos( ta );
				i += v * Math.sin( ta );
			}
 
			out[w] = Math.sqrt( r * r + i * i ) / len;
		}
 
		return out;
	};
} )( 64 );

При начальном создании:
sizeколичество наших гармоник (должно быть кратно 2),
полезных гармоник всегда на 1 меньше, т.к. первая гармоника (0 Hz) бесполезна для нашей цели


Возвращает функцию с параметрами:
dataмассив данных
lenего длинна


При вызове ее с данными звука, вернет массив длиной size с амплитудами гармоник.

Соответственно, пропускаем 0 значение из этого буфера (тот самый 0 Hz), а значения с 1 по size - 1 и есть высоты наших «палочек» от самой низкой гармоники (басы) до самой высокой (писк).

Ну и используя наш опыт WEB Audio API и его ScriptProcessor - демка на 64 гармоники (заодно можно увидеть, почему самая первая гармоника нам не нужна - после нормализации ее амплитуда всегда 0):

играть


Зная вот эти алгоритмы аппроксимации, переложить этот код в код однокристалки не составит труда (обычно ограничения там в том, что числа целочисленные и доступны только действия +-*/).

08.01.2015, Protocoder
Protocoder21.01.2015 16:48:57#ответить
Подправил работу в WebKit-ах (Chrome, Safari и т.д.)
Написать комментарий