Вейвлет Коэна – Добеши – Фово - Cohen–Daubechies–Feauveau wavelet - Wikipedia

Пример двумерного вейвлет-преобразования, который используется в JPEG2000

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

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

Характеристики

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

Строительство

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

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

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

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

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

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

и

${\displaystyle 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 - некоторое целое число, используемое для центрирования симметричных последовательностей в нуле или для установления причинности соответствующих дискретных фильтров.

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

Таблицы коэффициентов

Вейвлет Коэна – Добеши – Фово 5/3, используемый в стандарте JPEG 2000

За А = 2 таким образом получается LeGall 5/3-вейвлет:

А	QА(Икс)	qчопорный(Икс)	qдвойной(Икс)	ачопорный(Z)	адвойной(Z)
2	${\displaystyle 1+X}$	1	${\displaystyle 1+X}$	${\displaystyle {\frac {1}{2}}(1+Z)^{2}\,Z}$	${\displaystyle {\frac {1}{2}}(1+Z)^{2}\,\left(-{\frac {1}{2}}+2\,Z-{\frac {1}{2}}\,Z^{2}\right)}$

---

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

А	QА(Икс)	qчопорный(Икс)	qдвойной(Икс)
4	${\displaystyle 1+2X+{\tfrac {5}{2}}X^{2}+{\tfrac {5}{2}}X^{3}}$	${\displaystyle 1-cX}$	${\displaystyle 1+(c+2)X+(c^{2}+2c+{\tfrac {5}{2}})X^{2}}$

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

k	Фильтр нижних частот анализа (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» (на основе исчезающих моментов).

Лифтинг разложения

Для тривиально факторизованных наборов фильтров a разложение подъема может быть дано явно.^[6]

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

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

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

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

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

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

В итоге промежуточные результаты подъема

${\displaystyle {\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}}}$

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

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

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

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

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

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

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

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

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

В итоге промежуточные результаты подъема

${\displaystyle {\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}}}$

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

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

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

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

Приложения

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

внешняя ссылка

• JPEG 2000: как это работает?
• Исходный код быстрого дискретного CDF 9/7 вейвлет-преобразования на языке C (реализация подъема) на Wayback Machine (архивировано 5 марта 2012 г.)
• CDF 9/7 Wavelet Transform для 2D-сигналов с помощью подъема: исходный код на Python
• Реализация 5/3-CDF-Wavelet с открытым исходным кодом на C # для произвольной длины

Рекомендации

1. Cohen, A .; Daubechies, I .; Feauveau, J.-C. (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 г.). «Общие характеристики и конструктивные соображения для кодирования видео временного поддиапазона». ITU-T. Группа экспертов по кодированию видео. Получено 13 сентября 2019.
4. Бовик, Алан С. (2009). Основное руководство по обработке видео. Академическая пресса. п. 355. ISBN  9780080922508.
5. Галл, Д. Ле; Табатабай, Али Дж. (1988). «Подполосное кодирование цифровых изображений с использованием симметричных коротких ядерных фильтров и методов арифметического кодирования». ICASSP-88., Международная конференция по акустике, речи и обработке сигналов: 761–764 т.2. Дои:10.1109 / ICASSP.1988.196696. S2CID  109186495.
6. Тилеманн, Хеннинг (2006). «раздел 3.2.4». Оптимально согласованные вейвлеты (Кандидатская диссертация).
7. Сипра, Барри Артур (1994). Что происходит в математических науках (том 2) Parlez-vous Wavelets?. Американское математическое общество. ISBN  978-0821889985.