Яндекс Поисковая Система


Яндекс, роботы и Сибирь — как мы сделали систему поиска по загруженному изображению
Март 13, 2016 – 09:27

Сегодня Яндекс запустил поиск картинки по загруженному изображению. В этом посте мы хотим рассказать о технологии, которая стоит за этим сервисом, и о том, как её делали.

Конечно, сама по себе задача не нова, и ей посвящено множество исследований. Но сделать прототип, работающий на академической коллекции, и построить промышленную систему, которая работает с миллиардами изображений и большим потоком запросов — очень разные истории.

Для чего всё это нужно?

Есть три сценария, при которых нужен поиск по загруженной картинке и которые нам и нужно было научиться обрабатывать.
  • Человеку нужна такая же или похожая картинка, но в другом разрешении (как правило, самая большая), а может, другого цвета, лучшего качества или не обрезанная.
  • Нужно понять, что на картинке. В этом случае достаточно короткого описания рядом с изображением, чтобы стало понятно, кто или что на нем.
  • Нужно найти сайт, на котором есть такая же картинка. Например, когда захотелось почитать о том, что на картинке. Или посмотреть на такие же картинки. Или купить то, что на картинке изображено, – в этом случае нужны магазины.

Как это работает?

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

Процесс поиска изображения по загруженной картинке в больших коллекциях, как правило, строится в таком порядке:

  1. Получение набора визуальных слов для загруженной картинки.
  2. Поиск кандидатов по инвертированному индексу, определяющему по заданному набору визуальных слов список содержащих его изображений.
  3. Проверка взаимного расположения совпавших дескрипторов для картинки-образца и исследуемого изображения. Это этап валидации и ранжирования кандидатов. Традиционно используется кластеризация преобразований Хафа или RANSAC.

Идеи подхода изложены в статьях:
  • J. Philbin, O. Chum, M. Isard, J. Sivic, and A. Zisserman. Object retrieval with large vocabularies and fast spatial matching. In CVPR, 2007
  • J. Sivic and A. Zisserman. Video google: a text retrieval approach to object matching in videos. In ICCV, 2003.
  • James Philbin Josef Sivic Andrew Zisserman Geometric Latent Dirichlet Allocation on a Matching Graph for Large-scale Image Datasets (Items 3.1, 3.2)

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

Ключевое в нашей реализации поиска кандидатов — это переход от индексирования визуальных слов к индексированию более дискриминативных признаков, специальная структура индекса.

Source: habrahabr.ru
Вас может заинтересовать
Регистрация в системе Яндекс
Регистрация в системе Яндекс ...
Типичная поисковая система
Типичная поисковая система ...
Поговорим оПоисковые системы
Поговорим о...Поисковые системы ...
Поисковая система Яндекс
Поисковая система Яндекс ...
Похожие публикации