Система идентификации личности по отпечаткам пальцев

9

Федеральное агентство по образованию

Государственное образовательное учреждение

высшего профессионального образования

«ИЖЕВСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ»

Факультет «Информатика и вычислительная техника»

Кафедра «Программное обеспечение»

ПОЯСНИТЕЛЬНАЯ ЗАПИСКА

к дипломной работе на тему:

«Система идентификации личности по отпечаткам пальцев. Подсистема распознавания»

Дипломник студент группы 10-19-1 Вотинцев А.С.

Руководитель д.т.н., профессор Мурынов А.И.

Консультант по экономической части к.э.н., доцент Радыгина И.И.

Консультант по безопасности и экологичности проекта Якименко Г.Ф.

Нормоконтроль Соболева В.П.

Рецензент вед. Инженер Кропачева Л.Н.

Заведующий кафедрой «Программное обеспечение» д. т. н., профессор

Мурынов А.И.

РЕФЕРАТ

Пояснительная записка к дипломной работе на тему «Система идентификации личности по отпечаткам пальцев. Подсистема распознавания» оформлена на 128 листах, содержит 27 рисунков, 18 таблиц.

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

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

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

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

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

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

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

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

СОДЕРЖАНИЕ

ВВЕДЕНИЕ

1. РАЗРАБОТКА СИСТЕМЫ ИДЕНТИФИКАЦИИ ЛИЧНОСТИ ПО

2. ОТПЕЧАТКАМ ПАЛЬЦЕВ

1.1. Обоснование целесообразности разработки системы идентификации

личности

по отпечаткам пальцев

1.1.1.Назначение системы

1.1.2.Характеристика функциональной структуры системы

1.1.3.Обоснование цели создания системы

1.1.4.Обоснование состава автоматизируемых задач

1.2.Аналитический обзор

1.2.1. BioLink

1.2.1.1. BioLink BioTime 2006

1.2.1.2. BioLink Authenteon Software Appliance (ASA)

1.2.2. Microsoft IntelliMouse Explorer with Fingerprint Reader

1.2.3. Сотовый телефон GI100

1.2.4. Adobe Photoshop

1.2.5. FineReader

1.2.6. Вывод по аналитическому обзору

1.3. Основные требования к системе

1.3.1. Основные цели создания системы и критерии эффективности ее функционирования

1.3.2. Функциональное назначение системы

1.3.3. Особенности и условия эксплуатации системы

1.3.4. Требования к функциональной структуре

1.3.5. Требования к техническому обеспечению

1.3.6. Требования к информационному обеспечению

1.3.7. Требования к программному обеспечению

1.4. Основные технические решения проекта системы

1.4.1. Решение по комплексу технических средств

1.4.2. Описание системы программного обеспечения

2. РАЗРАБОТКА ПОДСИСТЕМЫ РАСПОЗНАВАНИЯ

2.1. Описание постановки задачи распознавания

2.1.1. Характеристика задачи

2.1.2. Входная информация

2.1.3. Выходная информация

2.1.4. Математическая постановка задачи

2.2. Описание алгоритма преобразования абсолютных параметров минюций к относительным параметрам

2.2.1. Назначение и характеристика алгоритма преобразования абсолютных параметров минюций к относительным

2.2.2. Используемая информация

2.2.3. Результаты решения

2.2.4. Математическое описание алгоритма преобразования абсолютных параметров минюций к относительным

2.2.4.1. Алгоритм нахождения габаритных размеров и количества точек в непрерывной области

2.2.5. Требования к контрольному примеру

2.2.6. Список условных обозначений

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

2.3.1. Назначение и характеристика алгоритма сравнения структурных представлений отпечатков пальцев

2.3.2. Используемая информация

2.3.3. Результаты решения

2.3.4. Математическое описание алгоритма нахождения статистических характеристик цветового кластера

2.3.5. Алгоритм нахождения статистических характеристик цветового кластера

2.3.6. Требования к контрольному примеру

2.3.7. Список условных обозначений

2.4. Описание подпрограммы «OnBnClickedCompare»

2.4.1. Вводная часть

2.4.2. Функциональное назначение

2.4.3. Описание информации

2.4.4. Используемые подпрограммы

2.4.5. Схема подпрограммы «OnBnClickedCompare»

2.5. Описание подпрограммы «Convert»

2.5.1. Вводная часть

2.5.2. Функциональное назначение

2.5.3. Описание информации

2.5.4. Используемые подпрограммы

2.5.5. Схема подпрограммы «Convert»

2.6. Описание подпрограммы «CompareWithBase»

2.6.1. Вводная часть

2.6.2. Функциональное назначение

2.6.3. Описание информации

2.6.4. Используемые подпрограммы

2.6.5. Схема подпрограммы « CompareWithBase»

2.7. Описание подпрограммы «Compare»

2.7.1. Вводная часть

2.7.2. Функциональное назначение

2.7.3. Описание информации

2.7.4. Используемые подпрограммы

2.7.5. Схема подпрограммы «Compare»

2.8. Описание контрольного примера

2.8.1. Назначение

2.8.2. Исходные данные

2.8.3. Контрольный пример

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

3. ОРГАНИЗАЦИОННО-ЭКОНОМИЧЕСКАЯ ЧАСТЬ

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

3.2. Расчет затрат на разработку подсистемы распознавания в системе идентификации личности по отпечаткам пальцев

4. БЕЗОПАСНОСТЬ И ЭКОЛОГИЧНОСТЬ ПРОЕКТА

4.1. Анализ опасных и вредных факторов, возникающих при работе на компьютере

4.2. Техника безопасности при эксплуотации компьютера

4.3. Организация рабочего места оператора

4.4. Требования к параметрам микроклимата помещения

4.5. Требования к освещению и расчет искусственного освещения

4.6. Пожарная безопасность

ЗАКЛЮЧЕНИЕ

ЛИТЕРАТУРА

ПРИЛОЖЕНИЕ 1 ТЕКСТ ПРОГРАММЫ

ПРИЛОЖЕНИЕ 2 РУКОВОДСТВО ПРОГРАММИСТА

ПРИЛОЖЕНИЕ 3 РУКОВОДСТВО ОПЕРАТОРА

ПРИЛОЖЕНИЕ 4 РЕЗУЛЬТАТЫ ТЕСТИРОВАНИЯ

ПРИЛОЖЕНИЕ 5 АЛЬТЕРНАТИВНОЕ ИСПОЛЬЗОВАНИЕ ПРОГРАММЫПЕРЕЧЕНЬ УСЛОВНЫХ ОБОЗНАЧЕНИЙ

СТ - специфическая точка - миньюция

БД - база данных с отпечатками

PIN - персональный идентификационный номер

ПЗС - память с зарядовой связью

КМОП - технология изготовления микросхем - кремний метал оксид полупроводник

ОП - отпечаток пальца

dpi - количество точек на дюйм (dot per inch)

ПО - программное обеспечение

ОС - операционная система

ЭВМ - электронно-вычислительная машина

ПК - персональный компьютер

LIFO - Last In First Out, метод обработки информации в структурах данных

MFC - Microsoft Foundation Class

ВВЕДЕНИЕ

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

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

Отпечаток пальца образует так называемые папиллярные линии на гребешковых выступах кожи, разделенных бороздками. Из этих линий складываются сложные узоры (дуговые, петлевые и завитковые), которые обладают свойствами индивидуальности и неповторимости, что позволяет абсолютно надежно идентифицировать личность. Хотя процент отказа в доступе уполномоченных пользователей составляет около 3, процент ошибочного доступа - меньше одного к миллиону. Преимущества доступа по отпечатку пальца - простота использования, удобство и надежность. Весь процесс идентификации занимает мало времени и не требует усилий от тех, кто использует данную систему доступа. Исследования также показали, что использование отпечатка пальца для идентификации личности является наиболее удобным из всех биометрических методов. Вероятность ошибки при идентификации пользователя намного меньше в сравнении с другими биометрическими методами /2/. Кроме того, устройство идентификации по отпечатку пальца не требует много места на клавиатуре или в механизме.

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

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

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

Типы минюций

Рис. 1

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

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

РАЗРАБОТКА СИСТЕМЫ ИДЕНТИФИКАЦИИ ЛИЧНОСТИ ПО ОТПЕЧАТКАМ ПАЛЬЦЕВ

1.1. Обоснование целесообразности разработки системы идентификации личности по отпечаткам пальцев

1.1.1. Назначение системы

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

Программный продукт найдет применение в различных прикладных системах, включая:

1) системы гражданской идентификации;

2) криминалистические системы идентификации;

3) крупномасштабные коммерческие приложения.

Системы гражданской идентификации включают в себя:

- водительские паспорта;

- национальные идентификационные карты граждан;

- регистрация избирателей;

- регистрация для социальных программ;

- иммиграционная регистрация, визы;

- идентификация сотрудников государственных учреждений.

Криминалистические системы идентификации включают в себя:

- находится ли данный гражданин в розыске;

- прежние судимости;

- регистрация заключенных/контроль доступа;

- мобильные и удаленные приложения;

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

Крупномасштабные коммерческие приложения включают в себя:

- доступ к Web-ресурсам, электронная коммерция;

- доступ для пользователей и сотрудников;

- финансовые сервисы, проверка оплаты;

- доступ в здания и помещения;

- программы лояльности;

1.1.2. Характеристика функциональной структуры системы

Функциональная схема системы приведена на рис. 1.1.

Обработка изображений состоит из следующих этапов:

1) ввод изображения в систему идентификации личности по отпеаткам пальцев;

2) в подсистеме анализа изображения происходит обработка растра с целью подавления шумов, а так же устранение типичных искажений изображения, таких как разрывы или слипания дуг папиллярного узора;

3) в подсистеме анализа изображения происходит выделение локальных особенностей, таких как окончание и раздвоение, для дальнейшего распознавания отпечатка;

4) в подсистеме распознавания происходит преобразование абсолютных параметров специальных точек к относительным параметрам для предотвращения влияния параллельного переноса и поворота пальца при сканировании отпечатка;

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

Функциональная схема системы идентификации личности по отпечаткам пальцев

- подсистема анализа - подсистема распознавания

Рис. 1.1

1.1.3. Обоснование цели создания системы

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

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

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

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

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

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

1.1.4. Обоснование состава автоматизируемых задач

Реализация системы идентификации личности по отпечаткам позволит интегрировать в едином интерфейсе все этапы обработки изображения отпечатка пальца и сравнения его с другими отпечатками:

1) анализ параметров изображения, выявление дфектов сканирования и их устранение;

2) выделение локальных особенностей - минюций. Формирование списка минюций в абсолютных параметрах;

3) сортировка списка абсолютных параметров, исключение ложных и ненадежных минюций;

4) конвертирование абсолютных параметров в отностительные, формирование списка относительных параметров;

5) установка системы допусков для учета корреляцции изображений;

6) учет всех зарегистрированных отпечатков;

7) распознавание отпечатка посредствам поиска совпадающих специальных точек в базе с отпечатками;

8) cпособ хранения описания отпечатков позволяет применять результат работы программы для различных сфер дейтельности.

1.2. Аналитический обзор

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

1.2.1. BioLink

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

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

1.2.1.1. BioLink BioTime 2006

BioTime 2006 - это система управления рабочим временем, являющаяся новейшей разработкой компании BioLink. Система BioTime 2006 упрощает обычные задачи учета и управления рабочим временем и обеспечивает простоту, легкость и удобство регистрации прихода и ухода сотрудников компании. Кроме того, система BioTime 2006 предоставляет различные виды отчетов по опозданиям, недоработкам и переработкам сотрудников, времени их прихода и ухода, а также автоматизирует создание табеля учета рабочего времени.

1.2.1.2. BioLink Authenteon Software Appliance (ASA)

Программный сервер BioLink Authenteon Software Appliance (ASA) - это программное обеспечение для сравнения шаблонов отпечатков пальцев BioLink. ASA объединяет в себе парольную защиту и клиент-серверную аутентификацию при входе в Windows, Novell и NFS при решении одной из самых актуальный на сегодняшний день проблем защиты - положительной идентификации пользователей корпоративной сети. Сервер поддерживает до 300 пользователей.

1.2.2. Microsoft IntelliMouse Explorer with Fingerprint Reader

Анонсированная Microsoft осенью 2004г. новая линейка продуктов с использованием биометрических технологий - сканер отпечатков пальцев, клавиатура со встроенным сканером и беспроводная оптическая мышь со сканером обладает возможностями:

1) снятие отпечатка пальца при кратковременном прикладывании пальца к сканеру;

2) ведение менеджера паролей для веб интерфейсов;

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

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

1.2.3. Сотовый телефон GI100

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

Ограничение доступа - при включении телефона происходит сканирование отпечатка пальца включившего /3/.

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

1.2.4. Adobe Photoshop

Профессиональный редактор растровых изображений. Основные возможности:

1) контроль цвета и тона компонент изображения: возможность подбора палитры, замены цветов, поддержка 32-битного цвета (прозрачности), возможность построения гистограмм распределения цвета;

2) интеллектуальное редактирование изображений: инструменты контекстной коррекции растра, позволяющие достичь фотореалистичности;

3) широкий набор фильтров, позволяющих модифицировать и улучшить изображение;

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

1.2.5. FineReader

Профессиональная программа распознавания печатного текста. Основные возможности:

1) загрузка изображения страницы из файла, получение изображения страницы со сканера;

2) интеллектуальное определение расположения строк и символов в тексте, распознавание символов при их неточном сканировании или зашумлении;

3) наличие возможности исправить неправильно распознанные символы;

4) возможность сохранения распознанного текста в виде документа word или pdf.

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

1.2.6. Вывод по аналитическому обзору

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

Среди программных продуктов, посвященных идентификации по папиллярному узору, можно выделить основные возможности:

1) программы реализуют возможность доступа по отпечаткам;

2) возможна обработка стандартными функциями (яркость, контрастность, изменение размера);

3) распознавание символов;

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

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

Эту задачу решает система распознавания личности по отпечаткам пальцев.

1.3. Основные требования к системе

1.3.1. Основные цели создания системы и критерии эффективности ее функционирования

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

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

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

1.3.2. Функциональное назначение системы

Реализация системы идентификации личности по отпечаткам позволит интегрировать в едином интерфейсе все этапы обработки изображения отпечатка пальца и сравнения его с другими отпечатками:

1) модификация изображения, исправление искажений;

2) выделение локальных особенностей - минюций. Формирование списка минюций в абсолютных параметрах;

3) сортировка списка абсолютных параметров, исключение ложных и ненадежных минюций;

4) конвертирование абсолютных параметров в отностительные, формирование списка относительных параметров;

5) установка системы допусков для учета корреляцции изображений;

6) сравнение одного отпечатка с множеством других.

1.3.3. Особенности и условия эксплуатации системы

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

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

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

- оптические;

- кремниевые;

- ультразвуковые.

Старейшей технологией сканирования отпечатка является оптическая. Сканирование отпечатка пальца мини-камерами на ПЗС или КМОП-чипе позволило существенно уменьшить стоимость систем идентификации. Но этот способ снятия отпечатка сталкивается с некоторыми трудноразрешимыми проблемами: получаемый образ зависит от окружающего освещения, на границах образа возможны искажения, датчик может быть относительно легко "обманут" (некоторые дешевые датчики можно "дурачить" печатной копией, сделанной на обычном копире). Остаются проблемы и с размерами сканера. Датчик не может быть меньше, чем фокусное расстояние камеры. Среди главных преимуществ оптических систем можно еще раз упомянуть относительно низкую цену и практическую неуязвимость к воздействию электростатического разряда.

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

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

Существуют и другие методы, либо использовавшиеся в прошлом, либо только разрабатываемые.

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

1.3.4. Требования к функциональной структуре

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

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

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

1.3.5. Требования к техническому обеспечению

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

Таблица 1.1

Технические характеристики персонального компьютера

Наименование	Значение
Частота процессора, МГц	от 900
Объем оперативной памяти, Мб	от 64
Разрешение экрана монитора	не менее 1024x768

1.3.6. Требования к информационному обеспечению

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

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

1.3.7. Требования к программному обеспечению

Систему целесообразно разрабатывать для функционирования под операционной системой семейства Windows, так как ОС данного класса наиболее широко распространены в современном мире. Платформой для разработки выбрана среда для разработки приложений Microsoft Visual Studio C++ 2003. Эта среда поддерживает алгоритмический язык C++ и обладает при этом возможностями быстрой разработки и проектирования визуальных интерфейсов, что особенно важно при работе с графической информацией.

1.4. Основные технические решения проекта системы

1.4.1. Решение по комплексу технических средств

Как уже отмечалось в п. 1.3.5, для достижения удобного пользователю режима функционирования системы необходимо следующая минимальная конфигурация персонального компьютера: частота процессора 900 МГц, объем оперативной памяти 64 Мб, монитор, поддерживающий разрешение 1024x768 точек. Также желательно наличие следующих периферийных технических средств: сканер отпечатков пальцев, цветной струйный принтер для вывода на печать результатов.

1.4.2. Описание системы программного обеспечения

Для реализации и функционирования проекта необходимо общесистемное программное обеспечение ОС Windows XP, в основе которой лежит ядро, характеризуемое 32-разрядной вычислительной архитектурой и полностью защищенной моделью памяти, что обеспечивает надежную вычислительную среду.

Разработка системы распознавания личности и ее подсистем будет вестись с использованием среды для разработки приложений Microsoft Visual Studio C++ 2003. Среда разработки включает в себя высокопроизводительный 32-битный компилятор, что позволяет оптимизировать создаваемый код. Microsoft Visual Studio C++ включает обширный набор средств, который повышает производительность труда программистов и сокращают продолжительность цикла разработки. Многофункциональная интегрированная среда разработки Microsoft Visual Studio C++ 2003 включает компилятор, удовлетворяющий стандарта ANSI/ISO, встроенный дизайнер форм, богатый набор средств для работы с компонентами, инструмент Solution Explorer, менеджер проектов и отладчик. Удобство разработки и эффективность созданных в данной среде разработки программа делают Microsoft Visual Studio C++ 2003 оптимальным выбором для построения исследовательской системы, какой является система распознавания личности.

РАЗРАБОТКА ПОДСИСТЕМЫ РАСПОЗНАВАНИЯ

1.5. Описание постановки задачи распознавания

1.5.1. Характеристика задачи

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

Представим структурное представление отпечатка пальцев в виде списка M, содержащего параметры специальных точек:

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

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

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

1) разработка алгоритма, обеспечивающего компенсацию влияния перемещения или поворота отпечатка пальца;

2) разработка и реализация системы допусков и критериев схожести при поиске подходящего отпечатка по существующей базе отпечатков;

3) сравнение минюций на отпечатках пальцев с использованием полученых критериев и обнаружение схожести отпечатков по количеству совпавших минюций.

1.5.2. Входная информация

Входной информацией являются список минюций в абсолютных параметрах, расположенный в памяти, содержащий все необходимые параметры. Каждый элемент массива содержит все необходимые параметры минюций: координаты целого типа - 2х4 байта, угол направления 8 байт, тип точки 1 байт, поэтому общий размер массива должен быть кратен 2*4+8+1 = 17 байт.

,

где X_i, Y_i - координаты минюций на растровом представлении изображения отпечатка пальцев, целые числа, величина которых ограничена размером изображения отпечатка в пикселах;

б_i - направление предполагаемого продолжения гребня на отпечатке пальцев в точки типа окончание и направление слипания для точки типа раздвоение, дробное число, величина которого изменяется (-pi, +pi);

Т_i - тип обнаруженной точки, битовое поле, принимает 2 значения «раздвоение» = 0 (false) и «окончание» = 1 (true);

k - количество минюций на исследуемом отпечатке.

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

Таблица 2.1

Формат элемента матрицы

Поле	Формат	Описание
x	Целое	Абцисса минюции на растре
y	Целое	Ордината минюции на растре
alpha	Целое	Ориентация минюции на растре
type	Байт	Тип минюции. Раздвоение или окончание
show	Байт	Видимость точки

2.1.3. Выходная информация

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

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

Таблица 2.2

Формат строки

Поле	Формат	Описание
Name	Строковое	Имя отпечатка (наименование файла, из которого были взяты параметры)
Count	Целое	Количество минюций совпавших при сравнении отпечатков.
Pct	Дробное	Степень сходства отпечатков в процентах, принимает значения (0, 100].

1.5.3. Математическая постановка задачи

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

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

На рис. 2.1 представлено изображение отпечатка пальца, с обнаруженными на нем минюциями. Линиями представлено относительное расположение точек относительно центральной.

На рис. 2.2 представлено изображение отпечатка того же пальца, но повернутого относительного первого на 45 градусов. Линиями представлено относительное расположение точек относительно центральной.

Прямой отпечаток

Рис. 2.1

Повернутый отпечаток

Рис 2.2

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

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

Область допуска

Рис. 2.3

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

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

Работа подсистемы реализуется следующими этапами:

- преобразование абсолютных параметров минюций к относительным параметрам минюций;

- разработка системы допусков для сравнения минюций;

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

Функциональная схема подсистемы представлена на рис.2.4

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

Рис. 2.4



1.6. Описание алгоритма преобразования абсолютных параметров минюций к относительным параметрам

1.6.1. Назначение и характеристика алгоритма преобразования абсолютных параметров минюций к относительным

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

Представим структурное представление отпечатка пальцев в виде списка M, содержащего параметры специальных точек:

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

Так как необходимо оценить расстояние между каждой из пар минюций, сложность этих алгоритмов превышает o(N²), где N - количество обнаруженных минюций на изображении отпечатка пальца. В среднем количество точек на отпечатке не превышает 50, таким образом, потребуется 50² = 2500 операций, что является небольшим объемом вычислений. Тесты показывают, что современные пользовательские ЭВМ способны выполнять около операций вычисления расстояния в секунду.

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

1.6.2. Используемая информация

При реализации данного алгоритма используется массив информации, сформированный на предыдущем этапе обработки изображения отпечатка пальца в подсистеме анализа изображения. Каждый элемент массива представляет из себя структуру, содержащую все необходимые для обработки параметры минюций: координаты целого типа - 2х4 байта, угол направления 8 байт, тип точки 1 байт, поэтому общий размер массива должен быть кратен 2*4+8+1 = 17 байт.

,

где X_i, Y_i - координаты минюций на растровом представлении изображения отпечатка пальцев, целые числа, величина которых ограничена размером изображения отпечатка в пикселах;

б_i - направление предполагаемого продолжения гребня на отпечатке пальцев в точки типа окончание и направление слипания для точки типа раздвоение, дробное число, величина которого изменяется (-pi, +pi);

Т_i - тип обнаруженной точки, битовое поле, принимает 2 значения «раздвоение» = 0 (false) и «окончание» = 1 (true);

k - количество минюций на исследуемом отпечатке.

Для обработки массивов используется двунаправленный список. Список представляет собой вектор:

В данную информационную структуру можно заносить и извлекать элементы с любой стороны.

1.6.3. Результаты решения

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

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

Таблица 2.3

Структура элемента массивазаписи

Поле	Формат	Описание
lij	Целое	Расстояние между i и j точками
A1ij	Дробное	Угол между собственным направлением точки i и направлением из точки i в точку j. A1ij[0, 2*M_PI)
A2i	Дробное	Угол между собственными направлениями точек i и j. A2ij[0, 2*M_PI)

1.6.4. Математическое описание алгоритма преобразования абсолютных параметров минюций к относительным

Обобщенное математическое описание преобразования приведено в п.2.1.4.

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

,

где i, j - минюции

dLength_ij - расстояние между точками i и j

dAlpha1_ij - угол между направлением точки i и направлением на точку j

dAlpha2_ij - угол между направлением точки i и точки j

Alpha_i - угол вектора самой точки

Alpha_ij - угол вектора направления от точки i к точке j

На рис. 2.5 представлено расположение точки i относительно точки j со всеми полученными параметрами.

относительные параметры

Рис. 2.5

1.6.4.1. Алгоритм нахождения габаритных размеров и количества точек в непрерывной области

1. Очистить список RelFing с относительными параметрами отпечатка

2. Если список AbsFing пуст, перейти к пункту 20

3. Для каждого элемента iterA1 списка AbsFing выполнить пункты 4 - 19

4. Очистить список listDots с относительными параметрами точки

5. Для каждого элемента iterA2 списка AbsFing выполнить пункты 5 - 17

6. Если iterA2 == iterA1, перейти к пункту 5.

7. l = |GetS(iterA1->coord, iterA2->coord)|

8. vecAB = GetAlpha(iterA2->coord, iterA1->coord)

9. tmpa = iterA1->alpha - vecAB;

10. Если (tmpa < 0), переход к п. 11, иначе переход к п. 12

11. tmpa = 2*M_PI + tmpa;

12. a1 = |tmpa * 180.0/M_PI +0.5|

13. tmpa = iterA2->alpha - iterA1->alpha

14. Если (tmpa < 0) , переход к п. 15, иначе переход к п. 16

15. tmpa = 2*M_PI + tmpa;

16. a2 = |tmpa * 180.0/M_PI +0.5|

17. Добавить в список listDots параметры очередной точки - l, a1, a2, перейти к п. 5.

18. отсортировать список listDots

19. занести относительные параметры точки listDots в список отпечатка RelFing, перейти к п. 3

20. Конец

1.6.5. Требования к контрольному примеру

Контрольный пример должен содержать отпечатки более чем с одной обнаруженной минюцией.

1.6.6. Список условных обозначений

RelFing - список минюций в относительных параметрах

AbsFing - список минюций в абсолютных параметрах

listDots - относительные параметры точки

iterA1 - исследуемая точка в абсолютных параметрах

iterA2 - точка в абсолютных параметрах, относительно которой вычисляется точка iterA1

l - расстояние между точками iterA1 и iterA2

GetS - функция вычисления расстояния

|| - округление до ближайшего целого

vecAB - вектор между направлениями точки iterA1 и iterA2

GetAlpha - функция вычисления угла между векторами

tmpa

a1 = угол между направлением самой точки и направлением на другую точку

a2 = угол между направлениями точек.

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

1.7.1. Назначение и характеристика алгоритма сравнения структурных представлений отпечатков пальцев

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

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

1.7.2. Используемая информация

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

1.7.3. Результаты решения

Результатами решения является список отпечатков из базы данных, структурное представление которых совпадает с исследуемым отпечатком или схоже с ним на несколько процентов. Структура элемента списка приведена в табл. 2.4.

Таблица 2.4

Структура записи об обнаруженных отпечатках

Поле	Формат	Описание
Name	Строковое	Имя отпечатка (наименование файла, из которого были взяты параметры)
Count	Целое	Количество минюций совпавших при сравнении отпечатков.
Pct	Дробное	Степень сходства отпечатков в процентах, принимает значения (0, 100].

1.7.4. Математическое описание алгоритма нахождения статистических характеристик цветового кластера

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

Область допуска

Рис. 2.6

Для вычисления степени сходства двух отпечатков происходит сравнение каждой минюции на обоих отпечатках:

M - список минюций на обрабатываемом образе

k - количество минюций на обрабатываемом образе

M = {m1, m2, …, mk}

N - список минюций одного отпечатка из базы отпечатков

l - количество минюций на отпечатке из базы отпечатков

N = {n1, n2, …, nl}

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

S = {mi, где i=(1..k), P(mi, N)}

r = | S | - количество совпавших точек.

P(mi , N) - Точка считается совпавшей, если относительно нее найдено необходимое количество удовлетворяющих условию точек.

Отпечатки считаются схожими, если количество совпавших точек превышает порог сходства (p):

r ? p - условия совпадения

r < p - условие не совпадения

1.7.5. Алгоритм нахождения статистических характеристик цветового кластера