(Авто)корреляция, обобщение

[zcorvid]

Под спойлером прикладная задача, мотивирующая вопрос. Задача по распознаванию образов.

(Оффтоп)

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

Постановка: Есть большое изображение, есть маленькое изображение, нужно на большом найти позиции, в которых маленькое изображение является частью большого.

Простейший способ решения - перебрать все потенциальные позиции вхождения и выполнить поточечное сравнение с паттерном. Это довольно долгая процедура, её можно ускорить, если применять дискретное преобразование Фурье. В принципе, этот вариант задачи имеет полное решение.

Формализация решения:

1. Вычислить корреляционную функцию $f$ изображения с паттерном (это можно сделать быстро с помощью БПФ)
2. Проанализировать $f$, приняв по ней решение, в каких точках имеет место вхождение паттерна в изображении (в качестве ответа можно отдать точки, в которых значение корреляции равно размеру паттерна)

На практике этот подход ничего не даст, так как реально бывают искажения. Например паттерн может неточно входить, хочется, чтобы малые искажения не мешали, для этого на втором этапе затем в качестве ответа пойдут точки, в которых значение корреляции, скажем, не меньше, чем $95%$ площади паттерна.

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

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

У нас объекты ищутся на фотографии, в итоге паттерн может оказаться не только сдвинут, но и подвергнут искажению. Для простоты будем считать, что искажение всегда можно описать как аффинное преобразование, таким образом, нужно найти не только сдвиг, но и аффинное преобразование, такие, что они укажут вхождение паттерна в изображение.

Хочется получить аналог первого шага для этой ситуации, некую корреляционную функцию, а также алгоритм её подсчёта быстрее, нежели полный перебор.

Немного рассуждений, как можно было бы строить корреляционную функцию.

Пусть дано евклидово пространство $V$ над полем $F$ и группа $G$, дано действие $G:V$, тогда корреляционная функция это отображение:

$$ \sigma : V \times V \to F^G $$

Для любых $u, v \in V$ определён функционал

$$ \sigma(u, v) : G \to F $$

по формуле

$$ <\sigma(u, v), g> := <u, gv> $$

Такое отображение $\sigma$ обобщает обычную корреляционную функцию, которая получится при $V = \mathbb{R}^n$, $G = \mathbb{Z}/n = <g>$ для $g$ - матрицы циклической перестановки базиса.

Таким образом, для всякого такого действия группы можно определить корреляционную функцию (и автокорреляционную, как композицию диагонального вложения $V \to V \times V \to F$). Для последнего примера эта конструкция как раз даёт всем известную корреляцию.

Если корреляция подсчитана, то можно её анализировать, находя, например, насколько близко от данного элемента проходит орбита какого либо другого элемента (этот "другой" элемент - на самом деле и будет нашим паттерном).

Вопрос - описано ли подобное обобщение где-либо? Насколько подобная теория развита, какие есть хорошо изученные примеры? Есть ли алгоритмы быстрого подсчёта такой функции, кроме обычной для сдвигов?

(Оффтоп)

Кстати о сдвигах. БПФ не единственный алгоритм быстрого поиска вхождений, если нам не требуется подсчёт корреляционной функции, а необходимо лишь найти вхождения, можно пытаться действовать по алгоритмам поиска строк, например КМП алгоритмом, возможно он также имеет обобщения на более сложные случаи, и чем-то похожим можно выполнить более сложный поиск, чем просто поиск вхождения подстроки (а может и КМП можно обобщить так, чтобы он искал нечёткие вхождения, скажем, когда есть совпадение по 9 из 10 символов паттерна).