− если обнаружена область разрыва, то выполняется восстановление целостности линии;
− если обнаружена область слипания, то выполняется разъединение линий.
Результатом работы является растр более пригодный для поиска на нем минюций, чем изначальный.
R – Битовый растр
Map – список. Map = {x, y}i
R.GetPixelColor(x,y) – получить значение цвета пикселя с координатами {x,y} на растре R
R.FloodFill(x, y, color) – залить область с цветом R.GetPixelColor(x,y) в цвет color
R.width() – ширина растра в пикселях
R.height() – высота растра в пикселях
R.ChangeLine(Map[i]) – обход по контуру линии из точки Map[i]
1. Начало
2. Формировать из растра R список линий Map
3. "i, : iÎ[1, |Map|] R.ChangeLine(Map[i])
4. Если растр R был изменён, то перейти к п. 2
5. Конец
Алгоритм для нахождения на растре точек принадлежащих разным папиллярным линиям.
2. x::=0, y::=0
3. Если R.GetPixelColor(x,y) != 0x000000, то перейти к п. 5
4. (x,y) Ì Map; R.FloodFill(x, y, 0xFFFFFF)
5. y++;
6. если y < R.width(), то перейти к п. 3
7. x++; y::=0;
8. если x < R.height(), то перейти к п. 3
9. Конец
Алгоритм для поиска слипаний, обрывов и устранение их на растре.
dot0, dot1 –точки принадлежащие контуру линии
vec0, vec1 – локальные направления
GetVec(dot0, dot1) - направление из точки dot0 в dot1
alphaTest – предопределенная константа определяющая сильное искривление контура папиллярной линии
NextDotCW(dot0, step) – получение координат точки следующей через step точек
Условия обрыва и слипания описаны в п.п. 2.2.4
2. dot0 ::= начальное значение
3. dot1 ::= NextDotCW(dot0, step);
4. vec0 ::= GetVec(dot0, dot1);
5. dot0 ::= dot1;
6. dot1 ::= NextDotCW(dot0, step);
7. vec1 ::= GetVec(dot0, dot1);
8. Если |vec1 – vec0| < alphaTest, то перейти к п. 11
9. Если найденная точка является слипанием, то разъединить линии
10. Если найденная точка является обрывом, то восстановить целостность линии
11. Если обход по контуру привел к начальной точке, то перейти к п.13
12. vec0 ::= vec1; перейти к п.5
13. Конец
Основной частью работы подсистемы является переход от растрового представления к структурному представлению. Для этого необходимо найти на растре такие области, которые соответствуют раздвоениям или окончаниям. Поиск осуществляется путем обхода черных областей на растре, соответствующих линиям папиллярного узора, по контуру, при этом места с сильным искривлением контура являются специфическими точками.
Входной информацией является битовый растр после предобработки. Растр имеет глубину 1бит на пиксель и разрешение 600dpi. Формат bmp (от слов BitMaP - битовая карта, или, говоря по-русски, битовый массив) представляет из себя несжатое (в основном), что позволяет не вносить погрешностей, изображение. Формат bmp довольно легко читается и выводится в ОС Windows, в которой есть специальные функции API /13/.
Выходной информацией является список параметров, где были обнаружены специфические точки (особенность, деталь), в абсолютных параметрах. Список, расположенный в памяти, на данном этапе содержит помимо нужных точек – ложные, которые образуются при некачественном входном образе. Каждый элемент массива содержит все необходимые параметры: координаты целого типа – 2х4 байта, угол направления 8 байт, тип точки 1 байт.
Структура массива:
Xi, Yi – Координаты минюции на растре
ai – Ориентация минюции
T – Тип (окончание либо раздвоение)
k – Количество минюций
Поиск минюций происходит по нахождению локальных особенностей. Локальные особенности это сильные искривления контура линий, одни из искривлений являются минюциями – это окончания и раздвоения, но помимо них существуют слипания соседних линий и обрывы одной линии.
На рис. 2.4 показано «окончание», при этом выполняется условие 2.
(2)
,
где A = {x,y};
B = {x,y};
D – эмпирическая величина.
На рис. 2.5 показано «раздвоение», при этом выполняется условие 2 для рис. 2.5.
Окончание
A – сильное искривление контура линии папиллярного узора;
B – вероятная точка продолжения линии папиллярного узора;
C – искривление контура в вероятной точке продолжения;
D1, D2 – прилегающие области;
L1, L2 – вероятные соседние линии папиллярного узора.
Рис. 2.4
Раздвоение
L1, L2 – вероятные соседние впадины папиллярного узора.
Рис. 2.5
Локальные особенности: разрыв и слипание описаны в п.п. 2.2.4.
Выделим основные действия по обработке каждой линии на изображении отпечатка:
− выделить произвольную черную точку на растре, принадлежащую обрабатываемой линии, и произвести обход по контуру линии папиллярного узора, которой принадлежит эта точка;
− если обнаружена минюция, то запишем ее координаты в список.
Результатом является список параметров, с обнаруженными специфическими точками (особенность, деталь), в абсолютных параметрах. Список на данном этапе содержит помимо нужных точек – ложные, которые образуются при некачественном входном образе.
R – битовый растр
R.width() – ширина растра в пикселах
R.height() – высота растра в пикселах
R.ReadLine(Map[i]) – обход по контуру линии из точки Map[i], получает список координат минюций
6. Начало
7. Формировать из растра R список линий Map
8. "i, : iÎ[1, |Map|] List ::= R.ReadLine(Map[i])
9. Вывод List
10. Конец
Алгоритм для нахождения на растре точек принадлежащих разным папиллярным линиям приведен в п.п. 2.2.5.1.
Алгоритм для поиска окончаний и раздвоений, формирования списка параметров локальных особенностей.
dot0, dot1 – точки принадлежащие контуру линии
vec0, vec1 – локольные направления
alphaTest – предопределенная константа
Return – возвращаемый список
9. type ::= vec1 < vec0; alpha ::= предположительное направление продолжения линии;
10. {dot0, alpha, type} Ì Return
В результате выделения специальных точек, есть такие, которые не являются минюциями и могут не присутствовать при следующем анализе, что отрицательно повлияет на результат сравнения и скорость работы, так как размер обрабатываемой информации будет больше. Для исключения таких точек выведем правила надежной точки:
− пара точек не может находиться ближе определенного расстояния;
− пара точек имеющих одинаковый тип и направленные друг на друга не могут находиться ближе 3*d, где d – расстояние между центрами соседних гребней;
− рядом с окончанием обязательно должны проходить пара соседних гребней;
− рядом с раздвоением обязательно должна проходить пара соседних впадин.
Входной информацией является выходная информация предыдущего этапа описанная в п.п. 2.3.3.
Страницы: 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, 30
