Содержание к диссертации
Введение
ГЛАВА 1. Методы и средства преобразования много мерных цифровых сигналов 33
1.1. Неразделимые многомерные решетки и фильтры. История вопроса . 33
1.1.1. Многоскоростные системы и банки фильтров. Введение 33
1.1.2. Преимущества неразделимой обработки данных 38
1.1.3. Исследования в области синтеза неразделимых матриц децимации 42
1.2. Биортогональные и ортогональные многомерные банки фильтров 44
1.2.1. Основные требования, предъявляемые к синтезируемым фильтрам 45
1.2.2. Основные подходы при проектирования многомерных банков фильтров 47
1.3. Системы кодирования многомерных сигналов 58
1.3.1. Моделирование и обработка изображений 59
1.3.2. Кодирование многомерных сигналов 65
1.3.3. Метод частичной сортировки вейвлет-коэффициентов 68
1.4. Предпосылки прорыва в технологиях обработки многомерных сигналов 75
1.4.1. Работы российских ученых по многомерным неразделимым многоскоростным системам 75
1.5. Выводы 78
ГЛАВА 2. Синтез неразделимых дециматоров и интерполяторов 80
2.1. Основные операции с многомерными сигналами 80
2.1.1. Многомерная дискретизация. Решетки и подрешетки 80
2.1.2. Многомерная децимация и интерполяция 82
2.2. Полная параметризация многомерных неразделимых матриц децимации 104
2.2.1. Требования к матрицам децимации 104
2.2.2. Двумерный случай 105
2.2.3. Трехмерный случай ПО
2.2.4. Произвольная размерность D .114
2.3. Свойства многомерных банков фильтров 119
2.3.1. Условие точного восстановления сигнала 121
2.3.2. Фильтры с линейной фазой 122
2.3.3. Пример. Двухканальные банки фильтров 130
2.4. Выводы 135
ГЛАВА 3. Разработка биортогональных и ортогональных многомерных банков фильтров 137
3.1. Синтез многомерных банков фильтров с помощью метода преобразования 137
3.1.1. Метод преобразования МакКлеллана 137
3.1.2. Синтез фильтра прототипа с четным размером носителя и свойством ТВС 138
3.2. Синтез многомерных банков фильтров с помощью методов компьютерной алгебры 141
3.2.1. Метод достройки унимодулярной матрицы 141
3.2.2. Синтез банков фильтров с линейной фазой для двухканальной системы 147
3.2.3. Синтез банков фильтров с нулевой фазой 149
3.3. Синтез биортогональных банков фильтров с помощью полиномов Бернштейна 155
3.3.1. Полиномы Бернштейна. Двумерный случай 156
3.3.2. Трехмерный случай 158
3.3.3. Четырехмерный случай 160
3.3.4. Теорема о разделяющей гиперплоскости 161
3.3.5. СКО-оптимизированные банки фильтров 163
3.3.6. Метод «неразделимый-через-разделимый» 165
3.3.7. Примеры проектирования 168
3.4. Синтез с помощью метода лифтинга 169
3.4.1. Основные этапы лифтинга 169
3.4.2. Лифтинг-схема и полифазное представление 170
3.4.3. Многомерные интерполяционные фильтры и фильтры с дробным сдвигом 172
3.5. Синтез неразделимых ортогональных фильтров 180
3.5.1. Синтез двухканальных неразделимых ортогональных фильтров 180
3.5.2. Структурный синтез четырехканальных ортогональных фильтров 183
3.5.3. Примеры проектирования 189
3.6. Факторизация полифазных матриц 190
3.6.1. Разложение полиномиальных матриц на элементарные множители 190
3.6.2. Факторизация двухканальных многомерных полифазных матриц 192
3.6.3. Сравнение числа операций 193
3.7. Результаты применения синтезированных многомерных банков фильтров 194
3.8. Выводы 196
ГЛАВА 4. Построение многомерных шкалирующих и вейвлет функций 198
4.1. Вейвлет-преобразование 198
4.2. Дискретное вейвлет-преобразование в Ш 201
4.3. Построение вейвлет базисов для двухканальных систем в RD 205
4.3.1. Биортогональные банки фильтров на основе полиномов Берн-штейна 209
4.4. Построение фильтров в RD при наличии сдвигов 209
4.5. Связь частотных характеристик фильтров многоскоростных си
стем и порождаемых ими вейвлетов 212
4.5.1. Условия Стренга- Фикса 213
4.6. Алгоритм построения многомерных вейвлетов 214
4.7. Выводы 216
ГЛАВА 5. Разработка и реализация системы кодирования многомерных сигналов 220
5.1. Выбор оптимальной цветовой модели для представления цветного изображения с целью его кодирования иерархическим алгоритмом 220
5.1.1. Классификация цветовых систем и анализ их характеристик 221
5.1.2. Разработка новой цветовой модели 222
5.1.3. Распределение бит по каналам цветного изображения. Динамический формат кодирования 222
5.1.4. Субъективное тестирование 227
5.1.5. Альтернативные критерии оценки качества сжатых изображений229
5.2. Иерархический алгоритм кодирования 236
5.2.1. Свойства потока . 238
5.2.2. Оптимизация алгоритма 238
5.3. Применение иерархического алгоритма для неразделимых решеток и банков фильтров 242
5.3.1. Неразделимая децимация 242
5.3.2. Необходимость адаптации алгоритма SPIHT 244
5.3.3. Сдвиг 244
5.3.4. Трехканальные неразделимые системы 249
5.3.5. Результаты 251
5.4. Сжатие изображений с помощью частичной сортировки вейвлет-коэффициентов 251
5.4.1. Алгоритм SQP 252
5.4.2. Результаты моделирования 259
5.5. Реализация многомерных многоскоростных систем 261
5.5.1. Описание многомерных сигналов 262
5.5.2. Продолжение сигнала 262
5.5.3. Децимация 268
5.5.4. Результаты моделирования 3-D многоскоростной системы 269
5.6. Программная реализация алгоритма сжатия изображений 272
5.6.1. Программный комплекс. Обзор 272
5.6.2. Программы "і сотр"и sptv 274
5.6.3. Три поколения программного обеспечения 275
5.6.4. Обработка трехмерных данных 277
5.7. Выводы 279
Выводы по диссертации 282
Литература
- Неразделимые многомерные решетки и фильтры. История вопроса
- Основные операции с многомерными сигналами
- Синтез многомерных банков фильтров с помощью метода преобразования
- Вейвлет-преобразование
Введение к работе
Глава 1
Неразделимые многомерные решетки и фильтры. История вопроса
Одним из основных средств обработки сигналов является линейное преобразование. Субполосное (подполосовое) кодирование является частным случаем линейного преобразования и имеет многочисленные полезные свойства. Оно реализуется путем свертки сигнала с несколькими полосовыми фильтрами и децимацией результата. В итоге получаются несколько каналов или подполосовых сигналов. Совокупность набора фильтров с де-циматорами называется банком фильтров (БФ). В банке анализа каждый получившийся в результате преобразования ММ подполосовой сигнал (или канал) несет в себе информацию о спектральной составляющей исходного ММ сигнала при некотором пространственно/временном масштабе. Для обратного синтеза сигнала (его реконструкции) выполняется операция интерполяции подполосовых сигналов (каналов), их фильтрация и сложение. Большинство методов синтеза фильтров направлено на устранение наложения спектров (aliasing), возникающего при децимации (см. 2.1.2.5.), и искажения сигналов.
Операция понижения (повышения) пространственно/временной плотности ММ отсчетов реализуется с помощью дециматоров j М (интерполяторов М), использующих целочисленную квадратную матрицу децимации (или матричный коэффициент растяжения) М. При этом, скажем, прореживание (децимация) ММ сигнала х(п) будет равно х(М п) (см. 2.1.2.4.).
Существуют два типа многомерных решеток, с помощью которых описываются операции понижения/повышения частоты следования ММ отсчетов: разделимые (или сепарабельные, или ортогональные) решетки, им соответствуют диагональные матрицы децимации М, и неразделимые (или несепарабельные), им соответствуют недиагональные матрицы децимации М. Цифровые фильтры, из которых состоят многоскоростные системы, в свою очередь могут быть как разделимыми, то есть представимыми в виде прямого (тензорного) произведения одномерных функций вдоль каждой из пространственно/временных координат, так и неразделимыми. Исторически первыми возникли разделимые ММ системы. Только последние примерно 10-12 лет стали появляться неразделимые системы.
Многоскоростная система (рис. 1.1) в общем случае состоит из банка анализа (БА) и банка синтеза (БС), устройств квантования и кодирования/декодирования подполосовых сигналов (каналов) [235]. Банк анализа состоит из фильтров #j(z) и дециматоров і М, банк синтеза - из интерполяторов Т М и фильтров Fi(z), где z = (21,..., ZD), D - число измерений сигнала, і = 0,1,... ,т - 1. В работе рассматривается случай максимально децимированной многоскоростной системы, когда число каналов равно т = detM. На рис. 1.1 показан только один уровень разложения входного сигнала x(z) на т каналов, в общем случае такому разложению может быть повторно подвергнут любой из таких подполосовых сигналов, и такое разложение может повторяться многократно.
Входной сигнал x(z) поступает на вход БА, а именно на входы фильтров #i(z), а потом прореживается (децимируется) в соответствии с матрицей децимации М. На выходе БА получаются m подполосовых сигналов (каналов), которые далее попадают в блок передачи сигнала, где они могут кодироваться, квантоваться, сжиматься и т.д. После передачи данных декодированные подполосовые сигналы поступают в БС, где сначала происходит интерполяция сигналов, а затем их фильтрация. Восстановленный сигнал х - это сумма подполосовых сигналов на выходе банка синтеза. В z-области выходной сигнал для двухканальных систем, когда т = 2, описывается равенством 2x(z) = x(z) [#o(z)F0(z) + ЯІМВД] + +x(-z) [tf0(-z)Fo(z) + Яі(-я)ВД].
Важнейшим блоком многоскоростной системы является блок децимации. В то время как осуществление одномерной децимации может быть выполнено единственным способом, в случае двух или более измерений это не так. Многомерная децимация представлена решеткой, которая может быть разделимой или неразделимой. В данной работе будет также решена задача синтеза неразделимых матриц децимации.
Другим важнейшим блоком являются цифровые фильтры. Здесь имеется множество вопросов, представляющих интерес, которые также должны быть рассмотрены. Синтез ММ цифровых фильтров для многоскоростных систем включает учет проектных ограничений, таких, как, например, ортогональность, линейная фаза, регулярность и др., необходимых для синтеза эффективных систем сжатия, удаления шумов и т.д. Фильтры сами по себе могут быть как разделимыми, так и неразделимыми, независимо от вида решетки. Важно то, что, можно иметь все комбинации разделимых/неразделимых операций при осуществлении децимации/фильтрации полифазных компонентов (см. о полифазном представлении далее в 2.1.2.8.). Неразделимые системы являются более сложными.
Банк фильтров (БФ) анализа разбивает сигнал на различные частотные подполосы (каналы), а БФ синтеза восстанавливает первоначальный сигнал из подполосовых сигналов. Если восстановленный сигнал идентичен первоначальному, не считая задержки и масштабирования, то система анализа-синтеза называется БФ со свойством точного восстановления сигнала. Свойство точного восстановления сигнала записывается как x(z) = z8#(z), где s = (si,..., SD) - это ММ сдвиг, a z8 = (z{\..., zjf).
Человеческая визуальная система чувствительна к фазовому искажению. Так как фазовое искажение можно избежать, применяя фильтры со свойством линейной фазы (ЛФ), то желательно, чтобы все фильтры, составляющие БФ, имели свойство ЛФ, когда система применяется для обработки изображений или видеосигналов.
Основные операции с многомерными сигналами
Пусть сигнал x{t) реализует отображение RD - R1, где t = [ti t2 ... tn]T. Дискретизация D-мерного сигнала x(t) определяется выражением [235]: y(n) = z(Vn), (2.1) где п = [щ щ ... по]т, п Є ZD, а V - несингулярная матрица D х D V = [vlV2...vD], (2.2) где Vj = [г/ц г 2,і ..., VD,I ]Т - это столбцы матрицы V.
В Р-мерном евклидовом пространстве RD решетка Л это множество всех линейных комбинаций D линейно независимых действительных векторов (столбцов) Vj из RD с целочисленными коэффициентами [130] A = {niVi+n2v2 + ... + n)V) щ eZ,i = 1,...,.0}.
Множество всех векторов vi называется базисом для Л. Пусть V является матрицей, столбцы которой являются представителями этих векторов. Тогда решетка это множество векторов Vn, где п = [щ щ ...пв]т Є ZD и можно записать Л = LAT(V). V является базисом решетки и называется матрицей дискретизации. Для заданной решетки базис не является единственно возможным, так как для любой унимодулярной целочисленной матрицы Е (такой, что ее определитель равен ±1) матрица V=VE даст другой базис для Л. Обозначим d(A) = det(V) в качестве определителя решетки Л. Плотность дискретизации или число отсчетов сигнала в единице объема будет равно l/d(A).
Пусть Г и Л являются решетками одинаковой размерности. Л называется подрешеткой Г: Л С Г, если каждая точка Л также является точкой Г. Если Л является подрешеткой Г, то d(A) является целочисленным множителем d(r). Частное d(A)/d(r) называется индексом Л в Г. Множество к + Л = {к + хх Є Л} для любого к Є Г называется классом смежности (или косетом) Л в Г [47]. Такой вектор к называется представительным вектором класса смежности к Є Л. Два класса смежности являются либо идентичными, либо непересекающимися ик + Л = сі + Л тогда и только тогда, когда k - d є Л. Всего имеются d(A)/d(r) непересекающихся классов смежности Л в Г и решетка Г является объединением непересекающихся классов смежности (Г : Л). Можно записать (Г:А) Г= и(Л + кі),к,-єГ,кі-кіЛ если i j. Важным понятием для частотного представления ММ сигналов является взаимная решетка. Для решетки Л множество всех векторов у таких, что угх целое для всех х Є Л, называется взаимной решеткой Л для решетки Л. Базисом для Л является множество щ таких, что ufvj = 6(i — j), i,j — 1,...,Д или эквивалентно UrV = ID, (2.3) где ID единичная матрица порядка D. Преобразование Фурье сигнала q(x), заданного на решетке Л, после под становки (2.1) будет равно 0(f) = q(x)e-J2,rfTx = Y, q(Vn)e-j27rfTVn, f Є RD. (2.4) хєЛ nZD Понятие z-преобразования может быть распространено на ММ сигналы, дискретизированные с помощью произвольной решетки [242]. Тогда z-преобразованием сигнала q(x) будет Q(z,A) = Q(zA) = 5 (x)z"x = J2 9(Vn)z"Vn, хєЛ neZD ГДЄ Z=[ZUZ2,...,ZD}, Z1 = 3%7%...J , zA = (ZAI,ZA2,...,ZAD), где Aj, j = 1,...,D- столбцы матрицы Л. Оператор сдвига (задержки) z1 означает сдвиг сигнала на і є IP отсчетов. Пусть g(x) это сигнал, заданный на Г. Обобщенным полифазным разложением Q{zT) над решеткой Л будет (см. также 2.1.2.8.) [235] (Г:Л) Q(zr) = J2 я№) г=1 где Qi{zA) является z-преобразованием $(х) = g(x + kj), х є Л. Вектора 1 составляют полный набор представителей классов смежности Л в Г.
Децимация состоит в понижении частоты дискретизации сигнала путем сохранения только части отсчетов. Можно продецимировать w(x) (заданный на решетке Г) над решеткой Л так, что полученный сигнал q(x) задан на Л с помощью где «о» это почленное произведение [146]: обозначение aob используется для покоординатного произведения векторов а и b: aob = (аі&і,.. . ,а#& ); Л = ТТ (r +qj), где % составляют полный набор векторов классов смеж ности для Г в Л . Децимация обозначается в виде q(x) = [w(x)] j Л, Q(f) = [W(f)] і Л или Q(zA) = [W(zr)] і Л. Оператор децимации является важнейшей частью банка анализа, изображенного на рис. 2.1.
Интерполяция (повышение частоты дискретизации) состоит в том, чтобы задавать сигнал на более частой решетке. Например, можно интерполировать q(x) (заданный на решетке Л) на новую решетку Г так, что полученный сигнал v(x) задан над решеткой Г с помощью соотношения
Известно, что V(f) = Q(f) и V(zv) = Q(zA). Для представления операции интерполяции, можно записать [122] и(х) = [q(x)] Г, V(f) = [Q(f)] Т Г или V(zr) = Q(zA) I Г. Оператор интерполяции является важнейшей частью банка синтеза, изображенного на рис. 2.2.
Свертка сигнала w(x) с импульсной характеристикой линейного инвариантного к сдвигу фильтра h(x) (где оба заданы на решетке Г) определяется через v(x) = уЄгМх -У)ЦУ) х Є Г, что равносильно V(zr) = H(zr)W(zr). Имеют место следующие соотношения
Существуют два вида децимации: разделимая и неразделимая. В случае разделимой децимации используется диагональная целочисленная матрица:
При этом осуществляется децимация на тг- по каждому г-му измерению в отдельности. В неразделимом случае операция децимации является более сложной. Неразделимую матрицу децимации (матричный коэффициент растяжения) можно преобразовать к виду, называемому формой Смита [198] M = UAV, (2.8) где Л - диагональная (разделимая) целочисленная матрица; U и V - унимодулярные целочисленные матрицы (detU = det V = 1), которые задают просто другой порядок перебора отсчетов без их децимации [235].
Целочисленная матрица Е называется унимодулярной, если det(E) = ±1. Для такой матрицы обратная матрица Е-1 также является целочисленной. Предположим обратное, что обратная матрица F целочисленной матрицы Е также целочисленная. Мы имеем EF = I, так что [det(E)][det(F)] = 1. Так как каждый определитель должен быть целочисленным, то это показывает, что оба определителя имеют единичную величину, то есть обе матрицы являются унимодулярными.
Известно [235], что если M-DxD действительная несингулярная матрица генерации решетки LAT(M), то если определить матрицу М = ME, где Е - некоторая D х D целочисленная матрица, удовлетворяющая уело-вию det(E) = ±1, тогда М - это новый базис, генерирующий ту же решетку LAT(JA). Другими словами, LAT(M) = LAT(ME). Пусть М - новый базис, генерирующий ту же решетку LAT(M). Тогда существует целочисленная матрица Е с det(E) = ±1, такая, что М = ME. Пусть имеются две последовательности х(п) = #а(Мп) и у(п) = яа(Мп). Тогда совсем необязательно, что будет выполняться равенство х(п) = у(п). Просто отсчеты у(п) получены перестановкой отсчетов х(п).
По данной матрице децимации М можно построить эскиз всех базисных векторов mjfc (столбцов матрицы М) в D-мерном координатном пространстве. Рассмотрим пример изображения базисных векторов в трехмерном пространстве FCO-решетки (см. 2.2.4.2.).
Синтез многомерных банков фильтров с помощью метода преобразования
Методы синтеза ММ фильтров с помощью преобразования МакКлеллана используются достаточно давно и успешно. Ниже будет рассматриваться пример синтеза двухканальных систем. Для построения банка фильтров необходимо располагать двумя объектами: 1. Одномерными фильтрами-прототипами HP{Z) = hp(n) - Z \ FP(Z) = fp(n) Z \ (3.1) n n Для выполнения свойства TBC, данные фильтры-прототипы должны удовлетворять (см. (2.69)) QP(Z) + QP(-Z) = 2, где QP(Z) = HP(Z) FP(Z). 2. Ядром преобразования Z = W(zi,Z2) = 5 51 1 2) 142. кото рое удовлетворяет свойству антисимметрии и может быть в общем случае как КИХ, так и БИХ: W(zhz2) = -W(-zb-z2), (3.2) или, что то же самое, что w(h,l2) = О, для li + /2 = четное произвольное, для h +l2 = нечетное Высокочастотные фильтры банков анализа и синтеза вычисляются как Hi{zhz2) = z1qiZ2q2FQ(-Zi,-z2), F1{zhz2) = г? z?#0(- b- ), где qi + q2 нечетно (см. (2.69)). Известно несколько типов получаемых банков фильтров: Преобразование W имеет нулевую фазу [151]. Чаще всего предлагалось либо W(zi,z2) = l/4(zi + j- + z2 + у), либо параметризованное через а,Ь преобразование [195] W(zi,z2) = 1/4zj +1/4zr1 +1/2Z2 + l/2z2-4l/2az1 + l/2f;-l/mz1h2 + l/S2b + l/32b$-l/327fc2-1/32 bz2 Zl + 1/32 + 1/32 g - 1/32 . Пары полуполосовых фильтров [209] Я0 = 1/2(1 + W) и FQ = -\l2{W + \){W-2). Сумма и разность всепропускающих фильтров Я0 = 1/2(1 + W) и #i = 1/2(1 — Ж), где W является всепропускающим фильтром [117]. Соответственно если F0 = 1/2(1 + W) и Fx = -1/2(1 - W), то T0(z) (см. (2.69)) является всепропускающим фильтром, а если F0 = 1/2(1+ W l) и Fi = 1/2(1 — W l), то система обладает свойством ТВС. Обобщенное преобразование переменных [147, 209, 210], когда фильтры прототипы (3.1) имеют только положительные степени W. Само преобразование W может быть как КИХ, так и БИХ.
Вопросы синтеза банков фильтров, которые состоят из фильтров с четным размером носителя, весьма важны. Как было замечено исследователями [241], фильтры с четным носителем имеют при обработке изображений в целом лучшие характеристики, чем фильтры с нечетным носителем, так как при этом удается избежать некоторые проблемы, связанные с тем, что многоскоростные системы не являются ЛИС системами. Фильтры с ЛФ с
четным носителем ведут к синтезу симметричных веивлетов, а с нечетным носителем - к антисимметричным вейвлетам. Также необходимо заметить, что фильтры с четным носителем могут реализовать задержку на половину периода дискретизации, что очень важно, например, при синтезе преобразователей Гильберта и комплексных веивлетов [149].
Свойство ТВС.
Пусть симметричный фильтр прототип имеет нечетную длину, тогда его можно выразить в виде Hp(Z) и Fp(Z), где Z = 1/2(г + l/z). Если выполняется (3.2), то это позволяет получить ММ фильтр со свойством ТВС [209]. Данное преобразование работает достатчно хорошо, когда длины импульсных характеристик являются нечетными, а сами характеристики -симметричными. Получаемые в результате ММ импульсные характеристики также имеют нулевую фазу и нечетный носитель. Причем в этом случае свойство ТВС, присущее одномерному прототипу, сохраняется. Однако это же преобразование не работает для четных носителей одномерных прототипов. Как показано в [246], если использовать "простое" расширение фильтра прототипа с нечетным носителем до четного путем умножения на 1 + по всем координатам или подобное ему преобразование, то в этом случае свойство ТВС не сохраняется.
Автором впервые предложена процедура построения банков фильтров с четным размером носителя [225]. Если можно выразить фильтры прототипы в виде HP(Z) = 1/2(1 + z-l)UH{Z) и FP(Z) = 1/2(1 + z)UF(Z), где UH(Z), UF(Z) зависят от Z = l/2(z + l/z), тогда их импульсные характеристики будут иметь центры симметрии соответственно В С# = 1/2 И Ср = -1/2. Используя второй вариант, позволяющий записать выполнение свойства ТВС (2.69), получим, что так как HP(Z)FP{Z) + HP{-Z)FP{-Z) = 1, то выполняется и Q±?luH(Z)UF(Z) + V- 1(JH(-Z)UF(-Z) = 1. (3.3) Исходя из вида этого соотношения, предлагается ввести две функции 4( 1,) и B(zi,Z2), которые удовлетворяют соотношению A(zhz2)B(zhz2) = ±(l + w(zhz2)).
Одновременно строятся низкочастотные фильтры банков анализа и синтеза в виде #0( 1,) = A(zhz2)UH{W(zhz2)) И F0(zhz2) = B(z\, Z2)UF(W(ZI, Z2)). Тогда выполняется следующая теорема.
Теорема 3.1. Если для фильтров прототипов Нр, Fp выполняется свойство ТВС, тогда и для пары Н0, Fo также выполняется свойство ТВС. Действительно, подставив #0,F0 в (2.69), получим, что 2ЬМ = A(zhz2)B(zhz2)UH(W(zhz2))UF(W(zhz2))+ +A(-zh-z2)B(-z1,-z2)UH(-W(zllz2))UF(-W(zuz2)) = (1 + W(zh z2))UH(W(zh z2))UF(W(zh z2))+ +J(1 - W(zhz2))UH(-W(zhz2))UF(-W(zhz2)). Если сравнить с (3.3), то сделав замену Z = W(zi,z2) и учитывая ее антисимметрию, можно сделать вывод, что и для новой пары ММ фильтров выполняется свойство ТВС. Свойство ЛФ.
Если дополнительно потребовать, чтобы W{z\,z2) имело нулевую фазу, a UH{Z\,Z2) и UF(z\,z2) имели линейную фазу (и симметричные относительно нуля центры симметрии), то тогда построенная ММ пара фильтров HQ,FQ также имеет линейную фазу. Действительно, если 4( ,1) = ±z?zr22A(zhz2), B(z ,z2l) = ±z zpB(zhz2), и тогда 1 (1.1) = W(zi,z2), то получим ±z?z?A(zhz2)UH(W(zhz2)) = ±z?z?H0(zhz2). Сравнивая с (2.60), получим, что фильтр Но имеет линейную фазу.
Для успешного синтеза ММ банков фильтров с четным носителем необходимо сначала синтезировать пару фильтров (речь идет о двухканаль-ных системах), каждый из которых является симметричным, удовлетворяет свойству ТВС и имеет четный носитель, т.е. 2k х 21.
Как следует из свойства 2.5 (см. табл. 2), для шахматной матрицы децимации не существует пары фильтров со свойством ТВС, если они оба имеют четный носитель.
Вейвлет-преобразование
Вейвлет-преобразование является инструментом, разбивающим сигнал на составляющие с разными частотами, каждая из которых затем исследуется с разрешением в подходящем масштабе [19]. Вследствие своего междисциплинарного происхождения (математика, физика, техника связи и т.д.), это преобразование нашло применение в самых разнообразных областях, включая обработку сигналов.
Во многих приложениях, имея заданный сигнал /(), необходимо знать его частотную характеристику локально во времени. Обычное преобразование Фурье дает представление о частотных характеристиках, но информацию, касающуюся временной локализации составляющих спектра, обычно трудно извлечь из этих характеристик. Для решения этой задачи используют оконное преобразование Фурье с помощью дополнительной функции-окна, которая может смещаться по оси времени, однако и это не всегда дает хорошие результаты.
Вейвлет-преобразование позволяет получить сходное частотно-временное описание с некоторыми существенными отличиями и преимуществами. Дискретное 1-D вейвлет-преобразование равно [19] Wf(m, п) = оГт 2 J f{t)i){aTmt - nb)dt (4.1) -00 где t = nto, п, m Z - целые числа. Предполагается, что / ip(t)dt = 0. -00
В качестве вейвлетов выбирают различные функции, хорошо локализованные во времени и в пространстве. Часто в качестве ф(-) берут вторую производную функции Гаусса V(t)=(l2)exp(2/2), которая удовлетворяет всем необходимым условиям.
Когда а меняет свое значение, функция а (х)=а-1/2 (х/а) меняется: большие значения масштабирующего параметра \а\ соответствует малым частотам и большому временному масштабу для фа ; малые параметры \а\ соответствуют высоким частотам и малым временным масштабам фа . Изменение параметра Ъ позволяет сместить центр временной локализации: каждая функция фа,ь(х) локализована около s = b. Поэтому (4.1) дает частотно-временное описание f.
Различие между вейвлет-преобразованием и оконным преобразованием Фурье состоит в неодинаковых функциях окна и фа ь. Последняя имеет ширину во времени, соответствующую частоте; высокочастотные фа,ь являются узкими, в то время как низкочастотные фа,ь - намного шире. В результате с помощью вейвлет-преобразования можно получить большую избирательность во времени и по частоте.
В общем случае параметры сдвига и сжатия a, b меняются на множестве R2 с ограничением а О. Функция f(t) может быть восстановлена с помощью формулы обращения 00 00 f = с? j j &W 4-2 -00-00 где () обозначает скалярное произведение в L2. Постоянная Сф зависит только от ф. Формула (4.2) может быть рассмотрена и как способ восстановления /, если известно ее вейвлет-преобразование, и как способ записи / в виде суперпозиции вейвлетов фа ь. Коэффициенты этой суперпозиции заданы через вейвлет-преобразование.
Для дискретного вейвлет-преобразования оба параметра а и Ъ принимают только дискретные значения. Вейвлет функция с дискретными индексами имеет вид Фт,п(Х) = %т/2ф(%тХ - пЬо). (4.3)
Одномерное вейвлет-преобразование применяется для задач обработки в общем случае нестационарных случайных сигналов - анализа и синтеза, оптимизации параметров моделей сигналов, выделения сигналов на фоне шумов различного происхождения. В случае сложных сигналов, например, с импульсными составляющими, благодаря высокому разрешению вейвлет-преобразования во временной области, возможно выделять и анализировать эти составляющие, локализовать фронты импульсов и другие особенности. Вейвлет-преобразование может быть обобщено для ММ функций, что позволяет применять его для обработки ММ сигналов [47].
Вейвлет-преобразование позволяет весьма эффективно создавать банки одномерных и многомерных фильтров для обработки речевых сигналов, изображений и др. [224]. Для изображений можно решать не только вопросы сжатия информации, но и улучшения качества изображений, реставрации путем акцентированного изменения коэффициентов в вейвлет области для изменения интересующих нас компонентов в нужную сторону. Возможно также слияние/совмещение изображений в одно изображение, изменение их размеров и разрешения.
Методы, использующие преобразование Фурье, долго преобладали в области обработки сигналов до 70-х годов. Ситуация полностью изменилась с развитием обработки изображений в 80-х. Изображения плохо моделируются гауссовскими процессами и переходные структуры типа границ часто более важны, чем усредненные свойства. Нелинейные алгоритмы стали неизбежны, открывая проблему обработки сигналов современной математике.
Большой класс изображений описывается функциями с ограниченной полной вариацией /Ву = f\f (x)\dx +оо. Разреженное представление / Є L2[0,1р может быть получено при усечении его разложения в ортонормированием базисе В = {gm}mN- Линейная аппроксимация / длиной Р внутри произведения (f,gm) это ортогональная проекция на пространство Vp, полученная с помощью Р векторов В, а именно с помощью первых Р векторов: р-1 ІР = 22{/ 9т)дт тп=0 201 Максимальная ошибка аппроксимации по множеству сигналов S равна e(S,P) = sup/-/p = sup J2 \{f,9m)\ Доказано, что для шара SBv feS feS m=P функция с ограниченной вариацией наиболее быстро может спадать в базисе В со скоростью E{SBV,P) »Р х [126].
Чтобы улучшить этот результат, создано адаптированное представление, как проекция / на Р базисных векторов, выбранных в зависимости от /: IP=Y1 (f 9m)9m-тпеїр
Нелинейная вейвлет аппроксимация сохраняет Р вейвлет коэффициентов самой большой амплитуды. Эффективность вейвлет базисов исходит из того, что они являются безусловными базисами большого семейства гладких пространств (пространств Бесова) и оптимальны для нелинейных аппроксимаций в шарах этих пространств. Было показано, что когда Р увеличивается, асимптотически E{SBV, Р) = 0(Р 2), и, таким образом, убывание ошибки происходит быстрее, чем при любой линейной аппроксимации, использующей параметры Р, которая спадает самое быстрое, как Р"1 [126].
В конце 80-х годов прошлого столетия масштабирующие уравнения с конечным числом слагаемых стали интенсивно изучаться [47]. К ним подошли почти одновременно в трех областях - в теории аппроксимации, в компьютерной графике (при построении уточняющих алгоритмов аппроксимации и интерполяции функций), а также в теории вейвлет-преобразования (построение вейвлетов с компактным носителем, то есть синтез КИХ БФ). Предтечей теории масштабирующих уравнений можно считать Ж. де Рама, изучавшего предельные кривые алгоритма срезания углов. В теории вейвлетов данные уравнения вошли, начиная с книги Добеши [19].
