LINUX.ORG.RU

[java] универсальное fft/dft

 


0

1

Хочу попробовать сделать анализатор спектра.

Исходные данные: дискретизированная функция без жёстко заданного шага дискретизации (шаг вычисляется перед дискретизацией, но постоянен). Дискретизированные значения хранятся в списке List<Sample> samples, где Sample — класс приблизительно такого вида:

public class Sample {
    private double x, y;
    public Sample(double _x, double _y)
    {
        x = _x;
        y = _y;
    }
    public double getX()
    {
        return x;
    }
    public double getY()
    {
        return y;
    }
}

Необходимо получить спектр по этим отсчётам в виде аналогичного списка классов с двумя полями — частота и значение мощности.

Если есть готовые решения — готов изучить, в том числе на C/Pascal. Стандартные функции для частоты дискретизации fд=2*Fmax не предлагать.

Ответ на: комментарий от Eddy_Em

Ява — без вариантов. А библиотеку почитаю, спасибо.

post-factum ★★★★★
() автор топика
Ответ на: комментарий от Eddy_Em

И не советую использовать яву - тормозить же будет жутко...

Если писать в си-стиле, то не будет. Но это довольно сложно, большинство жава-девелоперов на такое не способны.

dizza ★★★★★
()
Ответ на: комментарий от vertexua

Ключевое в моём вопросе — понятный алгоритм преобразования при шаге дискретизации, отличном от 1/2Fmax.

post-factum ★★★★★
() автор топика
Ответ на: комментарий от post-factum

Так это же просто: было у вас N отсчетов с шагом t секунд. БПФ даст нам те же N отсчетов, но на весь диапазон отчетов будет приходиться диапазон частот в 1/t Гц (т.е. шаг по частоте будет равен 1/(Nt) Гц). Т.е. если у вас на БПФ пик приходится на K отчетов, то основная гармоника сигнала попадет на частоту K/(Nt) Гц.

Eddy_Em ☆☆☆☆☆
()
Ответ на: комментарий от Eddy_Em

Да, а смысл двойки в теореме Котельникова-Найквиста в том, что несмотря на то, что на весь диапазон БПФ приходится \nu_m = 1/(Nt) Гц, вы не сможете отличить частоту \nu_1 от частоты \nu_m - \nu_1. Т.е. надо быть уверенным, что частоты сигнала не превосходят \nu_m/2.

Eddy_Em ☆☆☆☆☆
()

Если есть готовые решения — готов изучить, в том числе на C/Pascal. Стандартные функции для частоты дискретизации fд=2*Fmax не предлагать.

Java + FFT это на грани троллинга =)

понятный алгоритм преобразования при шаге дискретизации, отличном от 1/2Fmax

Куча вопросов сразу - тебе в реалтайме надо? Какая задача, я не понимаю зачем это может потребоваться... Но такие проблемы можно решить интерполяцией, или я не так понял?

I-Love-Microsoft ★★★★★
()
Ответ на: комментарий от Eddy_Em

Это, получается, нужно гармошку частот либо разжать, либо сжать? Лучше, конечно, такое объяснение понятно закодировать, например, в Си.

post-factum ★★★★★
() автор топика
Ответ на: комментарий от post-factum

Если вам просто надо по дискретной равномерной временной сетке сигнала построить спектр - нет ничего проще. Рассчитываете шаг по частоте (как я выше привел), делаете БПФ, «отрезаете» от него левую половинку и выводите на экран.

Eddy_Em ☆☆☆☆☆
()
Ответ на: комментарий от post-factum

realtime fftw3, кстати, довольно быстро считает: у меня на слабенькой машинке получалось вычислять смещение объекта по корреляционной функции со скоростью 25 кадров в секунду на фрейме до 256х256.

Eddy_Em ☆☆☆☆☆
()
Ответ на: комментарий от vertexua

По моим субьективным сравнениям БПФ в GSL выполняется медленнее, чем в fftw3 (а я выбирал именно наиболее скоростную - для realtime'а).

Eddy_Em ☆☆☆☆☆
()
Ответ на: комментарий от Eddy_Em

А как в данном случае сравнение может быть субьективным? Или числа, которые обьективны, или нет чисел

vertexua ★★★★★
()
Ответ на: комментарий от vertexua

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

Eddy_Em ☆☆☆☆☆
()
Ответ на: комментарий от Eddy_Em

Так это же просто: было у вас N отсчетов с шагом t секунд. БПФ даст нам те же N отсчетов, но на весь диапазон отчетов будет приходиться диапазон частот в 1/t Гц (т.е. шаг по частоте будет равен 1/(Nt) Гц). Т.е. если у вас на БПФ пик приходится на K отчетов, то основная гармоника сигнала попадет на частоту K/(Nt) Гц.

Не вводите в заблуждение людей, ДПФ не считает «спектр» сигнала. Для чистого ДПФ нет зависимости между пиком отсчёта и основной гармоникой. Это на самом деле совсем не просто и без основ ЦОС здесь ничего хорошего не сделать.

mashina ★★★★★
()
Ответ на: комментарий от mashina

> Не вводите в заблуждение людей, ДПФ не считает «спектр» сигнала.

А что он считает, интересно? Я всегда думал, что как не передискретизовывай интеграл \int f(t) \exp(-iwt) dt все получится то или иное приближение к ПФ.

annoynimous ★★★★★
()
Ответ на: комментарий от mashina

Не вводите в заблуждение людей

Ну, звиняйте. Если ДПФ не дает спектра, значит, надо все учебники выкинуть...

Eddy_Em ☆☆☆☆☆
()

В общем, всем спасибо, я тут включил мозг и написал нужную библиотеку сам. Кому интересно — стучите, дам код.

post-factum ★★★★★
() автор топика
Ответ на: комментарий от Eddy_Em

На Java, да. Быстродействие на высоких частотах не радует, особенно ввиду используемого алгоритма.

post-factum ★★★★★
() автор топика
Ответ на: комментарий от post-factum

У меня на одноядерном селероне (2.5ГГц) на сях скорость была достаточно высокой: участок видео 128х128 пикселей фильтровался вейвлетами, а затем вычислялась его КФ (т.е. 1 прямое + 1 обратное 2D вейвлет-преобразование с промежуточной «подчисткой» ВЧ гармоник + 1 прямое + 1 обратное БПФ с промежуточным перемножением на образ опорного кадра).

Так что, про тормоза явы не зря легенды ходят :)

Eddy_Em ☆☆☆☆☆
()
Ответ на: комментарий от Eddy_Em

Я думаю, здесь вопрос не в тормозах явы, а в том, как я делаю преобразование.

Используемый алгоритм по сути — сплав генератора качающейся частоты и коррелятора. Чем больше окно частот преобразования, тем медленнее оно работает. С другой стороны, на высоких частотах для отрисовки строить спектр с шагом 1 Гц не надо, там и 100 Гц — нормальный шаг, работает приемлемо. Конечно, для риалтайма не катит, но у меня такая задача и не стоит.

post-factum ★★★★★
() автор топика
Ответ на: комментарий от annoynimous

А что он считает, интересно? Я всегда думал, что как не передискретизовывай интеграл \int f(t) \exp(-iwt) dt все получится то или иное приближение к ПФ.

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

mashina ★★★★★
()
Ответ на: комментарий от mashina

просто ДПФ не даёт результата, который ожидают от понятия спектр.

Точно так же, как и дискретный сигнал очень далек от реального аналогового.

Eddy_Em ☆☆☆☆☆
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.