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

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

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

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

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

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

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

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

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

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

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

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

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

---

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

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

Нумерация

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

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

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

Подъем разложения

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

Четное число факторов сглаживания

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

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

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

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

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

Теперь давайте будем странными. ${\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},}$

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

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

Приложения

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

Внешние ссылки

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

Ссылки

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