(по цифровому вещанию) Dvorkovich_V_Cifrovye_videoinformacionnye_sistemy
.pdf
Глава 8. Другие методы кодирования изображений
Рис. 8.11. Аттрактор для |
Рис. 8.12. Аттрактор для |
доменов 4 × 4 пиксела |
доменов 8 × 8 пикселов |
Следует обратить внимание на огромную разницу во времени при упаковке и восстановлении изображения. Процесс упаковки при рассмотренных вариантах подбора ранговых областей занимает интервал времени, на несколько порядков больший, чем процесс восстановления, реализуемый в реальном масштабе времени.
Рис. 8.13 иллюстрирует одно из основных свойств аттрактора — процесс восстановления этого же аттрактора но из другого исходного изображения (левый верхний угол). Как видно, после пятой итерации восстановления получается тот же аттрактор.
Таким образом, фрактальные методы обработки изображений уже сейчас могут найти применение в телевидении при заранее сжатых сюжетах (например, кинофильмах) и распаковке в реальном масштабе времени.
Дальнейшие исследования в этом направлении, возможно, позволят реализовать фрактальные алгоритмы и для непрерывного процесса кодирования/декодирования динамических изображений.
8.3. Фрактальные методы кодирования изображений
Рис. 8.13. Восстановление изображения (аттрактора), сжатого фрактальным методом, из другого (произвольного) изображения
Вейвлеты — это семейство математических функций определенной формы, локальных как во временной, так и в частотной областях [3.98-3.106]. Вейвлеты обычно формируются с помощью одной порождающей базовой функции путем ее сдвигов и растяжений по оси времени. Вейвлет-преобразование (WT — Wavelet Transform) сигналов является обобщением спектрального анализа (типичный представитель — классическое преобразование Фурье). Для анализа формы и спектра сигналов обычно используют так называемое непрерывное преобразование (НВП, CWT — Continious Wavelet Transform), при преобразовании и кодировании сигналов применяют дискретное преобразование (ДВП, DWT — Discrete Wavelet Transform).
Вейвлет-преобразования в общем случае используют две непрерывные, взаи-
мозависимые и интегрируемые по всей временной оси t функции:
|
∞ |
|
|
– вейвлет-функции ψ(t) с нулевым значением интеграла |
ψ(t)dt = 0 и с |
|
−∞ |
частотным Фурье-образом Ψ(ω); c использованием этих функций можно выделить локальные особенности сигнала;
– масштабирующие, так называемые скейлинг-функции ϕ(t) с единичным
∞
значением интеграла ϕ(t)dt = 1 ; с их помощью реализуется грубое
−∞
приближение (аппроксимация) сигнала, они необходимы при раздельном анализе низкочастотных и высокочастотных составляющих.
Вейвлет-функция ψ(t) определяется той или иной базисной функцией ψ0(t)
с применением к ней операций смещения во времени и масштабирования: |
|
|||||||
ψ(t) |
≡ |
ψ (t) = a−1/2 |
ψ |
|
|
t − b |
, |
(9.1) |
|
a,b |
|
0 |
a |
|
|
||
где a и b — действительные числа (a, b R), параметр a > 0 определяет масштаб
функции ψ(t), а b — ее смещение по временной оси. |
|
Фурье-образ ψ(t) определяется выражением: |
|
Ψ(ω) = ∞ ψ(t) · e−jωtdt. |
(9.2) |
−∞
Вкачестве примеров аналитически заданных базисных вейвлет-функций ψ0(t) ≡
≡ψ1,0(t) можно привести:
9.1. Непрерывное вейвлет-преобразование
Рис. 9.1. Базисные вейвлет-функции: а) Хаара; б) мексиканская шляпа; в) Морле; |
|
||
г) производная гауссовой кривой |
|
||
вейвлет Хаара (рис. 9.1а): |
|
|
|
ψH (t) = |
1, |
при 0 t < 1/2, |
|
1, |
при 1/2 t < 1, |
(9.3) |
|
|
−0, |
иначе; |
|
мексиканская шляпа (рис. 9.1б): |
|
|
|
2 |
|
2 |
|
ψMhat(t) = √ |
|
π−1/4(1 |
− t2) · e−t /2; |
3 |
|||
вейвлет Морле — модулированная Гауссова кривая (рис. 9.1в):
ψM (t) = π−1/4 e−jαt − e−α2/2 · e−t2/2, где α = π
производная Гауссовой кривой (рис. 9.1г):
√2π−1/4t · e−t2/2.
(9.4)
+
ln22 ; (9.5)
(9.6)
-
Допустим, сигнал u(t) стремится к нулю при t → ±∞ и обладает конечной энергией: P = ∞ u2(t)dt < ∞. По аналогии с преобразованием Фурье прямое
−∞
Глава 9. Вейвлеты и кратномасштабная обработка изображений
Рис. 9.2. Форма и спектр вейвлетов четного типа при разных значениях параметра «a» (мексиканская шляпа) — а, б; форма и спектр вейвлетов нечетного типа при разных значениях параметра «a» (производная Гауссовой кривой) — в, г
непрерывное вейвлет-преобразование задается вейвлет-коэффициентами: |
|
|
|
∞ |
|
C(a, b) = |
u(t)ψa,b(t)dt, (a, b R), a > 0. |
(9.7) |
−∞
Прямое непрерывное вейвлет-преобразование является разложением сигнала по всем возможным сдвигам и растяжениям/сжатиям сигнала u(t).
В отличие от Фурье-спектра C(a, b) является функцией двух аргументов: временного масштаба «a» (в единицах, обратных частоте) и временного смещения «b» (в единицах времени).
Локальные особенности сигналов наиболее эффективно можно проанализировать путем выбора или расчета формы используемых вейвлет-функций и их частотного спектра. Так, при анализе гармонических сигналов вейвлетами четного типа (например, рис. 9.2а, б) коэффициенты C(a, b) воспроизводятся в виде ярких горизонтальных полос с пиками и впадинами на доминирующих частотах вейвлетов, совпадающих с частотой гармоник сигналов. Нарушения гладкости сигналов фиксируются вертикальными полосами, пики в сигналах выделяются максимумами, а впадины — минимумами вейвлетных коэффициентов. Вейвлеты нечетного типа (например, рис. 9.2в, г) более резко реагируют на скачки
9.1. Непрерывное вейвлет-преобразование |
|
Рис. 9.3. Преобразования импульсов Кронекера (а), сигналов Лапласа (б) и сигналов Гаус- |
|
са (в) с применением вейвлета «мексиканская шляпа» |
|
и быстрые изменения в сигналах, отмечая их максимумами или минимумами в зависимости от знака производных.
На рис. 9.3 приведены результаты применения вейвлета ψMhat(t) для анализа следующих сигналов: двух разнополярных импульсов Кронекера, сигналов, форма которых подчиняется законам Лапласа и Гаусса. Цветовая гамма спектра на этих рисунках соответствует естественному цветовому ряду от красного (большие значения коэффициентов) к фиолетовому (малые значения коэффициентов). На сечениях спектра видно, что свертка единичных импульсов с разномасштабными вейвлетами повторяет форму вейвлетов, как это и положено при операции свертки. Соответственно, линии максимальных экстремумов на сечениях (в зависимости от полярности) определяют временное положение импульсов.
На рис. 9.4 приведены результаты применения вейвлета ψDG(t) для анализа импульсов с крутым, плавным и линейным переходами при использовании вейвлета «производная Гауссовой кривой». Центры переходов фиксируются нулевыми значениями коэффициентов C(a, b), а их крутизна отражается в основном на значениях функции C(a, b) при малых величинах параметра «a».
Формула реконструкции сигнала u(t) с применением обратного непрерывного вейвлет-преобразования представима в виде:
|
∞ ∞ |
|
|
|
|
u(t) = Cψ−1 |
|
C(a, b) · ψa,b(t) · |
dadb |
, |
(9.8) |
|
|||||
a2 |
−∞ −∞
где постоянная Cψ зависит только от базисной функции ψ0(t) и определяется так:
Cψ = 2π |
|
|Ψ0|ω|)| |
|
dω < ∞. |
(9.9) |
|
∞ |
(ω |
2 |
|
|
−∞
Глава 9. Вейвлеты и кратномасштабная обработка изображений
Рис. 9.4. Преобразования импульсов с крутым (а), плавным (б) и линейным (в) перехо- |
дами при использовании вейвлета «производная гауссовой кривой» |
Условие конечности Cψ ограничивает класс функций, которые можно применить в качестве вейвлетов. Для обеспечения сходимости интеграла (9.8) в нуле значение Ψ0(0) должно быть тождественно равно нулю и, следовательно, функция ψ(t) должна иметь нулевое среднее значение. Это означает, что не для всех сигналов возможна их точная реконструкция при использовании базисной функции ψ0(t).
-
Для уменьшения избыточности вейвлет-преобразований обычно задают дискретные значения коэффициентов a и b на множестве целых чисел I {−∞, ∞}. Чаще всего используют так называемое диадное преобразование, при котором
a = 2m, b = k · 2m, ψm,k = 2−m/2ψ 2−mt − k , m, k I. |
(9.10) |
Вейвлет-коэффициенты прямого преобразования: |
|
|
|
Cm,k = dm,k = ∞ u(t) · ψm,k(t)dt, |
(9.11) |
−∞
где dm,k — дискретные детализирующие коэффициенты для вейвлет-представле- ния сигнала уровня k. Обратное дискретное преобразование для непрерывных сигналов задается формулой:
∞ |
∞ |
|
|
|
|
u(t) = Cψ |
dm,k · ψm,k. |
(9.12) |
−∞ −∞
Часто осуществляется нормировка базисных функций в частотной области таким образом, что Cψ = 1.
9.3. Кратномасштабный вейвлет-анализ
Как и при непрерывном вейвлет-преобразовании, обратное дискретное преобразование (9.12) не может обеспечить восстановление сигналов, имеющих ненулевую постоянную составляющую. В этом случае восстановление дает близкий к исходному сигнал, причем близость воспринимается в смысле обеспечения минимума среднеквадратичной погрешности восстановления.
Поэтому при обработке таких сигналов вейвлеты используются, как правило,
впаре со связанными с ними дискретными (масштабирующими) скейлинг-функ- циями. Если вейвлеты рассматривать как аналоги полосовых фильтров сигнала,
восновном высокочастотных, при выделении локальных особенностей в сигнале, то скейлинг-функции вейвлетов представляют собой аналоги низкочастотных фильтров, которыми из сигнала выделяются в отдельный массив составляющие, не прошедшие вейвлетную фильтрацию.
Аналитика масштабирующей функций при произвольном m = m0 − ϕk(t) = = ϕm0 ,k(t) практически повторяет выражения (9.10)–(9.11):
ϕk = 2−m0/2ϕ 2−m0 t − k , m0, k I, |
ck = ∞ u(t) · ϕk (t)dt, |
|
−∞ |
и образует дополнительный базис пространства L2(R) на всей действительной оси R(−∞, ∞).
Сумма вейвлет-коэффициентов и скейлинг-коэффициентов разложения сигналов соответственно дает возможность выполнять точную реконструкцию сигналов, при этом вместо (9.12) используется следующее соотношение при обратном преобразовании:
|
∞ |
∞ ∞ |
|
|
|
|
|
u(t) = |
ck · ϕk(t) + |
dm,k · ψm,k(t), |
(9.13) |
|
k=−∞ |
m=m0 k=−∞ |
|
где ck — скейлин-коэффициенты, которые обычно называют коэффициентами аппроксимации сигнала, dm,k — вейвлет-коэффициенты или коэффициенты детализации.
Практическое использование вейвлет-преобразований связано в основном с дискретными вейвлетами, поскольку широко применяются цифровые методы обработки данных, а также в силу различий дискретного и непрерывного преобразований, хотя последние дают несколько более наглядное представление результатов анализа в виде поверхностей вейвлет-коэффициентов по непрерывным переменным.
На рис. 9.5 анализируемый сигнал состоит из двух модулированных гауссианов. Преобразование вейвлетом Морле четко показывает их пространственную и частотную локализацию, в то время как спектр Фурье дает только частотную локализацию.
Однако базисы на основе непрерывных вейвлетов часто не являются строго ортонормированными, поскольку их элементы бесконечно дифференцируемы и экспоненциально спадают на бесконечности. У дискретных вейвлетов эти проблемы легко снимаются, что обеспечивает более точную реконструкцию сигналов.
Глава 9. Вейвлеты и кратномасштабная обработка изображений
Рис. 9.5. Преобразование вейвлетом Морле сигнала в виде двух модулированных гауссианов
-
Представление формы сигнала путем суммирования его грубой аппроксимации с добавлением детализирующих локальных уточнений на различных временных интервалах — основа его кратномасштабного анализа (Multiresolution Analisis).
Часто требуется представить сигнал в виде совокупности его последовательных приближений. Например, при анализе изображений из некоторой базы данных можно сначала передать грубую его версию, а затем последовательно ее уточнять. При сжатии изображений очень часто без визуальной потери качества можно убирать из изображения незначимые мелкомасштабные детали.
Для реализации таких возможностей обычно используют ортогональные вейвлеты. Такие вейвлеты могут быть реализованы, основываясь на представлении некоторого пространства сигналов V в виде системы вложенных подпространств Vm, отличающихся друг от друга только перемасштабированием независимой переменной.
Ортогональный кратномасштабный анализ сигналов базируется на следующих исходных предпосылках:
–пространство L2(R) определяется как иерархически вложенные подпростран-
ства Vm L2(R), m = 0, ±1, ±2, . . . , которые не пересекаются и объединение которых в пределе дает L2(R), при этом условием вложенности является —
Vm Vm+1: · · · V−1 V0 V1 V2 · · · Vm Vm+1 · · ·.
–условие полноты разбиения определяется как: m I Vm = L2(R);
–условием ортогональности подпространств является: ∩m I Vm = {0};
–условие сохранения в подпространстве при сдвигах сигналов: vm(t) Vm
vm(t + 1) Vm;
–для любого сигнала vm(t) Vm его масштабное преобразование по аргументу 2 перемещает этот сигнал в соседнее подпространство: vm(t) Vm
vm(2t) = vm+1(t) Vm+1, vm(t) Vm vm(t/2) = vm−1(t) Vm−1;
9.3. Кратномасштабный вейвлет-анализ
Рис. 9.6. Разбиение пространства L2(R) на систему вложенных подпространств
–для пространства V0 существует функция ϕ(t) V0, целочисленные сдвиги которой по аргументу образуют ортонормированный базис пространства V0: ϕ0,k = ϕ(t − k), k I(k = 0, ±1, ±2, . . .), и условие нормировки этой масштабирующей (скейлинг) функции определяется соотношением:
∞ ϕ(t)dt = 1. |
(9.14) |
−∞ |
|
Из этих условий следует, что если подпространство V0 имеет ортонормированный базис ϕ0,k, то и все остальные подпространства также имеют ортонормированные базисы, которые образуются масштабным преобразованием базиса ϕ0,k:
ϕm,k(t) = 2−m/2ϕ 2−mt − k , m, k I. |
(9.15) |
Если сигнал vm(t) принадлежит пространству Vm, то одновременно он входит и в пространство Vm+1, и вместе с ним в этом пространстве находится и сигнал vm(2t). Увеличение номера пространства позволяет изучать все более и более мелкие детали и особенности сигнала с более высокочастотными компонентами.
На рис. 9.6 в условном виде приводится разбиение пространства L2(R) на систему вложенных подпространств. Все подпространства не пересекаются и вложены друг в друга так, что объем меньшего по номеру подпространства Vm−1 в два раза меньше объема подпространства Vm, при этом четные числовые отсчеты сигнала vm(t) Vm входят в подпространство Vm−1, а нечетные отсчеты остаются в подпространстве с границами [Vm−1, Vm) и отмеченном на рисунке индексами Wm.
Сигналы vm(t) являются ортогональными проекциями исходного сигнала u(t) на подпространства Vm, что реализует возможность анализа сигнала на различ-