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

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

Visual Word (Визуальное слово)

Квантованное представление вектора признаков. Результат разделения пространства признаков на конечное число ячеек (Feature Cells). Каждая ячейка соответствует одному визуальному слову. Аналог слова в текстовом поиске.

Feature Vector (Вектор признаков)

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

Posting List (Список соответствия / Постинг-лист)

Структура данных инвертированного индекса. Для каждого Visual Word существует свой Posting List, содержащий список идентификаторов изображений (document identifiers), в которых это слово встречается. В данном патенте списки также содержат Geometry data.

Geometry Data (Геометрические данные)

Информация о пространственном расположении области признака, соответствующей Visual Word. Включает координаты (position) и масштаб (scale/size) области на изображении.

Feature Space Density (Плотность пространства признаков)

Метрика, показывающая, насколько часто встречается данный Visual Word. Рассчитывается на основе количества векторов признаков, попавших в ячейку, и размера этой ячейки. Высокая плотность означает общий, недискриминативный признак (аналог IDF).

Feature Cell (Ячейка признаков)

Область в пространстве признаков, определяющая Visual Word. Формируется в процессе кластеризации.

Tree Structure (Древовидная структура)

Структура данных, используемая для эффективного управления параллельным обходом Posting Lists. Позволяет быстро определить, какой список нужно продвинуть следующим, и идентифицировать совпадения.

Conditional Move Instruction (Инструкция условного перемещения)

Инструкция процессора, позволяющая перемещать данные в зависимости от условия без использования инструкций ветвления (branching). Используется для оптимизации обновления Tree Structure.

RANSAC (Random Sample Consensus)

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

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

Claim 1 (Независимый пункт): Описывает основной метод вычисления оценки сходства изображения путем параллельного обхода нескольких posting lists.

1. Система получает изображение-запрос и определяет его visual words.
2. Идентифицируются соответствующие posting lists. Каждый элемент списка содержит идентификатор изображения и связанные с ним geometry data. Для каждого списка поддерживается курсор (item cursor).
3. Система продвигает один из курсоров к следующему элементу.
4. Определяется количество курсоров, указывающих на одно и то же изображение (т.е. количество совпавших визуальных слов).
5. Если это количество достигает порога (threshold), система идентифицирует geometry data для совпавших слов.
6. Вычисляется оценка сходства (score) для этого изображения до достижения конца posting list (before advancing to an end of the particular posting list). Оценка основана на сравнении визуальных слов запроса и кандидата с использованием их geometry data.
7. Изображение ранжируется на основе этой оценки.

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

Claim 4 (Зависимый): Детализирует механизм обхода с использованием Tree Structure.

Обход осуществляется путем продвижения курсора того списка, который идентифицирован в корневом узле (root node) древовидной структуры. Листовые узлы соответствуют posting lists.

Claim 6 (Зависимый): Указывает на модификацию оценки сходства.

Вычисленная оценка взвешивается на основе рассчитанной Feature Space Density для соответствующего визуального слова.

Claim 7 (Зависимый): Описывает оптимизацию обновления Tree Structure.

Обновление родительских узлов выполняется с использованием инструкций Conditional Move для повышения производительности процессора.

Claim 10 (Зависимый): Определяет метод расчета Feature Space Density.

Плотность рассчитывается на основе деления количества векторов признаков в ячейке (Feature Cell) на вычисленный размер этой ячейки.

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

Изобретение применяется исключительно в инфраструктуре поиска изображений (Image Search System), например, в Google Images (поиск по картинке) и Google Lens.

INDEXING – Индексирование и извлечение признаков
На этом этапе происходят ключевые предварительные вычисления:

1. Извлечение Feature Vectors из изображений.
2. Квантование пространства признаков (офлайн): кластеризация векторов для определения Visual Words.
3. Расчет Feature Space Density для каждого визуального слова.
4. Построение Index Database: создание Posting Lists, включающих идентификаторы изображений и соответствующие Geometry data.

RANKING – Ранжирование (Этап L1 Retrieval / Отбор Кандидатов)
Это основная область применения патента в режиме реального времени.

1. Получение Visual Words из изображения-запроса.
2. Эффективный параллельный обход Posting Lists с использованием Tree Structure.
3. Идентификация изображений-кандидатов (matching images), удовлетворяющих порогу совпадений.
4. Вычисление первичной оценки сходства (similarity score) на лету с использованием геометрической верификации и взвешивания по плотности.

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

• Изображение-запрос (или его набор Visual Words).
• Index Database (Posting Lists с Geometry data).
• Данные о Feature Space Density.

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

• Список похожих изображений, ранжированных по вычисленной оценке сходства.

На что влияет

• Конкретные типы контента: Влияет исключительно на поиск и ранжирование изображений в системах, использующих изображение в качестве запроса (Query by Image, Visual Search).
• Специфические запросы: Не влияет на ранжирование веб-страниц или изображений по текстовым запросам.

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

• Условия применения: Алгоритм применяется при получении поискового запроса, содержащего изображение (Image Query).
• Триггеры активации: Механизм оценки сходства на лету активируется, когда система идентифицирует изображение-кандидат, имеющее пороговое количество общих Visual Words с запросом.

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

Процесс А: Офлайн-индексация и обучение

1. Сбор данных и Квантование: Сбор обучающих векторов признаков и их кластеризация для определения Feature Cells (Visual Words).
2. Расчет плотности: Вычисление размера каждой ячейки. Расчет Feature Space Density (количество точек / размер).
3. Расчет весов: Определение веса (W) для каждого Visual Word на основе плотности. Высокоплотные слова могут быть исключены из индекса.
4. Построение индекса: Создание Posting Lists. Заполнение списков идентификаторами изображений и их Geometry data (координаты, масштаб). Списки сортируются по идентификаторам.

Процесс Б: Обработка запроса в реальном времени

1. Получение запроса и Извлечение признаков: Система получает изображение-запрос, извлекает Feature Vectors и квантует их в Visual Words. (Система может выбрать подмножество слов с наименьшей плотностью).
2. Инициализация обхода: Идентифицируются соответствующие Posting Lists. Инициализируется Tree Structure, листовые узлы заполняются первыми элементами списков.
3. Параллельный обход (Цикл):
   1. Проверка совпадения: Анализируется корневой узел (Root Node) древовидной структуры. Если счетчик совпадений в корневом узле достигает порога, идентификатор документа признается совпадением (Matching Image).
   2. Оценка сходства (если совпадение): Немедленно вычисляется Similarity Score. Это включает:
      • Извлечение Geometry data из индекса.
      • Выполнение геометрической верификации (например, RANSAC) для поиска оптимального отображения (geometric mapping). Патент приводит пример $f(x,y)=[ax+b, cy+d]$.
      • Подсчет количества выровненных (aligned) визуальных слов.
      • Взвешивание результата с учетом Feature Space Density.
   3. Продвижение курсора: Продвигается курсор того Posting List, который указан в корневом узле (наименее продвинутый список).
   4. Обновление структуры: Tree Structure обновляется снизу вверх для отражения нового состояния курсоров. Этот шаг оптимизирован с помощью Conditional Move Instructions.
4. Завершение и Ранжирование: Цикл повторяется до завершения обхода списков. Найденные изображения сортируются по вычисленным оценкам сходства.

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

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

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

• Мультимедиа факторы: Пиксельные данные изображений (как индексируемых, так и запроса) являются основой для извлечения Feature Vectors.
• Структурные факторы (внутри изображения): Критически важными являются Geometry data — пространственные характеристики областей признаков. Они включают:
  • Координаты (Position): Положение центра области на изображении (x, y).
  • Масштаб (Scale): Размер области признака.

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

• Feature Space Density (d): Метрика частотности/уникальности визуального слова. Рассчитывается офлайн как количество обучающих векторов в ячейке, деленное на размер ячейки.
• Порог совпадений (Threshold): Минимальное количество общих Visual Words, необходимое для активации оценки сходства.
• Geometric Mapping (Геометрическое отображение): Математическая трансформация координат. Система ищет оптимальное преобразование (например, используя RANSAC), которое наилучшим образом совмещает координаты признаков запроса с координатами признаков найденного изображения.
• Вес визуального слова (W): Множитель для оценки сходства, основанный на плотности. Патент предлагает формулу: