07 апреля (обновлено 07 мая)

Похожи?

Методы поиска изображений по образцам


Когда мы смотрим на окружающих нас лица людей, предметы, природу, мы не осознаем какой объем работы проделывает наш мозг, что бы обработать весь поток визуальной информации. Нам не составит труда найти знакомого нам человека на фотографии, или отличить здание от памятника. Казалось бы, компьютеры отлично могут хранить огромные объемы информации, картинки, видео и аудио файлы. Что мешает им с такой же легкостью найти фото определенного человека из личной фотогалереи? Этому препятствует ряд моментов:

 

  1. Масштаб. Изображения имеют разный масштаб. Предметы, которые мы воспринимаем как одинаковые, на самом деле занимают разную площадь на разных изображениях.
  2. Место. Интересующий нас объект может находиться в разных местах изображения.
  3. Фон и помехи. Предмет, который мы воспринимаем как что-то отдельное, на изображении никак не выделен, и находится на фоне других предметов. Кроме того, изображение не идеально и может быть подвержено всякого рода искажениям и помехам.
  4. Проекция, вращение и угол обзора. Изображение является лишь двумерной проекцией нашего трехмерного мира. Поэтому поворот объекта и изменение угла обзора кардинальным образом влияют на его двумерную проекцию — изображение. Один и тот же объект может давать совершенно разную картинку, в зависимости от поворота или расстояния до него.


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

Возникает вопрос, какие критерии оценки схожести следует оценивать в описании. Попробуем дискретизировать эту задачу, классифицировав возможные варианты поиска.

1) «Near-dublicates» - изображения фактически одного и того же объекта, сделанных приблизительно с одного ракурса и примерно одной освещенностью.

 

Как частный случай – поиск оригинала изображения по миниатюрной и\или искаженной копии.

2) Похожие по конфигурации сцены, хотя могут быть и разные по назначению

3) «Category-level classification» - изображения из одного класса объектов (сцен)

Каждая из поставленных задач требует использования различных признаков.

Сравнение гистограмм

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


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


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

 

Метод сравнения хеша

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


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


Его можно представить в виде нескольких последовательных шагов.

  1. Уменьшение изображения до некоторого минимального размера, например 8х8px. Этот шаг позволяет избавиться от высоких частот, а также позволяет генерировать хеш инвариантный к пропорциям изображения, так как уменьшается до квадрата. А общее число пикселей становится 64;
  2. Удаление цветовой информации, то есть преобразование изображения в градации серого. Это позволяет во-первых, сократить размер хеша втрое (остается лишь яркостная характеристика, вместо информации о красном, зеленом и синем цветах), а также делает хеш инвариантным к гамме цвета;
  3. производится вычисление средней яркости изображения;
  4. последовательное сравнение каждого из 64 пикселей со средним. Если яркость выше среднего, то отмечаем его как 1, иначе как 0. В результате этого шага мы получаем цепочку из 64 битов.
  5. для сокращения цепочки и упрощения последующего поиска каждая тетрада преобразуется в соответствующее 16-ричное значение. В итоге получается слово из 16 символов.


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


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


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

  1. В случае такого подхода, первоначально берется изображение размером немного больше, например 32х32px;
  2. затем точно также изображение преобразуется в оттенки серого
  3. Применяется DCT-преобразование для всего блока, размером 32х32 (в отличие от алгоритма JPEG сжатия, который использует блоки 8х8);
  4. Сокращение DCT. В то время как блок был 32х32, берут лишь левый верхний блок 8х8. Так как именно там содержатся низкие частоты исходного изображения:
  5. аналогичное первому способу получение бинарной цепочки и преобразование ее в 16-ричныю.

Метод SURF

Для решения задачи 2 и 3 типа, может применяться алгоритм SURF(Speeded Up Robust Feature) или «Ускоренный надежный алгоритм». SURF является одним из самых эффективных и быстрых современных алгоритмов. Кроме того, он является распространенным методом, его реализации есть во многих математических библиотеках.


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

  • иметь другой масштаб
  • быть повернут в плоскости изображения
  • быть в произвольном месте сцены
  • может быть зашумлен, виден не полностью, частично заслонен другими предметами
  • может иметь отличную от образца яркость и контраст
  • его может не быть совсем

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

Решение, как несложно понять, хорошее, но нереализуемое. И вот почему. Пусть образец и сцена имеют типичные размеры — порядка сотен пикселов по вертикали и горизонтали. Посчитав общее число всевозможных шаблонов, их поворотов, масштабов и локализации, а также умножив на число операций попиксельного сравнения, получим около (10^12) операций для поиска и локализации образца на сцене. Кроме того, непосредственное сравнение образца со сценой может дать плохой результат, из-за шумов, искажений, заслонения, объектов фона.

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


В целом, принцип выбора ключевых точек не важен. Главное что бы их было не слишком много и они присутствовали на изображении образца всегда.

Чем меньше участок, тем меньше на него влияют крупномасштабные искажения. Так, если объект в целом, подвержен эффекту перспективы (то есть ближний край объекта имеет больший видимый размер, чем дальний), то для малого его участка явлением перспективы можно пренебречь и заменить на изменение масштаба. Аналогично, небольшой поворот объекта вокруг некоторой оси может сильно изменить картинку объекта в целом, но малые участки изменятся незначительно.

На рисунке показаны особые точки изображения в образце(слева) и на сцене(справа). Несмотря на то, что сцена имеет другой масштаб, угол обзора и частично заслонена другим объектом, ключевые точки достаточно точно идентифицируются.

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


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


Гессиан инвариантен относительно вращения. Но не инвариантен масштабу. Поэтому SURF использует разномасштабные фильтры для нахождения гессианов.
Для каждой ключевой точки считается направление максимального изменения яркости (градиент) и масштаб, взятый из масштабного коэффициента матрицы Гессе.


После нахождения ключевых точек, SURF формирует их дескрипторы. Дескриптор представляет собой набор из 64(либо 128) чисел для каждой ключевой точки. Эти числа отображают флуктуации градиента вокруг ключевой точки (что понимается под флуктуацией — рассмотрим ниже). Поскольку ключевая точка представляет собой максимум гессиана, то это гарантирует, что в окрестности точки должны быть участки с разными градиентами. Таким образом, обеспечивается различие дескрипторов для разных ключевых точек.

Флуктуации градиента окрестностей ключевой точки считаются относительно направления градиента вокруг точки в целом (по всей окрестности ключевой точки). Таким образом, достигается инвариантность дескриптора относительно вращения. Размер же области, на которой считается дескриптор, определяется масштабом матрицы Гессе, что обеспечивает инвариантность относительно масштаба.