Особые точки и области

Особые точки и области Определение • Особая точка изображения - это точка с характерной(особой) окрестностью Названия: • Особенность (feature) • Характеристическая / интересная точка (interest point) Детектор и дескриптор Процесс определения особых точек достигается путём использования детектора и дескриптора. • Детектор – это метод извлечения особых точек из изображения. Детектор обеспечивает инвариантность нахождения одних и тех же особых точек относительно преобразований изображений. Дескриптор – идентификатор особой точки, выделяющий её из остального множества особых точек. В свою очередь, дескрипторы должны обеспечивать инвариантность нахождения соответствия между особыми точками относительно преобразований изображений Требования к особенностям • Повторяемость (Repeatability) • Особенность (feature) должна находится в том же месте несмотря на изменения точки обзора и освещения • Значимость (Saliency) • Каждая особенность должна иметь уникальное (distinctive)описание • Компактность и эффективность • Особенностей гораздо меньше .чем пикселей в изображении • Локальность (Locality) • Особенность занимает маленькую область изображения, поэтому работа с ней нечувствительна к перекрытиям Детекторы углов Угол– это точка, у которой в окрестности интенсивность изменяется относительно центра (x,y). Углы определяются по координатам и изменениям яркости окрестных точек изображения. Главное свойство таких точек заключается в том, что в области вокруг угла у градиента изображения преобладают два доминирующих направления, что делает их различимыми. Лапласиан напоминание Виды углов В зависимости от количества пересекаемых граней существуют разные виды углов: L-, Y- (или T-), и Xсвязные (некоторые выделяют еще стреловидно связные углы ). Различные детекторы по-разному реагируют на каждый из таких видов углов. Подходы к определению особых точек • Основанные на интенсивности изображения: особые точки вычисляются напрямую из значений интенсивности пикселей изображения. • Использующие контуры изображения: методы извлекают контуры и ищут места с максимальным значением определяют пересечения. Эти методы чувствительны к окрестностям пересечений, поскольку извлечение часто может быть неправильным в тех местах, где пересекаются 3 или более краев. • На основе использования модели: используются модели с интенсивностью в качестве параметров, которые подстраиваются к изображениям-шаблонам до субпиксельной точности. Имеют ограниченное применение с особыми точками специальных видов (например, L-связными углами), зависят от используемых шаблонов. Детекторы углов • Главное свойство: в области вокруг угла уградиента изображения два доминирующих направления • Уголки хорошо повторяются и различимы Детектор Моравеца Рассматривается изменение яркости окна W (обычно размера 3х3, 5х5, 7х7 пикселей) относительно интересующей точки при сдвиге окна W на 1 пиксель в 8ми направлениях (горизонтальных, вертикальных и диагональных) Алгоритм Функция окна w(x,y) = -1 1 * * * * -1 1 Ищем локальный max в min{E} (u,v)=(1,0),(1,1),(0,1),(-1,1) Алгоритм Для каждого пикселя (x,y) в изображении вычислить изменение интенсивности • Построить карту вероятности нахождения углов в каждом пикселе (x,y) изображения посредством вычисления оценочной функции С(x,y) = min{E}. То есть определяется направление, которому соответствует наименьшее изменение интенсивности, т.к. угол должен иметь смежные ребра. • Отсечь пиксели, в которых значения C(x,y) ниже порогового значения T. • Выбрать E(u,v) имеющее большие значения • Резюме- детектор Моравеца Детектор Моравеца обладает свойством анизотропии в 8 направлениях смещения окна. Основными недостатками рассматриваемого детектора являются отсутствие инвариантности к преобразованию поворота и возникновение ошибок детектирования при наличии большого количества диагональных ребер Детектор Харриса Оптимальным детектором L-связных углов является детектор Харриса. Харрис и Стефенс улучшили детектор, введя анизотропию по всем направлениям, т.е. рассматривают производные яркости изображения для исследования изменений яркости по множеству направлений. Идея Для углов E(u,v) должно быть большой Разложение в ряд Тейлора f(x+u,y+v) = f(x,y) + ufx(x,y)+vfy(x,y)+ 1/2![u2fxx(x,y) + uvfxy(x,y) + v2fyy(x,y)] + 1/3![u3fxxx(x,y) + u2vfxxy(x,y) + uv2fxyy(x,y) + v3fyyy(x,y)] +… Приближение первого порядка: f(x+u,y+v) ~ f(x,y) + ufx(x,y)+vfy(x,y) Математические детали Функция окна w(x,y) = Разложение в ряд Тейлора 2го порядка I(x,y) вокруг (x,y) Математические детали Интерпретация матрицы моментов Градиенты выровнены по осям (вертикальные или горизонтальные) Если одно из λ близко к 0, тогда это не угол, и нужно искать другие точки Собственные вектора/собственные значения Собственные вектора u удовлетворяют уравнению Au = λu где λ – собственное значение det(A – λI) = 0 Пусть А = H(матрица 2х2) Тогда: Собственные вектора: График производных Ix Iy Заполнение эллипса Объяснение Угол характеризуется большими изменениями функции E(x,y) по всем возможным направлениям (x,y), что эквивалентно большим по модулю собственным значениям матрицы M. Мера отклика угла по Харрису. Поскольку напрямую считать собственные значения является трудоёмкой задачей, Харрисом и Стефеном была предложена мера отклика R = detM – k (traceM)2 detM = λ1λ2 traceM = λ1 + λ2 (k = 0.04-0.06) Алгоритм детектора Харриса 1. Вычислить градиент изображения в каждом пикселе с использованием гауссова сглаживания Ix = Gx*I Iy= Gy*I 2. Вычислить матрицу вторых моментов М по окну(по сути) Ix2 = Ix Ix Iy2 = IyIy Ixy = IxIy для каждого пикселя 3. Вычислить отклик R = Det(M) – k(Trace(H)) для каждого пикселя 4. Отсечение по порогу R 5. Найти локальные максимумы функции отклика (nonmaximum suppression) по окрестности заданного радиуса 6. Выбор N самых сильных локальных максимумов? Пример http://docs.opencv.org/2.4/doc/tutorials/features2d/ trackingmotion/harris_detector/harris_detector.html void cornerHarris(InputArray src, OutputArray dst, int blockSize, int ksize, double k, int borderType=BORDER_DEFAULT ) src – Input single-channel 8-bit or floating-point image. dst – Image to store the Harris detector responses. blockSize – Neighborhood size ). ksize – Aperture parameter for the Sobel operator. k – Harris detector free parameter. borderType – Pixel extrapolation method. Детектор Förstner В отличие от детектора Харриса собственные значения вычисляются явно. Функция отклика угла Фёрстнера : R = λ1 λ2 /(λ1+λ2) = detM/trM Детектор Фёрстнера на практике часто используется для расширения возможностей детектора Харриса – нахождению круговых особых точек вместе с углами. https://en.wikipedia.org/wiki/ Corner_detection#The_F.C3.B6rstner_corner_d etector Алгоритм SUSAN (Smallest Univalue Segment Assimilation Nucleus) Углы определяются сегментацией круговы х окрестностей в схожие (оранжевы е) и непохожие (синие) участки. Для каждого пикселя рассматривается круговая область фиксированного радиуса. Центр пикселя назы вается ядром, значение его интенсивности запоминается. Все остальны е пиксели разделяются на 2 категории: в схожие (оранжевы е) и непохожие (синие) участки в зависимости от того, схоже ли значение интенсивности ядра, или нет. Там, где присутствует участок изображения под круговой областью без изменений, схожие участки занимают почти всю площадь, на гранях это отношение падает до 50%, на углах еще уменьшается приблизительно до 25%. Углы находятся там, где относительная площадь схожих участков(similar USAN) достигает локального минимума ниже определенного порога. Алгоритм показы вает хорошую точность ко всем видам углов, но неустойчив к размы тию на изображениях. Алгоритм SUSAN 1. Поместить центр круговой маски(обычно 37) в точку изображения. 2. Внутри круговой маски вычислить разницу интенсивности. 3. Суммировать к-во «похожих»пикселей 4. Для угла область USN будет меньше чем размер маски и будет локальным минимумом 5. Найти центроиды областей USAN и их близость друг относительно друга и определить ложноположительные. 6. Выбрать особые точки с помощью поиска локальных максимумов функции отклика (nonmaximum suppression) Алгоритм FAST (Features from Accelerated Segment Test) Рассматривается окружность из 16 пикселей вокруг точки кандидата P. Точка является угловой, если существуют N смежных пикселей на окружности, интенсивности которых больше Ip +t или интенсивности всех меньше Ip- t, где Ip – интенсивность точки P, t – пороговая величина. Далее необходимо сравнить интенсивность в вертикальных и горизонтальных точках на окружности под номерами 1, 5, 9 и 13 с интенсивностью в точке P (для того, чтобы как можно быстрее отсечь ложные кандидаты). Если для 3 из этих точек выполнится условие Ipi > Ip +t или Ipi < Ip +t, i=1,..,4, то проводится полный тест для всех 16 точек. Эксперименты показали, что наименьшее значение N, при котором особые точки начинают стабильно обнаруживаться, равно N=9. алгоритм имеет ряд недостатков, например, вблизи некоторой окрестности может обнаружится несколько особых точек, эффективность алгоритма зависит от порядка обработки изображения и распределения пикселей. Алгоритм, основанный на кривизне масштабного пространства (curvature scale space,CSS) 1. Применить детектор границ Канни (Canny). 2. Выделить контуры границ из бинарной карты. Проверить концы контуров на смежность с другими. Отметить эту точку как T связный угол, если конец контура соединяется с границей. 3. Вычислить значения кривизны у каждого контура на наибольшем масштабе σhigh . Положить начальными значениями локальные максимумы кривизны, при условии что значение кривизны выше порога t и вдвое выше соседних локальных минимумов. 4. Отсортировать углы по убыванию от самого наибольшего масштаба к меньшему с целью улучшения свойства локализации. 5. Сравнить T связные углы с остальными углами и, если они находятся близко друг у другу, удалить один из углов. Алгоритм, основанный на кривизне масштабного пространства (curvature scale space,CSS) 1. Применить детектор границ Канни (Canny). 2. Вы делить контуры . Проверить концы контуров на смежность с другими. Отметить эту точку как T связны й угол, если конец контура соединяется с границей. 3. Вы числить значения кривизны у каждого контура на наибольшем масштабе σ high . Положить начальны ми значениями локальны е максимумы кривизны , при условии что значение кривизны вы ше порога t и вдвое вы ше соседних локальны х минимумов. 4. Отсортировать углы по убы ванию от самого наибольшего масштаба к меньшему с целью улучшения свойства локализации. 5. Сравнить T связны е углы с остальны ми углами и, если они находятся близко друг у другу, удалить один из углов. T связный промежуток отмечается как угол, а промежуток между концами контуров дозаполняется. Один угол маркируется дважды Преобразование Хафа • Преобразование Хафа — это метод обнаружения прямых и кривых линий на полутоновых или цветных изображениях. Метод позволяет указать параметры семейства кривых и обеспечивает поиск на изображении множества кривых заданного семейства, с использованием процедуры голосования. Процедура голосования применяется к пространству параметров, из которого и получаются объекты определённого класса фигур по локальному максимуму в так называемом накопительном пространстве (accumulator space), которое строится при вычислении трансформации Хафа. Преобразование Хафа для поиска прямых Прямая может быть задана уравнением y = ax + b и может быть вычислена по любой паре точек (x, y) на изображении. Главная идея преобразования Хафа — учесть характеристики прямой не как уравнение, построенное по паре точек изображения, а в терминах её параметров, то есть a — коэффициента наклона и b — точки пересечения с осью ординат. Исходя из этого прямая, заданная уравнением y = ax + b, может быть представлена в виде точки с координатами (b, a) в пространстве параметров. Преобразование Хафа для поиска прямых Однако прямые, параллельные осям координат, имеют бесконечные значения для параметров a и b. То есть, если прямая близка к вертикали, то использование уравнения у = ах + b для ее представления затруднительно, поскольку при этом угловой коэффициент стремится к бесконечности. Один из способов обойти эту трудность состоит в представлении прямой с помощью нормали: xcosƟ + y sinƟ = ρ Преобразование Хафа для поиска прямых xcosƟ + y sinƟ = ρ Вместо прямых линий, геометрические места точек, лежащих на одной прямой, в плоскости ρƟ представляют собой синусоидальные кривые. Как и ранее, Q точек, лежащих на прямой xcosƟ + y sinƟ = ρ, порождают в пространстве параметров Q синусоидальных кривых, пересекающихся в точке (ρ’,Ɵ’). Если последовательно придавать Ɵ всевозможные дискретные значения и находить соответствующие им значения р, будет выполнено Q приращений содержимого ячейки накопления (ρ’,Ɵ’) Преобразование Хафа для поиска прямых . Преобразование Хафа для поиска прямых xcosƟ + y sinƟ = ρ Реально для аккумулятора выбираются ячейки шагом больше 1. Это связано с дискретностью. В серии экспериментов 1976 О'Горман и Кловс дискретизировали значения d с шагом ρ и значения Ɵ с шагом 10. Алгоритм Преобразование Хафа для поиска окружностей (x- с 1)2 + (y- с 2) 2 = с 32 Основное отличие состоит в увеличении числа параметров до трех (с1, с2 и с3), что приводит к трехмерному пространству параметров с кубическими ячейками, накапливаемые значения в которых имеют вид А(с1, с2., с3). Процедура состоит в последовательном присваивании параметрам с1 и с2 всех сочетаний допустимых дискретных значений, нахождением для каждой пары значения с3, которое бы удовлетворяло уравнению и увеличением накопленного значения в ячейке, отвечающей тройке Модификация пр. Хафа 1 Алгоритм использует оценку ориентации нормали в голосующих контурных точках. • Обнаружение пикселов края, окружающих периметр объекта. Голосующими контурными точками считаются точки с высоким значением модуля градиента. • Для каждого обнаруженного краевого пиксела используется оценка положения и ориентации контура с целью оценки центра кругового объекта радиуса R путем движения на расстояние R от краевого пиксела в направлении нормали к контуру. Модификация пр. Хафа 2 Если радиус окружности является неизвестным или переменным, необходимо включить R в качестве дополнительной переменной в параметрическое пространство-аккумулятор: тогда процедура поиска пика должна определить радиус, так же как и положение центра путем рассмотрения изменений вдоль третьего измерения параметрического пространства. Если размер обнаруженной окружности нас не интересует и требуется обнаружить только ее центр, то можно обойтись и без увеличения размерности пространства параметров. Алгоритм нахождения кругов 1. используется детектор границ Кенни для нахождения границ на изображении 2. для ненулевых точек высчитывается градиент (через вычисление 1-й производной по X и Y через cvSobel()) 3. определяются центры кругов 4. относительно центра определяются ненулевые точки, лежащие на одном расстоянии Модификация пр. Хафа 1 Пусть для каждого возможного направления на "центр" контурная точка голосует не точкой на расстоянии R, а лучом в этом направлении)(a). Таким образом, окажутся задействованы все возможные положения "центра" при любом масштабе объекта, и это позволит искать окружности независимо от их радиуса. (b) Обобщенное преобразование Хафа Метод голосования контурных точек в пространство параметров можно обобщить и на случай кривых, не описываемых в аналитической форме. Рассмотрим сначала задачу обнаружения объекта произвольной формы, заданного эталонным изображением, в случае, когда требуется обеспечить инвариантность результатов обнаружения к сдвигу изображения, но не к его масштабу. Существенно то, что расстояние R от текущего пиксела границы до ее центра является функцией R(ϕ) от угла ϕ радиуса-вектора, направленного от точки контура к центру. В дополнение, в общем случае, "центр" здесь должен заново интерпретироваться как некая условная точка локализации O. Выбор точки локализации OO не является единственным и может регулировать ошибки. В общем случае следует ожидать, что положение точки локализации рядом с центром тяжести периметра объекта минимизирует ошибки, обусловленные неточностью оценки ориентации края. Обобщенное преобразование Хафа Для определения простых форм функция R(ϕ) может быть описана аналитически. Однако для большинства форм это невозможно. Тем не менее показано, что подход еще остается жизнеспособным, так как для запоминания информации о форме можно использовать специальные просмотровые таблицыпросмотровые таблицы (look-uptable), содержащие дискретные значения R(ϕ) для различных значений углов. Соответственно, алгоритм состоит из этапов обучения детектора Хафа путем составления LUT по эталонному изображению(a) и этапа обнаружения объекта на тестовом изображении путем голосования контурных точек с использованием этой LUT(б). Общий алгоритм 1. Вычисляется модуль градиента изображения в каждой точке, который подвергается пороговому преобразованию, в результате чего формируется двоичное изображение. 2. Выполняется разбиение (дискретизация) пространства параметров на ячейки накопления. 3. Для всех ненулевых пикселей двоичного изображения, полученного в п. 1, находятся образы в пространстве параметров и осуществляется процедура накопления. 4. Анализируются накопленные значения и отыскиваются ячейки с наибольшей концентрацией точек. 5. Исследуются отношения между пикселями изображения, отвечающих выбранным ячейкам накопления (в основном на предмет их связности). Размерность массива накопления равна числу параметров Модификации • • • • Вероятностное преобразование Хафа Случайное преобразование Хафа Иерархическое преобразование Хафа Рекуррентное преобразование Хафа в скользящем окне Блобы «Капля», «Blob» - вначале для особенностей такого типа была разработана теория выбора характерного размера Slide by S. Lazebnik Поиск краев -напоминание Source: S. Seitz Поиск краев -напоминание Source: S. Seitz От краев к блобам • Край = «всплеск» • Блоб = совмещение двух «всплесков» Величина отклика Лапласиана достигает максимума в центре блоба в том случае, если размер Лапласиана «соответствует» размеру блоба Slide by S. Lazebnik Выбор масштаба Нужно найти характеристический размер блоба путем свертки с Лапласианом в нескольких масштабах и найти максимальные отклики Однако, отклик Лапласиана затухает при увеличении масштаба: Slide by S. Lazebnik Нормализация масштаба Отклик производной фильтра гаусса на идеальный край затухает при увеличении σ Нужно домножить производную на σ для достижения инвариантности к масштабу Лапласиан это вторая производная фильтра гаусса, поэтому домножаем на σ2 Эффект нормализации Slide by S. Lazebnik Поиск блобов в 2D Лапласиан Гауссиана(LoG): Центрально симметричный оператор поиска блобов в 2D Slide by S. Lazebnik Поиск блобов в 2D Лапласиан Гауссиана: Центрально симметричный оператор поиска блобов в 2D Slide by S. Lazebnik Выбор масштаба Slide by S. Lazebnik Выбор масштаба Slide by S. Lazebnik Эффективная реализация (DoG) MSER (Maximally Stable Extremal Regions) Используется в качестве метода Blob обнаружения. Представим все возможные отсечения изображения. В результате получим набор бинарных изображений при разных значениях порога T={0…255} (пиксель, интенсивность которого меньше порога считаем черным, в противном случае, белым). Таким образом, строится пирамида, у которой на начальном уровне, соответствующем минимальному значению интенсивности, находится белое изображение, а на последнем уровне, отвечающем максимальному значению интенсивности, – черное. Такая пирамида позволяет построить множество связных компонент, соответствующих белым областям, – регионов с максимальным значением интенсивности. Если инвертировать бинарные изображения в пирамиде, то получим набор регионов с минимальным значением интенсивности. Алгоритм • Сортируем множество всех пикселей изображения в порядке возрастания/убывания интенсивности. • Построим пирамиду связных компонент. Для каждого пикселя отсортированного множества выполним последовательность действий: – обновление списка точек, входящих в состав компоненты; – обновление областей следующих компонент, в результате чего пиксели предыдущего уровня будут подмножеством пикселей следующего уровня. Выполним для всех компонент поиск локальных минимумов (находим пиксели, которые присутствуют в данной компоненте, но не входят в состав предыдущих). Набор локальных минимумов уровня соответствует экстремальному региону на изображении. Иными словами для каждой области находим порог, при котором рост площади минимален Резюме Углы Блобы Области