Презентация Методы и средства обработки изображений. (Лекция 3) онлайн

Содержание слайда: Методы и средства обработки изображений Яночкин Алексей Леонидович Ассистент каф. ЭВМ

Содержание слайда: Сегментация изображений Лекция 3

Содержание слайда: Из чего состоит изображение?

Содержание слайда: Из «кусков» - отдельных объектов

Содержание слайда: Сегментация Сегментация - это способ разделения сцены на «куски», с которыми проще работать Тесселяция - разбиение изображения на неперекрывающиеся области, покрывающие все изображение и однородные по некоторым признакам Можно и по другому сегментировать изображение Пересекающиеся области Иерархическое представление

Содержание слайда: Результат сегментации Как мы будем записывать результат сегментации? Сделаем карту разметки – изображение, в каждом пикселе которого номер сегмента, которому принадлежит этот пиксель Визуализировать удобно каждый сегмент своим цветом

Содержание слайда: Простейшая сегментация Чем отличаются объекты на этом изображении?

Содержание слайда: Пороговая бинаризация

Содержание слайда: Пороговая бинаризация Пороговая фильтрация (thresholding) Пиксели, которых выше/ниже некоторого порога, заданного «извне», помечаются 1 Ниже порога помечаются 0 Бинарное изображение – пиксели которого могут принимать только значения 0 и 1 Бинаризация - построение бинарного изображения по полутоновому / цветному

Содержание слайда: Пороговая бинаризация

Содержание слайда: Пороговая фильтрация Более интересный способ – определение порога автоматически, по характеристикам изображения Анализ гистограммы

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

Содержание слайда: Анализ гистограммы Сгладить гистограмму; Найти ячейку гистограммы hmax с максимальным значением; На стороне гистограммы не относящееся к объекту (на примере – справа от пика фона) найти яркость hp, количество пикселей с яркостью >= hp равняется p% (например 5%) от пикселей яркости которых >= hmax; Рассчитать порог T = hmax - (hp - hmax);

Содержание слайда: Адаптивная бинаризация

Содержание слайда: Адаптивная бинаризация Необходима в случае неравномерной яркости фона/объекта. Для каждого пикселя изображения I(x, y): В окрестности пикселя радиуса r высчитывается индивидуальный для данного пикселя порог T; Если I(x, y) > T + C , результат 1, иначе 0; Варианты выбора T:  T = mean  T = median T = (min + max) / 2

Содержание слайда: Адаптивная бинаризация

Содержание слайда: Шум в бинарных изображениях Часто возникает из-за невозможности полностью подавить шум в изображениях, недостаточной контрастности объектов и т.д.

Содержание слайда: Шум в бинарных изображениях По одному пикселю невозможно определить – шум или объект? Нужно рассматривать окрестность пикселя!

Содержание слайда: Подавление и устранение шума Широко известный способ - устранение шума с помощью операций математической морфологии: Сужение (erosion) Расширение (dilation) Закрытие (closing) Раскрытие (opening)

Содержание слайда: Математическая морфология Множество A обычно является объектом обработки Множество B (называемое структурным элементом) – инструмент обработки

Содержание слайда: Операция «расширение» Операция «расширение» - аналог логического «или»

Содержание слайда: Операция «расширение» Расширение (dilation) A (+) B = {t  R2: t = a + b, a  A, b  B}

Содержание слайда: Операция «cужение» Сужение (erosion) A (-) B = (AC (+) B)С, где AC -дополнение A

Содержание слайда: Операция «cужение» Что будет?

Содержание слайда: Операция «cужение»

Содержание слайда: Операция «cужение»

Содержание слайда: Метрики Евклидово расстояние: ДE(p,q)=[(x-s)2+(y-t)2]1/2  Модульное расстояние (метрика городских кварталов):  Д4(p,q)= │x-s│+│y-t│  Шахматное расстояние: Д8(p,q) = max{│x-s│,│y-t│}

Содержание слайда: Метрики

Содержание слайда: Важное замечание Результат морфологических операций во многом определяется применяемым структурным элементом. Выбирая различный структурный элемент можно решать разные задачи обработки изображений: • Шумоподавление • Выделение границ объекта • Выделение скелета объекта • Выделение сломанных зубьев на изображении шестерни

Содержание слайда: Операция выделения контура объекта При работе с бинарными изображениями контуры объекта можно получить с помощью операций математической морфологии Внутреннее оконтуривание CI =A–(A(-)B) Внешнее оконтуривание CO =(A(+)B)–A

Содержание слайда: Операция выделения контура объекта

Содержание слайда: Операции раскрытия и закрытия Морфологическое раскрытие (opening) open(A,B)=(A(-)B)(+)B Морфологическое закрытие (closing) close(A, B) = (A (+) B) (-) B

Содержание слайда: Применение открытия

Содержание слайда: Сужение vs Открытие

Содержание слайда: Дефекты бинаризации

Содержание слайда: Применение закрытия Применим операцию закрытия к изображению с дефектами объектов:

Содержание слайда: Не лучший пример для морфологии

Содержание слайда: Применение операции «открытия» Часто помогает медианная фильтрация!

Содержание слайда: Медианный фильтр Фильтр с окрестностью 3x3 Теперь можем с помощью морфологии убрать оставшиеся точки, тонкие линии и т.д.

Содержание слайда: Что дальше?

Содержание слайда: Выделение связных областей Определение связной области: Множество пикселей, у каждого пикселя которого есть хотя бы один сосед, принадлежащий данному множеству. Соседи пикселей:

Содержание слайда: Разметка связных областей

Содержание слайда: Рекурсивный алгоритм

Содержание слайда: Рекурсивный алгоритм

Содержание слайда: Последовательное сканирование

Содержание слайда: Последовательное сканирование

Содержание слайда: Выделенные связанные компоненты

Содержание слайда: Анализ выделенных областей

Содержание слайда: Геометрические признаки Для каждой области можно подсчитать некий набор простейших числовых характеристик: Площадь Центр масс Периметр Компактность Ориентацию главной оси инерции Удлиненность (эксцентриситет)

Содержание слайда: Площадь и центр масс

Содержание слайда: Периметр и компактность

Содержание слайда: Подсчет периметра области Пиксель лежит на границе области, если он сам принадлежит области и хотя бы один из его соседей области не принадлежит. (внутренняя граница) Пиксель лежит на границе области, если он сам не принадлежит области и хотя бы один из его соседей области принадлежит. (внешняя граница) Периметр зависит также от того 4-х или 8-ми связность используется для определения соседей.

Содержание слайда: Пример периметров области

Содержание слайда: Инвариантные характеристики

Содержание слайда: Ориентация главной оси инерции

Содержание слайда: Пример

Содержание слайда: Фотометрические признаки Для каждой области можно подсчитать некий набор простейших числовых характеристик: Средняя яркость Средний цвет (если изображение цветное) Гистограмма распределения яркостей (или три гистограммы распределения R, G, B) Дисперсию (разброс) яркостей или цвета Разумеется, все это считается по исходному, а не бинарному изображению!

Содержание слайда: Как анализировать признаки

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

Содержание слайда: Ручной подбор Из общих соображений: Ложки более вытянутые, чем сахарные кусочки Ложки больше чем сахарные кусочки Сахарные кусочки квадратные Области появляющиеся из-за шума обычно небольшие и неквадратные Пытаемся сконструировать решающее правило, проверяем экспериментально Может быть весьма утомительно

Содержание слайда: Графический анализ Собрать тренировочную базу изображений Где только ложки Где только сахар Где только шум Как получить такие? Да просто закрасить все остальное. Брать признаки и строить графики

Содержание слайда: Графический анализ Диаграмма распределения эксцентриситета (проблема – не получается отличить шум от ложек)

Содержание слайда: Графический анализ График распределения эксцентриситета и площади (гораздо лучше – можем подобрать значения порогов)

Содержание слайда: Метод k-средних Метод k-средних – метод кластеризации данных. Целью задачи кластеризации является разбиение множества объектов на кластеры (классы) на основе некоторой меры сходства объектов.

Содержание слайда: Метод k-средних Дано: Набор векторов , i = 1,…, p; k – число кластеров, на которые нужно разбить набор .   Найти: k средних векторов mj, j = 1,…, k (центров кластеров); отнести каждый из векторов к одному из k кластеров;

Содержание слайда: Метод k-средних Алгоритм: 1. Случайным образом выбрать k средних mj j = 1,…, k; 2. Для каждого xi i = 1,…,p подсчитать расстояние до каждого из mj j=1,…, k, отнести (приписать) xi к кластеру j’, расстояние до центра которого mj’ минимально; 3. Пересчитать средние mj j=1,…, k по всем кластерам; 4. Повторять шаги 2, 3, пока кластеры не перестанут изменяться

Содержание слайда: Метод k-средних

Содержание слайда: Метод k-средних

Содержание слайда: Метод k-средних

Содержание слайда: Недостатки Не гарантируется достижение глобального минимума суммарного квадратичного отклонения V, а только одного из локальных минимумов. Результат зависит от выбора исходных центров кластеров, их оптимальный выбор неизвестен. Число кластеров надо знать заранее.

Содержание слайда: Признаки изображения Какие признаки мы можем использовать для сравнения пикселей и регионов? Яркость Цвет ?

Содержание слайда: Пример

Содержание слайда: Текстура Это типичные примеры текстурных шаблонов для исследований психофизиологоического восприятия изображений Человек явно использует не только яркость и цвет, но и ориентацию краёв (градиентов изображения), их распределение, для анализа изображений Текстура — преимущественная ориентация элементов, составляющих материал (одно из определении)

Содержание слайда: «Простые клетки» V1

Содержание слайда: Психологическое свойство текстуры

Содержание слайда: Форма из текстуры

Содержание слайда: Схема простого алгоритма

Содержание слайда:

Содержание слайда:

Содержание слайда:

Содержание слайда: Jean Baptiste Joseph Fourier Дикая идея (1807): Любая периодическая функция может быть представлена как взвешенная сумма синусов и косинусов различной частоты Воспринята была не сразу: Ни Лагранж, ни Лаплас, Пуассон не верили в это Впервые переведена работа на английский в 1878 году Преобразование Фурье

Содержание слайда: Преобразование Фурье

Содержание слайда: Преобразование Фурье

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

Содержание слайда: Пример g(t) = sin(2pf t) + (1/3)sin(2p(3f) t)

Содержание слайда: Пример g(t) = sin(2pf t) + (1/3)sin(2p(3f) t)

Содержание слайда: Ограниченный сигнал Как быть, если сигнал задан на отрезке? Продлить сигнал за границы отрезка, затем разложить В зависимости от типа разложения, продлять нужно по разному Продление должно быть периодическим Можем использовать только синусы или только косинусы, в зависимости от этого продлевать нужно по-разному Если косинусное преобразование, то продление должно быть чётной функцией

Содержание слайда: Прямоугольный сигнал

Содержание слайда: Прямоугольный сигнал

Содержание слайда: Прямоугольный сигнал

Содержание слайда: Прямоугольный сигнал

Содержание слайда: Прямоугольный сигнал

Содержание слайда: Прямоугольный сигнал

Содержание слайда: Прямоугольный сигнал

Содержание слайда: Спектр частот

Содержание слайда: Свойства Разрывы функции приводят к тому, что требуется больше слагаемых для достижения точности sin() – нечётная функция, поэтому продление должно быть нечётной функцией Поскольку у реального сигнала значение на конце и в начале сигнала обычно разное, то продление почти всегда с разрывом Для реальных сигналов разложение через косинусы эффективнее, чем через синусы Также в базисе косинусов есть константа

Содержание слайда: 2D преобразование

Содержание слайда: Пример

Содержание слайда: Пример

Содержание слайда: Сжатие с потерями (JPEG)

Содержание слайда: Первый коэффициент B(0,0) называется DC, средняя интенсивность Верхние левые коэффициенты соответствуют низким частотам, верхние – высоким частотам

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

Содержание слайда: Пример

Содержание слайда: Пример Делим G на Q и округляем: round ( G(i,j) / Q(i,j) ) При этом обнуляются высокие частоты Значения Q позволяют менять степень сжатия Значения обходятся зигзагом и кодируются без потерь (RLE или арифметическое)

Содержание слайда: Размер блока JPEG Маленький блок Быстрее Больше корреляции между соседними пикселям Большой блок Лучше сжатие в плавных регионах По стандарту 8x8

Содержание слайда: Пример сжатия

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

Содержание слайда: Спектральный анализ

Содержание слайда: Спектральный анализ

Содержание слайда: Искусственная сцена

Содержание слайда: Края в изображении

Содержание слайда: Теорема о свёртке Преобразование Фурье от свёртки двух функций можно представить как произведение преобразований Фурье каждой из функций F[g∗h]= F[g]F[h] Обратное преобразование Фурье от произведения есть свёртка двух обратных преобразований Фурье F−1[gh]= F−1[g]∗F−1[h] Свёртка в пространстве эквивалентна произведению в частотном диапазоне Можно существенно ускорить многие операции свёртки!

Содержание слайда: Резюме Сегментация изображения позволяет работать не со всем изображением в целом, а с отдельными областями В отдельных случаях мы можем решить задачу распознавания, анализируя геометрические и фотометрические признаки сегментов Сегменты могут быть однородны по яркости, цвету, текстуре и по комбинации этих признаков Переход от представления в виде регулярной сетки к частотному представлению позволяет учесть структуру изображения Сжатие изображений по алгоритму JPEG Использование теоремы о свёртке позволяет эффективнее фильтровать изображение Фильтр Гаусса – фильтр низких частот