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

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

Attribute / Dimension (Атрибут / Измерение)

Числовое значение, представляющее определенную визуальную характеристику изображения. Изображение представляется как набор таких измерений (вектор признаков). В патенте упоминается, что они могут быть связаны с техниками сжатия (JPEG, WebP и т.д.).

Clustering (Кластеризация)

Процесс группировки результатов поиска изображений на основе их визуального сходства друг с другом (например, с помощью pair-wise similarity comparison). Используется для создания высококачественного ранжирования.

Image-dimension repository (Репозиторий измерений изображений)

Хранилище, которое сохраняет связь между конкретным изображением и тем dimension, который был определен как оптимальный для его ранжирования.

Kendall's Tau Distance (Расстояние тау Кендалла)

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

Query Image (Изображение-запрос)

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

Reference Ranking Set (Эталонный набор ранжирования)

Высококачественное ("идеальное") ранжирование похожих изображений. Генерируется с помощью ресурсоемких методов (например, кластеризации) и служит стандартом качества для обучения системы.

Weighted Distance Function (Функция взвешенного расстояния)

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

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

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

1. Идентификация первого набора изображений, похожих на изображение-запрос.
2. Генерация первого ранжирования на основе множества атрибутов.
3. Генерация второго ранжирования на основе группировки изображений в кластеры.
4. Сравнение первого и второго ранжирований с эталонным набором ранжирования (reference set of rankings).
5. Выбор конкретного набора ранжирования на основе сравнения.
6. Ранжирование второго набора изображений (связанного с другим, будущим запросом) на основе атрибута, ассоциированного с выбранным набором ранжирования.
7. Предоставление этого ранжированного второго набора.

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

Claim 3 (Зависимый от 1): Уточняет генерацию эталонного набора.

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

Claim 5 (Зависимый от 1): Уточняет механизм ранжирования на основе кластеров.

Для каждого кластера определяется оценка сходства (similarity score) (например, на основе сходства хотя бы одного изображения в кластере с запросом). Ранжирование генерируется на основе этих оценок схожести кластеров.

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

Изобретение применяется в системах визуального поиска (Google Images, Google Lens) и затрагивает этапы индексирования и ранжирования.

INDEXING – Индексирование и извлечение признаков
На этом этапе из изображений извлекаются визуальные признаки (dimensions) и сохраняются в индексе.

Офлайн-обработка и анализ данных (Model Training)
Основной механизм обучения выполняется вне процесса обработки запроса в реальном времени:

• Выполнение кластеризации для генерации Reference Ranking Set.
• Тестирование различных dimensions с помощью Dimension selection engine.
• Сохранение результатов в Image-dimension repository.

RANKING – Ранжирование / RERANKING – Переранжирование
На этапе выполнения запроса (онлайн) система использует результаты обучения для ускорения:

• Система (Similar image identification engine) проверяет Image-dimension repository.
• Если для изображения-запроса (или похожего на него) известен оптимальный атрибут, система использует Weighted Distance Function, сфокусированную на этом атрибуте, для быстрого ранжирования кандидатов (Low-Overhead Ranking). Это заменяет необходимость кластеризации в реальном времени.

Входные данные:

• Изображение-запрос (Query Image).
• Набор похожих изображений-кандидатов из индекса.
• Визуальные атрибуты (dimensions) для всех изображений.
• Данные из Image-dimension repository.

Выходные данные:

• Отсортированный список похожих изображений.

На что влияет

• Типы контента и форматы: Влияет на все типы изображений, которые могут быть обработаны системой и представлены в виде dimensions. Упоминаются форматы JPEG, GIF, PNG, TIFF, WebP.
• Специфические запросы: Влияет исключительно на запросы типа "Поиск по изображению" (Search by Image) или функции "Похожие изображения" (Similar Images). Не влияет на поиск по ключевым словам.

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

• Условия применения (Обучение): Применяется периодически для анализа новых или популярных изображений, чтобы заполнить Image-dimension repository, или когда для запроса еще не определен оптимальный атрибут.
• Условия применения (Онлайн / Low-Overhead): Применяется, когда пользователь отправляет запрос, и система предварительно вычислила и сохранила оптимальный dimension для этого или визуально похожего изображения.

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

Процесс А: Обучение и выбор оптимального атрибута (Выполняется офлайн или периодически)

1. Получение данных: Выбор изображения-запроса и идентификация набора похожих изображений.
2. Генерация эталона (Reference Ranking Set):
   • Кластеризация результатов на основе их визуального сходства друг с другом.
   • Переранжирование результатов на основе кластеров (например, приоритет у больших или более релевантных кластеров). Результат сохраняется как эталон.
3. Генерация альтернативных ранжирований: Для каждого доступного атрибута (Dimension T):
   • Расчет расстояний с использованием Weighted Distance Function, которая придает большой вес атрибуту T.
   • Создание альтернативного ранжирования на основе этих взвешенных расстояний.
4. Сравнение и оценка:
   • Сравнение каждого альтернативного ранжирования с эталонным набором.
   • Расчет оценки сходства порядков с использованием Kendall's Tau Distance.
5. Выбор и сохранение:
   • Идентификация атрибута, чье ранжирование получило наивысшую оценку (наиболее близко к эталону).
   • Сохранение связи между изображением и этим оптимальным атрибутом в Image-dimension repository.

Процесс Б: Быстрое ранжирование (Выполняется онлайн)

1. Получение запроса: Получение нового изображения-запроса от пользователя.
2. Идентификация кандидатов: Поиск похожих изображений в индексе.
3. Проверка репозитория: Запрос к Image-dimension repository для поиска сохраненного оптимального атрибута для этого или похожего изображения.
4. Применение взвешенного ранжирования: Если атрибут найден, ранжирование кандидатов с использованием Weighted Distance Function, сфокусированной на этом атрибуте. (Этап кластеризации пропускается).
5. Вывод результатов: Предоставление отранжированного списка пользователю.

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

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

Патент фокусируется исключительно на визуальных данных.

• Мультимедиа факторы: Основные используемые данные — это визуальные признаки, извлеченные из изображений. Они представлены как набор числовых значений — Dimensions (вектор признаков). Патент упоминает пример, где изображение может быть представлено набором из 59 измерений.

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

Система использует несколько ключевых методов вычислений:

1. Функции расстояния (Distance Functions) и Алгоритмы кластеризации: Используются для измерения базового визуального несходства и для группировки результатов (упоминаются спектральная и иерархическая кластеризация).

2. Взвешенные функции расстояния (Weighted Distance Functions): Используются для расчета расстояния с акцентом на конкретный атрибут (t). Патент приводит несколько примеров формул. Например (Equation 1):

$D_{t}(x_{q}, x_{i}) = d(x_{q}, x_{i}) + c * (x_{q,t} - x_{i,t})^2$

Где $D_{t}$ — расстояние с весом на атрибуте t, $d(x_{q}, x_{i})$ — базовое расстояние, c — константа, а $(x_{q,t} - x_{i,t})$ — разница значений атрибута t между запросом и результатом.

3. Расстояние тау Кендалла (Kendall's Tau Distance): Используется для сравнения двух ранжирований (Equation 4):