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

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

Санкт-Петербургский Национальный Исследовательский Университет

Информационных Технологий Механики и Оптики

Реферат

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

Санкт-Петербург - 2014

ВВЕДЕНИЕ

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

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

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

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

Решаемые задачи:

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

анализ существующих методов поиска соответствия в найденном классификатором классе;

программная реализация найденных методов и их комбинаций;

выявление на основе тестовой выборки наиболее эффективных методов или их комбинаций;

достижение конечной цели работы.

Новизна: повышение быстродействия поиска в системе при соблюдении оптимальной точности и надежности системы за счет комбинации различных классификаторов и выявления наиболее точных методов для осуществления быстрого и корректного поиска в определенном классификатором классе. Быстродействие планируется достичь за счет правильной сегментации системной базы данных отпечатков пальцев в соответствии с натуральным распределением классов (0.279, 0.317, 0.338, 0.037, и 0.029 для классов завиток, правая петля, левая петля, дуга, и полусфера, соответственно), а также возможно за счет объединения нескольких классов в один. В частности показатели быстродействия и точности системы значительно улучшаются при объединении классов дуга и полусфера в один класс. Точность классификации также планируется повысить за счет реализации эффективного метода обнаружения позиции центральной точки и внедрения в систему модуля улучшения изображений отпечатков пальцев перед выполнением этапа извлечения особых точек.

1. ОПИСАНИЕ ОБЪЕКТА КОМПЬЮТЕРИЗАЦИИ

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

Глобальные признаки - те, которые можно увидеть невооружённым глазом:

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

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

Впадинка (бороздка) - желобок между выступами;

Центр (ядро) - пункт, локализованный в середине отпечатка или некоторой выделенной области; точка наибольшей кривизны выступа;

Дельта - зона, где выступ разветвляется на три линии, а затем они сходятся в одной точке;

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

В традиционной дактилоскопии папиллярные узоры пальцев рук делятся на три основных класса: дуговые (около 5% всех отпечатков), петлевые (65%) и завитковые (30%); для каждого класса проводится более детальная классификация на подклассы. В рамках данной работы классификация будет произведена на пять классов: завиток (W), правая петля (R), левая петля (L), дуга (A), и полусфера (T).

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

Рисунок 1.1 - Основные классы отпечатков пальцев с учетом натурального распределения. a) Левая петля, b) Правая петля, c) Завиток, d) Дуга, e) Полусфера.

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

На изображении отпечатка пальца выделяют следующие детали (рисунок 1.2):

Конечные точки (окончания выступов) - точки, в которых «отчетливо» заканчиваются выступы;

Точки ветвления - точки, в которых происходит расхождение линий выступа.

Рисунок 1.2 - Примеры деталей.

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

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

2. ЛОКАЛЬНЫЙ ОБЗОР СИСТЕМ, ОСУЩЕСТВЛЯЮЩИХ РАСПОЗНАВАНИЕ ПО ОТПЕЧАТКАМ ПАЛЬЦЕВ

биометрический отпечаток палец распознавание

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

3. ГЛОБАЛЬНЫЙ ОБЗОР СИСТЕМ, ОСУЩЕСТВЛЯЮЩИХ РАСПОЗНАВАНИЕ ПО ОТПЕЧАТКАМ ПАЛЬЦЕВ

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

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

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

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

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

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

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

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

3.2 Обзор классификаторов изображений отпечатков пальцев

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

1. Классификатор «K»-ближайших соседей. Решающее правило «К» ближайших соседей заключается в том, что вначале находятся «К» ближайших соседей для тестового образца в пространстве признаков. После этого тестовый образец относится к классу, который наиболее часто представлен среди «К» ближайших соседей. Два верхних класса, которые были найдены с помощью классификатора «К» ближайших соседей, должны соответствовать классам, которые имеют самое высокое и второе по величине количество среди «К» ближайших соседей. Обычно рассматриваются 10 ближайших соседей (K=10). Точность классификации не всегда увеличивается с увеличением K; здесь возникает проблема классификации, связанная с определением оптимальной величины К для объема проверочной выборки конечного размера.

2. Классификатор Нейронная сеть. В данном случае обучали многослойную нейронную сеть с прямым распространением, используя в качестве обучающего алгоритма алгоритм быстрого распространения. Нейронная сеть имеет один скрытый слой из 20 нейронов, 192 входных нейрона, и 5 выходных нейронов, которые соответствуют пяти классам.

3. Двухэтапный Классификатор. Для упрощения задачи классификации мы декомпозируем 5-ти классовую задачу на набор из 10 2-х классовых задач. Целью является выполнение задачи простой классификации, используя классификатор «К» - ближайших соседей и затем используется набор двух-классовых классификаторов нейронных сетей для манипуляции с едва заметными различиями.

Первый этап использует классификатор «К» - ближайших соседей (К = 10), чтобы выбрать два наиболее вероятных класса для текущего входного образца. Мы получили путем наблюдения, что в 85.4 % случаев, класс с максимальной частотой попадания в группу «К» ближайших соседей это правильный класс (класс прошел классификацию) и в 12.6 % случаев класс со второй по величине частотой это также правильный класс. Другими словами, классификатор «К» - ближайших соседей приводит к нахождению двух классов с наибольшей частотой попадания в группу с точностью 98 %. Этот результат используется для точного отнесения отпечатков пальцев к двум из пяти классов. Каждый отпечаток будет иметь вхождение в два из пяти классов БД и поиск соответствия в БД должен быть произведен только в соответствующих двух классах.

Второй этап использует 10 (C₂⁵) различных нейронных сетей для 10 различных парных классификаций. Эти нейронные сети имеют 192 входных нейрона, 20-40 скрытых нейронов находятся в одном скрытом слое, и 2 выходных нейрона. Каждая нейронная сеть обучена использовать образцы только из двух соответствующих классов в обучающей выборке. Например, нейронная сеть, которая находит различие между правой петлей и завитком обучена использовать только образцы, помеченные как правая петля и завиток в обучающей выборке. Схема двухэтапного классификатора представлена на рисунке 3.1.

Рисунок 3.1 - Схема двухэтапного классификатора.

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

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

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

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

Рассмотрим этапы сравнения двух отпечатков по локальным признакам:

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

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

Бинаризация изображения отпечатка. Приведение к чёрно-белому изображению (1 bit) пороговой обработкой;

Утончение линий изображения отпечатка. Утончение производится до тех пор, пока линии не будут шириной 1 пиксель;

Извлечение деталей. Изображение разбивается на блоки 9х9 пикселей. После этого подсчитывается число чёрных (ненулевых) пикселей, находящихся вокруг центра. Пиксель в центре считается деталью, если он сам ненулевой, и соседних ненулевых пикселей: один (деталь - «окончание») или два (деталь - «раздвоение»). Процесс извлечения деталей представлен на рисунке 3.2.

Рисунок 3.2 - Процесс извлечения деталей. Рисунок анимирован. Для запуска обновите страницу.

Координаты обнаруженных деталей и их углы ориентации записываются в вектор:

W(p)=[(x1, y1, 1), (x2, y2, 2)...(xp, yp, p)],

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

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

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

- Поиск пар соответствующих деталей. При поиске для каждой детали нужно перебрать до 30 значений поворота (от -15 градусов до +15), 500 значений сдвига (от -250 пикселей до +250 пикселей - хотя, конечно, границы выбирают и поменьше) и 10 значений масштаба (от 0,5 до 1,5 с шагом 0,1). Итого до 150 000 шагов для каждой из 70 возможных деталей. На практике, все возможные варианты не перебираются - после подбора нужных значений для одной детали их же пытаются подставить и к другим деталям, иначе было бы возможно сопоставить практически любые отпечатки друг другу;

- Оценка соответствия отпечатков. Оценка соответствия отпечатков выполняется по формуле K=(D*D*100%)/(p*q), где D - количество совпавших деталей, p - количество деталей эталона, q - количество деталей идентифицируемого отпечатка). В случае если результат превышает 65%, отпечатки считаются идентичными (порог может быть понижен выставлением другого уровня бдительности).

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

Рисунок 3.3 - Пример сопоставления деталей между введенным и шаблонным изображениями отпечатков пальцев

Если выполнялась аутентификация, то на этом всё и заканчивается. Для идентификации необходимо повторить этот процесс для всех отпечатков, находящихся в базе данных. Затем выбирается пользователь, у которого наибольший уровень соответствия (разумеется, его результат должен быть выше порога 65%).

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

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

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

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

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

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

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

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

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

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

ЗАКЛЮЧЕНИЕ

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

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

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

ЛИТЕРАТУРА

Задорожный В., "Идентификация по отпечаткам пальцев", Часть 1, 2004;

Задорожный В., "Идентификация по отпечаткам пальцев", Часть 2, 2007;

Давлетханов М., "Способы идентификации по отпечаткам пальцев", 2004;

Вакуленко А., Юхин А., "Биометрические методы идентификации личности: обоснованный выбор и внедрение", 2007;

Размещено на Allbest.ru