Как Google определяет текстовое описание изображения для визуального поиска, анализируя похожие картинки и связанные с ними запросы

Термины и определения

Query by Image (Запрос по изображению)

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

Local Descriptors (Локальные дескрипторы)

Абстрактное математическое описание визуальных признаков локальной области изображения. Используются для нахождения визуальных совпадений между разными изображениями. Могут вычисляться с использованием вейвлетов (например, Gabor wavelets).

Distributed kd-tree (Распределенное kd-дерево)

Структура данных, используемая для индексации локальных дескрипторов и быстрого поиска ближайших соседей (визуально похожих признаков) в многомерном пространстве.

Image Affinity (Аффинность изображений)

Мера визуального сходства между двумя изображениями. В контексте графа изображений определяется как произведение весов ребер (оценок совпадения) вдоль максимального пути аффинности (maximum affinity path) между двумя изображениями.

N-gram (N-грамма)

Последовательность из N токенов (слов). В патенте это текстовые фразы, ассоциированные с изображением. Источники n-грамм: query phrases, по которым кликали на изображение, и текст из referrers (страниц, содержащих изображение).

Yield (Выход, Эффективность)

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

Selection Cost (Стоимость выбора)

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

Derived Textual Query (Производный текстовый запрос)

Текстовое описание (n-gram), которое система генерирует для входного изображения-запроса путем анализа n-грамм визуально похожих изображений.

Image-specific Score (Оценка n-граммы для изображения)

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

Overall Score (Общая оценка n-граммы)

Агрегированная оценка для n-граммы, рассчитанная на основе Image-specific Scores всех визуально похожих изображений, найденных по запросу.

Ключевые утверждения (Анализ Claims)

Патент содержит несколько групп утверждений, описывающих процесс индексации (Claim 1 и зависимые) и процесс обработки запроса (описан в Summary/Detailed Description).

Claim 1 (Независимый пункт, Фокус на индексации): Описывает метод создания поискового индекса изображений.

1. Получение группы изображений и их метаданных.
2. Генерация локальных дескрипторов для каждого изображения.
3. Построение начального индекса с использованием этих дескрипторов.
4. Генерация набора совпадающих изображений (matching images) для каждого изображения с помощью индекса. Совпадение основано на match score (визуальное сходство).
5. Использование группы изображений и их совпадений для определения финального набора изображений (final image selection). Это включает:
   • Генерацию неориентированного графа (изображения = вершины, совпадения = взвешенные ребра).
   • Определение парной аффинности изображений (pairwise image affinity) на основе весов ребер вдоль пути в графе.
   • Выбор финального набора изображений с использованием аффинности.
6. Расчет набора n-грамм и соответствующих оценок для каждого изображения, используя аффинность изображений и метаданные.
7. Генерация нового (финального) индекса, используя финальный набор изображений и включая соответствующие n-граммы.

Claim 4, 11 (Зависимые): Детализируют расчет аффинности.

Pairwise image affinity определяется путем нахождения maximum affinity path (пути максимальной аффинности) между двумя изображениями в графе и рассчитывается как произведение весов ребер вдоль этого пути.

Claim 5, 12 (Зависимые): Определяют метод выбора финального набора изображений.

Выбор изображений осуществляется путем максимизации функции Yield (Выход) по всему графу. Формула Yield: $Y := Sum_{i}(max_{j}(s_{j})(w_{ij})) - (\text{selection cost})(s_i)$(sj​)(wij​))−(selection cost)(si​). Она балансирует выгоду от охвата изображения и затраты на его включение в индекс (selection cost).

Где и как применяется

Изобретение в основном применяется на этапах индексирования и понимания запросов в системе визуального поиска.

INDEXING – Индексирование и извлечение признаков
Это основной этап для создания инфраструктуры визуального поиска.

• Извлечение признаков: Вычисление Local Descriptors (визуальных признаков) для изображений.
• Сбор метаданных: Ассоциация изображений с метаданными: query phrases, click counts, referrers, text snippets.
• Построение индекса и Анализ графа: Создание индекса (например, Distributed kd-tree), построение графа визуального сходства, расчет Image Affinity и использование этой информации для ассоциации изображений с релевантными n-grams (семантическими описаниями).
• Оптимизация индекса: Выбор финального набора изображений путем максимизации Yield.

QUNDERSTANDING – Понимание Запросов
Когда пользователь отправляет изображение в качестве запроса, система должна интерпретировать его.

• Система использует визуальный индекс для нахождения похожих изображений.
• Анализируются n-grams, связанные с этими похожими изображениями.
• Система выполняет процесс выбора наилучшей n-gram, чтобы сгенерировать Derived Textual Query. Это и есть процесс понимания семантики изображения.

RANKING – Ранжирование
После того как Derived Textual Query сгенерирован, он передается в стандартную систему ранжирования для поиска результатов (веб-страниц, других изображений и т.д.).

На что влияет

• Конкретные типы контента: В первую очередь влияет на изображения. Особенно важно для e-commerce (товары), медиа (фотографии событий, людей), локального поиска (фотографии мест).
• Специфические запросы: Влияет на обработку визуальных запросов (Query by Image, Google Lens). Также косвенно влияет на текстовый поиск изображений, так как определяет, какие n-grams ассоциируются с какими изображениями.

Когда применяется

• Триггеры активации (Индексация): Алгоритм индексации применяется только к изображениям, которые удовлетворили пороговому количеству кликов (threshold number of clicks) в ответ на текстовые запросы. Это используется как фильтр популярности и релевантности.
• Триггеры активации (Запрос): Алгоритм активируется, когда пользователь явно использует функцию визуального поиска (например, загружает изображение в поисковую строку).

Пошаговый алгоритм

Процесс А: Индексация изображений и генерация N-грамм (Офлайн)

1. Сбор и Фильтрация Данных: Получение коллекции изображений. Отбор группы изображений, которые получили как минимум пороговое количество кликов в результатах поиска.
2. Идентификация Метаданных: Для каждого отобранного изображения идентифицируются метаданные: query phrases, количество кликов, URL-адреса рефереров и текстовые сниппеты из них.
3. Вычисление Визуальных Признаков: Для каждого изображения рассчитываются local descriptors (например, с использованием вейвлетов для областей интереса).
4. Построение Начального Индекса: Генерация начального индекса (например, распределенного kd-tree) с использованием local descriptors.
5. Идентификация Совпадений: Для каждого изображения находится набор визуально похожих изображений (matching set) с использованием индекса. Сходство оценивается с помощью Match Score.
6. Построение Графа: Создается неориентированный граф, где изображения — это вершины, а совпадения — ребра, взвешенные по Match Score.
7. Расчет Аффинности и Отбор Изображений: Граф обрабатывается для определения pairwise image affinity ($a_{ij}$) путем нахождения пути максимальной аффинности. Затем определяется финальный набор изображений путем максимизации метрики Yield (Y) по всему графу.
8. Расчет и Валидация N-грамм: Для каждого изображения рассчитывается набор n-грамм и их Image-specific Scores ($w_{ik}$). N-грамма подтверждается, если она есть у нескольких похожих изображений.
9. Генерация Финального Индекса: Создается финальный поисковый индекс.

Процесс Б: Обработка Запроса по Изображению (Онлайн)

1. Получение Запроса: Система получает изображение в качестве запроса.
2. Поиск Похожих Изображений: Система запрашивает финальный индекс для получения группы визуально похожих изображений.
3. Расчет Общих Оценок N-грамм: Система определяет Overall Score для каждой n-граммы путем агрегации Image-specific Scores от всех похожих изображений. Применяется фильтрация (стоп-слова, черные списки).
4. Выбор Текстового Описания: Система выбирает одну n-грамму в качестве Derived Textual Query. Процесс итеративно ищет лучшую n-грамму, начиная с коротких (N=1) и переходя к более длинным, обновляя выбор, если более длинная n-грамма имеет более высокую оценку или является надстрокой (superstring) текущего лучшего варианта и превышает порог принятия.
5. Выполнение Поиска: Система выполняет поиск, используя выбранное текстовое описание (n-грамму) в качестве текстового запроса.

Какие данные и как использует

Данные на входе

• Контентные факторы (Визуальные): Пиксельные данные самих изображений. Используются для вычисления Local Descriptors и определения визуального сходства (с помощью вейвлетов Gabor wavelets).
• Поведенческие факторы: Критически важные данные. Query phrases (текстовые запросы, по которым изображение показывалось в поиске). Clicks (количество выборов изображения для данной Query Phrase).
• Ссылочные и Контекстные факторы: Referrers (URL страниц, содержащих изображение или ссылку на него). Используются text snippets с этих страниц (текст, физически близкий к изображению) и anchor text ссылок на изображение.

Какие метрики используются и как они считаются

• Match Score (Оценка совпадения): Оценка визуального сходства между двумя изображениями на основе совпадения local descriptors.
• Image Affinity ($a_{ij}$): Произведение Match Scores вдоль пути максимальной аффинности между двумя изображениями в графе.
• Yield (Y): Метрика для оптимизации состава индекса. Формула: $Y := Sum_{i}(max_{j}(s_{j})(w_{ij})) - (\text{selection cost})(s_i)$(sj​)(wij​))−(selection cost)(si​).
• N-gram Image-Specific Score ($w_{ik}$): Рассчитывается как