2. Дискретное косинусное преобразование

Для уменьшения корреляции соседних пикселей применяются различные обратимые преобразования, представляющие исходные данные в видео не коррелированных коэффициентов. ДКП является одним из эффективных преобразований для решения задачи декорреляции и концентрации энергии в спектральных составляющих. Косинусное преобразование в отличие от преобразования Фурье применяется только для симметричных функций. При использовании частотно-временных преобразований используется понятие периодического расширения функции, заключающееся в следующем: если преобразуется дискретный ряд отсчетов, то его спектр становится периодичным, а в случае преобразования частотного спектра периодически продолжается восстановленный дискретный ряд данных.

ДКП было изучено в лабораторной работе № 1, поэтому описание процедуры преобразования вы можете узнать в соответствующем разделе пособия. Дополнительно можно изучить ДКП в [2,8]

3. Вейвлет-преобразование

Термин "Вейвлет" (wavelet) в переводе с английского означает "маленькая (короткая) волна". Вейвлеты - это обобщенное название семейств математических функций определенной формы, которые локальны во времени и по частоте, и в которых все функции получаются из одной базовой (порождающей) посредством ее сдвигов и растяжений по оси времени. Вейвлет-преобразования рассматривают анализируемые временные функции в терминах колебаний, локализованных по времени и частоте. Как правило, вейвлет-преобразования (WT) подразделяют на дискретное (DWT) и непрерывное (CWT).

DWT используется для преобразований и кодирования сигналов, CWT - для анализа сигналов.[4]

Основная область применения вейвлет преобразований – анализ и обработка сигналов и функций, нестационарных во времени или неоднородных в пространстве, когда результаты анализа должны содержать не только частотную характеристику сигнала (распределение энергии сигнала по частотным составляющим), но и сведения о локальных координатах, на которых проявляют себя те или иные группы частотных составляющих или на которых происходят быстрые изменения частотных составляющих сигнала. По сравнению с разложением сигналов на ряды Фурье, вейвлеты способны с гораздо более высокой точностью представлять локальные особенности сигналов, вплоть до разрывов 1-го рода (скачков). В отличие от преобразований Фурье, вейвлет-преобразование одномерных сигналов обеспечивает двумерную развертку, при этом частота и координата рассматриваются как независимые переменные, что дает возможность анализа сигналов сразу в двух пространствах.

Базисная функция, вейвлет-функция – это некоторое "короткое" колебание, но не только. Понятие частоты спектрального анализа здесь заменено масштабом, и,чтобы перекрыть "короткими волнами" всю временную ось, введен сдвиг функций во времени. Базис вейвлетов – это функции типа ψ((t-b)/a), где b - сдвиг, а – масштаб. Функция ψ(t) должна иметь нулевую площадь и, еще лучше, равными нулю первый, второй и прочие моменты.

П ервое упоминание о подобных функциях (которые вейвлетами не назывались) появилось в работах Хаара (Haar) еще в начале прошлого века. Вейвлет-функция Хаара - это короткое прямоугольное колебание на интервале [0,1], показанное на рис. 3.1. [6]

Рис.3.9 Вейвлет-функция Хаара

Свойства вейвлет-функций,

• Локализация. Вейвлет-функции должны быть непрерывными, интегрируемыми, иметь компактный носитель и быть локализованными как во времени (в пространстве), так и по частоте. Если вейвлет-функция в пространстве сужается, то ее "средняя" частота повышается, спектр вейвлет-функции перемещается в область более высоких частот и расширяется. Этот процесс должен быть линейным – сужение функции вдвое должно повышать его "среднюю" частоту и ширину спектра также вдвое.

Вейвлет-функцию можно считать хорошо локализованной при выполнении условий:

ψ(t) ≤ C/(1+|t|)^1+ε, ψ(f) ≤ C/(1+|f|)^1+ε, С=const, при ε> 0.

• Нулевое среднее значение, т.е. выполнение условия для нулевого момента:

ψ(t) dt = 0,

что обеспечивает выделение локальных особенностей сигналов в пределах вейвлетного носителя на уровне региональных изменений и тренда, нулевое усиление постоянной составляющей сигналов, нулевое значение частотного спектра вейвлет-функции при ψ=0, и локализацию ее спектра в виде полосового фильтра с центром на определенной (доминирующей) частоте ω₀. Для анализамелкомасштабных флюктуаций и особенностей высокого порядка, как правило, требуются и нулевые значения определенного количества последующих моментов:

t^mψ(t) dt = 0. (3.1)

Такие вейвлет-функции называются вейвлетами m-го порядка.

• Ограниченность. Необходимое и достаточное условие:

||ψ(t)||² = |ψ(t)|²dt< (3.2)

Оценка ограниченности и локализации может выполняться с использованием выражений:

|ψ(t)| < 1/(1+|t|ⁿ), или |Ψ(ω)| < 1/(1+|ω_o|ⁿ), (3.3)

где ω_o – средняя частота вейвлет-функции. Число n должно быть как можно больше.

Автомодельность базиса или самоподобие. Форма всех базисных вейвлет-функцийψ_ab(t) должна быть подобна материнскомувейвлетуψ(t), т.е. должна оставаться одной и той же при сдвигах и масштабировании (растяжении/сжатии), иметь одно и то же число осцилляций.

В основе вейвлет-преобразований, в общем случае, лежит использование двух непрерывных, взаимозависимых и интегрируемых по независимой переменной функций:

• Вейвлет-функции (t), как psi-функции времени с нулевым значением интеграла и частотным фурье-образом(ω). Этой функцией, которую обычно и называют материнским вейвлетом, выделяются локальные особенности сигнала. В качестве вейвлетов обычно выбираются функции, хорошо локализованные и во временной, и в частотной области. Пример временного и частотного образа функции приведен на рис. 3.2.

Масштабирующей функции ψ(t), как временной скейлинг-функции phi с единичным значением интеграла, которой выполняется грубое приближение

• (аппроксимация) сигнала.

Рис. 3.10. Вейвлетные функции в двух масштабах.

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

Непрерывное вейвлет-преобразование (НВП, CWT- ContiniousWaveletTransform).

Непрерывным вейвлет-преобразованием (или вейвлетным образом) функции s(t) L²(R) называют функцию двух переменных:

С(a,b) = s(t), (a,b,t) = s(t)(а,b,t) dt, a, b  R, a ≠ 0. (3.4)

где вейвлеты (a,b,t) _ab(t) – масштабированные и сдвинутые копии порождающего вейвлета(t) L²(R), совокупность которых создает базис пространства L²(R). Для обработки изображений используется другой вид преобразования – дискретный.

Дискретное вейвлет-преобразование. При обработке данных на ПК может выполняться дискретизированная версия непрерывного вейвлет-преобразования с заданием дискретных значений параметров (a, b) вейвлетов с произвольным шагом Δa и Δb. В результате получается избыточное количество коэффициентов, намного превосходящее число отсчетов исходного сигнала, которое не требуется для реконструкции сигналов.

Дискретное вейвлет-преобразование (ДВП) обеспечивает достаточно информации, как для анализа сигнала, так и для его синтеза, являясь вместе с тем экономным по числу операций и по требуемой памяти. ДВП оперирует с дискретными значениями параметров а и b, которые задаются, как правило, в виде степенных функций:

a = а_о^-m, b = k·а_о^-m, a_o> 1, m, k  I,

где I – пространство целых чисел {-, }, m – параметр масштаба, k – параметр сдвига. Базис пространства L²(R) в дискретном представлении:

ψ_mk(t) = |а_о|^m/2ψ(а_о^mt-k), m,k I, ψ(t) Î L²(R). (3.5)

Вейвлет-коэффициенты прямого преобразования:

C_mk= s(t)ψ_mk(t)dt.(3.6)

Значение 'a' может быть произвольным, но обычно принимается равным 2, при этом преобразование называется диадным вейвлет-преобразованием. Для диадного преобразования разработан быстрый алгоритм вычислений, аналогичный быстрому преобразованию Фурье, что предопределило его широкое использование при анализе массивов цифровых данных.

Обратное дискретное преобразование для непрерывных сигналов при нормированном ортогональном вейвлетном базисе пространства:

s(t) = C_mkψ_mk(t). (3.7)

Как и для непрерывного вейвлет-преобразования, обратное дискретное преобразование (1.21) не может выполнить восстановление нецентрированных сигналов в силу нулевого первого момента вейвлетных функций и, соответственно, центрирования значения вейвлет-коэффициентов C_mk при прямом вейвлет-преобразовании. Поэтому при обработке числовых массивов данных дискретные вейвлеты используются, как правило, в паре со связанными с ними дискретными скейлинг-функциями [4,5].

Достоинства и недостатки вейвлетных преобразований.

• Вейвлетные преобразования обладают всеми достоинствами преобразований Фурье.

• Вейвлетные базисы могут быть хорошо локализованными как по частоте, так и по времени. При выделении в сигналах хорошо локализованных разномасштабных процессов можно рассматривать только те масштабные уровни разложения, которые представляют интерес.

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

Недостатком вейвлетных преобразований является их относительная

• сложность.

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

Непрерывные вейвлет-функции дают несколько более наглядное представление результатов анализа в виде поверхностей вейвлет-коэффициентов по непрерывным переменным. На рис. 3.3 анализируемый сигнал состоит из двух модулированных гауссианов. Преобразование вейвлетомМорлета четко показывает пространственную и их частотную локализацию.[7]

Рис. 3.11 Пространственная и частотная локализация

Для наглядного отображения преимущества Вейвлет-преобразования относительно преобразования Фурье, рассмотрим тот же нестационарный сигнал:

Рис. 3.12. Нестационарный сигнал

В ейвлет преобразование для такого сигнала будет иметь вид:

Рис. 3.13 Вейвлет-преобразование нестационарного сигнала

Таким образом, вейвлет-преобразование, в отличии от оконного преобразования Фурье, которое имеет постоянный масштаб в любой момент времени для всех частот, имеет лучшее представление времени и худшее представление частоты на низких частотах сигнала и лучшее представление частоты с худшим представлением времени на высоких частотах сигнала. На рисунках хорошо видно, что полученное вейвлет-преобразование является более детализированным по времени в области высоких значений масштаба (низких частот) и менее детализирована в области низких значений масштаба (высоких частот). Из этого следует, что вейвлет преобразования дает возможность уменьшить влияние принципа неопределенности Гейзенберга на полученном частотно-временном представлении сигнала. С его помощью низкие частоты имеют более детальное представление относительно времени, а высокие — относительно частоты.[1,2,3,5,6,7].

Дискретное Вейвлет преобразование изображений

ДВП обрабатывает каждую строку и столбец исходного изображения с помощью частотного фильтра.

Рис. 3.14. Схема работы частотного фильтра.

В связи с тем, что каждый проход с использованием частотного фильтра на выходе увеличивает объем информации в два раза, после обработки размер

12

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

• LL – низкие частоты по строкам и столбцам

• HL – высокие частоты по строкам и низкие по столбцам

• LH – низкие частоты по строкам и высокие по столбцам

• HH – высокие частоты по строкам и столбцам

По стандарту количество этапов может быть от 0 до 32. Для обычного изображения используют от 4-х до 8-ми этапов. На каждом следующем этапе обрабатывается только низкочастотная область (LL), так как в высокочастотных областях обычно не содержится важной информации.

Рис. 3.15. Схема выполнения одного этапа ДВП.

Рис. 3.16. Последовательное применение ДВП к изображению.

Применительно к растровым изображениям вейвлет-преобразование положено в основу кодера JPEG2000. [7]