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

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

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

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

Содержание

  • 1 Свойства
  • 2 Конструкция
  • 3 Таблицы коэффициентов
  • 4 Нумерация
  • 5 Разложение подъема
    • 5.1 Четное число коэффициентов гладкости
    • 5.2 Нечетное число коэффициентов гладкости
  • 6 Приложения
  • 7 Внешние ссылки
  • 8 Ссылки

Свойства

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

Конструкция

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

(1 - X 2) AQA (X) + (X 2) AQA (2 - 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 \ left (1 - {\ frac {X} {2}} \ right) ^ {A} \, Q_ {A} ( X) + \ влево ({\ frac {X} {2}} \ right) ^ {A} \, Q_ {A} (2-X) = 1.}

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

QA (X) = q prim (X) q dual (X), {\ displaystyle Q_ {A} (X) = q _ {\ text {prim} } (X) \, q _ {\ text {dual}} (X),}{\ displaystyle Q_ {A} (X) = q _ {\ text {prim}} (X) \, q _ {\ text {dual} } (X),}

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

a prim (Z) = 2 Z d (1 + Z 2) A q прим (1 - Z + Z - 1 2) {\ 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 {prim}} (Z) = 2Z ^ {d} \, \ left ({\ frac {1 + Z} {2}} \ right) ^ {A} \, q _ {\ text {prim}} \ left (1 - {\ frac {Z + Z ^ {- 1}} {2}} \ right)}

и

двойное (Z) = 2 Z d (1 + Z 2) A q двойное (1 - Z + Z - 1 2) {\ 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)}{\ 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 - некоторое целое число, используемое для центрирования симметричных последовательностей в нуле или для того, чтобы сделать соответствующие дискретные фильтры причинными.

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

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

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

Для A = 2 один получает таким образом 5/3-вейвлет LeGall :

AQA(X)qprim (X)qdual (X)aprim (Z)aдвойной (Z)
21 + X {\ displaystyle 1 + X}{\ displaystyle 1 + X} 11 + X {\ displaystyle 1 + X}{\ displaystyle 1 + X} 1 2 (1 + Z) 2 Z {\ displaystyle {\ frac {1} {2}} (1 + Z) ^ {2} \, Z}{\ displaystyle {\ frac {1} {2}} (1 + Z) ^ {2} \, Z} 1 2 (1 + Z) 2 (- 1 2 + 2 Z - 1 2 Z 2) {\ displaystyle {\ frac {1} {2}} (1 + Z) ^ {2} \, \ left (- {\ frac {1} {2}} + 2 \, Z - {\ frac {1} {2) }} \, Z ^ {2} \ right)}{\ displaystyle {\ 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 + 2 X + 5 2 X 2 + 5 2 X 3 {\ displaystyle Q_ {4} (X) = 1 + 2X + {\ tfrac {5} {2}} X ^ {2} + {\ tfrac {5} {2}} X ^ {3}}{\ displaystyle Q_ {4} (X) = 1 + 2X + {\ tfrac {5} {2}} X ^ {2} + {\ tfrac {5} {2}} X ^ {3}} , этот многочлен имеет ровно один действительный корень, поэтому он является произведением линейного множителя 1 - c X {\ displaystyle 1-cX}{\ displaystyle 1-cX} и квадратичный множитель. Коэффициент c, который является обратным корню, имеет приблизительное значение -1,4603482098.

AQA(X)qпервичный (X)qдвойной (X)
41 + 2 X + 5 2 X 2 + 5 2 X 3 {\ displaystyle 1 + 2X + { \ tfrac {5} {2}} X ^ {2} + {\ tfrac {5} {2}} X ^ {3}}{\ displaystyle 1 + 2X + {\ tfrac {5} {2}} X ^ {2} + {\ tfrac {5} {2 }} X ^ {3}} 1 - c X {\ displaystyle 1-cX}{\ displaystyle 1-cX} 1 + (с + 2) Икс + (с 2 + 2 с + 5 2) Икс 2 {\ displaystyle 1+ (c + 2) X + (c ^ {2} + 2c + {\ tfrac {5} {2}}) X ^ {2}}{\ displaystyle 1+ (c + 2) X + (c ^ {2} + 2c + {\ tfrac {5} {2}}) X ^ {2}}

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

230>-0,078223266529
kАнализ фильтра нижних частот

(1/2 a двойной)

Анализ фильтр верхних частот

(b двойной)

фильтр нижних частот синтеза

(a прим)

фильтр верхних частот синтеза

(1/2 b прим)

−40,026748757411000,026748757411
-3-0,0168641184430,091271763114-0,091271763114-316864118>-0,078223266529-0,057543526229-0,057543526229-0,078223266529
-10,266864118443-0,5912717631140,591271763114-0,266864118443
00.60294901 82361.115087051,115087050.602949018236
10,266864118443-0,5912717631140,591271763116
  • 0,5912717631184
  • -0,057543526229-0,057543526229-0,078223266529
    3-0,0168641184430,091271763117 <173113>0,091271763114173113>>0,016864118443
    40,026748757411000,026748757411

    Нумерация

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

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

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

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

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

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

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

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

    a 0 = 1 n, a m = 1 (n 2 - 4 ⋅ m 2) ⋅ a m - 1. {\ displaystyle {\ begin {align} a_ {0} = {\ frac {1} {n}}, \\ a_ {m} = {\ frac {1} {(n ^ {2} -4 \ cdot m ^ {2}) \ cdot a_ {m-1}}}. \ end {align}}}{\ displaystyle {\ begin {align} a_ {0} = {\ frac {1} { n}}, \\ a_ {m} = {\ frac {1} {(n ^ {2} -4 \ cdot m ^ {2}) \ cdot a_ {m-1}}}. \ end {выровнено }}}

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

    sm (z) = am ⋅ (2 ⋅ m + 1) ⋅ (1 + z (- 1) м). {\ displaystyle s_ {m} (z) = a_ {m} \ cdot (2 \ cdot m + 1) \ cdot (1 + z ^ {(- 1) ^ {m}}).}{\ displaystyle s_ {m } (z) = a_ {m} \ cdot (2 \ cdot m + 1) \ cdot (1 + z ^ {(- 1) ^ {m}}).}

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

    x - 1 (z) = z, x 0 (z) = 1, xm + 1 (z) = xm - 1 (z) + am ⋅ (2 ⋅ m + 1) ⋅ (z + z - 1) ⋅ z (- 1) м ⋅ xm (z), {\ displaystyle {\ begin {align} 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 {align}}}{\ displaystyle {\ begin {выровнено } 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), \ конец {выровнен}}}

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

    xn / 2 (z) Знак равно 2 - N / 2 ⋅ (1 + Z) N ⋅ Zn / 2 по модулю 2 - N / 2. {\ displaystyle x_ {n / 2} (z) = 2 ^ {- n / 2} \ cdot (1 + z) ^ {n} \ cdot z ^ {n / 2 {\ bmod {2}} - n / 2}.}{\ displaystyle x_ {n / 2} (z) = 2 ^ {- n / 2} \ cdot (1 + z) ^ {n} \ cdot z ^ {n / 2 {\ bmod {2}} - n / 2}.}

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

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

    Теперь пусть n {\ displaystyle n}n будет нечетным.

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

    a 0 = 1 n, a m = 1 (n 2 - (2 ⋅ m - 1) 2) ⋅ a m - 1. {\ displaystyle {\ begin {align} a_ {0} = {\ frac {1} {n}}, \\ a_ {m} = {\ frac {1} {(n ^ {2} - (2 \ cdot m-1) ^ {2}) \ cdot a_ {m-1}}}. \ end {align}}}{\ displaystyle {\ begin {align} a_ {0} = {\ frac {1} {n}}, \\ a_ {m} = { \ frac {1} {(n ^ {2} - (2 \ cdot m-1) ^ {2}) \ cdot a_ {m-1}}}. \ end {align}}}

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

    sm (z) = am ⋅ ((2 ⋅ m + 1) + (2 ⋅ m - 1) ⋅ z) / zm mod 2. {\ Displaystyle s_ {m} (z) = a_ {m} \ cdot ((2 \ cdot m + 1) + (2 \ cdot m-1) \ cdot z) / z ^ {m {\ bmod {2} }}.}{\ displaystyle s_ {m} (z) = a_ {m} \ cdot ((2 \ cdot m + 1) + (2 \ cdot m-1) \ cdot z) / z ^ {м {\ bmod {2}}}.}

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

    x - 1 (z) = z, x 0 (z) = 1, x 1 (z) = x - 1 (z) + a 0 ⋅ x 0 (z), xm + 1 (z) = xm - 1 (z) + am ⋅ ((2 ⋅ m + 1) ⋅ z + (2 ⋅ m - 1) ⋅ z - 1) ⋅ z ( - 1) м ⋅ xm (z), {\ displaystyle {\ begin {align} 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 {align}}}{\ Displaystyle {\ begin {align} 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 {align}}}

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

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

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

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

    Приложения

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

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

    Ссылки

    1. ^Cohen, A.; Добеши, I.; Feauveau, J.-C. (1992). «Биортогональные основы всплесков с компактным носителем». Сообщения по чистой и прикладной математике. 45 (5): 485–560. doi : 10.1002 / cpa.3160450502.
    2. ^Добеши, Ингрид (1992). Десять лекций по вейвлетам. СИАМ. doi : 10.1137 / 1.9781611970104. ISBN 978-0-89871-274-2.
    3. ^Салливан, Гэри (8–12 декабря 2003 г.). «Общие характеристики и конструктивные соображения для кодирования видео временного поддиапазона». МСЭ-Т. Группа экспертов по кодированию видео. Проверено 13 сентября 2019 г. CS1 maint: date format (ссылка )
    4. ^Bovik, Alan C. (2009). The Essential Guide to Video Processing. Academic Press. p. 355. ISBN 9780080922508.
    5. ^Галл, Д. Ле; Табатабай, Али Дж. (1988). «Подполосное кодирование цифровых изображений с использованием симметричных коротких ядерных фильтров и арифметики. методы кодирования ». ICASSP-88., Международная конференция по акустике, речи и обработке сигналов: 761–764, том 2. doi : 10.1109 / ICASSP.1988.196696.
    6. ^Тилеманн, Хеннинг ( 2006). "Раздел 3.2.4". Оптимально согласованные вейвлеты (докторская диссертация).
    7. ^ Ципра, Барри Артур (1994). Что происходит в математических науках (том 2) Парлез -вус вейвлеты ?. Американское математическое общество. ISBN 978-0821889985.
    Последняя правка сделана 2021-05-15 14:01:13
    Содержание доступно по лицензии CC BY-SA 3.0 (если не указано иное).
    Обратная связь: support@alphapedia.ru
    Соглашение
    О проекте