2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки





Начать новую тему Ответить на тему
 
 Поиск похожих изображений, перцептивный хеш
Сообщение17.04.2017, 11:00 
Аватара пользователя


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

Для простоты считается, что входные изображения уже правильно обрезаны (то есть, скажем, изображение буквы "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$ можно было алгоритмически не слишком сложно считать.

 Профиль  
                  
 
 Re: Поиск похожих изображений, перцептивный хеш
Сообщение22.04.2017, 05:49 
Аватара пользователя


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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 2 ] 

Модераторы: Toucan, maxal, Karan, PAV, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group