22
шумов), сложнее в программировании, и как правило требуют
увеличенных вычислительных ресурсов. В промышленных установках
таких факторов стараются по максимуму избегать.
Все установки подобного рода оснащены источником равномерного
освещения области, попадающей на изображение. Подборка
интенсивности освещения, угла и цвета – часть этапа настройки
оборудования. В качестве примера, на рисунке ниже изображен один и тот
же объект, снятый при разной интенсивности и угле освещения. Методы
обработки могут показывать разные результаты в сильной зависимости от
освещения.
а) б) в)
Рисунок 9. Фотография объекта при разных условиях освещения
1.5. Методы поиска образов объектов, описание
1.5.1. MatchTemplate - прямое сопоставление
Функция MatchTemplate позволяет выполнить поиск объекта по
заранее отснятому образу - шаблону. Исходный код разработанной
функции с пред- и постобработкой представлен в Приложении А.
Во время ее выполнения изображение шаблона temp
последовательно (скользящим окном) накладывается на исходное
изображение image и между ними вычисляется корреляция, результат
которой заносится в результирующее изображение result. Корреляцию
23
между изображениями можно считать разными способами. Выбор способа
указывается через передачу функции значения параметра method:
1) method=CV_TM_SQDIFF
????
????
????
????
????
????
????
????????
????????
2) method=CV_TM_SQDIFF_NORMED
????
????
????
????
????
????
????
????????
????????
????
????
????
????
????
????
????
????????
????????
3) method=CV_TM_CCORR
????
????
????
????
????
????
????
????????
4) method=CV_TM_CCORR_NORMED
????
????
????
????
????
????
????
????????
????
????
????
????
????
????
????
????????
????????
5) method=CV_TM_CCOEFF
????
????
????
????
????
????
????
????????
,
где
????
????
????
????
????
????
????
????
????
????????
????????????????
???? ????
????
????
????
????
????
????
????
????
????????
????????????????
???? ????
24
6) method=CV_TM_COEFF_NORMED
????
????
????
????
????
????
????
????????
????
????
????
????
????
????
????
????????
????????
(а) (б)
Рисунок 10. Результат работы алгоритма, без поворота (а) и с поворотом до
5° (б)
1.5.2. Поиск особых точек
Метод основан на сопоставлении локальных особенностей двух
изображений. Точку, окрестность которой можно отличить от окрестности
любой другой точки изображения, называют «особой точкой» (feature).
Листинг представлен в Приложении Б.
В [18] Tuytelaars и Mikolajczyk (2006) выделили следующие свойства,
которыми должны обладать особые точки:
Повторяемость (repeatability) – особая точка находится в одном
и том же месте сцены или объекта изображения, несмотря на
изменения точки обзора и освещённости.
Отличительность / информативность
(distinctiveness/informativeness) – окрестности особых точек
25
должны иметь большие отличия друг от друга, так, чтобы
возможно было выделить и сопоставить особые точки.
Локальность (locality) – особая точка должна занимать
небольшую область изображения, чтобы быть уменьшить
вероятность чувствительности к геометрическим и
фотометрическим искажениям между двумя изображениями,
снятых в различных точках обзора.
Количество (quantity) – число обнаруженных особых точек
должно быть достаточно большим, так чтобы их хватило для
обнаружения даже небольших объектов. Однако оптимальное
количество особых точек зависит от предметной области. В
идеале количество обнаруженных особых точек должно
адаптивно определяться с использованием простого и
интуитивного порога. Плотность расположения особых точек
должна отражать информационное содержимое изображения,
чтобы обеспечить его компактное представление.
Точность (accuracy) – обнаруженные особые точки должны
точно локализовываться, как в исходном изображении, так и
взятом в другом масштабе.
Эффективность (efficiency) – время обнаружения особых точек
на изображении должно быть допустимым в критичных по
времени программах.
В качестве окрестности точки берется окно, размер и форма которого
зависит от алгоритма.
Алгоритмы поиска особых точек объединяет использование так
называемых детектора и дескриптора.
Детектор – это способ извлечения особых точек из изображения.
Детектор обеспечивает инвариантность нахождения одних и тех же особых
точек относительно преобразований изображений.
26
Дескриптор - идентификатор особой точки, выделяющий её из
остального множества особых точек, представляет собой числовой или
бинарный вектор определенных параметров. Длина вектора и вид
параметров определяются применяемым алгоритмом. В свою очередь,
дескрипторы должны обеспечивать инвариантность нахождения
соответствия между особыми точками относительно преобразований
изображений [19].
Дескриптор позволяет выделить особую точку из всего их множества
на изображении, что необходимо для сопоставления ключевых пар
особенностей, принадлежащих одному объекту, при сравнении разных
изображений.
В параграфах 1.5.2.1 - 1.5.2.8 рассмотрены некоторые из наиболее
часто используемых дескрипторов, реализованных в OpenCV и
опробованных в проекте.
Метод позволяет определить трансформацию изображения (нас
интересует сдвиг и угол поворота) за один проход алгоритма.
Рисунок 11. Результат работы метода на изображении без дубликатов
1.5.2.1. SURF
Алгоритм SURF (Speeded-Up Robust Features) положительно
зарекомендовал себя в задачах поиска объектов на изображениях, 3D
реконструкции, при сравнении изображений [10, 15, 25, 28].
27
SURF ищет особые точки с помощью матрицы Гессе. Детерминант
матрицы Гессе (т.н. гессиан) достигает экстремума в точках
максимального изменения градиента яркости. Для двумерной функции ее
детерминант определяется следующим образом:
????
????
????
????
????
????
Где H – матрица Гессе,
????
????
– функция изменения градиента яркости.
Гессиан инвариантен относительно поворота. Но не инвариантен к
масштабу. Поэтому метод SURF использует разномасштабные фильтры
для нахождения гессианов. Для каждой ключевой точки считается
градиент и масштаб. Градиент в точке вычисляется с помощью фильтров
Хаара. Размер фильтра берется равным 4s (где s – масштаб особой точки).
Рисунок 12. Фильтры Хаара для вычисления градиента по оси X и Y
(черные области имеют значение -1, белые +1)
Дескриптор представляет собой набор из 64 (либо 128) чисел для
каждой ключевой точки. Эти числа отображают флуктуации градиента
вокруг ключевой точки. Поскольку ключевая точка представляет собой
максимум гессиана, тем самым гарантируется, что в окрестности точки
должны быть участки с разными градиентами. Таким образом,
обеспечивается дисперсия (различие) дескрипторов для разных ключевых
28
точек, за счет чего достигается инвариантность дескриптора относительно
поворота. Размер области, на которой считается дескриптор, определяется
масштабом матрицы Гессе, что обеспечивает инвариантность
относительно масштаба.
1.5.2.2. FAST
Ростен и Драммонд (Edward Rosten and Tom Drummond, 2005) ввели
достаточно успешный алгоритм FAST (Features from Accelerated Segment
Test) – особенности ускоренных испытаний сегмента.
Алгоритм заключается в следующем:
1) Выбрать пиксель P, который является кандидатом в список особых
точек.
2) Выбрать подходящее значение триггера яркости T,
3) Определить окружность длиной 16 пикселей вокруг точки P.
4) Пиксель p является особой точкой, если существует N
последовательных пикселей на окружности, которые ярче чем Ip+T
или темнее чем Ip-T.
Рисунок 13. Определение особой точки алгоритмом FAST [21]
Эксперименты авторов показали, что наименьшее значение N, при
котором особые точки начинают стабильно обнаруживаться, равно N=9.
29
1.5.2.3. BRIEF
Данный дескриптор представляется в виде вектора длиной 256,
состоящего из результатов бинарных тестов вокруг особой точки. В
окрестности 31×31 пиксель сравниваются средние значения яркостей
между x и y, где x,y – области 5×5 пикселей:
????
????
I - средняя яркость выбранной области.
Для достижения инвариантности к вращению область вычисления
дескриптора ориентируется по ориентации особой точки θ.
Все n=256 наборов x
i
и y
i
формируют матрицу S размерностью 2×n. Далее
S с помощью матрицы поворота R_θ ориентируется в соответствии с углом
θ:
S
θ
=R
θ
S.
А сам вектор дескриптора записывается как:
g
n
(I,θ)=f
n
(I)|(x
i
,y
i
) S
θ
,
где f
n
(I)=∑
1≤i≤n
2
i-1
τ(I;x
i
,y
i
).
1.5.2.4. ORB
ORB – Oriented FAST and Rotated BRIEF, представлен в 2011г [23]. В
его основе лежит комбинация алгоритмов FAST и BRIEF, рассмотренные
выше, с некоторыми улучшениями.
Улучшение детектора FAST заключается в предварительном
рассмотрении пикселей с шагом 90°. Выбор только этих четырех пикселей
на окружности позволяет быстро отсеять неподходящие точки. Для
ускорения расчетов принято ограничение в пятьсот особых точек. Если их
больше, применяется детектор углов Харриса, для выбора наиболее
значимых. Для устойчивости к вращению объекта вводится параметр
угловой ориентации , который вычисляется как направление яркости с
наибольшей интенсивностью относительно центральной точки.
30
1.5.2.5. BRISK
BRISK – Binary Robust Invariant Scalable Keypoints, представлен в
2011 году.
Для достижения инвариантности к масштабу, предлагается выбирать
наилучшую особую точку с максимальным значением интенсивности в
пирамиде, которая состоит из октав
и внутренних октав
.
Октавы формируются как сжатие оригинального изображения
в
раза.
Внутренние октавы расположены между
и
и представлены в виде
сжатой
в
раза. Поиск особых точек в октавах осуществляется
детектором FAST.
Рисунок 14. Пример поиска особой точки с максимальным значением S
[23].
Дескриптор BRISK.
Область вокруг особой точки разбивается на 60 участков (рис. 1.3):
????
????
31
Рисунок 15. Область вычисления дескриптора [23].
Множество разбивается на 2а подмножества:
????
????
????
????
где
размер особой точки.
Вычисляется среднее значение градиента множества :
????
????
????
????
????
????
????
????
Дескриптор состоит из бинарной строки длиной 512, заполненной
результатами проведенных тестов в множестве :
????
????
,
где
????
????
интенсивность окрестности радиуса
точки
,
угол направления градиента .
1.5.2.6. KAZE, AKAZE
При разработке данного метода, представленного в 2012 году,
старались добиться высокой скорости работы как детектора, так и
дескриптора. При этом найденные особые точки и их дескрипторы