Система идентификации личности по отпечаткам пальцев Подсистема анализа изображения (стр. 7 из 20)

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.ReadLine(Map[i]) – обход по контуру линии из точки Map[i], получает список координат минюций

6. Начало

7. Формировать из растра R список линий Map

8. "i, : iÎ[1, |Map|] List ::= R.ReadLine(Map[i])

9. Вывод List

10. Конец

2.3.5.1. Описание алгоритма «Формирование списка линий»

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

2.3.5.2. Описание алгоритма «ReadLine»

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

dot0, dot1 – точки принадлежащие контуру линии

vec0, vec1 – локольные направления

GetVec(dot0, dot1) - направление из точки dot0 в dot1

alphaTest – предопределенная константа

NextDotCW(dot0, step) – получение координат точки следующей через step точек

Return – возвращаемый список

Условия обрыва и слипания описаны в п.п. 2.2.4

1. Начало

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. type ::= vec1 < vec0;
alpha ::= предположительное направление продолжения линии;

10. {dot0, alpha, type} Ì Return

11. Если обход по контуру привел к начальной точке, то перейти к п.13

12. vec0 ::= vec1; перейти к п.5

13. Конец

2.4. Описание постановки задачи сортировки списка абсолютных параметров, исключение ложных и ненадежных минюций

2.4.1. Характеристика задачи

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

− пара точек не может находиться ближе определенного расстояния;

− пара точек имеющих одинаковый тип и направленные друг на друга не могут находиться ближе 3*d, где d – расстояние между центрами соседних гребней;

− рядом с окончанием обязательно должны проходить пара соседних гребней;

− рядом с раздвоением обязательно должна проходить пара соседних впадин.

2.4.2. Входная информация

Входной информацией является выходная информация предыдущего этапа описанная в п.п. 2.3.3.

2.4.3. Выходная информация

Выходной информацией является список минюций в абсолютных параметрах. Данное структурное представление на основе минюций достаточно для распознавания личности по отпечаткам пальцев. Такое представление гораздо меньше растрового по размеру, благодаря чему организуется удобное хранение и быстрая обработка. Каждый элемент массива содержит все необходимые параметры: координаты целого типа - 2х4 байта, угол направления 8 байт, тип точки 1 байт. При среднем количестве точек 50 получаем объем занимаемый одним обработанным отпечатком примерно 850 байт.

2.4.4. Математическая постановка

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

На рис. 2.6 показан вид пореза или складки кожи, при этом выполняется следующее условие:

, (3)

Порез

D1, D2 – прилегающие области;

L1, L2 – вероятные соседние линии папиллярного узора.

Рис. 2.6

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

Полученный список сортируется по условию:

(4)

где: i, j – найденные точки;

x, y – координаты минюции на растре;

a – угол направления;

T – тип минюции (раздвоение или окончание);

D1, D2, aMin, aMax – константы (устанавливаются экспериментально).

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

1. Начало

2. "i,j : i¹j Ù

выполнить Delete(Array,j), Delete(Array,i)

3.

"i,j : i¹j Ù

4.
выполнить Delete(Array,j), Delete(Array,i)

Конец

2.5. Описание подпрограмм

2.5.1. Подпрограмма NextDotCW

Подпрограмма NextDotCW производит поиска следующей точки на контуре линии «по часовой стрелке», благодаря ей организуется обход линии по контуру. Предназначена для реализации алгоритма исправления искажений и используется при поиске минюций на входном образе. Схема подпрограммы изображена на рис. 2.7.

Синтаксис:

CPoint TFingPicture::NextDotCW(const CPoint dot, int &vec)

Входные данные для данной подпрограммы представлены:

CPoint dot – структура данных – точка {x,y} от которой нужно найти соседствующую точку;

int vec – направление предыдущего перехода при поиске, vecÎ[0..7]. Служит для ускорения поиска;

COLORREF clMas[9] – массив цветов окрестных точек;

Выходные данные для данной подпрограммы представлены:

CPoint incXY[8] – координаты окрестных точек;

CPoint newDot – найденная точка, которая является смежной с точкой dot. Переход от точки dot к найденной смежной точке образует обход «по часовой стрелке».

2.5.2. Подпрограмма NextDotCCW

Подпрограмма NextDotCCW производит поиска следующей точки на контуре линии «против часовой стрелки», благодаря ей организуется обход линии по контуру. Предназначена для реализации алгоритма исправления искажений и используется при поиске минюций на входном образе. Схема подпрограммы изображена на рис. 2.8.

Синтаксис:

CPoint TFingPicture::NextDotСCW(const CPoint dot, int &vec)

Входные данные для данной подпрограммы представлены:

CPoint dot – структура данных – точка {x,y} от которой нужно найти соседствующую точку;

int vec – направление предыдущего перехода при поиске, vecÎ[0..7]. Служит для ускорения поиска;

COLORREF clMas[9] – массив цветов окрестных точек;

Выходные данные для данной подпрограммы представлены:

CPoint incXY[8] – координаты окрестных точек;

CPoint newDot – найденная точка, которая является смежной с точкой dot. Переход от точки dot к найденной смежной точке образует обход «против часовой стрелки»

Схема подпрограммы «NextDotCW»

Рис. 2.7

Схема подпрограммы «NextDotСCW»

Рис. 2.8

2.5.3. Подпрограмма LookPic

Подпрограмма LookPic предназначена для обработки загруженного изображения и получение из него списка папиллярных линий. Каждая линия определяется одной точкой {x,y}. Схема подпрограммы изображена на рис. 2.9.

Синтаксис:

list<TMapElDot> TAnalysePicture::LookPic()

Входные данные для данной подпрограммы представлены:

TFingPicture *pic – указатель на битовый образ в памяти, который был загружен для обработки

Выходные данные для данной подпрограммы представлены:

list<TMapElDot> Map – список папиллярных линий на растре.

Используемые переменные:

Map – список обрабатываемых линий на папиллярном узоре, каждой линии соответствует точка {x,y}.

Используемые подпрограммы:

Pic.GetPixel(x,y) – возвращает цвет пикселя с координатами {x,y} на растре pic;

ClearLine(pic,x,y) – удаление области с цветом GetPixel(x,y) на растре pic.

Схема подпрограммы «LookPic»

Рис. 2.9

Подпрограмма ChangeLine

Подпрограмма ChangeLine предназначена для модификация линии на растре, производит исправление слипаний и обрывов. Схема подпрограммы изображена на рис. 2.10.

Синтаксис:

int TAnalysePicture::ChangeLine(list<TMapElDot>::iterator _dot, list<TMapElDot> &_map)

Входные данные для данной подпрограммы представлены:

TFingPicture *pic – указатель на битовый образ в памяти, который был загружен для обработки;

list<TMapElDot>::iterator _dot – указатель на текущую обрабатываемую линию;

list<TMapElDot> &_map – список обрабатываемых линий на растре.

Выходные данные для данной подпрограммы представлены:

int changeN – произведенное количество исправлений на растре;