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

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

Флуктуации градиента также считаются с помощью фильтра Хаара.

Размещено на http://www.allbest.ru/

Рис. 1 Схема работы метода SURF

Интегральное представление изображения

Для эффективного вычисления фильтров Гессе и Хаара - используется интегральное представление изображений.

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

Где I (i,j) - яркость пикселов исходного изображения.

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

Где ABCD - интересующий нас прямоугольник.

Вычисление матрицы Гессе

Обнаружение особых точек в SURF основано на вычислении детерминанта матрицы Гессе (гессиана).

Матрица Гессе для двумерной функции и ее детерминант определяется следующим образом:

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

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

Рис. 2. На рисунке показаны концы отрезка, распознанные как ключевые точки, с помощью матрицы Гессе.

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

На рисунке изображены дискретизированные фильтры для нахождения четырех элементов матрицы Гессе (четвертый - совпадает с третьим, поскольку матрица Гессе симметрична). Фильтры имеют пространственный масштаб 9x9 пикселов. Темные участки соответствуют отрицательным значениям фильтра, светлые - положительным.

Однако SURF не использует лапласиан гауссианы в том виде, который изображен на рисунке. Во-первых, по утверждению авторов, дискретизированный лапласиан гауссианы имеет довольно большой разброс значения детерминанта, при вращении образца (напомним, что в идеале гессиан должен быть инвариантен к вращению). Особенно детерминант "проседает" в районе поворота на 45 граудсов. А во-вторых, и это главное, фильтр для лапласиана гауссианы имеет непрерывный характер. Почти все пикселы фильтра имеют разные величины яркости. А это не позволяет эффективно использовать такой мощный механизм расчёта, как интегральную матрицу изображения.

Поэтому SURF использует бинаризованную аппроксимацию лапласиана гауссиан (авторы назвали его Fast-Hessian):

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

Таким образом, в SURF, гессиан вычисляется так:

Где Dxx, Dyy, Dxy - свертки по фильтрам, изображенным на рисунке вверху. Коэффициент 0.9 имеет теоретическое обоснование, и корректирует приближенный характер вычислений.

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

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

Кроме того, свойства гессиана таковы, что он достигает максимума, как в точке белого пятна на черном фоне, так и черного пятна на белом фоне. Таким образом, метод обнаруживает и темные, и светлые особенности изображения.

Метод распознает как светлые точки на темном фоне, так и темные точки на светлом фоне.

Достижение инвариантности относительно масштаба

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

Из соображений симметрии и дискретизации, размер фильтра Fast-Hessian не может принимать произвольные значения. Допустимые размеры этого фильтра таковы (начиная с минимального): 9, 15, 21, 27 и так далее, с шагом 6. Однако, на практике, постепенно увеличивать размер фильтра на 6 - не выгодно, потому что для крупных масштабов шаг 6 оказывается слишком мелким, а фильтры - избыточными. Поэтому (и по некоторым другим причинам), SURF разбивает все множество масштабов на так называемые октавы. Каждая октава покрывает определенный интервал масштабов, и имеет свой характерный размер фильтра.

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

Рис. 3. Рисунок показывает две ключевые точки разного масштаба в одной точке изображения.

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

Исходя из перечисленного, октава содержит не один фильтр, а четыре фильтра, которые хорошо покрывают характерный масштаб октавы:

На рисунке показаны первые три октавы метода SURF. Цифры в прямоугольниках показывают размер фильтра Fast-Hessian. Логарифмическая шкала снизу - показывает масштабы, покрываемые октавами.

Шаг размера фильтра в первой октаве - составляет 6, во второй - 12, в третьей - 24 и так далее.

Как видим, октавы значительно перекрываются друг другом. Это увеличивает надежность нахождения локальных максимумов. Почему в октаве именно четыре фильтра станет ясно из следующей главы.

Теоретически, масштабы бесконечны, однако в реальных изображениях, они вполне конечны, и основная масса сосредоточена в интервале от 1 до 10 (по данным авторов метода). Для покрытия этого диапазона достаточно четырех октав. Плюс добавляется одна или две октавы для покрытия больших масштабов. Итого, используется 5-6 октав. Теоретически, этого вполне достаточно для покрытия всевозможных масштабов на изображении 1024x768 пикселов.

Нахождение локального максимума гессиана

Для нахождения локального максимума гессиана, используется так называемый метод соседних точек 3x3x3.

Его смысл понятен из рисунка ниже:

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

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

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

Удвоение шага пикселов для октав позволяет экономить при расчёте фильтров. Как вы наверно уже заметили, размеры фильтров в октавах повторяются. Так, например, фильтр размером 27 присутствует в трех октавах. Так вот, при вычислениях, этот фильтр будет считаться только для первой октавы. Вторая и третья - просто используют расчёты первой октавы. А удвоение шага пикселов гарантирует, что точки, в которых нужно считать гессиан, уже были просчитаны предыдущей октавой.

Поэтому, несмотря на то, что октава содержит четыре фильтра, на самом деле каждая октава (кроме первой) считает только два характерных для нее размера, два других - всегда можно взять из предыдущих октав. Первая же октава вынуждена считать все четыре своих фильтра.

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

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

Нахождение ориентации особой точки

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

Сначала, вычисляются точечные градиенты в пикселах, соседних с особой точкой. Для рассмотрения берутся пикселы в окружности радиуса 6s вокруг особой точки. Где s - масштаб особой точки. Для первой октавы берутся точки из окрестности радиусом 12.

Для вычисления градиента, используется фильтр Хаара. Размер фильтра берется равным 4s, где s - масштаб особой точки. Вид фильтров Хаара показан на картинке:

Рис. 4. Фильтры Хаара. Черные области имеют значения - 1, белые +1.

Фильтры Хаара дают точечное значение перепада яркости по оси X и Y соответственно. Поскольку фильтры Хаара имеют прямоугольную форму, их значения легко считаются с помощью интегральной матрицы. Для расчёта одного фильтра произвольного размера требуется всего 6 операций.

Значения вейвлета Хаара dX и dY для каждой точки умножаются на вес и запоминаются в массиве. Вес определяется как значение гауссианы с центром в особой точке и сигмой равной 2s. Взвешивание на гауссиане необходимо для отсечения случайных помех на далеких от особой точки расстояниях.

Далее, все найденные значения dX и dY, условно наносятся в виде точек на плоскость, как показано на рисунке:

Рис. 5. На рисунке показаны все найденные градиенты в виде точек в пространстве dXdY.

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

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

Отметим, что не всегда требуется инвариантность дескрипторов относительно вращения. Метод SURF имеет модификацию, в которой ориентация особых точек не рассчитывается. Такая модификация позволяет надежно идентифицировать точки, повернутые не более чем на ±15 градусов.

Вычисление дескриптора особой точки

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

Для вычисления дескриптора, вокруг особой точки формируется прямоугольная область, имеющая размер 20s, где s - масштаб в котором была найдена особая точка. Для первой октавы, область имеет размер 40x40 пикселов. Квадрат ориентируется вдоль приоритетного направления, вычисленного для особой точки.

Дескриптор считается как описание градиента для 16 квадрантов вокруг особой точки.

Далее, квадрат разбивается на 16 более мелких квадрантов, как показано на рисунке. В каждом квадранте берется регулярная сетка 5x5 и для точки сетки ищется градиент, с помощью фильтра Хаара. Размер фильтра Хаара берется равным 2s, и для первой октавы составляет 4x4.

Следует отметить, что при расчёте фильтра Хаара, изображение не поворачивается, фильтр считается в обычных координатах изображения. А вот полученные координаты градиента (dX,dY) поворачиваются на угол, соответствующий ориентации квадрата.

Итого, для вычисления дескриптора особой точки, нужно вычислить 25 фильтров Хаара, в каждом из 16 квадрантов. Итого, 400 фильтров Хаара. Учитывая, что на фильтр нужно 6 операций, выходит, что дескриптор обойдется минимум в 2400 операций.

После нахождения 25 точечных градиента квадранта, вычисляются четыре величины, которые собственно и являются компонентами дескриптора:

Две из них есть просто суммарный градиент по квадранту, а две других - сумма модулей точечных градиентов.

Рис. 6. На рисунке показано поведение этих величин для разных участков изображений

Рисунок показывает поведение дескриптора для разных изображений. Для равномерных областей - все значения близки к нулю. Для повторяющихся вертикальных полосок - все величины, кроме второй близки к нулю. При увеличении яркости в направлении оси X, две первые компоненты имеют большие значения.

Четыре компонента на каждый квадрант, и 16 квадрантов, дают 64 компонента дескриптора для всей области особой точки. При занесении в массив, значения дескрипторов взвешиваются на гауссиану, с центром в особой точке и с сигмой 3.3s. Это нужно для большей устойчивости дескриптора к шумам в удаленных от особой точки областях.

Плюс к дескриптору, для описания точки используется знак следа матрицы Гессе, то есть величина sign (Dxx+Dyy). Для светлых точек на темном фоне, след отрицателен, для темных точек на светлом фоне - положителен. Таким образом, SURF различает светлые и темные пятна.

На картинке показаны особые точки изображения. Зеленая линия показывает характерное направление для особой точки. Синий цвет окружности показывает положительный след матрицы Гессе, красный - отрицательный след.

Среда разработки и причины ее выбора

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

Разработка модулей, а также пользовательского интерфейса приложения будет осуществляться на языке программирования C# в среде разработки Microsoft Visual Studio 2011 beta. Это одна из самых мощных и систем, позволяющая на самом современном уровне создавать как отдельные прикладные программы Windows, так и разветвленные комплексы, предназначенные для работы в корпоративных сетях и в Интернет. Пользовательский интерфейс этой среды служит для организации взаимодействия с программистом и включает в себя ряд окон, содержащих различные элементы управления. С помощью средств интегрированной среды разработчику удобно проектировать интерфейсную часть приложения, а также писать программный код и связывать его с элементами управления. В интегрированной среде разработки проходят все этапы создания приложения, включая отладку.

Microsoft Visual Studio 2011 - это комбинация нескольких важнейших технологий:

1. высокопроизводительный компилятор в машинный код;

2. объектно-ориентированная модель компонент;

3. визуальное (а, следовательно, и скоростное) построение приложений из программных прототипов.

Разработка приложений в Microsoft Visual Studio 2011 осуществляется с применением объектно-ориентированного программирования (ООП) и визуального программирования. ООП и визуальное программирование позволяют создавать прикладные программы самого разного назначения. Это позволяет разработчикам строить приложения весьма быстро из заранее подготовленных объектов, а также дает им возможность создавать свои собственные объекты для среды разработки. Никаких ограничений по типам объектов, которые могут создавать разработчики, не существует.

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

Хранение информации будет осуществляться при помощи СУБД MS SQL Server 2008. Эта система отталкивается от концепции платформы данных Майкрософт: она упрощает управление любыми данными в любом месте и в любой момент времени. Она позволяет хранить в базах данных информацию, полученную из структурированных, полуструктурированных и неструктурированных источников, таких как изображения и музыка. В SQL Server 2008 имеется большой набор интегрированных служб, расширяющих возможности использования данных: вы можете составлять запросы, выполнять поиск, проводить синхронизацию, делать отчеты, анализировать данные. Все данные хранятся на основных серверах, входящих в состав центра обработки данных. К ним осуществляется доступ с настольных компьютеров и мобильных устройств. Таким образом, существует полный контроль над данными независимо от того, где я их сохранил. Так же система SQL Server 2008 позволяет обращаться к данным из любого приложения, разработанного с применением технологий Microsoft.net и Visual Studio, а также в пределах сервисно-ориентированной архитектуры и бизнес-процессов - через Microsoft BizTalk Server. Сотрудники, отвечающие за сбор и анализ информации, могут работать с данными, не покидая привычных приложений, которыми они пользуются каждый день, например приложений выпуска 2007 системы Microsoft Office. SQL Server 2008 позволяет создать надежную, производительную, интеллектуальную платформу, отвечающую всем требованиям по работе с данными.

2. Методика