Петербургский Государственный Университет о распаллеливании дактилоскопических алгоритмов




Скачать 115.26 Kb.
Название Петербургский Государственный Университет о распаллеливании дактилоскопических алгоритмов
Дата публикации 31.05.2014
Размер 115.26 Kb.
Тип Документы
literature-edu.ru > Информатика > Документы
Сартасов С.Ю.
Россия, Санкт-Петербург, Санкт-Петербургский Государственный Университет
О РАСПАЛЛЕЛИВАНИИ ДАКТИЛОСКОПИЧЕСКИХ АЛГОРИТМОВ

Введение


Задачи дактилоскопической идентификации решаются в различных системах, как в коммерческих, так и в академических. Основным показателем качества системы является качество распознавания отпечатка в терминах False Accept Rate (FAR, коэффициент ложного доступа) и False Reject Rate (FRR, коэффициент ложного отказа доступа). В настоящее время достигнуто такое значение FAR, как , что свидетельствует о высоком уровне развития разрабатываемых биометрических решений.

Вместе с тем практика внедрения идентификационных решений показывает, что качество распознавания не всегда является единственной характеристикой качества всей системы в целом. При построении «электронной проходной» в учреждении немаловажным параметром является также и время идентификации личности, так как длительное распознавание приводит к появлению очередей.

В общей схеме биометрической системы [1] (рисунок 1) мы можем выделить 5 точек, быстродействие в которых влияет на быстродействие всей системы:



Рис. 1. Общая схема биометрической системы

  1. В сканере – захват изображения отпечатка.

  2. В линиях связи между сканером и экстрактором свойств.

  3. В экстракторе свойств – быстродействие экстрактора.

  4. В мэтчере – последовательное сопоставление всех шаблонов базы с предоставленным.

  5. В мэтчере – быстродействие алгоритма сопоставления.

Первая и вторая точки обычно работают достаточно быстро, и суммарная задержка между прикладыванием пальца и получением изображения в экстракторе составляет порядка 50-200 мс (для популярных в коммерческих системах устройств Futronic FS80, Futronic FS84, Authentec AES1610). Третья и пятая точка связаны с алгоритмом распознавания. К сожалению, не все алгоритмы, требующие серьёзных вычислительных затрат, могут быть эффективно распараллелены, что негативно влияет на их применимость. Четвёртая точка связана с проблемой масштабируемости биометрической системы – увеличением времени сопоставления и ранжирования шаблонов с ростом их числа в базе данных. Для быстрого решения этой проблемы часто бывает достаточно просто разделить весь массив шаблонов на нескольких частей и запустить алгоритм сопоставления отдельно в каждом потоке для каждой получившейся части, где число потоков не превышает общее число ядер процессоров вычислительной машины. Такой способ применяется для не слишком больших баз отпечатков (порядка тысяч), но в случае больших баз для получения приемлемого времени сопоставление производится на нескольких вычислительных машинах сразу.

Методология GPGPU (General-Purpose Graphical Processing Unit) заключается в том, что для вычислений общего назначения применяется видеокарта вычислительной машины. Она представляется нам перспективной для более эффективной реализации параллельной обработки отпечатка в биометрической системе, как на этапе построения шаблона, так и на этапе сопоставления. Ранее мы уже рассматривали алгоритм дактилоскопической идентификации FingerCode[2] при исследовании его пространственных характеристик. Как будет показано ниже, он обладает рядом свойств, благодаря которым его реализация с применением GPGPU даёт значительный выигрыш в производительности. На основании полученных результатов мы предлагаем двухступенчатую архитектуру биометрической системы, лучше адаптированную к масштабированию.
  1. Обзор технологии CUDA


Одной из реализаций методологии GPGPU является технология CUDA фирмы NVIDIA, используемая в видеокартах семейства GeForce [3]. Её программная модель показана на рис.2:



Рис.2. Программная модель технологии CUDA

Согласно данной модели все вычисления делятся на осуществляемые на центральном процессоре (хост или host) и на осуществляемые на видеокарте (устройство или device). Во время выполнения вычислений хост обращается к устройству, передавая на исполнение программное ядро (kernel) – скомпилированный шейдер графического процессора. Перед вызовом ядра происходит конфигурация потоков устройства. Предполагается, что при работе ядра будет создано большое количество потоков, которые объединяются в блоки. Все потоки одного блока исполняются на одном мультипроцессоре устройства, причём физически потоки в блоке объединяются в пулы (warp), в которых все команды исполняются одновременно. Множество блоков образует сетку (grid). В настоящее время число потоков в пуле составляет 32, размерность блока и сетки может составлять до 3 измерений включительно, однако максимальное число потоков в блоке не должно превышать 1024. На одном мультипроцессоре может одновременно исполняться до 16 блоков с суммарным числом потоков, не превышающим 2048.

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

  1. Размер блока надо подбирать с учётом потребления регистровой памяти в каждом потоке, так как её количество ограничено в каждом мультипроцессоре.

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

  3. Невозможно использовать рекурсивные функции.

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

Таким образом, перевод на GPGPU некоторых алгоритмов может быть затруднён.
  1. О параллельной реализации алгоритма FingerCode


Об алгоритме дактилоскопической идентификации FingerCode можно более подробно узнать в [4]. Алгоритм построения шаблона следующий:

  1. Построить поле направлений папиллярных линий отпечатка пальца. Для его построения можно использовать фильтры Собеля и сглаживающий фильтр.

  2. На основании некоторого алгоритма выделить опорную точку. Алгоритмы поиска опорной точки по полю направлений, как правило, тоже редуцируются к операциям свёртки. В нашей работе мы использовали алгоритм из [5] как более устойчивый к повороту пальца.

  3. Провести свёртку P фильтрами Габора области, ограниченной M концентрическими кольцами толщиной K пикселов и внутренним радиусом наименьшего кольца L пикселов. По результатам нашей работы [2] из соображений построения модуля непрерывной классификации мы выбрали M=3, K=24, L=14, P=7, что позволило установить рабочую точку FAR = 12.26%, FRR=1.3%.

  4. В P получившихся изображениях разбить каждое кольцо на N секторов. Вычислить математическое ожидание и среднее отклонение цветов пикселов в каждом секторе. Из тех же соображений мы выбрали N=9.

  5. Из MNP средних отклонений составить вектор, который и будет шаблоном FingerCode.

Элементами, по которым осуществляются итерации на шагах 1-4 – это пикселы изображения и углы поля направлений в двумерном массиве. Во всех этих алгоритмах итерации не зависят друг от друга, то есть для обработки каждого элемента необходимо знать его численное значение и в ряде случае исходное значение элементов в некоторой его окрестности, но не результат преобразования соседних элементов. Следовательно каждую итерацию можно выполнять независимо от остальных и параллельно с ними. Отдельно отметим, что наиболее вычислительно ёмкой является операция свёртки изображения фильтрами Габора – она может занимать до 80-95% всего времени работы алгоритма.

Реализация данного алгоритма с использованием GPGPU была ранее рассмотрена в [6]. Хотя ускорение работы алгоритма в 35 раз при том, что FAR всей системы остался неизменным, является отличным результатом, необходимо отметить существенные, с нашей точки зрения, недостатки:

  1. Так как нет указания на выбранный метод поиска опорной точки, мы полагаем, что был использован метод из оригинальной работы [4], который не даёт удовлетворительно точного ответа для повёрнутых отпечатков.

  2. В работе говорится об уменьшении размера шаблона с 640 до 512 элементов. Не указаны пространственные характеристики соответствующей этому шаблону системы колец и число фильтров.

  3. В работе не указывается, какое время тратится на применение к изображению фильтров и поиск опорной точки. Не уточняется, входит ли в работу мэтчера ранжирование результатов, или это только вычисление сумм.

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

Степень схожести двух шаблонов определяется евклидовым расстоянием



где {xi}, {yi} – двашаблонаFingerCode. Чем меньше метрика, тем более схожи шаблоны. В работе [6] предлагается вычислять данную метрику параллельно. Так как метрика алгоритмически простая и не требует больших вычислительных затрат в рамках сопоставления одной пары шаблонов, мы не реализовывали параллельную версию алгоритма её вычисления. Для значительного прироста быстродействия, как было сказано ранее, оказалось, достаточно просто распараллелить вычисление метрики по всему массиву. Предлагается следующая схема оптимизации вычислений, учитывающая технологические особенности платформы. Поскольку при обращении к глобальной памяти мультипроцессорможет считывать не отдельные слова, а 16 4-байтовых слов, для оптимизации обращения к памяти видеокарты элементы массива были переставлены следующим образом: шаблоны объединялись в группы по 32 (размер пула), и все элементы с одинаковым индексом записывались последовательно. Пример такой перестановки показан на рис. 3 для пула в 8 потоков и векторов из 3 компонент. Одним цветом обозначены компоненты одного и того же вектора, числами обозначен индекс компонента вектора.



Рис. 3. Пример перестановки элементов FingerCode для 8 векторов из 3 компонент.

Алгоритмы были реализованы на языке CUDA C с применением арифметики с плавающей запятой обычной точности. Ранжирование результатов осуществлялось во всех случаях на CPU. Исходные коды доступны по ссылке: http://code.google.com/p/cuda-fingerprinting/

Результаты работы алгоритма были получены на 3 машинах с различными видеокартами компании NVIDIA. Так какчисло мультипроцессоров зависит от модели видеокарты, время работы алгоритма может заметно отличаться. Результаты измерений приведены в таблице 1. Все времена указаны в миллисекундах.

Таблица 1

Результаты исполнения последовательной и параллельной версий алгоритма FingerCodeна машинах разных конфигураций

Конфигурация

Опорная точка

Шаблон

Мэтчер

Ранжи-рование

Сумма

Только GPU

Полное ускоре-ние

Ускорение с GPU

Машина 1 (CPU)

40,125

1336,547

121,1

23,5

1521,27

1497,77







Машина 2 (GPU)

9

143,75

1,95

35,3

190

154,7

801%

968%

Машина 3 (GPU)

3

46,95

1

30,9

81,85

50,95

1859%

2940%

Машина 1 (GPU)

3

36,35

1

28,3

68,65

40,35

2216%

3712%


Конфигурации машин следующие:

Машина 1: Intel Core i5-2400 с частотой 3.3 ГГц, 8 Гб ОЗУ, видеокарта Nvidia GeForceGTX 570

Машина 2: Samsung RF511 S01, видеокарта Nvidia GeForce 540M

Машина 3: Intel Core i5-2400 счастотой 3.3 ГГц, 4 ГбОЗУ, видеокарта Nvidia GeForce GTX 560

Сопоставление и ранжирование осуществлялись в наших экспериментах на базе в 60000 искусственных отпечатков без учёта поворота. Необходимо отметить, что алгоритм ранжирования не был реализован на GPU, и видно, что в самом быстром варианте он становится новым узким местом работы системы.

Наши эксперименты на машине 1показывают, что на массиве из миллиона FingerCode время сопоставления по нашей схеме составляет 4 мс. Так как в нашей работе мы используем 9секторов, наиболее вероятными для поворота будут 5 направлений. При вычислении метрик схожести нет необходимости хранить по 5 представлений каждого FingerCode. Для достижения этой цели достаточно сформировать представления сопоставляемого FingerCode, так как сопоставление шаблона I, повёрнутого на 2π/P, с шаблоном II из базы эквивалентно сопоставлению Iс II, который повёрнут на -2π/P. Таким образом, расчётное число сопоставлений в секунду составляет



Из результатов также становится заметно, что после ускорения одним из узких мест системы становится ранжирование результатов, время работы которого нелинейно возрастает с увеличением числа шаблонов в базе отпечатков. В этой связи мы также реализовали на CUDA битоническую сортировку [7]. Однако этот алгоритм недостаточно хорошо ложится на модель памяти CUDA, вследствие чего время его работы может отличаться от раза к разу. Наши эксперименты показывают, что это время работы для миллиона элементов можно аппроксимировать нормальным распределением с математическим ожиданием 8,05 мс и дисперсией 1,65 мс.

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


Встраивание в схему биометрической системы непрерывного классификатора добавляет в неё два дополнительных звена (рис.4):



Рис.4. Схема биометрического распознавания для непрерывного классификатора и мэтчера

Между тем, как правило, алгоритмы классификации и идентификации выбираются так,чтобы использовать разные и взаимно дополняющие элементы отпечатков, например, классификатор по типу узора и мэтчер на основе минуций. Как следствие экстракторы свойств мэтчера и классификатора не пересекаются или минимально пересекаются по используемым артефактам (например, они оба используют поле направлений, но по-разному). Это позволяет нам выполнять часть блоков независимо друг от друга. Разделение исполнения этих блоков на два или более физических вычислительных устройства (CPU+GPU или GPU+GPU) позволяет добиться большего ускорения, нежели исполнение их на одном устройстве (рис. 5), при этом надо принять во внимание, что вызовы программных ядер CUDA асинхронны по умолчанию. Начиная с видеокарт, поддерживающих CUDA Compute Capability 2.0, существует возможность одновременного запуска до 4 программных ядер на одном GPU. Это становится актуальным для видеокарт последних моделей, где число мультипроцессоров может оказаться меньше числа блоков программного ядра.



Рис.5. Параллельная схема биометрической системы

Заключение


Мы показали, что алгоритм FingerCode может быть эффективно реализован с применением технологии NVIDIA CUDA. Полученные данные о времени работы алгоритма вместе с найденной рабочей точкой уже являются приемлемыми для его использования в коммерческих системах для реализации непрерывного классификатора. В частности, возможность ранжирования базы из миллиона отпечатков по убыванию степени похожести менее, чем за 50 миллисекунд, с использованием не самого лучшего оборудования из доступного на рынке, позволяет говорить о применимости непрерывной классификации в системах реального времени и о достижении существенно лучшей масштабируемости процедуры сопоставления. Предлагаемая нами схема биометрической системы предназначена для лучшего использования вычислительных мощностей видеокарты. Наши дальнейшие исследования направлены на построение высокоточного мэтчера с применением технологии CUDA.

СПИСОК ЛИТЕРАТУРЫ


  1. Bolle Ruud и др. Guide to Biometrics. - London : Springer Professional Computing, 2003.

  2. Сартасов С.Ю. О пространственных характеристиках алгоритма FingerCode // Компьютерные инструменты в образовании. СПб: Автономная некоммерческая организация Центр информатизации образования КИО–2011, 6.

  3. Боресков А.В., Харламов А.А. Основы работы с технологией CUDA. – М.-ДМК-Пресс, 2010.

  4. Jain Anil K. и др. Filterbank-Based Fingerprint Matching // IEEE Transactions on Image Processing. - Piscataway, N.J. : IEEE Signal Processing Society, May 2000 г.. – 5 : Т. 9.

  5. LifengSha Feng Zhao, Xiaoou Tang. Improved FingerCode for Filterbank-based Fingerprint Matching // Proceedings of International Conference on Image Processing (ICIP) 2003. – Washington, DC: IEEE, 2003.

  6. S. Bay et al.GPU-Accelerated Fingerprint Matching. http://developer.download.nvidia.com/GTC/PDF/GTC2012/Posters/P0373_11-2610_GTC2011_POSTER-MITRE_GPU-Accelerated_Fingerprint_Matching_v1.pdf

  7. Фальфушинский В.В., Гречко В.О. Параллельно-конвейерные схемы алгоритмов сортировки // Международная конференция «Высокопроизводительные вычисления HPC-UA’2011», Киев, 2011.

Добавить документ в свой блог или на сайт

Похожие:

Петербургский Государственный Университет о распаллеливании дактилоскопических алгоритмов icon Биофизические механизмы метода грв биоэлектрографии
Санкт-Петербургский государственный университет информационных технологий, механики и оптики; 2 Университет «Холос», Фэйрвью, Миссури,...
Петербургский Государственный Университет о распаллеливании дактилоскопических алгоритмов icon Перечень используемых сокращений 5
Спбгуап – Санкт-Петербургский Государственный Университет Аэрокосмического Приборостроения 5
Петербургский Государственный Университет о распаллеливании дактилоскопических алгоритмов icon Пояснительная записка к курсовой работе по дисциплине «Технология...
Государственное образовательное учреждение санкт-петербургский государственный университет
Петербургский Государственный Университет о распаллеливании дактилоскопических алгоритмов icon Курсовая работа Культурологическая проблематика в работе Л. Н. Гумилева...
Санкт-Петербургский Государственный Университет Телекоммуникаций им проф. М. А. Бонч-Бруевича
Петербургский Государственный Университет о распаллеливании дактилоскопических алгоритмов icon Дипломному проекту на тему: «Разработка методов встраивания информации...
Санкт-Петербургский государственный электротехнический университет “лэти” им. В. И. Ульянова (Ленина)” (СПбгэту)
Петербургский Государственный Университет о распаллеливании дактилоскопических алгоритмов icon Модели и методы компьютерной поддержки взаимодействия эксперта и...
Санкт-Петербургский государственный электротехнический университет «лэти» им. Ульянова (Ленина)
Петербургский Государственный Университет о распаллеливании дактилоскопических алгоритмов icon Дипломному проекту на тему: «Разработка методов встраивания информации...
Санкт-Петербургский государственный электротехнический университет “лэти” им. В. И. Ульянова (Ленина)” (СПбгэту)
Петербургский Государственный Университет о распаллеливании дактилоскопических алгоритмов icon Российской Федерации Федеральное агентство по образованию санкт-петербургский...
Одобрены на заседании кафедры «Социально-культурный сервис и туризм», протокол №8 от 19. 03. 2010 г
Петербургский Государственный Университет о распаллеливании дактилоскопических алгоритмов icon Рабочая программа дисциплины семантический web для профиля «Технологии семантического Web»
«Санкт-Петербургский государственный электротехнический университет \"лэти\" имени В. И. Ульянова (Ленина)»
Петербургский Государственный Университет о распаллеливании дактилоскопических алгоритмов icon Правила приема граждан в негосударственное образовательное учреждение...
Образования «санкт-петербургский университет управления и экономики» на основные образовательные программы высшего профессионального...
Литература


При копировании материала укажите ссылку © 2015
контакты
literature-edu.ru
Поиск на сайте

Главная страница  Литература  Доклады  Рефераты  Курсовая работа  Лекции