Методы обработки изображений с импульсным шумом на основе алгоритма кластеризации Кутлунин Павел Евгеньевич

Содержание к диссертации

Введение

Глава 1. Обзор методов кластеризации изображений 10

1.1 Проблема и инструменты сегментации изображений 10

1.2 Кластеризация методом k-средних 12

1.3 EM-кластеризация 14

1.4 Метод среднего сдвига 16

1.5 Метод водораздела (Watershed Segmentation) 18

1.6 SUSAN 19

1.7 Интерактивная сегментация изображений

1.7.1 Magic Wand 21

1.7.2 GraphCuts 21

1.7.3 Intelligent Scissors 22

1.7.4 GrubCut 23

1.7.5 Lazy Snapping 23

1.7.6 Progressive Cut 24

1.7.7 Random Walker 24

1.7.8 GrowCut 25

1. 8. Выводы 26

Глава 2. Использование метода кластеризации изображений для выделения односвязных областей 27

2.1. Введение 27

2.2. Постановка задачи выделения односвязных областей и метод её решения 29

2.3. Компьютерный эксперимент по выделению односвязных областей 35

2.4. Обсуждение результатов 52

2.5. Выводы 53

Глава 3. Использование метода кластеризации для выделения контуров на изображении 54

3.1. Введение 54

3.2. Постановка задачи выделения контуров и метод её решения 56

3.3. Компьютерный эксперимент по нахождению границ на изображениях 57

3.4. Обсуждение результатов 68

3.5. Выводы 75

Глава 4. Выявление повреждённых пикселей на изображении с помощью алгоритма кластеризации 76

4.1. Введение 76

4.2. Постановка задачи 78

4.3. Алгоритм определения повреждённых пикселей 79

4.4. Компьютерный эксперимент по выявлению повреждённых пикселей 82

4.5 Алгоритм восстановления повреждённых пикселей 92

4.6. Обсуждение результатов 102

4.7. Выводы 105

Заключение 107

Список литературы

• Метод водораздела (Watershed Segmentation)
• Intelligent Scissors
• Компьютерный эксперимент по выделению односвязных областей
• Компьютерный эксперимент по нахождению границ на изображениях

Введение к работе

Актуальность темы исследования

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

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

Первый подход связан с представлением изображения в виде функции или набора функций от двух переменных, для которых определены значения в узлах прямоугольной сетки. В этом случае к изображению применяются численные методы анализа непрерывных функций с использованием конечных разностей. Значительный вклад в развитие данного подхода внесли: Дж. Кэнни, Дж. Прюитт, Л. Робертс, И. Собель, Х. Щарр, В.А. Сойфер, Б.М. Миллер, Ю.И. Журавлёв, Л.П. Ярославский, В.С. Киричук, А.Г. Коробейников, И.П. Гуров, В.В. Сергеев и др. Однако данный подход имеет существенные ограничения к применению в случае изображений с импульсным шумом. Импульсный шум воспринимается как локальные максимумы функции и усиливается при вычислении производных. Для устранения данной проблемы используются методы предварительной обработки, основанные на сглаживающих фильтрах. Однако подобная предобработка, устраняя точечные шумы, приводит к размытию контуров и ухудшает окончательные результаты обработки изображения.

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

Метод сегментации изображений, основанный на представлении изображения в виде графа с последующим его разбиением на подграфы, был предложен Фелзензвалбом и Хаттенлохером (P.F. Felzenszwalb, D.P. Huttenlocher, 2004). Каждому пикселю изображения сопоставлялась вершина графа, а вес ребра, соединяющего соседние пиксели, вычислялся на основе разности интенсивностей цветовых компонент и геометрического расстояния между пикселями. Разбиение на подграфы производилось удалением отдельных рёбер таким образом, чтобы вес удаляемого ребра превосходил веса всех рёбер, входящих в подграф. Данный метод не получил развития в рамках задачи кластеризации изображений в силу высоких требований к памяти и

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

Проблема поиска пикселей на изображении, изменённых импульсным шумом, также относится к задачам обучения без учителя и не имеет на сегодняшний день удовлетворительного решения. Широко распространённый подход состоит в подавлении шумов с помощью сглаживающих фильтров. Однако сглаживающие преобразования вносят существенные изменения в изображение. В связи с этим в последние двадцать лет развивается подход, основанный на выявлении повреждённых пикселей и их дальнейшей аппроксимации. Большинство современных методов выявления повреждённых пикселей использует алгоритм SD-ROM (Abreu E. и др., 1996). В данном алгоритме исследуется некоторая малая окрестность каждого пикселя и принимается решение о его поврежденности. Главным недостатком алгоритма SD-ROM и других методов, основанных на нем, состоит в локальности данных, используемых для принятия решения, которая не позволяет выявлять протяжённые элементы изображения. Как следствие, методы, основанные на алгоритме SD-ROM, характеризуются высоким процентом ложных срабатываний. В связи с этим актуальной является задача построения метода выявления повреждённых пикселей на основе анализа изображения в целом.

Цель работы

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

Для достижения поставленной цели были решены следующие задачи:

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

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

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

4. Реализация и тестирование разработанных алгоритмов.

Объект исследования

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

Предмет исследования

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

Методы исследования

Для решения данного комплекса задач были использованы методы теории графов и методы кластеризации.

Основные положения, выносимые на защиту

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

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

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

Научная новизна

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

9. Разработан алгоритм выделения контуров на основе кластеризации. Новизна состоит в том, что для определения контуров не используются дифференциальные фильтры, что делает алгоритм устойчивым к импульсным шумам. Алгоритм позволяет получить контурные линии заданной толщины.

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

11. Разработан программный комплекс, позволяющий осуществлять кластеризацию изображения, выделение контуров объектов на изображении и выявление импульсного шума на изображении. Разработанный программный комплекс зарегистрирован в «Фонде алгоритмов и Программ Российской Академии Наук» под серийным номером PR15003 19 мая 2015 года и PR15005 21 мая 2015 года. Для программного комплекса получены свидетельства о государственной

регистрации программ для ЭВМ №2015614744 от 28 апреля 2015 года и №2015614745 от 28 апреля 2015 года.

Практическая и научная значимость результатов

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

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

Апробация работы

Основные результаты диссертации докладывались и обсуждались на следующих научных конференциях: Международная научная конференция «Решетнёвские чтения» (Красноярск, 2012), VI Международная конференция «Проблемы оптимизации и экономические приложения» (Омск, 2015), научный семинар в институте систем информатики им. А.П. Ершова СО РАН (Новосибирск, 2015).

Степень достоверности результатов работы

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

Публикации

Материалы диссертации опубликованы в 12 печатных изданиях, из них 3 статьи в журналах из списка, рекомендованного ВАК, 5 статей в материалах конференций и 4 свидетельства о регистрации программ.

Личное участие автора в получении научных результатов На этапе разработки алгоритмов основные результаты исследований получены в соавторстве с научным руководителем, д.ф.-м.н., профессором С.В. Белимом, и являются неделимыми. Реализация и тестирование алгоритмов является самостоятельной работой автора.

Структура и объем диссертации

Метод водораздела (Watershed Segmentation)

ЕМ-кластеризация стала интересной для области компьютерного зрения после статьи, описывающей систему Blobworld [56], которая использует особенности цвета и текстуры в векторе свойств для каждого пикселя и алгоритм, описанный выше, для разбиения изображения. Кроме использования ЕМ-кластеризации, в этой статье также описывается новый набор особенностей, которые могут быть использованы в векторе свойств пикселей: полярность, анизотропия и контраст [56]. Полярность является мерой пространства, для которого все векторы градиентов в некоторой окрестности направлены в одну сторону; анизотропия - функция отношения собственных значений матрицы вторых момента и контраста, является мерой однородности значений пикселей. Текстура вычислялась для различных масштабов для каждого пикселя, и масштаб, в котором изменения полярности становились минимальными (менее 2%), выбирался в качестве оптимального масштаба для данного пикселя. Алгоритм тестировался на маленьких значениях К, чтобы произвести небольшое количество областей, называемых каплями (blobs, отсюда название системы Blobworld), которые могут быть использованы для поиска по изображению.

Для работы описанных выше методов кластеризации k-средних и ЕМ-алгоритма необходимо задать требуемое количество кластеров. В то время как для определённого круга задач указание параметра является разумным, существует ряд задач, где количество кластеров в значительной степени зависит от исходного изображения. Следовательно, алгоритмы кластеризации, которые могут определять количество кластеров в процессе кластеризации, больше подходят для задач разбиения произвольного изображения. Для выбора количества кластеров во время процесса кластеризации был специально разработан метод среднего сдвига.

Идея метода среднего сдвига очень проста и основана на гистограмме изображения. Рассмотрим работу алгоритма на монохромном изображении, а затем опишем его использование для цветных изображений. Пусть X = {x„...,xN} - множество из N пикселей изображения, и предположим, что вектора свойств V{xt) имеют только одну координату -интенсивность серого тона, то есть векторы являются одномерными. Пусть Н(Х) - гистограмма изображения, Н(Х) - это множество контейнеров #0,#1,...,#G, где 0 и G- минимальная и максимальная интенсивности серого тона соответственно. Окном гистограммы W называется смежное множество контейнеров некоторой фиксированной длины ws, сосредоточенное вокруг некоторого контейнера bt. В общем случае длина ws окна W будет нечётным числом. Идея метода среднего сдвига заключается в том, чтобы начать алгоритм с произвольного окна с центром в виде случайного точки и сдвигать его центр, основываясь на данных внутри него, до тех пор, пока окно не сойдётся в моде гистограммы. Эта мода определяет кластер, и процесс повторяется, пока все контейнеры не будут связаны с вычисленными точками. Процедура сдвига выполняется в несколько шагов и гарантированно сходится: 1. Инициализировать алгоритм случайной точкой, на основе которой выбирается контейнер и выбирается окно W с центром в этом контейнере. 2. Вычислить центр тяжести или взвешенное среднее wm гистограммы значений в окне W : wm = Ь,(Ь.) , где /( ,.) - счётчик в контейнере, bjGW нормализованный путём деления на сумму всех счётчиков во всех контейнерах окна W. 3. Переместить окно поиска W в точку wm . 4. Повторять шаги 2 и 3 до схождения. Для использования метода среднего сдвига для кластеризации монохромных изображений процедура сдвига выполняется для каждого уровня серого тона и точка схождения сохраняется. Несмотря на то, что теоретически различные точки схождения должны представлять разные кластеры, на практике точки сходимости, находящиеся на небольшом расстоянии друг от друга, группируются для формирования центров кластеров, затем пиксели распределяются по группам с соответствующими точками схождения. Небольшие участки на изображении могут быть исключены из рассмотрения, как это делается в большинстве процедур кластеризации. Похожие подходы встречаются при использовании алгоритмов таксономии для сегментации изображений [14, 33].

В обобщённом алгоритме среднего сдвига [58, 59, 67, 100] используется многомерный вектор свойств и три параметра. Для пространственной области, т.е. точки на двухмерном изображении, параметр as определяет размер окрестности, в которой выполняется переключение. Для диапазона областей, т.е. векторов свойств, параметр тг нормализует диапазон данных. Третий параметр -минимальный размер области - отфильтровывает небольшие области. Затем алгоритм производит нормализацию с целью использования многомерных пространственных областей S нормированных векторов свойств вместо использования одномерного окна серых тонов. Обобщённая фильтрация сдвига среднего определяется следующей процедурой, в которой { у}у=1..„ - множество пикселей, {Zj} у=1 „ - результирующие точки схождения для каждого пикселя.

Intelligent Scissors

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

Пусть на некотором этапе построена часть дерева. Рассмотрим ближайших соседей пикселей, для которых соответствующие вершины входят в построенную часть дерева. Из множества найденных ближайших соседей выбирается пиксель vn, для которого расстояние до одного из пикселей vm, входящих в дерево является минимальным. Вершина, соответствующая пикселю vn, присоединяется к дереву ребром с весом d(vm, V,,). Алгоритм продолжается до тех пор, пока не будут исчерпаны все пиксели изображения. Данный алгоритм относится к классу жадных, так как на каждом шаге вносится минимальный возможный вклад в общий вес дерева.

Утверждение 2. Результат работы предложенного алгоритма эквивалентен результату работы алгоритма Прима. Доказательство. Пусть на некотором этапе построена часть дерева Tk=(Vk,Ek) , содержащая вершины Vk ={vl,...,vk} . Рассмотрим пиксели, для которых соответствующие вершины не входят в Tk. Пусть V\ - множество пикселей, соответствующих неприсоединённым на к-ом шаге вершинам. Согласно алгоритму Прима, строится часть дерева Tk+i, путём присоединения новой вершины v j к дереву Tk . Tk+1=(Vk+l,Ek+l), (16) Vk+l=Vk\J{v j}, Ek+i=EkV{(vi v j)} V\+1 = V\\{v j}. Вершина v j выбирается таким образом, чтобы вес ребра d{v hvt) был минимальным, vt є Т Алгоритм продолжается до тех пор, пока не будут исчерпаны все вершины V .

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

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

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

При работе данного жадного алгоритма построения минимального остовного дерева в первую очередь будут присоединяться точки, относящиеся к одному кластеру. После исчерпания кластера будет происходить переход на следующий кластер. Ребро, соответствующее переходу на соседний кластер, будет существенно отличаться по длине от соседних рёбер. Для разбиения дерева на поддеревья применяется алгоритм, состоящий из двух шагов. На первом шаге вычисляется максимальный вес ребра в дереве: d = maxOO)). На втором шаге удаляются рёбра, вес которых больше R0d. R0 параметр, задаваемый пользователем и R0 є [0,1] . Для того чтобы не выделять кластеры, содержащие одну вершину, будем удалять только рёбра, приводящие к выделению поддерева, состоящего более, чем из одной вершины.

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

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

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

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

Компьютерный эксперимент по выделению односвязных областей

Необходимость выделения контуров на цифровых изображениях возникает в процессе решения большого количества задач, связанных с анализом графических объектов. На сегодняшний день большинство алгоритмов выделения контуров основываются на дифференциальных операторах. Основная идея всех этих методов состоит в том, что на границах контуров двумерная функция интенсивности цвета испытывает скачок, который может быть определён с помощью исследования производных функции интенсивности цвета. Дифференциальные методы выделения контуров состоят из двух этапов. На первом этапе усиливаются перепады интенсивности. На втором этапе с помощью пороговых методов выделяются контурные точки. Следует отметить, что дифференциальные методы усиливают точечные импульсные шумы. Большинство методов выделения контуров изображения основываются на исследовании градиента интенсивности цвета. Одним из исторически первых методов был предложен Л. Робертсом [45] и основывался на использовании перекрёстного матричного оператора, содержащего конечные разности соседних элементов. Позже Дж. Прюиттом был предложен оператор на основе понятия центральной разницы [45]. Основным недостатком этого подхода является чувствительность к шуму. Наиболее известный из дифференциальных методов выделения контуров основывается на операторе Собеля [45]. Данный подход также основывается на центральных разностях, однако вес центральных элементов увеличен вдвое. Недостатком оператора Собеля является отсутствие полной вращательной симметрии. В работе Г. Шарра [45] предпринята попытка снизить отрицательные эффекты оператора Собеля за счёт увеличения веса центрального элемента, который превосходит веса крайних пикселей в 3,3 раза.