FingerСode при работе использует заранее обнаруженные особые точки на отпечатке пальца - точки ядра, но не включает в себя способ нахождения этих точек.

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

Еще на положении особых точек основывается классификация отпечатков пальцев. Тип отпечатка пальца - еще один вид глобальных признаков. Отпечатки разделяются на три основных типа: спираль, петля и дуга (рис.2.5).

Рис.2.5 - Отпечатки типа «Петля», «Спираль» и «Дуга»

Есть четыре основных подхода к определению особых точек [8]:

· На основе индекса Пуанкаре;

· На основе комплексных фильтров 1 степени;

· На основе комплексных фильтров 2 степени;

· На основе индекса Пуанкаре с преобразованием Хафа.

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

· расстояние до 15 пикселов - точка определена верно;

· расстояние от 15 до 30 пикселов - точка найдена с допустимой ошибкой;

· расстояние от 30 пикселов - точка определена не верно.

Задачи, которые ставились в этой главе:

· Изучить и реализовать метод, основанный на комплексной свертке с фильтрами первой степени;

· Изучить и реализовать метод, основанный на индексе Пуанкаре;

· Составить метрики и сравнить по ним данные методы.

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

Значения дисперсии, упоминающиеся далее, были выбраны на основании экспериментов.

Для реализации была выбрана архитектура CUDA, в частности библиотека cudafingerprinting.

CUDA (англ. Compute Unified Device Architecture) -- программно-аппаратная архитектура параллельных вычислений, которая позволяет существенно увеличить вычислительную производительность благодаря использованию графических процессоров фирмы Nvidia.

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

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

· интерфейс программирования приложений CUDA (CUDA API) основан на стандартном языке программирования Си с некоторыми ограничениями. По мнению разработчиков, это должно упростить и сгладить процесс изучения архитектуры CUDA;

· разделяемая между потоками память (shared memory) размером в 16 Кб может быть использована под организованный пользователем кэш с более широкой полосой пропускания, чем при выборке из обычных текстур;

· более эффективные транзакции между памятью центрального процессора и видеопамятью;

· полная аппаратная поддержка целочисленных и побитовых операций;

· поддержка компиляции GPU кода средствами открытого LLVM.

2.1 Метод, основанный на комплексных фильтрах первой степени

Данный метод состоит из следующих этапов:

a) Строится гауссова пирамида исходного изображения отпечатка пальца.

Вычисляются четыре уровня гауссовой пирамиды - набор изображений, получаемый из исходного изображения путём его последовательного сжатия (рис.2.6). Нулевой уровень - само изображение. Последующие уровни вычисляются из предыдущих. Изображение размывается с помощью свертки с гауссовым фильтром и уменьшается в два раза по каждому измерению. Для построения фильтра была использована функция Гаусса со значением дисперсии равным 0,8. Размер гауссова фильтра считался по правилу «трех сигм» [8]:

, (2.1)

где S - сторона фильтра.

Далее размер фильтров считался по тому же правилу.

Рис.2.6 - Четыре уровня гауссовой пирамиды от 0-го до 3-го

Далее поиск особых точек проходит на самом нижнем уровне пирамиды. На каждом уровне положение точки последовательно уточняется. Поиск точки происходит в окне 13х13 пикселов, построенном вокруг точки, найденной на предыдущем уровне.

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

b) Вычисление поля направлений.

Для каждого уровня строится поле направлений, показывающее, как ориентированы папиллярные линии отпечатка. Для этого производится свертка изображения с фильтрами, построенными по формулам [7,8,9]:

(2.2)

(2.3)

где g(x,y) - функция гаусса с дисперсией 0,6.

Из этих значений для каждой точки формируется комплексное число:

, (2.4)

где a- результат обработки первым фильтром в данной точке, - результат обработки вторым (рис.2.7).

Рис.2.7 - Модуль и аргумент поля направлений (0 уровень)

c) Возведение поля направлений в квадрат.

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

Рис.2.8 - Модуль и аргумент поля направлений возведенного в квадрат (0 уровень)

d) Выделение точек вращательной симметрии

К полю направлений возведенному в квадрат применяется комплексная свертка с фильтрами первой степени.

Фильтр для выделения ядра [8,9]:

(2.5)

Фильтр для выделения дельты:

(2.6)

Результат обработки фильтром в точке представляется комплексным числом (рис.2.9, рис.2.10):

Рис.2.9 - Результат обработки фильтром для ядра и дельты (1 уровень)

Рис.2.10 - Результат обработки фильтром для ядра и дельты (0 уровень)

e) Разделение точек ядра и дельты

Для того чтобы не происходило ошибочного определения результата фильтрации на точках другого типа, ответ фильтра модифицируется следующим образом [2,6]:

, (2.7)

где - модуль результата для ядра, - модуль результата для дельты (рис.2.11, 2.12).

Рис.2.11 - Новый результат фильтрации для ядра (1 уровень)

Рис.2.12 - Новый результат фильтрации для ядра (0 уровень)

f) Модификация результата обработки фильтром для нижнего уровня.

Для нижнего уровня пирамиды (в данном случае - второго) результат фильтрации модифицируется для получения лучшей точности. Это обусловлено тем, что изображение на нижнем уровне уступает остальным в качестве и тем, что ошибка в определении точки на этом уровне неизбежно приводит к ошибке всего метода [9].

1) Производится свертка поля направлений данного уровня с гауссовым фильтром с дисперсией 1,5;

2) Результат свертки поэлементно умножается на результат фильтрации второго уровня.

3) Результат фильтрации на данном уровне поточечно умножается на гауссиану с дисперсией по x равной 7 и по y равной 15.

4) Далее два комплексных изображения усредняются: берется 1/2 от их поточечной суммы (рис.2.13).

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

Рис.2.13 - Не модифицированный и модифицированный результат фильтрации (2 уровень, изображение увеличено)

g) Выделение особой точки

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

2.2 Метод, основанный на индексе Пуанкаре

Метод основан на индексе Пуанкаре. Индекс Пуанкаре показывает суммарное изменение направлений вдоль замкнутой кривой на поле направлений. Для кривой вокруг точки ядра индекс Пуанкаре принимает значение или , для точки вокруг дельты , во всех остальных точках значение 0 [10].

Данный метод состоит из следующих этапов:

a. Вычисление поточечного поля направлений.

Для каждой точки отпечатка пальца вычисляется направление папиллярных линий в ее окрестности.

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

(2.8)

для компоненты x:

(2.9)

для компоненты y, функция гаусса строится с дисперсией 1 (рис.2.14).

Рис.214 - Градиент изображения. Компонента x и компонента у

Далее значения градиентов усредняются. Вычисляются значения поточечного умножения [9]:

, (2.10)

, (2.11)

(2.12)

Каждое из получившихся изображений сворачивается с гауссовым фильтром (с дисперсией равной 5). Далее поле направлений в точке i,j вычисляется по формуле [10,11]:

(2.13)

и приводится к промежутку .

Значение поля направлений представляет собой угол в радианах (рис.2.15).

Рис.2.15 - Поле направлений

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

Рис.2.16 - Поле направлений удвоенное и возведенное в квадрат

c. Вычисляется градиент от поля направлений, удвоенного и возведенного в квадрат [12]. Компоненты вектора градиента вычисляются с помощью свертки поля направлений из пункта 2 с фильтрами и . После этого значения компонент градиента приводятся к промежутку (рис.2.17).

Рис.2.17 - Градиент поля направлений. Компоненты x и y

d. Вычисление индекса Пуанкаре. Вместо вычисления криволинейного интеграла, по теореме Грина вычисляется интеграл по поверхности [12]:

e.

, (2.14)

где - контур,

A - поверхность.

Соответствующие производные , вычисляются с помощью свертки с фильтром , а - с фильтром (рис.2.18).

Рис.2.18 - Производные из формулы (2.14) по x и по y

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

Индекс Пуанкаре вычисляется для каждой точки изображения (рис.2.19).

Рис.2.19 - Значение индекса Пуанкаре в каждой точке изображения

f. Нахождение точки ядра

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

2.3 Результаты

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

В работе использовалась база данных отпечатков пальцев FVC2000, DB2 набор A, отпечатки с 1_1 по 50_8. Эта часть базы данных содержит отпечатки 50 человек, по 8 отпечатков на человека. Каждый отпечаток представлен в виде изображения в формате .tif с размером 364 x 256 пикселов и разрешением 500 dpi. Стоит отметить, что FVC2000 была построена для тестирования систем распознавания отпечатков пальцев и содержит много отпечатков низкого качества. информационный отпечаток цифровой код

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

Таблица Результаты сравнения рассмотренных методов

	d<=15	15<d<=30	d>30
Метод основанный на комплексных фильтрах первой степени	6,25 %	9,5 %	84,25 %
Метод, основанный на индексе Пуанкаре	27,25 %	26,5 %	46,25 %

2.4 Выводы

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

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

Реализация на CUDA имеет довольно высокую скорость выполнения на ЭВМ. Подходит для пунктов с большим человеческим трафиком.



Заключение

В данной дипломной работе было представлено общее описание внутренних особенностей получившей наибольшее распространение биометрической технологии.

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

· расстояние до 15 пикселов - точка определена верно;

· расстояние от 15 до 30 пикселов - точка найдена с допустимой ошибкой;

· расстояние от 30 пикселов - точка определена не верно.

Задачи, которые ставились в этой главе:

· Изучить и реализовать метод, основанный на комплексной свертке с фильтрами первой степени;

· Изучить и реализовать метод, основанный на индексе Пуанкаре;

· Составить метрики и сравнить по ним данные методы.

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



Список использованной литературы

1. Bazen, A.M. Extraction of Singular Points from Directional Fields of Fingerprints [Text] /А.М.Bazen, S.H.Gerez - Mobile Communications in Perspective , Annual CTIT Workshop, Enschede, The Netherlands, - 2001.

2. Nilsson,K. Localization of corresponding points in fingerprints by complex filtering [Text] / K.Nilsson, J.Bigun - School of Information Science, Computer and Electrical Engineering (IDE), Halmstad University, Halmstad, Sweden - 2003.

3. Le,T.H., Fingerprint reference point detection for image retrieval based on symmetry and variation [Text] /T.H.Le, H.T.Van - Pattern Recognition, Department of Computer Science, Ho Chi Minh City University of Natural Science, Ho Chi Minh City, Vietnam - 2012.

4. Wti,N. Model based algorithm for singular point detection from fingerprint images [Text] / N.Wti, J.Zhou - Pattern Recognition, Department of Computer Science, Ho Chi Minh City University of Natural Science, Ho Chi Minh City, Vietnam - 2004.

5. Maltoni, D.. Handbook of Fingerprint Recognition [Text] /, D.Maltoni, D.Maio, A.K.Jain, S.Prabhakar - М.: Springer-Verlag London - 2009.

6. Cappelli,R. MCC: a Baseline Algorithm for Fingerprint Verification in FVC-onGoing [Text] / R.Cappelli, M.Ferrara, D.Maltoni, M.Tistarelli - Proceedings 11th International Conference on Control, Automation, Robotics and Vision (ICARCV), Singapore, December - 2010.

7. Fronthaler,H. Local features for enhancement and minutiae extraction in fingerprints [Text] /H,Franthaler, K.Kollreider, J.Bigun - IEEE Trans Image Process - 2008.

8. Кузин, Л.Т. Основы кибернетики [Текст] / Л.Т.Кузин. М.: Т.2 Москва, Энергия, 1979.

9. Препарата,Ф. Вычислительная геометрия: Введение [Текст] / Ф. Препарата, М.Шеймос. М.: Москва, Мир, 1989.

10. Турканов,Г. Классификатор Байеса для переменного количества признаков [Текст] / Г.Турканов, Е.В.Щепин. М.: Тр. МФТИ, 2016.

11. Малыхин,Ю.В. Цепная развертка [Текст] / Ю.В.Малыхин, Е.В.Щепин. // Современные проблемы математики, механики и математической физики. - Москва, 2015.

12. Рутм,Г. CUDA Fortran для ученых и инженеров [Текст] /Г.Рутм, М.Фатика. - М.:ДМК Пресс, 2014, 364с.

13. Марковский, Н.Д. Параллельные вычисления на GPU. Архитектура и программная модель CUDA [Текст]: учеб. пособие / Н.Д. Марковский, Д.Н. Микушин. - М.: Изд-во Московского университета, 2012, 336с.



Приложение

Презентационные материалы

Размещено на Allbest.ru

...