Компания
362,50
рейтинг
9 сентября 2013 в 13:05

Разработка → Яндекс, роботы и Сибирь — как мы сделали систему поиска по загруженному изображению

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

Технология внутри Яндекса получила название «Сибирь». От CBIR — Content-Based Image Retrieval.

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



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


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

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

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


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

Процесс поиска изображения по загруженной картинке в больших коллекциях, как правило, строится в таком порядке:
  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)

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

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

Для отбора кандидатов одинаково хорошо показали себя два метода:
  1. Индексирование высокоуровневых особенностей или визуальных фраз (словосочетаний). Они представляют собой комбинацию визуальных слов и параметров, характеризующих взаимное расположение и другие относительные характеристики соответствующих локальных особенностей изображения.
  2. Мульти-индекс, где ключ составляется из квантованных частей дескрипторов (product quantization). Метод был опубликован: download.yandex.ru/company/cvpr2012.pdf

При валидации мы используем собственную реализацию кластеризации преобразований между изображениями.

Теперь поднимемся на уровень выше и посмотрим на схему продукта в целом.



  1. Картинка пользователя попадает во временное хранилище.
  2. Оттуда уменьшенная копия изображения попадает в демон, где для картинки вычисляются дескрипторы и визуальные слова и из них формируется поисковый запрос.
  3. Запрос отправляется сначала на средний метапоиск и оттуда распределяется по базовым поискам. На каждом базовом поиске может найтись множество изображений.
  4. Найденные изображения отправляются обратно на средний метапоиск. Там происходит слияние результатов, и полученный отранжированный список показывается пользователю.

Каждый базовый поиск работает со своей частью индекса. Этим обеспечивается масштабируемость системы: при росте индекса добавляются новые фрагменты и новые реплики базового поиска. А отказоустойчивость обеспечивается дублированием базовых поисков и фрагментов индекса.

И еще один важный нюанс. Когда мы строили наш поисковый индекс изображений, то для того чтобы повысить эффективность поиска, использовали уже имеющиеся у нас знания о дубликатах изображений. Использовали это таким образом, что из каждой группы дубликатов мы брали только по одному представителю и включали его в индекс поиска по картинке. Логика проста: если картинка релевантна запросу, то все её копии будут так же релевантным ответом.







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



image

image

image

image

Это наш первый шаг в поиске изображений по контенту. Конечно, мы будем развивать подобные технологии и делать на их основе новые продукты. И уж чего-чего, а идей и желания у нас для этого хватает.
Автор: @krainov
Яндекс
рейтинг 362,50

Комментарии (57)

  • +8
    Молодцы!
  • +6
    Задержались с бета-тестом.

    1. В гугле можно тянуть картинку на форму ввода запроса и при этом автоматически открывается поле для переноса картинки. У вас для этого нужно нажимать лишнюю кнопочку с иконкой фотоаппарата.

    2. Тащим например вот эту фотку portswigger.net/css/portswigger-logo.gif
    с главной этого сайта portswigger.net/index.html, гугл правильно грузит фотку и находит что это, у вас же если делать по яндекс-логике, то ответ «По указанному адресу не смогли найти картинку, попробуйте ввести другой адрес.» А если сделать интуитивно — перетащить картинку на пиктограмму фотоаппарата в строке поиска — то мы переходим по ссылке < a href=«index.html» > т.е нас редиректит на главную сайта.
  • +21
    Спасибо за замечания. Сейчас дорожки протопчут, а потом мы их заасфальтируем. Посмотрим, как чаще используют, куда кликают, куда переходят — и дошлифуем интерфейс.
  • +1
    Бегло ознакомился cо статьей, я правильно понимаю, что идея алгоритма у вас вертится вокруг построения диаграммы Вороного по Дескрипторам ключевых точек? А как данный подход масштабируется при увеличении данных? Не смотрели при разработке в сторону моделей нейронного газа, или(буквально сегодня мной описанных на хабре) растущих нейронных сетей? Или глубокие сети(они вроде бы применяются в аналогичном сервисе от Google)?
    • +3
      Строго говоря наш алгоритм кластеризации не эквивалентен алгоритму построения диаграммы Вороного.
      Масштабируется наше решение очень хорошо. Это как раз было одним из важнейших условий.
      Для этой задачи мы нейронные сети не рассматривали. Нейронные сети — это эффективное средство для определения категорий изображений, а не для поиска копий.
      Google, насколько, нам известно, тоже нейронные сети использует не для поиска копий, а для распознавания категорий (наиболее частых меток) на фотографиях в Google+. Но тут, конечно, лучше у них спрашивать.
      • 0
        Вы же решаете задачу кластеризации при поиске копий? Модели нейронного газа и растущих нейронных сетей как раз для этого и разработаны.
        А про способы масштабирования можно поподробней? Это ведь самая интересная часть вашей системы.
        • +3
          Вы же решаете задачу кластеризации при поиске копий? Модели нейронного газа и растущих нейронных сетей как раз для этого и разработаны.

          Решаем, да. Но так сложилось, что сейчас мы это делаем без использования сетей.
          А про способы масштабирования можно поподробней? Это ведь самая интересная часть вашей системы.

          В основном масштабирования мы добиваемся не столько алгоритмами, сколько архитектурой. Посмотрите на схему: довольно очевидно, что компенсировать рост объемов индекса можно большим дроблением и увеличением количества базовых поисков (CBIR search на схеме).
          Но если решать задачу в жестких рамках — скажем, если есть условие, что количество картинок в индексе растет, а количество «железа» нет — то можно «играть» размерами индекса, убирая наиболее частотные визуальные слова. И, кроме того, можно строже отбирать кандидатов для валидации, что несколько уменьшит полноту, но заметно увеличит скорость.
  • +4
    Очень хотелось бы расширение для Хрома, позволяющее запускать Яндексовский поиск по картинке прямо из контекстного меню по правому клику мыши. То есть как аналогичный функционал у расширения «Гугл — поиск по картинкам». Это чертовски удобно.
  • –13
    Яндекс впереди планеты всей…
    а идей и желания у нас для этого хватает

    Могу подкинуть ещё пару идей. Как насчет поиска изображения из камеры смартфона? Голосовой поиск?
  • 0
    В принципе для поиска по загруженному изображению можно приспособить и более простой алгоритм:

    habrahabr.ru/post/122372
    • 0
      Как описываемый вами алгоритм решает дилемму стабильности-пластичности? Даже если брать в качестве хэша изображения 64*64, а интенсивность в диапазоне [0...255], то всего таких хэшей будет чуть больше миллиона. И при очень больших размерах базы(а у поисковой системы база именно такой должна быть) коллизий будет значительно больше, чем при feature matching'е на той-же базе.
      • 0
        Ну так индексирование в моем алгоритме — это просто способ уменьшить количество сравнений. В моем случае оказалось достаточно трехмерного индекса, но ничего в принципе не мешает использовать индексы большей размерности, например, пятимерные индексы.
        • +1
          Трехмерные индексы — это индексы i[1], i[2], i[3](в терминологии той статьи)? Это ведь по сути некоторые частные случаи для градиентов(кстати, похожи на часть Хааровских фич для детектирования лиц). Для тех-же SIFT дескрипторов вычисляется значительно больше градиентов, и совокупность дескрипторов для изображения будет более репрезентативной «подписью» для изображения.

          Вообще, если интересно, по одному из методов оценки совокупностей особых точек можно почитать в моей статье.
    • +3
      Такой подход не решает проблем с сильными модификациями. Самый частый случай модификации — это кроп. Но бывает разное: и элементы двигают, и текст меняют, и добавляют всякое…
      Возьмем для примера логотип хабра — чего тут только не встретишь.
      • 0
        Безусловно, у моего алгоритма есть недостатки (к кропу он не устойчив). Однако большинство случаев хватает и его. В частности очень эффективно ищет похожую картинку (картинку с другим разрешением или степенью сжатия).

        P.S. К стати почему вы не ищете картинки по блогам и социальным сетям?
  • –6
    Яндекс изобрел SURF (habrahabr.ru/post/103107/) и как водится написал об этом намного путанее и загадочнее чем оно есть на самом деле ))
    • +4
      SURF — это один из возможных способов получения локальных дескрипторов.
      Мы его не используем, но это не принципиально. Можно и SURF использовать. Выбор дескриптора — это далеко не самое важное.
  • +1
    Протестировал. Почему-то через раз выдает ошибку «не удалось загрузить картинку». То, что удалось загрузить, показало, что картинки почему-то находятся только в доменной.ру зоне, нет картинок из соц.сетей, нет картинок из фотобанков, кроме русского pressfoto. Надеюсь, в скором будущем все это тоже будет работать.
  • +3
    Заранее извиняюсь за дилетантскую постановку вопросов, но очень интересно узнать:

    — кэшируются ли свойства изображений (имя файла, exif и так далее);
    — сохраняется ли история поиска для зарегистрированных пользователей;
    — есть ли планы по интеграции с Яндекс.диском (например кнопка «отправить в Яндекс.диск»);
    — планируется ли распознавание изображений (за отдельную плату скорее всего, так как слишком затратно для вас будет).
    • +1
      кэшируются ли свойства изображений (имя файла, exif и так далее)

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

      Нет, мы это не предусматривали. Когда мы исследовали задачу поиска по картинке, мы не увидели такой потребности
      есть ли планы по интеграции с Яндекс.диском (например кнопка «отправить в Яндекс.диск»)

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

      Распознавать изображения мы, конечно, хотим. Это довольно очевидное развитие продукта. Но я не представляю, что станем брать за это деньги.
      • +1
        Про свойства спросил потому, что подумал как было бы хорошо если по найденному фотошопленному обрезку нашелся оригинал с исходным exif-ом. А если бы еще под это дело и API, то…… я себя остановил, больше мечтать не буду.
        История полезна если вдруг навернулся жесткий диск, забыл взять флэшку где все ранее найденные оригиналы прекрасных примеров для прототипа интерфейса (случайный пример привел) в высоком разрешении.
        В Яндекс.диск удобно отправлять найденный результат для дальнейшего расшаривания. Например если сейчас срочный поиск не с домашнего/личного компьютера, а нужен результат как раз сейчас и еще дома (чтобы не повторять поиск снова). Поверьте, это было бы очень удобно.
        С распознаванием было бы шикарно, более лестного эпитета даже не подберу.
  • +1
    почему выдается
    картинка не загрузилась, попробуйте загрузить другую.?
    • +2
      Есть два варианта: либо не пролезла по размеру (у нас сейчас ограничение 8 мегабайт), либо (если это загрузка по урлу) плохой пинг до картинки и мы не смогли ее скачать.
      • 0
        картинка загружалась с диска и ее размер много меньше 8 МБ
        • +3
          Пришлите, пожалуйста, мне этот файл. Я попробую разобраться в чем причина.
          Я послал в личном сообщении свой e-mail адрес.
  • +3
    Давно ждал подобного рода фичу. Спасибо!
    • +5
      А чем вас не устраивали аналоги, начиная от tineye.com и заканчивая, как ни «странно», гуглом images.google.ru/?
  • 0
    www.tineye.com в 2008 году решил похожую задачу ( мы на тот момент не успели за ними)
  • 0
    Есть три сценария, при которых нужен поиск по загруженной картинке и которые нам и нужно было научиться обрабатывать.

    Поиск соуса ещё.
  • +4
    Сегодня день тестировщика, а самый первый тест — всегда банальный. Берем первую картинку со стрекозой из яндекса и ищем ее. Правильно — ничего не находит.

    image
    • +1
      У нас такой картинки действительно нет в индексе. Но вы правы: раз картинки нет в индексе, то и не надо ее на стартовой странице держать. Убрали, спасибо.
  • +1
    По сути я один из ваших конкурентов. Представляю узко тематический, семантический поиск. В последнее время приходится всё больше конкурировать с гуглом и вами, но всё же мы всё ещё на плаву.
    В данный момент я про семантические имиджборды или ещё данбуру подобные имиджборды (если что мой anime-pictures.net).

    Так вот, меня удивляет почему Яндекс не пытается использовать все те теги, что люди старательно прописывают к картинкам? За счёт того, что мы вручную проставляем связи (теги), мы можем гарантировать очень релевантный поиск для конкретной темы изображений, яндекс мог бы этим пользоваться ну и стараться отправлять по больше нам пользователей. Но в итоге из-за того, что на наших страницах только картинки и теги, все поисковики (не только Яндекс) нас крайне не любят, хотя мне кажется лучше было бы сотрудничать.
    Кроме того такие сайты часто гораздо лучше первоисточников, так как на них авторы редко любят описывать свои творения.

    К слову на наших объёмах для поиска по картинке хватает поиска по среднему цвету или по хеш функции (вот этот проект iqdb.org).
    • +3
      Внедрите в своих тегах хотя бы простую семантическую разметку microformats.org/wiki/rel-tag-ru. Это значительно повысит шансы для машиночитаемого разбора тегов.
      • 0
        Это не поможет. rel-tag говорит какой тег прописать для конкретной ссылки, а у меня теги на конкретной странице с картинкой и туда можно попасть как правило через поиск по коллекции (а там где картинки списком у меня не хватит производительности, что бы генерировать теги). Да и слово «тег» у нас имеет немного другой смысл.

        Кроме того у нас теги имеют тип (автор, персонаж, произведение, характеристики) и это так же не учитывается. Да и каждый тег у нас на 3 языках… :)
  • +1
    Есть три четыре сценария, при которых нужен поиск по загруженной картинке и которые нам и нужно было научиться обрабатывать.

    fixed

    Обнаружение сайтов, нарушающих авторские права. Само собой незаконных копий картинок, но и для книг, музыки и фильмов можно искать, загрузив обложки.
  • +2
    Интересно узнать, планируете ли вы подключить OCR и уточнять поиск по картинке текстовым поиском по словам на картинке, а также по совпадениям имён загруженного и исходного файлов, или по совпадению имени с текстом на картинке.
    • 0
      Использование OCR довольно обойдется дорого с точки зрения ресурсов. OCR отрабатывает на картинке на порядок медленнее, чем получение визуальных слов. И даже если с этим смириться, то встает вопрос о целесообразности. У нас, конечно, пока статистики нет — мы только запустились. Но предположу, что среди загружаемых картинок текст будет в лучшем случае у 5%. А скорее всего еще реже.
  • 0
    Странно, что не находятся картинки с Викисклада (жму на сайте Wikimedia Commons «случайная страница» и делаю поиск по этому изображению). Казалось бы — общедоступный архив изображений, используемых в Википедии, должен покрывать многие «классические» объекты поиска (достопримечательности, картины, животных, растения), заодно можно было бы брать геоинформацию для достопримечательностей и подсовывать в выдачу Яндекс.Карты.
    • 0
      Странно. Википедию мы хорошо индексируем. А какая именно картинка не нашлась?
      • 0
        10 раз зашёл на страницу commons.wikimedia.org/wiki/Special:Random/File и запускаю поиск по картинке: найдено 4 из 10
      • 0
        Вот, например, одна из ненайденных: commons.wikimedia.org/wiki/File:Fuente_La_Noble_Habana.JPG
        • +3
          Посмотрел. Действительно у нас нет. Это очень плохо. Мы исправимся. Спасибо за замечание.
  • +2
    давно пользовался tineye, потом пришел в эту нишу гугл, сейчас и яндекс подтянулся
    яндекс молодцы!

  • –1
    Возможно просьба покажется странной, но нет ли у Вас статьи «The Inverted Multi-Index» на русском языке?
    • +2
      К сожалению нет. Ее сразу на английском писали.
    • 0
      К сожалению, подобного рода статьи изначально пишут на английском языке. Английский — язык международного научного (и не только) общения)
      • 0
        Я знаю это. Просто боюсь что-либо пропустить/не так понять при чтении на английском. Надежда умирает последней) К сожалению по этой теме очень мало глубокой литературы на русском.
  • +1
    Добрый день. Как при вашем методе поиска влияет водяной знак, накладываемый на изображения? Например, интернет-магазины используют оригинальное изображение от производителя и накладывают на него свой водяной знак. Насколько вероятно найти все одинаковые фотографии с разными водяными знаками на разных веб-сайтах?
    • +2
      Водяные знаки вообще никак не влияют. Мы находим картинки с гораздо более сильными модификациями: кропы, фотожабы, коллажи… Иногда даже удается найти совсем другое изображение того же самого объекта.
    • 0
      Использую похожий метод. Вычисляются дескрипторы (SURF) и сопоставляются по базе. Водяной знак нисколько не влияет на результат, больше того при поиске объекта (немного другая задача) даже непрозрачное перекрытие части объекта позволит найти объект. Процент перекрытия зависит от количества оставшихся ключевых точек на видимой области. Удавалось найти даже объект на 80% площади закрытый другим
      • 0
        Простите, а как вы сопоставляете дескрипторы по базе? Простым перебором?
        • 0
          Да, перебор. До такого крутого поиска, как у ребят из Яндекса, пока далеко.
          • 0
            А тестировали на больших базах? По идее на достаточно больших базах должно много коллизий выплывать начать, не говоря уж о низкой скорости работы.
            • 0
              Да, тестировал. Коллизии на больших базах будут всегда, но их количество можно минимизировать (добавив проверки, естественно, увеличив время выполнения). Т.к. мне нужно также получить координаты найденного объекта на изображении, ищется гомография, если дескрипторы заматчились, по гомографии получаем ограничивающий 4х-угольник найденного объекта на исходном изображении, легко проверяем углы на допустимые значения (60-120 градусов для моей задачи). В стандартных примерах opencv все это есть (углы придется только самому посчитать). Проблема с временем выполнения решается подходом в статье.
  • 0
    Надо думать поиск по картинкам требует немалых вычислительных ресурсов. Не рассматриваете ли вы варианты аппаратного ускорения каких-либо ваших алгоритмов?
    • 0
      Именно для поиска аппаратное ускорение нам не особо поможет. Другое дело классификация, катетеризация, сегментация… — тут, конечно, мы рассматриваем возможность использования различных аппаратных средств.

Только зарегистрированные пользователи могут оставлять комментарии. Войдите, пожалуйста.

Самое читаемое Разработка