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

Описание

Какую задачу решает

Патент решает проблему эффективности и скорости поиска визуально похожих изображений (Content-Based Image Retrieval) в очень больших коллекциях данных. Он направлен на ускорение процесса сопоставления (matching) и оценки сходства (scoring). Основная задача — интегрировать дорогостоящую геометрическую верификацию (проверку пространственного соответствия признаков) непосредственно в этап первичного поиска, избегая задержек и многократного доступа к данным.

Что запатентовано

Запатентована система и метод для быстрого поиска похожих изображений на основе модели «мешка визуальных слов» (Bag-of-Visual-Words). Суть изобретения заключается в методе параллельного обхода нескольких списков соответствия (posting lists) и вычисления оценки сходства на лету (on-the-fly), до того как обход будет завершен. Это достигается за счет хранения геометрических данных (geometry data) признаков непосредственно в posting lists и использования оптимизированной древовидной структуры для управления обходом.

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

Система работает в несколько этапов:

• Индексация: Изображения анализируются, из них извлекаются векторы признаков (feature vectors), которые квантуются в visual words. В индекс (posting lists) сохраняются идентификаторы изображений вместе с geometry data (положение, масштаб) для каждого визуального слова.
• Запрос: Изображение-запрос также конвертируется в набор visual words.
• Параллельный обход: Система одновременно (параллельно) обходит posting lists, соответствующие визуальным словам запроса. Для оптимизации того, какой список продвигать следующим, используется специальная древовидная структура (Tree Structure).
• Оценка на лету: Когда одно и то же изображение встречается в пороговом количестве списков, оно немедленно оценивается. Система использует geometry data, извлеченные прямо из индекса, для выполнения геометрической верификации (проверяя пространственное соответствие признаков).
• Взвешивание: При оценке система учитывает уникальность признаков (Feature Space Density), придавая больший вес редким словам.

Актуальность для SEO

Высокая (для инфраструктуры Image Search / Visual Search). Хотя современные методы поиска изображений все чаще полагаются на нейросетевые эмбеддинги, модель Bag-of-Visual-Words с геометрической верификацией остается фундаментальной технологией, особенно для поиска точных совпадений. Описанные методы оптимизации обхода индекса и интеграции оценки критически важны для систем, работающих в реальном времени с большими объемами данных (например, Google Lens).

Важность для SEO

Патент имеет преимущественно инфраструктурное значение (4/10) и описывает внутренние механизмы движка поиска изображений (Image Search Engine). Он не дает прямых рекомендаций для SEO-специалистов по оптимизации веб-страниц или текстового контента. Однако он критически важен для глубокого понимания того, как Google анализирует визуальное содержание, определяет сходство и идентифицирует объекты на изображениях. Эти знания необходимы для разработки стратегий в области Image SEO и Visual Search.

Детальный разбор

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

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): Множитель для оценки сходства, основанный на плотности. Патент предлагает формулу: $W=e^{0.5\ast (1-2d_i}$

Выводы

1. Инфраструктурный фокус: Патент описывает внутреннюю архитектуру и оптимизацию производительности системы поиска по изображениям (CBIR). Он не имеет отношения к ранжированию веб-страниц в основном поиске.
2. Модель «Bag-of-Visual-Words»: Подтверждается использование модели BoVW, рассматривающей изображения как наборы локальных визуальных признаков (Visual Words).
3. Критичность геометрической верификации: Визуальное сходство определяется не просто наличием одинаковых признаков, но и их пространственным соответствием. Система проверяет, можно ли совместить признаки одного изображения с признаками другого через геометрические трансформации (Geometric Mapping).
4. Оптимизация скорости за счет хранения данных в индексе: Ключевое нововведение — хранение Geometry data непосредственно в Posting Lists. Это позволяет выполнять сложную геометрическую верификацию на лету во время первичного обхода индекса, что радикально ускоряет поиск.
5. Важность уникальности признаков (Feature Space Density): Система использует механизм, аналогичный IDF. Общие, часто встречающиеся визуальные признаки (высокая плотность) имеют меньший вес или игнорируются, в то время как уникальные, редкие признаки (низкая плотность) считаются более важными для определения сходства.
6. Низкоуровневые оптимизации: Google применяет оптимизации на уровне процессора (Conditional Move Instructions) и структур данных (Tree Structure) для достижения максимальной скорости обхода индекса.

Практика

Best practices (это мы делаем)

Практическое применение ограничено областью Image SEO и оптимизацией под визуальный поиск (Visual Search/Google Lens).

• Использование высококачественных и четких изображений: Четкость и хорошее освещение позволяют системе надежно и стабильно извлекать Feature Vectors и определять Visual Words. Это повышает вероятность того, что изображение будет корректно проиндексировано и найдено в визуальном поиске.
• Фокус на визуальной уникальности контента: Создавайте собственные изображения с уникальными объектами или композициями. Изображения, содержащие редкие визуальные признаки (низкая Feature Space Density), будут иметь больший вес при определении сходства и релевантности в визуальном поиске.
• Обеспечение визуальной консистентности (для E-commerce): При публикации нескольких изображений одного товара с разных ракурсов важно сохранять условия съемки. Система способна установить связь между такими изображениями через Geometric Mapping, определив, что это один и тот же объект, несмотря на разную перспективу.

Worst practices (это делать не надо)

• Использование изображений низкого качества: Зашумленные, размытые или сильно сжатые изображения затрудняют извлечение стабильных признаков, что может привести к ошибкам индексации и снижению видимости в поиске по картинкам.
• Злоупотребление шаблонными стоковыми изображениями: Использование исключительно популярных стоковых фото, состоящих из общих визуальных элементов (высокая Feature Space Density), снижает дискриминационную способность изображения. Система может придавать меньший вес таким изображениям при визуальном сопоставлении.
• Искусственные манипуляции с геометрией: Сильное искажение пропорций или добавление графических элементов, нарушающих естественную структуру сцены, может помешать процессу геометрической верификации (например, RANSAC) и снизить оценку сходства при поиске по образцу.

Стратегическое значение

Патент подчеркивает, что для Google Image Search и Visual Search ключевыми факторами являются качество исходных данных (четкость изображения) и уникальность визуальной информации. Для E-commerce и контентных проектов стратегически важно инвестировать в создание собственного, качественного визуального контента. Понимание механизма BoVW и геометрической верификации помогает понять, как работают такие продукты, как Google Lens, и почему они могут находить товары или объекты по пользовательским фотографиям.

Практические примеры

Сценарий: Поиск товара в E-commerce по фотографии пользователя (Visual Search)

1. Действие пользователя: Пользователь фотографирует кроссовок (Изображение-запрос) и загружает его в Google Lens.
2. Обработка запроса: Google извлекает Visual Words из фото (например, логотип, текстура материала, форма подошвы) и их координаты (Geometry Data).
3. Поиск в индексе: Система быстро сканирует Posting Lists в поиске изображений с похожим набором Visual Words.
4. Идентификация кандидата: Система находит студийное фото этого же кроссовка на сайте интернет-магазина. У этого фото много общих Visual Words с запросом.
5. Геометрическая верификация (на лету): Несмотря на разные ракурсы, система использует RANSAC и Geometry data (извлеченные прямо из индекса), чтобы проверить, можно ли совместить признаки. Она определяет, что пространственное расположение логотипа относительно подошвы соответствует геометрической трансформации.
6. Взвешивание: Система придает больший вес уникальным элементам дизайна кроссовка (низкая Feature Space Density) и меньший вес общей форме.
7. Результат: Система определяет высокое визуальное сходство и показывает пользователю ссылку на страницу товара.

Вопросы и ответы