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

      Рассматривая отпечаток пальцев с точки зрения технологий идентификации и аутентификации (верификации) клиента, сразу ссылаемся на сайт поставщика оборудования, компанию "Биолинк", а также на статью, детально описывающую использумый алгоритм распознавания отпечатка "Тестирование алгоритма распознавания отпечатков пальцев с использованием аппаратного сервера AVS и программы генерации искусственных отпечатков пальцев SFinGE", перепечатку которой в сокращенном варианте продублируем ниже.

 

       Принятые определения и сокращения

В данном документе используются следующие основные определения и сокращения:

 

      Цель данного документа

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

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

      В разделе «Создание искусственных отпечатков пальцев» речь пойдет о программном обеспечении SFinGE, позволяющем создавать искусственные ОП. База данных искусственных ОП использовалась при тестировании алгоритма BioLink. Здесь Вы найдете общую информацию о программе, ее основных параметрах, процессе и результате работы.

      Раздел «Тестирование алгоритма BioLink» посвящен собственно тестированию алгоритма BioLink.

      Раздел «Резюме» содержит общие выводы, сделанные исходя из результатов тестирования.

      В разделе «Ссылки» указаны основные источники информации, использованные при подготовке документа.

 

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

      Анатомия пальца

      Как известно, каждый человек имеет уникальные, неизменные отпечатки пальцев.

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

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

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

      На еще более локальном уровне ОП может быть охарактеризован локальными особенностями, или минюциями (иначе их называют характеристиками Фрэнсиса Гальтона, см. сноску [1]). На Рис. 1. Типы минюций показаны два типа минюций: разветвление папиллярной линии и окончание папиллярной линии.

      Сравнение минюций ОП составляет основу множества алгоритмов автоматического сравнения и распознавания ОП.

      

      Трудности при сравнении нескольких моделей отпечатков одного пальца

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

      Приложение пальца к сканеру считается правильным, если:

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

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

      В целом, сила приложения пальца к сканирующей поверхности распределяется неравномерно, уменьшаясь при смещении от центра к краям. На Рис. 2. Области контакта пальца со сканирующей поверхностью показаны три основные области пальца, находящиеся в непосредственном контакте со сканирующей поверхностью:

      Сотрудниками лаборатории Biometric Systems Lab университета г. Болоньи (Италия) был проведен следующий эксперимент: испытуемому предлагалось два раза приложить палец к сканирующему устройству: один раз палец был приложен правильно, а во втором случае палец был намеренно смещен после соприкосновения со сканирующей поверхностью, формируя таким образом деформацию кожи. Затем изображения полученных ОП были наложены друг на друга. Расхождения между особыми точками <нормального> и <деформированного> ОП оказались весьма значительными, особенно в районах b и с. Применение функции модели искажения, также разработанной в данной лаборатории, показало, что модель справляется с подобными деформациями.

      Разработанная Лабораторией формула позволяет сократить расстояние между особыми точками от 15,19 до 2,89 единиц. Таким образом, формула деформации представляет собой хороший инструмент для разработки алгоритмов распознавания, устойчивых к искажениям.

      Параметры и способы тестирования

      Для того чтобы провести качественное тестирование методик распознавания ОП и оценить значения параметров FAR и FRR, необходимо наличие БД с большим количеством моделей ОП (порядка 100-200 тысяч моделей ОП). Необходимость наличия БД такого большого объема объясняется тем, что эксперимент проводится над очень малыми числами - 10-х. Протестировать такие малые числа на небольших БД просто невозможно.

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

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

 

      Создание искусственных отпечатков пальцев

      Программа SFinGE вер. 2.0

      Программное обеспечение SFinGE позволяет создавать (с минимальными затратами) огромные БД с целью проведения тестов алгоритмов распознавания ОП. Например, БД с 10 тысячами ОП была создана на одном компьютере (Pentium IV) всего за 10 часов.

      Программа SFinGE вер. 2.0. сертифицирована BTC (Biometric Testing Center).

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

      Программа SFinGE вер. 2.0 позволяет создавать искусственные ОП, похожие на настоящие, полученные при помощи различных сканеров: емкостных или оптических.

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

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

      Основные параметры программы

      Number of fingers: количество искусственных ОП, которые будут сгенерированы программным обеспечением SFinGe. Возможные значения: от 0 до 100 тысяч.

      Impressions per finger: количество изображений отпечатков одного пальца, которые будут сгенерированы SFinGe. Возможные значения: от 0 до 10. Таким образом, общим количеством сгенерированных ОП будет Number of fingers х Impressions per finger.

      Generator seed: данный параметр позволяет определить внутренний идентификатор при случайной выборке набора внутренних идентификаторов ОП. Этот параметр позволяет повторить ту же самую базы данных любому другому пользователю SFinGE.

      Class distribution: данный параметр определяет, будет ли ОП сгенерирован в соответствии с равномерным распределением 5 типов кожных узоров (дуга, шатровая дуга, левая петля, правая петля, завиток) или с естественным распределением (дуга = 3,7%, заостренная дуга = 2,9%, левая петля = 33,8%, правая петля = 31,7%, завиток = 27,9%).

      Rotation: угол поворота сгенерированного ОП.

      Deformation: величина искажения ОП.

      Noise: уровень зашумления ОП.

      Scratches Степень наличия искусственно созданных царапин.

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

      Журнал работы

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

      Время генерации

      Процедуру генерации ОП можно условно представить в виде двух основных шагов:

      Выполнение вышеуказанных операций занимает в среднем: 11,5 сек для создания основного изображения ОП (мастера); 4,9 для генерации изображений одного и того же ОП с использованием мастера.

      Процесс генерации

      Процесс генерации искусственного ОП представлен 4 основными стадиями:

      Генерация поля направлений

      Модель, предложенная Шерлоком и Монро, позволяет искусственно создавать поле направлений на базе информации о положении центров и дельт. На Рис. 4. Поле направлений изображен пример поля направлений, созданный с использованием этого метода. :

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

      Генерация поля плотности

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

      На Рис. 5. Поле плотности показан пример поля плотности:

      Создание папиллярных линий

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

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

      Результат применения фильтра Габора, используемого для генерации папиллярных линий, показан на Рис. 6. Генерация папиллярных линий:

      Процесс создания папиллярных линий ОП (путем наращивания) при наличии нескольких изолированных выступов представлен на Рис. 7. Процесс наращивания папиллярных линий:

      Зашумление

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

      Процедура искусственного зашумления проходит в несколько шагов:

      Результат генерации

      Результатом процесса генерации искусственных ОП программы SFinGE является изображение ОП в формате .tiff. Примеры изображений искусственных ОП, созданных с использованием SFinGE, представлены на Рис. 8. Искусственные отпечатки пальцев:

     

      Тестирование алгоритма BioLink

      Цель проведения тестирования

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

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

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

      Цель проведенного данного тестирования заключается в определении точности и скорости разработанного алгоритма распознавания ОП.

      Средства проведения тестирования

      Тестирование алгоритма распознавания ОП, разработанного компанией BioLink, проводилось сотрудниками компании в феврале 2002 года в Московском офисе компании BioLink.

      При проведении тестов в качестве единого хранилища и средства оперативного поиска моделей ОП использовался программно-аппаратный сервер Authenteon Velocity Server, который разработан на базе многопроцессорной архитектуры (512 DSP-процессоров) с параллельной обработкой задач.

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

      С использованием программного обеспечения SFinGE было создано 100 тысяч искусственных ОП, и для каждого из них получено 4 изображения (программа SFinGE позволяет создавать до 10 изображений одного пальца, отличающихся степенью деформации, сдвигами и углом поворота). Таким образом, было автоматически сгенерировано 400 тысяч изображений. При этом 3 из 4 изображений были использованы для создания паспорта ОП, а 4-ое изображение было отдельно преобразовано в модель, которая использовалась для сравнения.

      Из 100 тысяч паспортов, 90 тысяч (каждый паспорт содержит по 3 модели ОП) были занесены в базу данных сервера AVS. Кроме того, в базу сервера AVS были занесены 5 тысяч паспортов (также по 3 модели ОП), полученные в результате сканирования реальных пальцев сканерами BioLink в рамках специально организованного мероприятия.

      Таким образом, БД сервера AVS при проведении тестирования составила: 90 тысяч искусственных ОП х 3 модели + 5 тысяч реальных ОП х 3 модели = 285 тысяч моделей ОП.

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

      При создании базы данных сервера AVS файлы в формате .tiff и .bmp, содержащие изображения ОП, были преобразованы в файлы специального формата BioLink Template.

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

      Результатом работы алгоритма при сравнении предъявленной и хранящейся в БД моделей является число, называемое «мерой сходства». В данном тестировании было принята мера сходства, равная 550, гарантирующая идентичность ОП.

      При проведении тестирования решение о совпадении предъявленной и хранящейся в БД модели ОП принимает тот, кто проводит тестирование. Алгоритм лишь выдает числовой критерий оценки степени близости двух моделей ОП, который может быть меньше 550 (в этом случае модели ОП не совпадают) или больше 550 (модели ОП совпадают). На основании этих чисел оценивается ошибочность или правильность работы алгоритма.

      Основные этапы тестирования

      Тестирование алгоритма и оценка производительности сервера аутентификации AVS проходило следующим образом – на вход сервера, в базе данных которого находились 285 тысяч моделей ОП, были направлены:

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

      Результаты тестирования

      В результате тестирования было получены следующие результаты:

      Результаты работы алгоритма

      Таблица 1. Результаты работы алгоритма

      Объем тестовой базы данных - 285 000 моделей отпечатков

Группы проверки	Кол-во проверок	Параметр	Результаты абсолютные	Результаты относительные
SFinGE, для которых есть паспорта в базе	10 000	FAR	0	0
		FRR	739	(7,39%)
SFinGE, для которых нет паспортов в базе	10 000	FAR	0	0
		FRR	N/A	N/A
Настоящие пальцы (есть в базе)	5 058	FAR	0	0
		FRR	147	(2,9%)

 

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

      Необходимо отметить, что в реальном прикладном программном обеспечении BioLink показатель FAR сведен к нулю за счет дополнительного сравнения «один к одному» после того, как получены результаты сравнения «один ко многим».

      Таким образом, в среднем алгоритм при работе продемонстрировал следующие показатели точности: FAR < 10-9 при FRR = 3%. Данные показатели являются революционными с точки зрения скорости обработки больших баз данных, а также с точки зрения показателя FAR (при приемлемом показателе FRR) в мировой биометрической индустрии.

      Резюме

      Проведенное тестирование позволило прийти к следующим основным выводам:

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

      Ссылки

      При создании данной работы были использованы следующие основные документы и источники всемирной паутины Интернет:

      1. R. Cappelli , A. Erol , D. Maio, D. Maltoni, Synthetic Fingerprint-image Generation, Deis - University of Bologna - Italy, NNCVIS-Middle East Technical University, Ankara-Turkey.

      2. R. Cappelli, D. Maio, D. Maltoni, Modelling Plastic Distortion in Fingerprint Images, DEIS, CSITE - CNR, Universita di Bologna, Bologna - Italy.

      3. http://bias.csr.unibo.it/research/biolab/sfinge.html - сайт Biometric Systems Lab.

      4. http://www.peoples.ru/state/detective/galton/#history - биография Фрэнсиса Гальтона.

 

      Сноска

      С 6 августа по 9 ноября 1888 года в Лондоне было совершено несколько ужасных убийств, лишивших лондонцев покоя. За жестокость убийцу прозвали Джеком Потрошителем. Скотланд-Ярд занялся составлением списков рецидивистов, однако описания внешности подозреваемых были поверхностными. Сотрудники отдела надзора за преступниками много дней рылись в картотеке, чтобы найти нужную карточку. Подобная ситуация была во всей Европе. Именно в эти дни сэр Фрэнсис Гальтон в своей лаборатории изучал тысячи отпечатков пальцев. Он находился на пороге великого открытия, благодаря которому его имя навсегда вошло в историю криминалистики.

      Будучи молодым человеком, Фрэнсис чем только не занимался: и математикой, и медициной, и антропологии, и биологией, и историей, и расовой генетикой. Потом он полностью погрузился в изучение вопросов наследственности, причин болезней и смерти, в результате чего стал основателем евгеники, придумав не только сверхпопулярную науку, но и сам термин. Книга его кузена Чарльза Дарвина "О происхождении видов" побудила Гальтона заняться вопросами наследования физических и умственных способностей и особенностей. Ученому нужны были статистические данные о многих поколениях разных семей. Год за годом он собирал эти данные. Для получения более обширного материала и был создан развлекательный павильон на международной выставке. Добытые сведения поступали в архив Гальтона. Чуть позже ученый открыл в знаменитом лондонском музее Саут-Кенсингтон постоянную лабораторию, где продолжали проводиться измерения. Именно в этой лаборатории и была впоследствии открыта дактилоскопия.

      В то время в полиции использовался бертильонаж: система регистрации карточек с характеристиками преступников, разработанная Бертильоном. Королевское общество заинтересовалось методом Бертильона и обратилось к Фрэнсису Гальтону с просьбой изучить этот вопрос и выступить с докладом на одной из знаменитых "пятниц" королевского научного общества. Во время выступления Гальтон упомянул, что, кроме системы Бертильона, существует еще один способ идентификации - с помощью отпечатков пальцев, на что никто пока не обращал внимания. Сразу же после доклада Гальтон принялся за работу. Его интересовало, действительно ли отпечатки пальцев не меняются в течение всей жизни человека. Гальтон припомнил, что один из его друзей, полицейский Хершель, вот уже 30 лет собирает отпечатки пальцев разных людей, ничего при этом не имея в виду. Гальтон погрузился в изучение этой коллекции, начал составлять собственную. По его распоряжению отпечатки пальцев брали у всех подряд, даже у посетителей лаборатории музея Саут-Кенсингтон. Результатом его исследований оказалась теория о том, что людей с идентичными пальцами не существует. Криминалисты пользуются этой теорией и по сей день. Открытие произвело эффект разорвавшейся бомбы, а для Скотланд-Ярда метод Гальтона оказался спасительной соломинкой – он позволил раскрыть сотни "висяков". Это была настоящая сенсация конца XIX века. Дактилоскопия за несколько лет завоевала Европу, Америку, чуть позже - Японию, Россию, страны Азии. В 1895 году дактилоскопия была взята на вооружение Скотланд-Ярдом, а в 1900 году в Англии перестали применять бертильонаж, и идентификация преступников стала строиться только на дактилоскопическом методе Гальтона, который стал официальным методом Скотланд-Ярда.