МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РФ
ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ
БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ
ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ
«ВОРОНЕЖСКИЙ ГОСУДАРСТВЕННЫЙ
УНИВЕРСИТЕТ»
М.А. Артемов,
Е.С. Барановский,
М.В. Киргинцев
ВЕЙВЛЕТ-ПРЕОБРАЗОВАНИЕ
В ЗАДАЧЕ СЖАТИЯ
ЦИФРОВЫХ ИЗОБРАЖЕНИЙ
Учебно-методическое пособие для вузов
Воронеж
Издательский дом ВГУ
2015
Стр.1
1 Введение
Цифровые изображения играют весьма важную роль в современном
информационном мире. Потребность в существенном увеличении
объемов и скорости передачи визуальной информации определяет постоянный
интерес к улучшению алгоритмов сжатия цифровых изображений.
В
данном учебном пособии рассматривается вейвлетный подход к
сжатию изображений. Понятия вейвлета и вейвлет-преобразования
являются сравнительно новыми, но они уже нашли широкие применения
во многих прикладных задачах, в том числе в задачах кодирования
и сжатия данных.
В современной литературе имеется несколько подходов к изложению
теории вейвлетов. Чаще всего вейвлет-преобразование определяется
как обобщение преобразования Фурье (см., например, [1, 2]).
При этом акцентируется внимание на преимуществах, которые дает
вейвлет-анализ по сравнению с классическим методами Фурье. Прежде
всего отмечается возможность обнаружения локализованных деталей
сигнала, в то время как Фурье-анализ дает усредненную развертку
сигнала. Новые возможности объясняются спецификой вейвлетпреобразования,
обеспечивающего двумерную развертку одномерного
сигнала за счет использования непрерывных масштабных преобразований
и сдвигов базисного вейвлета. Другой подход к определению
вейвлетов связан с использованием высокочастотных и низкочастотных
фильтров (см. [3, глава 6]).
На наш взгляд, знакомство с теорией вейвлетов следует начинать с
рассмотрения системы вейвлетов Хаара, названной по имени венгерского
математика Альфреда Хаара. Эта система вейвлетов достаточно
проста и допускает наглядную геометрическую интерпретацию. Базовые
вейвлеты Хаара хорошо иллюстрируют идею разложения потока
информации на основной и уточняющий информационный поток.
Следуя подходу, предложенному в монографии [3], мы рассматри3
Стр.3
Определение. Выражение вида
m
i=1
ξixi, ξi ∈ R,
называется линейной комбинацией векторов x1,x2, . . . ,xm. Линейная
комбинация называется нетривиальной, если среди коэффициентов
ξ1, . . . , ξm есть ненулевые, и тривиальной в противном случае.
Определение. Система векторов x1,x2, . . . ,xm называется линейно
зависимой, если существует нетривиальная линейная комбинация
этих векторов, равная нулевому вектору. В противном случае система
векторов называется линейно независимой. Другими словами, система
x1,x2, . . . ,xm называется линейно независимой, если из равенства
m
i=1
следует
ξ1 = ξ2 = · · · = ξm = 0.
Пример. Система функций {sin2(t), cos2(t), 1} является линейно
зависимой, a система функций fi, i = 1, . . . , 4, где
fi(t) =
1, если t ∈ i−1
∈ i−1
0, если t /
4 , i
4 , i
4 ,
4 ,
линейно независима.
Определение. Бесконечная система векторов x1,x2, . . . , называется
линейно независимой, если любая ее конечная подсистема линейно
независима.
Упражнение. Приведите пример бесконечной линейно независимой
системы функций в пространстве L2(0, 1).
6
ξixi = 0
Стр.6
2.3 Евклидово пространство
Определение. Линейное пространство с фиксированным в нем
скалярным произведением называется евклидовым пространством.
Напомним, что скалярным произведением в линейном пространствеE
называется функция, сопоставляющая паре элементов x,y ∈ E
вещественное число (x,y) и удовлетворяющая следующим условиям:
(i) (x1 +x2,y) = (x1,y)+(x2,y),
(ii) (λx,y) = λ(x,y),
(iii) (x,y) = (y,x),
(iv) (x,x) ≥ 0, причем (x,x) = 0 только при x = 0.
Примеры.
1) Пространство Rn со скалярным произведением
(x,y) =
i=1
n
xiyi,
где x = (x1, . . . ,xn), y = (y1, . . . , yn), есть евклидово пространство.
2) Пространство L2(0, 1) со скалярным произведением
(v,u) =
1
0
u(t)v(t) dt.
где u, v ∈ L2(0, 1), является евклидовым пространством.
Скалярное произведение позволяет ввести в абстрактном линейном
пространстве E понятие нормы (длины) вектора. Норма определяется
с помощью формулы
x = (x,x)1/2.
Из условий (i)–(iv) следует, что основные свойства длины вектора,
которые выполняются в обычном трехмерном пространстве, остаются
справедливыми в случае абстрактного евклидова пространства.
Упражнение. Докажите справедливость неравенства Коши-Буняковского
(x,y)
≤ xy.
7
Стр.7
2.4 Сходимость и замыкание
Пусть x1,x2, . . . — последовательность элементов пространства E.
Определение. Говорят, что последовательность {xn} сходится
к x (пишут xn →x), если
xn −x→0 при n→∞.
Пусть M ⊂ E — некоторое множество, u — некоторый элемент
пространства E.
Определение. Говорят, что u является точкой прикосновения множества
M, если найдется последовательность {xn} ⊂ M сходящаяся
к u.
Определение. Совокупность всех точек прикосновения множества
M обозначается M и называется замыканием множества M.
2.5 Ортогональные системы векторов
Пусть E — евклидово пространство. Введем понятие угла между
ненулевыми векторами x,y ∈ E.
Определение. Угол между векторами x,y ∈ E определяется как
решение уравнения
cosϕ = (x,y)
xy
, ϕ ∈ [0, π]
(2.1)
относительно ϕ.
Для обоснования корректности определения заметим следующее.
Из неравенства Коши-Буняковского вытекает, что
0 ≤ |(x,y)|
xy ≤ 1.
Поэтому уравнение (2.1) имеет решение и это решение единственно.
Если (x,y) = 0, то cosϕ = 0 и, следовательно, ϕ = π/2. В этом
случае векторы называются ортогональными.
8
Стр.8