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

Аннотация

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

Введение  

При установлении диагноза и проведении лечения врачи все больше полагаются на медицинские изображения, к которым относятся рентгенограммы, УЗИ, магнитно-резонансная томография (MRI - Magnetic Resonance Imaging), компьютерная томография (CT - Computed Tomography), томография на позитивном излучении (PET – Positive Emission Tomography) и т.д. Использование медицинских изображений растет с каждым годом, в следствии внедрения новейшей медицинской техники в больницах и диагностических центрах.

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

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

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

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

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

На вход алгоритм получает:

1.                  исходное изображение;

2.                  дополнительную информацию от пользователя:

–                     ограничение на то, что некоторые конкретные пиксели обязательно должны принадлежать объекту/фону;

–                     ограничивающий прямоугольник вокруг объекта;

–                     примерную границу объекта и др.

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

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

Рассмотрим случай, показанный на рисунке 1.

 

Рисунок 1. – Пути прохождения муравьев от “дома” к пище.

 

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

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

Базовый муравьиный алгоритм, независимо от модификаций, можно представить в виде схемы (Рисунок 2)

Рисунок 2. –Обобщенный муравьиный алгоритм.

 

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

Поиск решений. Вероятность перехода из вершины i в вершину j определяется согласно формулы 1:

                                                                                                 (1)

где  представляет множество возможных вершин, связанных с вершиной i, для муравья k, τ_ij- уровень феромона, d_ij – эвристическое расстояние, α иβ – константные параметры.

Обновление феромона происходит в соответствии с формулой 2.

 

                                                                                               (2)

где n_k – количество муравьев, ρ– интенсивность испарения, L_k(t) – длина пути, построенного k-ым муравьем в момент времени t, а Q – параметр значимости, т. е    – феромон, откладываемый k-ым муравьём, использующим ребро (i,j).

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

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

2.                  определить значение следа феромона;

3.                  определить эвристику поведения муравья, когда строим решение;

4.                  если возможно, то реализовать эффективный локальный поиск;

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

6.                  настроить параметры алгоритма.

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

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

Инициализируем N пикселов {Р₁,…,Р_n}  для кластеризации, расположенные в массиве таким образом, что каждый элемент массива связан только с одним пикселом. Каждый муравей а_i  из колонии с К муравьями  {a₁,…,а_k} присоединяет случайно выбранный пиксел из элементов массива и возвращается в гнездо.

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

Оценка качества работы алгоритмов.

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

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

Поэтому естественно, что для сравнения алгоритмов интерактивной сегментации чаще всего используют субъективное сравнение: берется несколько изображений, и нескольким пользователям ставится одна из 2 задач:

-сегментировать данным алгоритмом все изображения не хуже заданного уровня (сравнение на «не хуже» осуществляется субъективно самими пользователями, для сравнения даётся какой-то образец сегментации). После чего определяется самый быстрый алгоритм;

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

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

1·         однородность регионов (однородность цвета или текстуры);

2·         непохожесть соседних регионов;

3·         гладкость границы региона;

4·         маленькое количество мелких «дырок» внутри региона.

Вывод.

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

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

 

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

1.             N. R. Pal and S. K. Pal, “A Review on Image Segmentation Techniques,” Pattern Recognition, Vol. 26, No 9, 2000

2.             R. Jain, R. Kasturi, and B. G. Schunck, Machine Vision, 2005

3.             S.-T. Bow, Pattern Recognition and Image Preprocessing, Marcel Dekker, Inc., New York, NY, 2006.