Система идентификации личности по отпечаткам пальцев. Подсистема распознавания

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

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

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

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

Прямой отпечаток

Рис. 2.1

Повернутый отпечаток

Рис 2.2

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

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

Область допуска

Рис. 2.3

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

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

Работа подсистемы реализуется  следующими этапами:

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

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

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

Рис. 2.4

 

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

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

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

Представим  структурное представление отпечатка  пальцев в виде списка M, содержащего параметры специальных точек:

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

Так как необходимо оценить расстояние между каждой из пар минюций, сложность  этих алгоритмов превышает o(N²), где N - количество обнаруженных минюций на изображении отпечатка пальца. В среднем количество точек на отпечатке не превышает 50, таким образом, потребуется 50² = 2500 операций, что является небольшим объемом вычислений. Тесты показывают, что современные пользовательские ЭВМ способны выполнять около операций вычисления расстояния в секунду.

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

2. Используемая информация

При реализации данного алгоритма  используется массив информации, сформированный на предыдущем этапе обработки изображения  отпечатка пальца в подсистеме анализа  изображения.  Каждый элемент массива  представляет из себя структуру, содержащую все необходимые для обработки параметры минюций: координаты целого типа – 2х4 байта, угол направления 8 байт, тип точки 1 байт, поэтому общий размер массива должен быть кратен 2*4+8+1 = 17 байт.

,

 

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

α_i – направление предполагаемого продолжения гребня на отпечатке пальцев в точки типа окончание и направление слипания для точки типа раздвоение, дробное число, величина которого изменяется (–pi, +pi);

Т_i – тип обнаруженной точки, битовое поле, принимает 2 значения «раздвоение» = 0 (false) и «окончание» = 1 (true);

k – количество минюций на исследуемом отпечатке.

Для обработки массивов используется двунаправленный список. Список представляет собой вектор:

В данную информационную структуру  можно заносить и извлекать элементы с любой стороны.

3. Результаты решения

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

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

Таблица 2.3

Структура элемента массивазаписи

 

Поле	Формат	Описание
lij	Целое	Расстояние между i и j точками
A1ij	Дробное	Угол между собственным  направлением точки i и направлением из точки i в точку j. A1ijÎ[0, 2*M_PI)
A2i	Дробное	Угол между собственными направлениями точек i и j. A2ijÎ[0, 2*M_PI)

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

Обобщенное математическое описание преобразования приведено в п.2.1.4.

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

 

,

 

где i, j – минюции

dLength_ij – расстояние между точками i и j

dAlpha1_ij – угол между направлением точки i и направлением на точку j

dAlpha2_ij – угол между направлением точки i и точки j

Alpha_i – угол вектора самой точки

Alpha_ij – угол вектора направления от точки i к точке j

На  рис. 2.5 представлено расположение точки i относительно точки j со всеми полученными параметрами.

 

относительные параметры

Рис. 2.5

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

1. Очистить список RelFing с относительными параметрами отпечатка
2. Если список AbsFing пуст, перейти к пункту 20
3. Для каждого элемента iterA1 списка AbsFing выполнить пункты 4 - 19
4. Очистить список listDots с относительными параметрами точки
5. Для каждого элемента iterA2 списка AbsFing выполнить пункты 5 - 17
6. Если iterA2 == iterA1, перейти к пункту 5.
7. l = |GetS(iterA1->coord, iterA2->coord)|
8. vecAB = GetAlpha(iterA2->coord, iterA1->coord)
9. tmpa = iterA1->alpha - vecAB;
10. Если (tmpa < 0), переход к п. 11, иначе переход к п. 12
11. tmpa = 2*M_PI + tmpa;
12. a1 = |tmpa * 180.0/M_PI +0.5|
13. tmpa = iterA2->alpha – iterA1->alpha
14. Если (tmpa < 0) , переход к п. 15, иначе переход к п. 16
15. tmpa = 2*M_PI + tmpa;
16. a2 = |tmpa * 180.0/M_PI +0.5|
17. Добавить в список listDots параметры очередной точки – l, a1, a2, перейти к п. 5.
18. отсортировать список listDots
19. занести относительные параметры точки listDots в список отпечатка RelFing, перейти к п. 3
20. Конец

5. Требования к контрольному примеру

Контрольный пример должен содержать отпечатки более чем с одной обнаруженной минюцией.

6. Список условных обозначений

RelFing  - список минюций в относительных параметрах

AbsFing - список минюций в абсолютных параметрах

listDots – относительные параметры  точки

iterA1 – исследуемая точка в абсолютных параметрах

iterA2 – точка в абсолютных параметрах, относительно которой вычисляется точка iterA1

l – расстояние между точками iterA1 и iterA2

GetS – функция вычисления расстояния

|| - округление до ближайшего целого

vecAB – вектор между направлениями точки iterA1 и iterA2

GetAlpha – функция вычисления угла между векторами 

tmpa

a1 = угол между направлением самой точки и направлением на другую точку

a2 = угол между направлениями точек.

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

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

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

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

2. Используемая информация

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

3. Результаты решения

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

 

Таблица 2.4

Структура записи об обнаруженных отпечатках

 

Поле	Формат	Описание
Name	Строковое	Имя отпечатка (наименование файла, из которого были взяты параметры)
Count	Целое	Количество минюций  совпавших при сравнении отпечатков.
Pct	Дробное	Степень сходства отпечатков в процентах, принимает значения (0, 100].

4. Математическое описание алгоритма нахождения статистических характеристик цветового кластера

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

Область допуска

Рис. 2.6

Для вычисления степени сходства двух отпечатков происходит сравнение каждой минюции на обоих отпечатках:

M – список минюций на обрабатываемом образе

k – количество минюций на  обрабатываемом образе

M = {m1, m2, …, mk}

N – список минюций одного  отпечатка из базы отпечатков

l – количество минюций на отпечатке  из базы отпечатков

N = {n1, n2, …, nl}

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

S = {mi, где i=(1..k), P(mi, N)}

r = | S | – количество совпавших точек.

P(mi , N) – Точка считается совпавшей,  если относительно нее найдено необходимое количество удовлетворяющих условию точек.

Отпечатки считаются схожими, если количество совпавших точек превышает порог  сходства (p):

r ≥ p – условия совпадения

r < p – условие не совпадения

5. Алгоритм нахождения статистических характеристик цветового кластера

1. CONFIRM_VAL = 9; DELTA_L = 10.0; DELTA_A = 10.0; confirmDot = 0; short needVal = |min(this->size(),fng.size())/3.0 +0.5|;
2. для каждо<span class="dash041e_0431_044b_0447_043d_044b_0439__Char" st