Рус Eng Cn Перевести страницу на:  
Please select your language to translate the article


You can just close the window to don't translate
Библиотека
ваш профиль

Вернуться к содержанию

Кибернетика и программирование
Правильная ссылка на статью:

Оптимизация параметров биоинспирированной гиперэвристики в задаче сегментации изображений

Родзин Сергей Иванович

кандидат технических наук

профессор, Южный федеральный университет

347928, Россия, Ростовская область, г. Таганрог, ул. Чехова, 80-1

Rodzin Sergey Ivanovich

PhD in Technical Science

Professor, Department of Software and Computer Usage, Southern Federal University

347928, Russia, Rostovskaya oblast', g. Taganrog, ul. Chekhova, 80-1

srodzin@yandex.ru
Другие публикации этого автора
 

 
Эль-Хатиб Самер Аднан

соискатель, кафедра математического обеспечения и применения ЭВМ, Южный федеральный университет

83076, Украина, Донецкая область, г. Донецк, ул. Я. Галана, 48

El'-Khatib Samer Adnan

Applicant, Department of software and the use of computers, Southern Federal University

83076, Ukraine, Donetskaya oblast', g. Donetsk, ul. Ya. Galana, 48

samer_elkhatib@mail.ru

DOI:

10.7256/2306-4196.2016.5.18507

Дата направления статьи в редакцию:

27-03-2016


Дата публикации:

29-01-2017


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


Ключевые слова:

сегментация изображений, гиперэвристика, алгоритм роя частиц, алгоритм k-средних, пиксель, кластер, оптимизация, расстояние, эксперимент, моделирование

Abstract: The subject of study is a new segmentation algorithm that allows improving the quality and speed of image processing in comparison with known algorithms. The authors consider the problem of segmentation of medical images and existing approaches to its solution. It is noted that segmentation is the most difficult part in the processing and analysis of medical images of biological tissue, since it is necessary select areas that correspond to different objects or structures on histological specimens: cells, organelles and artifacts. Particular attention is paid to algorithms of particle swarms and k-means. In solving the problem, authors use swarm intelligence methodology, cluster analysis, the theory of evolutionary computation, mathematical statistics, computer modeling and programming. The article suggests a new hyper-heuristic algorithm and its modification to solve the problem of segmentation of medical images in order to improve image quality and processing speed. Authors present experimental results obtained on the basis of test data from a known set of medical MRI images using the software developed by the authors. The optimal values of coefficients that determine the behavior and efficiency hyper heuristics that reduces the number of iterations of the algorithm are defined. The results demonstrate the advantage and confirm the efficiency of hyper heuristics algorithms in systems of digital medical imaging solutions to the problem of segmentation of medical images.


Keywords:

segmentation images, hyper heuristics, particle swarm algorithm, k-means algorithm, pixel, cluster, optimization, distance, experiment, modeling

Введение

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

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

К наиболее известным алгоритмам автоматической сегментации относятся фильтры Робертса, Собеля, Превитта, Кэнни, гистограммные методы, методы теории графов. В последнее время стало ясно, что автоматические алгоритмы не способны решать произвольные задачи сегментации с гарантированным по точности результатом. Начиная с 2000-х гг., наибольшее внимание исследователей уделяется интерактивным методам сегментации, большая часть которых являются развитием методов GraphCut [6] и GrabCut [7]. В методе GraphCut пользователь указывает несколько пикселей, принадлежащих фону и несколько пикселей, принадлежащих объекту. Метод трактует всё изображение, как граф. Сегментация осуществляется с помощью нахождения минимального разреза графа. В GrabCut пользователь задает ограничивающий прямоугольник вокруг объекта. Исходя из цветового распределения внутри и снаружи ограничивающего прямоугольника, строится первая цветовая статистика объекта и фона. В качестве цветовой модели используется смесь гауссиан с заданным количеством компонент. Затем поочередно производится сегментация и уточнение цветовой статистики. После каждого уточнения цветовой статистики, граф (в котором ищется минимальный разрез) перевзвешивается. Оба этих метода достаточно качественно сегментируют объекты, однако имеют относительно низкое быстродействие. Реализация обеих методов представлена в известной библиотеке алгоритмов обработки изображений OpenCV [8].

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

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

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

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

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

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

Для получения более эффективного результата предлагается использовать гиперэвристику – подход, направленный на автоматизацию процесса выбора, комбинирования, обобщения или адаптации нескольких более простых эвристических алгоритмов (или их частей) для эффективного решения задачи.Гиперэвристики – это относительно новый тип алгоритмов, в которых для получения результата используется набор простых однопроходных эвристик управляемых общей схемой [10].Идея состоит в разработке подхода, позволяющего комбинировать несколько известных эвристик, усиливая их достоинства и компенсируя слабости.

Для решения задачи сегментации медицинских изображений в [11, 12] были предложены модифицированные алгоритмы роя частиц и муравьиных колоний. Проведенные экспериментальные исследования показали, что результаты сегментации медицинских изображений могут быть улучшены при использовании гиперэвристики PSO-k-means, которая представляет собой композицию алгоритмов роя частиц иk-средних. Однако это улучшение результатов сегментации изображений достигается путем исследования и выбора оптимальных параметров алгоритмов, входящих в гиперэвристику, таких как число частиц в рое и коэффициенты ускорения частиц.

В основе предлагаемой гиперэвристики лежит алгоритм роя частиц (ParticleSwarmOptimization, PSO), который был доказан Р. Эберхартом, Ю. Ши, Дж. Кеннеди [13], Р. Поли [14] и первоначально предназначался для имитации социального поведения роя (птиц в стае, рыб в косяке и др.). Известно, что всякого рода роевые объединения играют важную роль в повышении эффективности поиска ими пищи, защиты от хищников, а также в уменьшении энергетических затрат. Обнаружены базовые принципы синхронного поведения роя, меняющего как по команде направление своего движения и перемещающегося как единое целое.

Алгоритм PSO показал свою конкурентоспособность при решении многих NP-полных трансвычислительных задач [15, 16]. Он был упрощен для выполнения численной оптимизации функций путем поддержки возможных решений-частиц, перемещаемых в пространстве согласно простой формуле по принципу поиска наилучшего положения. При определении следующего положения частицы учитывается информация о наилучшей частице из числа ее соседей, а также информация о данной частице на той итерации алгоритма, на которой этой частице соответствовало наилучшее значение целевой функции. Таким образом, каждая частица роя подчиняется правилам поведения, которые учитывают локальный успех каждой частицы и глобальный оптимум всех частиц (или некоторого множества соседей) роя.

Отметим, что PSO-алгоритм имеет много общего с генетическим алгоритмом (ГА): оба являются алгоритмами случайно-направленного поиска, начинают работать со случайно сгенерированной популяцией решений и рассчитывают свои целевые функции, выполняя в процессе эволюции поиск лучшего решения. Однако в PSO-алгоритме нет генетических операторов, подобных кроссинговеру и мутации, а потенциальные решения-частицы имеют память, взаимодействуют и изменяют свои скорости. Кроме того, механизмы передачи информации в ГА и PSO-алгоритме совершенно различны. В ГА хромосомы обмениваются информацией (генами) друг с другом, поэтому вся популяция движется как единая группа в область оптимума. В PSO-алгоритме только информация о глобально лучшей координате среди всех частиц передается другим частицам, поэтому в большинстве случаев все частицы стремятся к лучшему решению быстрее, нежели в ГА. Также преимущество PSO-алгоритма перед ГА заключается в том, что для его реализации необходимо определять только значение целевой функции, и он имеет меньше параметров управления, чем ГА. Таким образом, логично сделать вывод о целесообразности применения PSO-алгоритма в гиперэвристике для решения задачи сегментации медицинских изображений.

Пусть n – количество параметров, подлежащих оптимизации, x1, x2,…, xn – параметры оптимизации.

Пусть f (x): RnR – целевая функция в n-мерном пространстве, которую требуется минимизировать:

f1

При реализации PSO-алгоритма n-мерное пространство поиска населяется роем из m частиц в рое (размер популяции элементарных решений). Координата i-й частицы (i ϵ [1:m]) задается вектором , который определяет некоторый набор параметров оптимизации. В процессе инициализации роя частицы случайным образом располагаются по всей области поиска. При этом каждая i-я частица имеет свой собственный вектор скорости vi ϵ Rn , которая в каждый конкретный момент времени, соответствующий некоторой итерации PSO-алгоритма, определенным образом влияет на значения координат позиции i-й частицы. Координаты позиции i-й частицы в n-мерном пространстве поиска однозначно определяют значение целевой функции f(xi) = f(x1, x2,…, xn).

Для каждой позиции n-мерного пространства поиска, в котором побывала i-я частица, вычисляется значение целевой функции f(xi). При этом каждая i-я частица запоминает свое лучшее значение целевой функции, а также координаты позиции в n-мерном пространстве, соответствующие этому значению целевой функции. Кроме того, каждая i-я частица «знает», где расположена позиция, являющаяся лучшей (в смысле формулы (1)) среди всех позиций, в которых уже побывали остальные частицы. Благодаря этому обеспечивается мгновенный обмен информацией между всеми частицами.

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

Сходимость PSO-алгоритма зависит от того, каким образом выполняется коррекция вектора скорости частиц. Известны различные подходы к выполнению коррекции вектора скорости

В классической версии PSO-алгоритма коррекция каждой j-йкоординаты вектора скорости (j ϵ [1:n]) i-й частицы выполняется в соответствии с формулой [13]:

f2

где vijj-я координата вектора скорости i-й частицы; xijj-я координата вектора xi, задающего позицию i-й частицы; yijj-я координата вектора лучшей позиции, найденного i-й частицей за время ее существования; y*jj-я координата глобально лучшей позиции всего роя частиц, в которой целевая функция имеет оптимальное значение; rpи rg – случайные числа на интервале (0,1); cpи cg– личный и глобальный коэффициенты ускорения частиц, являющиеся константами и определяющие поведение и эффективность PSO-алгоритма в целом. С помощью коэффициентов ускорения cpи cg масштабируются случайные числа rpи rg. При этом глобальный коэффициент ускорения cg управляет воздействием глобальной лучшей позиции на скорости всех частиц, а личный коэффициент ускорения cp – – воздействием личной лучшей позиции на скорость некоторой частицы.

Довольно часто при выполнении коррекции вектора скорости vi используется модификация формулы (2):

f3

в которой перед j-й координатой вектора скорости i-й частицы добавлен множитель w – весовой коэффициент инерции, благодаря чему скорость изменяется более плавно.

Далее для каждой i-й частицы (i ϵ [1:m]) рассчитывается новое значение целевой функции f (xi) и выполняется проверка: не стала ли новая позиция с вектором координат xi лучшей среди всех позиций, в которых i-я частица ранее побывала. Если новая позиция i-й частицы признается лучшей на текущий момент времени, то информация о ней сохраняется в векторе yi с «запоминанием» значения целевой функции f (xi) в этой позиции.

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

При реализации гиперэвристики, наряду с модифицированным PSO-алгоритмом, используется известный алгоритм k-means [17]. Это один из наиболее популярных алгоритмов кластеризации без обучения, целевой функцией которого является минимизация суммарного квадратичного отклонения точек кластеров от центров этих кластеров:

f4

где K – число кластеров, Clk – полученные кластеры, k ϵ [1:K], hk – центры масс векторов xi ϵ Clk. Основная идея алгоритма k-means заключается в том, что на каждой итерации перевычисляется центр масс для каждого кластера, полученного на предыдущем шаге, затем векторы вновь разбиваются на кластеры в соответствии с тем, какой из новых центров оказался ближе по выбранной метрике. Первоначально выбираются K случайных центров кластеров. Алгоритм завершается, когда на какой-то итерации не происходит изменения центра масс кластеров. Завершение работы k-means происходит за конечное число итераций, так как количество возможных разбиений конечного множества конечно, а на каждом шаге суммарное квадратичное отклонение (4) не увеличивается, поэтому зацикливание невозможно. Временная сложность алгоритма k-means невысокая – O(m), что делает его пригодным задач большой размерности. Однако при этом не гарантируется достижение глобального минимума суммарного квадратичного отклонения (4), а результат зависит от выбора исходных центров кластеров, число которых надо знать заранее.

Гиперэвристический алгоритм сегментации медицинских изображений

Для получения более точного результата в задаче сегментации медицинских изображений предлагается гиперэвристический алгоритм PSO-k-means, использующий композицию из PSO-алгоритма и алгоритма k-means. Гиперэвристика заключается в том, что вначале для сегментации применяется модификация PSO-алгоритма, которая позволяет приблизиться к оптимальному решению, но показывает медленную сходимость вблизи оптимума. Затем полученное решение используется в качестве исходного для алгоритма k-means. Аналогичный подход использовался в [18, 19] для задачи распознавания изображений, полученных цифровыми камерами.

Отличие предлагаемого гиперэвристического PSO-k-means алгоритма от аналогов состоит в следующем. В алгоритме PSO-k-means каждая частица xi является центром hik кластера Clk: xi= (hi1,…,hik,…,hiK). Поэтому рой из m частиц представляет собой множество кандидатов на роль центров K кластеров. Целевая функция является многокритериальной, а ее значение для каждой частицы определяется следующим образом:

f5

где qmax – максимальное значение в наборе данных цифрового s-битового изображения (qmax =2s–1); Q – матрица, отображающая связь между пикселем и центром кластера для частицы i. Каждый булевский элемент этой матрицы указывает на принадлежность пикселя qp кластеру Clk для частицы i. Константы w1 и w2 – весовые значения каждого критерия, которые определяются пользователем; dmax – максимальное среднее евклидово расстояние от частиц до связанных с ними кластеров, которое вычисляется согласно выражению:

f6

где ni,k – число пикселей частицы i, принадлежащих к кластеру Clk ; dmin(xi) – минимальное эвклидово расстояние между любой парой кластерных центров, которое вычисляется согласно выражению:

f7

Целевая функция (5) одновременно минимизирует внутрикластерные расстояния между пикселями и их кластерными центрами, и максимизирует расстояния между любой парой кластеров. Иными словами, целевая функция предполагает выделение компактных и хорошо разделенных кластеров. Таким образом, для получения оптимального решения используется аддитивная скаляризация с весовыми значениями w1 и w2 для каждого из критериев, задаваемых пользователем.

Ниже приводится пошаговое описание предлагаемого гиперэвристического алгоритма PSO-k-means.

Ш а г 1. Выбор количества частиц в рое m, личного и глобального коэффициентов ускорения cpи cg, максимального количества итераций Nmax, определение границ для параметров поиска оптимума, параметров для целевой функции f, согласно (5).

Ш а г 2. For i= 1,…, m (цикл по количеству частиц в рое)

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

2.2 Начальное положение частицы принять за ее лучшее известное положение yi=xi.

2.3 Если f(yi) < f(y*), то обновить наилучшее известное состояние роя, заменив y* на yi.

2.4 Случайная инициализация скоростей частиц vi.

Ш а г 3. Текущее количество итераций N = 1.

Ш а г 4. For i = 1,…, m (цикл по количеству частиц в рое)

Ш а г 5. For j= 1,…, n (цикл по количествупараметров целевой функции)

5.1 Сгенерировать случайные числа rpи rg ϵ (0, 1).

5.2 Обновить скорость частицы vij.

5.3 xij = xij + vij.

Ш а г 6. Если f(xi)<f(yi), то обновить лучшее известное положение частицы yi =xi, иначе переход к п. 4.

Ш а г 7. Если f(xi)<f(y*), то обновить лучшее состояние роя y* = xi, иначе переход к п. 4.

Ш а г 8. Текущее количество итераций N = N + 1.

Ш а г 9. Если текущее количество итераций N <= Nmax, то переход к п. 4, иначе y* содержит лучшее из найденных решений.

Ш а г 10. В соответствии с найденным решением инициализировать число кластеров K и их центры в соответствии с найденными модифицированным PSO алгоритмом лучшими позициями частиц.

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

Ш а г 12. Рассчитать новые центры кластеров согласно (5). Если они не совпадают с предыдущими, то переход к п. 11.

Ш а г 13. Сохраняем лучшее решение для каждой частицы.

Ш а г 14. Сохраняем лучшее решение среди всех m частиц.

Ш а г 15. Обновляем кластерные центры согласно полученным решениям.

Ш а г 16. Если произошли изменения в кластерах, то переход к п. 12.

Ш а г 17. Конец.

Гиперэвристический алгоритм PSO-k-means может быть улучшен. Выше отмечалось, что множитель w в формуле (3) влияет на баланс между размерами поискового пространства и вниманием к найденным субоптимальным решениям. Если этот множитель больше 1, то скорости частиц увеличиваются, они разлетаются в стороны и исследуют пространство поиска оптимума более тщательно. Иначе, скорости частиц со временем уменьшаются, и скорость сходимости зависит от выбора значений коэффициентов ускорения частиц cp и cg. Таким образом, большие значения коэффициента инерции способствуют исследованию пространства поиска, а малые – локализации решения. В [20] предлагалось линейно изменять множитель `Omega`от некоторого максимального значения `omega` max до некоторого минимального значения `Omega`min:

f8

где nmax – максимальное число итераций, n – номер текущей итерации. Рекомендуемые значения `Omega`max = 0,9; `Omega`min = 0,4; снижение значения `Omega` до `Omega`min производится на протяжении 1500 итераций.

Однако результат работы гиперэвристического алгоритма можно улучшить, если изменять весовой коэффициент инерции `Omega`экспоненциально:

f9

Обозначим эту модификацию гиперэвристики через EPSO.

Результаты экспериментов

Проведено экспериментальное исследование разработанного гиперэвристического алгоритма PSO-k-means и его модификации EPSO. Целью экспериментов являлся оптимальный выбор таких параметров гиперэвристик PSO-k-means и EPSO как число частиц m, а также cpи cg– личного и глобального коэффициентов ускорения частиц соответственно.

Для экспериментального тестирования использовался набор медицинских МРТ-изображений (MRI images) компании Ossirix[21]. Все медицинские снимки для исследования были поделены на шесть групп: головной мозг; сердце; легкие; печень; костные структуры; другие.

Исследованием предусматривалось моделирование поведения PSO-k-means и EPSO с различными вариантами параметров с целью определения влияния начальных параметров на сходимость алгоритмов, число итераций, близость найденного решения к оптимальному, степень идентичности результата обработки эталонному изображению. Для удобства проведения исследований было разработано несколько вспомогательных инструментальных средств. На рисунке 1 представлен внешний вид формы, в которой отображаются результаты исследований алгоритма.

_1_01

Рисунок 1 – Форма результатов исследований алгоритмов сегментации роя частиц

Для выявления оптимального значения количества частиц m снимки исследовались при различных и условиях снимков (зашумленность, контрастность, размытость). Исследования проводились как в автоматическом, так и в интерактивном режиме [22, 23].

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

_2_01

Рисунок 2 – Диапазон значений оптимального количества частиц m в зависимости от размеров снимка

Из рисунка 2 видно, что при размере изображения до 50×50 пикселей рационально использовать не более 10 частиц для алгоритма PSO-k-means и не более 8 – для алгоритма EPSO. При больших значениях размера снимков (до 800×800 пикселей), уместно брать не более 70 и 62 частиц соответственно. Данные значения установлены экспериментальным путем и являются средними величинами, полученными при различных вариантах комбинаций начальных расстановок частиц. Это означает, что оптимальные или близкие к ним решения достигались как при меньшем, так и при большем количестве частиц, но это происходило гораздо реже. Поэтому диаграммы на рисунке 2 являются обобщенными результатами для автоматической сегментации медицинских снимков с помощью PSO-k-means и EPSO.

Для выявления оптимальных значений коэффициентов cpи cg, снимки исследовались при различных начальных параметрах алгоритма, различных начальных размерах и условиях зашумленности, контрастности и размытости снимка.

При различных значениях m алгоритм выполняет разное число итераций. В процессе решения происходит отбор лучшей частицы на текущем этапе. Для того чтобы выяснить влияние параметров PSO-k-means и EPSO на процесс получения решения и на общее число проделанных итераций, было проведено несколько десятков пусков алгоритмов с различным начальным количеством частиц. Далее производилась выборка лучших решений на основе формулы (5) и наименьшего числа итераций. Соответственно были отобраны лучшие решения для каждого случая. Далее проводилось моделирование и соответствующие результаты зависимости числа итераций от числа частиц до и после введения частиц с коэффициентами из лучших решений представлены на гистограммах рисунков 3 и 4.

_3

Рисунок 3 - Число итераций до и после коррекции коэффициентов PSO-k-means

_4

Рисунок 4 - Число итераций до и после коррекции коэффициентов EPSO

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

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

План экспериментов включал в себя выполнение для каждого изображения в группе от 30 до 100 запусков PSO-k-means и EPSO различных подтипов. Как видно из рисунка 1 все результаты исследований сохранялись в базе данных. После получения необходимого объема экспериментальных данных, делался запрос к СУБД вида:

Code 1 - PSO-k-means best solution retrieve from database

select i.Name, p.c1, p.c2, p.w, p.w1, p.w2, p.betta, p.fitness from Images i, ImageAnt ia, Particle p where ia.ImageID = i.ImageID and p.particleId = ia.AntID and ia.algorithm = 5 and p.fitness = (select MAX(particle.fitness) from particle, ImageAnt where ia.ImageID = ImageAnt.ImageID)

После получения коэффициентов для лучших решений в рамках одной группы производилось вычисление среднего арифметического для снимков одного подтипа. Соответственно подобная статистика собиралась для всех групп изображений и алгоритмов PSO-k-means и EPSO. Результаты представлены в таблицах 1 и 2.

Таблица 1 - Значение коэффициентов cp и cg для различных подтипов снимков для алгоритма PSO-k-means

t1_01

Таблица 2 - Значение коэффициентов cp и cg для различных типов снимков для алгоритма EPSO

t2

Заключение

Выполнена постановка задачи сегментации и предложен новый гиперэвристический алгоритм PSO-k-means и его модификация EPSO для решения задачи сегментации медицинских изображений, который позволяет повысить качество и скорость обработки изображений по сравнению с известными алгоритмами. Это подтверждается результатами экспериментальных исследований, полученных на основе тестовых данных из известного набор медицинских МРТ-снимков с использованием разработанного авторами программного обеспечения. Экспериментально установлено, что первичные центры кластеров не оказывают влияния на конечное решение для гиперэвристического алгоритма PSO-k-means, а для алгоритма EPSO при установлении начальных центров кластеров наблюдается улучшение конечного решения и снижение количества итераций на 3%. Также установлены оптимальные значения коэффициентов, определяющих поведение и эффективность гиперэвристик, что позволяет уменьшить количество итераций алгоритмов на 8,1% и 9,3% соответственно.

Результаты демонстрируют преимущество и подтверждают перспективность использования гиперэвристических алгоритмов PSO-k-means и EPSO в системах цифровой обработки медицинских снимков для решения задачи сегментации медицинских изображений.

Исследование выполнено при финансовой поддержке гранта Российского фонда фундаментальных исследований (проект № 16-07-00336) в Южном федеральном университете.

Библиография
1. Gonzalez R.C., Woods R.E. Digital image processing. Prentice-Hall, 2008. 954 р.
2. Pratt W.K. Introduction to digital image processing. CRC Press, 2013. 756 р.
3. Gan G., et. Data clustering: theory, algorithms, and applications.-SIAM, Philadelphia, ASA, Alexandria, 2007. 466 p.
4. Xu R., et. Clustering. N.Y.: John Wiley & Sons, 2009. 358 p.
5. Ilango M., et. A survey of grid based clustering algorithms // Int. jour. of eng. science and technology. 2010. vol. 2(8). P. 3441-3446.
6. David L. Object recognition from local scale-invariant features // Proc. of the Int. Conf. on Computer Vision, 1992, vol. 2, P. 1150–1157.
7. Rother C., Kolmogorov V., Blake A. GrabCut-interactive fore-ground extraction using iterated graph cuts. UK: Microsoft research Cambridge, 2003. P. 24.
8. Bradski G., Kaehler A. Learning OpenCV: Computer vision with the OpenCV library.-O’Reylly Media, 2008. P. 45.
9. Дороничева А.В., Савин С.З. Методы распознавания медицинских изображений для задач компьютерной автоматизированной диагностики // Современные проблемы науки и образования. 2014. № 4. С. 13; URL: http://www.science-education.ru/ru/article/view?id=14414 (дата обращения: 27.02.2016).
10. Burke E.K., Kendall G. Search methodologies: introductory tutorials in optimization and decision support techniques / Ross P. Chapter 20. Hyper-heuristics. Springer science+business media, NY, 2014. P. 611-623.
11. Скобцов Ю.А., Эль-Хатиб С.А. Компьютерная система сегментации медицинских изображений методом роя частиц // Вестник НТУ "ХПИ". Серия: Информатика и моделирование. Харьков: НТУ "ХПИ". 2015. № 36. С. 147-154.
12. Эль-Хатиб С.А., Скобцов Ю.А. Система сегментации медицинских снимков методом муравьиных колоний // Научно-технические ведомости СПбПУ «Информатика. Телекоммуникации. Управление». 2015. № 2(217). С. 9-19.
13. Eberhart R., Shi Yu., Kennedy J. Swarm intelligence. Morgan Kaufmann, 2010. 512 р.
14. Poli R. Analysis of the publications on the applications of particle swarm optimization // Jour. of artificial evolution and applications. 2008. Article ID 685175. Р. 1-10.
15. Курейчик В.В., Курейчик В.М., Родзин С.И. Теория эволюционных вычислений. М.: Физматлит, 2012. 260 с.
16. Rodzin S. Smart dispatching and metaheuristic swarm flow algorithm // Jour. of computer and systems sciences international. 2014. Vol. 53. No. 1. P. 109–115.
17. McQueen, J.B., 1967. Some methods for classification and analysis of multivariate observations // Proc. of the 5th Berkeley symp. on mathematical statistics and probability, (MSP’67), Uni of California press, Berkeley, 1967. P. 281-297.
18. Rana S., Jasola Kumar R. A hybrid sequential approach for data clustering using k-means and particle swarm optimization algorithm // Int. Jour. of Engineering, Science and Technology. 2010. Vol. 2. No. 6.-P. 167-176.
19. Saini G., Kaur H. A novel approach towards k-mean clustering algorithm with PSO // Int. jour. of computer science and information technologies. – 2014.-vol. 5 (4). – P. 5978-5986.
20. El-Desouky N., et. A new approach to weight variation in swarm optimization // Proc. of the 9th int. conf. Al-azhar engineering, 2007. P. 240 – 244.
21. Медицинская система OsiriX [Электронный ресурс]. – Режим доступа: http://www.osirix-viewer.com
22. Коробейников А.Г., Алексанин С.А. Методы автоматизированной обработки изображений при решении задачи магнитной дефектоскопии // Кибернетика и программирование. - 2015. - 4. - C. 49 - 61. DOI: 10.7256/2306-4196.2015.4.16320. URL: http://www.e-notabene.ru/kp/article_16320.html
23. Коробейников А.Г., Федосовский М.Е., Алексанин С.А. Разработка автоматизированной процедуры для решения задачи восстановления смазанных цифровых изображений // Кибернетика и программирование. - 2016. - 1. - C. 270 - 291. DOI: 10.7256/2306-4196.2016.1.17867. URL: http://www.e-notabene.ru/kp/article_17867.html
References
1. Gonzalez R.C., Woods R.E. Digital image processing. Prentice-Hall, 2008. 954 r.
2. Pratt W.K. Introduction to digital image processing. CRC Press, 2013. 756 r.
3. Gan G., et. Data clustering: theory, algorithms, and applications.-SIAM, Philadelphia, ASA, Alexandria, 2007. 466 p.
4. Xu R., et. Clustering. N.Y.: John Wiley & Sons, 2009. 358 p.
5. Ilango M., et. A survey of grid based clustering algorithms // Int. jour. of eng. science and technology. 2010. vol. 2(8). P. 3441-3446.
6. David L. Object recognition from local scale-invariant features // Proc. of the Int. Conf. on Computer Vision, 1992, vol. 2, P. 1150–1157.
7. Rother C., Kolmogorov V., Blake A. GrabCut-interactive fore-ground extraction using iterated graph cuts. UK: Microsoft research Cambridge, 2003. P. 24.
8. Bradski G., Kaehler A. Learning OpenCV: Computer vision with the OpenCV library.-O’Reylly Media, 2008. P. 45.
9. Doronicheva A.V., Savin S.Z. Metody raspoznavaniya meditsinskikh izobrazhenii dlya zadach komp'yuternoi avtomatizirovannoi diagnostiki // Sovremennye problemy nauki i obrazovaniya. 2014. № 4. S. 13; URL: http://www.science-education.ru/ru/article/view?id=14414 (data obrashcheniya: 27.02.2016).
10. Burke E.K., Kendall G. Search methodologies: introductory tutorials in optimization and decision support techniques / Ross P. Chapter 20. Hyper-heuristics. Springer science+business media, NY, 2014. P. 611-623.
11. Skobtsov Yu.A., El'-Khatib S.A. Komp'yuternaya sistema segmentatsii meditsinskikh izobrazhenii metodom roya chastits // Vestnik NTU "KhPI". Seriya: Informatika i modelirovanie. Khar'kov: NTU "KhPI". 2015. № 36. S. 147-154.
12. El'-Khatib S.A., Skobtsov Yu.A. Sistema segmentatsii meditsinskikh snimkov metodom murav'inykh kolonii // Nauchno-tekhnicheskie vedomosti SPbPU «Informatika. Telekommunikatsii. Upravlenie». 2015. № 2(217). S. 9-19.
13. Eberhart R., Shi Yu., Kennedy J. Swarm intelligence. Morgan Kaufmann, 2010. 512 r.
14. Poli R. Analysis of the publications on the applications of particle swarm optimization // Jour. of artificial evolution and applications. 2008. Article ID 685175. R. 1-10.
15. Kureichik V.V., Kureichik V.M., Rodzin S.I. Teoriya evolyutsionnykh vychislenii. M.: Fizmatlit, 2012. 260 s.
16. Rodzin S. Smart dispatching and metaheuristic swarm flow algorithm // Jour. of computer and systems sciences international. 2014. Vol. 53. No. 1. P. 109–115.
17. McQueen, J.B., 1967. Some methods for classification and analysis of multivariate observations // Proc. of the 5th Berkeley symp. on mathematical statistics and probability, (MSP’67), Uni of California press, Berkeley, 1967. P. 281-297.
18. Rana S., Jasola Kumar R. A hybrid sequential approach for data clustering using k-means and particle swarm optimization algorithm // Int. Jour. of Engineering, Science and Technology. 2010. Vol. 2. No. 6.-P. 167-176.
19. Saini G., Kaur H. A novel approach towards k-mean clustering algorithm with PSO // Int. jour. of computer science and information technologies. – 2014.-vol. 5 (4). – P. 5978-5986.
20. El-Desouky N., et. A new approach to weight variation in swarm optimization // Proc. of the 9th int. conf. Al-azhar engineering, 2007. P. 240 – 244.
21. Meditsinskaya sistema OsiriX [Elektronnyi resurs]. – Rezhim dostupa: http://www.osirix-viewer.com
22. Korobeinikov A.G., Aleksanin S.A. Metody avtomatizirovannoi obrabotki izobrazhenii pri reshenii zadachi magnitnoi defektoskopii // Kibernetika i programmirovanie. - 2015. - 4. - C. 49 - 61. DOI: 10.7256/2306-4196.2015.4.16320. URL: http://www.e-notabene.ru/kp/article_16320.html
23. Korobeinikov A.G., Fedosovskii M.E., Aleksanin S.A. Razrabotka avtomatizirovannoi protsedury dlya resheniya zadachi vosstanovleniya smazannykh tsifrovykh izobrazhenii // Kibernetika i programmirovanie. - 2016. - 1. - C. 270 - 291. DOI: 10.7256/2306-4196.2016.1.17867. URL: http://www.e-notabene.ru/kp/article_17867.html