32
должны были удовлетворять высоким показателям точности при
сравнении изображений.
Применение алгоритма FED - Fast Explicit Diffusion [26] на
пирамидальной схеме позволяет построить нелинейную многомасштабную
пирамиду. Применение нелинейного коэффициента масштабирования
позволяет увеличить скорость нахождения нужной особой точки по
сравнению с Гауссовой пирамидой:
Вычисление данного коэффициента основано на изменении яркости
изображения при масштабировании.
Детектор.
Для каждого октавы
в пирамиде вычисляется определитель
Гессиана.
где
нормализированный относительно масштаба
коэффициент, для вычисления
с учетом размера октавы
Производные второго порядка вычисляются с помощью фильтра
Шарра[11] с шагом
. Данный фильтр позволяет учитывать
ориентацию особых точек. С помощью такого подхода ищем такие точки в
октаве, значение фильтра которых выше заданного порога и является
наибольшим из окрестности точки пикселей.
Далее, для каждой точки из потенциальных максимумов
сравнивается её значение относительно результатов в соседних октавах
в окне размером
соответственно. В итоге расположение
особой точки оценивается с субпиксельной точностью соответствуя
квадратичной функции к определителю Гессиана в соседних
пикселей для поиска максимума.
Дескриптор M-LDB.
33
Первоначальный дескриптор LDB [27] основывался на тех же
принципах что и рассмотренный выше BRIEF, но к сравнениям яркостных
показателей областей добавили сравнение значений градиентов яркости по
оси и , в итоге результат одного теста состоит из трех битов вместо
одного. Проведение тестов проводилось в окне размером
пикселей, деленном на 4, 9 и 16 областей.
Но LDB имеет недостатки такие как не инвариантность к вращению
и масштабированию. И в качестве решения этих проблем в AKAZE
используется его улучшенная версия – M-LDB:
Окно дескриптора ориентируется по ориентации особой точки.
Инвариантность к масштабу получена с помощью выбора размера
окна дескриптора в зависимости от размера октавы
в которой найдена
его особая точка.
В отличии от LDB в M-LDB тесты проводятся не между средним
значением всех пикселей в области, а между заданным их количеством в
зависимости от размера
. Что позволяет ускорить вычисление
дескриптора.
Итоговый бинарный дескриптор имеет длину 486 по три
составляющих. [24]
1.5.2.7. FREAK
Особенностью алгоритма FREAK (Fast Retina Keypoints) является
использование распределения, аналогичного сетчатке глаза, в которой
размер просматриваемого окна увеличивается при удалении от центра.
Плотность точек при этом падает экспоненциально при удалении от
центра. Для снижения чувствительности к шуму каждая окрестность
точки, соответствующей нервной клетке, должна быть сглажена.
Алгоритмы BRIEF и ORB используют одно ядро сглаживания для разных
окрестностей. По аналогии с сетчаткой предлагается использовать разные
34
ядра сглаживания как в алгоритме BRISK. Отличие FREAK заключается в
экспоненциальном росте радиусов окрестностей и перекрывании полей.
Рисунок 16. Плотность ганглиозных клеток сетчатки (слева) и области
сетчатки (справа) [29]
Рисунок 17. Иллюстрация окрестностей точек по методу FREAK в
наложении на соответствующие области сетчатки [29]
Каждый круг (Рисунок 17) представляет собой стандартное
отклонение гауссова ядра, применяемого к соответствующим точкам
выборки. Для построения бинарных дескрипторов F используется
пороговая разница между парами рецептивного поля с соответствующими
им ядрами Гауссиан. То есть, F представляет собой двоичные строки,
формируемые с помощью последовательности однобитовых разниц по
Гауссу
????
????
где Pa – пары рецептивных полей, N – выбранный размер дескриптора,
35
????
????
????
????
где
– сглаженная яркость поля P.
Авторы алгоритма предлагают некоторые наборы пар, сопоставив
средние яркости которых можно построить бинарный вектор,
описывающий любую точку. После чего вопрос поиска соответствий
сводится к вопросу поиска минимальных расстояний между векторами
признаков.
1.5.2.8. DAISY
Детектор DAISY разработан для решения задачи сопоставления
изображений в случае значительных внешних изменений, т.е. данный
дескриптор в отличие от ранее рассмотренных работает на плотном
множестве пикселей и вычисляет дескриптор для каждого пикселя
изображения. При этом авторы DAISY в работе [32] показали, что
дескриптор работает в 66 раз быстрее, чем SIFT, запущенный на плотном
множестве пикселей. В DAISY использованы идеи построения SIFT
дескриптора. Выбирается круговая окрестность особой точки (см. Рисунок
18).
Рисунок 18. Сетка построения окрестностей
Для каждой окрестности выполняется та же последовательность
36
действий, что и в алгоритме SIFT, но взвешенная сумма магнитуд
градиентов заменяется сверткой исходного изображения с производными
Гауссова фильтра, взятыми по 8 направлениям. Авторы [32] показали, что
построенный дескриптор обладает инвариантностью, как и SIFT, при этом
для решения задачи сопоставления в случае, когда все пиксели считаются
особыми, требует меньших вычислительных затрат.
1.6. Методы поиска инвариантов
1.6.1. LogPolar – полярно-логарифмическое преобразование
Рассмотрение лог-полярных преобразований имеет биологическое
обоснование. Первые достоверные доказательства логполярного
сопоставления в визуальной системе приматов были представлены в [49] и
[50]. Лог-полярное отображение является принятой моделью
представления в первичной зрительной коре приматов [51] - [53].
Лог-полярное преобразование имеет два основных преимущества:
1) инвариантность к вращению и масштабу, и 2) пространственно
изменяющаяся выборка в сетчатке является решением для уменьшения
объема информации, проходящей через оптический нерв при сохранении
высокого разрешения в ямке и захвате широкого поля зрения. Это
сокращение полосы пропускания помогает нам обрабатывать изображение
с высоким разрешением только в фокусе внимания, осознавая более
широкое поле зрения.
Некоторые исследователи разрабатывают лог-полярные датчики для
перспективных применений. Эти усилия направлены на перенос
принципов из «биологического» в аппаратное обеспечение СБИС.
Рассмотрим полярную систему координат (r,θ), где r обозначает
радиальное расстояние от центра (xc , yc ) и θ обозначает полярный угол.
Любая точка изображения с координатами (x, y) может быть представлена
в полярных координатах (r,θ))
37
????
????
????
????
Применяя полярное координатное преобразование к изображению I,
отобразим радиальные строки в декартовой системе координат к
горизонтальным строкам в полярном координатном пространстве.
Преобразованное изображение обозначим Ip.
Преимущество этого нового координатного пространства в том, что
простое масштабирование и вращение в этой системе координат могут
быть получен изменением значений (r,θ). С помощью коэффициента
масштабирования α в декартовом пространстве изображение I(x,y)
отображается на I(αx, αy). Чтобы определить коэффициент
масштабирования в логарифмическом пространстве применим
преобразование:
????
????
????
????
????
????
????
????
????
????
???? ????
(а) (б)
Рисунок 19. Изображение чипа от Образца 1 (а) и его полярно-
логарифмическое преобразование (б)
38
1.6.2. GI - геометрические инварианты
Под геометрическими инвариантами поднимается преобразование,
позволяющее выявить на обрабатываем изображении объекты по их
формам, свойства которых соответствуют, после аналогичных
преобразований, формам на шаблоне. Например, в контексте специфики
поиска электрических компонентов, такими формами могут быть
прямоугольные контуры корпусов микросхем либо их коллекции контуров
элементов внутри микросхемы.
Поиск форм и вычисление их характеристик выполняется
посредством составления замкнутых контуров объектов, с последующей
оценкой соотношения их сторон, занимаемой площади, либо отношение
занимаемой площади к площади минимального описывающего
прямоугольника (окружности), и т.п.
В разработанной программе отдельный модуль посвящен
исследованию подобных преобразований. OpenCV предоставляет
дифференциальный набор различных функций, и их можно использовать
как элементарные составляющие такого алгоритма. Как следствие,
алгоритм требует настройки большого количества входных параметров.
Тем не менее, по опыту программирования метода, это является
преимуществом, поскольку позволяет не только гибко настроить алгоритм
посредством параметрирования отдельных его шагов, но также позволяет
менять местами этапы, добавлять или убирать некоторые из них.
Кроме того, метод может быть сконфигурирован под разные
образцы, работает независимо от угла поворота объектов, не требует
применения оконных функций, нечувствителен к количеству объектов.
Для прямоугольных объектов применим алгоритм вычисления угла
поворота.
Пример последовательности при обработке Образцов 1, 2 и 3:
39
- Исходное изображение (см. Рисунок 20, а)
- Применение фильтра (см. Рисунок 20, б). В зависимости от
параметров метода, выполняет побитовое инвертирование, применяет
билатеральный фильтр, либо фильтр Гаусса. Также на данном этапе
выполняется оператор Erode и Dilation (утоньшение и утолщение границ).
- Морфологическое преобразование (см. Рисунок 20, в)
- Поиск контуров (см. Рисунок 20, г)
- Результат работы алгоритма – обнаружение структур,
соответствующих заданным параметрам формы (см. Рисунок 20, д,
Рисунок 21, г)
- Результат вычисления угла поворота объектов (см. Рисунок 20, е)
(а) (б) (в)
(г) (д) (е)
Рисунок 20. Этапы преобразования изображения в методе геометрических
инвариантов
40
(а) (б) (в) (г)
Рисунок 21. Окна конфигуратора метода геометрических инвариантов
Таким образом, выделение образов объектов на изображении
сводится к следующей последовательности:
- такое преобразование образа объекта, чтобы контуры однозначно
соответствовали его геометрической форме или форме какого-либо его
участка,
- сохранение последовательности преобразований и их параметров,
- применение сохраненной последовательности к изображению, на
котором выполняется поиск,
- корректировка параметров с учетом появившегося фона и их
сохранение (ручное дообучение алгоритма).
Листинг не представлен из-за большого объема кода.
41
ГЛАВА 2. Разработка метода получения координат объектов
2.1 Сравнение рассмотренных алгоритмов
2.1.1 Сравнение времени работы
В таблице ниже приведены данные, полученные при исследовании
методов поиска шаблона соответствующего образца на изображении, где
(для образцов 1, 2 и 3) были дублирующиеся объекты, и (для образцов 4 и
5) – однотонный фон рабочего стола установки (случай с треем не
проверялся, т.к. соответствует случаю с пластиной, и не все алгоритмы
корректно работают).
Время поиска одного объекта, миллисекунд
Метод
Образец 1
Образец 2
Образец 3
Образец 4
Образец 5
MatchTemplate
198
170
141
178
150
Особые точки
(лучший р-т)
1177
1200
1250
800
950
LogPolar
2500
2480
2400
2000
1980
GI
180
148
120
50
45
2.1.2 Выявленные недостатки
2.1.2.1 Прямое сопоставление
Метод MatchTemplate ограничен в использовании – линейное
построчное сканирование прямоугольным окном подразумевает
игнорирование разницы угла между шаблоном объекта и его образом на
исследуемом изображении. Чтобы обеспечить вычисление угла,
необходимо вызывать функцию сканирования в цикле, каждый раз меняя
угол поворота шаблона. Угол в цикле, в котором коэффициент