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

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

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

Квантованное представление локального признака изображения. Является элементом предопределенного словаря, созданного путем кластеризации пространства признаков (Feature Vectors).

Feature Region (Область признака)

Локальная область на изображении (например, эллиптическая), из которой извлекаются визуальные признаки.

Image Tile / Region (Тайл / Регион изображения)

Часть изображения, полученная в результате его разбиения (например, сеткой). Используется для кодирования грубого пространственного расположения Feature Region.

Image Tiling (Разбиение на тайлы)

Схема разделения изображения на Image Tiles. В патенте описывается возможность использования разных схем разбиения (different image tiling) для разных визуальных слов.

Feature Descriptor (Дескриптор признаков)

Компактное представление изображения. Состоит из набора элементов, каждый из которых кодирует пару: Visual Word и связанный с ним Image Tile.

Color Descriptor (Цветовой дескриптор)

Компактное представление цветовой информации изображения, например, закодированные репрезентативные значения цветов (средние значения RGB).

Near-duplicate images (Изображения-почти дубликаты)

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

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

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

1. Генерация множества векторов признаков (feature vectors) для каждого изображения.
2. Детализация процесса генерации:
   • Определение feature region.
   • Вычисление feature vector из этой области.
   • Квантование вектора в одно из предопределенных visual words.
   • Определение image tile, в котором находится feature region.
   • Ассоциирование visual word с этим image tile.
3. Классификация изображений как near-duplicate images, если они имеют по крайней мере пороговое количество совпадающих visual words, связанных с совпадающими image tiles.

Ядро изобретения — требование совпадения не только визуального контента (Visual Word), но и его пространственного расположения (Image Tile) для идентификации дубликата.

Claim 2 (Зависимый от 1): Вводит ключевую техническую особенность для повышения точности.

1. Определение различного разбиения на тайлы (different image tiling) для каждого visual word в словаре.

Сетка, используемая для определения Image Tile, не фиксирована для всего изображения, а смещается в зависимости от того, какой именно Visual Word анализируется.

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

1. Вычисление смещения (offset) на основе индексного номера visual word.

Claim 7 (Независимый пункт): Описывает метод удаления дубликатов относительно конкретного изображения запроса (Query by Image).

1. Получение изображения запроса (query image) и набора результатов поиска.
2. Генерация feature vectors (с Visual Words и Image Tiles) для изображения запроса и для каждого изображения в результатах.
3. Определение того, что одно или несколько изображений в результатах являются near-duplicate images изображения запроса (на основе порога совпадения).
4. Удаление этих дубликатов из набора результатов поиска.

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

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

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

• Система анализирует изображения из коллекции (Image Collection).
• Выполняются процессы извлечения признаков, квантования (Visual Words) и пространственного кодирования (Image Tiles).
• Генерируются компактные Feature Descriptors и Color Descriptors для каждого изображения.
• Эти дескрипторы сохраняются в Index Database.

RANKING / RERANKING – Ранжирование и Переранжирование
Механизм применяется во время выполнения запроса (online) благодаря компактности дескрипторов.

• Удаление дубликатов (Deduplication): При получении набора результатов поиска система быстро сравнивает их дескрипторы, идентифицирует наборы почти дубликатов и выбирает один репрезентативный результат для показа, подавляя остальные. Это улучшает разнообразие (Diversity) выдачи.
• Фильтрация Query by Image: Если запрос содержит изображение, система использует этот механизм для удаления из выдачи изображений, которые почти идентичны запрошенному (Claim 7).

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

• Коллекция изображений (результаты поиска или индекс).
• Предварительно вычисленный словарь Visual Words и связанные с ними смещения (offsets) для разбиения на тайлы.

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

• Отфильтрованный набор результатов поиска с удаленными дубликатами.
• Идентификаторы наборов изображений-почти дубликатов.

На что влияет

• Конкретные типы контента: Влияет исключительно на изображения. Наибольшее влияние оказывается на типы контента, где часто встречаются вариации одного изображения: стоковые фотографии, изображения товаров в e-commerce, новостные изображения.
• Специфические запросы: Влияет на вертикаль Поиска по Картинкам (Image Search) и обратный поиск по изображению (Reverse Image Search).
• Форматы контента: Влияет на все графические форматы. Патент упоминает, что система может адаптировать пороги для разных типов изображений (например, требовать больше совпадений для чертежей/схем – line drawings).

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

• Триггеры активации: Механизм сравнения активируется при обработке результатов поиска для обеспечения разнообразия или при обработке запроса по изображению.
• Пороговые значения: Ключевыми условиями срабатывания являются:
  • Порог количества совпадающих элементов дескриптора (threshold number of matching visual words associated with matching image tiles).
  • Опционально: Порог цветовой дистанции (threshold color distance).

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

Процесс А: Генерация дескрипторов (Индексация)

1. Извлечение признаков: Для каждого изображения определяются Feature Regions и вычисляются Feature Vectors.
2. Выбор признаков: Выбирается подмножество наиболее значимых Feature Regions (например, на основе размера, контрастности или плотности) для обеспечения компактности дескриптора.
3. Квантование признаков: Каждый выбранный Feature Vector квантуется в ближайший Visual Word из словаря.
4. Пространственное квантование: Для каждого Visual Word определяется уникальное разбиение изображения на тайлы (используя смещение/offset, основанное на индексе слова). Определяется Image Tile, в который попадает признак.
5. Генерация Feature Descriptor: Кодируются пары (Visual Word ID + Image Tile ID) для всех выбранных признаков.
6. Генерация Color Descriptor: Вычисляются и кодируются репрезентативные цветовые значения (например, средние значения RGB, возможно, с фокусом на центр изображения).
7. Сохранение: Дескрипторы сохраняются в индексе.

Процесс Б: Обнаружение почти дубликатов (Сравнение)

1. Выбор пары изображений: Выбирается пара изображений для сравнения.
2. Сравнение цветов (Опционально): Вычисляется дистанция между Color Descriptors. Если дистанция превышает порог, процесс останавливается (не дубликаты).
3. Сравнение признаков: Подсчитывается количество совпадающих элементов в Feature Descriptors. Совпадение требует идентичности как Visual Word ID, так и Image Tile ID.
4. Проверка порога: Определяется, превышает ли количество совпадений установленный порог. Порог может зависеть от типа изображения.
5. Дополнительные проверки (Опционально): Может проверяться, происходят ли совпадения из разных тайлов изображения (для подтверждения глобального сходства композиции).
6. Классификация: Если пороги пройдены, изображения классифицируются как почти дубликаты.

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

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

• Мультимедиа факторы (Пиксельные данные): Система использует необработанные пиксельные данные изображений для извлечения локальных признаков (Feature Vectors) и глобальной цветовой информации (Color Descriptor). Анализируются контраст, текстуры, формы и цвета.

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

• Visual Word ID: Индекс, полученный путем квантования Feature Vector. Словарь создается офлайн путем кластеризации (например, k-means).
• Image Tile ID: Индекс, полученный путем квантования пространственного расположения признака. Используется сетка разбиения, которая может быть смещена уникально для каждого Visual Word (Image Tiling Offset).
• Number of Matching Elements (Количество совпадающих элементов): Метрика схожести Feature Descriptors. Подсчитывает количество пар (Visual Word ID + Image Tile ID), которые идентичны в обоих дескрипторах.
• Color Distance (Цветовая дистанция): Метрика различия Color Descriptors. Упоминается возможность использования L1 расстояния (сумма абсолютных значений разностей) между соответствующими репрезентативными цветовыми значениями.
• Thresholds (Пороги): Предопределенные значения для классификации. Патент упоминает, что пороги могут адаптироваться:
  • Порог цветовой дистанции может зависеть от количества совпадающих визуальных слов.
  • Порог совпадения признаков может зависеть от типа изображения (например, выше для line drawings).

1. Эффективность и скорость обнаружения дубликатов: Патент фокусируется на создании очень компактных дескрипторов, позволяющих проводить сравнение "online" (во время выполнения запроса) без значительных задержек.
2. Важность пространственной информации (Композиция): Ключевым элементом является требование совпадения не только локальных признаков (Visual Words), но и их расположения (Image Tiles). Изображения с одинаковым набором объектов, но разной композицией, не будут считаться дубликатами.
3. Уникальное разбиение на тайлы повышает точность: Использование разного разбиения (different image tiling) для каждого Visual Word (путем смещения сетки) значительно повышает надежность пространственной проверки без увеличения размера дескриптора.
4. Устойчивость к модификациям: Механизм устойчив к типичным изменениям изображений, таким как изменение размера, сжатие, обрезка и незначительные правки (например, добавление небольшого текста или водяного знака).
5. Адаптивные пороги: Система способна адаптировать критерии схожести в зависимости от типа контента (фотографии против схем) и степени совпадения признаков.

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

• Создание уникального визуального контента: Приоритет отдается созданию собственных фотографий и графики. Если объекты на фото и их композиция уникальны, система не классифицирует контент как дубликат, используя описанный механизм сравнения Visual Words и Image Tiles.
• Уникальные фото для E-commerce: Для интернет-магазинов критически важно использовать собственные фотографии товаров, а не стандартные изображения от производителя. Используйте разные ракурсы, уникальный фон и композиции. Это помогает избежать кластеризации с конкурентами и повышает шансы на видимость в Image Search.
• Значительная модификация стоковых изображений: Если используются стоковые изображения, их необходимо существенно модифицировать, чтобы изменить базовые Feature Vectors и их расположение. Это должно быть нечто большее, чем просто обрезка или изменение размера (например, интеграция в сложный коллаж или дизайн).
• Использование высококачественных изображений: Система выбирает наиболее значимые признаки (feature regions) для генерации дескриптора, часто основываясь на контрастности и размере. Четкие, высококачественные изображения позволяют системе лучше идентифицировать уникальные признаки и могут быть выбраны в качестве канонической версии.

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

• Создание псевдо-уникального контента: Попытки "уникализировать" изображения путем незначительных изменений (изменение размера, добавление водяного знака, рамки, изменение сжатия) неэффективны. Описанный механизм классифицирует такие изображения как near-duplicates.
• Массовое использование стоковых фото без изменений: Такие изображения с высокой вероятностью будут классифицированы как дубликаты изображений на других сайтах и могут быть подавлены в выдаче.
• Использование идентичных изображений для разных товаров: Использование одного и того же изображения для разных SKU (например, отличающихся незначительными деталями) приведет к тому, что только одно из них будет представлено в поиске по картинкам.

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

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

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

Сценарий: Дедупликация фотографий товара в E-commerce

1. Ситуация: Производитель предоставил официальное фото нового смартфона (Изображение А). Десять разных интернет-магазинов используют это фото. Один магазин сделал собственное фото этого же смартфона с другого ракурса и на другом фоне (Изображение Б).
2. Обработка Google:
   • Система индексирует все 11 изображений и вычисляет Feature Descriptors.
   • При сравнении дескрипторов 10 копий Изображения А система обнаруживает высокое количество совпадающих Visual Words в одинаковых Image Tiles. Они классифицируются как почти дубликаты.
   • При сравнении Изображения А и Изображения Б система обнаружит много совпадающих Visual Words (тот же объект), но из-за изменения ракурса и фона они будут находиться в разных Image Tiles. Они НЕ будут классифицированы как почти дубликаты.
3. Результат в выдаче: В Google Images по запросу модели смартфона Google покажет Изображение А (выбрав одну каноническую версию из 10 копий) и Изображение Б. Девять дубликатов Изображения А будут отфильтрованы.