ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Evgenij Masherov                     2:5020/175.2   11 Dec 2001  10:37:24
 To : Konstantin Filinov
 Subject : Вейвлеты
 -------------------------------------------------------------------------------- 
 

 Mon Dec 10 2001 22:58, Konstantin Filinov wrote to Евгений Машеров:
 
  ЕМ>> В трех - кратно-масштабный анализ:)
  ЕМ>> Если чуть больше слов - используем базисные функции, которые после
  ЕМ>> растяжения в два раза (рассматриваются и иные растяжения) переходят в
  ЕМ>> себя. Основное уравнение: f(2x)=SUM a(i)*f(x-i) Эти функции локализованы
  ЕМ>> в  пространстве, в отличие от раскинутых от плюс до минус бесконечности
  ЕМ>> синусов/косинусов. Поэтому ими лучше приближаются функции, содержащие
  ЕМ>> быстрые изменения, скажем, изображения. Далее либо мылом, либо, если
  ЕМ>> народу интересно, можно начать обсуждение в эхе.
 
  KF>     Интересно, расскажи подробнее.:)
 
  Рассмотрим подробнее эту формулу. Коэффициент, равный корню из двух, введен
 лишь для удобства выкладок, и можно рассмотреть представление ее, в котором он
 не вводится. При этом, разумеется, пропорционально меняются прочие
 коэффициенты.  Масштаб, равный двум, наиболее прост для понимания, и с его
 использованием получены наиболее ценные практически результаты, однако можно 
 рассмотреть и иные масштабы, в том числе - не обязательно целые. (Впрочем,
 польза от такого, равного двум, масштаба обнаружилась задолго до появления
 самого слова 'вейвлет' - именно удвоению частоты соответствует перенос ноты на
 октаву, так что нотная запись есть древнейшая форма вейвлет-преобразования).
 Ограничение сдвигов целыми числами естественно для задач обработки сигналов,
 которые представлены набором отсчетов, взятых через равные промежутки. В общем
 случае можно рассматривать и дробный сдвиг. Легко видеть, что основное
 соотношение задает масштабную и базисную функции с точностью до умножения на
 произвольное число, так что вводят условие нормировки. Как правило, требуют,
 чтобы интеграл от масштабной функции от минус до плюс бесконечности, был бы
 равен единице. 
   Простейшая форма такого соотношения вида
 f(x) =f(2x)+f(2x-1)
 уже приводит к чрезвычайно важному классу функций - вейвлетам Хаара. Решением
 его является функция, равная единице на отрезке от нуля до единице и нулю -
 вне этого отрезка. Это дает нам масштабную (скейлинг-) функцию. Базисная же
 функция этого вейвлета представляет собой единицу - на отрезке от нуля до
 ½, минус единицу - от ½ до единицы и нулю на всем прочем
 протяжении аргумента (Рис. 2). В этом  проявляется общее свойство всех
 вейвлетов - знакопеременность, откуда и происходит их название -  буквально
 означающее 'маленькая волна' или 'волнушка'. Вообще, интеграл от базисной
 функции любого вейвлета равен нулю.
   Рассмотрим представление функции в виде разложения по базису вейвлетов Хаара,
 в процессе которого, возможно, прояснится польза от вейвлетов в некоторых
 практически важных классах задач. Положим, что в нашем распоряжении функция,
 заданная своими отсчетами через равные промежутки времени. Если она достаточно
 гладкая, то соседние отсчеты отличаются мало, и можно взять отсчеты через
 вдвое большие интервалы, а в качестве значений функции взять средние между
 соседними отсчетами. Полученная функция будет лишь приблизительно описывать
 поведение исходной (хотя качество приближения может быть хорошим - обычная
 телефонная сеть представляет речевой сигнал последовательностью отсчетов с
 частотой 8000 Гц, тогда как для воспроизведения всей полосы речи нужно по
 крайней мере вшестеро большая частота, а в сельских телефонных сетях
 использовалась и частота 4000 Гц, и разборчивость сохранялась). Чтобы не
 потерять информацию, будет запоминать и разницу между соседними отсчетами
 (также с половинной частотой выборки - очевидно, этого достаточно для
 восстановления сигнала!). Hетрудно заметить, что последовательность
 усредненных пар являет собой набор коэффициентов разложения по масштабным
 функциям базиса Хаара, сдвинутым по времени с шагом 2, а последовательность
 разностей - набор коэффициентов разложения по базисным функциям Хаара.
   Оставим на время последовательность разностей и проведем ту же процедуру с
 набором усредненных пар - превратив ее в два половинной длины вектора -
 средние средних (разумеется, это попросту средние по четверкам соседних
 значений) и разности средних. Разности также отложим до времени, и продолжим
 ту же процедуру со средними (здесь и в дальнейшем удобно нам полагать, что
 число точек в нашем сигнале составляет степень двух - имевшему дело с быстрым
 преобразованием Фурье ограничение это не покажется столь обременительным! А
 именно быстрое вейвлет-преобразование мы сейчас и получили). В конечном итоге
 получим мы среднее значение сигнала, величину изменения среднего между первой
 и второй половинами сигнала, два изменения между четвертями, четыре изменения
 между осьмушками исходного сигнала и т.п. , вплоть до разностей отдельных
 отсчетов.
 Положим, что нашей целью является нахождение способа достаточно точного, но
 при этом экономного представления сигнала. Тогда на гладких участках разности
 будут малы, и могут быть, без большой ошибки, приняты равными нулю, но в тех
 местах, где имеют место резкие изменения, значения соответствующих
 коэффициентов будут велики. Представляя (немногие!) большие коэффициенты с
 достаточной точностью,  а малыми пренебрегая (ошибка при этом составляет
 величину порядка отброшенных коэффициентов), имеем возможность с малой
 погрешностью представить сигнал малым объемом информации. Разложение Фурье
 было бы в этой задаче весьма эффективно, если бы сигнал был бы одинаков по
 спектральному составу на всем своем протяжении, но если в нем имеется
 нестационарность, все коэффициенты Фурье будут не малы и занулять их
 бесполезно. (Вместо отбрасывания коэффициентов можно рассмотреть их
 представление кодом Хаффмана, что в принципе позволяет придти к сжатию 
 сигнала без потерь, хотя и с меньшей степенью сжатия).
 
 Евгений Машеров АКА СанитарЖеня
 
 --- ifmail v.2.15
  * Origin: FidoNet Online - http://www.fido-online.com (2:5020/175.2)
 
 

Вернуться к списку тем, сортированных по: возрастание даты  уменьшение даты  тема  автор 

Тема:    Автор:    Дата:    Вейвлеты   Roman Kirillov   09 Dec 2001 17:29:49   Вейвлеты   …ўЈҐ­Ё© Њ иҐа®ў   10 Dec 2001 20:52:00   Вейвлеты   Konstantin Filinov   10 Dec 2001 23:58:29   Вейвлеты   Evgenij Masherov   11 Dec 2001 10:35:26   Вейвлеты   Evgenij Masherov   11 Dec 2001 10:37:24   Вейвлеты   Evgenij Masherov   11 Dec 2001 10:39:32   Вейвлеты   Evgenij Masherov   11 Dec 2001 10:41:27   Вейвлеты   Roman Kirillov   14 Dec 2001 09:38:48   Вейвлеты   …ўЈҐ­Ё© Њ иҐа®ў   17 Dec 2001 20:37:10   Re: Вейвлеты   Alexander Lezin   10 Dec 2001 19:07:04   Вейвлеты   Ilia Kantor   12 Dec 2001 17:00:26