принципы адаптации вычислительных алгоритмов




Скачать 413.33 Kb.
Названиепринципы адаптации вычислительных алгоритмов
страница5/10
Дата22.10.2012
Размер413.33 Kb.
ТипДокументы
1   2   3   4   5   6   7   8   9   10

Задача поиска ключевых точек на изображении при помощи алгоритма SIFT


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

В настоящее время существует несколько алгоритмов, позволяющих решающих задачу поиска ключевых точек [25], одним из наиболее устойчивых среди них является алгоритм Scale-invariant feature transform (SIFT).

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

На первом этапе алгоритма происходит построение так называемой пирамиды Гаусса. К исходному черно-белому изображению I(x, y) многократно применяется фильтр Гаусса [19, 20]:

, (10)

где k, σ0 и N – параметры алгоритма, оптимальные значения для которых приведены в [19, 20]. Затем строится так называемая разностная пирамида (рис. 5):

, (11)



Рис. 5. Пирамида Гаусса и разностная пирамида

На втором этапе алгоритма полученная разностная пирамида воспринимается как функция трех переменных – D(x, y, σ). На данном этапе ищутся локальные экстремумы (xi, yi, σi), которые в дальнейшем будем называть кандидатами.

На третьем этапе происходит уточнение положения и отсев кандидатов, согласно критерию, также описанному в [19, 20]. Существенным является тот факт, что время обработки разных кандидатов может отличаться (оно определяется значениями пирамиды в окрестностях найденного в дискретной сетке экстремума). Кандидаты, прошедшие отбор в дальнейшем называются ключевыми точками.

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

На последнем, пятом, этапе происходит вычисление дескрипторов ключевых точек. Дескриптор представляет собой нормированный вектор в R128. Для вычисления дескриптора также используется распределение направления и величины градиента в окрестности ключевой точки – окрестность «поворачивается» на подсчитанную ранее ориентацию ключевой точки, делится на шестнадцать областей и для каждой области считается гистограмма распределения направления градиента. Каждая гистограмма содержит восемь корзин, из полученных гистограмм формируется дескриптор ключевой точки (рис. 6).



Рис. 6. Пример работы алгоритма SIFT. Стрелками отмечены найденные ключевые точки.

Недостатком алгоритма SIFT является его трудоемкость – на традиционной архитектуре обработка одного кадра разрешением 320 на 240 длится более половины секунды. Такая скорость работы является неприемлемой для некоторых приложений, требующих поиска ключевых точек в режиме реального времени при обработке потока изображений с относительно высокой (10-20 кадров в секунду) частотой кадров.
1   2   3   4   5   6   7   8   9   10

Похожие:

принципы адаптации вычислительных алгоритмов iconпринципы адаптации вычислительных алгоритмов к архитектуре графических акселераторов
Целью работы является изучение ключевых особенностей отображения вычислительных алгоритмов на gpu -архитектуру, выявление ряда факторов,...
принципы адаптации вычислительных алгоритмов iconЗадача параметрической аппроксимации двумерной функции с использованием метода случайного поиска 10
Принципы адаптации вычислительных алгоритмов под параллельную архитектуру графических акселераторов
принципы адаптации вычислительных алгоритмов iconОсобенности адаптации вычислительных алгоритмов под параллельную архитектуру графических акселераторов
В работе обсуждаются вопросы отображения вычислительных алгоритмов на параллельную архитектуру gpu-акселератора. В качестве примера...
принципы адаптации вычислительных алгоритмов iconПрограмма вступительного экзамена в магистратуру по направлению подготовки 231000. 68 «Программная инженерия»
...
принципы адаптации вычислительных алгоритмов icon1. цели и задачи дисциплины, ее место в учебном процессе согласно гос впо в дисциплину «Вычислительные системы, сети и телекоммуникации» должно включаться
Вычислительных машин: общие принципы построения и архитектуры вычислительных машин, информационно-логические основы вычислительных...
принципы адаптации вычислительных алгоритмов iconАлгоритмы
Основы алгоритмизации. Понятие об алгоритме. Применение алгоритмов. Свойства алгоритмов. Типы алгоритмов: линейные, циклические,...
принципы адаптации вычислительных алгоритмов iconСодержание, основные понятия
Понятие алгоритма, свойства алгоритмов. Использование алгоритмов, система команд исполнителя. Способы записей алгоритмов. Формальное...
принципы адаптации вычислительных алгоритмов iconОглавление 4
Архитектура графических акселераторов, средства отображения на них вычислительных алгоритмов и исследуемые алгоритмы 10
принципы адаптации вычислительных алгоритмов iconБилет №4
Понятие алгоритма: свойства алгоритмов, исполнители алгоритмов. Автоматическое исполнение алгоритма. Способы описания алгоритмов....
принципы адаптации вычислительных алгоритмов iconТическая логика и теория алгоритмов
Темпоральные логики высказываний линейного времени и вычислительных деревьев: их синтаксис и семантика
Разместите кнопку на своём сайте:
Библиотека


База данных защищена авторским правом ©lib.znate.ru 2014
обратиться к администрации
Библиотека
Главная страница