УСКОРЕНИЕ ИНДЕКСИРОВАНИЯ И ПОИСКА ИЗОБРАЖЕНИЙ ПО ОБРАЗЦУ В РАСПРЕДЕЛЕННОЙ БАЗЕ ДАННЫХ

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

Поиск изображений на основе содержимого состоит из следующих этапов:

• Этап индексирования. Отвечает за извлечение векторных объектов (локальных дескрипторов) из изображений и их сохранение в базе данных.

• Этап поиска изображений в базе. На этом этапе вектор признаков изображения запроса сравнивается с векторами признаков изображения базы данных.

Введем некоторые понятия и опишем инструменты:

MapReduce — это подход для вычисления некоторых наборов распределенных задач с использованием большого количества компьютеров (называемых «нодами»), образующих кластер. MapReduce состоит из двух шагов: Map и Reduce. На этапе map происходит предварительная обработка входных данных. Для этого один из компьютеров, называемый главным узлом (master node), получает входные данные задачи, разделяет их на подзадачи и передает другим компьютерам — рабочим узлам (worker node) для предварительной обработки. На этапе reduce происходит свёртка предварительно обработанных данных. Главный узел получает ответы от рабочих узлов и на их основе формирует результат.

Apache Spark — фреймворк с открытым исходным кодом для реализации распределённой обработки неструктурированных и слабоструктурированных данных, входящий в экосистему проектов Hadoop.

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

Метод k–ближайших соседей — метрический алгоритм для автоматической классификации объектов или регрессии. В случае использования метода для классификации объект присваивается тому классу, который является наиболее распространённым среди k соседей данного элемента, классы которых уже известны.

На этапе индексирования используется распределенная модель MapReduce на Spark для ускорения процесса. Для хранения изображений используется распределенная система работы с данными Alluxio для улучшения операции чтения/записи.

Этап поиска ускоряется использованием метода параллельного поиска k-ближайших соседей (k-NN), основанный на модели MapReduce и реализованной в Apache Spark, в дополнение к использованию метода кэширования в Spark framework.

Измерения производительности предлагаемой реализации поиска производится на наборе изображений ImageCLEFphoto2, который состоит из 20.000 изображений. Во время эксперимента использовался однорежимный кластер, в котором как ведущий, так и ведомый находятся в одном узле. Ядра процессора используются в качестве slave для master, чтобы гарантировать, что обработка изображений может выполняться параллельно, используя доступные вычислительные ресурсы. Эксперименты проводились с использованием одноузлового кластера с шестиядерным процессором AMD Ryzen 5 1600X, на 3.60 ГГц и 16 ГБ памяти, под управлением Ubuntu 16.04 LTS. Так же использовали Alluxio 1.8.1, Spark 2.1.0, Java 8 и Scala 2.10.4 для обеспечения распределения и распараллеливания вычислений.

Эксперименты проводятся для индексирования 20.000 изображений с использованием двух распределенных систем хранения данных: HDFS и Alluxio на Spark framework. В таблице 1 показано общее время, затраченное на извлечение и сохранение векторов объектов в системах Alluxio и HDFS. Можно заметить, что при увеличении набора данных изображений Alluxio занимает меньше времени для сохранения векторов объектов по сравнению с системой HDFS.

Таблица 1

Время индексирования различных наборов данных изображений

Производительность рассматриваемого метода индексирования сравнивается с другими современными методами, такими как метод централизация (Zhang et al., 2010), метод Костантини и Николусси (Costantini and Nicolussi, 2015). Таблица 2 показывает, что используемый метод превосходит другие связанные методы работы с точки зрения времени индексирования. Это увеличение достигнуто путем использование Alluxio и модели MapReduce для того чтобы быстро пройти вверх по изображениям хранить и индексировать.

Таблица 2

Сравнение различных подходов индексирования

В таблице 3 сравнивается среднее время, затрачиваемое на поиск изображений различных размеров. Сравнивается время поиска с использованием параллельного алгоритма k-NN с методом кэширования и без него. Можно наблюдать, что увеличение времени существенно при использовании метода кэша. Действительно, подход с методом кэша превосходит лучшие из используемых алгоритмов примерно на 20 %.

Таблица 3

Сравнение среднего времени вычислений в модуле поиска

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

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

1. Ding, Q. A framework for distributed nearest neighbor classification using Hadoop [Текст] / J. Ding, R. Boykin // Journal of Computational Methods in Sciences and Engineering. –2015. –Vol.17. –P. 11-19.
2. Maillo, J. A mapreduce-based k-nearest neighbor approach for big data classification [Текст] / J. Maillo, I. Triguero, F. Herrera // 2015 IEEE Trustcom/BigDataSE/ISPA. –2015. –Vol. 2. –P. 167–172.
3. A new parallel and distributed approach for large scale images retrieval [Текст] / M.A. Belarbi, S.A. Mahmoudi, S. Mahmoudi, G. Belalem // Cloud Computing and Big Data: Technologies, Applications and Security. –2017. –Vol. 49. –P. 185-201.
4. A new approach for large-scale scene image retrieval based on improved parallel-means algorithm in mapreduce environment [Текст] / J. Cao, M. Wang, H. Shi, G. Hu, Y. Tian // Mathematical Problems in Engineering.  –2016. –Vol.6. –P. 1-17.
5. J. Dean, J. MapReduce: simplified data processing on large clusters [Текст] / J. Dean, S. Ghemawat // Communications of the ACM. –2008. –Vol. 51(1). –P. 107-113.