Система идентификации личности по отпечаткам пальцев (стр. 6 из 21)
Представим структурное представление отпечатка пальцев в виде списка 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. Результаты решения
Выходной информацией для данной задачи является массив размерностью (kxk) с пустыми диагональными элементами, содержащий списки минюций и их взаимное расположение друг с другом.
Каждый элемент массива содержит описание точки, расстояние до второй точки, угол между собственным направлением точки и направлением во вторую точку, Угол между собственными направлениями двух точек. В табл. 2.3 приведен формат элемента массива.
Таблица 2.3
Структура элемента массивазаписи
| Поле | Формат | Описание |
| lij | Целое | Расстояние между i и j точками |
| A1ij | Дробное | Угол между собственным направлением точки i и направлением из точки i в точку j. A1ijÎ[0, 2*M_PI) |
| A2i | Дробное | Угол между собственными направлениями точек i и j. A2ijÎ[0, 2*M_PI) |
1.6.4. Математическое описание алгоритма преобразования абсолютных параметров минюций к относительным
Обобщенное математическое описание преобразования приведено в п.2.1.4.
Преобразование происходит для каждой обнаруженной минюции относительно всех остальных точек по следующим формулам:
,где i, j – минюции
dLengthij – расстояние между точками i и j
dAlpha1ij – угол между направлением точки i и направлением на точку j
dAlpha2ij – угол между направлением точки i и точки j
Alphai – угол вектора самой точки
Alphaij – угол вектора направления от точки i к точке j
На рис. 2.5 представлено расположение точки i относительно точки j со всеми полученными параметрами.
относительные параметры
Рис. 2.5
1.6.4.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. Конец
1.6.5. Требования к контрольному примеру
Контрольный пример должен содержать отпечатки более чем с одной обнаруженной минюцией.
1.6.6. Список условных обозначений
RelFing - список минюций в относительных параметрах
AbsFing - список минюций в абсолютных параметрах
listDots – относительные параметры точки
iterA1 – исследуемая точка в абсолютных параметрах
iterA2 – точка в абсолютных параметрах, относительно которой вычисляется точка iterA1
l – расстояние между точками iterA1 и iterA2
GetS – функция вычисления расстояния
|| - округление до ближайшего целого
vecAB – вектор между направлениями точки iterA1 и iterA2
GetAlpha – функция вычисления угла между векторами
tmpa
a1 = угол между направлением самой точки и направлением на другую точку
a2 = угол между направлениями точек.
1.7. Описание алгоритма сравнения структурных представлений отпечатков пальцев
1.7.1. Назначение и характеристика алгоритма сравнения структурных представлений отпечатков пальцев
Вследствие эластичности кожи и роста человека расстояние между точками может измениться, что не должно влиять на результат распознавания, однако разные точки так же не должны быть приняты за одну. Для этого в подсистеме распознавания была разработана система допусков при сравнении двух отпечатков.