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

Описание

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

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

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

Запатентован метод автоматической группировки изображений с использованием кластеризации графа, называемого Image Region Graph. Изобретение определяет регионы изображений как вершины графа и использует два типа взвешенных ребер: matching-edges (связи между похожими регионами в разных изображениях) и overlap-edges (связи между регионами внутри одного и того же изображения). Кластеризация этого графа позволяет объединять изображения, изображающие одни и те же объекты или сцены.

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

Система сначала обрабатывает изображения для идентификации interest-points (ключевых точек) и вычисления local descriptors (описаний признаков вокруг этих точек). На основе совпадений дескрипторов определяются регионы. Затем строится граф, где эти регионы являются вершинами. Добавляются взвешенные ребра: matching-edges для связей между изображениями и overlap-edges для связей внутри изображения. После построения графа применяется алгоритм кластеризации (например, иерархическая агломеративная кластеризация) для группировки вершин (vertex-clusters). Изображения, чьи регионы попали в один кластер вершин, объединяются в visual-cluster.

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

Высокая. Хотя патент опубликован в 2012 году, задача автоматической организации и понимания визуального контента остается фундаментальной для Google (Google Images, Google Photos). Базовые принципы компьютерного зрения, описанные в патенте (извлечение признаков, сопоставление дескрипторов, кластеризация сходства), по-прежнему лежат в основе систем идентификации объектов и сцен, хотя конкретные реализации могли эволюционировать.

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

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

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

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

Center-of-gravity (Центр тяжести)

Центральная точка региона, вычисляемая на основе координат входящих в него interest-points. Используется для расчета расстояния в overlap-edges.

Image Region Graph (Граф регионов изображения)

Граф, построенный для коллекции изображений, где вершины представляют регионы изображений, а ребра (matching-edges и overlap-edges) — связи между ними.

Interest-point (Ключевая точка)

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

Local Descriptor / Feature Vector (Локальный дескриптор / Вектор признаков)

Математическое описание набора визуальных признаков в области вокруг interest-point.

Matching-edge (Ребро совпадения)

Ребро графа, соединяющее две вершины (региона), которые визуально совпадают и находятся в разных изображениях. Вес ребра отражает уверенность в совпадении.

Overlap-edge (Ребро перекрытия)

Ребро графа, соединяющее две вершины (региона), которые находятся внутри одного и того же изображения. Вес ребра отражает степень их перекрытия или близости.

Region (Регион)

Набор interest-points на изображении, которые способствуют совпадению с другим изображением. Регион является вершиной (vertex) в Image Region Graph.

Vertex-cluster (Кластер вершин)

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

Visual-cluster (Визуальный кластер)

Группа изображений, полученная в результате кластеризации. Состоит из изображений, чьи регионы принадлежат одному vertex-cluster.

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

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

1. Представление регионов изображений как вершин (vertices) в графе.
2. Соединение пар совпадающих вершин (matching-vertices) с помощью matching-edge. (Совпадающие вершины определяются как представляющие соответствующие регионы в двух разных изображениях).
3. Соединение пар перекрывающихся вершин (overlap-vertices) с помощью overlap-edge. (Перекрывающиеся вершины определяются как представляющие регионы одного и того же изображения).
4. Присвоение весов (weights) всем matching-edges и overlap-edges.
5. Организация графа в visual-clusters.

Claim 4 и 5 (Зависимые): Детализируют веса для matching-edges.

Вес matching-edge основан на уровне уверенности (level of confidence) в соответствующем совпадении. Уровень уверенности, в свою очередь, основан на вероятности того, что совпадение между регионами является ложноположительным (false positive).

Claim 6, 7 и 8 (Зависимые): Детализируют веса для overlap-edges.

Вес overlap-edge основан на уровне перекрытия соответствующих регионов (level of corresponding region overlap). Этот уровень перекрытия основан на расстоянии между centers-of-gravity регионов, а также на размере (size) каждого региона.

Claim 10 (Зависимый): Детализирует шаг организации графа (Claim 1, шаг e).

1. Кластеризация графа для генерации одного или нескольких vertex-clusters (каждый кластер является подграфом).
2. Группировка изображений в visual-clusters на основе этих vertex-clusters.

Claim 12 и 13 (Зависимые): Уточняют метод кластеризации.

Кластеризация может выполняться с использованием иерархического алгоритма кластеризации (hierarchical-clustering algorithm), в частности, иерархической агломеративной кластеризации (hierarchical-agglomerative clustering).

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

Изобретение применяется в системах управления и поиска больших коллекций изображений, таких как Google Images или Google Photos.

INDEXING – Индексирование и извлечение признаков
Это основной этап применения патента. После того как изображения собраны (CRAWLING), на этапе индексации происходит вся обработка:

1. Извлечение признаков: Идентификация interest-points и вычисление local descriptors для каждого изображения.
2. Сопоставление и построение графа: Сравнение изображений, определение регионов и построение Image Region Graph с использованием matching-edges и overlap-edges.
3. Кластеризация: Выполнение кластеризации графа для формирования visual-clusters.
4. Сохранение: Результаты кластеризации сохраняются в базе данных или индексе изображений.

RANKING – Ранжирование
На этапе ранжирования система использует предварительно вычисленные данные о visual-clusters. Это помогает:

• Определять, какие изображения показывают один и тот же объект или тему.
• Выбирать наиболее репрезентативное изображение из кластера (Патент упоминает выбор репрезентативного изображения, например, имеющего наибольшее количество ребер).
• Обеспечивать разнообразие выдачи, избегая показа слишком большого количества похожих изображений из одного кластера.

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

• Коллекция цифровых изображений (Image Corpora).

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

• Image Region Graph (промежуточный результат).
• Vertex-clusters (промежуточный результат).
• Visual-clusters (группы похожих изображений).
• Идентификаторы репрезентативных изображений для кластеров (опционально).

На что влияет

• Конкретные типы контента: Влияет на все типы изображений (фотографии, графика). Особенно эффективно для контента, где есть четкие визуальные признаки, позволяющие идентифицировать объекты, сцены, продукты или достопримечательности.
• Конкретные ниши или тематики: Имеет значительное влияние в E-commerce (группировка фотографий одного и того же товара), Travel (группировка фотографий достопримечательностей), Новости (идентификация изображений, относящихся к одному событию).

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

• При каких условиях работает алгоритм: Алгоритм применяется при обработке коллекции изображений для их организации.
• Триггеры активации: Активируется в процессе индексации новых изображений или при периодическом перестроении индекса для обновления существующих кластеров. Для формирования связей необходимо наличие достаточного количества совпадающих interest-points между изображениями.

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

Фаза 1: Подготовка данных и построение Image Region Graph

1. Идентификация признаков: Для каждого изображения в коллекции определяются interest-points. (Например, с использованием функции Laplacian-of-Gaussian).
2. Вычисление дескрипторов: Для каждой interest-point вычисляется local descriptor (например, с использованием вейвлетов Габора).
3. Сопоставление изображений: Изображения сравниваются путем сопоставления их наборов local descriptors. Определяются пары совпадающих изображений.
4. Определение регионов (Вершин): Идентифицируются регионы — наборы interest-points, которые способствуют совпадению между парой изображений. Каждый регион становится вершиной графа.
5. Добавление Matching-Edges: Добавляются ребра между совпадающими регионами в разных изображениях. Вес назначается на основе уверенности в совпадении (Формула 1 в патенте: обратно пропорционально вероятности ложного срабатывания).
6. Добавление Overlap-Edges: Добавляются ребра между регионами внутри одного изображения. Вес назначается на основе степени перекрытия (Формула 2 в патенте: зависит от расстояния между centers-of-gravity и размеров регионов).

Фаза 2: Кластеризация и Группировка

7. Вычисление расстояний (Опционально): Может быть построен граф кратчайших путей (Shortest Path Graph) для определения расстояния между любыми двумя вершинами.
8. Кластеризация графа: Применяется алгоритм кластеризации (например, иерархическая агломеративная кластеризация). Пары вершин или существующих кластеров с наименьшей стоимостью (весом/расстоянием) итеративно объединяются, пока стоимость не превысит определенный порог. Результат — набор vertex-clusters.
9. Группировка изображений: Изображения группируются в visual-clusters. Visual-cluster состоит из всех изображений, содержащих регионы (вершины) из соответствующего vertex-cluster.
10. Выбор представителя (Опционально): Внутри visual-cluster может быть выбрано репрезентативное изображение (например, изображение с наибольшим количеством matching-edges).

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

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

• Мультимедиа факторы: Основные данные — это пиксельные данные самих изображений. Алгоритм анализирует визуальное содержимое для извлечения interest-points и local descriptors.
• Системные данные: Патент упоминает, что в индекс изображений могут включаться и другие данные (user information, geo-tagging information, tag information), но они не используются в описанном алгоритме построения и кластеризации графа.

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

• Методы анализа изображений:
  • Для обнаружения interest-points: Упоминается использование функции Laplacian-of-Gaussian.
  • Для вычисления local descriptors: Упоминается использование набора вейвлетов Габора (Gabor wavelets).
• Вес (Стоимость) Matching-Edge: Вычисляется по формуле (1) из патента: d_ij = 1 / -log(P_FPij), где P_FPij — вероятность того, что совпадение между регионами i и j является ложноположительным.
• Вес (Стоимость) Overlap-Edge: Вычисляется по формуле (2) из патента. Эта метрика зависит от расстояния между центрами тяжести (centers-of-gravity) двух регионов и их размеров (squared expansion).
• Расстояние между кластерами: Используется в процессе иерархической агломеративной кластеризации. Патент предлагает несколько вариантов расчета расстояния между кластерами n и m (Формулы 4a, 4b, 4c), например, минимальное расстояние между элементами кластеров (4a).
• Алгоритмы: Упоминаются алгоритмы поиска кратчайшего пути (Dijkstra, Floyd-Warshall) и иерархическая агломеративная кластеризация.

Выводы

1. Автоматизация и масштабирование организации изображений: Патент описывает надежный метод для автоматической группировки визуально похожих изображений без необходимости ручного тегирования, что критически важно для масштаба Google.
2. Комплексная модель сходства через граф: Ключевой инновацией является построение Image Region Graph, который учитывает связи как между разными изображениями (matching-edges), так и внутри одного изображения (overlap-edges). Это обеспечивает более точное понимание визуальных связей.
3. Идентификация объектов и сцен: Описанный механизм позволяет системе понять, что разные изображения показывают один и тот же объект, сцену или продукт, даже если они отличаются по масштабу, ракурсу или качеству.
4. Основа для дедупликации и каноникализации: Группировка в visual-clusters является основой для дедупликации результатов поиска изображений и выбора канонического (репрезентативного) изображения для конкретной сущности или темы.
5. Зависимость от качества визуальных признаков: Эффективность системы напрямую зависит от способности извлекать стабильные interest-points и информативные local descriptors из изображений.

Практика

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

• Фокус на четкости и качестве изображений: Создавайте и используйте высококачественные изображения с четкими, хорошо различимыми объектами. Это способствует обнаружению стабильных interest-points и вычислению качественных local descriptors, что необходимо для точного сопоставления и включения в релевантные visual-clusters.
• Предоставление разнообразных ракурсов: Для E-commerce и сайтов, ориентированных на продукты или объекты, предоставляйте несколько высококачественных изображений с разных ракурсов. Это увеличивает количество визуальных связей (matching-edges) с другими изображениями в индексе Google, укрепляя позицию ваших изображений в visual-cluster объекта.
• Создание уникального визуального контента: Инвестируйте в создание уникальных фотографий и графики. Уникальные изображения имеют больше шансов быть выбранными в качестве репрезентативных в visual-cluster по сравнению с широко распространенными стоковыми фотографиями или фотографиями от поставщиков.

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

• Использование изображений низкого качества: Размытые, нечеткие или сильно сжатые изображения не позволят системе надежно извлечь interest-points. Такие изображения вряд ли будут эффективно кластеризованы или высоко ранжированы.
• Манипуляции с дубликатами изображений: Попытки заполнить выдачу путем создания множества почти идентичных изображений (например, с минимальными изменениями цвета, размера или наложением водяных знаков) неэффективны. Система, основанная на сопоставлении local descriptors, распознает их как визуально идентичные и сгруппирует в один кластер, выбрав только одно репрезентативное изображение.
• Игнорирование визуальной составляющей SEO: Фокусировка только на текстовых атрибутах (alt-текст, заголовки) и игнорирование качества и уникальности самого изображения ограничивает потенциал ранжирования в Google Images и других визуальных продуктах Google.

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

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

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

Сценарий: Улучшение видимости товара в Google Images для E-commerce

1. Задача: Повысить трафик на карточку нового товара (например, модель кроссовок) из поиска по картинкам.
2. Действие: Вместо использования 3 стандартных фотографий от производителя, публикуются 10 уникальных высококачественных фотографий: общие планы с разных сторон, крупные планы текстуры материала, фото подошвы, фото на модели.
3. Как это работает (по патенту): Google анализирует эти изображения и извлекает множество четких interest-points и local descriptors (особенно из крупных планов деталей). Система строит Image Region Graph и находит matching-edges с другими изображениями этих кроссовок в интернете (включая фото пользователей и обзоры).
4. Ожидаемый результат: Благодаря большому количеству качественных и уникальных визуальных данных, изображения сайта с большей вероятностью будут включены в visual-cluster этой модели кроссовок. Высокое качество и разнообразие ракурсов увеличивают шанс, что одно из изображений сайта будет выбрано как репрезентативное для кластера при различных запросах пользователей (например, «кроссовки модель X подошва» или «кроссовки модель X купить»).

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