Факультет компьютерных наук и технологий
Кафедра автоматизированных систем управления
Специальность Информационные системы и технологии в технике и бизнесе
Обработка цифровых изображений является крайне важным процессом, который имеет широкий спектр применения, начиная от определения номера машины участника дорожного движения и заканчивая выявлением злокачественных новообразований в организме человека [1].
Сегментация – это процесс разделения чего-либо на составные части, между которыми существуют ярко выраженные отличия. В случае с цифровыми изображениями, сегментация – это процесс распределение пикселей изображения по группам, внутри которых сохраняется некоторый критерий схожести элементов. В свою очередь, между этими группами существует определенное отличие.
Сегментирование является одной из важнейших и наиболее трудоемких задач в области обработки цифровых изображений. На текущий момент существует значительное количество методов и алгоритмов сегментации, каждый из которых имеет свои сильные и слабые стороны. Основными принципами [2], на которых строятся алгоритмы сегментирования изображений являются:
Однако, не смотря на многообразие, универсального подхода не существует. Каждая область применения имеет свою специфику, из-за чего требования к алгоритму сегментирования значительно разнятся.
Современный уровень развития технологий в области компьютерной диагностики делает возможным предоставление оцифрованной визуальной информации высокого разрешения.
Повышение степени детальности изображения позволяет запечатлеть больший объем информации, что в ряде областей возымеет критическое значение. Пропорционально объему информации, растет и объем самих изображений. Это приводит к тому, что существующие методы обработки значительно теряют в эффективности. Такое положение дел способствует тому, что задача повышения быстродействия и эффективности алгоритмов сегментации изображения становится все более актуальной.
Возникает необходимость в поиске решения, которое обеспечило бы значительный прирост производительности методов сегментирования изображений.
Выпускная квалификационная работа посвящена решению задачи повышения эффективности и производительности алгоритмов сегментации изображений. Для нахождения решения предполагается использование роевых алгоритмов на аппаратной базе современных GPGPU [3]. В качестве программной платформы выступит стандарт параллельных вычислений OpenCL [4], а также кроссплатформенный объектно-ориентированный язык программирования высокого уровня Java [5].
Целью проводимых исследований является разработка инструментальных средств параллельной сегментации трехмерных изображений с использованием методов роевого интеллекта. Основные задачи исследования:
Объект исследования: методы сегментации цифровых изображений.
Предмет исследования: параллельная сегментация изображений сприменением роевых алгоритмов.
В рамках выполнения выпускной квалификационной работы магистранта предполагается получение теоретических результатов по следующим направлениям:
Для получения экспериментальной оценки теоретических результатов необходимо разработать инструментальные средства сегментации.Разработка предусматривает следующие шаги:
Тема сегментации цифровых изображений не является новой. На текущий момент существует множество методов и алгоритмов, многие из которых себя хорошо зарекомендовали. Значительная часть существующих подходов разработана и представлена университетами Европы, США, а также ведущих стран Азии и Южной Америки.
Методы сегментирования, использующие алгоритмы кластеризации, на текущий момент являются классическим
решением задачи обработки изображений. Ярким примером современного варианта применения таких алгоритмов
является метод, представленный М. Алмазруи в статье GPU-based fuzzy C-means clustering algorithm for
image segmentation
[6]. Объектом эксперимента стал набор медицинских изображений головного мозга человека.
Алгоритм сегментации выполнялся параллельно, аппаратной платформой выступил современный GPGPU NVIDIA Tesla C2050.
Программной основой стал стандарт параллельных вычислений CUDA.
При сохранении приемлемого уровня качества исходного результата,
распараллеливание обеспечило 674-кратное ускорение, в сравнении с последовательным выполнением алгоритма.
Полученные результаты явно указывают на перспективность использования параллельных вычислений.
Более инновационным решением задачи сегментации может стать применение эвристических алгоритмов.
Статья Parallel particle swarm optimization for image segmentation
[7] за авторством А. Кристиади
демонстрирует использование алгоритма роя частиц (PSO) для сегментирования изображения с применением
кластеризации. При проведении эксперимента также использовались технологии параллельных вычислений CUDA.
Результаты эксперимента показали, что, при небольшом объеме входной информации, распараллеливание себя не оправдывает, и последовательная реализация демонстрирует лучший результат. Однако, с ростом уровня качества и объема изображения, ситуация в корне меняется, и параллельная версия алгоритма показывает 1.7-кратный прирост производительности. Это связано с тем, что применении параллелизма также требует определенных ресурсов, объем которых нивелируется при обработке более крупных массивов данных.
В статье И. Чжу GPU accelerated fuzzy connected image segmentation by using CUDA
[8] приводится описание
распараллеливания алгоритма сегментации, в основе которого лежит метод нечетких связностей.
Объектом эксперимента выступили изображения томографии головного мозга здорового человека. Результаты проведения эксперимента показали, что, в сравнении с последовательной версией алгоритма, распараллеливание дало 14.4-кратный прирост в скорости выполнения. Примечательным является тот факт, что эффективность параллелизма возрастает при работе с объемом данных большего размера.
Другим, достаточно популярным и хорошо себя зарекомендовавшим, является метод сегментации с
использованием алгоритма разрастания областей. В статье П. Н. Хаппа A Parallel region growing algorithm
for image segmentation on GPUs
[9] описывается применение распараллеленной версии данного алгоритма для
сегментирования изображения.
В процессе реализации алгоритма, автор столкнулся с необходимостью решения некоторых нетривиальных задач, связанных со структурой памяти современных GPU. Процесс разрешения возникших проблем очередной раз подтвердил необходимость понимания и учета специфики аппаратной платформы GPU для ее успешной эксплуатации.
Результаты эксперимента показали отсутствие значительной разницы в качестве результата сегментации при помощи исходной и модифицированной в угоду параллелизму версий алгоритма. Кратность ускорения в сравнении с последовательным выполнением на CPU варьируется от 1.38 до 6.86, она повышается при увеличении объема обрабатываемой визуальной информации.
В статье П. Ф. Фельзенцвальба Efficient graph-based image segmentation
[10] представлен метод сегментации
изображения с использованием алгоритма разбиения графа.
Результаты эксперимента показали производительность и гибкость представленного метода сегментирования. Несмотря на то, что алгоритм был представлен достаточно давно, он до сих пор остается производительным, эффективным и способен выдавать удовлетворительны результат при небольших временных затратах.
Публикация Использование пчелиных алгоритмов для решения комбинаторных задач
[11] за авторством
В. М. Курейчика демонстрирует использование разных алгоритмов для нахождения решения комбинаторной
задачи разбиения графа.
Результаты выполнения экспериментов показали, что роевые эвристические алгоритмы на порядок лучше справляются с поставленной задачей. При этом, муравьиный алгоритм лучше подходит для решения небольших задач, а алгоритм пчелиной колонии показывает более высокую эффективность при увеличении объема входных данных.
В публикации В. В. Курейчика Роевой алгоритм в задачах оптимизации
[12] приводится описание работы алгоритма,
основанного на поведении колонии медоносных пчел, при решении оптимизационных задач проектирования.
В публикации приведена оценка временной сложности алгоритма, его математическая модель, а также описание нахождения оптимума целевой функции с его использованием.
В заключении дается утверждение о способностях алгоритма к распараллеливанию и получению оптимальных и квазиоптимальных решений.
На кафедре автоматизированных систем управления (АСУ), факультета компьютерных наук и технологий
Донецкого национального технического университета проводятся исследования и разработки в области
эвристических алгоритмов. Примером значимых работ может служить монография Метаэвристики
за авторством Ю.А. Скобцова и Е.Е. Федорова [13].
Среди магистрантов кафедры АСУ проводились исследования и разработки в области применения эвристических
алгоритмов к задаче сегментации изображений. Примером результатов таких исследований стала выпускная
квалификационная работа магистранта С.А. Эль-Хатиба Компьютерная система сегментации медицинских изображений
на основе алгоритма муравьиных колоний
[14], а также его публикация уже в качестве аспиранта
Компьютерная система сегментации медицинских изображений методом роя частиц
[15].
Основой метода [16] является представление изображения в виде графа, в котором вершины – это пиксели изображения. Длина ребер между вершинами определяется разностью характеристик двух соседних пикселей, на основании которых осуществляется сегментация. Значение длины ребра рассчитывается по формуле (1):
Начальный этап алгоритма предполагает сравнение пикселей с 4 (северный, южный, западный, восточный) или 8 соседними (добавляются промежуточные). Такой подход позволяет сделать выбор в пользу производительности или же качества конечного результата. После прохождения данного этапа будет получено большое количество разрозненных сегментов. Далее, согласно критерию (2) происходит объединение этих сегментов:
Рис. 1. Объединение сегментов
На практике, при программной реализации данного алгоритма, более эффективным подходом будет обработка массива ребер графа, отсортированных по возрастанию их веса. Каждое ребро проходит проверку н возможность объединения сегментов, которые оно соединяет. Следует понимать, что на начальном этапе каждый пиксель представляет свой сегмент.
Данный алгоритм хорошо масштабируем и позволяет определять конечный результат, основываясь на текущих приоритетах в сторону повышения качества и, как следствие, трудоемкости, или же в сторону повышения производительности с сохранением минимально приемлемого качества результата сегментации.
Помимо уже указанной возможности регулирования количества ребер в графе, существует способ модификации расчетной формулы разности пикселей (3):
Переменные в данной формуле определяются тем, что в качестве расчетной характеристики пикселей при сегментировании взяты значения цветовой модели RGB. Помимо них, в формулу добавлены координаты пикселя в трех плоскостях (речь идет о трехмерных изображениях).
Это лишь один из вариантов структуры расчетной формулы. Гибкость выбранного алгоритма предоставляет возможность выбора оптимальных характеристик пикселей, которые позволят выполнить высококачественную сегментацию исходя из оценки параметров исходного изображения. Следовательно, не исключается задействование дополнительных моделей, которые позволят провести эффективную оценку исходного изображения и на ее основании определить значения, которые будут использоваться при сегментировании.
На текущем этапе выполнения выпускной квалификационной работы предполагается [17] использовать роевой алгоритм для эффективного распределения мощностей выбранной аппаратной базы.
Природа алгоритма пчелиной колонии подразумевает его выдающийся уровень эффективности при выполнении задачи распределения имеющихся трудовых ресурсов, которыми в данном случае выступают вычислительные элементы графического ускорителя, способные выполнять различные поставленные задачи параллельно.
Оптимизация распределения нагрузки с использованием алгоритма пчелиной колонии требует предварительной оценки объема и некоторых других критериев входной информации.
Основой представляемого подхода является распределение пикселей исходного изображения на некоторое количество блоков по определенному критерию. Для каждого такого блока, по формуле (4), будет рассчитано количество выделенных вычислительных элементов:
В рамках каждого блока, выделенные элементы следует разделить на фактические рабочие группы, размер которых определяется спецификациями выбранной программной платформы распараллеливания, а также физической структурой текущей аппаратной базы.
Ключевые моменты описываемого метода сегментации изображений могут быть схематически представлены следующим образом (рис. 2):
Рис. 2. Алгоритм сегментации (Анимация: 133 кб, 8 кадров, неогр. число повторений)
Предполагается, что программной основой распараллеливания представленного алгоритма выступит универсальный кроссплатформенный стандарт параллельных вычислений OpenCL. Среди ведущих стандартов в сфере параллельных вычислений (CUDA, OpenCL, OpenMP и др.), выбранный отличается кроссплатформенностью и легкостью интеграции в различные системы, при этом отставание в производительности от основного конкурента в лице CUDA незначительно и с выходом новых версий стандарта становится все меньше [18].
На текущий момент, реализована последовательная версия алгоритма, сегментирующая двумерные медицинские изображения МРТ, размером 512 на 512 пикселей. Программная реализация обеспечена средствами платформы Java.
При проведении эксперимента, сегментация изображения осуществлялась несколькими версиями алгоритма (с использованием 4-ех связного и 8-ми связного графа) при разных значениях аргумента k. Результаты замеров времени приведены в таблице 1.
| № | Связность графа | k | Затраченное время, сек |
|---|---|---|---|
| 1 | 4 | 300 | 31,188 |
| 2 | 4 | 3000 | 27,438 |
| 3 | 4 | 30000 | 30,971 |
| 4 | 8 | 300 | 35,094 |
| 5 | 8 | 3000 | 34,693 |
| 6 | 8 | 30000 | 35,024 |
Результаты эксперимента говорят о том, что, на данном этапе реализации алгоритма, использование 4-ех связного графа не дает значительного преимущества в скорости выполнения. При этом, с субъективной точки зрения, 8-ми связный граф обеспечивает более высокий уровень качества конечного результата. На рис. 3 представлена исходное изображение, которое использовалось при проведении эксперимента.
Рис. 3. Исходное изображение
На рисунках 4(а) и 4(б) представлены результаты сегментации изображений при значении k = 3000.
Рис. 4. Результаты сегментации
Выпускная квалификационная работа магистранта посвящена исследованиям методик сегментации изображений и разработке инструментальных средств параллельного сегментирования, которые в перспективе позволили бы снизить трудоемкость разработки систем, имеющих в своей основе модули обработки медицинских цифровых изображений.
На текущем этапе выполнения работы обеспечено достижение следующих целей:
Дальнейшим направлением исследований и разработки будет:
На момент написания реферата, магистерская работа не завершена. Окончательное завершение планируется в мае 2018 года. Полный текст работы и материалы по теме могут быть получены у магистранта или его научного руководителя не ранее указанной даты.