УДК 004.021
ИССЛЕДОВАНИЕ И РАЗРАБОТКА МЕТОДА РАСПОЗНАВАНИЯ ОБЪЕКТА НА ИЗОБРАЖЕНИИ С ПОМОЩЬЮ АЛГОРИТМА МУРАВЬИНЫХ КОЛОНИЙ
А.Ю.Плитка, К.А.Ручкин Донецкий национальный технический университет, г. Донецк
кафедра искусственного интеллекта и системного анализа dartin1@mail.ru
Плитка А.Ю. Ручкин К.А. Исследование и разработка метода распознавания объекта на изображении с помощью алгоритма муравьиных колоний.
С развитием науки и техники, обилием графической информации и ее активным обменом, все более актуальным становится автоматическое распознавание объектов на изображениях с решением задачи выделении их контуров. Их практическое применение предполагает более высокие требования к методикам распознавания объектов на изображении. Основная сложность при решении данной задачи – учет различных дополнительных факторов на изображении: разнообразие фона, вариабельность различных частей изображения, зашумленность. В данной статье рассматривается возможность применения алгоритма муравьиных контуров для распознавания объектов на изображении, приводятся преимущества перед генетическим алгоритмом.
Ключевые слова: распознавание объектов, муравьиные колонии, роевой алгоритм.
Введение. Задача распознавания границ объектов на изображении является одной из основных для областей, занимающихся обработкой и анализом изображений. Границы объектов содержат большую часть информации об изображении и исследования зрительной системы человека показывают, что края объектов изображения имеют особое значение, поскольку объекты могут быть определены всего лишь несколькими грубыми контурами.
Обычно технологии распознавания и классификация изображений включают в себя следующие этапы: предобработка изображения, определение границ изображения, извлечение признаков и автоматическая классификация. На практике цвет фона, размер объектов, зашумление, могут прервать определение границ; поэтому, большой проблемой является поиск методов, с высокой скоростью и устойчивостью к помехам.
Постановка задачи. Задачи определения границ изображений легко сводятся к задачам оптимизации графов. Поскольку в основе муравьиного алгоритма лежит моделирование передвижения муравьёв по некоторым путям графа, то такой подход является эффективным способом поиска рациональных решений для задач оптимизации, в первую очередь, на графах [1].
Генетический алгоритма для распознавания объектов на изображении. Генетические алгоритмы (ГА) являются одним из самостоятельных разделов теории искусственного интеллекта – эволюционных вычислений, которые основаны на математическом моделировании процессов биологической эволюции. В основе ГА лежат принципы естественной эволюции, сформулированные Дарвином, – естественный отбор, изменчивость, наследственность. С их помощью ГА моделируют генетические процессы, происходящие в биологических сообществах. Обычно генетические алгоритмы применяются для решения оптимизационных проблем. Предметная область ГА включает в себя проблемы комбинаторики, биоинформатики, теории игр и др. ГА применяются также для обработки и распознавания образов, в частности изображений.
В рамках данной проблемы ГА может быть использован как при подготовке изображения к распознаванию, в частности при фильтрации, сегментации, разметке сцены, так и непосредственно для его распознавания. В
[4]рассматривается подход автоматической разметки сцены с помощью ГА. Комбинация использования семантических сетей для представления ограничений области и нечеткой логики для достижения соответствия меток этим ограничениям породили новую стратегию вычисления
Применение алгоритма муравьиных колоний для распознаваня объекта на изображении. Для того чтоб построить соответствующий муравьиный алгоритм для решения какой-либо задачи, необходимо:
1.Представить задачу в виде набора компонент и переходов или набором неориентированных взвешенных графов, на которых муравьи могут строить решения;
2.определить значение следа феромона;
3.определить эвристику поведения муравья, когда строим решение;
4.если возможно, то реализовать эффективный локальный поиск;
5.выбрать специфический муравьиный алгоритм и применить для решения задачи;
6.настроить параметры алгоритма.
Рассмотрим алгоритм кластеризации изображения, основанный на алгоритме муравьиных колоний. В этом алгоритме муравьи представляются простыми агентами, которые случайным образом перемещаются по дискретному массиву. Пикселы, которые рассеяны в элементах массива могут быть перемещены из одного элемента массива в другой, формируя кластеры.
динамически кластеризируют изображение на независимые кластеры, которые включают только сходные между собой пикселы. Кроме этого агент представляет новые вероятностные правила для присоединения или исключения пикселов, а так же стратегию локального перемещения для ускорения сходимости алгоритма.
Предположим, размерность массива равна N. Каждый элемент этого массива связан с гнездом муравьев в определенном порядке, что позволяет муравьям легко переходить от одного элемента к другому. В процессе алгоритма муравьи могут изменять, строить или убирать существующие кластеры пикселов. Кластер представляется соединением двух или более пикселов и пространственно расположен в отдельной ячейке массива, что упрощает его идентификацию.
Инициализируем N пикселов {Р1,…,Рn} для кластеризации, располо- женные в массиве таким образом, что каждый элемент массива связан только с одним пикселом. Каждый муравей аi из колонии с К муравьями {a1,…,аk} присоединяет случайно выбранный пиксел из элементов массива и возвращается в гнездо.
После начального этапа инициализации происходит этап кластеризации. Выбор муравья производится случайным образом. Он перемещается от своего гнезда к элементам массива и определяет с помощью вероятностного правила, присоединять ли этот пиксел к кластеру. Каждый муравей знает список расположения пикселов, которые не были присоединены другими муравьями. Случайным образом муравей определяет следующий пиксел из списка свободных. Этот алгоритм повторяется для каждого муравья. Алгоритм останавливается при прохождении заданного количества итераций.
Сравнение алгоритмов. Эксперименты, описанные в литературе, показывают, что генетические алгоритмы очень эффективны в поиске глобальных минимумов адаптивных рельефов, так как в них исследуются большие области допустимых значений параметров нейронных сетей. (Градиентные алгоритмы дают возможность находить только локальные минимумы.) Другая причина того, что генетические алгоритмы не застревают
влокальных минимумах — случайные мутации, которые аналогичны температурным флуктуациям метода имитации отжига. Естественно
генетические алгоритмы не свободны от недостатков. К ним можно отнести прежде всего следующие. Конфигурация для решения сложных реальных задач не очевидна. Для решения конкретной задачи необходимо выбрать или разработать представление (кодирование) потенциального решения. Существует также проблема определения
Всравнении с генетическими алгоритмами муравьиные алгоритмы имеют некоторые преимущества: базируются на памяти обо всей колонии вместо памяти только о предыдущем поколении; меньше подвержены неоптимальным начальным решениям
Кнедостаткам относятся следующие свойства муравьиных алгоритмов: сходимость гарантируется, но время сходимости неизвестно; обычно необходимо применение дополнительных методов, таких как локальный поиск; сильно зависят от настроечных параметров, которые подбираются только исходя из экспериментов.
Выводы. Алгоритм муравьиных колоний имеет огромный потенциал для решения задач, связанных с обработкой изображений, включая определение границ, извлечение признаков, сегментацию, сжатие изображения. Вариации алгоритма для решения задачи определения объекта на изображении были рассмотрены. Так же в данной статье был произведен общий анализ алгоритма муравьиных колоний, используемого для обработки изображений, были выявлены его преимущества и недостатки по сравнению с генетическим алгоритмом. Все это дает направление для более подробного исследования данной задачи, и попытке применить данный алгоритм на практике.
Список литературы
1.Dorigo M, Vittorio M, Alberto C. Ant System: Optimization by a Colony of Cooperating Agents, IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics). 1996; 26(1):29−41.
2.Dorigo M, Thomas S. Ant Colony Optimization: Overview and Recent Advances. Techreport, IRIDIA, Universite Libre de Bruxelles, 2009.
3.Tabakhi S, Parham M, Fardin A. An Unsupervised Feature Selection Algorithm based on Ant Colony Optimization, Engineering Applications of Artificial Intelligence. 2014;
4.Khanna K, Navin R. Reconstruction of Curves From Point Clouds using Fuzzy Logic and Ant Colony Optimization, Neurocomputing. 2015; 161:72−80.
5.Aghdam Mehdi H, Nasser GA, Mohammad EB. Text Feature Selection using Ant Colony Optimization, Expert Systems with Applications. 2009; 36(3):6843−53.
6.Jun S, Dong H. Statistical Theory of Edge Detection, Computer Vision, Graphics, and Image Processing. 1998; 43(3):337−46.
7.Barbosa H. Ant Colony Optimization: Techniques and Applications. In Tech, 2014.