Алгоритм сравнения изображений

Алгоритм сравнения изображений

Сообщение re1aps » 17 апр 2012, 20:41

Актуальность
И так сейчас довольно актуальна задача сравнения изображений в той или иной сфере, будь то поиск нечетких дубликатов изображений, аутентификация при помощи распознавания лиц, составление панорам, выделение объектов на изображениях(полученных например с камеры робота или спутника), данный список можно дополнять часами, но я этого делать не буду, ибо смысл понятен. Почитав литературу и добрую часть постов на эту тему, я решил сделать вывести свой алгоритм для сравнения изображений, т.к. существующие алгоритмы обладают следующими недостатками:
1. Требуют больших временных затрат.
2. Необходимо обладать довольно мощным аппаратным обеспечением для их реализации.
3. Эффективность и область данных алгоритмов двояка.
4. Большая часть алгоритмов запатентована.
5. Ну и соответственно нет алгоритма решающего все вышеперечисленные пункты в полном объеме.
Проблематика
Проблемы которые возникают при разработке данных алгоритмов могут быть следующие:
1. Масштаб - т.е. одинаковые изображения могут быть разного масштаба и соответственно компьютер считает их разными.
2. Помехи, искажения, фон - т.е. абсолютно одинаковые изображения могут быть зашумлены, искажены либо же иметь разный фон и соответственно компьютер посчитает их разными.
3. Вращение - т.е предложенный алгоритм должен быть инвариантен ко вращению изображения.
Понятно, что данный список как и в случае с областью применения данного алгоритма можно продолжать часами, поэтому я описал лишь ключевые моменты.Соответственно наша задача заключается в том, чтобы предложить такой вариант алгоритма, который бы решал основные проблемы при сравнении изображений.
Решение вышеописанной задачи
Все мы понимаем, что можем взять и влоб(попиксельно), повернув на все углы, взять в разных масштабах и что только в голову не взбредет, сравнить изображения. Но представте какие вычислительные мощности нам понадобятся для этого? ответ прост - это теоретически не реально реализовать, а затем расчитать. Я выше не написал, но мы можем сравнивать не только 2 картинки между собой, а коллекцию(множество) картинок между собой, собственно в большинстве случаев это и приходится делать. Как и во всех современных алгоритмах присущих этой тематике, я предлагаю выделять на изображении особые точки. Особой называется такая точка на изображении которая является уникальной именно на данном изображении(фактически это группа пикселей), в свою очередь, на изображении это могут быть:
1. Резкие перепады яркости
2. Небольшие геометрические фигуры
3. Углы
4. Края линий
5. И т.п.
Для чего нам нужны ключевые точки? ответ прост - для того, чтобы не сравнивать изображение полностью, а сравнивать лишь области с ключевыми точками. В результате нагрузка на вычислительные узлы становится гораздо меньше, а точность сравнения увеличивается за счет инвариантности ключевых точек к масштабированию, повороту и т.п., об это далее. В целом, принцип выбора ключевых точек не важен. Главное что бы их было не слишком много и они присутствовали на изображении всегда. А почему вокруг точек выделяются малые участки? А вот почему. Чем меньше участок, тем меньше на него влияют крупномасштабные искажения. Так, если объект в целом, подвержен эффекту перспективы (то есть ближний край объекта имеет больший видимый размер, чем дальний), то для малого его участка явлением перспективы можно пренебречь и заменить на изменение масштаба. Аналогично, небольшой поворот объекта вокруг некоторой оси может сильно изменить картинку объекта в целом, но малые участки изменятся чуть-чуть.С другой стороны, участок вокруг ключевой точки не должен быть слишком мал. Очень малые участки несут слишком мало информации об изображении и с большей вероятностью могут случайно совпадать между собой.
Алгоритм
Весь алгоритм можно расписать в несколько шагов:
1. Приводим изображение к серому цвету и сжимаем его до размерности 100х100.
2. При помощи DoG (Difference of Gaussian) находим особые точки изображения.
3. По найденным ключевым точках выделяем область для последующего сравнения.
4. Приводим область к одинаковому размеру и пикселизируем (квантуем).
5. Выполняем попиксельное сравнение изображений.
Пояснения некоторых шагов
Шаг 2: Что такое DoG?
Основным моментом в детектировании особых точек является построение пирамиды гауссианов (Gaussian) и разностей гауссианов (Difference of Gaussian, DoG). Гауссианом (или изображением, размытым гауссовым фильтром) является изображение
b0ade808a50d9b0857fb5b2cf3525aa8.png
b0ade808a50d9b0857fb5b2cf3525aa8.png (5.65 КБ) Просмотров: 30653

Здесь L — значение гауссиана в точке с координатами (x,y), а sigma — радиус размытия. G — гауссово ядро, I — значение исходного изображения, * — операция свертки.
Разностью гауссианов называют изображение, полученное путем попиксельного вычитания одного гауссина исходного изображения из гауссиана с другим радиусом размытия.
b8f91eacbbd6f1280f43059bb7633184.png
b8f91eacbbd6f1280f43059bb7633184.png (12 КБ) Просмотров: 30653

В двух словах скажем о масштабируемых пространствах. Масштабируемым пространством изображения является набор всевозможных, сглаженных некоторым фильтром, версий исходного изображения. Доказано, что гауссово масштабируемое пространство является линейным, инвариантным относительно сдвигов, вращений, масштаба, не смещающим локальные экстремумы, и обладает свойством полугрупп. Для нас важно, что различная степень размытия изображения гауссовым фильтром может быть принята за исходное изображение, взятое в некотором масштабе.
В общем, инвариантность относительно масштаба достигается за счет нахождения ключевых точек для исходного изображения, взятого в разных масштабах. Для этого строится пирамида гауссианов: все масштабируемое пространство разбивается на некоторые участки — октавы, причем часть масштабируемого пространства, занимаемого следующей октавой, в два раза больше части, занимаемой предыдущей. К тому же, при переходе от одной октавы к другой делается ресэмплинг изображения, его размеры уменьшаются вдвое. Естественно, что каждая октава охватывает бесконечное множество гауссианов изображения, поэтому строится только некоторое их количество N, с определенным шагом по радиусу размытия. С тем же шагом достраиваются два дополнительных гауссиана (всего получается N+2), выходящие за пределы октавы. Далее будет видно, зачем это нужно. Масштаб первого изображения следующей октавы равен масштабу изображения из предыдущей октавы с номером N.
Параллельно с построением пирамиды гауссианов, строится пирамида разностей гауссианов, состоящая из разностей соседних изображений в пирамиде гауссианов. Соответственно, количество изображений в этой пирамиде будет N+1.
60a0638879b89bfc5bcc6584ca3ff112.png
60a0638879b89bfc5bcc6584ca3ff112.png (97.05 КБ) Просмотров: 30653

На рисунке слева изображена пирамида гауссианов, а справа — их разностей. Схематично показано, что каждая разность получается из двух соседних гауссианов, количество разностей на единицу меньше количества гауссианов, при переходе к следующей октаве размер изображений уменьшается вдвое
После построения пирамид дело остаётся за малым. Будем считать точку особой, если она является локальным экстремумом разности гауссианов. Для поиска экстремумов будем использовать метод, схематично изображенный на рисунке
c6f8188b199623b4937bf6a1b66df25c.png
c6f8188b199623b4937bf6a1b66df25c.png (34.47 КБ) Просмотров: 30653

Если значение разности гауссианов в точке, помеченной крестиком, больше (меньше) всех значений в точках, помеченных кругляшками, то эта точка считается точкой экстремума
В каждом изображении из пирамиды DoG ищутся точки локального экстремума. Каждая точка текущего изображения DoG сравнивается с её восьмью соседями и с девятью соседями в DoG, находящихся на уровень выше и ниже в пирамиде. Если эта точка больше (меньше) всех соседей, то она принимается за точку локального экстремума.
Думаю теперь должно быть понятно, зачем нам понадобились «лишние» изображения в октаве. Для того, чтобы проверить на наличие точек экстремума N'e изображение в DoG пирамиде, нужно иметь N+1'е. А для того, чтобы получить N+1'е в DoG пирамиде, надо иметь N+1'е и N+2'е изображения в пирамиде гауссианов. Следуя той же логике можно сказать, что нужно строить 0'е изображение (для проверки 1'го) в пирамиде DoG и ещё два в пирамиде гауссианов. Но вспомнив, что 1'е изображение в текущей октаве имеет тот же масштаб, что и N'е в предыдущей (которое уже должно быть проверено) можем немного расслабиться и читать дальше.
Шаг 5: Сравнение изображений
Для определения похожести изображений будем использовать меру близости – D. Тогда похожесть изображений можно вычислить использую следующую формулу:
ыв.png
ыв.png (4.11 КБ) Просмотров: 30653
, где I1,I2 сравниваемые изображения.
Для большей наглядности метода можно выразить похожесть изображений в процентах, для этого можно воспользоваться формулой:
ф.jpeg
ф.jpeg (5.15 КБ) Просмотров: 30653
, где 255 максимальная величина цветовой шкалы(напомню я использую оттенки серого), например для hsv было бы 360.
Заключение
В заключении хотелось бы сказать, что алгоритм хорош пока только в теории, на практике попытаюсь реализовать его в ближайшее время(когда оно собственно будет :) ), конечно если кто хочет посодействовать - я не откажусь. Задавайте вопросы, делайте конструктивные замечания, ну все в этом духе.

Статья написана специально для развития ресурса robocraft.ru. При написании статьи использовал материалы с сайтов wikipedia и habrahabr.
re1aps
 
Сообщения: 12
Зарегистрирован: 14 апр 2012, 14:35
programming: C++, python

Re: Алгоритм сравнения изображений

Сообщение noonv » 18 апр 2012, 07:48

гм... т.е. получается что-то вроде SIFT-а на жёстко ресайзнутой картинке, но вместо рассчёта дескрипторов - предлагается сравнивать окрестности ключевых точек по корреляции?
Аватара пользователя
noonv
Администратор
 
Сообщения: 557
Зарегистрирован: 05 май 2011, 15:44
Откуда: Калининград
programming: С++

Re: Алгоритм сравнения изображений

Сообщение re1aps » 18 апр 2012, 08:47

noonv писал(а):гм... т.е. получается что-то вроде SIFT-а на жёстко ресайзнутой картинке, но вместо рассчёта дескрипторов - предлагается сравнивать окрестности ключевых точек по корреляции?

Если сказать проще, то от сифта только DoG, который можно использовать где угодно :) проще говоря при помощи DoG мы определяем ключевые точки, чтобы определить границы на изображении, затем склеить интересную область изображения состоящую из этих ключевых точек, получится как бы некая маленькая область на изображении, которую мы и будем сравнивать.
re1aps
 
Сообщения: 12
Зарегистрирован: 14 апр 2012, 14:35
programming: C++, python


Вернуться в Идеи

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

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

cron
© 2009-2021 |  Top.Mail.Ru О проекте  |  Политика Конфиденциальности  |