Размещено на http://www.allbest.ru/

Федеральное агентство связи

Федеральное государственное бюджетное образовательное учреждение высшего образования «Поволжский государственный университет телекоммуникаций и информатики»

Факультет Информационных систем и технологий

Направление (специальность) Информационные системы и технологии

Кафедра Информационных систем и технологий

Выпускная квалификационная работа (бакалаврская работа)

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

Утверждаю зав.кафедрой, д.т.н., доцент Н.И. Лиманова

Руководитель доцент, к.т.н., с.н.с. О.Л. Куляс

Н. контролер ассистент А.С. Лошкарев

Разработал ИСТ-31 А.А. Куртуков

Самара 2017



Федеральное агентство связи

Федеральное государственное бюджетное образовательное учреждение высшего образования «Поволжский государственный университет телекоммуникаций и информатики»

Задание по подготовке выпускной квалификационной работы

Студента Куртукова Александра Александровича

1 Тема ВКР Моделирование некоторых методов сегментации изображений

Утверждена приказом по университету от 3.04.17 № 74-2

2 Срок сдачи студентом законченной ВКР 15.06.2017

3 Исходные данные и постановка задачи

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

2. Изучить основные типы существующих методов сегментации изображений

3.Провести моделирование двух методов сегментации изображений

4. Проанализировать результаты, полученные в результате моделирования

4 Перечень подлежащих разработке в ВКР вопросов или краткое содержание ВКР. Сроки исполнения 15.06.2017

1. Основные методы сегментации изображений

2.Реализация и сравнение двух методов сегментации изображений

5 Перечень графического материала. Сроки исполнения 15.06.2017

Презентационные материалы

6 Дата выдачи задания « 4 » апреля 2017 г.

Кафедра Информационных систем и технологий

Утверждаю зав. кафедрой, д.т.н., доцент Н.И. Лиманова

Должность Уч. степень, звание Подпись Дата Инициалы Фамилия

Руководитель доцент, к.т.н., с.н.с. О.Л. Куляс

Должность Уч. степень, звание Подпись Дата Инициалы Фамилия

Задание принял к исполнению ИСТ-31 А.А. Куртуков

Группа Подпись Дата Инициалы Фамилия



Федеральное агентство связи

Федеральное государственное бюджетное образовательное учреждение высшего образования «Поволжский государственный университет телекоммуникаций и информатики»

Студент ИСТ-31 А.А.Куртуков

Руководитель ВКР доцент,к.т.н.,с.н.с. О.Л.Куляс

Показатели качества ВКР

1 Работа выполнена :
- по теме, предложенной студентом
- по заявке предприятия
		наименование предприятия
- в области фундаментальных и поисковых научных исследований
		указать область исследований
2 Результаты ВКР:
- рекомендованы к опубликованию
		указать где
- рекомендованы к внедрению
		указать где
- внедрены
		акт внедрения
3 ВКР имеет практическую ценность		Реализовано ПО для сегментации изображений
		в чем заключается практическая ценность
4 Использование ЭВМ при выполнении ВКР:
(ПО, компьютерное моделирование, компьютерная обработка данных и др.)		Программная среда Matlab,
		Открытая библиотека OpenCV
5. ВКР прошла проверку на объем заимствований		% заимствований
		электронная версия сдана

По ВКР студента Куртукова Александра Александровича

На тему Моделирование некоторых методов сегментации изображений



Введение

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

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

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

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

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

Объектом исследований является цифровая обработка изображений.

Предметом исследований являются алгоритмы и методы сегментации изображения.

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

• Изучить и проанализировать основные методы сегментации изображений;

• Составить план алгоритма, реализующего определенный метод сегментации изображений;

• Провести моделирование алгоритма и анализ результатов программными средствами C++ и Matlab.

Теоретические и практические вопросы, лежащие в основе дипломной работы, рассмотрены в большом количестве источников различного характера. К таким источникам относятся учебные и учебно-методические пособия, специальные издания и электронные источники информации. Математический аппарат методов сегментации изображений рассматривается в работахD.Comaniciu [1-3], W.Doyle [4], M.C.Аndrade[5,6],T.Kong [7],G.Bertrand [8], E.J.Breen [15] L.Vincent [9], F.Meyer [10], M.Grimaud [11], S.Beucher [12], C.Vachier [13] и Р.Гонсалеса [14].

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

Во втором разделе описывается реализация алгоритма сегментации изображений с использованием метода водораздела и на основе графов, проведен анализ результатов. При моделировании использовались средства среды Matlab и открытой библиотеки OpenCV.

Заключение содержит обобщённые результаты дипломной работы, выводы по работе и рекомендации по использованию её результатов.



1. Методы сегментации изображений

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

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

Рис.1.1 - Классификация методов сегментации изображений



1.1 Бинаризация

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

Пороговая обработка изображения может проводиться разными способами.

1.1.1 Бинаризация с нижним порогом

Бинаризация с нижним порогом является наиболее простой операцией, в которой используется только одно значение порога [1]:

(1.1)

Все значения вместо критерия становятся 1, в данном случае 255 (белый) и все значения(амплитуды) пикселей, которые больше порога t -- 0 (черный).

1.1.2 Бинаризация с верхним порогом

Иногда можно использовать вариант первого метода, который дает негатив изображения, полученного в процессе бинаризации. Операция бинаризации с верхним порогом [2]:

(1.2)



1.1.3 Бинаризация с двойным ограничением

Для выделения областей, в которых значения яркости пикселей может меняться в известном диапазоне, вводится бинаризация с двойным ограничением (t₁<t₂):

(1.3)

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

1.1.4 Неполная пороговая обработка

Данное преобразование дает изображение, которое может быть проще для дальнейшего анализа, поскольку оно становится лишенным фона со всеми деталями, присутствующими на исходном изображении [2].

(1.4)

1.1.5 Многоуровневое пороговое преобразование

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

(1.5)



1.2 Локальная пороговая обработка

В локальных методах пороговой обработки пороговое значение меняется для каждой точки исходя из некоторых признаков области, принадлежащей некоторой окрестности данной точки. Недостатком такого рода преобразований является низкая скорость работы алгоритмов, связанная с пересчетом пороговых значений для каждой точки изображения.

1.2.1 Метод Отсу

Метод использует гистограмму распределения значений яркости пикселей растрового изображения. Строится гистограмма по значениям, где N - это общее кол-во пикселей на изображении, - это кол-во пикселей с уровнем яркости i. Диапазон яркостей делится на два класса с помощью порогового значения уровня яркости k,k -- целое значение от 0 до L. Каждому классу соответствуют относительные частоты [3]:

(1.6)

(1.7)

Средние уровни для каждого из двух классов изображения:

(1.8)

(1.9)

Далее вычисляется максимальное значение оценки качества разделения изображения на две части [3]:

(1.10)

где, - межклассовая дисперсия,

- это общая дисперсия для всего изображения целиком.

1.2.2 Определение порога на основе градиента яркости изображения

Предположим, что анализируемое изображение можно разделить на два класса - объекты и фон. Алгоритм вычисления порогового значения состоит из следующих 2 шагов [4]:

1. Определяется модуль градиента яркости для каждого пикселя изображения

(1.11)

где

и

2. Вычисление порога:

(1.12)

1.2.3 Метод использования энтропии гистограммы

Метод приобрел свои различные формы описания и возможные вариации. Распределения общей массы порогов на определенное количество с использованием различных законов и форм распределения.

Очевидно, вид гистограммы зависит от того, как построены классовые интервалы принадлежности случайной величины. Даже в сильно упрощающем случае равномерного разбиения до сих пор нет удовлетворительного способа построения «правильного» разбиения области гистограммы, представляющей эмпирическую плотность вероятности. «Правильность» разбиения подразумевает, что в стационарном случае ошибка аппроксимации предположительно непрерывной плотности функции распределения кусочно-постоянной функцией минимальна. Трудность состоит в том, что оцениваемая плотность неизвестна, поэтому число интервалов сильно сказывается на виде распределения частот конечной выборки. С одной стороны, при фиксированной длине выборки укрупнение интервалов разбиения ведет к уточнению эмпирической вероятности попадания в них, но слишком сильно сглаживает изучаемое распределение. С другой стороны, измельчение интервалов делает вид распределения неоправданно изрезанным в силу малого количества данных, случайно попадающих в каждый из интервалов. Следовательно, задача построения гистограммы эквивалентна задаче оптимальной фильтрации шума в зависимости от объема данных [4].

Задача оптимального разбиения гистограммы довольно популярна среди специалистов по математической статистике, но нет единого устоявшегося мнения относительно ее решения, поскольку ответы носят полуэмпирический характер, либо требуют априорного знания закона распределения вероятностей, либо вообще имеют характер бытовых советов «группировать так, чтобы было не меньше 6 и не больше 20 интервалов». В классических же курсах по математической статистике эта проблема не обсуждается, видимо, как не решенная до конца или, может быть, как не существенная.

1.3 Глобальная пороговая обработка

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

1.3.1 Метод Бернсена

1. Обычная квадратная апертура с нечетным числом пикселей пробегает в цикле по всем пикселям исходного изображения. На каждом шаге находится Min и Max [4].

2. Находится среднее значение Avg= (Min + Max) /2.

3. Если текущий пиксель больше Avg<E - он становится белым, иначе - чёрным. E - некая константа заданная пользователем.

4. Если среднее меньше порога контраста - то текущий пиксель становится того цвета, который задавался параметром «цвет сомнительного пикселя».

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

1.3.2 Метод Эйквила

Одним из самых производительных методов является метод Эйквеля. Его часто применяют для обработки четких и контрастных изображений. Согласно данному методу изображение обрабатывается с помощью двух концентрических окон: маленького - S, и большого L. Обычно форма окон принимается квадратной. Оба окна последовательно слева направо сверху вниз накладываются на изображение с шагом равным стороне маленького окна S. Для окна L рассчитывается порог B так, чтобы поделить пиксели на два кластера. Если математические ожидания уровня яркости в двух кластерах имеют разницу, превышающую некоторый заданный пользователем уровень , то все пиксели внутри окна S бинаризуются в соответствии с порогом T. В противном случае, яркость пикселей из окна S заменяется некоторым близким значением [4].

1.3.3 Метод Ниблэка

Идея данного метода состоит в варьировании порога яркости B бинаризации от точки к точке на основании локального значения стандартного отклонения. Порог яркости в точке (x, y) рассчитывается так:

(1.13)

где - среднее и -среднеквадратичное отклонение выборки для некоторой окрестности точки.

Размер окрестности должен быть минимальным, но таким, чтобы сохранить локальные детали изображения. В то же время размер должен быть достаточно большим, чтобы понизить влияние шума на результат. Значение k определяет, какую часть границы объекта взять в качестве самого объекта. Значение k=-0.2 задает достаточно хорошее разделение объектов, если они представлены черным цветом, а значение k=+0.2, - если объекты представлены белым цветом [5].

1.3.4 Метод Яновица и Брукштейна

В качестве пороговой поверхности бинаризации используется поверхность потенциалов, строящаяся на основе локальной максимизации градиента яркости. Значение градиента яркости часто рассчитывается с помощью контурного оператора Собеля или Кэнни. Изображение фильтруется с целью получения контурных линий толщины в 1 пиксель, а затем усредняющим фильтром 3Ч3. Потенциальная поверхность, теперь, строится по итерационной интерполирующей схеме. Расчет поверхности идет в порядке, начиная от контурных пикселей. Для каждого не контурного пикселя рассчитывается интерполяционный остаток R(x, y) и новое значение пикселя P(x, y) на n+1-ом шаге должно рассчитываться в соответствии с формулами:

(1.14)

(1.15)

в в пределах 1?в?2 для быстрой сходимости.

1.4 Сегментация методом управляемого водораздела

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

Существует много изображений, которые содержат исследуемый объект достаточно однородной яркости на фоне другой яркости. В качестве примера можно привести рукописный текст, ряд медицинских изображений и т.д. Если яркости точек объекта резко отличаются от яркостей точек фона, то решение задачи установления порога является несложной задачей. На практике это не так просто, поскольку исследуемое изображение подвергается воздействию шума и на нем допускается некоторый разброс значений яркости. Известно несколько аналитических подходов к пороговому ограничению по яркости. Один из методов состоит в установлении порога на таком уровне, при котором общая сумма элементов с подпороговой яркостью согласована с априорными вероятностями этих значений яркости [5].

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

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

Развитие технологий обработки изображений привело к возникновению новых подходов к решению задач сегментации изображений и применении их при решении многих практических задач.

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

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

1.5 Метод быстрой корреляции

Метод быстрой корреляции с предварительно подготовленным множеством шаблонов состоит из следующих шагов [5].

1. Предварительные действия включают в себя подготовку набора шаблонов (выполняется один раз для всего набора изображений).

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

3. Формирование корреляционных полей заключается в расчете корреляции с каждым из шаблонов для всех его положений в области поиска.

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

5. Принятие решения осуществляется на основе анализа корреляционных полей в области выбранных точек. Необходимо по набору точек корреляционных полей выбрать координаты искомого объекта. Простейшим критерием выбора является максимальное значение корреляции по всем оставшимся точкам всех корреляционных полей.

1.6 Многошаговая сегментация

Будем считать, что исходное изображение представлено в полутоновой серой шкале. Выделение однородных по яркости областей (сегментация) в этом случае фактически сводится к кластеризации значений всего одной характеристики (признака) - яркости. Это означает, что обработка всего изображения может осуществляться в рекуррентной сети с одним входным нейроном (M=1). В то же время обычное представление изображения - двумерная матрица. Такое представление естественным образом предполагает использование сети со многими входами (M>1) для распараллеливания процесса обработки. Применение такой рекуррентной сети для кластеризации в нашем случае возможно, если модифицировать сеть таким образом, чтобы у всех нейронов входного слоя была бы одна и та же активационная функция с одинаковыми значениями параметров. Тогда обработка всех яркостей изображения входным слоем сети математически будет эквивалентна их обработке на одном нейроне, что можно использовать при программном моделировании сети. Границам диапазона значений входных сигналов нейрона[]соответствует минимальная и максимальная яркости пикселей изображения.

Сам процесс сегментации, рассматриваемый в этой работе, требует некоторых дополнительных пояснений, приведённых ниже [5].

Пусть µ меняется дискретно от до некоторого . Из уравнения 1.16 ясно, что .

,

(1.16)

Каждому значению ?[ ,], i=1,2,… при отображении соответствует своя последовательность итераций, разбивающая диапазон яркостей изображения на ряд интервалов с одинаковыми свойствами (т. е. кластеров). В зависимости от распределения значений яркостей, часть этих интервалов заполнится, а часть останется пустыми. В целом, всей совокупности значений соответствует некоторое конечное множество разбиений диапазона.

Процесс кластеризации предполагает нахождение оптимального по некоторому критерию значения , которое обеспечивает наилучшее выделение кластеров. Пусть таким критерием является max|?H| энтропии распределения, получаемого в результате отображения, разбивающего диапазон яркостей на ряд кластеров. Тогда полученное разбиение обеспечивает максимальную упорядоченность распределения яркостей изображения для данного по всем выделенным кластерам. Выполним теперь для каждого заполненного кластера следующую процедуру - усредним его яркости и полученным средним заменим все значения, входящие в кластер. Энтропия распределения не изменится, а результатом будет сегментированное изображение, поскольку в нём множество разных исходных яркостей пикселей разделено на несколько подмножеств, объединяющих в себе близкие яркости пикселей [6].

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

На рис. 1.2, схематично представлено распределение значений яркости изображения для до их усреднения в пределах кластера (верхняя часть рис.1.2а) и после усреднения с последующей заменой всех текущих значений кластера (нижняя часть рис.1.2а). Энтропия в обоих случаях неизменна и равна 1,89 бита. На рис.1.2б, представлено распределение для некоторого значения ? при повторном процессе. Энтропия, соответственно, равна 1,24 бита. Иными словами, новое распределение более упорядочено.

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

При реализации многошагового процесса возникает вопрос о его сходимости к устойчивому сегментированному изображению (энтропия которого не меняется) [6].

Рис.1.2 - Распределение значений яркостей по кластерам для разных mм. Цифрами указано количество значений, попавших в интервал [, ], k=1,2,…,5

1.7 Метод нормальных разрезов

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

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

Одним из методов разделения графа является метод нормализованных разрезов. Суть метода заключается в том, чтобы разрезать два связанных компонента так, чтобы в каждой группе стоимость разрезания была мала по сравнению с общим сходством. Этот подход можно формализовать, разделив взвешенный граф V на два компонента А и В и за- писав декомпозицию графа как [6]:

(1.17)

где cut(A,B) - сумма весовых коэффициентов всех рёбер графа V, один конец которых лежит в А, а другой - в В;

assoc(A,V) - сумма весовых коэффициентов всех рёбер, один конец которых находится в А. Данный параметр мал, если при разрезании получаются два компонента, имеющих между собой мало рёбер с малыми весовыми коэффициентами и много внутренних рёбер с большими весовыми коэффициентами

1.8 Метод квантилей

Метод в его исходном виде предполагает, что яркость любого пикселя объекта на изображении выше, чем яркость любого пикселя фона. Из этого предположения вытекает простой метод сегментации. Упорядочим все пиксели изображения по убыванию яркости. Из нашего предположения следует, что пиксели, принадлежащие проекции объекта, расположатся в начале упорядоченной последовательности. Поэтому мы можем пометить первые S пикселей меткой «Объект» - они и будут принадлежать искомой проекции [5,6].

К сожалению, это предположение выполняется не всегда. Наше изображение здесь тоже не исключение. Результат сегментации описанным методом представлен ниже. Пиксели объекта отмечены белым цветом, пиксели фона -- чёрным.

Рис.1.3 - Обработка изображения методом квантилей

На реальных изображениях, как наше, вряд ли удастся подобрать такое пороговое значение яркости, чтобы большую порога яркость имели ровно S пикселей изображения. Часто при одном пороге яркости (t) мы отсекаем A<S пикселей, а при пороге (t-1)-B>S пикселей. «Упорядочить», как предложено выше, одинаковые по яркости пиксели мы не можем, мы должны или брать все пиксели яркости (t), или не брать. Самый простой способ решить - посмотреть, что меньше: (S-A) или (B-S). Смотрим, какое число - A или B - ближе к тому, что нужно получить, и берём соответствующий порог.

Предположение оригинального метода не выполняется зачастую из-за влияния шума: хотя в среднем яркость пикселя объекта выше яркости пикселя фона, но в отдельных случаях может быть и наоборот. (Здесь стоит отметить, что когда разница средних яркостей большая, а дисперсия шума невелика, то может «работать» и первый метод.) «Улучшенный» метод квантилей использует именно предположение о разнице средних значений яркости объекта и фона.

Математическая статистика говорит нам, что в нашем случае гауссова шума оценка среднего значения яркости в точке, выполненная путём вычисления среднего арифметического яркости по окрестности, будет состоятельной и несмещённой оценкой. Иными словами, мы не знаем истинную среднюю яркость для каждого пикселя изображения, но мы можем взять некоторую окрестность этого пикселя B(z,r), где z - координаты пикселя, r - радиус окрестности [7]:

(1.18)

и вычислить среднее арифметическое яркости по этой окрестности:

(1.19)

Здесь Q - множество пикселей изображения, - яркость изображения в точке t. Этой оценкой мы вполне легально можем пользоваться вместо истинного среднего значения, и чем больший радиус окрестности мы возьмём, тем точнее будет оценка.

В «улучшенном» методе квантилей прежде всего вычисляется среднее арифметическое по вышеприведённой формуле в каждой точке. Затем выполняется та же процедура, что и в оригинальном методе, только вместо непосредственных значений яркости используются оценки среднего. Вместо сглаживания изображения путём вычисления среднего арифметического на практике часто используется сглаживание изображения фильтром Гаусса - это взвешенное среднее с коэффициентами соответствующего распределения; такое сглаживание решает некоторые проблемы, имеющиеся у среднего арифметического.)

Для нашего изображения мы получим вот такой результат (сегментация с r=1):

Рис.1.4 - Сегментация изображения методом квантилей с радиусом r=1

Результат заметно улучшился. Увеличим радиус для вычисления среднего арифметического до r=2:

Рис.1.5 - Сегментация изображения методом квантилей с радиусом r=2

При радиусе 2 посторонних «пятнышек» совсем не осталось. Можно, однако, заметить, что с увеличением радиуса искажается граница объекта. Это связано с тем, что оценка истинного среднего по среднему арифметическому верна лишь тогда, когда окрестность B(z,r) лежит или целиком на объекте, или целиком на фоне, то есть когда в неё попадают случайные величины с одним и тем же оцениваемым средним значением. На границе в окрестность попадают пиксели и фона, и объекта, что, естественно, искажает оценку [7].

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

Ниже представлены результаты, полученные после выполнения выбора наибольшей связной компоненты на изображениях с результатом сегментации оригинальным методом и «улучшенным» методом с r=1 (при r=2 и так остаётся всего одна связная компонента):

Рис.1.6 - Обработка изображений с выбором наибольшей связной компоненты

Метод квантилей был изобретён достаточно давно, очень прост в реализации. При всей своей простоте, метод даёт неплохие результаты. Хотя в решаемых в настоящее время сложных задачах обработки изображений таких простых методов уже недостаточно для получения нужного результата и разработаны более сложные методы сегментации, простые методы не теряют актуальности. Они используются как составная часть более сложных алгоритмов, а также весьма полезны для реализации «в железе», когда требуются простые в плане вычислений, но надёжные алгоритмы.

1.9 Сегментация изображений на графах

Алгоритм Краскала (или алгоритм Крускала) - эффективный алгоритм построения минимального основного дерева взвешенного связного неориентированного графа. Также алгоритм используется для нахождения некоторых приближений для задачи Штейнера.

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

Пример:

Дан взвешенный неориентированный граф. Требуется найти такое поддерево этого графа, которое бы соединяло все его вершины, и при этом обладало наименьшим весом (т.е. суммой весов рёбер) из всех возможных. Такое поддерево называется минимальным остовным деревом или просто минимальным остовом.

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

Свойства минимального остова [7,8]:

· Минимальный остов уникален, если веса всех рёбер различны. В противном случае, может существовать несколько минимальных остовов (конкретные алгоритмы обычно получают один из возможных остовов);

· Минимальный остов является также и остовом с минимальным произведением весов рёбер (доказывается это легко, достаточно заменить веса всех рёбер на их логарифмы);

· Минимальный остов является также и остовом с минимальным весом самого тяжелого ребра (это утверждение следует из справедливости алгоритма Крускала);

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

Алгоритм Крускала:

Данный алгоритм был описан Крускалом (Kruskal) в 1956 г.

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

Простейшая реализация [8]:

Этот код самым непосредственным образом реализует описанный выше алгоритм, и выполняется за O(MlogN+N²). Сортировка рёбер потребует O(MlogN) операций. Принадлежность вершины тому или иному поддереву хранится просто с помощью массива tree_id - в нём для каждой вершины хранится номер дерева, которому она принадлежит. Для каждого ребра мы за O(1) определяем, принадлежат ли его концы разным деревьям. Наконец, объединение двух деревьев осуществляется за O(N) простым проходом по массиву tree_id. Учитывая, что всего операций объединения будет N-1, мы и получаем асимптотику O (MlogN+N²).

int m;

vector< pair < int, pair<int,int>>> g (m); // вес - вершина 1 - вершина 2

int cost = 0;

vector< pair<int,int>> res;

sort (g.begin(), g.end());

vector<int> tree_id (n);

for (int i=0; i<n; ++i)

tree_id[i] = i;

for (int i=0; i<m; ++i)

{

int a = g[i].second.first, b = g[i].second.second, l = g[i].first;

if (tree_id[a] != tree_id[b])

{

cost += l;

res.push_back (make_pair (a, b));

int old_id = tree_id[b], new_id = tree_id[a];

for (int j=0; j<n; ++j)

if (tree_id[j] == old_id)

tree_id[j] = new_id;

}

}

Так же, как и в простой версии алгоритма Крускала, отсортируем все рёбра по неубыванию веса. Затем поместим каждую вершину в своё дерево (т.е. своё множество) с помощью вызова функции DSU MakeSet - на это уйдёт в сумме O (N). Перебираем все рёбра (в порядке сортировки) и для каждого ребра за O (1) определяем, принадлежат ли его концы разным деревьям (с помощью двух вызовов FindSet за O (1)). Наконец, объединение двух деревьев будет осуществляться вызовом Union - также за O (1). Итого мы получаем асимптотику O (M log N + N + M) = O (M log N).

Реализация [8]:

Для уменьшения объёма кода реализуем все операции не в виде отдельных функций, а прямо в коде алгоритма Крускала.

Здесь будет использоваться рандомизированная версия DSU.

vector<int> p (n);

int dsu_get (int v) {

return (v == p[v]) ? v : (p[v] = dsu_get (p[v]));

}

void dsu_unite (int a, int b) {

a = dsu_get (a);

b = dsu_get (b);

if (rand() & 1)

swap (a, b);

if (a != b)

p[a] = b;

}

... вфункции main(): ...

int m;

vector< pair < int, pair<int,int>>> g; // вес - вершина 1 - вершина 2

... чтениеграфа ...

int cost = 0;

vector< pair<int,int>> res;

sort (g.begin(), g.end());

p.resize (n);

for (int i=0; i<n; ++i)

p[i] = i;

for (int i=0; i<m; ++i) {

int a = g[i].second.first, b = g[i].second.second, l = g[i].first;

if (dsu_get(a) != dsu_get(b)) {

cost += l;

res.push_back (g[i].second);

dsu_unite (a, b);

}

}

До начала работы алгоритма необходимо отсортировать рёбра по весу, это требует O(E Ч log(E)) времени. После чего компоненты связности удобно хранить в виде системы непересекающихся множеств. Все операции в таком случае займут O(EЧб(E, V)), где б - функция, обратная к функции Аккермана. Поскольку для любых практических задачб(E, V) < 5, то можно принять её за константу, таким образом, общее время работы алгоритма Краскала можно принять заO(E * log(E)).

Рис.1.7 - Иллюстрация графа из N вершин и графа, у которого каждая вершина в своём множестве

В текущей постановке задачи вершины графа(v_i)- представляют собой города, а ребраe()- дороги между городами. Нам известны расстояния между парами городов()- это вес реберw(e()). Нужно найти MST, т.е. такое дерево в графе (без циклов: зачем строить лишние дороги), чтобы сумма ребер была минимальной и при этом все вершины были достижимы.

Изначально каждая вершина (город) сам по себе и является единственным гордым представителем соответствующего множества (по количеству вершин). Пусть пока думает, что именно она образовала MST. В ходе алгоритма мы эффективно и дипломатично объединим все эти разрозненные множества в одно единственное G так, чтобы участвующие в нем вершины образовали MST. Для этого [8,9]:

· Сортируем все имеющиеся в графе ребра в порядке возрастания длины (дороги);

· Пробегая по ребрам в порядке возрастания длин, смотрим на концы ребра e = (a,b):

· Если вершины (a и b) принадлежат одному множеству: Значит, они уже участвуют в некотором образованном подмножестве микро-MST, внутри их подграфа сумма ребер уже минимальна. Такое ребро пропускается - оно нам не нужно т.к. иначе оно образует цикл в дереве, и мы зря израсходуем асфальт;

· Если вершины (a и b) принадлежат разным подмножествам микро-MST: Нужно объединять, т.к. мы нашли ребро (дорогу) минимальной длины, объединяющее (сливающее) оба подмножества в одно. Все ребра меньшей длины уже рассмотрены и дешевле, чем этим ребром, объединить не получится. Такое ребро заносится в список ребер, использованных при построении дерева MST, а множества объединяются в одно;

· Продолжаем цикл объединения до получения одного единственного множества, равного искомому MST, в котором будут присутствовать все вершины графа;

· Получаем одно единственное множество вершин (MST) и список ребер, использованных для его объединения, который представляет собой дерево минимальной суммарной длинны, объединяющее все вершины.

Рис.1.8 - Иллюстрация работы алгоритма Краскала

Для реализации понятия «множество» в алгоритме Краскала применяется структура данных Disjoint-set data structure. Работа с ней оптимизирована на выполнение двух основных операций [9]:

· Узнать для некоторой вершины, какому множеству в текущий момент она принадлежит;

· Быстро объединить эти множества в одно.

Чтобы приблизиться к теме сегментации изображений, описание продолжим в терминологии пикселей изображения и их цвета. Допустим, мы сегментируем попугайчика на фоне какого-нибудь Японского синего моря. Сначала каждый пиксель (вершина графа) будет сам по себе - в собственном сегменте (множестве), но в ходе алгоритма пиксели (вершины) «схожего» цвета (одного объекта) постепенно объединяются в один сегмент.

Допустим, на определенном шаге алгоритма попалось ребро, соединяющее два соседних пикселя: на одном конце ребра пиксель «оранжевый», а на другом «красный». Длину ребра определим как «разницу цвета» между пикселями. Все ребра меньшей длины (со схожим цветом) уже объединены: наверняка уже выделен оранжевый и красный сегмент попугайчика. Следуя алгоритму, нам нужно узнать, в одном ли сегменте лежат текущие «оранжевый» и «красный» пиксель? Если в разных, и мы считаем, что сегменты по цвету схожи, то объединяем их в один и продолжаем построение. В общем, тот же алгоритм Краскала, только с пикселями.

Используемая для этих операций структура - очень похожа на дерево (хотя и реализуется массивом индексов). В ней для каждого пикселя указан предок, т.е. указатель (индекс) на некоторый схожий по цвету пиксель, находящийся в том же самом сегменте. Основные операции [9]:

· Поиск сегмента некоторого пикселя x': идем по предкам до самого верха. Самый верхний пиксель - это корень дерева, «представитель» данного сегмента на текущий момент.

· Объединение сегментов. Если у пикселей разные «представители» -- значит, они принадлежат различным сегментам, иначе корень был бы один. Для их объединения «представителя» сегмента меньшей высоты (от самого далекого пикселя до корня) ссылаем (из него указываем) на более длинного «представителя», чтобы не увеличивать высоту дерева. Теперь имеем объединенный сегмент с общим представителем.

· Для того, чтобы в следующий раз не бегать далеко от пикселя к корню, после того, как «представитель» будет успешно обнаружен, устанавливаем прямую ссылку из пикселя - сразу на него. Это сокращает путь следующих поисков, и называется "path compression".

Рис.1.9 - Иллюстрация работы структуры данных Disjoint-set data structure

1.10 Выводы

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



2. Программная реализация методов сегментации изображений

2.1 Сегментация методом водораздела на основе библиотеки OpenCV

Разделение соприкасающихся предметов на изображении является одной из важных задач обработки изображений. Часто для решения этой задачи используется так называемый метод маркерного водораздела. При преобразованиях с помощью этого метода нужно определить "водосборные бассейны" и "линии водораздела" на изображении путем обработки локальных областей в зависимости от их яркостных характеристик.

Метод маркерного водораздела является одним из наиболее эффективных методов сегментации изображений. При реализации этого метода выполняются следующие основные процедуры [9,10]:

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

2. Вычисление маркеров переднего плана изображений. Они вычисляются на основании анализа связности пикселей каждого объекта.

3. Вычисление фоновых маркеров. Они представляют собой пиксели, которые не являются частями объектов.

4. Модификация функции сегментации на основании значений расположения маркеров фона и маркеров переднего плана.

5. Вычисления на основании модифицированной функции сегментации.

Алгоритм работает с изображением как с функцией от двух переменных f=I(x,y), где x,y- координаты пикселя.

Рис.2.1 - Пример работы метода водораздела

Значением функции может быть интенсивность или модуль градиента. Для наибольшего контраста можно взять градиент от изображения. Если по оси OZ откладывать абсолютное значение градиента, то в местах перепада интенсивности образуются хребты, а в однородных регионах - равнины. После нахождения минимумов функции f, идет процесс заполнения «водой», который начинается с глобального минимума. Как только уровень воды достигает значения очередного локального минимума, начинается его заполнение водой. Когда два региона начинают сливаться, строится перегородка, чтобы предотвратить объединение областей. Вода продолжит подниматься до тех пор, пока регионы не будут отделяться только искусственно построенными перегородками [10].

Рис.2.2 - Иллюстрация процесса заполнения «водой»

Такой алгоритм может быть полезным, если на изображении небольшое число локальных минимумов, в случае же их большого количества возникает избыточное разбиение на сегменты. Например, если непосредственно применить алгоритм к рис.2.3, получим много мелких деталей рис.2.4.

Рис.2.3 - Исходное изображение

Рис.2.4 - Изображение после сегментации алгоритмом WaterShed

Чтобы избавиться от избытка мелких деталей, можно задать области, которые будут привязаны к ближайшим минимумам. Перегородка будет строиться только в том случае, если происходит объединение двух регионов с маркерами, в противном случае будет происходить слияние этих сегментов. Такой подход убирает эффект избыточной сегментации, но требует предварительной обработки изображения для выделения маркеров, которые можно обозначить интерактивно на изображении рис.2.5, 2.6.

Рис.2.5 - Изображение с маркерами

Рис.2.6 - Изображение после сегментации алгоритмом WaterShedс использованием маркеров

Если требуется действовать автоматически без вмешательства пользователя, то можно использовать, например, функцию findContours для выделения маркеров, но тут тоже для лучшей сегментации мелкие контуры следует исключить рис.2.7 [10], например, убирая их по порогу по длине контура. Или перед выделением контуров использовать эрозию с дилатацией, чтобы убрать мелкие детали.

Рис.2.7 - В качестве маркеров использовались контуры, имеющие длину выше определенного порога

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

Код для запуска алгоритма:

Mat image = imread("coins.jpg", CV_LOAD_IMAGE_COLOR);

// выделимконтуры

Mat imageGray, imageBin;

cvtColor(image, imageGray, CV_BGR2GRAY);

threshold(imageGray, imageBin, 100, 255, THRESH_BINARY);

std::vector<std::vector<Point>> contours;

std::vector<Vec4i> hierarchy;

findContours(imageBin, contours, hierarchy, CV_RETR_TREE, CV_CHAIN_APPROX_SIMPLE);

Mat markers(image.size(), CV_32SC1); markers = Scalar::all(0);

intcompCount = 0;

for(intidx = 0; idx>= 0; idx = hierarchy[idx][0], compCount++)

{

drawContours(markers, contours, idx, Scalar::all(compCount+1), -1, 8, hierarchy, INT_MAX);

}

std::vector<Vec3b>colorTab(compCount);

for(inti = 0; i<compCount; i++)

{

colorTab[i] = Vec3b(rand()&255, rand()&255, rand()&255);

}

watershed(image, markers);

Mat wshed(markers.size(), CV_8UC3);

for(inti = 0; i<markers.rows; i++)

{ for(int j = 0; j <markers.cols; j++)

{

int index = markers.at<int>(i, j);

if(index == -1) wshed.at<Vec3b>(i, j) = Vec3b(0, 0, 0);

elseif (index == 0) wshed.at<Vec3b>(i, j) = Vec3b(255, 255, 255);

else wshed.at<Vec3b>(i, j) = colorTab[index - 1];

}

}

imshow("watershed transform", wshed);

waitKey(0);

2.2 Сегментация методом водораздела средствами Matlab

Шаг 1: Считывание цветного изображения и преобразование его в полутоновое [11,15].

Считаем данные из файла pears.png:

rgb=imread('pears.png');

и представим их в виде полутонового изображения.

I=rgb2gray(rgb);

imshow(I)

text(732,501,'…','FontSize',7,'HorizontalAlignment','right')

Рис.2.8 - Исходное изображение

Шаг 2: Использование значения градиента в качестве функции сегментации.

Для вычисления значения градиента используется оператор Собеля, функция imfilter и другие вычисления. Градиент имеет большие значения на границах объектов и небольшие (в большинстве случаев) вне границ объектов.

hy=fspecial('sobel');

hx=hy';

Iy=imfilter(double(I), hy, 'replicate');

Ix=imfilter(double(I), hx, 'replicate');

gradmag=sqrt(Ix.^2+Iy.^2);

figure, imshow(gradmag,[]), title('значениеградиента')

Рис.2.9 - Значение градиента

Таким образом, вычислив значения градиента, можно приступить к сегментации изображений с помощью рассматриваемого метода маркерного водораздела [11,12].

L=watershed(gradmag);

Lrgb=label2rgb(L);

figure, imshow(Lrgb), title('Lrgb')

Рис.2.10 - Предварительная сегментация изображения

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