Параллельная сегментация трехмерных изображений на основе алгоритма разбиения графа с применением роевого интеллекта

Авторы: Казанцев М.А., Привалов М.В.

Источник: М.А. Казанцев Параллельная сегментация трехмерных изображений на основе алгоритма разбиения графа с применением роевого интеллекта / М.А. Казанцев, М.В. Привалов // Сборник статей студенческой научно-технической конференции «В мире компьютерных технологий» – Севастополь, 2017 – С.43-47.

Аннотация

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

Ключевые слова: сегментация, разбиение графа, алгоритм пчелиной колонии, распараллеливание, OpenCL.

Abstract

Article describes the parallel 3D image segmentation algorithm based on the swarm intelligence implementation of the graph cut approach. The idea of this method lays in the image representation as a graph, where pixels define graph’s vertices with the edges’ weights dependent on a pixels similarity. Implementation of the algorithm is directed towards an increase of the segmentation performance by means of the bee colony swarm intelligence methods parallelization with the help of the open GPU programming standard OpenCL.

Keywords: segmentation, graph cut, artificial bee colony algorithm, parallelization, OpenCL.

Введение

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

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

1. Анализ существующих методов решения

В настоящее время существует значительное количество методов сегментации, которые показали свою эффективность, однако, применяемые в них алгоритмы сегментации разрабатывались в условиях, когда необходимость работы с большими объемами данных отсутствовала, и, как следствие, они значительно теряют в эффективности и быстродействии при увеличении объема входной информации. Это делает актуальным создание таких средств сегментации, которые хорошо бы себя показали в работе с более «тяжелыми» изображениями, а также в лучшей степени реализовали технические и программные возможности современных вычислительных платформ. Спиральная томография (СКТ) и конусно-лучевая компью-терная томография (КЛТ) являются распространёнными методами диагностики, поэтому прикладной задачей, на примере которой возможно проводить исследования подходов к распараллеливанию методов обработки изображений, может стать сегментация 3D СКТ изображений.

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

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

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

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

Ключевые принципы алгоритма пчелиной колонии [3]:

1. Результаты работы пчел-разведчиков определяют наиболее перспективные места для поиска нектара.
2. Соответственно уровню их «перспективности», на каждый участок отправляется не-которое количество пчел-рабочих.
3. Рабочие собирают нектар, попутно уточняя информацию разведчиков о количестве нектара в некотором радиусе от изначального участка.

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

Следует отметить, что при увеличении размерности графа до 1000 вершин, разрыв в пользу алгоритма пчелиных колоний увеличивается [4].

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

2. Сегментация изображения методом разбиения графа

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

На начальном этапе выполнения алгоритма происходит сравнение пикселей изобра-жения с 4 соседними (северный, южный, западный, восточный) [5]. После этого, будет по-лучено большое количество разрозненных сегментов, которые, по возможности, следует объединить. Критерием объединения отдельных сегментов является выполнение условия (2):

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

Другой особенностью такого подхода является хорошая масштабируемость алгоритма разбиения графа. Благодаря этому, при наличии достаточно мощного аппаратного обеспечения есть возможность повысить качество конечного результата путем увеличения количества ребер в графе. На начальном этапе алгоритма сегментации будет происходить сравнение пикселей с 8 соседними вместо 4 (добавляются северо-западный, северо-восточный, юго-западный, юго-восточный пиксели). Такие изменения повлекут за собой значительное увеличение вычислительной нагрузки, однако, вместе с тем возрастет качество конечного результата. Помимо этого, исследования показали наличие возможности модификации способа расчета длины ребер путем добавления в формулу не только спектральных, но также и пространственных характеристик пикселей [5], что даёт в результате (3):

3. Сегментация изображения методом разбиения графа с использованием алго-ритма пчелиной колонии

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

В данном случае понятие «пчелы» исходит из специфики архитектуры современных ускорителей вычислений, которая представляет из себя совокупность аппаратных и программных элементов, способных выполнять различные задачи параллельно, тем самым значительно сокращая временные затраты. Например, в рамках применения массивно-параллельных вычислений на видео- и специализированных ускорителях пчелой может считаться одна нить вычислений или рабочий элемент. Среди существующих платформ распараллеливания графических и массивно-параллельных вычислений платформа OpenCL [6] основана на универсальном и открытом стандарте, в связи с чем в данной работе предлага-ется адаптировать параллельный алгоритм именно к реализации на ней.

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

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

Число пчел для каждого блока пикселей определяется по формуле (4) [3]:

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

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

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

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

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

Закдючение

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

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

Список источников

1. Метаэвристики: монография / Ю.А. Скобцов, Е.Е. Федоров. – Донецк: Изд-во «Ноу-лидж» (Донецкое отделение), 2013 – 426 с.
2. Курс «Эволюционные вычисления», лек.11 «Роевые и муравьиные алгоритмы» (Д.В. Сперанский, Ю.А. Скобцов; НОУ «ИНТУИТ»), 2014.
3. Роевой алгоритм в задачах оптимизации (В.В. Курейчик, Д.Ю. Запорожец; «Известия ЮФУ. Технические науки»), 2010.
4. Использование пчелиных алгоритмов для решения комбинаторных задач (В.М. Ку-рейчик, А.А. Кажаров; Технологический институт Южного федерального университета, г. Таганрог, Россия; persianland1987@gmail.com, kur@tsure.ru), 2010.
5. Efficient Graph-Based Image Segmentation (by Pedro F. Felzenszwalb (MIT) and Daniel P. Huttenlocher; Cornell University), 2004.
6. An Introduction to the OpenCL Programming Model (by J. Tompson and K. Schlachter; NYU: Media Research Lab; tompson@cims.nyu.edu, ks228@cs.nyu.edu), 2012.