Українська   English
ДонНТУ   Портал магистров

Реферат по теме Исследование и разработка метода определения объекта на изображении с помощью алгоритма муравьиных колоний

Содержание

Введение

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

Среди так называемых Soft computing techniques, разработанных за последние десять лет для трудно решаемых задач дискретной оптимизации, числятся:

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

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

1. ПОСТАНОВКА ЗАДАЧИ

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

Для достижения данной цели необходимо выполнить данные задачи:

  1. Проанализировать современное состояние проблемы определения объектов на изображении.
  2. Проанализировать современные методы роевой оптимизации детектирования объектов на изображении.
  3. Разработать роевой метод определения объектов на изображении с помощью алгоритма муравьиных колоний.
  4. Предложить модификацию роевого алгоритма, для оптимизации алгоритма муравьиных колоний для определения объекта на изображении.
  5. Разработка программного обеспечения, роевого алгоритма, для оптимизации алгоритма муравьиных колоний и проведение его тестирования.
  6. Проведение сравнения эффективности разработанного роевого алгоритма с существующим алгоритмом.

2. ОБЗОР СОВРЕМЕННОГО СОСТОЯНИЯ ПРОБЛЕМЫ

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

В работе “Ant Colony Optimization towards Image Processing” K. Kavita, A. Madan рассматриваются различные задачи обработки изображений, которые могут быть достигнуты с помощью оптимизации алгоритма муравьиных колоний – важная область мягких вычислений. Алгоритм муравьиных колоний, представляет собой подход, основанный на вычислительном интеллекте, который используется для решения комбинаторных проблема оптимизации. Простота и оптимальный подход алгоритма муравьиных колоний привела к его применимости к маршрутизации, планированию, проблемы с подмножеством, заданием и классификацией. Обнаружение края, привязка к краям, извлечение функции, сегментация и сжатие изображений – это различные задачи обработки изображений, в которых алгоритм успешно применяется.

В работе “An application of ant colony optimization to image clustering” T. Piatrik, E. Izquerto рассматривается возможность кластеризации изображения с помощью оптимизации алгоритма муравьиных колоний. Авторы пришли к тому, что исходный поиск изображений может быть значительно улучшен за счет обеспечения хорошей первоначальной кластеризации визуальных данных. Проблема кластеризации изображений заключается в том, что большинство современных алгоритмов не могут идентифицировать отдельные кластеры, существующие в разных подпространствах признаков. В данной статье предлагается новый подход для кластеризации подпространств на основе оптимизации колоний муравьев и механизма обучения. Предлагаемый алгоритм меняет предположение о том, что все кластеры в наборе данных находятся в одном наборе измерений, присваивая веса функциям в соответствии с локальными корреляциями данных вдоль каждого измерения. Результаты экспериментов с наборами данных реальных изображений показывают необходимость выбора функций в кластеризации и преимуществ выбора функций локально.

В работе “A Novel Image Segmentation Algorithm Based on Artificial Ant Colonies” Huizhi Cao, Peng Huang, and Shuqian Luo представлен новый алгоритм сегментации, в котором используется биологически вдохновленная парадигма, известная как колонии искусственных муравьев. Учитывая особенности колоний искусственных муравьев, используется расширенная модель, применяемая при сегментации изображения. Каждый муравей в модели наделен способностью запоминать ссылочный объект, который будет обновляться при обнаружении новой цели. Мера нечеткой связности принимается для оценки сходства между целевым объектом и эталонным объектом. Поведение одного муравья зависит от соседних муравьев, и сотрудничество между муравьями осуществляется путем обмена информацией посредством обновления феромонов. Моделируемые результаты показывают эффективность нового алгоритма, который способен сохранять детали объекта и нечувствителен к шуму.

В работе “Image Feature Selection Based on Ant Colony Optimization” Ling Chen, Bolun Chen, Yixin Chen представляется алгоритм выбора признаков, основанный на оптимизации колонии муравьев (ACO). Для n функций большинство методов выбора объектов на основе ACO используют полный граф с ребрами O (n2). Однако искусственные муравьи в предлагаемом алгоритме пересекаются на орграфе с только 2n дугами. Алгоритм использует производительность классификатора и количество выбранных функций как эвристическую информацию и выбирает оптимальное подмножество функций с точки зрения размера набора функций и эффективности классификации. Экспериментальные результаты на разных изображениях показывают, что алгоритм может получить лучшую точность классификации с меньшим набором функций по сравнению с другими алгоритмами.

3. СОВРЕМЕННЫЕ МЕТОДЫ РОЕВОЙ ОПТИМИЗАЦИИ ДЕТЕКТИРОВАНИЯ ОБЪЕКТОВ НА ИЗОБРАЖЕНИИ

3.1. Муравьиный алгоритм

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

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

близка к минимальному остовному дереву графа их муравейников.

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

Непрямой обмен – стигмержи (stigmergy), представляет собой разнесённое во времени взаимодействие, при котором одна особь изменяет некоторую область окружающей среды, а другие используют эту информацию позже, когда в неё попадают. Биологи установили, что такое отложенное взаимодействие происходит через специальное химическое вещество – феромон (pheromone), секрет специальных желёз, откладываемый при перемещении муравья. Концентрация феромона на пути определяет предпочтительность движения по нему.

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

3.2 История создания муравьиных алгоритмов

Началось всё с изучения поведения реальных муравьёв. Эксперименты с Argentine ants, проводимые Госсом в 1989 и Денеборгом в 1990 году послужили отправной точкой для дальнейшего исследования роевого интеллекта. Исследования применения полученных знаний для дискретной математики начались в начале 90-х годов XX века, автором идеи является Марко Дориго из Университета Брюсселя, Бельгия. Именно он впервые сумел формализовать поведение муравьёв и применить стратегию их поведения для решения задачи о кратчайших путях. Позже при участии Гамбарделлы, Тайлларда и Ди Каро были разработаны и многие другие подходы к решению сложных оптимизационных задач при помощью муравьиных алгоритмов. На сегодняшний день эти методы являются весьма конкурентоспособными по сравнению с другими эвристиками и для некоторых задач дают наилучшие на сегодняшний день результаты.

3.3 Концепция муравьиных алгоритмов

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

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

anim.gif

Схема передвижения муравьев

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

3.4 Обобщенный алгоритм

Любой муравьиный алгоритм, независимо от модификаций, представим в следующем виде:

Теперь рассмотрим каждый шаг в цикле более подробно:

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

      • 1245

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

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

3.5 Этапы решения задач при помощи муравьиных алгоритмов

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

Также определяющими являются:

4 РОЕВОЙ МЕТОД ОПРЕДЕЛЕНИЯ ОБЪЕКТОВ НА ИЗОБРАЖЕНИИ С ПОМОЩЬЮ АЛГОРИТМА МУРАВЬИНЫХ КОЛОНИЙ

Задача формулируется как задача поиска минимального по стоимости замкнутого маршрута по всем вершинам без повторений на полном взвешенном графе с n вершинами. Содержательно вершины графа являются городами, которые должен посетить коммивояжёр, а веса рёбер отражают расстояния (длины) или стоимости проезда. Эта задача является NP-трудной, и точный переборный алгоритм её решения имеет факториальную сложность.

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

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

  1. Муравьи имеют собственную память. Поскольку каждый город может быть посещён только один раз, то у каждого муравья есть список уже посещённых городов - список запретов. Обозначим через список городов, которые необходимо посетить муравью k, находящемуся в городе i.
  2. Муравьи обладают зрением - видимость есть эвристическое желание посетить город j, если муравей находится в городе i. Будем считать, что видимость обратно пропорциональна расстоянию между городами .
  3. Муравьи обладают обонянием - они могут улавливать след феромона, подтверждающий желание посетить город j из города i на основании опыта других муравьёв. Количество феромона на ребре (i,j) в момент времени t обозначим через .
  4. 4. На этом основании мы можем сформулировать вероятностно-пропорциональное правило, определяющее вероятность перехода k-ого муравья из города i в город j:

    Где , - параметры, задающие веса следа феромона. При =0 алгоритм вырождается до жадного алгоритма (будет выбран ближайший город). Заметим, что выбор города является вероятностным, правило (1) лишь определяет ширину зоны города j; в общую зону всех городов бросается случайное число, которое и определяет выбор муравья. Правило (1) не изменяется в ходе алгоритма, но у двух разных муравьёв значение вероятности перехода будут отличаться, т.к. они имеют разный список разрешённых городов.

  5. 5. Пройдя ребро (i,j), муравей откладывает на нём некоторое количество феромона, которое должно быть связано с оптимальностью сделанного выбора. Пусть есть маршрут, пройденный муравьём k к моменту времени t, - длина этого маршрута, а Q - параметр, имеющий значение порядка длины оптимального пути. Тогда откладываемое количество феромона может быть задано в виде:

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

    где m - количество муравьёв в колонии.

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

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

4.1 Муравьиный алгоритм для задачи коммивояжёра в псевдокоде

Алгоритм:

Сложность данного алгоритма, как несложно заметить, зависит от времени жизни колонии ( ) городов (n) и количества муравьёв в колонии (m).

5 МОДИФИКАЦИЯ АЛГОРИТМА МУРАВЬИНЫХ КОЛОНИЙ ДЛЯ ОПРЕДЕЛЕНИЯ ОБЪЕКТА НА ИЗОБРАЖЕНИИ

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

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

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

5.1 Достоинства

5.2 Недостатки

ВЫВОДЫ

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

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

  1. Вадим Конушин, Владимир Вежневец,Методы сегментации изображений: интерактивная сегментация, // Вестник МГУ им Ломоносова – №4, 2008. – С. 107-118
  2. L. Lucchese and S.K. Mitra “Color Image Segmentation: A State-of-the-Art Survey”, 2001
  3. N. R. Pal and S. K. Pal, “A Review on Image Segmentation Techniques,” Pattern Recognition, Vol. 26, No 9, 2000
  4. R. Laptik, D. Navakauskas, Application of Ant Colony Optimization for Image Segmentation [Электронный ресурс]. - Режим доступа: http://www.ktu.lt/lt/mokslas/....
  5. Ruobing Zou, Weiyu Yu, Image Segmentation Based on Local Ant Colony Optimization [Электронный ресурс]. - Режим доступа: http://www.computer.org/portal/web/csdl/....
  6. Ахметшин А.М., Ахметшина Л.Г., Сегментация низкоконтрастных медицинских радиологических изображений методом пространственно-резонансного отображения [Электронный ресурс]. - Режим доступа: http://www.uacm.kharkov.ua/download/....
  7. Tomas Piatrik, Ebroul Izquierdo, An application of ant colony optimization to image clustering [Электронный ресурс]. - Режим доступа: http://citeseerx.ist.psu.edu/....
  8. Dzung L.Pham, Chenyang Xu, Jerry L.Prince, A survey of current methods in medical image segmentation [Электронный ресурс]. - Режим доступа: http://www.mcs.csueastbay.edu/....
  9. Huizhi Cao, Peng Huang, Shuqian Luo, A novel image segmentation algorithm based on artificial ant colonies [Электронный ресурс]. - Режим доступа: http://books.google.ru/....
  10. Myung-Eun Lee, Soo-Hyung Kim, Wan-Hyun Cho, Soon-Young Park, Jun-Sik Lim, Segmentation of Brain MR Images Using an Ant Colony Optimization Algorithm [Электронный ресурс]. - Режим доступа: http://www.computer.org/....