Как 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)

Вроде так