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

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

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

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

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

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

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

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

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

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

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

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

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

Задачей распознавания изображений отпечатков пальцев занималась магистр ДонНТУ Евстюничева А. В. Тема магистерской работы: «Автоматизированная система контроля доступа на основании распознавания отпечатков пальцев». В ходе выполнения магистерской работы были созданы проверочная и тестовая выборки отпечатков пальцев, частично реализован многоканальный подход для классификации отпечатков пальцев. В частности был получен вектор признаков - Код пальца и на его основании была осуществлена классификация методом Эвклидова расстояния. Однако вектор признаков был не совсем корректно генерирован в связи с неточной работой алгоритма определения месторасположения центральной точки. Тем ни менее была создана прекрасная база – теоретическая и практическая – для дальнейших исследований и продолжения работы в данном направлении.

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

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

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

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

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

2) На основе структуры. Подход на основе структуры использует оценку ориентационного поля на изображении отпечатка пальца для того, чтобы отнести отпечаток к одному из пяти классов. Нейронная сеть, распознающая отпечатки пальцев, обучалась на изображениях с 2000 пальцев (одно изображение с пальца) и тестировалась на независимом наборе, состоящем из 2000 изображений, снятых с тех же пальцев. Более поздняя версия этого алгоритма (G.T. Candela, P.J. Grother, C.I. Watson, RA. Wilkinson, and C.L. Wilson) была тестирована на базе данных NIST-14, которая является естественно распределенной базой данных, обеспечивая лучшее выполнение алгоритма. Однако должно предполагаться совершенствование этого представления, так как база данных NIST-14 содержит маленький процент отпечатков пальцев типа дуга, которые поддаются классификации наиболее сложно, а нейронная сеть, используемая в алгоритме, неявно использует эту информацию для получения выгоды. Подобный подход на основе структуры, который использует скрытые модели Маркова для классификации (A. Senior), полагается на надежность оценки местоположений выступов, что является сложным из-за зашумленности изображения. В другом подходе на основе структуры используются кривые B-сплайна (базисные полиномиальные кривые), чтобы классифицировать отпечатки пальца (M.M.S. Chong, T.H. Ngee, L. Jun, and R.K.L. Gay).

3) На основе частоты. Подходы на основе частоты используют спектр частот отпечатков пальца для классификации. Здесь используются ряды Фурье (A.P. Fitz and R.J. Green).

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

5) Гибридные подходы. Гибридные подходы комбинируют два или более видов подходов для классификации (B.G. Sherlock and D.M. Monro, M. Kawagoe and A. Tojo). Эти подходы подают надежды, но не были проверены на больших базах данных. Например, отчет M. M. S. Chong и др. заканчивается на 89 отпечатках пальца, Fitz и Green - на 40 отпечатках пальцев, и M. Kawagoe и A. Tojo - на 94 отпечатках пальцев. Наиболее перспективным является двухэтапный классификатор, который позволил бы сначала отнести отпечаток пальца к одному из подклассов, а после уже в этом подклассе производить сравнение. Среди гибридных подходов особое место занимает многоканальный подход распознавания изображений отпечатков пальцев [7].

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

Рассмотрим несколько наиболее известных и используемых классификаторов: классификатор «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 % ошибок.

4. Классификатор скрытой модели Маркова. [9]

5. Классификатор дерево решений. [9]

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

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

1. Корреляционное сравнение. [1],[2],[3],[10]

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

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

Рисунок 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, дает низкие результаты. Также следует учитывать, что люди, не имеющие совсем, или имеющие небольшое количество ключевых точек (особое состояние кожного покрова) не могут пользоваться данной системой. Количество ключевых точек может быть ограничивающим фактором для безопасности алгоритма. Кроме того, возможны сбои в системе из-за ложных ключевых точек (участок, содержащий ошибку, возникшую из-за низкого качества регистрации, воспроизведения изображения или нечеткого отпечатка полос).

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

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

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

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

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

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

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

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

ЗАКЛЮЧЕНИЕ

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

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

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

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

Рисунок 4 - Схема планируемых этапов магиастерской работы.

Дальнейшие исследования по магистерской работе будут заключаться в программной реализации данной схемы. При этом возможны корректировки в выбранном методе определения регистрационной точки, классификаторе и методе для поиска соответствия в выявленном классе. Это связано с тем, что магистерская работа находится на стадии разработки, поиск материалов по данным методам продолжается и возможно будут найдены более надежные и быстродействующие методы, что будет доказано экспериментально на основе тестовой выборки. Также учитывая современные тенденции, планируется создать систему пригодную одновременно как для идентификации [5],[6], так и для верификации [5],[6]. Окончательный вариант магистерской работы будет завершен в декабре 2008 г.

ЛИТЕРАТУРА

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

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

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

[4] Кухарев Г. А., материалы из монографии "Биометрические системы"/ СПб.: Политехника, 2001, 240 с.;

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

[6] Зиятдинов А. И., "Принципы построения систем биометрической аутентификации"/ МФТИ, 2005, 8 с.;

[7] A.K. Jain, S. Prabhakar, L. Hong, "A Multichannel Approach to Fingerprint Classification"/ IEEE TRANSACTIONS ON PATTERN ANALYSIS and MACHINE INTELLIGENCE, 1999, p.348-359;

[8] L. Hong, Y. Wan, A.K. Jain, "Fingerprint Image Enhancement: Algorithm and Performance Evaluation"/ IEEE TRANSACTIONS ON PATTERN ANALYSIS and MACHINE INTELLIGENCE, 1998, p. 777-789;

[9] A. Senior, "A Combination Fingerprint Classifier"/ IEEE TRANSACTIONS ON PATTERN ANALYSIS and MACHINE INTELLIGENCE, 2001, p. 1165-1174;

[10] D. Maltoni, D. Maio, A.K. Jain, S. Prabhakar, "Handbook of Fingerprint Recognition"/ Springer, New York, 2003.