Применение математических методов при организации пропускного режима

В курсовой работе мы будем рассматривать только те характеристики, которые применимы в системах контроля и управления доступом (СКУД) или в близких им задачах. В силу своего превосходства это в первую очередь именно статические характеристики. Из динамических характеристик на сегодняшний момент, только распознавание по голосу имеет хоть какую-то статистическую значимость (сравнимую с худшими статическими алгоритмами FAR~0.1%, FRR~6%), но лишь в идеальных условиях.

Чтобы ощутить  вероятности FAR и FRR, можно оценить, как  часто будут возникать ложные совпадения, если установить систему  идентификации на проходной организации  с численностью персонала N человек. Вероятность ложного совпадения полученного сканером отпечатка  пальца для базы данных из N отпечатков равна FAR∙N. И каждый день через пункт  контроля доступа проходит тоже порядка N человек. Тогда вероятность ошибки за рабочий день FAR∙(N∙N). Конечно, в  зависимости от целей системы  идентификации вероятность ошибки за единицу времени может сильно варьироваться, но если принять допустимым одну ошибку в течение рабочего дня, то:

(1)

Тогда получим, что стабильная работа системы идентификации при FAR=0.1%=0.001 возможна при численности персонала N≈30.

Отпечатки пальцев

Дактилоскопия (распознавание отпечатков пальцев) — наиболее разработанный на сегодняшний день биометрический метод идентификации личности. Катализатором развития метода послужило его широкое использование в криминалистике 20 века. Каждый человек имеет уникальный папиллярный узор отпечатков пальцев, благодаря чему и возможна идентификация. Обычно алгоритмы используют характерные точки на отпечатках пальцев: окончание линии узора, разветвлении линии, одиночные точки. Дополнительно привлекается информация о морфологической структуре отпечатка пальца: относительное положение замкнутых линий папиллярного узора, «арочных» и спиральных линий. Особенности папиллярного узора преобразовываются в уникальный код, который сохраняет информативность изображения отпечатка. И именно «коды отпечатков пальцев» хранятся в базе данных, используемой для поиска и сравнения. Время перевода изображения отпечатка пальца в код и его идентификация обычно не превышает 1с, в зависимости от размера базы.

Характерное значение FAR для метода распознавания отпечатков пальцев – 0.001%. Из формулы (1) получим, что стабильная  работа системы идентификации при FAR=0.001% возможна при численности персонала N≈300.

Преимущества и недостатки метода

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

Недостатки: папиллярный узор отпечатка пальца очень легко повреждается мелкими царапинами, порезами. Люди, использовавшие сканеры на предприятиях с численностью персонала порядка нескольких сотен человек заявляют о высокой степени отказа cканирования. Многие из сканеров неадекватно относятся к сухой коже и не пропускают стариков.[4]

Алгоритмы верификации

Алгоритмы ВЕРИФИКАЦИИ отвечают на вопрос «Тот ли это человек, за кого себя выдает». Они производят попарное сравнение  имеющегося и предоставленного набора информации, с их помощью реализуется  подтверждение личности человека. Результатом  верификации есть либо «Опознан», либо «Не опознан» с указанной долей  вероятности.

Алгоритм  верификации отпе-чатков пальцев  состоит из двух частей – регистрации  отпечатков пользователей в БД и  собственно самого процесса верификации. Однажды обученная система будет распознавать человека по его природному идентификатору - пальцу.

 

Принцип распознавания  человека по отпечатку пальца

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

Имея  известный набор особых точек {(x,y,θ,type)}, извлеченный при регистрации, и тестовый, алгоритм оценивает схожесть точечных образцов и выдает результат – «Опознан» или «Не опознан».

Схема работы алгоритма

1. Адаптивная  фильтрация, выделение зоны интереса 

2. Бинаризация,  выделение однородных областей

3. Морфологическая  обработка

4. Утоньшение 

5. Векторизация 

6. Векторная  постобработка

7. Сравнение  двух наборов особых точек

Адаптивная фильтрация, выделение  зоны интереса

Адаптивная  фильтрация направлена на:

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

2.Устранение мелких деффектов 
(затягивание небольших разрывов, 
сглаживание линий пальца)

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

Морфологическая обработка

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

Утоньшение

Морфологическая операция утоньшения приводит бинарное изображение к его скелету, в  котором толщина всех линий – 1 пиксел. Операция стягивает линии  в центр, не делая при этом разрывов. Реализовано на основе итеративной  нелинейной фильтрации с апертурой  фильтра 3х3.

 

 

 

Векторизация

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

Векторная постобработка

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

Некоторые из производимых операций:

• Удаление «мостов»
• Удаление «палочек»
• Соединение небольших разрывов
• Удаление «усиков»

 

 

 

Сравнение наборов особых точек

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

Типы датчиков отпечатков пальцев

Существует  большое количество различных типов  датчиков отпечатков пальцев – оптические (на эффекте полного внутреннего  отражения, оптических фибрах), электро-оптические, емкостные, температурные, пьезоэлектические, ультразвуковые. Среди них нет наилучшего, все они имеют свои преимущества и недостатки. 
 
Алгоритмы были опробованы на оптических, емкостных и пьезоэлектрических типах датчиков, а также на синтетических отпечатках.

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

Задача идентификации

Алгоритмы ИДЕНТИФИКАЦИИ отвечают на вопрос «Кто этот человек». Для этого один и  тот же входной отпечаток должен быть сравнен со всеми имеющимися в базе данных. Так как базы данных могут достигать очень больших  размеров, для уменьшения вычислений была введена классификация отпечатков пальцев. При идентификации производится сравнение только с имеющимися отпечатками  того же класса.

Классификация основывается на наличии в отпечатке  сингулярных точек в направлениях линий – петель, дельт и завитков.

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

Векторные архитектуры

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

 

Для решения  этой проблемы могут быть использованы векторные архитектуры процессоров  – SIMD решения (Single Instruction Multiple Data). Бόльшая часть операций, выполняемых над изображением, может быть распараллелена и выполнена одновременно разными АЛУ (арифметико-логическими устройствами).

Алгоритмы верификации были реализованы на SIMD-процессоре VC01 фирмы Alpha Mosaic, который имеет векторную архитектуру с кратностью шестнадцать. В результате верификация один к одному при частоте ядра 75 МГц занимала в среднем 350 мс, из которых 130 мс уходило на захват отпечатка пальца с емкостного датчика.[1]

Реализация алгоритма «сравнение по особым точкам»

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

План действий:

1.Бинаризация полученного изображения

2.Скелетизация изображения

3.Выделение точек

4.Сравнение точек

Реализация сделана на Python (версии 2.7.1), PIL(Python Imaging Library), для разбора картинки на пиксели.

Шаг 1. Бинаризация

Код первого  шага смотрите в Приложение 1.

 

 

Шаг 2. Скелетизация

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

здесь серым  обозначены пиксели, цвет которых не имеет значения

Восемь  первых шаблонов, являются основной частью. Четыре снизу для устранения «шума», при чем эти четыре так же могут быть повернуты на 90, 180 и 270 градусов, и ищутся вторым обходом изображния.

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

Код этого  действия смотрите в Приложении 2.

Шаг 3. Выделение особых точек

Тут все  тривиально. Если в окрестности из 8 точек, есть только одна черная, то это конечная точка. Если же их 2 то это просто  точка линии. Три — точка ветвления.

Код этого  шага смотрите в Приложении 3.

Шаг 4. Сравнение точек

Простой поиск точки, которая попадает в окрестность 30*30 и является точкой того же типа.

Код этого  шага смотрите в Приложении 4.

 

Заключение

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

Результаты  работы системы за неделю, учитывая, что в офисе работает N=100 человек:

 

FAR – 0,0001% (1 срабатывание за 5 рабочих дней)

FRR – 5% (каждому двадцатому человеку приходилось повторно прикладывать палец)

 

Характеристики FAR и FRR практически не меняются в зависимости от взятия временного промежутка. Система построена таким образом, чтобы ни в коем случае не пропустить человека, который не имеет на это право, а так же чтобы не было случайной регистрации одного сотрудника вместо другого.

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

Доступ по отпечаткам пальцев является оптимальным  для объектов с количеством  персонала до  нескольких сотен  человек.

 

Литература

1. Р.М. Болл. Руководство по биометрии - М.:Техносфера, 2007.
2. Структура организации ITV [Электронный ресурс]: http://www.itv.ru/company/management.php
3. Организация пропускного режима [Электронный ресурс]: http://bre.ru/security/11191.html
4. Биометрические методы идентификации человека [Электронный ресурс]: http://habrahabr.ru/post/126144/

 

 

 

 

 

 

Приложение

Приложение 1

def binary(img):

bImg=[]

for i in range (img.size[ 0 ]):

tmp=[]

for j in range (img.size[ 1 ]):

t=img.getpixel((i,j))

p=t[ 0 ] * 0.3 +t[ 1 ]* 0.59 +t[ 2 ] * 0.11

if p > 128 :

p= 1

else :

p= 0

tmp.append(p)

bImg.append(tmp)

return bImg

 

Приложение 2

def tmpDelete

(img): #вызов  процедуры скелетизации, на входе  список списков