Без темы
<<  Династия меценатов Рябушинских Длина окружности и площадь круга  >>
Дискретизация Свертка ДПФ
Дискретизация Свертка ДПФ
План
План
Сигналы
Сигналы
Сигналы
Сигналы
Оцифровка сигналов
Оцифровка сигналов
Оцифровка сигналов
Оцифровка сигналов
Теорема Котельникова
Теорема Котельникова
Теорема Котельникова
Теорема Котельникова
Теорема Котельникова
Теорема Котельникова
Эффект Гиббса
Эффект Гиббса
Наложение спектров
Наложение спектров
Наложение спектров
Наложение спектров
Наложение спектров
Наложение спектров
Линейные системы
Линейные системы
Импульсная характеристика
Импульсная характеристика
Импульсная характеристика
Импульсная характеристика
Свертка
Свертка
Линейные системы
Линейные системы
Двумерные фильтры
Двумерные фильтры
Двумерные фильтры
Двумерные фильтры
Двумерные фильтры
Двумерные фильтры
Примеры фильтров
Примеры фильтров
Примеры фильтров
Примеры фильтров
Примеры фильтров
Примеры фильтров
Примеры фильтров
Примеры фильтров
Примеры фильтров
Примеры фильтров
Примеры фильтров
Примеры фильтров
Двумерные фильтры
Двумерные фильтры
Двумерные фильтры
Двумерные фильтры
Двумерные фильтры
Двумерные фильтры
Двумерные фильтры
Двумерные фильтры
Двумерные фильтры
Двумерные фильтры
Двумерные фильтры
Двумерные фильтры
Двумерные фильтры
Двумерные фильтры
Звук и слух
Звук и слух
Основы слухового восприятия
Основы слухового восприятия
Основы слухового восприятия
Основы слухового восприятия
Преобразование Фурье
Преобразование Фурье
Преобразование Фурье
Преобразование Фурье
Преобразование Фурье
Преобразование Фурье
Преобразование Фурье
Преобразование Фурье
Преобразование Фурье
Преобразование Фурье
Преобразование Фурье
Преобразование Фурье
Спектральный анализ
Спектральный анализ
Спектральный анализ
Спектральный анализ
Спектральный анализ
Спектральный анализ
Спектральный анализ
Спектральный анализ
Спектральный анализ
Спектральный анализ
Спектральный анализ
Спектральный анализ
Спектральный анализ
Спектральный анализ
Преобразование Фурье
Преобразование Фурье
Преобразование Фурье
Преобразование Фурье
Спектральный анализ
Спектральный анализ
Спектральный анализ
Спектральный анализ
Спектральный анализ
Спектральный анализ

Презентация: «Дискретизация Свертка ДПФ». Автор: Alexey Lukin. Файл: «Дискретизация Свертка ДПФ.ppt». Размер zip-архива: 2305 КБ.

Дискретизация Свертка ДПФ

содержание презентации «Дискретизация Свертка ДПФ.ppt»
СлайдТекст
1 Дискретизация Свертка ДПФ

Дискретизация Свертка ДПФ

Лектор: Лукин Алексей Сергеевич

Сайт курса: http://imaging.cs.msu.ru

2 План

План

Основные определения Дискретизация, теорема Котельникова Линейные системы, свертка Простейшие двумерные фильтры для изображений Дискретное преобразование Фурье Спектральный анализ

3 Сигналы

Сигналы

Сигнал – скалярная функция от одного или нескольких аргументов

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

S(t) – звук

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

4 Сигналы

Сигналы

Аналоговые (непрерывные) звук в воздухе или в проводе, идущем от микрофона изображение (до ввода в компьютер) движение стрелки датчика Цифровые (дискретные) звук в компьютере (одномерный массив чисел) изображение в компьютере (двумерный массив чисел) запись показаний датчика в компьютере (одномерный массив)

Одномерный цифровой сигнал

5 Оцифровка сигналов

Оцифровка сигналов

Дискретизация по времени (аргумент функции) Квантование по амплитуде (значение функции) АЦП (ADC) – аналогово-цифровой преобразователь Параметры: частота дискретизации, разрядность квантования (пример: 44.1 кГц, 16 бит – формат Audio CD)

6 Оцифровка сигналов

Оцифровка сигналов

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

X(t) – исходный сигнал x(?) – спектр, т.Е. Коэффициенты при гармониках с частотой ?

(Разложение на синусоиды с различными частотами)

7 Теорема Котельникова

Теорема Котельникова

Пусть спектр сигнала x(t) не содержит частот выше F, т.е. X(?)=0 за пределами отрезка [-F, F] дискретизация сигнала x(t) производится с частотой Fs , т.е. в моменты времени nT, здесь T= Fs-1 Fs > 2F Тогда исходный аналоговый сигнал x(t) можно точно восстановить из его цифровых отсчетов x(nT), пользуясь интерполяционной формулой

8 Теорема Котельникова

Теорема Котельникова

Как выглядят интерполирующие sinc-функции?

Бесконечно затухающие колебания

9 Теорема Котельникова

Теорема Котельникова

Реконструкция аналоговых сигналов. Sinc-интерполяция.

10 Эффект Гиббса

Эффект Гиббса

Применимость sinc-интерполяции для изображений Эффект Гиббса: пульсации сигнала при ограничении его спектра

Цифровые отсчеты

Sinc-интерполяция

Другая интерполяция

11 Наложение спектров

Наложение спектров

Что будет, если условия теоремы Котельникова не выполнены? Пусть звук не содержит частот выше 20 кГц. Тогда, по теореме Котельникова, можно выбрать частоту дискретизации 40 кГц. Пусть в звуке появилась помеха с частотой 28 кГц. Условия теоремы Котельникова перестали выполняться.

(aliasing)

12 Наложение спектров

Наложение спектров

Проведем дискретизацию с частотой 40 кГц, а затем – восстановим аналоговый сигнал sinc-интерполяцией. Помеха отразилась от половины частоты дискретизации в нижнюю часть спектра и наложилась на звук. Помеха переместилась в слышимый диапазон. Это называется наложением спектров (алиасинг).

13 Наложение спектров

Наложение спектров

Как избежать наложения спектров? Применить перед оцифровкой анти-алиасинговый фильтр Он подавит все помехи выше половины частоты дискретизации (выше 20 кГц) и пропустит весь сигнал ниже 20 кГц. После этого условия теоремы Котельникова будут выполняться и алиасинга не возникнет. Следовательно, по цифровому сигналу можно будет восстановить исходный аналоговый сигнал (но без помехи).

14 Линейные системы

Линейные системы

Система – преобразователь сигнала Линейность: Инвариантность к сдвигу:

x(t)

y(t)

H

15 Импульсная характеристика

Импульсная характеристика

Единичный импульс ?[n] Разложение произвольного сигнала на взвешенную сумму единичных импульсов

16 Импульсная характеристика

Импульсная характеристика

Отклик системы на единичный импульс h[n] – импульсная характеристика системы (импульсный отклик системы) Физическая реализуемость системы (causality)

17 Свертка

Свертка

Вычисление отклика линейной системы на произвольный входной сигнал Свертка

H[n] – ядро свертки

18 Линейные системы

Линейные системы

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

19 Двумерные фильтры

Двумерные фильтры

Как работают фильтры

Коэффициенты фильтра, ядро свертки 3x3, «функция размытия точки»

-1 ? k ? 1, -1 ? p ? 1

20 Двумерные фильтры

Двумерные фильтры

Свертка

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

// Обнулить изображение Dest[i][j] ... // Выполнить свертку for (i=0; i<Height; i++) // Для каждого пикс. Dest[i][j]... for (j=0; j<Width; j++) for (k=-1; k<=1; k++) // ...превратить его в ядро свертки for (p=-1; p<=1; p++) Dest[i+k][j+p] += Src[i][j] * Ker[k][p]; // и сложить

21 Двумерные фильтры

Двумерные фильтры

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

22 Примеры фильтров

Примеры фильтров

Размытие (blur)

23 Примеры фильтров

Примеры фильтров

Повышение четкости (sharpen)

24 Примеры фильтров

Примеры фильтров

Нахождение границ (edges)

25 Примеры фильтров

Примеры фильтров

Тиснение (embossing)

26 Примеры фильтров

Примеры фильтров

Простейшее размытие Константное размытие “box-фильтр” (любой размер фильтра) Гауссово размытие (любой размер фильтра)

27 Примеры фильтров

Примеры фильтров

Повышение резкости Нахождение границ Тиснение

+ Модуль, нормировка, применение порога…

+ Сдвиг яркости, нормировка…

28 Двумерные фильтры

Двумерные фильтры

Свойства двумерной свертки (повторение) Линейность Инвариантность к сдвигу

Пусть X и Y – изображения, H – ядро свертки

29 Двумерные фильтры

Двумерные фильтры

Сепарабельные (разделимые) фильтры

Если фильтр сепарабельный, то фильтрацию можно производить быстрее: Отфильтровать все столбцы одномерным фильтром F(k) Отфильтровать все строки одномерным фильтром G(p)

Гауссиан – сепарабельный фильтр, т.к.

Еще один сепарабельный фильтр – box-фильтр

30 Двумерные фильтры

Двумерные фильтры

Unsharp Mask Идея: вычесть из изображения его размытую копию, скомпенсировав уменьшение яркости Параметры: радиус, сила эффекта, порог срабатывания Переменная сила эффекта ? помогает избежать усиления шума. Обычно ? уменьшают при малых значениях разности X – GX (меньше порога срабатывания)

? регулирует силу эффекта, GX – размытая копия изображения (обычно фильтр Гаусса)

31 Двумерные фильтры

Двумерные фильтры

Медианный фильтр Каждый пиксель принимает значение, являющееся медианой значений пикселей в окрестности Медиана – средний элемент в отсортированном массиве Позволяет подавить шум (особенно, единичные «выпадающие» пиксели), не размывая границ Медианный фильтр нелинейный (как доказать?) Что делать для цветных изображений? Векторная медиана – такой элемент массива, для которого сумма L1-расстояний до остальных элементов минимальна (для одномерного случая – совпадает с предыдущим определением)

32 Двумерные фильтры

Двумерные фильтры

Медианный фильтр 5x5

33 Двумерные фильтры

Двумерные фильтры

Сравним с обычным гауссовым размытием

34 Двумерные фильтры

Двумерные фильтры

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

35 Звук и слух

Звук и слух

Диапазон звуковых сигналов и пороги восприятия

Sine sweep

2x102

20

2

2?10-1

2?10-2

2?10-3

2?10-4

2?10-5

2?10-6

100

1000

10000

2

5

2

5

2

5

2

36 Основы слухового восприятия

Основы слухового восприятия

Звуковые волны поступают на улитку, возбуждая ее колебания Жесткость улитки меняется с расстоянием, поэтому каждая часть резонирует в своем частотном диапазоне

image from Wikipedia

37 Основы слухового восприятия

Основы слухового восприятия

К разным частям улитки подходят различные группы нервов, передающие в мозг информацию об амплитуде и фазе колебаний Таким образом, улитка раскладывает звук на частотные составляющие

image from Wikipedia

38 Преобразование Фурье

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

Зачем раскладывать сигналы на синусоиды? Анализ линейных систем Особенности слухового восприятия Хорошо разработана теория и практика Дискретное преобразование Фурье (ДПФ) Для вещественного сигнала Прямое и обратное преобразования Фурье

39 Преобразование Фурье

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

Базисные функции дискретного преобразования Фурье для сигнала длины N = 8. Имеем N/2 + 1 = 5 различных базисных частот. Имеем N+2 базисные функции, 2 из которых тождественно равны нулю. Количество информации не изменяется: N чисел

40 Преобразование Фурье

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

Базисные функции образуют N-мерный ортогональный базис в пространстве N-мерных векторов исходных сигналов. Следовательно, разложение обратимо, т.е. по коэффициентам разложения (Ak, Bk) можно точно восстановить исходный дискретный сигнал. Обратное преобразование Фурье – вычисление суммы конечного ряда Фурье (сложить N штук N-точечных синусоид со своими коэффициентами).

41 Преобразование Фурье

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

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

42 Преобразование Фурье

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

Быстрое преобразование Фурье (БПФ, FFT) – ускоренный алгоритм вычисления ДПФ Основан на периодичности базисных функций (много одинаковых множителей) Математически точен (только ошибки округления) Число умножений порядка N·log2N, намного меньше, чем N2 Ограничение: большинство реализаций FFT принимают только массивы длиной N = 2m Существует и обратное БПФ (IFFT) – такой же быстрый алгоритм вычисления обратного ДПФ.

43 Преобразование Фурье

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

Входные данные FFT N = 2m, размер FFT Входной вектор длины N, иногда в комплексном представлении Выходные данные FFT Коэффициенты Ak и Bk, иногда записанные в комплексном представлении

44 Спектральный анализ

Спектральный анализ

Как вычислить и отобразить спектр сигнала? Взять нужный отрезок сигнала длины 2m; если нужный отрезок короче – дополнить его нулями Если нужно – умножить сигнал на весовое окно, плавно спадающее к краям (для уменьшения размытия спектра, подробности – на следующих лекциях) Вычислить FFT Перевести комплексные коэффициенты в полярную форму: получить амплитуды и фазы Отобразить график зависимости амплитуды от частоты

Примеры весовых окон

45 Спектральный анализ

Спектральный анализ

Отображение спектра звука Спектр – график зависимости амплитуды от частоты Низкие частоты – слева, высокие – справа Часто применяется логарифмический масштаб частот и амплитуд: “log-log-спектр” Временное и частотное разрешение спектра

Децибелы:

A1 – амплитуда измеряемого сигнала, A0 – амплитуда сигнала, принятого за начало отсчета (0 дБ)

Разница на 6 дБ – разница по амплитуде в 2 раза, разница на 12 дБ – разница по амплитуде в 4 раза.

Часто за 0 дБ принимается либо самый тихий слышимый звук, либо самый громкий звук, который может воспроизвести аудио-устройство.

46 Спектральный анализ

Спектральный анализ

Примеры звуков и их спектров

Нота на гитаре

Фрагмент песни (стерео запись)

Сигнал близок к периодическому ? его спектр линейчатый

47 Спектральный анализ

Спектральный анализ

Отображение спектра звука: спектрограмма (сонограмма) Спектрограмма – график зависимости амплитуды от частоты и от времени, показывает изменение спектра во времени Short Time Fourier Transform (STFT)

48 Спектральный анализ

Спектральный анализ

Отображение спектра звука: спектрограмма (сонограмма) Спектрограмма – график зависимости амплитуды от частоты и от времени, показывает изменение спектра во времени Short Time Fourier Transform (STFT)

49 Спектральный анализ

Спектральный анализ

Отображение спектра звука: спектрограмма (сонограмма) Спектрограмма – график зависимости амплитуды от частоты и от времени, показывает изменение спектра во времени Низкие частоты – снизу, высокие – сверху Время идет справа налево Амплитуда – яркость или цвет Частотное и временное разрешение Short Time Fourier Transform (STFT)

Показывает изменение спектра во времени

50 Спектральный анализ

Спектральный анализ

Примеры звуков и их спектрограмм

Нота на гитаре

Логарифмический масштаб частот

Линейный масштаб частот

51 Преобразование Фурье

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

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

52 Преобразование Фурье

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

Быстрое вычисление двумерного ДПФ Вычислить одномерные комплексные ДПФ от каждой строки изображения. Результаты записать в виде комплексных массивов «обратно» в промежуточное «комплексное» изображение. Вычислить одномерные комплексные ДПФ от каждого столбца промежуточного комплексного изображения. Комплексные результаты записать «обратно». Это и есть коэффициенты двумерного ДПФ. Одномерные ДПФ можно считать с помощью FFT.

53 Спектральный анализ

Спектральный анализ

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

54 Спектральный анализ

Спектральный анализ

Примеры изображений и их спектров

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

Две синусоиды – две точки

55 Спектральный анализ

Спектральный анализ

Примеры изображений и их спектров

По спектру прослеживаются преобладающие направления в исходной картинке

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

«Дискретизация Свертка ДПФ»
http://900igr.net/prezentacija/obschestvoznanie/diskretizatsija-svertka-dpf-89916.html
cсылка на страницу

Без темы

1473 презентации
Урок

Обществознание

85 тем
Слайды
900igr.net > Презентации по обществознанию > Без темы > Дискретизация Свертка ДПФ