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

Размещено на http://www.allbest.ru/

Содержание

Введение

1. Предметная область

1.1 Анализ предметной области

1.2 Актуальность разработки системы

1.3 Основные назначения системы

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

1.5 Постановка задачи

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

2. Определение системных и технических разработок

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

2.1.1 Компания BioLink

2.1.2 Microsoft IntelliMouse Explorer with Fingerprint Reader

2.1.3 Редактор изображений Adobe Photoshop

2.1.4 FineReader - программное обеспечение распознавания текста

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

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

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

2.5 Функциональная структура системы

2.6 Техническое обеспечение системы

2.7 Информационное обеспечение системы

2.8 Программное обеспечение системы

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

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

3.2 Описание постановки задачи выявления дефектов сканирования и их устранение

3.3 Описание алгоритма «Формирование списка линий»

3.4 Описание алгоритма «ReadLine»

3.5 Описание постановки задачи сортировки списка абсолютных параметров, исключение ложных и ненадежных минюций

3.6 Описание подпрограмм

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

4. Экономический анализ

4.1 Цель технико-экономического обоснования

4.2 Главные понятия экономики и рыночных отношений

4.3 Вычисление объема и трудоемкости разработки ПО

5. Безопасность жизнедеятельности

5.1 Анализ условий труда

5.2 Мероприятия по улучшению условии труда (освещение, кондиционирование воздуха)

5.2.1 Расчет систем кондиционирования

5.2.2 Расчет искусственного освещения

Заключение

Список литературы

Приложения

Введение

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

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

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

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

Работа посвящена анализу растра, получение объектной модели, и поиска схожих отпечатков.

1. Предметная область

1.1 Анализ предметной области

отпечаток палец минюция сканирование

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

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

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

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

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

Рисунок 1.1 - Типы минюций

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

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

1.2 Актуальность разработки системы

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

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

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

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

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

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

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

1.3 Основные назначения системы

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Многофункциональная схема системы, показанной на рисунке 1.2.

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

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

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

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

4) подсистема анализа изображения сортируются приобретенные характеристики локальных особенностей;

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

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

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

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

1.5 Постановка задачи

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

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

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

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

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

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

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

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

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



2. Определение системных и технических разработок

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

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

2.1.1 Компания BioLink

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

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

Система управления временем BioLink BioTime 2006

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

Программный сервер BioLink

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

2.1.2 Microsoft IntelliMouse Explorer with Fingerprint Reader

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

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

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

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

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

2.1.3 Редактор изображений Adobe Photoshop

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

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

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

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

возможность создания многих независимых слоев в одном изображении.

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

2.1.4 FineReader - программное обеспечение распознавания текста

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

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

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

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

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

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



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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

оптические;

кремниевые;

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

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

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

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

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

2.5 Функциональная структура системы

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

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

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

2.6 Техническое обеспечение системы

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

Таблица 2.1- Технические характеристики персонального компьютера.

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

2.7 Информационное обеспечение системы

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

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

2.8 Программное обеспечение системы

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



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

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

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

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

Модели представления изображений в ЭВМ можно разделить на два типа: растровые и векторные.

Наиболее распространенная форма представления «сырых» изображений на ЭВМ - это растр. Изображение в этом случае представляет собой матрицу из NxM точек (пикселей). Визуализация растровых изображений достаточно проста и заключается в построчном выводе его пикселей на экран. Однако модель этого типа не несет в себе структурной и тем более семантической информации, что ограничивает сферу ее применения. При вводе изображений из реального мира в ЭВМ они часто предстают в растровой форме.

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

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

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

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

Рисунок 3.1 - Типы минюций

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

Входная информация. Входной информацией является битовый растр отпечатка, полученный с помощью сканирования разрешением 600dpi. Расширение битового файла по умолчанию *.bmp. Формат bmp (от слов BitMaP - битовая массив) представляет из себя несжатое (в основном), что позволяет не вносить погрешностей, изображение, которое довольно легко читается и выводится в ОС Windows, в которой есть специальные функции API, которые в этом помогают.

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

Структура массива:

Таблица 3.1 - Формат строки файла со структурным описанием.

Поле	Формат	Описание
X	Целое	Абсцисса минюции на растре
Y	Целое	Ордината минюции на растре
	Целое	Ориентация минюции на растре
T	Байт	Тип минюции. Раздвоение или окончание
k	Целое	Количество минюций

Математическая постановка задачи. Работа подсистемы реализуется следующими этапами:

корректировка входного образа, устранение дефектов и искажений;

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

фильтрация полученного списка параметров;

Для решения поставленных задач требуются стандартные операции для работы с массивом, которые представлены в таблице 3.2.

Таблица 3.2 - Операции над массивом

Обозначение	Расшифровка
|Array|	количество элементов массива
Array[i]	обращение к i-му элементу массива
	операция добавления элемента E в конец массива M
Delete(Array,Pos)	операция удаления элемента на позиции Pos из массива Array
Delete(Array, Element)	операция удаления элемента Element из массива Array
Pos(Array,Element)	операция получения номера элемента Element в массиве Array
Array1Array2	операция добавления в конец массива Array1 не дублируемых элементов массива Array2
Array1Array2	операция пересечения массивов
	логическая операция принадлежности элемента E массиву M
Sort(Arrayf)	операция сортировки массива Array по значению поля f

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

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

3.2 Описание постановки задачи выявления дефектов сканирования и их устранение

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

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

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

Входная информация. Входной информацией является битовый растр отпечатка, полученный с помощью сканирования разрешением 600dpi. Расширение битового файла по умолчанию *.bmp. Формат bmp (от слов BitMaP - битовый массив) представляет из себя несжатое (в основном), что позволяет не вносить погрешностей, изображение. Формат bmp довольно легко читается и выводится в ОС Windows, в которой есть специальные функции API.

Входной растр представлен форматом BMP, который имеет структуру представленную на рисунке 3.3.

Рисунок 3.3 - Входной растр представленный форматом BMP

В начале стоит заголовок файла - BITMAPFILEHEADER.

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

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

На рисунке 3.4 показан разрыв полосы, при всем этом производится последующее условие (формула 3.1):

, (3.1)

где A= {x,y};

B= {x,y};

- эмпирическая величина.

На рисунке 3.5 показано слипание линий, при этом выполняется условие (формула 3.1) для рисунка 3.5.



Рисунок 3.4 - Разрыв линии

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

B - вероятная точка продолжения линии папиллярного узора;

C - искривление контура в вероятной точке продолжения;

D1, D2 - прилегающие области;

L1, L2 - вероятные соседние линии папиллярного узора.

Рисунок 3.5 - Слипание линий

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

B - вероятная точка продолжения линии папиллярного узора;

C - искривление контура в вероятной точке продолжения;

D1, D2 - прилегающие области;

L1, L2 - вероятные соседние впадины папиллярного узора.

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

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

если обнаружена область разрыва, то выполняется восстановление целостности линии;

если обнаружена область слипания, то выполняется разъединение линий.

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

R - Битовый растр

Map - список. Map = {x, y}i

R.GetPixelColor(x,y) - получить значение цвета пикселя с координатами {x,y} на растре R

R.FloodFill(x, y, color) - залить область с цветом R.GetPixelColor(x,y) в цвет color

R.width() - ширина растра в пикселях

R.height() - высота растра в пикселях

R.ChangeLine(Map[i]) - обход по контуру линии из точки Map[i]

Начало

Формировать из растра R список линий Map

i, : i[1, |Map|] R.ChangeLine(Map[i])

Если растр R был изменён, то перейти к п. 2

Конец



3.3 Описание алгоритма «Формирование списка линий»

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

Начало

x::=0, y::=0

Если R.GetPixelColor(x,y) != 0x000000, то перейти к п. 5

(x,y) Map; R.FloodFill(x,y, 0xFFFFFF)

y++;

если y < R.width(), то перейти к п. 3

x++; y::=0;

если x < R.height(), то перейти к п. 3

Конец

Описание алгоритма «ChangeLine». Алгоритм для поиска слипаний, обрывов и устранение их на растре.

dot0, dot1 -точки принадлежащие контуру линии

vec0, vec1 - локальные направления

GetVec(dot0, dot1) - направление из точки dot0 в dot1

alphaTest - предопределенная константа определяющая сильное искривление контура папиллярной линии

NextDotCW(dot0, step) - получение координат точки следующей через step точек

Условия разрыва и слипания описаны в пункте. 3.2.

Начало

dot0 ::= начальное значение

dot1 ::= NextDotCW(dot0,step);

vec0 ::= GetVec(dot0, dot1);

dot0 ::= dot1;

dot1 ::= NextDotCW(dot0, step);

vec1 ::= GetVec(dot0, dot1);

Если |vec1 - vec0| < alphaTest, то перейти к п. 11

Если найденная точка является слипанием, то разъединить линии

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

Если обход по контуру привел к начальной точке, то перейти к п.13

vec0 ::= vec1; перейти к п.5

Конец

3.4 Описание алгоритма «ReadLine»

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

Входная информация. Входной информацией является битовый растр после предобработки. Растр имеет глубину 1бит на пиксель и разрешение 600dpi. Формат bmp (от слов BitMaP - битовая карта, или, говоря по-русски, битовый массив) представляет из себя несжатое (в основном), что позволяет не вносить погрешностей, изображение. Формат bmp довольно легко читается и выводится в ОС Windows, в которой есть специальные функции API.

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

Рисунок 3.6 - Структура массива

где Xi, Yi - Координаты минюции на растре;

i - Ориентация минюции;

T - Тип (окончание либо раздвоение);

k - Количество минюций.

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

На рисунке 3.6 показано «окончание», при этом выполняется условие (формула 3.2).

(3.2)

гдеA= {x,y};

B= {x,y};

- эмпирическая величина.

На рисунке 3.7 показано «раздвоение», при этом выполняется условие (формула 3.2) для рисунка 3.7.



Рисунок 3.6 - Окончание

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

B - вероятная точка продолжения линии папиллярного узора;

C - искривление контура в вероятной точке продолжения;

D1, D2 - прилегающие области;

L1, L2 - вероятные соседние линии папиллярного узора.

Рисунок 3.7 - Раздвоение

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

B - вероятная точка продолжения линии папиллярного узора;

C - искривление контура в вероятной точке продолжения;

D1, D2 - прилегающие области;

L1, L2 - вероятные соседние впадины папиллярного узора.

Локальные особенности: разрыв и слипание описаны в пункте 3.2.

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

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

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

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

R - битовый растр

Map - список. Map = {x, y}i

R.GetPixelColor(x,y) - получить значение цвета пикселя с координатами {x,y} на растре R

R.FloodFill(x, y, color) - залить область с цветом R.GetPixelColor(x,y) в цвет color

R.width() - ширина растра в пикселях

R.height() - высота растра в пикселях

R.ReadLine(Map[i]) - обход по контуру линии из точки Map[i], получает список координат минюций

Начало

Формировать из растра R список линий Map

i, : i[1, |Map|] List ::= R.ReadLine(Map[i])

Вывод List

Конец

Описание алгоритма «ReadLine»

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

dot0, dot1 -точки принадлежащие контуру линии

vec0, vec1 - локальные направления

GetVec(dot0, dot1) - направление из точки dot0 в dot1

alphaTest - предопределенная константа

NextDotCW(dot0, step) - получение координат точки следующей через step точек

Return - возвращаемый список

Условия обрыва и слипания описаны в п.п. 2.2.4

Начало

dot0 ::= начальное значение

dot1 ::= NextDotCW(dot0, step);

vec0 ::= GetVec(dot0, dot1);

dot0 ::= dot1;

dot1 ::= NextDotCW(dot0, step);

vec1 ::= GetVec(dot0, dot1);

Если |vec1 - vec0| < alphaTest, то перейти к п. 11

type ::= vec1 < vec0;

alpha ::= предположительное направление продолжения линии;

{dot0, alpha, type} Return

Если обход по контуру привел к начальной точке, то перейти к п.13

vec0 ::= vec1; перейти к п.5

Конец

3.5 Описание постановки задачи сортировки списка абсолютных параметров, исключение ложных и ненадежных минюций

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

пара точек не может находиться ближе определенного расстояния;

пара точек имеющих одинаковый тип и направленные друг на друга не могут находиться ближе 3*d, где d - расстояние между центрами соседних гребней;

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

рядом с раздвоением обязательно должна проходить пара соседних впадин.

Входная информация. Входной информацией является выходная информация предшествующего шага.

Выходная информация. Выходной информацией является список минюций в абсолютных параметрах. Данное структурное представление на основе минюций достаточно для распознавания личности по отпечаткам пальцев. Такое представление гораздо меньше растрового по размеру, благодаря чему организуется удобное хранение и быстрая обработка. Каждый элемент массива содержит все необходимые параметры: координаты целого типа - 2х4 байта, угол направления 8 байт, тип точки 1 байт. При среднем количестве точек 50 получаем объем занимаемый одним обработанным отпечатком примерно 850 байт.

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

На рисунке 3.8 показан вид пореза либо складки кожи, при всем этом производится последующее условие (формула 3.3):

, (3.3)



гдеA= {x,y};

B= {x,y};

- эмпирическая величина.

Рисунок 3.8 - Порез

где D1, D2 - прилегающие области;

L1, L2 - вероятные соседние линии папиллярного узора.

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

Полученный список сортируется по условию (формула 3.4):

(3.4)

где:i, j- найденные точки;

x, y - координаты минюции на растре;

a- угол направления;

T- тип минюции (раздвоение или окончание);

1, 2, aMin, aMax - константы (устанавливаются экспериментально).

Алгоритм решения задачи.

Начало

i,j : ij выполнить Delete(Array,j), Delete(Array,i)

i,j : ij

выполнить Delete(Array,j), Delete(Array,i)

Конец

3.6 Описание подпрограмм

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

Синтаксис:

CPoint TFingPicture::NextDotCW(const CPoint dot, int &vec)

Входные данные для данной подпрограммы представлены:

CPoint dot - структура данных - точка {x,y} от которой нужно найти соседствующую точку;

int vec - направление предыдущего перехода при поиске, vec[0..7]. Служит для ускорения поиска;

COLORREF clMas[9] - массив цветов окрестных точек;

Выходные данные для данной подпрограммы представлены:

CPoint incXY[8] - координаты окрестных точек;

CPointnewDot - найденная точка, которая является смежной с точкой dot. Переход от точки dot к найденной смежной точке образует обход «по часовой стрелке».

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

Синтаксис:

CPoint TFingPicture::NextDotСCW(const CPoint dot, int &vec)

Входные данные для данной подпрограммы представлены:

CPoint dot - структура данных - точка {x,y} от которой нужно найти соседствующую точку;

int vec - направление предыдущего перехода при поиске, vec[0..7]. Служит для ускорения поиска;

COLORREF clMas[9] - массив цветов окрестных точек;

Выходные данные для данной подпрограммы представлены:

CPoint incXY[8] - координаты окрестных точек;

CPoint newDot - найденная точка, которая является смежной с точкой dot. Переход от точки dot к найденной смежной точке образует обход «против часовой стрелки»

Рисунок 3.9 - Схема подпрограммы «NextDotCW»



Рисунок 3.10 - Схема подпрограммы «NextDotСCW»

Подпрограмма LookPic. Подпрограмма LookPic предназначена для обработки загруженного изображения и получение из него списка папиллярных линий. Каждая линия определяется одной точкой {x,y}. Схема подпрограммы изображена на рисунке 3.11.

Синтаксис:

list<TMapElDot> TAnalysePicture::LookPic()

Входные данные для данной подпрограммы представлены:

TFingPicture *pic - указатель на битовый образ в памяти, который был загружен для обработки

Выходные данные для данной подпрограммы представлены:

list<TMapElDot>Map - список папиллярных линий на растре.

Используемые переменные:

Map - список обрабатываемых линий на папиллярном узоре, каждой линии соответствует точка {x,y}.

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

Pic.GetPixel(x,y)- возвращает цвет пикселя с координатами {x,y} на растре pic;

ClearLine(pic,x,y) - удаление области с цветом GetPixel(x,y) на растре pic.

Рисунок 3.11 - Схема подпрограммы «LookPic»

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

Синтаксис:

int TAnalysePicture::ChangeLine(list<TMapElDot>::iterator _dot, list<TMapElDot>&_map)

Входные данные для данной подпрограммы представлены:

TFingPicture *pic - указатель на битовый образ в памяти, который был загружен для обработки;

list<TMapElDot>::iterator _dot - указатель на текущую обрабатываемую линию;

list<TMapElDot>&_map - список обрабатываемых линий на растре.

Выходные данные для данной подпрограммы представлены:

intchangeN - произведенное количество исправлений на растре;

TFingPicture *pic - в результате обработки входной образ подвергается изменениям.

Используемые переменные:

Dot0, dot1 -точки принадлежащие контуру обрабатываемой линии. Начальное значение dot0 = _dot.

vec0, vec1 - локальные направления;

step - шаг получения последующей точки;

alphaTest - предопределенная константа, определяющая сильное искривление контура папиллярной линии.

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

GetVec(dot0, dot1)- направление из точки dot0 в dot1;

NextDotCW(dot0, step) - получение координат точки следующей через step точек.

Слипание и обрыв описаны в пункте 3.2.



Рисунок 3.12 - Схема подпрограммы «ChangeLine»

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

Синтаксис:

TAbsFing TAnalysePicture::ReadPic(list<TMapElDot>::iterator _dot)

Входные данные для данной подпрограммы представлены:

TFingPicture *pic - указатель на битовый образ в памяти, который был загружен для обработки;

list<TMapElDot>::iterator _dot - указатель на текущую обрабатываемую линию.

Выходные данные для данной подпрограммы представлены:

TAbsFing absfing - список параметров локальных особенностей, формат описан в п.п. 2.1.3.

Используемые переменные:

Dot0, dot1 - точки принадлежащие контуру обрабатываемой линии. Начальное значение dot0 = _dot;

vec0, vec1 - локальные направления;

step - шаг получения последующей точки;

alphaTest - предопределенная константа, определяющая сильное искривление контура папиллярной линии.

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

GetVec(dot0, dot1)- направление из точки dot0 в dot1;

NextDotCW(dot0, step) - получение координат точки следующей через step точек.

Раздвоение и окончание описаны в пункте 3.3.

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

Синтаксис:

int TAnalysePicture::DotsFilter(TAbsFing &_dots)

Входные данные для данной подпрограммы представлены:

TAbsFing &_dots - список точек найденный на растре, он содержит помимо нужных точек - минюций, лишние, непостоянные точки, которые не подходят для объектного описания папиллярного узора.

Выходные данные для данной подпрограммы представлены:

TAbsFing _dots - список параметров минюций, формат описан в п.п. 2.1.3.

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

Порез(dot) - относится ли данная точка к точкам образованным порезами и инородными телами (см. п.п. 2.4.4);

Filter(dot1, dot2) - условие фильтрования (см. п.п. 2.4.4).



Рисунок 3.13 - Схема подпрограммы «ReadPic»

Рисунок 3.14 - Схема подпрограммы «DotsFilter»



Подпрограмма AnalysePicture. Подпрограмма AnalysePicture предназначена для обработки загруженного изображения и получение из него объектного образа для последующего хранения и сравнения. Схема подпрограммы изображена на рисунке 3.15.

...