Сходимость дискретного преобразования Фурье

[ИСН]

(Оффтоп)

Было, разумеется, я с этого и начал. А что? У Вас был план через непрерывное преобразование вывести клиента на какое-то противоречие? Так это слишком длинно. Он бы сорвался и уплыл, поверьте моему опыту.

[Otta]

(Оффтоп)

Зачем мне такие грандиозные планы. )) Все проще. Поскольку клиент в своих рассуждениях пытался опираться на непрерывное преобразование Фурье (по крайней мере, он так думал) и требовал "чего-то похожего", то и хотелось знать, чего именно. Тем более, заметьте, что на слова о непрерывном преобразовании Фурье и о дискретном он отзывается соответственно в отношении 100:0 (даже не беря в расчет правильность ответов). Это говорит о чем? О том, что такое дискретное, он не знает вообще. Если Вы хотели действовать не слишком длинно, имело бы гораздо больший смысл спросить его сразу определение дискретного преобразования Фурье. Он бы сразу сорвался и уплыл. Поверьте моему)) опыту.

И вообще, что за клуб рыболовов-любителей. ))
Расстроили Вы меня. Вот.

[ИСН]

(Оффтоп)

Ну извините.
Насчёт вопроса "что такое ДПФ" - я практически к нему и пришёл под конец. Впрочем, итог один.

[Igor_Dmitriev]

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

[provincialka]

Сначала надо дать определение, что такое в данном случае"лучше".

[Igor_Dmitriev]

Лучше приближает -- это кода для получения заданной точности надо меньше частот.

[nikvic]

Стал быть, что-то вроде сжатия данных с потерями?

[Евгений Машеров]

Не претендую на лавры Вольфа Мессинга, но, мне кажется, я понял, что интересует топикстартера. Нет ли каких-то условий, при которых коэффициенты ДПФ быстро убывают, аналогично скорости убывания в непрерывном случае в зависимости от существования k-тых производных (т.е. речь не о сходимости, а о быстроте убывания, вообще для ДПФ говорить о "сходимости" как-то странно).
Подозреваю, что речь идёт о сжатии изображений и т.п. сжатии с потерями, когда наличие разрывов порождает "высокочастотный дребезг", мешающий отбросить коэффициенты при этих частотах. Эмпирически выяснено, что, убирая разрывы, улучшаем сжатие (скажем, в JPEG используется косинус-преобразование взамен ДПФ/БПФ именно для повышения сжимаемости, устраняя разрывы на границах рисунка)

[nikvic]

Евгений Машеров в сообщении #747350 писал(а):

Эмпирически выяснено, что, убирая разрывы, улучшаем сжатие (скажем, в JPEG используется косинус-преобразование взамен ДПФ/БПФ именно для повышения сжимаемости, устраняя разрывы на границах рисунка)

Какие границы рисунка? Пазлы 8х8, и стыкуются они скверно...

[Евгений Машеров]

Вот как раз о границах "пазлов" речь и идёт. Если бы использовали двумерное БПФ - были бы разрывы на границах, где "повторение". А ДКП получается в предположении, что продолжается перевёрнутым квадратиком.

[nikvic]

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

[Евгений Машеров]

Я об убывании коэффициентов. Для ДКП, что предполагает чётность преобразовываемой функции, а для произвольного фрагмента 8х8 приходится мысленно его "достраивать" тремя зеркально отражёнными его копиями, чтобы получить чётность по обеим осям, удаётся получить быстрейшее убывание коэффициентов (именно за счёт того, что нет "разрывов на краях"), чем если бы использовали БПФ (ДПФ) с "достраиванием" копиями изображения. А чем быстрее они убывают - тем больше степень сжатия за счёт обнуления малых для заданного качества.

[Igor_Dmitriev]

Цитата:

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

Да, поняли всё правильно: мне надо, чтобы быстро убывали вклады частот.

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

[nikvic]

Igor_Dmitriev в сообщении #747771 писал(а):

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

Обрезание (старших коэф-в) - самое надёжное

Но желательно знать, откуда берутся "сигналы".

[Евгений Машеров]

(Оффтоп)

Лет уж скоро 30 тому, когда я был молодым, а jpeg совсем юным, мы с друзьями за рюмкой кофе придумывали, как оный усовершенствовать. Идея ускорить убывание коэффициентов весьма естественная, собственно, DCT там именно для этого - если рисунок (фрагмент 8х8, имеется в виду) продолжается трансляцией (а продолжается он неявно, по самой сути разложения в ряд Фурье), то на границе, вообще говоря, возникают разрывы, и коэффициенты убывают, как 1/n, где n номер частотной составляющей, а если продолжить, отражая на границе, то полученный фрагмент 16х16 можно рассматривать, как чётную по X и Y функцию без разрывов на краях, и убывание порядка $1/n^2$
Вот я и предложил вообще развернуть по кривой Пеано (ну, по пеаноподобной, строго говоря), вообще сняв вопрос о "продолжении на границах". Что, собственно, один из нашей компании сделал, правда, лишь в квадратике 8х8, а не по всему рисунку, как я предлагал, и даже получил некое улучшение (на коррекцию стандарта JPEG не потянуло, но кандидатскую он сделал). Полноценной оценки не было, не усилилась ли при этом "зернистость" (чего не было бы при развёртке по рисунку в целом, но для 8х8 весьма вероятно) - не проверяли.
Дальнейшее улучшение могло быть связано с устранением на полученной кривой разрывов, например, выявлением их, заменой самых крупных на 0 (или на среднее изменение по соседним точкам) с вынесением сведений о таких заменах в отдельный массив, содержащий точку разрыва и его величину, который сопровождает в сжатом файле массив коэффициентов разложения (возможно, также сжатый, хотя бы RLE или там Хаффманом). При этом для того, чтобы последняя точка вернулась бы к первой, надо ещё вводить "дрейф", равный сумме разрывов, делённой на общее число точек. (Это реализовано не было).
Ну и возможности использовать для сжатия наличие трёх цветовых каналов (как правило, коррелированных) и, для сжатия видео, предыдущий (-ие) кадр(-ы) весьма вкусная, но ничего сколько-нибудь проработанного у нас не было (разностное представление, разве что)
Впрочем, до изделия не довели. Если Вам чем-то поможет - буду рад.