Поиск похожих изображений, перцептивный хеш

[zcorvid]

Общая задача - распознавание образов. Конкретика не столь важна (могу её, если интересно, отдельно на правах оффтопа описать), частная задача, которую нужно решить состоит в следующем. Имеется набор типовых изображений (например, набор шаблонов символов), на вход подаются различные изображение, нужно по каждому принять решение - является ли картинка изображением символа.

Для простоты считается, что входные изображения уже правильно обрезаны (то есть, скажем, изображение буквы "O" и такое же её изображение, но смещённое в правый нижний угол, так что осталось много свободного места, будем считать совсем разными изображениями).

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

Теперь задача усложняется. Входные изображения могут быть искажены не только преобразованием растяжения (диагональная матрица 2x2), допустимо искажение поворотом, либо преобразованием смещения:

$$ R_{\varphi} = \begin{pmatrix} \cos\varphi& -\sin\varphi \\ \sin\varphi& \cos\varphi \end{pmatrix} $$ $$ S_{\alpha} = \begin{pmatrix} 1& \alpha \\ 0& 1 \end{pmatrix} $$

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

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

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

В большей степени вопрос касается сдвигов $S_{\alpha}$, так как поворот можно побороть другим методом, попросту подобрав его с помощью свёрток (это не очень хороший метод, но хоть что-то).

На всякий случай привожу вариант математической постановки вопроса, вдруг кто-то предложит решение прямо этой общей задачи. (Формулировка не претендует на максимальную строгость).

(Общая постановка задачи)

Есть два изображения $A_1$, $A_2$, пусть $F$ - некий функционал различия изображений (метрика), пусть $N$ - норма на пространстве $GL(2, \mathbb{R})$, нужно найти функционал $F$ и норму $N$, чтобы функционал $\Phi(A_1, A_2) := \min_{P \in GL(2, \mathbb{R})} \{F(A_1, PA_2)\}$ был адекватной мерой похожести изображений (то есть, он хотя бы должен равняться нулю, если изображения получены друг из друга аффинным преобразованием), при этом нужно, чтобы функционал $\Phi$ можно было алгоритмически не слишком сложно считать.

[bondkim137]

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