Цифровая обработка сигналов и изображений

часа лекций
4 часа лабораторных работ
Экзамен

контрольную работу (КР защищается индивидуально каждым студентом).
Выполнить и защитить ДВЕ

лабораторные работы (выполнение и защита ЛР возможна в бригаде в составе двух человек).
ЗАЧЕТ (два теоретических вопроса из перечня).

До зачета допускаются студенты, защитившие КР и две ЛР.

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

Фурье. Преобразование Фурье.
Теорема корреляции.
Теорема свертки.
Теорема отсчетов.
Определение дискретного преобразования Фурье (ДПФ) и обратного дискретного преобразования Фурье (ОБПФ).
Свойства ДПФ (теорема линейности, теорема комплексной сопряженности, теорема сдвига, теорема сверки, теорема корреляции).
Вычислительная сложность ДПФ.
Двумерное ДПФ.
Алгоритм быстрого преобразования Фурье (БПФ) с децимацией во временной области.
Вычислительные преимущества БПФ.
Обратное быстрое преобразование Фурье.
БПФ с частотной децимацией.
Схемы вычисления свертки и корреляции на основе БПФ.
Класс несинусоидальных ортогональных функций (функции Радемахера, функции Хаара, функции Уолша).
Код Грея.
Преобразование Уолша.
Преобразование Уолша-Адамара (Адамара).
Алгоритм быстрого преобразования Уолша-Адамара.
Дискретное косинусное преобразование (ДКП). Применение ДКП: сжатие изображений (алгоритм JPEG).
Вейвлет- преобразование. Принцип неопределенности Гейзенберга.
Кратномасштабный анализ.
Дискретное вейвлет-преобразвование. Алгоритм JPEG 2000.

формы аналитического выражения сигнала – представление записи этого сигнала с

помощью колебаний или спектра (временное или частотное представление).

Примеры сигналов

Цифровая обработка сигналов (Digital Signal Processing)

s(t) – звук

f(x,y) – изображение

времени является случайной величиной.

Детерминированный сигнал – величину такого сигнала можно

предсказать в любой момент времени (в любой точке).

(до ввода в компьютер)
запись показаний датчика
Цифровые (дискретные)
Примеры:
звук в компьютере (одномерный

массив чисел)
изображение в компьютере (двумерный массив чисел)
запись показаний датчика в компьютере (одномерный массив)

Классификация сигналов

времени, которое можно рассматривать как причинное.
Периодическое
колебание,

которое задается на интервале и любое значение повторяется через интервалы времени, равные Т (период):
Финитное
колебание, локализованное во времени, т.е. колебание равное нулю вне некоторого ограниченного интервала времени
Непрерывное
колебание, которое рассматривается в каждой точке оси времени, т.е. такое колебание задано на несчетном временном интервале
Дискретное
колебание рассматривается только в фиксированный момент времени, т.е. заданное на счетном множестве временных точек

очевидно, что чем шире интервал дискретизации выборки и грубее квантование,

тем меньше требуется данных для представления сигнала. Однако, если сигнал представлен слишком малым объемом данных, то возникает опасность потерять информацию, которую содержит сигнал. Проблема выбора интервала дискретизации…

половины периода.

Теорема Котельникова-Найквиста-Шеннона: если сигнал таков, что его

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

ФУРЬЕ

Разложение в ряд Фурье

иллюстрация формулы Эйлера

на интервале ,

если


При множество {Un(t)} называется ортонормированным.

Жозеф Фурье показал, что любую произвольную функцию

можно представить в виде бесконечной суммы синусных и косинусных членов:


где (рад/с) – основная угловая частота, которая связана с периодом T функции соотношением . Частоты называют гармониками, так как они кратны основной частоте . В данном случае речь идет о системе ортогональных функций вида

Разложение функции в ряд Фурье

Фурье
(отображение исходной функции времени в спектральную область)


Обратное преобразование Фурье
(восстановление

функции по её спектру)

преобразования Фурье

умножений
N-1 комплексных сложений
Все N коэффициентов ДПФ требуют:
N2 комплексных умножений
N(N-1) комплексных

сложений
Более быстрые методы основаны на свойствах симметрии и периодичности
Симметрия
Периодичность

для случаев, когда
Разделим x[n] на две последовательности длиной N/2
Четные

элементы в первой последовательности
Нечетные элементы во второй последовательности



Пусть n=2r для четных и n=2r+1 для нечетных элементов






G[k] и H[k] - N/2-точечные ДПФ для каждой последовательности

ДПФ
2(N/2)2 комплексных умножений
2(N/2)2 комплексных сложений
Комбинация выходов двух ДПФ дает
N комплексных

умножений
N комплексных сложений
Итоговая вычислительная сложность
N2/2+N комплексных умножений
N2/2+N комплексных сложений
Более эффективно, чем прямое ДПФ
Повторяем тот же процесс
Делим N/2-точечные ДПФ на
два N/4-точечные ДПФ
Комбинируем выходы

останутся 2-точечные ДПФ

сложность:
Nlog2N комплексных сложений и умножений

одним умножением





Финальная вычислительная сложность БПФ с прореживанием по времени
(N/2)log2N комплексных

сложений и умножений

(«верхняя» и «нижняя»)


Получим



Аналогично для второй половины

в алгоритмах с прореживанием по времени и по частоте

от частоты и от направления синусоиды.
Амплитуды отображаются в виде яркостей.
Нулевая

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

– это точка
(не забываем про симметричное отражение спектра)
Две синусоиды –

две точки

в исходной картинке
Много высоких частот в спектре – много мелких

деталей в исходном изображении

частоты
Низкие частоты – слева, высокие – справа
Часто применяется логарифмический масштаб

частот и амплитуд: “log-log-спектрограмма”
Временное и частотное разрешение спектрограммы

large) :

90%, 95%, 98%, 99%, 99.5%,

99.9%

Image

Fourier Spectrum

СЕЙЧАС ПРОСЛУШАЛИ…
Контрольная работа