День добрый знатоки всяких разных преобразований из time domain в frequency domain!

Извиняюсь за вероятное ламерство вопроса!
Я начинающий в этом деле! Само преобразование меня нисколько не смущает и не пугает, закодить ео если что смогу! Мне интересно другое! Интерпретация результатов таких преобразований!

К примеру БПФ!
Решил зажать песню к слову! Беру первые 512 выборок! БПФ вернет мне 512 комплексных значений (амплитуда и фаза).. так?
И вот собственно вопросы..
- амплитуды каких частот это будут?
- или это еще не готовые амплитуды и еще что то нужно сделать?
- что делать с фазами? (а то как то вместо 512 чисел уже 1024 нарисовалась для хранения)
- как интерпретировать вообще эти результаты и понять какие данные можно выкинуть что бы потом восстановить без ощутимых для слуха потерь? (понимаю /*надеюсь что правильно понимаю*/ что по амплитудам смотреть.. но как уже говорил для меня загадка какие частоты находятся в ответе..)

Может можно пример привести конкретный! Типа вот 8 вхдных значений.. вот 8 выходных и т.п. Такие то игнорим и сохраняем место таким образом..
Или где такой пример можно глянуть?


Спасибо!

Вот покапался у вас и нашел ссылочку
http://www.dsp.sut.ru/book/lections/l4/l4_4.htm

Там есть раздел: практический пример.

Ответ про отбрасывания значений начинаяя от N/2 прочитал!

И про вычисление амплитуды SQRT(real^2 + img^2).. вроде так?
И про распределение частот в выходном массиве тоже вроде понял!

Но не пойму все еще что делать с фазами? За счет чего получится сжатие?

Раз N/2 значений игнорим то остается еще N/2 (комплексных) которые и займут по размеру столько же сколько N входных значений!
Или сжатие будет за счет того что в оставщихся N/2 значениях слабые частоты (и их фазы) можно просто занулись и эффективней сохранить уже использую обычные алгоритмы сжатия?

И сорри! Не покАпался, а покопался
Совсем забываю следить за грамотностью в инете!!

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

Это сообщение отредактировал(а) maxim1000 - 8.4.2004, 11:53

Если нравятся время-частотные преобразования, то сжимать можно вейвлетами.

Максим1000

Не ну понятно что не дает! Я именно к тому как можно частотную информацию обработать дабы зажать лучше! Вот и спрашивю за счет чего же таки сжимают и как правильно что отбросить что бы потери в качестве не были слышны

Более того еще вопрос! Результаты ведь вещественого типа? Ничего если я до целого буду округлять? Слышал про целочисленные преобразования фурье! Они округляют или вообще с целыми работают?

Спасибо!

Podval

С вейвлетами еще не ковырялся! Может и с ними все организую! Спрашивать если что у тебя можно?

Дело насколько я знаю обстоит немного сложнее.
Есть целая теория насчёт того, что человеческое ухо не воспринимает частоты A, если амплитуда частоты B больше на N (существуют таблицы). Такие значения можно сажать на ноль. в итоге получим много нулей подряд.
Ещё: не вероятно, что в сигнале присутствуют ВСЕ возможные частоты, которые воспринимает человеческое ухо. За счёт этого нам становатся не нужны все биты значений оригинального сигнала.

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

Сергей спасибо!

В мп3 они насколько я знаю именно так и делают.. это кацца masking нзывается! (только они не по всему спектру сразу смотрят а более детально по 32м диапазонам если не ошибаюсь)
По поводу того что это сожнее.. я ни на миг не сомневаюсь! Нужно ж по идее понимать где эти частоты во времени находятся что бы сказать происходит ли этот эффект скрытия или нет! %)

Товарисчи!
Еще комментарии будут? Или идеи по написанию революционного компрессора ))


Как закодю Держитесь

Цитата(dwr_budr @ 8.4.2004, 22:00)

Podval С вейвлетами еще не ковырялся! Может и с ними все организую! Спрашивать если что у тебя можно?

Нужно!

И еще рекомендую зарегистрироваться на форуме, появятся полезные возможности.
Добавлено @ 12:02

Цитата

Слышал про целочисленные преобразования фурье! Они округляют или вообще с целыми работают?

Именно работают! И кстати, не только преобразование Фурье, есть и другие целочисленные.

2Podval

Да не вопрос зарегюсь Точнее я уже регился когда то Просто забыл пароль! И лень было его заново получать

Как поживает супер-кодек?
Я тут подумал..
Ты же поток разбиваешь на части-окна и анализируешь спектр окна. Тут то ИМХО маскинг применять и надо. То есть исходишь из того, что все частоты в окне имеют место одноврменно и маскируешь.
Реализацию в вейвлетах не встречал, так что должно быть что то принципиально новое. Попробовать в любом случае стоит! Кстати, podval, как ты думаешь, принесёт что нибудь Zero-Tree в однодимензиональном сигнале?

2 sergej.z

Поживает :)
Завтра преподу план проекта несу :)
А через недельку начну кодить собственно!
Только FFT вероятно не буду использовать. Игрался с ним и после обработки каждого интервальчика в частотном виде при склеивании на границах получались счелчки..
Как их сглаживать я не знаю (поделитесь если кто знает)

Зато вычитал про MDCT (midified discrete cosine transform). В нем преобразование по своей природе мы делаем на нахлестывающихся друг на друга интервалах, и следовательно в этом факте само сглаживание и заложено! (поправьте если неправ.. лучше знать о неверном предположении заранее :)

Ну а дальше буду разбивать на поддиапазоны и применять маскинг! Как частотный так и временной! (ждите в скорем времени много вопросов :)

Потом квантование и что нить типа адаптивного хаффмана! (это пока такие мысли)

В догонку хочется что б сам формат был фреймованный и игрался как мп3 с любогоместа.. но не думаю что я все успею до 10го июня :)

PS Кстати MDCT как раз в mp3 и используется.. да и в Vorbis'е тоже если ничего не напутал читая :)

Цитата

Только FFT вероятно не буду использовать. Игрался с ним и после обработки каждого интервальчика в частотном виде при склеивании на границах получались счелчки..

Цитата

Зато вычитал про MDCT (midified discrete cosine transform). В нем преобразование по своей природе мы делаем на нахлестывающихся друг на друга интервалах, и следовательно в этом факте само сглаживание и заложено!

ни FFT, ни DCT понятия не имеют обо всем сигнале, на их вход подается просто сигнал фиксированной длины, никто не запрещает подавать на вход FFT кусочки с перекрытием

Цитата

Потом квантование и что нить типа адаптивного хаффмана!

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

Цитата

В догонку хочется что б сам формат был фреймованный и игрался как мп3 с любогоместа.. но не думаю что я все успею до 10го июня

достаточно сделать так, чтобы ошибка, случайно возникшая где-то всередине, достаточно быстро затухала

Цитата(sergej @ 22.4.2004, 00:59)

Кстати, podval, как ты думаешь, принесёт что нибудь Zero-Tree в однодимензиональном сигнале?

А что именно ты хочешь спросить? Только по-русски

Как Zero tree по русски.... ??

Существует ведь Z-Tree в вейвлет - кодирование картинки (двухдимензионального сигнала).




Та же Лена



Я эксперементировал с сигналами и "Haar trandformation", но ничего, Где можно было бы применить Z-Tree, не получилось. Но ведь как-то это возможно..

2 maxim1000

FFT vs DMCT
Я понимаю что ни FFT ни DCT не знают о сигнале! Но мне непонятен следующий аспект!

В MDCT все просто. Взял 1024 выборки. С 0й по 1023ю и получил 512 частот.
Дальше еще 1024 теперь с 512й... снова 512 частот. Каждый раз полноценные 512 частот.
Т.е. выходная размерность всегда будет в 2 раза меньше входной!
Таким образом пройдя через весь файл мы обработали 2N элементов, а в ответ получили N элементов!

А как с FFT? Обсчитали 1024 выборки.. получили 1024 комплексных рузультата! Из них половина симметричная! Т.е. 512(+1) комплексных результатов! Т.е. по сути 1024 числа! И если мы будем обсчитывать в нахлест, то на 2N входных значение получим 2N выходных. Сам себе взял и увеличил объем данных которые нужно будет хранить :) Доперекрывался я называется :) Как с этим быть?



Адаптивный хаффман.
Я осознаю насколько это медленно постоянно обновлять дерево. Но раскодирование файла в реальном времени думаю даже тормозной адаптивный хаффман будет успевать делать. (+ overhead не нужно будет хранить)
Но опять таки это пока идея. Может подойдя к фазе упаковки я осознаю, что мне будет удобнее что-нибудь другое! Спасибо за комментарий повышающий бдительность :)
Поводу скорости. Самая первая версия сего супе пупер кодека будет дико медленная :) Тот же MDCT я написал в лоб. Но безусловно потом такие моменты перепишу более быстро.


Ошибка.
Можно тут подробнее? Просто я вижу поток битов и если будет ошибка пострадает лишь один фрейм. А что ты имеешь в виду под затуханием?

sergej.z

Цитата

Как Zero tree по русски....   ??

Я это понимаю

Так ты хотел применить к одномерным сигналам?

Цитата

Так ты хотел применить к одномерным сигналам?

Ну конечно! Ёлы палы, Чего то у меня с теминами не того

PS:Я так понимаю Z-Tree подходит лишь для низкочастотных сигналов или нет?

Цитата

В MDCT все просто. Взял 1024 выборки. С 0й по 1023ю и получил 512 частот.

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

Цитата

Ошибка. Можно тут подробнее? Просто я вижу поток битов и если будет ошибка пострадает лишь один фрейм. А что ты имеешь в виду под затуханием?

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

Цитата(sergej @ 24.4.2004, 03:50)

PS:Я так понимаю Z-Tree подходит лишь для низкочастотных сигналов или нет?

Моя твоя не понимай
А здесь ты что хотел сказать?

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

Из книжки:

Цитата

Из теории кодирования с погрешностью известно, что оптимальное рас- пределение бит достигается в случае, если сигнал поделен на субполосы, содержащие «белый» шум. Для реальных сигналов это достигается в случае неравномерной ширины субполос: в области НЧ они более узки, чем в облас- ти ВЧ. Вот почему вейвлет-преобразование обеспечивает компактность энергии. Эта компактность энергии ведет к эффективному применению скалярных квантователей. Однако они не учитывают остаточную структуру, сохраняю- щуюся в вейвлет-коэффициентах, в особенности ВЧ субполос. Современные алгоритмы сжатия все тем или иным образом используют эту структуру для повышения эффективности сжатия. Одним из наиболее естественных способов является учет взаимосвязей между коэффициентами из различных субполос. В высокочастотных субпо- лосах имеются обычно большие области с нулевой или малой энергией. Об- ласти с высокой энергией повторяют от субполосы к субполосе свои очерта- ния и местоположение. И это неудивительно – ведь они появляются вокруг контуров в исходном изображении – там, где вейвлет-преобразование не мо- жет адекватно представить сигнал, что приводит к «утечке» части энергии в ВЧ субполосы. Медленно изменяющиеся, гладкие области исходного изо- бражения хорошо описывают НЧ вейвлет-базисы, что приводит к «упаковке» энергии в малом числе коэффициентов НЧ области. Этот процесс примерно повторяется на всех уровнях декомпозиции, что и приводит к визуальной «похожести» различных субполос. Итак, априорное знание о том, что изображение состоит из гладких об- ластей, текстур и контуров, помогает учитывать эту межполосную структу- ру. Кодеры, использующие структуру нульдерева, сочетают учет структуры коэффициентов с совместным кодированием нулей, в результате чего полу- чается очень эффективный алгоритм сжатия.

А теперь скачивай книжку .

2 maxim1000

Вoт по этой ссылке я собственно mdct делал
http://en.wikipedia.org/wiki/Modified_disc...osine_transform

Кра-а-а-тенькое описание:

Прямое преобразование:
2n элементов на входе дают n элементов на выходе.
Поэтому пересчет нахлестывающихся промежутков не грозит увеличением данных

Обратное преобразование:
n входных жлементов дают 2n выходных
Однако выходные 2n элементов не равны входным (как ты и подозревал :)
Поэтому нахлестывающиеся промежутки выходных 2n элементов нужно еще в добавок сложить. Тогда получаются оригинальные значения.

Правда самые первые 0...n элементов не востановятся ровно как и последние mn...(m+1)n так как не с чем они не перехлестываются, но ничего нам не мешает дополнить входной сигнал чуток с обоих сторон дабы был нахлест :)


А за комментарии про ошибку спасибо :)

Это сообщение отредактировал(а) dwr_budr - 24.4.2004, 21:52

Люди.
скажите вот что.
Когда мы сделали преобразование Фурье, у нас на выходе значение амплитуд sin и cos(реальная и мнимая часть). А теперь по какой формуле производиться преобразование в парe: амплитуда у синуса и фаза.

Если я не ошибаюсь, то амплитуда находится 2*sqrt(x[i]^2 + y[i]^2)/N

Фаза = arctan(Im/Re)
Амплитуда = sqrt(Re^2 + Im^2)

Вроде так