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

[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 не особая проблема. Но все-таки Хаар - самая простая (тривиальная) реализация(кстати потому его очень любят ПЛИСеры), и плюс целочисленность...

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

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

[Xenia]

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

Хорошо. Путь будет Хаар . А где его взять?

[Oldring]

Хорошо. Путь будет Хаар . А где его взять?

Кхм... Здесь.
http://ru.wikipedia.org/wiki/%D0%94%D0%B8%...%BD%D0%B8%D0%B5

[DRUID3]

Кхм... Здесь.

Говеннейшая реализация... Хотя вообще-то это образовательный материал и ему незачем соответствовать каким-то иным запросам кроме наглядности...

[Oldring]

Говеннейшая реализация... Хотя вообще-то это образовательный материал и ему незачем соответствовать каким-то иным запросам кроме наглядности...

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

[Xenia]

Мне кажется, коллега в состоянии реализовать Хаара и самостоятельно по этой статье с нужной степенью качестве.

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

Давайте-ка я вам дам на словах QL-алгоритм диагонализации симметричных матриц , и посмотрю как вы споро программку на С++ по моим словам накропаете, и сколько в ней будет ошибок.

Разумные люди понимают наличие разрыва между "формулками" и программной реализацией. В свое время (где-то в 60-х годах) Райнш и Уилкинсон написали "Справочник алгоритмов на языке Алгол" для матричных вычислений. А до тех пор лишь в математических журналах алгоритмы на пальцах показывали, вот дело и стояло на месте. Именно с этого момента все эти алгоритмы стали активно использоваться (коммерческие пакеты EISPACK, LINPAСK, LAPACK и т.п.). И плевать, что там алгоритмы на Алголе! Зато написано настолько понятно, что я сама до сих пор тем Справочником активно пользуюсь, потому как в современных пакетах уже не разобраться.

А у вас, я гляжу, стиль объяснения такой, чтобы только указочкой на формулки указывать и округлые общие слова говорить. Я не только по себе сужу, но и другим темам, где вы объяснения даете (например, тема "Сложение сигналов в самый узкий"). Вы уж извините меня за прямоту, но у меня сложилось впечатление, что вы сами не понимаете того, что пытаетесь объяснять другим.

Говеннейшая реализация...

Ну так и где же ваша хорошая реализация, которую я уже "три года" жду? Или вы тоже, как Oldring, будете кругами вокруг ходить, советовать мне Гугликом по интернетику поискать?

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

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

[DRUID3]

Ну и что? Вы хотите просто жить... Раскладывать нужно на то, на что нужно, а не на то, что проще.

Искать под фонарем...

Эх Таня... Ну пробует человек этот мир на зуб... Что в этом плохого!? В конце концов вспомните себя в 26...

Разумные люди понимают наличие разрыва между "формулками" и программной реализацией. В свое время (где-то в 60-х годах) Райш и Уилкинсон написали "Справочник алгоритмов на языке Алгол" для матричных вычислений. А до тех пор лишь в математических журналах алгоритмы на пальцах показывали, вот дело и стояло на месте. Именно с этого момента все эти алгоритмы стали активно использоваться (коммерческие пакеты EISPACK, LINPAСK, LAPACK и т.п.). И плевать, что там алгоритмы на Алголе! Зато написано настолько понятно, что я сама до сих пор тем Справочником активно пользуюсь, потому как в современных пакетах уже не разобраться.

Да, все верно. Хорошие вычислительные алгоритмы - дело очень непростое. А писать ЦОС(не либу вызывать поставляемую с процом, как у bf) это совсем не одно и то-же, что ваять утилитку. Кто не верит - пусть попробует сам. Пишу это специально для говнодиректоров, говноменеджеров и прочих унылых болванов которые в жизни вообще ни строчки кода не написали сами(ну разве что когда катали на экзамене), но думают, что главное "правильно сыграть" руководителя... Ну и еще "горячим головам" которые по молодости и наивности своей рискуют осчастливить какого-то недоумка за миску риса...

Ну так и где же ваша хорошая реализация, которую я уже "три года" жду? Или вы тоже, как Oldring, будете кругами вокруг ходить, советовать мне Гугликом по интернетику поискать?

))) Я не так давно гуглил опенсоус вейвлет-проекты. Кстати именно потому вспомнил Вашу просьбу. И почти везде - полнейшее гавно(неуниверсальные процедуры - под определенный базис, системные вызовы внутри вычислительной функции, FIR "в лоб" с поэлементным сдвигом массива, нигде не применена быстрая свертка - хотя где-где а в вейвлетах ей самое место, задействованы "массивные" механизмы расширений языка - как вот на WiKi, неразделимо срощены с кодированием - для 2D и т.д. ... ну и float восновном). Еще опенджпег правда не просмотрел. Он, кстати, целочисленный насколько помню - хорошо для ARM7-9. Все-равно - того что видел вполне достаточно что-бы отсоветовать гуглить... Но... Все-таки Вы наглая барышня - вот так брать на понт - мол "а тебе слабо"? Потому у меня к Вам ответное предложение - читайте личку...

[Xenia]

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

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

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

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

Кажется (но точно не помню) такую матрицу составляли, как циркулянт - укладывали форму сигнала в верхнюю строку, а каждую ниже лежащую получали циклическим сдвигом на единичку (на одну временную дискрету) влево от того, что находится этажом выше. Например, для сигнала data[5] = { 1, 2, 3, 4, 5 }; матрица получалась такой:

1 2 3 4 5
2 3 4 5 1
3 4 5 1 2
4 5 1 2 3
5 1 2 3 4

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

Вы где-нибудь встречали что-нибудь подобное? А то я не уверена, что излагаю что-то реальное, а не свои фантазии из головы, где всё поперепуталось .