Кент Брюстер | Инженер Pinterest, Разработка продуктов

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

Результаты и аннотации для полноэкранных скриншотов были довольно неутешительными. Поскольку они имели тенденцию совпадать со снимками экрана, которые ранее были сохранены в Pinterest, мы показывали такие результаты, как «Веб-сайт», «Интернет-сайт» и «Тема Wordpress» вместо интересных объектов внутри снимков экрана.

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

Вместо того, чтобы отправлять каждый снимок экрана обратно в Pinterest для анализа, мы нашли способ обнаруживать интересные вещи, используя только JavaScript внутри расширения браузера.

Преобразовать снимок экрана в данные

Для поиска внутри изображения нам нужно смотреть на цвета отдельных пикселей. Обычно это невозможно с использованием обычного HTML, CSS и JavaScript, но поскольку мы находимся внутри расширения браузера, у нас есть более высокий уровень привилегий. Вот оригинальный снимок экрана, преобразованный в тег ‹CANVAS›:

Уменьшить разрешение исходных данных

Скриншоты могут быть огромными, и мы собираемся сделать кучу рекурсивных вызовов функций, что является прекрасным способом вывести браузер из строя с ошибкой «Превышен максимальный размер стека вызовов». Поэтому, прежде чем делать что-либо еще, давайте уменьшим размер нашей статистической вселенной с 1100x800 (почти миллион пикселей) до максимальных 80x80.

Для этого мы берем большее из двух измерений (высоту или ширину) и делим на 80, чтобы получить размер нашего образца. Если наш оригинал имеет размер 1100x800, мы будем использовать образцы 14x14, преобразовав наше исходное изображение примерно в следующее:

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

Подсчитайте и объявите самые популярные цвета «фоном».

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

[ “#ffffff”: 1321, “#ffeeee”: 910, “#ffeeaa”: 317 … “#a5e290”: 1]

Образцы наиболее распространенных цветов (здесь мы будем использовать три верхних) помечаются как фон.

Как только мы узнаем цвета фона, мы снова опрашиваем все образцы переднего плана. На этот раз мы конвертируем значения красный-зеленый-синий (RGB) в значения оттенка-насыщенности (HSV) и находим все образцы, которые имеют тот же оттенок и значение, что и верхний цвет фона. Когда мы находим их, мы объявляем их также самими образцами фона. Это улавливает многие ситуации, когда у нас есть полупрозрачный фон под увеличенным изображением, например, при просмотре крупным планом изображений Twitter и сообщений Instagram.

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

Удалить изолированные пиксели

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

Залить оставшиеся блоки переднего плана, отмечая высоту и ширину

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

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

То, что осталось? Только интересные прямоугольники, здесь показаны белым цветом:

Найдите самый интересный прямоугольник в мире

Прямоугольник интереснее, если он:

  • больше по площади, чем 1/16 размера холста
  • не более чем в 3 раза шире своей высоты
  • портрет вместо пейзажа
  • ближе к верхнему левому углу, чем другие прямоугольники того же размера

Прямоугольник вообще не интересен, если он:

  • размером менее 100x100 пикселей
  • более чем в 5 раз шире, чем его высота

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

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

Полученные результаты

После первоначального выпуска визуального поиска в нашем расширении для браузера мы изучили анонимный образец полноэкранных снимков экрана, который был обработан Pinners с помощью инструмента выбора. Мгновенное обнаружение функций изображения привело к согласию (или улучшению) того, что Pinner выбирал в 85% случаев. Во всех случаях, когда обнаруживались интересные вещи, поисковые аннотации возвращали что-то получше, чем «Веб-сайт».

Эти улучшения теперь доступны для всех, и мы обнаруживаем интересные вещи на снимках экрана в 96% случаев, с гораздо более высоким процентом появления и сохранения релевантных результатов поиска, и все это без необходимости уточнять первоначальный выбор Pinner.

Благодарности: Келей Сюй, Райан Ши, Стивен Рамкумар и Стивен Уоллинг