Содержание к диссертации
Введение
1. Методы и алгоритмы сегментации изображений 15
1.1. Обзор методов и алгоритмов сегментации изображений 15
1.2. Бионические модели и методы сегментации изображений 24
1.3. Задачи диссертационной работы 30
1.4. Выводы 33
2. Разработка и оценка гибридного муравьиного метода сегментации сложноструктурированных изображений 35
2.1. Разработка гибридного муравьиного метода сегментации изображений 35
2.2. Определение оптимальных параметров настройки гибридного муравьиного метода 45
2.3. Оценка вычислительной сложности гибридного муравьиного метода 64
2.4. Оценка времени работы гибридного муравьиного метода с помощью теоремы дрейфа 66
2.5. Выводы 70
3. Разработка и оценка гиперэвристического роевого метода сегментации сложноструктурированных изображений 72
3.1. Гиперэвристический роевой метод сегментации изображений 72
3.2. Определение оптимальных параметров настройки гиперэвристического роевого метода
3.3. Оценка вычислительной сложности гиперэвристического роевого метода 101
3.4. Выводы 103
4. Программная реализация, апробация и тестирование разработанных методов сегментации изображений 106
4.1. Описание характеристик и основных функциональных возможностей программного приложения для системы сегментации изображений 106
4.2. Тестирование разработанных методов сегментации и экспериментальные данные 116
4.3. Сравнительная оценка времени работы методов сегментации изображений 141
4.4. Оценка вычислительной сложности гибридного муравьиного метода и гиперэвристического роевого метода с использованием анализа дрейфа 149
4.5. Выводы 152
Заключение 155
Список сокращений и условных обозначений 158
Список использованных источников
- Задачи диссертационной работы
- Оценка вычислительной сложности гибридного муравьиного метода
- Определение оптимальных параметров настройки гиперэвристического роевого метода
- Сравнительная оценка времени работы методов сегментации изображений
Введение к работе
Актуальность темы исследования. Разработка методов распознавания изображений является одной из актуальных и трудных задач теоретической информатики. При создании систем распознавания, к которым предъявляются повышенные требования по точности и производительности, возникает необходимость применения новых методов автоматизации процедуры распознавания изображений. Несмотря на то, что задача разработки методов распознавания изображений, хорошо исследована в теоретическом плане, однако универсального метода ее решения не существует, а практическое решение представляется очень трудным. Существует определенная зависимость эффективности работы методов распознавания от априорных данных и условий работы системы, которые не всегда позволяют решать задачу распознавания с достаточно высокой эффективностью.
При компьютерной обработке и распознавании изображений решается широкий круг задач. Одним из основных этапов распознавания является процесс разделения изображения на неперекрывающиеся области (сегменты), покрывающие все изображение и однородные по некоторым признакам. Сегментация упрощает анализ однородных областей изображения, а также яркостных и геометрических характеристик. Реализация сегментации осуществляется с помощью специальных методов. Их целью является отделение анализируемого объекта, структуры или области интереса от окружающего фона. Это сложная задача, качество выполнения которой существенно влияет на точность и на возможность последующего компьютерного анализа изображений, поскольку возникают трудности, связанные с шумами, размытием изображений и т.д.
Сегментация изображений является актуальной научно-практической задачей, решение которой оказывает существенное влияние на результаты анализа и распознавания изображений. Сегментация – результат понимания изображения, инструмент для его распознавания. Создание эффективных методов сегментации позволит повысить качество и скорость обработки изображений по сравнению с известными методами.
Степень разработанности темы. Для решения задачи сегментации изображений было разработано много методов, базирующихся на яркостной, градиентной и текстурной информации изображения. Результаты исследований методов сегментации и распознавания изображений изложены в работах отечественных и зарубежных ученых: В.П. Вежневеца, Р. Вудса, Р. Гонсалеса, И.П. Гурова, Р. Дуда, Ю.И. Журавлева, В.С. Киричука, А.Г. Коробейникова, Д. Кэнни, Б.М. Миллера, У. Прэтта, Д. Прюитта, К. Рао, Л. Робертса, С.З. Савина, В.В. Сергеева, И. Собеля, В.А. Сойфера, Л.Т. Сушковой, П. Фелзензвалба, К. Фу, Я.А. Фурмана, Р. Харалика, Д. Хаттенлохера, Х. Щарра, С.В. Яблонского, Л.П. Ярославского.
Поскольку в общем случае задача сегментации изображений не решена, возникает необходимость в разработке и реализации усовершенствованных методов и алгоритмов сегментации изображений. Направлениями совершенствования являются максимальное соответствие сегментированной
области реальному объекту, работа в режиме реального времени, низкая вероятность ошибок.
Востребованными областями распознавания цифровых изображений
являются медицина, картография, промышленность, искусство и др. Одной из
главных проблем теоретической информатики является анализ и распознавание
сложноструктурированных изображений. Сложноструктурированные
изображения являются семантически насыщенными изображениями и состоят из большого количества объектов различных видов, каждый из которых обладает собственными значимыми характеристиками. Примерами сложноструктурированных изображений могут быть топографические карты, снимки поверхности Земли из космоса и т.д. Эти изображения имеют свои особенности. Они компактны и малоконтрастны по сравнению с окружающим фоном и являются сложными, размерными и вариабельными. Это накладывает повышенные требования к точности детектирования образований и объектов на изображениях, является основным фактором, который ограничивает применение известных подходов для сегментации изображений.
Авторская гипотеза состоит в том, что подходящим способом для
эффективного решения задачи сегментации сложноструктурированных
изображений является использование математических преобразований,
описывающих коллективное поведение децентрализованной
самоорганизующейся системы, состоящей из множества агентов, локально взаимодействующих между собой и с окружающей средой для достижения предопределенной цели. В природе примерами подобного рода систем являются роевые системы. Каждый агент функционирует автономно, используя правила. В то же время, алгоритм поведения всей системы получается на удивление разумным. Роевой интеллект рассматривается в теоретической информатике как эффективная процедура оптимизации, которой присуща масштабируемость; гибкость; отсутствие жесткой структуры; простота правил поведения агентов.
Важным свойством алгоритмов роевого интеллекта является зависимость их эффективности от используемых в алгоритмах эвристических коэффициентов. Эти коэффициенты могут принимать бесконечное число значений из некоторого диапазона. Поэтому встает вопрос об их подборе и целесообразности проведения экспериментальных исследований на всемирно распространенных тестовых задачах и бенчмарках из библиотек, посвященных распознаванию изображений, чтобы выяснить оптимальные значения коэффициентов и оценить вычислительную сложность роевых алгоритмов.
Ответы на эти и некоторые другие вопросы могли бы в значительной мере конкретизировать и прояснить перспективы применения методов роевого интеллекта для сегментации изображений. Получение теоретической оценки роевых методов сегментации, позволило бы расширить сферу применения бионических моделей в теории распознавания изображений, получить новые научные данные о путях развития объекта исследований, повысить их продуктивность в области сегментации изображений и показать их практический потенциал.
Цель и задачи диссертации. Цель заключается в повышении точности и скорости решения задачи сегментации изображений, имеющей существенное значение для разработки методов анализа и распознавания изображений, на основе использования бионических моделей роевого интеллекта.
В диссертации содержится решение следующей научной проблемы: при заданных исходных изображениях в виде набора пикселей с такими визуальными свойствами, как яркость, цвет, текстура, а также определенного размера, уровня шума, контрастирования и качества, необходимо в пределах имеющихся ресурсов найти такую разметку цифровых изображений на определенное количество регионов, которая обеспечивает высокую точность и качество распознавания изображений.
Для решения научной проблемы и достижения поставленной цели необходимо решить следующие задачи:
анализ существующих методов и алгоритмов сегментации изображений и выделения границ объектов, выявление и обоснование подходов наиболее пригодных для достижения поставленной цели;
разработка, исследование и применение моделей и методов роевого интеллекта для решения задачи сегментации изображений с учетом критериев точности и скорости распознавания;
теоретическая и экспериментальная оценка потенциала роевых методов сегментации с целью расширения сферы применения бионических моделей в теории распознавания изображений, получения новых научных данных о путях развития исследований в области сегментации изображений, повышении их продуктивности;
реализация и тестирование разработанных методов путем разработки специализированного программного обеспечения для сравнения разработанных методов с конкурирующими методами на всемирно распространенных тестовых задачах из библиотек бенчмарок.
Методы исследований. При решении сформулированных в работе задач использовались методы роевого интеллекта, методы кластеризации данных, методы эволюционных вычислений, теория дрейф-анализа, теория множеств, математической статистики, математического моделирования, методы объектно-ориентированного проектирования и программирования.
Научная новизна. В работе получены следующие новые научные результаты, которые выносятся на защиту:
биоинспирированный муравьиный метод сегментации изображений, отличающийся использованием быстрого кластерного анализа (k-means) для перевычисления центра каждого сегмента и применением суперпозиции нескольких критериев оптимальности решений с учетом, как цветовых, так и геометрических характеристик изображения, что позволяет повысить качество обработки изображений в среднем на величину 8,7% по сравнению с известными методами, а также применять метод для сегментации зашумленных и контрастных изображений;
гиперэвристический роевой метод сегментации изображений, отличающийся от известных выбором, комбинированием и адаптацией в
процессе поиска решения нескольких подчиненных эвристик в зависимости от качества исходных изображений (без артефактов и искажений, зашумленные, размытые, контрастные), а также применением динамического весового коэффициента инерции, что позволяет повысить качество и снизить время обработки изображений (в среднем на 9%) по сравнению с известными методами. Метод способен работать, как в автоматическом, так и в интерактивном режимах;
оптимальные параметры настройки муравьиного и роевых методов сегментации, реализующие механизмы управления процессом поиска в пространстве решений, что обеспечивает высокую скорость и точность работы методов, препятствует их преждевременной сходимости в локальных оптимумах;
полиномиальные теоретические и экспериментальные оценки трудоемкости муравьиного и роевых методов сегментации изображений, полученные на основе теорем дрейф-анализа и подтвержденные экспериментально на наборах реальных изображений и бенчмарок из известных международных библиотек.
Теоретическая значимость работы состоит в повышении точности и скорости сегментации изображений за счет использования разработанных бионических методов с доказанными полиномиальными оценками трудоемкости. Теоретически обоснованы и экспериментально установлены оптимальные параметры настройки методов для сегментации изображений.
Практическая значимость работы состоит в возможности использования разработанного программного обеспечения разработчиками систем распознавания изображений, в частности, медицинских снимков, для повышения оперативности и качества процедур диагностирования областей интереса.
Результаты диссертации получены при выполнении научно-исследовательских работ:
на кафедре «Автоматизированные системы управления» Донецкого национального технического университета по теме "Разработка и исследование методов построения компьютерных систем технической и медицинской диагностики" (2012-2015 гг.);
в Институте компьютерных технологий и информационной безопасности ЮФУ по теме проектной части государственного задания в сфере научной деятельности «Разработка теории и основных принципов эволюционных вычислений для поддержки принятия оптимальных решений при проектировании многоцелевых интеллектуальных систем» (2016 г.);
по гранту РФФИ «Развитие теории и применение метаэвристических моделей, методов и алгоритмов для трансвычислительных задач принятия оптимальных решений» (2016-2017 гг.).
Разработанные методы и программное обеспечение используются:
в Институте неотложной и восстановительной хирургии им.
В.К. Гусака (г. Донецк) в рамках научно-исследовательских работ в отделе
неотложной кардиологии и кардиохирургии, что подтверждается соответствующими актами;
в учебном процессе Донецкого национального технического университета на кафедре «Автоматизированные системы управления» и на кафедре математического обеспечения и применения ЭВМ Института компьютерных технологий и информационной безопасности Южного федерального университета.
Степень достоверности и апробация результатов. Достоверность и обоснованность использованных методов исследования и полученных научных результатов подтверждается непротиворечивостью известным данным, высокой степенью сходимости теоретически полученных результатов с полученными экспериментальными данными для реальных изображений и бенчмарок известных международных библиотек.
Основные положения диссертационной работы докладывались и обсуждались на следующих научных конференциях: региональной межвузовской конференции «Young scientists' researches and achievements in science» (Донецк, 2013), VIII всеукраинской конференции «Современные тенденции развития информационных технологий в науке, образовании и экономике» (Луганск, 2014), XVIII международной конференции «Нейроинформатика-2016» (Москва, НИЯУ МИФИ, 2016), XIX международной конференции «Мягкие вычисления и измерения» (Санкт-Петербург, СПбГЭТУ, 2016), Конгрессе по интеллектуальным системам и технологиям IS&IT (Дивноморск, 2016), III международной конференции «Информационные технологии в науке, управлении, социальной сфере и медицине ITSMSSM» (Томск, 2016).
Публикации. По теме диссертационной работы опубликованы 14 печатных работ, отражающих основные положения исследования, в том числе 3 статьи в журналах, рекомендованных ВАК РФ; 1 статья - в изданиях, индексируемых в библиографических базах Scopus и Web of Science, 12 статей -в изданиях, индексируемых в библиографической базе РИНЦ. В рамках диссертационной работы получено свидетельство о регистрации программ для ЭВМ «Программа сегментации МРТ-снимков с использованием модифицированных алгоритмов муравьиных колоний и роя частиц» (№ 2016616997 от 23.06.2016).
Структура и объем работы. Диссертация состоит из введения, 4 разделов, заключения, списка использованной литературы из 120 наименований. Общий объем работы 178 стр., иллюстраций - 77, таблиц - 18.
Задачи диссертационной работы
Под сегментом подразумевается некоторая изолированная область, состоящая из отдельных элементов (пикселей), такая, что расстояние между ее элементами минимально, а расстояние между двумя соседними областями – максимально. Сегментация подразумевает разбиение множества элементов, на сегменты таким образом, чтобы расстояние между элементами внутри группы являлось бы минимальным, а в то же время, расстояние между группами – максимальным. Сегментация является одним из основных этапов обработки и анализа изображений. От ее решения напрямую зависят все последующие этапы обработки, такие как классификация, извлечение образов и идентификация. Сегментация – это сложная слабо формализованная задача, достоверность решения которой оценивается эмпирически по адекватности зрительного восприятия или по результатам автоматического обнаружения заранее заданных объектов.
Любое изображение состоит из наборов пикселей, которые имеют такие визуальные свойства, как яркость, цвет, текстура. В рамках одного объекта либо же конкретной части объекта данные свойства практически не изменяются. Однако на границах объектов указанные свойства претерпевают изменения. Задача сегментации заключается в упрощении исходного изображения с целью последующего анализа для распознавания объектов интереса и их границ.
Результатом сегментации изображения является множество областей (регионов), которые полностью охватывают изображение, либо же набор контуров (границ), которые полностью охватывают изображение. В пределах одного региона пиксели имеют схожие характеристики либо вычисляемые свойства, такие, как цвет, интенсивность либо текстура. Соседние регионы, как правило, имеют сильные отличия по одним и тем же признакам. Главная сложность в процессе сегментации заключается в наличии дополнительных факторов, присущих изображениям: вариабельность фона, наличие шума на изображениях, разница между частями изображения.
Подходы к сегментации можно разделить на два класса: автоматические [1], не требующие участия пользователя, и интерактивные [2], использующие пользовательский ввод для уточнения непосредственно в процессе работы.
Методы и алгоритмы автоматической сегментации изображений не требуют взаимодействия с пользователем, подразумевают выделение регионов с известными свойствами или же сегментацию изображения на однородные регионы. Это разные задачи, поскольку в одном случае ведется поиск областей с известной априорной информацией, а в другом случае свойства регионов не известны, зато на разбиение изображения накладываются условия однородности.
Если априорная информация о свойствах регионов на изображении не используется, то соответствующие методы и алгоритмы сегментации применимы к любым изображениям и являются универсальными. Наиболее значимыми из этой группы методов и алгоритмов являются алгоритм k-средних, гистограммные методы [6], а также методы вейвлет-анализа на основе оценки фрактальной размерности изображений, методы выделения краёв, разрастания областей, разреза графа.
Алгоритм К-средних (k-means) предполагает быстрый кластерный анализ путем выделения К сегментов (кластеров), которые располагаются на максимальном расстоянии друг от друга [3]. Число кластеров К выбирается опираясь на результаты экспериментов либо интуитивно [4]. Идея алгоритма состоит в том, что центры кластеров соответствуют локальным максимумам плотности распределения данных. Базовый алгоритм K-средних предполагает случайный или эвристический выбор K центров кластеров, размещение каждого пикселя изображения в кластер с ближайшим центром к этому пикселю, после чего заново пересчитываются центры кластеров до сходимости процесса. Алгоритм гарантированно сходится, но не обязательно приводит к оптимальному решению, поскольку зависит от начального множества кластеров и значения K. Сложность алгоритма O(dTN2), где d – размерность изображения, N – число пикселей, T – число итераций алгоритма, причем dT N. К недостаткам алгоритма относится его чувствительность к шумам, снижение скорости работы на больших объемах данных, необходимость предварительно указать число кластеров К [5].
Важным моментом при решении задачи автоматической сегментации является вычисление признаков для оценки меры однородности областей сегментации изображения, если признаков яркости, цвета, градиента изображения недостаточно для хорошей сегментации изображения [7]. Известны попытки применения вейвлет-анализа на основе оценки фрактальной размерности изображений. Данный подход более подходит для обнаружения искусственных изменений ландшафта по фотографиям из космоса [8], или обнаружения искусственных объектов на изображениях, полученных с телекамер. Эксперименты показали, что подобного рода сегментация с использованием оценки фрактальной размерности в качестве одного из признаков дает хорошие результаты. Однако для рассматриваемого вида признаков не существует параметров, оптимальных для всех типов изображений и объектов [9]. К тому же не наблюдается явной зависимости результатов сегментации от характера применяемых вейвлет–функций, а признаки на основе фрактальной размерности из-за допущений в процедурах их оценки привносят определенные искажения в бинарное изображение (увеличение линейных размеров объектов, искажение их геометрической формы).
Оценка вычислительной сложности гибридного муравьиного метода
Число муравьев m влияет на вычислительную сложность метода. Ошибочно полагать, что чем больше муравьев, тем лучше. При большом количестве муравьев в колонии производительность значительно падает, поскольку сильно увеличивается время работы метода, происходит переизбыток феромонов, метод застревает на локальном оптимуме. При небольшом значении числа итераций nt0 метод может «не успеть» найти оптимальное решение. При бесконечном числе итераций вероятность нахождения глобального оптимума стремится к 1, но возникает вопрос о времени работы метода. Начальная концентрация феромона т0 , степень влияния феромона а и степень принадлежности пикселя определенному кластеру Р также оказывают непосредственное влияние на скорость поиска решений и сходимость к оптимуму. Для определения оптимальных значений параметров проведем экспериментальные исследования для разработанного гибридного муравьиного метода сегментации. Исследуем параметры m - число муравьев, а - степень влияния феромона и Р - степень принадлежности пикселя определенному кластеру, а также влияние начальных центров кластеров на выбор оптимального решения. Для тестирования метода сегментации используем набор известных сложноструктурированных изображений компании Ossirix [34]. Для исследования все снимки были поделены на несколько групп.
Особенностью рассматриваемого типа сложноструктурированных изображений, является то, что они не исключают ошибок в интерпретации полученных результатов, обусловленных, в основном, техническими особенностями метода диагностики. Данные ошибки в теоретической информатике принято называть артефактами. Артефакты – это погрешности, которые значительно ухудшают качество визуализации. Существует целый перечень побочных эффектов, которые существенно ухудшают качество графической картинки.
На всех изображениях в той или иной степени присутствуют разного рода артефакты, поэтому крайне важно понимать причины их появления и знать пути их частичного или полного устранения.
Некоторые артефакты сложноструктурированных изображений приводят к «размытым» снимкам, с нечеткими границами. Другие - к наличию шума на выходном снимке. Шум может быть как постоянным, так и случайным. Как правило, зашумленные изображения проходят этап предварительной фильтрации и шумоподавления (в разработанной программной реализации также предусмотрен данный этап – этап предобработки).
В случае правильного выполнения инструкций по проведению исследования и правильно откалиброванного и настроенного диагностического аппарата, снимки получаются хорошего качества и без обозначенных артефактов.
Особым видом сложноструктурированных изображений являются снимки с введением контрастного вещества, как правило, гадолиния. Данный вид снимков обладает определенной спецификой, благодаря «подсветке» интересующих исследователя участков организма человека, что делает снимок отличающимся от обычного состояния. Наличие приведенных выше факторов и возможных артефактов, позволяет классифицировать следующие группы исходных сложноструктурированных изображений: изображения хорошего качества (без наличия артефактов и прочих искажений); «зашумленные» изображения; «размытые» изображения; «контрастные» изображения.
Выделение данных групп имеет важное значение для процесса сегментации сложноструктурированных изображений, т.к. начальные условия оказывают существенное значение на весь процесс кластеризации изображения в целом, что требует исследования поведения методов для всех заданных начальных условий.
Исследование предусматривает моделирование поведения метода с различными вариантами параметров с целью определения влияния начальных параметров на общую сходимость метода, число итераций, близость найденного решения к оптимальному, степень идентичности результата обработки эталонному изображению.
Для проведения исследований было разработано несколько вспомогательных инструментальных средств, которые будут описаны в главе 4. Все результаты экспериментальных исследований сохраняются в СУБД Microsoft SQL Server. Это позволяет в последующем с помощью языка запросов SQL делать выборку решений по наиболее интересующим нас параметрам и на основании этого получать определенные зависимости и делать выводы.
План экспериментов включает следующие шаги: оценку качества работы метода сегментации; определение оптимальных параметров гибридного муравьиного метода; исследование изменения параметров метода при автоматической сегментации; исследование изменения параметров метода при масштабировании исходного изображения; исследование изменения параметров метода при интерактивной сегментации; экспериментальное определение коэффициентов а и Р; улучшение сегментации цветных изображений. Оценка качества работы метода сегментации.
Без количественных оценок невозможно определить оптимальную методику сегментирования аномальных объектов на сложноструктурированных изображениях, задать соответствующие параметры чувствительности методов поиска объектов, сделать вывод об информативности результата автоматизированной диагностики исследуемой патологии [75-76]. Качество работы методов сегментации изображений оценивается с помощью коэффициентов схожести (Similarity coefficient), чувствительности (Sensitivity coefficient), специфичности (Specifity coefficient) и точности сегментации (Segmentation accuracy). Проверка результатов автоматической сегментации обычно производится методом визуальной субъективной оценки экспертом. При проверке наиболее часто используются следующие свойства: однородность кластеров (однородность цвета или текстуры); непохожесть соседних кластеров; гладкость границы кластера; маленькое количество мелких «дырок» внутри кластера. Для сравнения методов интерактивной сегментации чаще всего применяют субъективное сравнение. С этой целью выбираются несколько изображений и пользователям ставится одна из двух задач: отсегментировать данным методом выбранные изображения не хуже заданного уровня, после чего измеряется, при каком методе на эту задачу ушло меньше всего времени; или за заданное время как можно лучше отсегментировать выбранные изображения, после чего субъективно оценивается, какой метод дал лучшую сегментацию.
Наиболее важным критерием качества сегментации является точность -степень соответствия результата работы метода эталонному стандарту сегментации для данного изображения. Для этого метод тестируется на общей базе изображений, для которых известна «правильная» сегментация. В качестве меры сходства результата сегментации с эталонным сегментированным изображением чаще всего используют коэффициент сходства (индекс) Жаккара [77], иногда - коэффициент Дайса [78].
Определение оптимальных параметров настройки гиперэвристического роевого метода
Частицы стремятся лететь непосредственно к позиции gbest самой успешной частицы. Данная социальная кооперация, помогает им обнаружить перспективные решения за довольно короткое время. Тем не менее, именно данное социальное взаимодействие, чаще всего приводит к попаданию в «яму» локального минимума. Как только находится новое значение gbest, это влияет на все частицы роя, которые устремляются к данной позиции. Процесс продолжается до тех пор, пока лучшее решение не будет найдено. Улучшение в эвристике Exponential PSO состоит в том, что значение со не остается постоянным. Оно уменьшается с каждой итераций от со = 0,9 до соmin = 0,4 на протяжении первых 150 итераций. Далее, если алгоритм все еще не сошелся, со рассчитывается как (max-/) 3 1 со = со- + 0.4 (.0) max где max - максимальное число итераций; / - номер текущей итерации.
Эвристика Exponential PSO влияет на исследование глобальных и локальных экстремумов. Процесс становится более быстрым и менее инертным, если инерционный вес со модифицировать и представить в экспоненциальном виде. Таким образом, модифицировав (3.10), движение частиц становится более быстрым и менее компактным. Таким образом, формула 3.10 модифицируется согласно [107]: (max—/) -( ) со = сое max +0.4 (3.11) Рассмотрим следующую подчиненную эвристику Elitist Exponential PSO (ЭЭРА), входящую в предлагаемый гиперэвристический роевой метод.
В эвристике PSO исходная популяция частиц размещается в случайных точках пространства изображения. Значение целевой функции рассчитывается, учитывая координаты частиц. В уравнении (3.6) г1 и г2 - нормально распределенные случайные числа. Если инерционный вес со небольшой, то существует вероятность преждевременной сходимости процесса [111]. Эвристика Elitist Exponential PSO (ЭЭРА) заключается в введении коэффициента темпа роста [5 для каждой частицы. Если значение целевой функции для частицы на t-й итерации больше, чем на (t-l) - й, тогда значение [5 увеличивается. После того, как значение pbest для всех частиц определено, обновляется текущее лучшее значение pbest. Значение gbest заменяется на pbest с наибольшим значением коэффициента [5. Шаги эвристики ЭЭРА схожи с шагами Exponential PSO, за исключением целевой функции.
В процессе сегментации, каждая частица х представляет К кластеров таким образом, что х.=(т.,...ж.,...ж) , где т представляет центр кластера / для I \ l1 , IJ , IK IJ J частицы /, Д. представляет темп роста частицы. Модифицированная фитнесс-функция выглядит следующим образом: f(X. , Z , Д.) = С01 flfmax(Z , X.) + & 2 Amax(Zmax min (Х/ )) (3. 12) где z max=2 — 1 для S-bit изображения, Z - матрица, отображающая связь между пикселем и центром кластера для частицы /. Каждый элемент этой матрицы z. показывает, принадлежит ли пиксель z кластеру С для частицы / , В /? у # max максимально допустимая степень роста. Эвристику ЭЭРА целесообразно применять для «контрастных» изображений. Входные данные аналогичны входным данным, используемым эвристикой PSO-K-means, но дополнительно необходимо использовать Дmax - параметр максимально допустимой степень роста. Ниже приводится пошаговое описание подчиненной эвристики. Шаг 1. Выбор количества частиц в рое т, личного и глобального коэффициентов ускорения с1 и С2, максимального количества итераций nt0 , максимально допустимой степени роста Дmax, определение границ для параметров поиска оптимума, параметров для целевой функции/, согласно (3.12); Шаг 2. Создать исходную популяцию пикселей (частиц) распределенных по пространству изображения S и инициализировать Д.; Шаг 3. Рассчитать значения пикселей на основе целевой функции (3.12); Шаг 4. Если текущий пиксель (текущая позиция частицы) лучше предыдущей, обновить ее (3.2). Также обновить значение Д. = Д. +1, если/3. Дmax; Шаг 5. Определить лучший пиксель (частицу) среди всех; Шаг 6. Обновить скорость пикселя согласно (3.6). Рассчитать pbest (3.4) и gbest (3.5) – лучшие глобальные и локальные решения частиц (пикселей); Шаг 7. Переместить частицу в новую позицию согласно (3.4); Шаг 8. Вернуться к шагу 3 до тех пор, пока не будет выполняться условие останова процедуры.
Особенность эвристики ЭЭРА заключается в расширении пространства поиска оптимума и в наличии механизма для предотвращения преждевременной сходимости метода, что, не позволяет упускать потенциально возможные лучшие решения [105 – 110].
Гиперэвристический роевой метод управляет представленными выше подчиненными эвристиками, исходя из особенностей сложноструктурированных изображений. С его помощью задача может решаться как единственной подчиненной эвристикой, так и с применением нескольких эвристик, каждая из которых сформирует частичное решение задачи. В последнем случае использование нескольких эвристик дает возможность компенсировать недостатки одних достоинствами других и, как следствие, получить лучшее решение, чем каждой из этих эвристик в отдельности. Другими словами, эффективность подчиненных эвристик форсируется при помощи использования гиперэвристики.
Сравнительная оценка времени работы методов сегментации изображений
На рисунке 4.20-а представлен снимок легких. Изображение сегментировалось на четыре кластера. На рисунке 4.20-б представлен результат обработки гибридным муравьиным методом, на рисунке 4.20-в – системой Ossirix. Результат сегментации на рисунке 4.20-б визуально представляется более качественным, нежели на рис. 4.20-в, т.к. были отделены контуры альвеол. На рис. 4.20 в данный фрагмент сливается с другой частью.
На рисунке 4.21-а представлен снимок черепа. Изображение сегментировалось на пять кластеров. Результаты сегментации на рис. 4.21-б и рис. 4.21-в являются схожими и пригодны для идентификации частей.
На рисунке 4.22-а представлен снимок легких. Изображение сегментировалось на четыре кластера. Результат сегментации на рисунке 4.22-б лучше, нежели на рис. 4.22-в, т.к. разработанному методу удалось лучше очертить контуры важных областей, что важно при анализе снимков.
На рисунке 4.23-а представлен снимок сердца. Изображение сегментировалось на четыре кластера. Результат сегментации на рисунке 4.23-б визуально представляется менее качественным, нежели на рис. 4.23-в, поскольку оказались не выделенными важные области на изображении, а некоторые области оказались частями других областей. Возможной, причиной неудачного результата является выбор неоптимальных значений параметров настройки для разработанного гибридного муравьиного метода.
Далее, проведено сравнение разработанного гибридного муравьиного метода с другими известными алгоритмами, в частности, с алгоритмом автоматической сегментации k-means [113] и алгоритмом интерактивной сегментации Magic Wand [2]. В качестве базы для сравнения алгоритмов использовались изображения из коллекции Ossirix [34]. Результаты сравнения были опубликованы в статьях [59 – 60].
Для корректного сравнения все изображения имели одинаковые характеристики: глубина цвета 8 бит; разрешающая способность 300 dpi; количество кластеров для разбивки – 5 (за исключением двух изображений, в которых число кластеров равно 4).
В качестве предварительной обработки выполнено шумоподавление (за исключением изображения на рис. 4.26). Для шумоподавления использован алгоритм «Размытие по Гауссу» с радиусом от 0,1 до 0,4 пикселей (исходные снимки практически не зашумлены). Оценивание качества сегментации производится сторонним наблюдателем, имеющим предварительные сведения об эталонной сегментации каждого изображения на снимке.
Например, на рисунке 4.24-а представлено исходное изображение маленькой менингиомы серпа в межполушарной щели, на рисунке 4.24-б – изображение после сегментации разработанным методом, на рисунке 4.24-в -изображение после сегментации алгоритмом k-means, на рисунке 4.24-г -изображение после сегментации алгоритмом Magic Wand.
Маленькая менингиома серпа в межполушарной щели: а – исходный снимок, б – сегментация гибридным муравьиным методом, в – сегментация алгоритмом k-means, г – сегментация алгоритмом Magic Wand Данное изображение сегментировалось на 5 кластеров. Особенность снимка в том, что контуры основных объектов на снимке очерчены, но подробная идентификация весьма затруднительна. В частности, данный снимок содержит едва различимую опухоль в центре. Различить эту опухоль без использования контрастного вещества практически невозможно. Сравнение результатов сегментации свидетельствует в пользу алгоритма k-means и разработанного гибридного муравьиного метода, причем результирующие контуры более явно выделены гибридным муравьиным методом. Алгоритм k-means, в отличие от гибридного муравьиного метода, осуществил неправильное соотнесение некоторых контуров, в частности, в верхней части снимков левые участки извилин соотнесены к разным кластерам.
Рассмотрим пример разновидности этого же снимка, но с использованием контрастного вещества. В качестве контрастного вещества использовался гадолиний. На рисунке 4.25-б представлено изображение после сегментации разработанным методом, на рисунке 4.25-в - изображение после сегментации алгоритмом k-means, на рисунке 4.25-г - изображение после сегментации алгоритмом Magic Wand.
Маленькая менингиома серпа в межполушарной щели с контрастным веществом: а - исходный снимок, б - сегментация гибридным муравьиным методом, в - сегментация алгоритмом k-means, г - сегментация алгоритмом Magic Wand Характеристики исходного изображения аналогичны изображению, представленному на рис. 4.24 на рисунках 4 и 5 идентичны. Размеры изображения - 800x600 пикселей.
Результат сегментации получился похожим на предыдущий пример. Но в данном случае, лучшим с точки зрения наблюдателя результатом является результат интерактивного алгоритма Magic Wand и гибридного муравьиного метода. Действительно, все контуры этими алгоритмами были четко выделены, и получилась правильная сегментация областей. Окружность в центре изображения - опухоль (невринома размером 1-2 см). Довольно часто сложноструктурированные изображения являются зашумленными. Например, на рисунке 4.26-а представлен снимок сердца с искусственным зашумлением, на котором присутствует средняя степень шума, а также результаты сегментации разработанным методом (рисунок 4.26-б), алгоритмом k-means (рисунок 4.26-в), алгоритмом Magic Wand (рисунок 4.26-г).
Снимок сердца с искусственным зашумлением: а - исходный снимок, б - сегментация гибридным муравьиным методом, в - сегментация алгоритмом k-means, г - сегментация алгоритмом Magic Wand Исходное изображение было зашумлено с помощью алгоритма равномерного шума. В качестве инструмента обработки использовался Adobe Photoshop, фильтр «Шум» с параметром «Эффект» равным 10%. Исходное изображение имеет размеры 500x300 пикселей. Производить сегментацию зашумленного изображения интерактивным методом довольно проблематично. Каждую область приходится сегментировать, используя определенный порог. В ходе эксперимента для отделения фона снимка использовался порог 100, для отделения областей интереса - различная комбинация уровней порогов - 72, 32, 20. Соответственно для отделения желудочков сердца использовались значения порогов от 5 до 15.
Что касается оценки результата, то для изображения на рисунке 4.26-а наилучший, с точки зрения наблюдателя, результат получен с помощью алгоритма k-means и гибридного муравьиного метода.