Как с MathNet.Numerics уменьшить число коэффициентов у преобразования Фурье?

Question

[SergeySerge11]

Что за ерунда, уже бибилотек 10 проверил, почему все так однообразно все делают. И ни какого функционала не дают. Я делал, вроде ыче понятно, вижу смысл, куда применить. Но решил эти "Быстрые алгоритм Фурье " посмотреть. И не могу понять а зачем они(конкретно так как в 4 библиотеках что знаю). Опишу подробно.
Все что хочу, это упоковать 10на10 байтов в 10на2 к примеру? xЧто возможно с помощью моей нативной реализации. А в этих супер крутых библиотеках нету просто функционала, при том во всех топовых библиотеках так.

Fourier.Forward(data);  //mathnet-numerics
// во всех библиотеках, так  плюс там какие параметры. опять из которых информации ни какой. На вызоде РОВНО ТАКОЙ же массив. То есть пространство ХУ свернули в ТАКОГО ЖЕ размера пространства, даже в 2 раза больше(за счет того что комплексные числа). Типа а Где сжатие информации?

Типа и все и и ни куда ни как.
К примеру хоть и за О(n*n) времени, сумел реализовать. И вполне приемлемо не теряя качества особо могу в 1мб упаковать 50КБ.
Я что-то не понимаю. В чем разница Быстрого преобразования, что на выходе выходит? Почему у меня не получается применить к массиву результата, то же самое, что я делаю к примеру при обычном преобразовании фурье.


Вот типа вот такое я получаю. Но это же вроде ожно и то же что и быстрое преобразование? Или нет? "Быстрое преобразование" это же как "Быстрая сортировка" аналогия,просто скорость или вообще что-то из другой сферы????
Потому что, если я получаю "быстрым преобразованием" то же самое. Т я это не могу, закинуть в
+=A*cos(i*n*x/T)+B*sin(...) ??? Но у меня не сходиться значения. Значит это какие разные коэффициенты. Или я обязан делать "обратное преобразования".
А тогда какой смысл в обычном преобразовании????
Я понимаю смысл, вот как у меня реализовано, и как примеры в Эксель. Где X*Y допустим 100*100 превращаться в 100*4 данных. Но не когда 100x100 d 100x100x2.
Либо я что-то не знаю.

Comments

[res2001]

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

Как делают сжатие с помощью БПФ я не в курсе.

[freeExec]

могу в 1мб упаковать 50КБ

Я что-то не понимаю.

Answer 1

[Wataru]

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

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

И да, там результат - это массив комплексных чисел, поэтому выходные данные в 2 раза больше входных, которые являются вещественными.

Comments

[SergeySerge11]

ну так я делаю.
Но вот только моя реализация в Лоб которая, вроде как вполне рабочая, почему-то н Очень сильно не совпадает по преобразованию со всеми библиотеками. То есть xn=>Xk какое-то другое. Но обратно восстановляет
Очевидно. Что любая Реализация преобразует хn => Xk . Хк должно быть независимо от алгоритма одно и то же. То есть я могу из любого дискретного преобразования (любой реализации, библиотеки) взять эти данные.
И произвести обратное.
Но у меня так не выходит.

[Wataru]

SergeySerge11, значит, у вас ощибка в реализации. Сравните несколько библиотек между собой - они-то совпадают?

[SergeySerge11]

Wataru, ошибка точно есть,. Но почему-то не всегда проявляется. При Генерации рандомной последовательности .к примеру MSE большая.
Вот например реализовал этот пример https://excel2.ru/articles/mnk-priblizhenie-trigon...
При том 100% как в статье, данные совпадают.
Логичный Вывод -> в статье Ошибка, но где?
ЛОЛ пока писал коммент, обратил внимание, что это не совсем Фурье из ссылки. Точнее это приближение тригонометрическим полиномом, то есть я Один Функционал решений перенес на другой. Поэтому и надумал себе нестыковок разных.

Answer 2

[mayton2019]

Игнорируй младшие коэффициенты - вот и будет сжатие. Так оно и работает. Честно-честно.

Comments

[res2001]

Ну как-бы да, но в результате появляется еще и мнимая часть (комплексные числа), о чем автор писал. Так что сжатия реально нет, т.к. вместо одного числа появляется 2.

[mayton2019]

Автор смешал в кучу несколько разных тем. Сжатие. Преобразование Фурье. И его оптимизация под названием БПФ.

Сжатие в том виде как оно реализовано в JPEG к примеру - чуть более сложное. Включает в себя квантизацию. Переход от вещественных чисел к целым. И кодирование их по хаффмену. Кроме того картинка подвергается стандартному издевательству над цветной графикой типа chroma subsampling которая основана вообще не на Фурье а на физиологии зрения. Вот поэтому в JPEG и получается сжатие.

[Wataru]

res2001, чтобы мнимой части не было, можно использовать целое дискретное преобразование или дискретное косинусное преобразование (что в jpeg и применяется).

[U235U235]

res2001, все так: из одного комплексного числа получается одно комплексное число. Если у вас функция действительная, то после Фурье будет комплексный результат. Но, результат будет симметричным! Комплекно-сопряженным. И для востановления достаточно половины данных.