Вейвлеты, что, зачем, как Опции

[1ns1d3r]

Здравствуйте.
Возможно кто-то сталкивался в вейвлетами и может ответить на несколько вопросов?

1. С какими целями можно применять анализ с помощью вейвлетов в радиоэлектронике?/какую инфу получаем, какой практический смысл?/

2. Посоветуйте литературу по теме /в которой были бы описаны методы анализа и что нам они дают/

[sidy]

Всем доброго времени суток. Меня интересует такой практический вопрос для случая сжатия статических изображений. В случае вейвлета Хаара вычисляется полусумма и полуразность между двумя соседними пикселями. А каков алгоритм в случае вейвлета Добеши? Говорят, что вейвлет Добеши использует больше чем два соседних пикселя. Можно рассказать об этом более подробнее? Спасибо.

Сообщение отредактировал sidy - Mar 29 2010, 16:53

[roscha]

Всем доброго времени суток. Меня интересует такой практический вопрос для случая сжатия статических изображений. В случае вейвлета Хаара вычисляется полусумма и полуразность между двумя соседними пикселями. А каков алгоритм в случае вейвлета Добеши? Говорят, что вейвлет Добеши использует больше чем два соседних пикселя. Можно рассказать об этом более подробнее? Спасибо.

Для сжатия статических изображений лучше (и на практике широко используется) биортогональный вейвлет.
Алгоритмом Моллата двумерный вейвлет сводится к последовательности одномерных. В результате получаются блоки вейвлет-коэффициентов.
Если сжатие с потерями, то вейвлет-коэффициенты поблочно подвергаются дополнительному квантованию.
Наконец, независимо от того, с потерями сжимаем или без потерь, совокупность вейвлет-коэффициентов подвергается энтропийному кодированию,
например, кодированию длинных серий (RLE - run-length-encoding) и Хаффмана.

[DRUID3]

Всем доброго времени суток.

Sieg Heil!

Меня интересует такой практический вопрос для случая сжатия статических изображений.

В случае вейвлета Хаара вычисляется полусумма и полуразность между двумя соседними пикселями.

А в случае 2-х точечного FFT(DFT) не так? Вся эта магия "Хаара" есть толко для 2-х точек - очевидно, что для любого подобного рода разложения мы ищем корреляцию с каждой, отдельно взятой из определенного набора(базиса), функцией на том или ином интервале. Этот алгоритм практически сводится к FIR с добавлением масштабирования - иначе значения будут бессмысленны. Но для семейства Хаар-Добеши-"Биортогонал" - по-сути имеющих одну природу - принцип построения базиса(с дополнительными требованиями упрощение формулы разложения/реконструкции и линейности ФЧХ соответственно), преобразование сводится, в общем случае, к децимация->FIR для одной подветки->на выходе - тот или иной коэффициент DWT,децимация для другой... и т.д. пока длинна функции для FIR не станет равна длине его самого. И только в частном случае - в случае 2-х точечной длинны FIR Хаар и Добеши сведутся к тем или иным блочным суммам. И только потому что децимация так "уродует" 2-х точечный FIR.

А каков алгоритм в случае вейвлета Добеши?

Вообще-то они родные братья...

Говорят, что вейвлет Добеши использует больше чем два соседних пикселя. Можно рассказать об этом более подробнее? Спасибо.

Дак и "Хаар" и "биортогонал" могут быть сколь угодно длинными изначально...

Bitte, gesundheit...

Для сжатия статических изображений лучше (и на практике широко используется) биортогональный вейвлет.

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

Алгоритмом Моллата двумерный вейвлет сводится к последовательности одномерных.

А можно по-подробнее, просто не встречал определение еще... Или это кто-то переоткрыл способ многомерного интегрирования-суммирования в Декартовом "мире" и назвал в честь себя?

В результате получаются блоки вейвлет-коэффициентов.

логично ...

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

...именно на сжатии с потерями вейвлеты обходят любых конкурентов по соотношению качество(сумма субъективных оценок)/размер картинки или ролика.

Наконец, независимо от того, с потерями сжимаем или без потерь, совокупность вейвлет-коэффициентов подвергается энтропийному кодированию,
например, кодированию длинных серий (RLE - run-length-encoding) и Хаффмана.

Причем зачастую в одной и той же операции с отбрасыванием незначимых коэффициентов DWT. И иногда в исходнике вообще не поймешь что хотел сказать аФФтАр.

P.S.: это все есть в книжонках которые я порекомендовал, не ленитесь скачайте(купите бумажную, как вариант) их и прочтите хоть самую тонкую...

[Xenia]

...он [биортогональный вейвлет] конечно лучше - по той простой причине, что из самого своего определения имеет линейную ФЧХ. Потому для высококачественного видео

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

[DRUID3]

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

Не прошло и 3-и года... Но все-таки... А нужны именно биортогонал? Или именно jpeg2000? Или простые вейвлеты типа Хаара?

[Xenia]

А нужны именно биортогонал? Или именно jpeg2000? Или простые вейвлеты типа Хаара?

Признаюсь, что в теории вейвлетов не сильна. Но насколько я понимаю, биортогонал мне не нужен. И, вероятно, jpeg2000 тоже. Скорее всего, мне нужен классический вариант типа Хаара. Однако видимо, будет лучше, если я вам расскажу о специфике своей задачи, а уж вы в ответ сами решите, который способ мне можно рекомендовать.

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

Значит так. АЦП измеряет напряжение на своем входе всегда с одной и той же периодичностью (обычно это 50Гц, чтобы меньше сказывались сетевые наводки). Долгое время "ничего нет", т.е. на входе присутствует некий постоянный шум или медленный дрейф ("базовая линия"). И вдруг внезапно "выходит" пик - сигнал гауссообразной формы со слегка заметным "хвостом" (задний фронт более пологий, чем передний, тогда как гауссиана полностью симметрична). Обычно за 20-60 секунд входное напряжение успевает достигнуть локального максимума, а затем снова сходит до уровня базовой линии. И так процесс продолжается от нескольких часов до суток с небольшим.

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

Соотношение времени, когда выходят пики, ко времени, когда "ничего нет", 1:1000 или даже больше. А интерес, как можно догадаться, представляют именно пики (их форма и время появления), а вовсе не базовая линия. Файл же с такой записью получается очень длинным (до десятка, а то и сотни гигабайт), когда полезной информации в нем все та же 1/1000.

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

Про целочисленность алгоритма я, возможно, заикнулась зря. Если нельзя, то и не надо. Тут я имела в виду, что все замеры у меня целочисленные, т.к. их продуцирует АЦП. Но я понимаю, что в таких задачах без плавающей арифметики обойтись сложно.

Я не настаиваю на вейвлетах, но, к сожалению, не знаю ортогональных разложений, которые бы экономно аппроксимировали сумму гауссиан с центрами в разных точках.

[Oldring]

Первое, что приходит в голову, - вырезать участки, содержащие пики, и хранить только эти участки, с указанием времени или номера точки, с которого тот участок начинается.

А вам какую именно информацию можно потерять? Потому что вейвлетами сжимают с потерями.

Первое, что приходит в голову - уменьшить частоту оцифрорвки раз тах в 50-100. У гауссового пика и спектр тоже гауссов, поэтому на расстоянии в несколько сигм от средней частоты информации уже нет.

Второе, что приходит в голову - это, действительно, детектирование отсутствия пика. С фиксированным порогом, наверное.

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

[Xenia]

А вам какую именно информацию можно потерять? Потому что вейвлетами сжимают с потерями.

Мне это известно, и я готова к тому, что будут потери. Тем не менее, мне бы хотелось аппросимировать пик псевдогауссовой формы как можно меньшим числом взаимноортогональных функций.

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

По моим представлениям, вейвлеты способны довольно сносно аппроксимировать гауссиану, благодаря тому, что снижают необходимость "подавления" паразиных вкладов, вдали от ее центра. Это происходит из-за того, что базисные функции вейвлета угасают сами собой с ростом расстояния, а гармоники нет. Отсюда и мои надежды на то, что для достижения 95% мне понадобиться гораздо меньше базисных функций вейвлета, чем гармоник.

P.S. Остальные ваши предложения мне не понравились , но я опасаюсь аргументировать свой отказ из-за того, что боюсь соскальзования темы в другую колею.

[DRUID3]

Вот так. Поленился, не ответил сразу, а "желтая стрела" жизни стремительно ушла вперед... Итак...

Мне это известно, и я готова к тому, что будут потери.

Меня пугает эта Ваша готовность. Может потому сам такой уже старый, а не научился безболезненно переживать потери... Но если серьезнее то, согласен с многоуважаемым Oldring'ом, думаю Вам скорее бы подошел вот такой способ...

Тем не менее, мне бы хотелось аппросимировать пик псевдогауссовой формы как можно меньшим числом взаимноортогональных функций.

Эх... Этот водоворот жизни и вечный наш поиск "чего-то там, за горизонтом"... Идея на-лету... Дифференциатор запускает коррелятор в котором только одна функция (вуалая) - гауссова .

Например, если я сделаю Фурье-преобразование и взгляну на частотную форму, то увижу, что при гауссовом исходном сигнале продукт будет выглядеть как медленно ниспадающая экспонента. Если мне захочется сохранить 95%, а в жертву принести только 5%, то я слишком мало смогу от той экспоненты отрезать. Зато если бы мой сигнал был периодической формы, то фурье-образ оказался бы очень подходящим продуктом - небольшим (выборочным) числом членов этого ряда я могла бы легко набрать эти 95%. А вот гаусс-кривую мне сделать малой кровью не удастся - членов ряда придется брать очень много...
... По моим представлениям, вейвлеты способны довольно сносно аппроксимировать гауссиану, благодаря тому, что снижают необходимость "подавления" паразиных вкладов, вдали от ее центра. Это происходит из-за того, что базисные функции вейвлета угасают сами собой с ростом расстояния, а гармоники нет. Отсюда и мои надежды на то, что для достижения 95% мне понадобиться гораздо меньше базисных функций вейвлета, чем гармоник.

"Вейвлетов" не меньше... Особенно чем дальше материнский вейвлет от гаусовой функции тем большее количество ненулевых векторов приходится использовать, представляя сигнал как их суперпозицию. И здесь Oldring уже приуспел в пояснении...

P.S. Остальные ваши предложения мне не понравились , но я опасаюсь аргументировать свой отказ из-за того, что боюсь соскальзования темы в другую колею.

Признаюсь, что в теории вейвлетов не сильна.

Так и я вообще-то даже не вейвлет-падаван... Юнглинг...Где-то так... Прочел брошюру, да книжечку пролистал...

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

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

Но насколько я понимаю, биортогонал мне не нужен. И, вероятно, jpeg2000 тоже. Скорее всего, мне нужен классический вариант типа Хаара. Однако видимо, будет лучше, если я вам расскажу о специфике своей задачи, а уж вы в ответ сами решите, который способ мне можно рекомендовать.
...
Про целочисленность алгоритма я, возможно, заикнулась зря. Если нельзя, то и не надо. Тут я имела в виду, что все замеры у меня целочисленные, т.к. их продуцирует АЦП. Но я понимаю, что в таких задачах без плавающей арифметики обойтись сложно.

Хаар по идее своей целочисленный. Да и всякие там Добеши и остальные масштабировать к int не особая проблема. Но все-таки Хаар - самая простая (тривиальная) реализация(кстати потому его очень любят ПЛИСеры), и плюс целочисленность...

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

Вы разбили мне сердце...