|
|
2.1.3. Выходная информация
Выходной информацией для данной подсистемы является список, содержащий отпечатки из базы данных, в которых были обнаружены сходства с обрабатываемым отпечатком. Значение, говорящее о том, что отпечатки совпали, так же получено опытным путем.
В каждой строке массива списка содержится описание отпечатка, его имя, количество совпавших точек при распознавании и степень сходства. В табл. 2.2 приведен формат строки.
Таблица 2.2
Формат строки
Поле
Формат
Описание
Name
Строковое
Имя отпечатка (наименование файла, из которого были взяты параметры)
Count
Целое
Количество минюций совпавших при сравнении отпечатков.
Pct
Дробное
Степень сходства отпечатков в процентах, принимает значения (0, 100].
1.5.3. Математическая постановка задачи
Преобразование относительных параметров к абсолютным параметрам компенсирует влияние параллельного переноса и поворота отпечатков пальцев при сканировании.
Преобразование происходит для каждой обнаруженной минюции относительно всех остальных минюций на изображении
На рис. 2.1 представлено изображение отпечатка пальца, с обнаруженными на нем минюциями. Линиями представлено относительное расположение точек относительно центральной.
На рис. 2.2 представлено изображение отпечатка того же пальца, но повернутого относительного первого на 45 градусов. Линиями представлено относительное расположение точек относительно центральной.
Прямой отпечаток
Рис. 2.1
Повернутый отпечаток
Рис 2.2
Для определения степени сходства обрабатываемого отпечатка с отпечатком, хранящимся в базе, была разработана сисьема допусков и критериев схожести отпечатков. Вследствие эластичности кожи и неплотного прижатия пальца при снятии отпечатка некоторые минюции на новом отпечатке могут сместиться, относительно минюций, хранящихся в базе.
Таким образом, точка считается совпавшей, если ее местоположение относительно другой точек входит в определенную область вокруг первоначального положения. На рис. 2.3 представлена область, в которой положение точки относительно другой считается совпавшим.
Область допуска
Рис. 2.3
Для вычисления степени сходства двух отпечатков происходит сравнение каждой минюции на обоих отпечатках. Cписок совпавших минюций получается при помощи отсеивания из первоначального списка тех минюций, которые не были обнаружены во втором списке, тоесть вокруг данной точки небыло обнаружено ниодной другой точки в попавшей в область допуска.
Отпечатки считаются схожими, если количество совпавших точек превышает определенный порог сходства.
Работа подсистемы реализуется следующими этапами:
- преобразование абсолютных параметров минюций к относительным параметрам минюций;
- разработка системы допусков для сравнения минюций;
- сравнение структурных представлений отпечатков пальцев.
Функциональная схема подсистемы представлена на рис.2.4
Функциональная схема подсистемы распознавания
Рис. 2.4
1.6. Описание алгоритма преобразования абсолютных параметров минюций к относительным параметрам
1.6.1. Назначение и характеристика алгоритма преобразования абсолютных параметров минюций к относительным
При приложении пальца к сканирующему устройству возможно смещение или поворот изображения отпечатка пальца по сравнению с тем, что уже хранится в базе. Данные погрешности не должны оказывать влияние на результат распознавания получаемого отпечатка пальца. Для этого был разработан алгоритм преобразования абсолютных параметров минюций к относительным. Посредствам такого преобразования удается предоствратить негативное влияние поворота и смещения, и распознать отпечаток, даже если он повернут на 180°.
Представим структурное представление отпечатка пальцев в виде списка M, содержащего параметры специальных точек:
Каждый из наборов параметров представляет собой одну точку. Для приведения параметров к относительным параметрам необходимо провести обзор и преобразование всех точек.
Так как необходимо оценить расстояние между каждой из пар минюций, сложность этих алгоритмов превышает o(N2), где N - количество обнаруженных минюций на изображении отпечатка пальца. В среднем количество точек на отпечатке не превышает 50, таким образом, потребуется 502 = 2500 операций, что является небольшим объемом вычислений. Тесты показывают, что современные пользовательские ЭВМ способны выполнять около операций вычисления расстояния в секунду.
Таким образом, на анализ одного изображения будет уходить в среднем секунд. Такие темпы обработки информации вполне отвечают понятию интерактивности, что является приемлемым условием.
1.6.2. Используемая информация
При реализации данного алгоритма используется массив информации, сформированный на предыдущем этапе обработки изображения отпечатка пальца в подсистеме анализа изображения. Каждый элемент массива представляет из себя структуру, содержащую все необходимые для обработки параметры минюций: координаты целого типа – 2х4 байта, угол направления 8 байт, тип точки 1 байт, поэтому общий размер массива должен быть кратен 2*4+8+1 = 17 байт.
,
где Xi, Yi – координаты минюций на растровом представлении изображения отпечатка пальцев, целые числа, величина которых ограничена размером изображения отпечатка в пикселах;
αi – направление предполагаемого продолжения гребня на отпечатке пальцев в точки типа окончание и направление слипания для точки типа раздвоение, дробное число, величина которого изменяется (–pi, +pi);
Тi – тип обнаруженной точки, битовое поле, принимает 2 значения «раздвоение» = 0 (false) и «окончание» = 1 (true);
k – количество минюций на исследуемом отпечатке.
Для обработки массивов используется двунаправленный список. Список представляет собой вектор:
В данную информационную структуру можно заносить и извлекать элементы с любой стороны.
1.6.3. Результаты решения
Выходной информацией для данной задачи является массив размерностью (k x k) с пустыми диагональными элементами, содержащий списки минюций и их взаимное расположение друг с другом.
Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29
При использовании материалов активная ссылка на источник обязательна.