Использование муравьиного алгоритма для кластеризации изображения

Авторы: T. Piatrik, E. Izquierdo

Автор перевода: М.А. Казанцев

Источник (англ.): T. Piatrik An application of ant colony optimization to image clustering / T. Piatrik, E. Izquierdo - Multimedia & Vision Research Group, Queen Mary University of London, 2008.

Аннотация

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

1. Введение

За прошедшие 10 лет резко возросло количество потребляемого цифрового медиа-контента, особенно изображений и видео. С ростом потребления, повышается важность методик обработки и управления соответствующим контентом. Значимым шагом в сторону поиска и определения содержимого на изображении является классификация. Традиционные методы классификации с управляемым процессом обучения предполагают предварительное наличие информации о классах всех объектов, которые есть в исходном наборе данных. В то же время, методы самообучающейся классификации не требуют какой-либо предварительной информации. Основная задача классификации, основанной на самообучении, также известной как «кластеризация» - разделение исходного набора данных на группы (кластеры) таким образом, чтобы данные в одном кластере были более схожи между собой, чем данные в разных [1]. Разделение (кластеризация) изображения на некоторые семантические классы затрагивает множество свойств изображения, включая особые комбинации цвета, текстур и форм. Проблема в том, что большинство существующих алгоритмов кластеризации, как правило, рассматривают всевозможные свойства и величины исходного набора данных в попытке получить максимально возможное количество информации об объектах. Однако, различные низкоуровневые дескрипторы и меры подобия изображений не предназначены для того, чтобы их естественно и осмысленно объединяли. Низкоуровневые дескрипторы, использовавшиеся в этой работе, имеют различные градации в разных величинах, а также основаны на различных специфических визуальных сигналах, представляющих многие аспекты содержимого. Цель компьютера определить связи между комплексными соединениями низкоуровневых атрибутов и семантик. В литературе, задача определения важных характеристик решена при помощи техник выделения признаков [2]. Эти техники выделают набор важных свойств для классификации и кластерного анализа, однако они способны найти только одно подходящее подмножество для всех кластеров. Следовательно, вместо того чтобы обрабатывать набор данных как единое целое, алгоритмы кластеризации подпространства сужают область поиска и получают возможность определить кластеры, которые существуют во множестве, возможно пересекающихся, подпространств. В этой статье предлагается новый подход к определению признаков кластеризации, основанный на муравьином алгоритме. Представляемый метод разделает данные на кластеры и определяет вес признаков, соответственно с локальными изменениями каждой из величин. В следующем разделе представлены основные понятия предлагаемого метода кластеризации. Выводы и оценка эксперимента с использованием двух наборов изображений приведены в разделе 3.

2. Кластеризация с использованием муравьиного алгоритма

Последние разработки в области эвристик сосредоточены на природных и биологических системах. Алгоритм муравьиной колонии – один из наиболее популярных методов в области роевого интеллекта [3]. Реальные преимущества муравьев кроются в их коллективном «разуме» и общении, основанном на феромонах.

В данном представлении, модель муравьиной колонии играет свою роль в определении веса признаков кластера, при этом каждый муравей предполагает вариант решения задачи кластеризации [4]. Каждый муравей определит принадлежность изображения x_i, 0< i < n+1 кластеру π_u 0 < u < k+1, с вероятностью P(_{x, π)}. Для каждого центроида C_u и для каждого признака F_l, в соответствии со внутрикластерной схожестью, будут рассчитаны веса. Для каждого изображения X_i будут пересчитаны обобщенные центроиды и определенные значения феромона будут увеличены, пропорционально качеству кластеризации. Широко распространенным способом определения оптимальности кластеризации является минимизация внутрикластерной и максимизация межкластерной схожести. Выполнение алгоритма прекращается, когда все муравьи получают один и тот же результат кластеризации.

3. Оценка результатов эксперимента и заключение

В данном разделе приведена экспериментальная оценка представленного алгоритма. Объектом эксперимента выступили наборы изображений реального мира. Представленный алгоритм подпространственной кластеризации, основанный на методе муравьиной колонии (SC-ACO), сравнивается с алгоритмом PROCULUS, алгоритмом выделения глобальных признаков методом К-средних (GFS-K-Means), а также алгоритмом К-средних без выделения признаков. Для визуального представления изображений были использованы следующие низкоуровневые признаки: макет цвета (CLD), структура цвета (CSD), доминантный цвет (DCD), гистограмма контуров (EHD), матрица совпадений уровня серого (GLC). Первый набор данных был взят из базы изображений Corel и включал 600 изображений, разделенных на 6 категорий, в каждой из которых было 100 изображений. Второй набор состоял из 500, сегментированных на области, вручную аннотированных [5], изображений, которые были взят с ресурса Flickr.

Образцы изображений из каждого набора приведены на рис. 1.

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

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

4. Благодарность

Предшествующие данной статье исследования были поддержаны Европейской комиссией по контракту FP6-027026.

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

1. Xu, R., and Wunch, D. 2005. Survey of Clustering Algorithms. IEEE Trans. Neural Network, Vol.6, No.3. 645-678.
2. Molina, L. C., Belanche, L., and Nebot, A. 2002. Feature Selection Algorithms: A Survey and Experimental Evaluation. Technical Report LSI-02-62-R (Universitat Politècnica de Catalunya, Barcelona, Spain, 2002).
3. Colorni, A., Dorigo, M., Maniezzo, V. 1991. Distributed optimization by ant colonies. In Proceedings of ECAL'91 European Conference on Artificial Life (Amsterdam, Netherlands 1991). Elsevier Publishing, 134-142.
4. Piatrik, T. and Izquierdo, E. 2006. Image Classification using an Ant Colony Optimization approach. In Proceedings of 1st International Conference on Semantic and Digital Media Technologies (Athens, Greece, December 6-8, 2006).
5. Papadopoulos, T. G., Chandramouli, K., Mezaris, V., Kompatsiaris, I., Izquierdo, E., and Strintzis, M. G. 2008 A Comparative Study of Classification Techniques for KnowledgeAssisted Image Analysis. In Proc. 9th International Workshop on Image Analysis for Multimedia Interactive services.