Реферат

Введение

Количество графической информации, в особенности, создаваемой пользователями интернета непрерывно растёт. Это связано с широким распространением мобильных устройств, оснащённых высококачественными цифровыми камерами, и ростом популярности сервисов публикации и распространения фотографий. За период с 2013 по 2017 годы количество создаваемых ежегодно фотографий выросло примерно в два раза и составило 1.2 триллиона [1]. Общее количество цифровых фотографий, сохранённых человечеством, по состоянию на 2017 г. оценивается в 4.7 триллиона. Не возникает сомнений что это число будет расти.

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

Цели и задачи исследования, планируемые результаты

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

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

Основными задачами исследования являются:

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

В качестве предметной области для решения задачи поиска был выбран поиск среди изображений архитектурных объектов.

С целью апробации результатов исследования планируется участие в научно-технических конференциях.

Статья Квантование цветового пространства в контексте решения задачи поиска изображений по содержанию [2] была представлена на II научно-практической конференции Программная инженерия: методы и технологии разработки информационно-вычислительных систем (ПИИВС-2018). В ней описываются существующие методы и алгоритмы поиска изображений в графических БД.

Обзор исследований и разработок

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

Обзор международных источников

Первой коммерческой системой, использующей методы поиска изображений является QBIC, описание которой представлено в [3]. В этой публикации описывается общая структура CBIR-системы, предлагаются три вида признаков, по которым строится индекс: признаки, основанные на цветах пикселей; признаки, основанные на текстурных характеристиках, и признаки, для построения которых используется информация о формах изображённых объектов.

Эти три подхода к формированию вектора признаков долгое время улучшались и совершенствовались. Например, в [4] описывается использование многомерных гистограмм признаков (цветов, плотности границ, текстурных характеристик, величина градиента и пр.), что привело к увеличению производительности поиска. Методы на основании гистограмм основаны на построении гистограммы признаков (например цвета) по всем точкам графического файла или по их подмножеству. Схожесть изображений, в этом случае, определяется как расстояние между ними в пространстве гистограмм. Для вычисления схожести может применяться ряд метрик, например евклидова или хи-квадрат, или же более специализированные метрики, ориентированные на работу именно с гистограммами [5].

В то время как цветовые характеристики используют информацию о цвете в каждой точке изображения, для построения текстурных признаков рассматриваются окрестности точек [6].

Другой подход к выделению вектора признаков появился с появлением алгоритмов вычисления локальных дескрипторов. Первым из таких дескрипторов стал SIFT, предложенный в [7]. Идеей этого класса методов является вычисление некоторого вектора признаков для каждой из ключевых точек. Элементом этого вектора могут быть вещественные числа или булевы значения. Во втором случае дескриптор называют бинарным. Определение ключевых точек осуществляется по их окрестностям. Предполагается, что при искажении изображения (перспективные искажения, афинные преобразования, изменения освещения и пр.) будет выделено тоже, или близкое к тому же, множество ключевых точек.

SIFT функционирует в несколько этапов. Сначала вычисляется функция разности изображений с применением фильтра Гаусса. Этот этап производится для изображений различного размера с целью достижения инвариантности к масштабу. Затем, находятся экстремумы этой функции, множество которых и является множеством ключевых точек. С каждой из ключевых точек ассоциируется её ориентация, по значениям пикселей в её окрестности строится вектор признаков. Ассоциирование ориентации с точкой позволяет добиться инвариантности SIFT к повороту.

SIFT и другие локальные дескрипторы используются для многих задач, таких как сопоставление изображений, распознавание образов и, в том числе, поиск изображений по содержимому. В работе [8] описывается использование SIFT для построения CBIR-системы. В этой статье предлагается использование функции Earth Mover’s Distance для вычисления расстояния между векторами признаков.

Вскоре после появления SIFT были разработаны и другие локальные дескрипторы, отличающиеся алгоритмом выделения ключевых точек и генерации вектора по их окрестностям. К ним относятся SURF, KAZE, AKAZE, ORB, BRISK и др. В работе [9] представлено краткое описание их функционирования и приводится количественная оценка их производительности на задаче сопоставления изображений. Согласно представленным результатам, наибольшей эффективностью, среди рассмотренных, обладает ORB [10] — бинарный дескриптор, использующий алгоритм выделения ключевых точек FAST и модификацию дескриптора BRIEF вычисляющего инвариантные к повороту бинарные дескрипторы (рисунок 1).

ORB применим для решения задачи поиска, о чем свидетельствуют результаты, полученные в [11]. В этой работе используется подход мешок слов, распространённый в системах поиска текста, для генерации вектора — представления всего изображения. В связи с большой размерностью дескриптора ORB (256 бит) и большим количеством ключевых точек, описание изображения невозможно представить в форме множества дескрипторов. Вместо этого строится модель мешок слов (bag of words) [12] (в контексте поиска графической информации её иногда называют мешок визуальных слов (bag of visual words) или мешок признаков (bag of features)). Производится кластеризация всех дескрипторов и строится гистограмма количества дескрипторов в каждом кластере. Эта гистограмма затем может быть сравнена с другими гистограммами любым применимым методом.

В последнее время широкое распространение получил нейросетевой подход в задаче обработки и классификации изображений. О его эффективности можно судить по результатам проводимого компанией Google весной 2019 года конкурса, посвящённого поиску изображений в графических базах данных [13]. Согласно публикаций команд-участников, занявших призовые места [14; 15], ими применялись комбинации из нескольких моделей свёрточных нейронных сетей для вычисления вектора признаков. Недостатком нейросетевого подхода является необходимость в наличии большой обучающей базы данных и большие затраты вычислительных ресурсов.

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

Кроме k-средних существуют и другие алгоритмы сегментации: алгоритм водораздела [18], Felzenszwalb [19], SLIC [20] и др. Эти алгоритмы используются для сегментации произвольных изображений. Также существуют и специализированные алгоритмы. Пример такого алгоритма приведён в публикации [21], где авторы описывают свой алгоритм сегментации фасадов зданий. Он восстанавливает перспективные искажения, присутствующие на фотографии, и, затем, анализирует значение сумм градиентов цветов в точках каждого из столбцов пикселей, что позволяет определить вертикальные линии смены зданий, то есть отделить изображение фасада одного здания от другого.

Обзор национальных источников

Алгоритмы и методы поиска изображений по содержанию также рассматриваются исследователями из Украины и России, однако публикаций на эту тему значительно меньше чем публикаций на английском языке.

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

Также стоит отметить публикацию [23], в которой предлагается использование предварительного этапа сегментации изображения на прямоугольные участки с учетом объёма поверхности в пространстве интенсивности. После этого участки объединяются в кластеры которые и добавляются в индекс.

Обзор локальных источников

Тема поиска изображений по содержанию также рассмотрена в работах магистров и работников Донецкого национального технического университета.

Среди работ магистров ДонНТУ, опубликованных на их личных сайтах, можно выделить работы Похиля М.Ю. (выпуск 2008 г.), который рассматривает традиционные подходы к разработке CBIR-систем; Тележкина Д.В. (выпуск 2007 г.), который выполняет постановку задачи поиска, процесса выделения признаков изображения. Лукьянов С.В. (выпуск 2005 г.) рассматривает проблему оценки качества функционирования информационной поисковой системы, работающей в графической БД.

Также магистры ДонНТУ Савченко Д.А. (выпуск 2010 г.), Комаричев М.Е. (выпуск 2012 г.) и Михалец В.В. (выпуск 2007 г.) работали над магистерскими диссертациями на темы, связанные с сегментацией изображений, являющейся шагом некоторых методов поиска.

Кроме работ магистров, в ДонНТУ публиковались и работы сотрудников университета на тему поиска изображений. В частности, в публикации [24] для поиска изображений выполняется построение гистограмных признаков на основании цветов пикселей, и производится кластеризация. В публикации [25] описывается метод уменьшения излишности результатов поиска путём использования математического аппарата мультимножеств.

Стоит отметить целый ряд публикаций авторов Башкова Е.А., Вовк О.Л. и Костюковой Н.С., посвящённых вопросам поиска изображений в графических базах данных. В число этих работ входит монография Поиск изображений по содержимому в графических базах данных [26].

Архитектура системы поиска изображений по содержанию

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

Схема работы типичной системы поиска изображений [27] представлена на рисунке 2.

На этапе работы оффлайн происходит выделение признаков каждого изображения коллекции. Эти признаки имеют значительно меньший объем по сравнению с исходным изображением, что упрощает поиск. По векторам признаков выполняется построение индекса. Для этого может быть использованы k-мерные деревья [28], хеш-функции [29], особые формы инвертированного индекса [30] или прочие методы.

Аналогичный процесс осуществляется и на этапе обработки пользовательского запроса: происходит выделение признаков из запроса и выполняется поиск схожих изображений в индексе. Для определения схожести используется некоторая функция расстояния — мера сходства.

Для реализации программной модели описанной выше архитектуры поисковой системы при написании магистерской диссертации будет использована микросервисная архитектура [31]. Согласно этому подходу, разрабатываемое приложение разбивается на множество компонентов ограниченного функционального назначения и точно определенным интерфейсом. Каждый из этих компонентов может выполняться как в пределах одной вычислительной системы, так и на разных системах, объединённых компьютерной сетью.

Компоненты в микросервисной архитектуре взаимодействуют между собой средствами IPC стека TCP/IP напрямую, например по HTTP, или с помощью брокера сообщений.

Преимуществами микросервисной архитектуры является простая горизонтальная масштабируемость (количество запущенных экземпляров компонентов может динамически изменяться в зависимости от требуемой нагрузки) и отказоустойчивость (в случае критической неисправности компонента он может быть остановлен и перезапущен автоматически; необработанные сообщения будут повторно отправлены на обработку). Микросервисная архитектура была успешно применена при создании высоконагруженных систем обработки видеоинформации и изображений [32].

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

Компонентами системы являются:

• хранилище изображений — база данных графических файлов, которые можно получить по их идентификаторам по протоколу HTTP;
• Web-интерфейс — графический пользовательский интерфейс системы, который позволяет пользователю выполнять запросы и просматривать результаты поиска;
• кэш запросов — база данных и интерфейс к ней, которая хранит идентификаторы запросов и результаты поиска, в случае если они были получены;
• хранилище запросов — база данных, которая временно хранит изображения, отправленные пользователем для поиска;
• извлечение дескрипторов — подсистема, выполняющая извлечение вектора признаков;
• поиск — подсистема, выполняющая запросы к базе данных векторов признаков, организованные по принципу MapReduce.

Для реализации описанной архитектуры были выбраны следующее программное обеспечение: Docker для контейнеризации компонентов, управления их жизненным циклом и организации взаимодействия; RabbitMQ в качестве брокера сообщений; MongoDB в качестве нереляционной базы данных для изображений, кэша и векторов признаков.

Выводы

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

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

Литература

1. Erric Perret. Here’s How Many Digital Photos Will Be Taken in 2017 [Электронный ресурс]. — URL: https://focus.mylio.com/tech-today/heres-how-many-digital-photos-will-be-taken-in-2017-repost-oct (дата обращения: 04.11.2019).
2. Полетаев В. А. Квантование цветового пространства в контексте решения задачи поиска изображений по содержанию / В. А. Полетаев, И. А. Коломойцева // Программная инженерия: методы и технологии разработки информационно-вычислительных систем (ПИИВС-2018): сборник научных трудов II научно-практической конференции (студенческая секция), Том 2 / Донец. национал. техн. ун-т; — Донецк, 2017. — С. 96–101.
3. The QBIC Project: Querying Images by Content Using Color, Texture, and Shape. The QBIC Project / T.J.W.I.R. Center [et al.]. — IBM Thomas J. Watson Research Division, 1993. — 20 p.
4. Pass G. Comparing images using joint histograms / G. Pass, R. Zabih // Multimedia Systems. — 1999. — Vol. 7. — № 3. — P.—234–240.
5. A Comparison on Histogram Based Image Matching Methods / W. Jia [и др.] // 2006 IEEE International Conference on Video and Signal Based Surveillance. — Sydney, Australia, 2006.
6. A comparative study of texture measures with classification based on feature distributions / M. Pietikainen [и др.] // Pattern Recognition. — 1996. — Т. 29. — С. 51–59.
7. Lowe D. G. Distinctive Image Features from Scale-Invariant Keypoints / D. G. Lowe // International Journal of Computer Vision. — 2004. — Vol. 60. — № 2. — P.—91–110.
8. Jurandy Almeida. SIFT applied to CBIR / Jurandy Almeida, Ricardo da S Torres, Siome Goldenstein // Revista de Sistemas de Informacao. — 2009. — P.—41–48.
9. Tareen S.A.K. A comparative analysis of SIFT, SURF, KAZE, AKAZE, ORB, and BRISK / S.A.K. Tareen, Z. Saleem. — 2018.
10. ORB: An efficient alternative to SIFT or SURF / E. Rublee [et al.] // 2011 International Conference on Computer Vision 2011 IEEE International Conference on Computer Vision (ICCV). — Barcelona, Spain: IEEE, 2011. — ORB.
11. Ma L. Fast Retrieval on Remote Sensing Imagery Based On ORB Feature / L. Ma, B. Jiang, Z. Xu // International Journal of Management and Applied Science. — 2018. — Vol. 4. — № 1. — P.—4.
12. O’Hara S. Introduction to the Bag of Features Paradigm for Image Classification and Retrieval / S. O’Hara, B. Draper. — 2011.
13. Google Landmark Recognition 2019 // Kaggle [Электронный ресурс]. — URL: https://kaggle.com/c/landmark-recognition-2019 (дата обращения: 04.11.2019).
14. Ozaki K. Large-scale Landmark Retrieval/Recognition under a Noisy and Diverse Dataset / K. Ozaki, S. Yokoo // arXiv:1906.04087 [cs]. — 2019.
15. 2nd Place and 2nd Place Solution to Kaggle Landmark Recognition andRetrieval Competition 2019 / K. Chen [и др.] // arXiv:1906.03990 [cs]. — 2019.
16. Stricker M. Spectral covariance and fuzzy regions for image indexing / M. Stricker, A. Dimai // Machine Vision and Applications. — 1997. — Vol. 10. — № 2. — P.—66–73.
17. Using Image Segmentation in Content Based Image Retrieval Method / M. Ouhda [и др.] // Lecture Notes in Networks and Systems. — 2018. — С. 179–195.
18. Kaur A. Image Segmentation Using Watershed Transform / A. Kaur // International Journal of Soft Computing and Engineerin. — 2014. — Vol. 4. — № 1. — P.—4.
19. Felzenszwalb P. F. Efficient Graph-Based Image Segmentation / P. F. Felzenszwalb, D. P. Huttenlocher // International Journal of Computer Vision. — 2004. — Vol. 59. — № 2. — P.—167–181.
20. SLIC Superpixels Compared to State-of-the-Art Superpixel Methods / R. Achanta [et al.] // IEEE Transactions on Pattern Analysis and Machine Intelligence. — 2012. — Vol. 34. — № 11. — P.—2274–2282.
21. Hernandez J. Morphological segmentation of building façade images / J. Hernandez, B. Marcotegui // 2009 16th IEEE International Conference on Image Processing (ICIP) 2009 16th IEEE International Conference on Image Processing (ICIP 2009). — Cairo: IEEE, 2009. — P.—4029–4032.
22. Воробжанский Н. Н. Алгоритмы поиска изображений по содержанию с использованием нечеткого гиперграфа: Системный анализ и информационные технологии / Н. Н. Воробжанский // Вестник ВГУ. — 2016. — № 2. — С. 85–91.
23. Р. Мельник. Пошук образів за індексами кластерів фрагментів зображень / Р. Мельник, Ю. Каличак // Вісник Національного університету Львівська політехніка. — 2011. — № 719: Комп’ютерні науки та інформаційні технології. — С. 262–269.
24. Пошук кольорових зображень з використанням методів гістограмних ознак і кластеризації / О. Л. Вовк [и др.]. — 2008.
25. Башков Е. А. Исследование возможностей использования математического аппарата мультимножеств при контекстном поиске изображений в базах данных / Е. А.  Башков, О. Л. Вовк, Н. С. Костюкова // Донбас—2020: перспективи розвитку очима молодих вчених: Матеріали V науково-практичної конференції. м. Донецьк, 25–27 травня 2010 р. — Донецьк, ДонНТУ Міністерства освіти і науки, 2010. — С. 973.
26. Башков Е. А. Поиск изображений по содержимому в графических базах данных [Текст] : монография / Е. А. Башков, О. Л. Вовк, Н. С. Костюкова. — Донецк : ГВУЗ ДонНТУ, 2014. — 120 с.
27. Aber Esa A M Alomairi. An overview of content-based image retrieval techniques / Aber Esa A M Alomairi, G. Sulong // Journal of Theoretical and Applied Information Technology. — 2016. — Т. 84. — № 2. — С. 215–223.
28. Beis J. S. Shape indexing using approximate nearest-neighbour search in high-dimensional spaces / J. S. Beis, D. G. Lowe // Proceedings of IEEE Computer Society Conference on Computer Vision and Pattern Recognition IEEE Computer Society Conference on Computer Vision and Pattern Recognition. — San Juan, Puerto Rico: IEEE Comput. Soc, 1997. — P.—1000–1006.
29. Lamdan Y. Geometric Hashing: A General and Effective Model-Based Recognition Scheme / Y. Lamdan, H. Wolfson // Proceedings ICCV ’88. — Tampa, Florida, USA, 1988. — С. 238–249.
30. Поиск изображений по визуальному подобию с применением инвертированных индексов цветовых гистограмм / И. В. Соченков [и др.] // Информационные технологии и вычислительные системы. — 2015. — С. 86–94.
31. Microservices: How To Make Your Application Scale. Microservices / N. Dragoni [и др.]. — 2017.
32. M. Sc. Michel Krämer. A Microservice Architecture for the Processing of Large Geospatial Data in the Cloud / M. Sc. Michel Krämer. — 2017.