Система поиска изображений по содержанию

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

• поиск изображений в Интернете;
• определение объектов по фотографии;
• каталогизация изображений произведений искусства;
• организация работы с архивами фотографических снимков;
• организация каталогов розничной продажи товаров;
• диагностика заболеваний (с помощью сравнения снимков);
• контроль распространения интеллектуальной собственности;
• контроль содержимого массивов изображений.

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

• масштаб;
• расположение на сцене;
• фон и помехи;
• проекция, вращение и угол обзора.

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

• масштабом;
• поворотом в плоскости изображения;
• расположением на сцене;
• наличием шумов, заслоняющих объектов;
• другими значениями яркости и контраста.

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

SURF (Speed Up Robust Feature) — один из наиболее популярных методов выделения ключевых точек и их дескрипторов. Он широко применяется в области систем компьютерного зрения, так как обеспечивает высокую степень инвариантности повороту, масштабу и шумам, а также является одним из самых эффективных и быстрых современных алгоритмов этого класса.

В совокупности с эффективным алгоритмом поиска ближайших соседей (Randomized KD-Tree) система представляет современное высокопроизводительное решение для большого круга задач, связанных с поиском изображений.

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

Рисунок. Основные модули CBIR-системы

Каждую точку описывает вектор, составленный из SURF-дескриптора (64 числа с плавающей точкой одинарной точности) и вектора, определяющего среднее значение цвета в окрестности 5×5 соответствующей точки (6 чисел). Для поиска был выбран алгоритм Randomized KD-Tree — наиболее эффективный для конкретного случая.

Так как метод SURF работает только в оттенках серого, часть информации об исходном изображении теряется. Для того чтобы исправить этот недостаток, необходимо добавить к каждой ключевой точке описание цветовых характеристик в некоторой ее окрестности. Выберем область 5×5 вокруг ключевой точки и вычислим средние значения для каждого RGB-канала среди 25 точек. Таким образом, мы получим цветовую характеристику первого порядка i-го канала E_i. Также вычислим среднеквадратическое отклонение от величины E_i для i-го канала, что даст нам цветовую характеристику второго порядка σ_i:

где P_ij — значение яркости j-го пикселя в i-ом канале, N — количество пикселей в окрестности (25). Для обеспечения лучшего контроля вклада, вносимого вектором цветовых признаков, введен коэффициент масштаба scale:

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

Реализация включает в себя следующие модули:

• Сторона сервера:
  • ngine.py — основной модуль, реализующий функции индексации и поиска;
  • storage.py — модуль, реализующий возможность сохранения и загрузки данных о проиндексированных изображениях;
  • server.py — многопоточный веб-сервер, формирующий страницу выдачи результатов.
• Сторона клиента:
  • index.html — главная HTML-страница;
  • results.html — шаблон страницы выдачи результатов;
  • style.css — файл CSS-стилей.

Система работает в несколько этапов:

• Вместе с запуском веб-сервера запускается индексация, выделяется набор признаков для каждого изображения в базе и добавляется запись в базу признаков в виде пар «URL-изображения => набор признаков».
• Состояние базы признаков сохраняется.
• Запрос от пользователя поступает с клиентской части веб-интерфейса.
• Многопоточный веб-сервер обрабатывает запрос, отправляя данные в бинарном виде в модуль engine.
• Для входного изображения выделяется набор векторов (признаков).
• Отправляется запрос на поиск ближайших соседей для этого вектора в пространстве проиндексированных признаков (возвращает набор индексов базы признаков).
• Алгоритм голосования подсчитывает, какое среднее расстояние (по всем точкам) до образца приходится на каждое проиндексированное изображение, и возвращает список экземпляров с наименьшими значениями расстояния в виде пар «URL-изображения => расстояние»:
  

  def perform_nn_search(self, vector, image_url): np = numpy.array(vector, numpy.float) nearest, dists = self.flann.nn_index(np, self.KEY_SEARCH_COUNT, checks=self.params[“checks”]) # Поиск ближайших векторов # Массивы, содержащие количество совпавших ключевых точек и суммарную дистанцию для них для каждого изображения count_map = {} dist_map = {} for points, dists in itertools.izip(nearest, dists): for index, dist in itertools.izip(points, dists): link = self.storage.data[0][index] if link not in count_map: count_map[link] = 1 else: count_map[link] += 1 # Найдена ключевая точка if link not in dist_map: dist_map[link] = math.sqrt(dist) else: dist_map[link] += math.sqrt(dist) # Добавляется дистанция до нее return self.voting_algorithm(count_map, dist_map) # Вызов алгоритма голосования def voting_algorithm(self, count_map, dist_map): for key in dist_map.keys(): dist_map[key] /= count_map[key] # Вычисление средней дистанции sorted_x = sorted(dist_map.iteritems(), key=lambda (k,v): (v,k)) # Изображения сортируются в порядке возрастания средней дистанции return sorted_x

• Веб-сервер формирует из шаблона на основе полученного списка страницу выдачи результатов и отправляет ее на сторону клиента.

Для эффективного выполнения ресурсоемких вычислений были использованы библиотеки OpenCV и FLANN.

Был проведен ряд экспериментов с целью настройки параметров на оптимальные значения и определения качества поиска системы в целом. Система тестировалась на специальной контрольной базе изображений COIL-100.

COIL-100 — популярная контрольная база, содержащая 100 разных объектов, отснятых на черном фоне с 72 позиций (в каждой позиции камера смещается на 5° вокруг вертикальной оси объекта относительно предыдущей позиции). Однако для ускорения процесса тестирования была создана уменьшенная база, состоящая из 15 случайных объектов, представленных в 72 позициях. Всего база содержит 1080 изображений размером 128×128 точек.

Общая точность на контрольной выборке составила 88%, что является неплохим показателем.

Литература

1. Velmurugan К., Santhosh Baboo S. Content-Based Image Retrieval using SURF and Colour Moments // Global Journal of Computer Science and Technology. 2011. № 11.
2. Muja M., Lowe D. G. Fast Approximate Nearest Neighbors With Automatic Algorithm Configuration. Vancouver, B. C., Canada: University of British Columbia, 2009.