Тема: «Автоматизированная система контроля доступа на основании распознавания отпечатков пальцев».

Введение. Актуальность. Новизна
1. Характеристика объекта
1.1 Описание объекта
1.2 Способы получения изображения
1.3 Область применения
2. Обзор методов
2.1 Задачи обработки изображений
2.2 Алгоритм методов распознавания
2.3 Анализ методов распознавания
2.3.1 Классы алгоритмов сравнения отпечатков пальцев
2.3.2 Классификация отпечатков пальцев
2.3.3 Подходы для автоматической классификации отпечатков пальцев
2.3.4 Классификаторы
2.3.5 Многоканальный подход к распознаванию отпечатков пальцев
2.3.6 Комбинированные методы распознавания отпечатков
Заключение
Список литературы

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

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

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

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

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

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

Основные определения, используемые в работе (Рис. 1.1):

• Гребень(Ridge) - линия отпечатка пальца возвышается, образуя гребень;
• Бороздка (Valley) - желобок между гребнями;
• Конечная точка (Ending point) - точка, где заканчивается линия гребня;
• Точка ветвления (Bifurcation) - точка расхождения линий гребня;
• Центр (Core) - точка наибольшей кривизны гребня;
• Дельта (Delta) - зона, где гребень разветвляется на три линии, а затем они сходятся в одной точке.

Рисунок 1.1 Изображение отпечатка пальца с нанесением особых точек.

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

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

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

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

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

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

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

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

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

Другая проблема: идентификация по отпечатку пальцев имеет очень низкий уровень FAR ("пропустить чужого", т.е. принимается решение "свой", хотя, на самом деле, субъект отсутствует в списке зарегистрированных пользователей).

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

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

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

Упрощенный алгоритм методов распознавания приведен на рис.2.2:

Рисунок 2.2. Алгоритм метода распознавания.

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

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

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

2. Фиксирование данных. Измерение и фиксация базовой биометрической информации, относящейся к конкретному образу.

3. Обработка данных. Перевод зафиксированных данных в цифровую форму с созданием эквивалента отпечатку пальца.

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

5. Сохранение подтвержденных биометрических данных.

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

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

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

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

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

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

На самом простом техническом уровне, например, если разрешение полученного со сканера изображения составляет 300-500 dpi, на изображении поверхности пальца можно выделить достаточно большое количество мелких деталей (minutiae), по которым можно их классифицировать, но, как правило, в автоматизированных системах используют всего два типа деталей узора (особых точек):

• конечные точки - точки, в которых "отчетливо" заканчиваются папиллярные линии;
• точки ветвления - определяются как точки, в которых папиллярные линии раздваиваются.

Если есть возможность получить изображение поверхности пальца с разрешением около 1000 dpi, на нем можно обнаружить детали внутреннего строения самих папиллярных линий, в частности, поры потовых желез (рисунок 2.3, пустыми кружками отмечены поры, черными кружками отмечены конечные точки и точки ветвления) и соответственно использовать уже их расположение в целях идентификации. Однако этот метод мало распространен из-за сложности получения в не лабораторных условиях изображений такого качества.

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

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

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

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

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

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

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

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

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

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

Рисунок 2.4 Разбиение папиллярного узора на ячейки

Расположение линий в каждой ячейке описывается параметрами некоторой синусоидальной волны (рисунок 2.5), то есть, задается начальный сдвиг фазы ( ), длина волны ( ) и направление ее распространения ( ).

Рисунок 2.5. Волновое представление линий в ячейке.

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

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

Классификация отпечатка пальца - это метод, используемый, чтобы определить отпечаток пальца в один из нескольких уже принятых типов, которые могут обеспечить механизм индексации. Классификация отпечатка пальца может быть рассмотрена как грубое соответствие отпечатков пальца. Вводимый отпечаток пальца сначала может быть отнесен на грубом уровне к одному из указанных типов и затем, на более точном уровне, это - сравнение с подмножеством в базе данных, соответствующей этому типу отпечатка пальца. Мы классифицируем отпечатки пальца в пять классов: завитушка (W), правая петля (R), левая петля (L), дуга (A), и полусфера(T) (рис. 2.6).

Рисунок 2.6 Основные классы отпечатков пальцев. (a)-двойная петля-W, (b) Завитушка (пальцевый узор) - W, (c) правая петля - R, (d) левая петля - L, (e) дуга - A, и (f) полусфера - T.

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

1) на основе модели.

Метод классификации отпечатка пальца на основе модели использует местоположения особых точек (ядро и разветвление), чтобы классифицировать отпечаток пальца в пять вышеупомянутых классов. Подход на основе модели использует знания людей-экспертов, применяя правила для каждой категории вручную построенной модели и поэтому, не требует обучения. Использование этих подходов показало точность 85% и 87.5% относительно базы данных NIST-4.

2) на основе структуры.

Подход на основе структуры использует предполагаемую область ориентации в изображении отпечатка пальца, чтобы классифицировать отпечаток пальца в один из этих пяти классов. Получена точность 90.2% с 10-процентным отклонением относительно базы данных NIST-4. Нейронная сеть обучалась на изображениях от 2 000 пальцев (одно изображение на палец) и затем была проверена на независимом наборе 2 000 изображений, взятых от тех же самых пальцев. Ошибка оказалась удивительной. Более поздняя версия этого алгоритма была проверена на базе данных NIST-14, которая является естественно распределенной базой данных, обеспечивая лучшее выполнение алгоритма. Однако, это улучшение выполнения предполагалось, так как база данных NIST-14 содержит маленький процент отпечатков пальцев типа дуга, которые наиболее трудны для классификаторов отпечатка пальца, а нейронная сеть, используемая в алгоритме, неявно использует эту информацию. Подобный подход на основе структуры, который использует скрытые модели Маркова для классификации, зависит от надежности оценки местоположений выступов, которая трудна в шумных изображениях. В другом подходе на основе структуры используются кривые B-сплайна, чтобы классифицировать отпечатки пальца.

3) на основе частоты.

Подходы на основе частоты используют спектр частоты отпечатков пальца для классификации. Здесь используются ряды Фурье.

4) синтаксический подход.

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

5) гибридные подходы.

Гибридные подходы комбинируют два или больше подхода для классификации. Эти подходы подают надежды, но не были проверены на больших базах данных. Например, отчет Чонг и др. заканчивается на 89 отпечатках пальца, Фитз и Грин - на 40 отпечатках пальцев, и Кавагое и Тоджо - на 94 отпечатках пальцев.

Классификатор - алгоритм отнесения объекта к какому-либо классу на основании его признаков. Рассмотрим несколько наиболее известных и используемых классификаторов: классификатор К-ближайший, классификатор нейронная сеть, двухэтапный классификатор, классификатор "отклонение выбора", классификатор скрытой модели Маркова, классификатор дерева решения.

1. Классификатор K-ближайший.

Классификатор К-ближайший приводит к точности 85.4% для задачи классификации пятого класса, когда рассматриваются 10 ближайших соседей (K=10). Точность классификации не всегда увеличивается с увеличением K; так существует оптимальное значение K для конечных учебных задач классификации размера модели. Для задачи классификации четвертого класса (где классы A и T были объединены в один класс), достигнута точность 91.5%. Смешанная матрица для классификатора K- ближайший показана в таблице 2.1.

Истинный класс	Заданный класс
	W	R	L	A	T
W	320	38	31	6	0
R	1	368	2	10	21
L	0	1	359	13	8
A	1	3	7	422	20
T	0	15	16	95	208

Таблица 2.1 Смешанная матрица для классификатора K-ближайших соседа (К=10)

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

2. Классификатор Нейронная сеть

В данном случае обучалась многослойная передовая нейронная сеть, используя быстрое распространение, обучающее алгоритм. Нейронная сеть имеет один скрытый слой с 20 нейронами, 192 нейронами входа, и пятью нейронами выхода, соответствующими этим пяти классам. Получалась точность 86.4% для задачи классификации пятого класса. Для задачи классификации четвертого класса, достигнута точность 92.1%. Смешанная матрица для классификатора нейронная сеть приведена в таблице 2.2.

Истинный класс	Заданный класс
	W	R	L	A	T
W	352	29	10	2	2
R	6	374	1	9	17
L	10	2	353	10	7
A	0	6	8	384	48
T	1	16	19	64	235

Таблица 2.2 Смешанная матрица для классификатора нейронной сети.

3. Двухэтапный Классификатор

Здесь идея состоит в том, чтобы выполнить "простую" задачу классификации, используя классификатор K-NN и затем - группу классификаторов нейронной сети с двумя классами, чтобы обращаться с более тонкими выделениями. Первая стадия использует классификатор K-ближайший (K = 10), чтобы привести к двум самым вероятным классам. Было замечено, что 85.4% времени, класс с максимальной частотой среди К-ближайших - правильный класс, а 12.6% времени, класс со второй наивысшей частотой - правильный класс. Другими словами, классификатор K-ближайший приводит к лучшим двум классам с точностью до 98%. Этот результат может использоваться, чтобы точно классифицировать отпечатки пальца в два из этих пяти классов. Каждый отпечаток пальца будет иметь вхождение в два из пяти разделения базы данных, и соответственно обязан будет входить только в соответствующие два разделения базы данных. Вторая стадия использует 10 различных нейронных сетей для 10 различных попарных классификаций. Эти нейронные сети имеют 192 нейрона входа, 20-40 скрытых нейронов в одном скрытом слое, и 2 нейрона выхода. Каждая нейронная сеть обучается, используя образцы только от двух соответствующих классов в учебном наборе. Например, нейронная сеть, которая различает R и W, обучается, используя только помеченные образцы R и W в учебном наборе.

Этот двухэтапный классификатор обеспечивает точность 90% для задачи классификации пятого класса, а для задачи классификации четвертого класса достигнута точность 94.8%. Смешанная матрица для двухэтапного классификатора приведена в таблице 2.3.

Истинный класс	Заданный класс
	W	R	L	A	T
W	366	16	8	4	1
R	3	372	1	8	17
L	6	0	364	6	7
A	2	1	3	405	39
T	0	6	14	55	261

Таблица 2.3 Смешанная матрица для двухэтапного классификатора.

Хотя этот классификатор является устойчивым к шуму и в состоянии правильно классифицировать большинство отпечатков пальца низкого качества в базе данных NIST-4, оно не применимо на некоторых очень плохих, некачественных изображениях отпечатка пальца, где никакая информация выступа не присутствует в центральной части отпечатка пальца. В отпечатках пальца низкого качества, очень трудно правильно обнаружить точку центра. Классификатор также не в состоянии правильно классифицировать изображения петли близнеца, которые помечены как пальцевой узор в базе данных NIST-4. Для этих изображений, алгоритм местоположения центра улучшает верхнее ядро и при рассмотрении определяет, что центр изображения похож на петлю в нужной области, что приводит к ошибочной классификации W как L или R. Приблизительно 3% ошибочно классифицируются из-за малого различия между петлей и типами дуги. Ошибочная классификация A-T составляет приблизительно 5% ошибок.

4. Классификатор отклонение выбора

Точность классификации может быть далее увеличена, применяя выбор отклонения. Использовалось (K, K') - классификатор К-ближайших для отклонения и предложенного двухэтапного классификатора для классификации. Если число обученных образцов от класса среди K-ближайших тестовой модели меньше чем K' (K'‹K), мы отклоняем тестовую модель и не пытаемся классифицировать ее. Большинство отклоненных изображений, которые используют эту схему, плохого качества. Другие отклоненные изображения - изображения, которые "кажется" принадлежат различным классам. Отклоняя 19.5% изображений для задач пятого класса, точность классификации может быть увеличена до 93.5%, а для задач классификации четвертого класса, точность может быть увеличена до 96.6% (табл 2.4).

Классификатор	(10,0)-NN	(10,5)-NN	(10,6)-NN	(10,7)-NN
Норма отклонения	1,8 %	8,5 %	19,5 %	32,5 %
Ошибка 5 класса	10 %	8,8 %	6,5 %	1 %
Ошибка 4 класса	5,2 %	4,5 %	3,4 %	2,2 %

Таблица 2.4 Соотношение отклонения ошибки

5. Классификатор скрытой модели Маркова

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

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

Размеры каждого признака называют структурой и структурами, R_ik для i-ой принятой за основу линии все вместе называют рядом, R_i, расположение которого сохранено. Для каждой ориентации ф принятой за основу линии, определено представление R_ф={R_i,V_i} отпечатка. В этом исследовании, использовались только горизонтальные и вертикальные линии, предоставляя особенности R_h и R_v, соответственно.

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

Для классификации, модель M_c построена для каждого класса, c, и максимальный класс вероятности выбран после вычисления вероятности данных R, образующих модель: argmax_cP(R| M_c).

Вероятности выделения структуры смоделированы с объединением диагональной ковариации, многомерных Гауссовских распределений. Таким образом, для любой структуры R_ik, возможно вычислить вероятность P(R_ik|S_ijk)) этого происходящий в любом состоянии S_ijk. С этими вероятностями, для любой модели ряда, вероятность любого ряда может быть приближена к максимальной вероятности любой последовательности состояния, выравнивающей признаки и состояния, вычисленные как результат вероятностей структуры и вероятностей перехода для последовательности состояния:

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

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

6. Классификатор дерево решения

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

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

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

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

Рисунок 2.7 Диаграмма алгоритма многоканального подхода

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

Главные шаги этого алгоритма извлечения признаков следующие:

1) Найти регистрационную точку (точку центра) и определить пространственное составление мозаики места изображения вокруг регистрационной точки (представленное совокупностью секторов).

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

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

Пусть I(x, y) обозначают серый уровень в пикселе (x, y) в М x N изображении отпечатка пальца и пусть (x_c, y_c) обозначают точку центра. Пространственное составление мозаики области изображения, которое состоит из значимой области, определено совокупностью секторов S_i, где i-сектор S_i вычислен в терминах параметров (r, ) следующим образом:

b - ширина каждой полосы, и k - число секторов, которые рассматривают в каждой полосе. Используются шесть концентрических полос вокруг пункта центра. Каждая полоса с 20 пикселами шириной (b = 20), и сегментированный в восемь секторов (k = 8) (рис. 2.8). Самая внутренняя полоса не используется для извлечения признаков, потому что сектора в области около центра содержат очень немного пикселов. Таким образом, в общей сложности 8 x 6 = 48 секторов ( с S₀ до S₄₇) определены.

Рисунок 2.8 Отпечаток пальца с точкой центра (х), ядром (o) и отмеченными 48 секторами.

Главные шаги алгоритма классификации следующие (рис. 2.7):

1) Определить местонахождение регистрационных точек во входном изображении и определить пространственное составление мозаики области вокруг регистрационной точки (сектора).

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

а) Оценить область ориентации О, используя алгоритм оценки ориентации наименьшего квадрата. Область ориентации О определена как N x N изображение, где O(i,j) представляет местную ориентацию выступов в пикселе (i,j). Изображение разделено на ряд wxw неналожившихся окон, и единственная местная ориентация определена для каждого окна.

б) Сгладить область ориентации в местном соседстве. Пусть приглаженной ориентации области будет представлена как O'.

в) Иницализировать A, изображение метки как правило указывает основную точку.

г) Для каждого пиксела (i, j) в O', вычисляют индекс Пуанкарэ (Poincare) и назначают соответствующие пикселы в А значение одного из индекса Пуанкарэ - (1/2). Индекс Пуанкарэ в пикселе (i, j) приложенный к пальцевидной кривой, которая состоит из последовательности пикселов, которые на расстоянии одного пиксела от соответствующей кривой, вычислен следующим образом:

где (·) и (·) - координаты х и y закрытой пальцевидной кривой с пикселями.

д) Найти связанные компоненты в A. Если область связанного компонента больше семи, ядро обнаружено в средней точке связанного компонента. Если область связанного компонента больше 20-ти, два ядра обнаружены в средней точке связанного компонента.

е) Если обнаружено больше, чем два ядра, возвратитесь к Шагу б).

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

з) Если никакая основная точка не обнаружена, вычислите матрицу ковариации векторной области в местном соседстве (q x q) каждой точки в области ориентации. Определите изображение признаков I с наибольшим собственным значением матрицы ковариации для каждого элемента в изображении ориентации. Ядро обнаружено в средней точке наибольшего связанного компонента в пороговом изображении F и центр назначен координатами ядра.

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

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

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

Ровный симметрический фильтр Габора имеет следующую общую форму в пространственной области

где f - частота синусоидальной волны плоскости по направлению от оси X, и и определяют Гауссовскую огибающую по осям Х и Y, соответственно, которые определяют полосу пропускания фильтра Габора.

В нашем алгоритме, частота фильтра f - это средняя частота выступов (1/K), где K - расстояние между выступами. Среднее расстояние между выступами - приблизительно 10 пикселов в изображении отпечатка пальца 500 точек на дюйм.

Опытным путем определены значения и , и оба берутся = 4.0.

Изображение отпечатка пальца разделено на четыре составляющих изображения, соответствующие четырем различным значениям (0⁰, 45⁰,90⁰, и 135⁰) относительно оси X (рис. 2.9). Изображение отпечатка пальца свернуто с каждым из четырех фильтров Габора, чтобы произвести четыре составляющих изображения.

Рисунок 2.9 Применение фильтров Габора. Размерность 33х33, f=0.1, =4.0, =4.0, (a) - ориентация 0⁰. (b) - ориентация 45⁰. (c) - ориентация 90⁰. (d) - ориентация 135⁰.

Перед разложением изображения отпечатка пальца, мы нормализуем необходимую область в каждом секторе отдельно к постоянному среднему и разнице. Нормализация сделана, чтобы удалить эффекты шума датчика и различий давления пальца. Пусть I(x, y) обозначают серое значение в пикселе (x, y), M_i и V_i, предполагаемом среднем и разнице сектора S_i, соответственно, и N_i(x, y), нормализованное значение серого уровня в пикселе (x, y). Для всех пикселов в секторе S_i, нормализованное изображение определено как:

где M₀ и V₀ - требуемое среднее и значение разницы, соответственно.

Нормализация - пиксельная операция, которая не изменяет четкость структур бороздочек и выступов. Для наших экспериментов, мы устанавливаем оба значения и M₀, и V₀ равными 100. Нормализованные, фильтрованные, и восстановленные изображения для отпечатка пальца, показаны на рис. 2.10.

Рисунок 2.10. Нормализованное, фильтрованное, и восстановленное изображения отпечатка пальца. (a) - нормализованное изображение, (b), (c),(d),(e) - фильтрованное (0⁰, 45⁰, 90⁰, 135⁰), (f) - восстановленное изображение.

3) Ввести вектор признаков в классификатор;

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

Пусть (x, y) будет составляющим изображением, соответствующим для сектора S_i. Для i (i = 0,1...47 и Є [0⁰, 45⁰, 90⁰, 135⁰]), стандартное отклонение , определено как:

где K_i - число пикселов в S_i, и - средние значения пиксела в (x, y). 192-мерные векторы признаков, коды пальцев, типичных изображений отпечатка пальца различных классов показаны как изображения серого уровня с четырьмя дисками, каждый диск, соответствующий одному фильтрованному изображению (рис. 2.11). Серый уровень в каждом секторе диска представляет значение признаков для этого сектора в фильтрованном изображении выхода. Можно заметить, что визуально это представление, кажется, очень хорошо отличает пять классов отпечатка пальца.

Рисунок 2.11. 192-мерные векторы признаков (коды пальцев). Тестовая модель - правая петля. Каждый диск соответствует одному специфическому фильтру с 48 признаками (показанные как серые значения). Каждый диск (8x6=48 секторов) для в общей сложности 192 (48 x 4) признаков. (a) Тестовая модель, (b) завитушка, (c) правая петля, (d) левая петля, (e) арка, (f) полусфера.

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

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

Схема 2.1 Алгоритм идентификации отпечатка пальца

(1) - используемые классификаторы:

• Классификатор К-ближайшего соседа;
• Классификатор Нейронная сеть;
• Двухэтапный классификатор;
• Классификатор Отклонениевыбора;
• Классификатор Скрытой моделиМаркова;
• Классификатор Дерево решения.

(2) - схема метода классификации отпечатков в подклассах.

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

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

[1] oтпечатки пальцев: ключ к будущему http://www.fond-ai.ru/art1/art446.html
[2] виталий задорожный часть 1 http://www.bre.ru/security/20994.html
[3] виталий задорожный часть 2 http://www.bre.ru/security/21052.html
[4] Считыватель отпечатков пальцев FingerChip корпорации ATMEL www.atmel.ru/Articles/Atmel31.htm
[5] A. Jain and S. Pankanti, "Automated Fingerprint Identification and Imaging Systems", Advances in Fingerprint Technology, http://poseidon.csd.auth.gr/papers/
PUBLISHED/CONFERENCE/pdf/kotropoulos2002b.pdf
[6] The FBI Fingerprint Image Compression Standard http://www.c3.lanl.gov/~brislawn/FBI/FBI.html
[7] CONTOURLET BASED FINGER PRINT MATCHING Atif Bin Mansoor, Awais Mansoorand Shoab A Khan http://rp.iszf.irk.ru/hawk/URSI2005/pdf/CP5.1(01180).pdf
[8] Иерархия биометрических стандартов Виталий Задорожный http://www.pcweek.ru/?ID=310118
[9] Djamel Bouchaffra and Venu Govindaraju and Sargur N. Srihari. Postprocessing of Recognized Strings Using Nonstationary Markovian Models. // IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 21 no. 10, pp. 990-999, 1997.
[10] Peter F. Brown and Vincent J. Della Pietra and Peter V. deSouza and Jennifer C. Lai and Robert L. Mercer. Class-Based n-gram Models of Natural Language. // Computational Linguistics, vol. 18, no. 4, pp. 467-479, 1992.
[11] Anil K. Jain and Robert P. W. Duin and Jianchang Mao. Statistical Pattern Recognition: A Review. // IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 22, no. 1, pp. 4-37, 2002.
[12] http://www.kstudio.ru/odp/index.php?c=/Science/Science_in_Society/ Forensic_Science/Fingerprints/

- подняться на начало страницы -