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

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

Ambiguous Signature (Неоднозначная сигнатура)

Сигнатура, которая имеет высокую вероятность изменения при незначительных сдвигах позиций слов. Это может произойти из-за "переключения" (flipping) дискретного значения угла или "перестановки" (swapping) порядка соседей.

Bounding Box (Ограничивающая рамка)

Прямоугольная область, содержащая слово. Используется для определения позиции слова (например, её центра).

Connected Components (Связанные компоненты)

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

Discretization (Дискретизация)

Процесс преобразования непрерывного значения угла в одно из фиксированного набора дискретных значений для уменьшения размера сигнатуры.

Focus Word (Фокусное слово)

Конкретное слово на странице, для которого в данный момент генерируется сигнатура.

Jaccard Similarity (Сходство Жаккара, Js, Jb)

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

kBitPerAngle

Параметр, определяющий количество бит для дискретизации угла. Например, 4 бита кодируют 16 возможных угловых диапазонов.

kNNCount (N)

Параметр, определяющий количество ближайших соседей (k-Nearest Neighbors), которые учитываются при генерации сигнатуры.

Signature (Сигнатура)

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

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

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

1. Система определяет позиции множества слов на текстовой странице.
2. Для первого слова (Focus Word) определяются относительные позиции множества вторых слов (соседей).
3. Генерируется значение сигнатуры (Signature), описывающее позиции вторых слов относительно первого.
4. Генерируются дополнительные сигнатуры для других слов на странице.
5. Первый набор сигнатур (для Страницы 1) сравнивается со вторым набором сигнатур (для Страницы 2).
6. Генерируется мера сходства (measure of similarity) на основе сравнения.
7. Мера сходства сохраняется.

Claim 6 (Зависимый от 1): Уточняет, что генерация сигнатуры включает расчет расстояния между первым словом и позициями вторых слов.

Claim 7 (Зависимый от 1): Уточняет, что генерация сигнатуры включает расчет угла между первым словом и позициями вторых слов.

Claim 8 (Зависимый от 7): Детализирует процесс генерации сигнатуры: рассчитанные углы конкатенируются (объединяются), и перед этим они упорядочиваются. (В описании патента уточняется, что упорядочивание основано на расстояниях).

Claim 9 (Зависимый от 7): Детализирует процесс генерации сигнатуры: рассчитанные углы конкатенируются, и перед этим они дискретизируются.

Claim 12 (Зависимый от 1): Указывает, что мера сходства является сходством Жаккара (Jaccard similarity).

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

Этот патент описывает технологию анализа изображений документов (Document Image Analysis) и не вписывается в стандартную архитектуру веб-поиска (сканирование и ранжирование HTML-страниц). Он применяется в специализированных системах.

INDEXING – Индексирование (Специализированное)
Технология используется на этапе обработки специфических корпусов данных, таких как отсканированные книги (Google Books) или коллекции PDF. Система анализирует изображения страниц (Raw page data) и извлекает визуальные признаки — наборы signatures. Эти данные (Page analysis data) сохраняются в индексе для последующего сравнения.

RANKING / RETRIEVAL (Поиск, Специализированный)
Применяется в сценариях, где требуется сравнение изображений:

1. Дедупликация: Сравнение индексированных изображений для поиска дубликатов или выбора наилучшей копии скана из разных источников.
2. Поиск по изображению: Сравнение загруженного пользователем изображения (например, фото страницы в Google Lens) с индексированными signatures для идентификации исходного документа.

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

• Изображение текстовой страницы (например, PNG, JPEG).
• Или данные о расположении слов на странице (например, bounding boxes из PDF).

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

• Набор signatures, характеризующий визуальный макет страницы.
• При сравнении двух страниц — мера их сходства (Similarity measure).

На что влияет

• Конкретные типы контента: Влияет исключительно на сравнение и идентификацию изображений текстовых документов (сканы книг, журналов, PDF-файлы, фотографии документов).
• Языковые ограничения: Система спроектирована так, чтобы быть независимой от языка, поскольку она анализирует только позиции слов, а не их содержание (OCR).

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

• Условия применения: Когда необходимо сравнить два изображения документа на предмет визуального сходства макета, особенно если использование OCR нецелесообразно, невозможно или слишком затратно.
• Сценарии использования (упомянутые в патенте):
  • Контроль качества при автоматическом сканировании книг (выбор лучшего изображения страницы из нескольких копий).
  • Поиск документа по фотографии низкого качества (идентификация книги по фото страницы с мобильного телефона).

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

Этап А: Генерация набора Signatures для страницы

1. Подготовка изображения (Предварительная обработка): Получение изображения. Опционально: преобразование в оттенки серого, нормализация фона, бинаризация, устранение перекосов.
2. Определение позиций слов:
   1. Извлечение слов из изображения с помощью анализа connected components или путем использования информации о bounding boxes.
   2. Фильтрация шума (например, удаление знаков препинания).
   3. Определение точечной позиции для каждого слова (например, расчет центроида).
3. Генерация сигнатур (Итерация по всем словам): Для каждого focus word:
   1. Определение N ближайших слов (kNNCount).
   2. Расчет расстояний (r) до каждого из N соседей.
   3. Расчет углов (a) до каждого из N соседей.
   4. Упорядочивание N соседей на основе рассчитанных расстояний (от ближайшего к дальнему).
   5. Дискретизация рассчитанных углов в соответствии с параметром kBitPerAngle.
   6. Конкатенация (объединение) упорядоченных дискретизированных значений углов для формирования signature.
4. Обработка неоднозначности (Опционально): Идентификация ambiguous signatures (где высока вероятность flipping или swapping). Такие сигнатуры могут быть отфильтрованы или для них могут быть сгенерированы дополнительные варианты.
5. Фильтрация набора (Опционально): Удаление неуникальных signatures из набора для предотвращения ложных срабатываний.
6. Хранение: Сохранение итогового набора signatures для страницы.

Этап Б: Сравнение двух страниц (P1 и P2)

1. Получение наборов Signatures: Извлечение набора S(p1) и S(p2).
2. Расчет сходства: Вычисление Jaccard similarity (Js), как отношение количества совпадающих signatures к общему количеству уникальных signatures в обоих наборах.

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

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

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

• Мультимедиа и Структурные факторы:
  • Пиксельные данные изображения страницы.
  • Геометрическое расположение слов на странице (координаты позиций, bounding boxes).

Патент НЕ использует контентные, ссылочные, поведенческие, временные или любые другие стандартные SEO-факторы.

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

• Расстояние (r) и Угол (a): Рассчитываются между focus word и его соседями. Расстояние используется для упорядочивания, угол – для формирования сигнатуры.
• kNNCount (N) и kBitPerAngle: Параметры, определяющие структуру сигнатуры.
• Jaccard Similarity (Js): Метрика для сравнения страниц P1 и P2 на основе их наборов сигнатур S(p1) и S(p2) (Формула 1 в патенте).

  $J(P1, P2) = \frac{|S(p1) \cap S(p2)|}{|S(p1) \cup S(p2)|}$

• Jaccard Similarity (Jb): Альтернативная метрика сходства, основанная на сравнении bounding boxes после выравнивания изображений (Формула 2 в патенте).

  $J_b(P1, P2) = \frac{\text{MatchCount}(p_1, p_2)}{\text{BoxCount}(p_1) + \text{BoxCount}(p_2) - \text{MatchCount}(p_1, p_2)}$

• Probability of Flip (P_flip): Вероятность того, что сигнатура изменится из-за переключения дискретизированного угла при малом сдвиге позиции слова (Формула 3 в патенте). Используется для обнаружения ambiguous signatures.

  $P_{flip} = 1 - \prod_{i=1}^{N}(1-p(\epsilon_i))$

• Probability of Swap (P_swap): Вероятность того, что сигнатура изменится из-за изменения порядка соседних слов, если их расстояния очень близки (Формула 4 в патенте).

  $P_{swap} = 1 - \prod_{i=1}^{N-1}(1-p(\frac{|r_i - r_{i+1}|}{\frac{1}{2}(|r_i| + |r_{i+1}|)}))$

1. Патент чисто технический и нерелевантен для веб-SEO: Патент описывает внутренние процессы Google, связанные с анализом изображений документов (Computer Vision / Document Image Analysis), без каких-либо прямых рекомендаций или выводов для SEO веб-сайтов.
2. Фокус на геометрии, а не семантике: Технология предназначена для идентификации визуально схожих документов исключительно на основе геометрии расположения слов. Содержание текста (OCR), язык и другие семантические факторы полностью игнорируются.
3. Специфические области применения: Основное применение технологии — это специализированные вертикали (Google Books) и конкретные задачи (дедупликация сканов, поиск по фотографии в Google Lens). Она не используется в основном алгоритме ранжирования веб-поиска.
4. Механизм работы: Ключевым элементом является генерация signature путем кодирования упорядоченных и дискретизированных углов между словом и его ближайшими соседями. Это создает устойчивый к искажениям визуальный идентификатор макета.
5. Эффективное сравнение: Использование дискретных сигнатур и Jaccard similarity позволяет быстро и эффективно сравнивать миллионы изображений документов.

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

Патент является инфраструктурным и описывает технологию анализа изображений документов. Практических выводов и рекомендаций для SEO-специалистов, занимающихся продвижением веб-сайтов (ранжированием в google.com), на основе этого патента нет.

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

Тактик SEO, которые этот патент делает неэффективными или опасными, нет, так как он не связан с факторами ранжирования веб-поиска и не направлен против манипуляций в нем.

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

Стратегического значения для SEO веб-сайтов патент не имеет. Он демонстрирует возможности Google в области компьютерного зрения и обработки изображений документов, но эти технологии не пересекаются со стандартными методами поисковой оптимизации HTML-контента и стратегиями построения E-E-A-T.

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

Практических примеров для SEO нет. Ниже приведен пример использования технологии, описанный в патенте.

Сценарий: Идентификация книги по фотографии страницы

1. Индексирование (Офлайн): Google сканирует миллионы книг (Google Books). Для каждой страницы рассчитывается набор signatures на основе расположения слов и сохраняется в специальном индексе.
2. Запрос пользователя: Пользователь фотографирует страницу книги на мобильный телефон (фото может быть низкого качества или с искажениями) и загружает его (например, через Google Lens).
3. Обработка запроса (Онлайн): Система анализирует фотографию, определяет позиции слов и генерирует набор signatures для этого изображения.
4. Поиск: Система ищет совпадения сгенерированных signatures в своем индексе и подсчитывает количество совпадений для каждой проиндексированной страницы.
5. Результат: Страница книги, имеющая наибольшее сходство Жаккара (Jaccard similarity) с фотографией, идентифицируется как источник. Система возвращает пользователю информацию об этой книге.