УДК 004.932.2
Вестник СибГАУ 2014. № 5(57). С. 44-50
МУЛЬТИАГЕНТНЫЙ ПОДХОД В РЕКОНСТРУКЦИИ ТЕКСТУРЫ НА ИЗОБРАЖЕНИЯХ
А. Н. Болгов
Сибирский государственный аэрокосмический университет имени академика М. Ф. Решетнева Российская Федерация, 660014, г. Красноярск, просп. им. газеты «Красноярский рабочий», 31
Е-mail: anbolgov@gmail.com
Рассматривается процесс разработки и применения мультиагентной системы для реконструкции текстуры фонового пространства изображения при удалении объектов. Рассматривается общая проблематика процедуры фото- и видеореконструкции, а также области ее применения. Проводится анализ существующих методов восстановления пропусков в больших массивах данных. Предлагается решение на основе одного из распространенных методов кластерного анализа - особой самоорганизующейся нейронной сети. Приводится поэтапный алгоритм обучения карт Кохонена: инициализация карты, выбор механизма отбора узлов, смещение смежных узлов в зависимости от функции соседства, определение меры обучения и переобучения сети, шаги грубой и тонкой подстройки. Разработан адаптированный алгоритм обучения и восстановления данных изображения на основе карт Кохонена. Введены механизм инициализации карты, структура обучающих векторов, методика выбора нейрона-победителя, функции соседства. Рассматривается принцип мультикарти-рования и применение кооперативного решения задачи на основе мультиагентного подхода. Расширен алгоритм мультиагентного решения на основе предварительной сегментации для определения смежных областей. Разработана архитектура мультиагентной системы, определено поведение отдельных агентов, спроектированы коммуникационные каналы для взаимодействия агентов. Реализована мультиагентная система восстановления текстуры на изображения. Представлены результаты экспериментов. Эксперименты были проведены на базе эталонных изображений для поиска объектов интереса (CBIR database). Приведены оценки эффективности выбранных параметров мультикартирования. Оценка оптимального количества карт при мультикартировании проведена на основе процента покрытия палитры исходного изображения. Представлены показатели точности и быстродействия агентного механизма для подсистем обучения и реконструкции, на основании которых можно сделать выводы об эффективности предлагаемой методики. Оценка точности проведена при помощи метрик SSIM, MSE, PSNR, а также при помощи методики попиксельного сравнения. Оценка быстродействия проведена для различных конфигураций мультиагентной системы с целью определения самой эффективной из них.
Vestnik SibGAU 2014, No. 5(57), P. 44-50
IMAGE TEXTURE RECONSTRUCTION BASED ON MULTIAGENT APPROACH
A. N. Bolgov
Siberian State Aerospace University named after academician M. F. Reshetnev 31, Krasnoyarsky Rabochiy Av., Krasnoyarsk, 660014, Russian Federation E-mail: anbolgov@gmail.com
Development and implementation of a multiagent system that designed for texture restoration of image background when deleting objects are examined in the thesis. General problems of photo and video reconstruction and its application are reviewed. The analysis of existing methods for restore gaps in big data arrays is held. Solution by using one of popular method of clustering analysis: special self-organizing neural network is offered. Algorithm of learning Koho-nen map is covered step by step: preparation initial map data, best matching unit choice, shifting adjacent nodes by neighborhood function, determination of training measures, ordering and fine tuning. Adaptation and modification of the Kohonen map algorithm for image restoring is proposed. Algorithms of initialization of map, choice of content of training vectors, best matching unit algorithm, neighborhood functions are highlighted in this paper. Kohonen multi-map principle and cooperative solution by using multiagent paradigm is considered. Mutliagent algorithm is expanded by presegmentation step for defining of adjacent areas. Architecture of a multiagent system is developed, behavior of individual agents and communication ways are determined. Multiagent system that allows restoring background pixels
of is implemented. Results of series of experiments are presented. Experiments were carried out on the database of images to search for objects of interest (CBIR database). Assessments of efficiency parameters of multimapping are presented. Evaluation of the optimal number of maps for by multimapping is based on a percentage of the original image palette coverage. The accuracy and performance of agent-based mechanism for the subsystems of training and reconstruction are represented. Assessments of accuracy metrics using SSIM, MSE, PSNR and method by pixel-per-pixel comparison are conducted. Performance estimation for various configurations of the multi-system is conducted in order to determine the most effective ones.
Введение. На сегодняшний день существует множество систем, в которых реализованы различные алгоритмы обработки изображений. Предварительная обработка изображений для решения прикладных задач является неотъемлемым этапом работы таких систем. Одной из важных задач предварительной обработки является удаление объектов и восстановление фонового пространства, располагающегося за ними. Выполнение данного этапа позволяет исключить из последующего анализа объекты, лежащие вне области интереса. При удалении некоторого объекта из изображения важно сохранить общую однородность фонового пространства, чтобы исключить возможные ложные срабатывания последующих алгоритмов обработки данных изображения. Подобная техника широко применяется при фотосъемке в процессе ретуши и общей корректировки композиции, а также в различных системах наблюдения и учета для более детальной фокусировки на определенной группе объектов интереса [1-3].
Для решения задачи восстановления фона существует множество подходов, многие из которых базируются на принципах статистического и кластерного анализа. Изображение в контексте подобных подходов рассматривается как огромный набор статистически упорядоченных данных. Группы пикселей связаны между собой, и на основе существующих алгоритмов возможно восстановление пикселя фоновой подложки путем статистического и кластерного анализа всего изображения в целом либо окружающих пикселей данной группы [4]. Высокую эффективность для восстановления данных имеют методы, построенные на основе кластерного подхода, например, карты Кохонена.
Карты Кохонена. Карты Кохонена, или самообучающиеся карты (Self-organizing Map - SOM) Кохо-нена, - это нейросетевая архитектура для автоматической кластеризации (классификации без учителя), в которой учитывается информация о взаимном расположении нейронов, которые образуют решетку [5-7]. Сигнал в такую нейросеть поступает сразу на все нейроны, а веса соответствующих синапсов интерпретируются как координаты положения узла, и выходной сигнал формируется по принципу «победитель забирает все», т. е. ненулевой выходной сигнал имеет нейрон, ближайший (в смысле весов синапсов) к подаваемому на вход объекту. В процессе обучения веса синапсов настраиваются таким образом, чтобы узлы решетки «располагались» в местах локальных сгущений данных, т. е. описывали кластерную структуру облака данных, с другой стороны, связи между нейронами соответствуют отношениям соседства между
соответствующими кластерами в пространстве признаков.
Изначально SOM представляет собой сетку из узлов, соединенных между собой связями. Кохонен рассматривал два варианта соединения узлов - прямоугольная и гексагональная сетки. Отличие состоит в том, что в прямоугольной сетке каждый узел соединен с четырьмя соседними узлами, а в гексагональной -с шестью ближайшими узлами. Таким образом, для двух таких сеток процесс построения SOM отличается лишь тем, где перебираются ближайшие к данному узлу соседи [8; 9].
Начальное положение сетки выбирается произвольным образом. Основными вариантами являются вариант случайного начального расположения узлов в пространстве и вариант расположения узлов в плоскости. После инициализации расположения узлов они начинают перемещаться в пространстве согласно следующему алгоритму:
M (t) = min(min(d (x(t), mif (t)))), (1)
i=0 j=0 j
где t - итерация обучения; W - ширина карты; H -высота карты; x(t) - обучающий вектор; mj (t) - нейрон карты в позиции (ij); d - функция сравнения двух векторов.
ml (t) = ml (t -1) + ha (t) • (x(t) - ml (t -1)) , (2) где t - итерация обучения; mi (t) - значение функции соседства; x(t) - обучающий вектор; hci - нейрон-карты.
Итогом работы алгоритма обучения является обученная карта, т. е. будут определены веса всех нейронов. Также возможен вариант обучения сразу нескольких
карт и выбор лучшей карты по определенным критериям.
Мультиагентный подход. Для эффективного решения задачи требуется механизм, позволяющий, с одной стороны, обеспечивать распределенное решение задачи восстановления текстуры, с другой стороны, получать оптимальные результаты точности в сравнении с базовым алгоритмом. Мультиагентный подход позволяет решить выше обозначенные проблемы. Агентом является все, что может рассматриваться как воспринимающее свою среду с помощью датчиков и воздействующее на эту среду с помощью исполнительных механизмов [10]. Решение задачи одним агентом на основе инженерии знаний представляет собой точку зрения классического искусственного интеллекта, согласно которой агент (например, интеллектуальная система), обладая глобальным видением проблемы, имеет все необходимые способности, знания и ресурсы для ее решения. Напротив, при создании многоагентных или мультиа-гентных систем (МАС) предполагается, что отдельный агент может иметь лишь частичное представление о задаче и способен решить лишь некоторую ее подзадачу. Поэтому для решения сколько-нибудь сложной проблемы, как правило, требуется взаимодействие агентов, которое неотделимо от формирования МАС. В МАС задачи распределены между агентами, каждый из которых рассматривается как член группы или организации. Распределение задач предполагает назначение ролей каждому из агентов, определение меры его ответственности и требований к опыту [11-13].
Предлагаемый механизм решения задачи реконструкции фона изображения. Предлагаемый алгоритм реконструкции фона на изображении на основе карт Кохонена состоит из двух основных этапов: обучение карты и восстановление пропусков в векторах данных. Для успешного выполнения данных этапов необходимо определить следующие аспекты и компоненты процесса:
ю. (х,у) = Р[1 +1 © 5,г +1 + 5], (3)
I = х-\\_Б/2\\ , (4)
г = у-\\5/2] , (5)
где - размер блока пикселей; Р[/, /] - пиксель, расположенный в 1-м столбце и }-й строке на изображении; х, у - координаты, для которых строится вектор.
При использовании представленного выше метода построения векторов необходимо учитывать следующие ограничения, заданные формулами
/2\\< х < Ж-\\_Б/2\\ , (6)
/2] < у < Н-\\_Б/2], (7)
где 5 - размер блока пикселей; Ж - ширина изображения; Н - высота изображения.
Данные условия вводятся в силу того, что размер рассматриваемого блока больше одного пикселя и, соответственно, количество таких блоков будет меньше, чем количество пикселей в изображении. Дополнительно накладывается условие, что 5 должно быть четным для более точного описания окружности пикселя, а именно, для симметричности окружности пикселя.
dij=Jx(xk- w,jk)2
где xk - k-е значение вектора входных данных; wijk -k-е значение вектора весов нейрона из i-й и j-й позиции карты; S - размерность вектора весов.
h(p, t) = e 2g (t 1,| p < a,
-3, a < Ip| < 3a, 0,|p| > 3a. 1,| p < 1, , 1<|p < 2,
где р - расстояние между узлами карты; г - номер итерации; а - заранее определенная константа (обычно а = 2).
и минимальная точность, рассчитываемая как сумма средних изменений весов в итерации обучения.
Определение данных компонентов, аспектов и настроек позволяет адаптировать технологию восстановления пропусков в данных для решения прикладной задачи реконструкции поврежденного изображения. Решение задачи восстановления фона изображения за удаляемым объектом состоит из двух основных этапов: обучение карты Кохонена и восстановление фона по обученной карте. Эффективность реконструкции «пропусков» на стыке нескольких текстур увеличивается при восстановлении каждой смежной текстуры по отдельно обученной карте. Для этого требуется еще один дополнительный шаг сегментации исходного изображения. Система состоит из двух основных блоков: блок обучения и блок восстановления. Данное разделение на блоки позволяет определить основные классы подзадач для решения общей задачи системы.
При анализе функциональных требований и проектировании будущей системы был сделан выбор в виде следующей модификации классического варианта решения задачи восстановления фона изображения по карте Кохонена: для увеличения точности получаемых результатов предлагается использование мультикартирования, т. е. построение сразу нескольких карт; затем на этапе восстановления параллельно восстанавливать изображение по нескольким картам с выбором оптимального значения для каждого пикселя.
С точки зрения мультиагентного подхода архитектура системы изображена на рис. 1.
Заключение. Экспериментальный программный продукт позволил провести исследование предложенной архитектуры в части точности и быстродействия решения задачи. Результаты реконструкции текстуры фона изображения представлены на рис. 2.
Для проведения экспериментальных исследований были выбраны 100 изображений различной сложности и размерности из базы эталонных изображений CBIR database (http://www.cs.washington.edu/). Данные файлы были объединены в группы по 10 изображений для удобства проведения тестов и интерпретации результатов.
На первом этапе исследования осуществлялся поиск оптимального количества карт (рис. 3).
По результатам проведенных исследований можно сделать следующий вывод: одна обученная карта Кохонена в большинстве случаев не покрывает 50 % палитры исходного изображения, поэтому мультикарти-рование является оптимальным механизмом для восстановления. Четыре карты являются оптимальным количеством карт, так как позволяют достигать более 92 % покрытия палитры без существенной потери производительности системы как в случае 8 карт. Результаты точности реконструкции приведены на рис. 4.
По результатам исследования точности восстановления можно сделать вывод, что многоагентная конфигурация алгоритма восстановления позволяет добиться лучших результатов. На менее сложных изображениях результаты многоагентной и одноагентной конфигурации близки, однако с увеличением размерности и структурной сложности изображений прирост точности становится заметен. Результаты исследования быстродействия алгоритмов представлены на рис. 5.
По результатам исследования быстродействия алгоритмов системы видно, что мультиагентный подход позволяет добиться увеличения быстродействия алгоритмов. Оптимальным числом агентов для системы является четыре, так как позволяет добиться почти 100 %-ого ускорения алгоритмов в сравнении с одно-агентным подходом. Однако дальнейшее увеличение числа агентов отрицательно сказывается на системе, так как увеличиваются затраты на коммуникацию агентов.
Рис. 1. Архитектура мультиагентной системы по восстановлению текстуры
а б в г
Рис. 2. Результаты реконструкции текстуры фона изображения: а - исходное изображение; б - сегментированное изображение; в - восстановленное изображение; г - восстановленное изображение с предварительной сегментацией
Рис. 3. Результаты поиска оптимального количества карт
■ 1 агент
□ Много а гсм 1 ос
« 50% 20% 10% 0%
I 1 агсм I
□ Много агентов
^30 сс
I 1 агент
□ Много агентов
^ 30% о 5
£ I 20%
Г Г . ГШ
■ 1 агеь I
□ Много агентов
Рис. 4. Результаты оценки точности алгоритма восстановления: а - по метрике М8Е; б - по метрике РБЫР.; в - по метрике ББГМ; г - по проценту точно восстановленных пикселей
сГ 4000
СС -57
■ 1 агент □ 2 агента
■ 4агента
■ 8агентов
■ 1 агент □ 2 агента
■ 4агента
■ S агентов
Рис. 5. Результаты исследования быстродействия алгоритмов системы: а - алгоритм обучения; б - алгоритм восстановления
Таким образом, проведенные исследования показали, что комбинирование методов кластерного анализа, классических приемов обработки изображений, а также мультиагентного подхода позволяет решить задачу реконструкции фона изображения. Выявлено, что мультиагентный подход не только не уменьшил точность работы системы, но и позволил добиться незначительного увеличения данного показателя. Кроме этого, механизм распределенного решения задачи позволил достичь 90-110 % увеличения быстродействия системы в сравнении с одноагентной системой.
Библиографические ссылки
References
© EOOTOB A. H., 2014