Вейвлет Коэна – Добеши – Фово

Вейвлеты Коэна-Добеши-Фово — это семейство биортогональных вейвлетов , которое стало популярным благодаря Ингрид Добеши . ^[1]^[2] Это не то же самое, что ортогональные вейвлеты Добеши , а также не очень похожие по форме и свойствам. Однако идея их конструкции одинакова.

Стандарт JPEG 2000 сжатия использует биортогональный вейвлет Ле Галля – Табатабаи (LGT) 5/3 (разработанный Д. Ле Галлом и Али Дж. Табатабаи). ^[3]^[4]^[5] для сжатия без потерь и вейвлет CDF 9/7 для сжатия с потерями .

Свойства [ править ]

Первичный генератор представляет собой B-сплайн, если простая факторизация $q_{\text{prim}}(X)=1$ (см. ниже).
Двойной генератор имеет максимально возможное количество коэффициентов гладкости для своей длины.
Все генераторы и вейвлеты в этом семействе симметричны.

Строительство [ править ]

Для каждого натурального числа A существует единственный многочлен $Q_{A}(X)$ степени A − 1, удовлетворяющую тождеству

\left(1-{\frac {X}{2}}\right)^{A}\,Q_{A}(X)+\left({\frac {X}{2}}\right)^{A}\,Q_{A}(2-X)=1.

Это тот же полином, который использовался при построении вейвлетов Добеши . Но вместо спектральной факторизации здесь мы пытаемся факторизовать

Q_{A}(X)=q_{\text{prim}}(X)\,q_{\text{dual}}(X),

где факторы представляют собой полиномы с действительными коэффициентами и постоянным коэффициентом 1. Тогда

a_{\text{prim}}(Z)=2Z^{d}\,\left({\frac {1+Z}{2}}\right)^{A}\,q_{\text{prim}}\left(1-{\frac {Z+Z^{-1}}{2}}\right)

и

a_{\text{dual}}(Z)=2Z^{d}\,\left({\frac {1+Z}{2}}\right)^{A}\,q_{\text{dual}}\left(1-{\frac {Z+Z^{-1}}{2}}\right)

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

В зависимости от корней $Q_{A}(X)$ , может быть до $2^{A-1}$ различные факторизации. Простая факторизация $q_{\text{prim}}(X)=1$ и $q_{\text{dual}}(X)=Q_{A}(X)$ , то основной масштабирующей функцией является B-сплайн порядка A − 1. Для A = 1 получается ортогональный вейвлет Хаара .

Таблицы коэффициентов [ править ]

Таким образом, для A = 2 получается 5/3-вейвлет ЛеГалла :

А	Вопрос _А ( Икс )	q _прим ( X )	q _{двойной} ( X )	число _{простое} ( Z )	двойной ( Z )
2	$1+X$	1	$1+X$	${\frac {1}{2}}(1+Z)^{2}\,Z$	${\frac {1}{2}}(1+Z)^{2}\,\left(-{\frac {1}{2}}+2\,Z-{\frac {1}{2}}\,Z^{2}\right)$

Для A = 4 получается 9/7-CDF-вейвлет . Получаешь $Q_{4}(X)=1+2X+{\tfrac {5}{2}}X^{2}+{\tfrac {5}{2}}X^{3}$ , этот многочлен имеет ровно один вещественный корень, поэтому он является произведением линейного множителя $1-cX$ и квадратичный коэффициент. Коэффициент c , обратный корню, имеет приблизительное значение -1,4603482098.

А	Вопрос _А ( Икс )	q _прим ( X )	q _{двойной} ( X )
4	$1+2X+{\tfrac {5}{2}}X^{2}+{\tfrac {5}{2}}X^{3}$	$1-cX$	$1+(c+2)X+(c^{2}+2c+{\tfrac {5}{2}})X^{2}$

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

к	Анализ фильтра нижних частот ( двойной ₎ 1/2	Анализ фильтра верхних частот ( б _{двойной} )	Синтезный фильтр нижних частот ( прим )	Синтез-фильтр верхних частот (1/2 б _прим )
-4	0.026748757411	0	0	0.026748757411
-3	-0.016864118443	0.091271763114	-0.091271763114	0.016864118443
-2	-0.078223266529	-0.057543526229	-0.057543526229	-0.078223266529
-1	0.266864118443	-0.591271763114	0.591271763114	-0.266864118443
0	0.602949018236	1.11508705	1.11508705	0.602949018236
1	0.266864118443	-0.591271763114	0.591271763114	-0.266864118443
2	-0.078223266529	-0.057543526229	-0.057543526229	-0.078223266529
3	-0.016864118443	0.091271763114	-0.091271763114	0.016864118443
4	0.026748757411	0	0	0.026748757411

Нумерация [ править ]

Существует две совпадающие схемы нумерации вейвлетов семейства CDF:

количество коэффициентов сглаживания фильтров нижних частот или, что эквивалентно, количество моментов исчезновения фильтров верхних частот, например «2, 2»;
размеры фильтров нижних частот или, что эквивалентно, размеры фильтров верхних частот, например «5, 3».

Первая нумерация была использована в книге Добеши « Десять лекций по вейвлетам» .Ни одна из этих нумераций не является уникальной. Количество исчезающих моментов не говорит о выбранной факторизации. Банк фильтров с размерами фильтров 7 и 9 может иметь 6 и 2 исчезающих момента при использовании тривиальной факторизации или 4 и 4 исчезающих момента, как в случае вейвлета JPEG 2000. Поэтому один и тот же вейвлет можно назвать «CDF 9/7» (в зависимости от размеров фильтра) или «биортогональный 4, 4» (в зависимости от исчезающих моментов). Аналогичным образом, один и тот же вейвлет может называться «CDF 5/3» (в зависимости от размеров фильтра) или «биортогональный 2, 2» (в зависимости от исчезающих моментов).

Лифтинг-разложение [ править ]

Для тривиально факторизованных наборов фильтров лифтинг-разложение . можно явно указать ^[6]

количество гладкости Четное коэффициентов

Позволять $n$ — количество коэффициентов сглаживания в фильтре нижних частот B-сплайна,который должен быть четным.

Затем определите рекурсивно

{\begin{aligned}a_{0}&={\frac {1}{n}},\\a_{m}&={\frac {1}{(n^{2}-4\cdot m^{2})\cdot a_{m-1}}}.\end{aligned}}

Подъемные фильтры

s_{m}(z)=a_{m}\cdot (2\cdot m+1)\cdot (1+z^{(-1)^{m}}).

В заключение, промежуточные результаты подъема таковы.

{\begin{aligned}x_{-1}(z)&=z,\\x_{0}(z)&=1,\\x_{m+1}(z)&=x_{m-1}(z)+a_{m}\cdot (2\cdot m+1)\cdot (z+z^{-1})\cdot z^{(-1)^{m}}\cdot x_{m}(z),\end{aligned}}

что приводит к

x_{n/2}(z)=2^{-n/2}\cdot (1+z)^{n}\cdot z^{n/2{\bmod {2}}-n/2}.

Фильтры $x_{n/2}$ и $x_{n/2-1}$ составляют набор фильтров CDF- n ,0.

коэффициентов гладкости Нечетное количество

Теперь позвольте $n$ быть странным.

Затем определите рекурсивно

{\begin{aligned}a_{0}&={\frac {1}{n}},\\a_{m}&={\frac {1}{(n^{2}-(2\cdot m-1)^{2})\cdot a_{m-1}}}.\end{aligned}}

Подъемные фильтры

s_{m}(z)=a_{m}\cdot ((2\cdot m+1)+(2\cdot m-1)\cdot z)/z^{m{\bmod {2}}}.

В заключение, промежуточные результаты подъема таковы.

{\begin{aligned}x_{-1}(z)&=z,\\x_{0}(z)&=1,\\x_{1}(z)&=x_{-1}(z)+a_{0}\cdot x_{0}(z),\\x_{m+1}(z)&=x_{m-1}(z)+a_{m}\cdot ((2\cdot m+1)\cdot z+(2\cdot m-1)\cdot z^{-1})\cdot z^{(-1)^{m}}\cdot x_{m}(z),\end{aligned}}

что приводит к

x_{(n+1)/2}(z)\sim (1+z)^{n},

где мы пренебрегаем переводом и постоянным множителем.

Фильтры $x_{(n+1)/2}$ и $x_{(n-1)/2}$ составляют набор фильтров CDF- n ,1.

Приложения [ править ]

Вейвлет Коэна-Добеши-Фово и другие биортогональные вейвлеты использовались для сжатия отпечатков пальцев для ФБР . ^[7] Стандарт сжатия отпечатков пальцев таким способом разработали Том Хоппер (ФБР), Джонатан Брэдли ( Национальная лаборатория Лос-Аламоса ) и Крис Брислоун (Национальная лаборатория Лос-Аламоса). ^[7] Используя вейвлеты, можно достичь степени сжатия примерно 20 к 1, то есть изображение размером 10 МБ можно уменьшить до 500 КБ, при этом пройдя тесты на распознавание. ^[7]

Внешние ссылки [ править ]

Ссылки [ править ]

^ Коэн, А.; Добеши, И.; Фово, Ж.-К. (1992). «Биортогональные базисы компактных вейвлетов». Сообщения по чистой и прикладной математике . 45 (5): 485–560. дои : 10.1002/cpa.3160450502 .
^ Добеши, Ингрид (1992). Десять лекций по вейвлетам . СИАМ. дои : 10.1137/1.9781611970104 . ISBN 978-0-89871-274-2 .
^ Салливан, Гэри (8–12 декабря 2003 г.). «Общие характеристики и соображения по проектированию временного поддиапазонного видеокодирования» . МСЭ-Т . Группа экспертов по видеокодированию . Проверено 13 сентября 2019 г.
^ Бовик, Алан С. (2009). Основное руководство по обработке видео . Академическая пресса . п. 355. ИСБН 9780080922508 .
^ Галл, Д. Ле; Табатабай, Али Дж. (1988). «Поддиапазонное кодирование цифровых изображений с использованием симметричных фильтров с коротким ядром и методов арифметического кодирования». ICASSP-88, Международная конференция по акустике, речи и обработке сигналов . С. 761–764 т. 2. дои : 10.1109/ICASSP.1988.196696 . S2CID 109186495 .
^ Тилеманн, Хеннинг (2006). «раздел 3.2.4» . Оптимально согласованные вейвлеты (кандидатская диссертация).
↑ Перейти обратно: Перейти обратно: ^а ^б ^с Ципра, Барри Артур (1994). Что происходит в математических науках (Том 2) Вейвлеты Parlez-vous? . Американское математическое общество. ISBN 978-0821889985 .

[1] Коэн, А.; Добеши, И.; Фово, Ж.-К. (1992). «Биортогональные базисы компактных вейвлетов». Сообщения по чистой и прикладной математике . 45 (5): 485–560. дои : 10.1002/cpa.3160450502 .

[2] Добеши, Ингрид (1992). Десять лекций по вейвлетам . СИАМ. дои : 10.1137/1.9781611970104 . ISBN 978-0-89871-274-2 .

[3] Салливан, Гэри (8–12 декабря 2003 г.). «Общие характеристики и соображения по проектированию временного поддиапазонного видеокодирования» . МСЭ-Т . Группа экспертов по видеокодированию . Проверено 13 сентября 2019 г.

[4] Бовик, Алан С. (2009). Основное руководство по обработке видео . Академическая пресса . п. 355. ИСБН 9780080922508 .

[5] Галл, Д. Ле; Табатабай, Али Дж. (1988). «Поддиапазонное кодирование цифровых изображений с использованием симметричных фильтров с коротким ядром и методов арифметического кодирования». ICASSP-88, Международная конференция по акустике, речи и обработке сигналов . С. 761–764 т. 2. дои : 10.1109/ICASSP.1988.196696 . S2CID 109186495 .

[6] Тилеманн, Хеннинг (2006). «раздел 3.2.4» . Оптимально согласованные вейвлеты (кандидатская диссертация).

[cipra94-7] Перейти обратно: Перейти обратно: ^а ^б ^с Ципра, Барри Артур (1994). Что происходит в математических науках (Том 2) Вейвлеты Parlez-vous? . Американское математическое общество. ISBN 978-0821889985 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]