Дактилоскоп: цифровая обработка отпечатков пальца

• Содержание
• 1. Введение
• 2. Постановка задачи
• 3. Обзор известных подходов
• 3.1 Криминалистический подход
• 3.1.2 Виды признаков различимости отпечатков
• 3.1.1 Нахождение признаков
• 3.2 Математический подход
• 3.3 Сравнительные характеристики подходов
• 4. Подход к решению задачи
• 5. Алгоритм решения задачи
• 6. Программная реализация
• 6.1 Файлы
• 6.2 Структуры данных
• 6.3 Процедуры и функции
• 7. Результаты экспериментов
• 8. Инструкция пользователю
• 9. Выводы
• 10. Безопасность и экологичность работы
• 10.1 Гигиенические критерии оценки напряженности трудового процесса.
• 10.2 Мероприятия по устранению вредных факторов напряженности труда разработчика
• 10.3 Экологичность работы
• 11. Заключение
• 12. Литература
• Приложение

1. Введение

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

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

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

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

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

Таблица. 1.1.

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

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

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

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

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

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

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

3. Обзор известных подходов

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

3.1 Криминалистический подход

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

3.1.2 Виды признаков различимости отпечатков

Существует четыре уровня признаков различимости отпечатков «Криминалистика» учебник М: Мир, 1975.

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

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

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

Второй уровень — макроэлементы отпечатка: центры и дельты. Их типы (дельты бывают левые и правые, центры с направлением и без), взаиморасположение и направленность более конкретно характеризуют отпечаток по сравнению с типом узора.

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

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

В криминалистике для идентификации используют первые три уровня признаков «Криминалистика» учебник М: Мир, 1975. Четвертый же уровень стал доступен к изучению лишь с появлением высокоразрешающей аппаратуры сканирования. Речь идет о микроскопических порах на папиллярных линиях — выходах потовых желез. Их расположение также уникально. Однако ни одна система дактилоскопической идентификации не использует данный критерий в связи с необходимостью обработки огромного объема информации и нестабильностью проявления данных элементов, связанной с загрязнением, запотеванием отпечатка.

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

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

Производится определение и сравнение типов узора на обоих отпечатках. В случае их совпадения анализируется расположение макроэлементов (одинаковость типов, направления, расстояний и т. д.). Если все признаки совпадают, работа переходит на точечный уровень. Анализируется наличие одинаковых элементов на обоих отпечатках. И в случае обнаружения хотя бы одного разногласия (например, на соответствующем участке параллельных линий у другого отпечатка найдено слияние/разветвление) — принимается решение о несовпадении отпечатков. Лишь в случае полного повторения расположения элементов делается противоположное заключение.

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

3.1.1 Нахождение признаков

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

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

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

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

3.2 Математический подход

Существует и другие методы, заимствованные из различных математических теорий обработки изображений Прэтт. У. «Цифровая обработка изображений» М.:Мир 1982 г. том 1,2. Один из них — корреляционное сравнение изображений двух отпечатков Дуда Р. «Распознавание образов и анализ сцен» М: Мир 1976 г. Суть его состоит в наложении двух изображений отпечатков пальцев в разных положениях и определение наилучшего коэффициента совпадения. При превышении априорно заданного порога совпадения — отпечатки признаются идентичными. Данный метод еще называют сравнение с эталоном, т. е. имеется некоторое изображение, которое называется эталоном, и с ним сравниваются остальные изображения. Для нашего примера эталоном может выступать анализируемый отпечаток, а сравниваемыми изображениями графическая информация об отпечатках пальцев, хранящаяся в базе данных. Таким образом, пусть g (i, j) — некоторое изображение, а t (i, j) — эталон, D — область изменения эталона. Тогда мера соответствия между частью изображения и эталоном можно выразить следующей формулой:

Здесь сумма берется по всем значениями i j таким, что точка (i-m, j-n) находится внутри области D.

Данное определение сводится к сдвигу эталона t (i, j) в положение (m, n) на изображении и к присвоению величине M (m, n) значения, равного числу элементов, в которых уровни полутонов изображения и размещенного на нем эталона различны. Естественно чем меньше значение M (m, n) тем лучше.

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

3.3 Сравнительные характеристики подходов

Таким образом, все за и против конкретного метода можно свести в следующую таблицу:

Таблица 3.1

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

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

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

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

4. Подход к решению задачи

дактилоскопия папиллярный криминалистический

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

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

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

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

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

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

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

Ниже приведены примеры подобных результатов.

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

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

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

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

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

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

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

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

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

Рис. 5.1. Распределение интенсивностей

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

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

Рис. 5.2 Аппроксимация

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

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

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

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

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

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

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

Таким общий алгоритм обработки изображения сводится к следующим пунктам.

Алгоритм анализа изображения.

Проводим очередную вертикальную линию.

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

Аппроксимируем полученные значения.

Определяем локальные максимумы, на ступенчатом графике.

Берем очередной максимум, и принимаем его в качестве линии.

Проверяем, не попадает ли в эту линию, ранее проанализированная. Если попадает, то идем на пункт 8.

Берем на линии затравочную точку, и инициируем прослеживание линии.

Если еще есть не рассмотренные максимумы на вертикальной линии, то идем на пункт 5.

Если еще не дошли до края изображения, то на пункт 1.

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

Алгоритм аппроксимации.

Минимум и максимум равны отрицательным значениям

Начало_интервала :=1; Конец_интервала:=1;

Берем очередное значение интенсивности.

Если минимум <0 и максимум < 0, то минимум := интенсивность и максимум := интенсивность.

Если минимум > интенсивность, то минимум := интенсивность.

Если максимум < интенсивность, то максимум := интенсивность.

Если (Максимум — Минимум > Порог), то Интервал [Начало_интервала, Конец_интервла] аппроксимируем величиной Максимум. Минимум и Максимум вновь приравниваются отрицательным величинам. Начало_интервала := Конец_интервала

Конец_интервала := Конец_интервла +1;

Если остались еще значения, то идем на пункт 3.

Конец.

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

Берем очередное направление (например, настраиваем угол)

Сумма_интенсивностей :=0;

Берем очередную точку, начиная с заданной, в текущем направлении.

Сумма_интенсивностей := Сумма_интенсивностей + Интенсивность_текущей_точки * Весовой_коэфициент.

Если прошли еще не все точки в текущем направлении, то на пункт 3.

Если это первое направление, то Минимум := сумма_интенсивностей и Максимум:= сумма_интенсивностей.

Если Максимум < сумма_интенсивностей, то Максимум := сумма_интенсивностей

Если Минимум > сумма_интенсивностей, то Минимум := сумма_интенсивностей.

Набираем статистику по интенсивностям, т. е. Массив_интенсивностей[ текущее_направление ] := сумма_интенсивностей.

Если текущее_направление еще не последнее, то на пункт 1.

Аппроксимируем график интенсивностей, представленный в виде массива Массив_интенсивностей.

Берем очередной локальный максимум на аппроксимированном графике.

Определяем вероятность по формуле: вероятность := (аппроксимируещая_величина — Минимум) / (Максимум — Минимум).

Если вероятность > 0.7, то определяем направление, например как середина аппроксимированного интервала. Это и будет одним из направлений для точки.

Если еще есть локальные максимумы, то на пункт 12.

Конец.

Алгоритм отслеживания линии.

Берем затравочную точку и помещаем ее в стек. Для затравочной точки запоминаем направление как отрицательное значение.

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

Просчитываем все направления для точки.

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

Запоминаем оставшиеся направления.

Если направлений не осталось, то на пункт 11.

Берем очередное направление.

Делаем шаг в текущем направлении.

Проталкиваем в стек полученную точку. Для точки запоминаем направление обратное текущему.

Если есть еще направления, то на пункт 7.

Если стек не пуст, то на пункт 2.

Конец.

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

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

6. Программная реализация

В результате работы была разработана программа, реализующая вышеуказанный алгоритм. Программа была разработана под ОС Windows 95, в среде программирования Delphi3. Выбор именно Delphi при разработке обусловлен следующими соображениями:

При разработке реализуется приложение под Windows, работа с которым представляется более удобным, нежели с приложением под DOS.

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

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

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

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

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

6.1 Файлы

finger.dpr — файл проекта

finger.dof — файл настроек проекта

main00.dcu — модуль содержащий основные процедуры и функции

main00.pas — соответствующий исходный код программы

main00.dfm — файл формы Delphi.

finger.resфайл ресурсов

finger.exe — выполняемый модуль.

6.2 Структуры данных

Line_appr = record

value: integer;

begin_dir, end_dir: integer;

Max_dir: integer;

end;

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

Value: integer — данное поле содержит аппроксимированное значение некоторого участка.

begin_dir: integer — содержит значение начала аппроксимированного участка. Данное значение представляет собой не что иное, как номер направление (от 0 до 35).

end_dir: integer — содержит значение конца аппроксимированного участка. Это значение, также как и begin_dir, представляет собой номер направления.

Max_dir: integer — данное поле содержит номер направления, при котором на данном аппроксимированном участке [begin_dir, end_dir] достигается максимальное значение, на не аппроксимированном графике. Данное направление, в случае если этот участок будет локальным максимумом, и его вероятность превысит порог, берется в качестве направления точки.

Tpoint = record

x, y: integer;

type_point: integer;

end;

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

x, y: integer — это экранные координаты найденной точки.

type_point: integer — это тип найденной точки (т.е. это может быть окончание линии или разветвление и т. д.).

T_Line_Appr_array = array [1.35] of Line_appr;

Это массив записей Line_appr. Таким образом, с помощью данного массива представляется аппроксимированный график.

T_All_Y = array [0.35] of integer;

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

T_Stack_El = class (TObject)

x, y: integer;

direction: integer;

end;

Данный класс представляет собой элемент стека. Используется на стадии отслеживания линии. Т.к. в задачах подобного типа, как правило, трудно предугадать размер стека, поэтому стек был реализован в виде списка, где в каждом элементе содержится указатель на элемент стека. Под элементы стека также динамически выделяется память. Т.к. все объекты в Object Pascal динамические и в синтаксисе необходимо указывать дополнительных^, что не загромождает код было решено реализовать элемент стека в виде потомка класса Tobject, и заодно наследовать все его полезные свойства, т. е. не требуется самостоятельно заботиться о выделении памяти под объект и т. п.

6.3 Процедуры и функции

function GetOpositeDir (direction: integer): integer;

Функция возвращает для направления direction значение его обратного направления.

function Sub_Direction (direction1,direction2: integer): integer;

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

function GetX (value: integer): integer;

Функция возвращает смещение по оси X в текущем направлении по вектору на величину value.

function GetY (value: integer): integer;

Функция возвращает смещение по оси Y в текущем направлении по вектору на величину value.

procedure SolvePixel (x, y: integer;var line_appr_array: T_line_appr_array;

var Num_Line_appr: integer;var All_Y: T_All_Y;

var Max_value, Min_value: integer);

Процедура просчитывает окрестность заданной точки и возвращает соответствующие результаты.

x, y — координаты рассматриваемой точки.

Line_appr_array — массив аппроксимированных значений.

Num_line_appr — количество аппроксимированный участков, используется совместно с Line_appr_array.

All_Y — массив, содержащие не аппроксимированные данные по всем направлениям.

Max_value — максимальное значение суммарной интенсивности в статистике.

Min_value — минимальное значение суммарной интенсивности в статистике.

function GetIntensPixel (x, y: integer): integer;

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

x, y — координаты пиксела.

procedure SolveLine (x, y: integer);

процедура просчитывает линий, начиная с затравочной точки.

x, y — координаты затравочной точки.

procedure MakeVertLine (value: ineteger);

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

procedure AnalysFingerPrint;

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

function CompareFingers: boolean;

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

7. Результаты экспериментов

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

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

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

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

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

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

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