Банки фильтров, шумоподавление «Введение в компьютерную графику» лекция Алексей Лукин

План Банки фильтров, основанные на STFT Банки фильтров, основанные на STFT Психоакустическая компрессия звука Психоакустическая компрессия звука Слуховая маскировка Слуховая маскировка Устройство алгоритма mp3 Устройство алгоритма mp3 Подавление стационарных шумов Подавление стационарных шумов Метод спектрального вычитания Метод спектрального вычитания STFT как банк фильтров, полосовые гейты STFT как банк фильтров, полосовые гейты Проблема «музыкального шума» Проблема «музыкального шума» Частотно-временное разрешение Частотно-временное разрешение Вейвлеты Вейвлеты Подавление шума на изображениях Подавление шума на изображениях

Часть 1 Банки фильтров и их применения

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

Банки фильтров, основанные на STFT Частотно-временное разрешение Частотно-временное разрешение Способность различать детали по частоте и по времени, «размытость» спектрограммы Способность различать детали по частоте и по времени, «размытость» спектрограммы Для STFT определяется длиной весового окна (а также, отчасти, размером и шагом DFT по времени) Для STFT определяется длиной весового окна (а также, отчасти, размером и шагом DFT по времени) Соотношение неопределенностей: разрешение по частоте обратно пропорционально разрешению по времени Соотношение неопределенностей: разрешение по частоте обратно пропорционально разрешению по времени 6 ms12 ms24 ms48 ms96 ms размер окна

Банки фильтров Банки фильтров – преобразования, разбивающие сигнал на несколько частотных полос в возможностью обратного синтеза Банки фильтров – преобразования, разбивающие сигнал на несколько частотных полос в возможностью обратного синтеза Пример: дискретное вейвлет-преобразование Пример: дискретное вейвлет-преобразование Возможные свойства БФ: точное восстановление, избыточность Возможные свойства БФ: точное восстановление, избыточность H2H2 H1H1 2 2 Коэффициенты 2 2 G2G2 G1G1 + x[n] ДекомпозицияРеконструкция (синтез)

Банки фильтров Применения: Применения: Раздельная обработка сигнала в разных частотных полосах Раздельная обработка сигнала в разных частотных полосах Компрессия сигналов с независимым квантованием в разных частотных полосах Компрессия сигналов с независимым квантованием в разных частотных полосах Пример банка фильтров, основанного на STFT Пример банка фильтров, основанного на STFT Декомпозиция: STFT с окном Хана (Hann), и с перекрытием между окнами 75% Декомпозиция: STFT с окном Хана (Hann), и с перекрытием между окнами 75% Синтез: обратное DFT от каждого блока, применение весовых окон Хана и сложение окон с наложением (OLA) Синтез: обратное DFT от каждого блока, применение весовых окон Хана и сложение окон с наложением (OLA) Свойства: Свойства: Точное восстановление Точное восстановление Наличие избыточности Наличие избыточности

Слуховая маскировка Абсолютный порог слышимости Абсолютный порог слышимости Как соотнести уровни в звуковом файле с абсолютными уровнями звука? Как соотнести уровни в звуковом файле с абсолютными уровнями звука?

Слуховая маскировка Сильные звуки (masker) маскируют более слабые (maskee) Сильные звуки (masker) маскируют более слабые (maskee) Одновременная маскировка Одновременная маскировка Временная маскировка (прямая и обратная) Временная маскировка (прямая и обратная)

Слуховая маскировка Маскировка тонами, шумами и общий порог маскировки Маскировка тонами, шумами и общий порог маскировки Шаг квантования выбирается пропорциональным порогу маскировки Шаг квантования выбирается пропорциональным порогу маскировки

Алгоритм mp3 Кодирование аудиоданных с потерями Кодирование аудиоданных с потерями mp3-файл x[n] FFT Банк фильтров QHuffman Психоакустический анализ Схема кодера mp3

Пред-эхо Pre-echo (pre-ringing) Pre-echo (pre-ringing) Размытие ошибки квантования по времени на всю длину окна

Пред-эхо Переключение размера окон в банке фильтров Переключение размера окон в банке фильтров

Шумоподавление Аддитивный шум Аддитивный шум Метод спектрального вычитания Шум предполагается стационарным, т.е. не меняющимся во времени (средняя мощность, спектр)

Стационарные шумы Общий принцип подавления Общий принцип подавления 1.Преобразование, компактно локализующее энергию (energy compaction) 2.Модификация коэффициентов преобразования (подавление коэффициентов, соответствующих шуму) 3.Обратное преобразование (восстановление очищенного сигнала)

Спектральное вычитание Спектральное вычитание для аудиосигналов Спектральное вычитание для аудиосигналов 1.STFT 2.Оценка спектра шума по участку без полезного сигнала 3.«Вычитание» спектра шума из спектра сигнала 4.Обратное STFT Spectral Subtraction, Short-Time Spectral Attenuation STFT Noise spectrum estimation Inverse STFT x[t]X[f,t] – W[f] S[f,t]s[t] Схема алгоритма спектрального вычитания

Спектральное вычитание Требования к банку фильтров Требования к банку фильтров Точное (или почти точное) восстановление Точное (или почти точное) восстановление Отсутствие «эффекта блочности» (перекрытие, окна) Отсутствие «эффекта блочности» (перекрытие, окна) Хорошая частотная локализация Хорошая частотная локализация Не требуется: сохранение количества информации Не требуется: сохранение количества информации Выбираем банк фильтров, основанный на STFT

Шумоподавление Многополосная интерпретация Многополосная интерпретация x[n] Банк фильтров (анализ) … Gate …… y[n] Банк фильтров (синтез) Пороги срабатывания гейтов зависят от уровня шума в каждой частотной полосе Гейт (gate) – устройство, подавляющее тихие сигналы (громкие пропускаются без изменения)

Спектральное вычитание Конструкция гейтов Конструкция гейтов Порог срабатывания зависит от шума нужно знать параметры шума обучение Порог срабатывания зависит от шума нужно знать параметры шума обучение Мягкое или жесткое срабатывание Мягкое или жесткое срабатывание Время срабатывания (attack/release time) Время срабатывания (attack/release time) Ограничение степени подавления Ограничение степени подавления Пример подавления: Здесь G – коэффициент усиления, W – оценка амплитуды шума, X – амплитуда сигнала.

Шумоподавление Шум случаен его спектр тоже случаен Шум случаен его спектр тоже случаен Пример спектра белого шума: Пример спектра белого шума: приближенный фрагментобщая спектрограмма

Шумоподавление После спектрального вычитания появляются случайно расположенные всплески энергии – артефакт «музыкальный шум» (musical noise) После спектрального вычитания появляются случайно расположенные всплески энергии – артефакт «музыкальный шум» (musical noise) «музыкальный шум»общая спектрограмма

Шумоподавление Музыкальный шум: методы борьбы Музыкальный шум: методы борьбы Завышение порога (недостаток – теряем больше сигнала) Завышение порога (недостаток – теряем больше сигнала) Ограничение G(f, t) снизу (чтобы музыкальный шум маскировался естественным шумом) Ограничение G(f, t) снизу (чтобы музыкальный шум маскировался естественным шумом) Увеличение времени срабатывания гейтов (при слишком сильном увеличении получается шумовое эхо и смазываются атаки в сигнале) Увеличение времени срабатывания гейтов (при слишком сильном увеличении получается шумовое эхо и смазываются атаки в сигнале) Сглаживание G(f, t) по времени и/или по частоте Сглаживание G(f, t) по времени и/или по частоте зашумленный сигналпростое спектр. вычитаниесглаживание по времени

Спектральное вычитание Эффекты фиксированного частотно-временного разрешения Эффекты фиксированного частотно-временного разрешения Эффект Гиббса (размытие транзиентов) Эффект Гиббса (размытие транзиентов) Недостаточное частотное разрешение Недостаточное частотное разрешение Зашумленный сигналРазмер окна 50 мсАдаптивное разрешение

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

Понятие вейвлета Обычно накладываемые условия на ψ(t): Обычно накладываемые условия на ψ(t): Интегрируемость Интегрируемость Нулевое среднее, нормировка Нулевое среднее, нормировка Нулевые моменты (vanishing moments) Нулевые моменты (vanishing moments)

Понятие вейвлета Примеры вейвлетов Примеры вейвлетов Meyer Mortlet Mexican hat

Непрерывное вейвлет- преобразование (CWT) Скалярные произведения исследуемой функции f(t) с вейвлетами ψ a,b (t) Скалярные произведения исследуемой функции f(t) с вейвлетами ψ a,b (t)

Дискретное вейвлет- преобразование (DWT) Используются лишь целочисленные сдвиги вейвлета и масштабирование в 2 раза Используются лишь целочисленные сдвиги вейвлета и масштабирование в 2 раза Возможность построения ортогонального преобразования Возможность построения ортогонального преобразования Дискретный вейвлет Дискретный вейвлет 1.Последовательность чисел 2.Ортогональна своим сдвигам на четное число точек 3.Существует скейлинг-функция (НЧ-фильтр), ортогональная вейвлету

Преобразование Хаара Простейший случай вейвлет-преобразования Простейший случай вейвлет-преобразования Дан входной сигнал x[n] Образуем от него последовательности полусумм и полуразностей: Легко видеть, что сигнал x[n] можно восстановить: Такое кодирование избыточно: из одной последовательности получаем две

Преобразование Хаара Устранение избыточности Устранение избыточности Проредим полученные последовательности в 2 раза: Легко видеть, что справедлив алгоритм восстановления: (интерполяция нулями) (фильтрация) (суммирование)

Дискретное вейвлет- преобразование Обобщение преобразования Хаара Обобщение преобразования Хаара Свойство точного восстановления (PR): Количество информации не изменяется. Нужно найти хорошие фильтры, обеспечивающие точное восстановление. H2H2 H1H1 2 2 Коэффициенты 2 2 G2G2 G1G1 + x[n] ДекомпозицияРеконструкция

Пирамидальное представление Продолжаем вейвлет-разложение для НЧ- коэффициентов Продолжаем вейвлет-разложение для НЧ- коэффициентов H2H2 H1H1 2 2 Коэффициенты x[n] H2H2 H1H1 2 2 Двумерное вейвлет- преобразование на каждом шаге получаем 4 набора коэффициентов: НЧ («основные») и ВЧ («детализирующие») Частотный диапазон делится на октавы Одномерный случай

Банки фильтров Как банки фильтров разбивают частотно- временную плоскость? Как банки фильтров разбивают частотно- временную плоскость? f t STFT f t Вейвлеты

Часть 2 Подавление шума на изображениях

Виды и примеры шумов Шумы СтационарныеИмпульсныеСмешанные Salt and pepper Помехи в видео Аддитивный белый Зерно пленки Белый шум – пиксели случайны, не коррелированны друг с другом. Гауссов/равномерный/треугольный шум – закон распределения амплитуд пикселей. Аддитивный шум – прибавляется к «чистому» изображению и не зависит от него. Шум + помехи в видео Salt and pepper AWGN

Методы шумоподавления Шумы СтационарныеИмпульсныеСмешанные Медианный фильтр Взвешенная медиана Ранговые фильтры Bilateral filter Non-Local Means Wavelet thresholding DCT, PCA, ICA Анизотропная диффузия Алгоритм BM3D Ранговые фильтры Комбинированные методы Salt and pepper AWGN

Простейшие методы Простейшие методы Простейшие методы Размытие изображения – вместе с шумом размывает детали Размытие изображения – вместе с шумом размывает детали Размытие в гладких областях – остается шум вблизи границ Размытие в гладких областях – остается шум вблизи границ Медианная фильтрация – хорошо подавляет импульсный шум, но удаляет мелкие детали Медианная фильтрация – хорошо подавляет импульсный шум, но удаляет мелкие детали

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

Bilateral filter Bilateral filter: художественное применение Bilateral filter: художественное применение (при слишком сильном действии)

Non-Local Means Адаптивные алгоритмы Адаптивные алгоритмы Non-local means (NL-means) – веса зависят от близости целых блоков, а не отдельных пикселей Non-local means (NL-means) – веса зависят от близости целых блоков, а не отдельных пикселей ν(x i,j ) – блок вокруг пикселя x i,j

Non-Local Means Вычисление весов Вычисление весов Способен сохранять текстуру изображения лучше, чем bilateral filter Способен сохранять текстуру изображения лучше, чем bilateral filter Иллюстрация из Buades et al 2005 Веса высоки для q1 и q2, но не для q3 +

Non-Local Means Достоинства и недостатки: Достоинства и недостатки: Высокое качество результирующего изображения Высокое качество результирующего изображения В исходном варианте – очень высокая вычислительная сложность В исходном варианте – очень высокая вычислительная сложность Ускоряющие расчет оптимизации: Ускоряющие расчет оптимизации: Использование команд MMX/SSE для сравнения блоков Использование команд MMX/SSE для сравнения блоков Разбиение изображения на блоки и усреднение целых блоков, а не отдельных пикселей Разбиение изображения на блоки и усреднение целых блоков, а не отдельных пикселей Промежуточный вариант между усреднением блоков и усреднением пикселей: усреднение маленьких блоков Промежуточный вариант между усреднением блоков и усреднением пикселей: усреднение маленьких блоков + –

Non-Local Means Применение к видео Применение к видео Область поиска блоков можно расширить на соседние кадры (сделать ее пространственно-временной) Область поиска блоков можно расширить на соседние кадры (сделать ее пространственно-временной) Для ускорения просчета можно применять сравнение блоков только по Y-каналу в цветовой модели YCrCb (YUV) Для ускорения просчета можно применять сравнение блоков только по Y-каналу в цветовой модели YCrCb (YUV)

Вейвлетный метод Вейвлетное шумоподавление для изображений Вейвлетное шумоподавление для изображений 1.DWT 2.Оценка уровня и спектра шума 3.Подавление вейвлет-коэффициентов (thresholding, shrinkage) 4.Обратное DWT + Подавление шума различного масштаба – Отсутствие инвариантности к сдвигу Плохая локализация энергии для наклонных границ