Описание постановки задачи выявления дефектов сканирования и их устранение

Характеристика задачи. Папиллярный узор представленный в виде растра содержит отдельные элементы линии. Линии – это отображение гребней папиллярного узора, обход по контуру этих линий позволит выделить отдельные гребни и получить информацию об их расположении на пальце. Однако в процессе получения растра отпечатка возможны типичные дефекты изображения, которые возникают вследствие попадания мусора на сканирующее устройство, существование порезов и складок на коже, непостоянном прижиме пальца к сканеру и изменение его положения при каждом новом сканировании.

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

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

Входная информация. Входной информацией является битовый растр отпечатка, полученный с помощью сканирования разрешением 600dpi. Расширение битового файла по-умолчанию *.bmp. Формат bmp (от слов BitMaP - битовый массив) представляет из себя несжатое (в основном), что позволяет не вносить погрешностей, изображение. Формат bmp довольно легко читается и выводится в ОС Windows, в которой есть специальные функции API.

Входной растр представлен форматом BMP, который имеет структуру представленнуюна рисунке 3.3.

Рисунок 3.3 - Входной растр представленный форматом BMP

В начале стоит заголовок файла – BITMAPFILEHEADER.

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

Математическая постановка. Поиск минюций происходит по нахождению локальных особенностей. Локальные особенности это сильные искривления контура линий. Искривления, которые являются минюциями – это окончания и раздвоения, но помимо них существуют слипания соседних линий и обрывы одной линии, что не является минюциями.

На рисунке 3.4 показан разрыв полосы, при всем этом производится последующее условие (формула 3.1):

, (3.1)

где A= {x,y};

B= {x,y};

D – эмпирическая величина.

На рисунке 3.5 показано слипание линий, при этом выполняется условие (формула 3.1) для рисунка 3.5.

Рисунок 3.4 - Разрыв линии

где A – сильное искривление контура линии папиллярного узора;

B – вероятная точка продолжения линии папиллярного узора;

C – искривление контура в вероятной точке продолжения;

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

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

Рисунок 3.5 - Слипание линий

где A – сильное искривление контура линии папиллярного узора;

B – вероятная точка продолжения линии папиллярного узора;

C – искривление контура в вероятной точке продолжения;

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

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

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

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

− если обнаружена область разрыва, то выполняется восстановление целостности линии;

− если обнаружена область слипания, то выполняется разъединение линий.

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

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]

Начало

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

"i, : iÎ[1, |Map|] R.ChangeLine(Map[i])

Если растр R был изменён, то перейти к п. 2

Конец

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

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

Начало

x::=0, y::=0

Если R.GetPixelColor(x,y) != 0x000000, то перейти к п. 5

(x,y) Ì Map; R.FloodFill(x,y, 0xFFFFFF)

y++;

если y < R.width(), то перейти к п. 3

x++; y::=0;

если x < R.height(), то перейти к п. 3

Конец

Описание алгоритма «ChangeLine». Алгоритм для поиска слипаний, обрывов и устранение их на растре.

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

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

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

alphaTest – предопределенная константа определяющая сильное искривление контура папиллярной линии

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

Условия разрыва и слипания описаны в пункте. 3.2.

Начало

dot0 ::= начальное значение

dot1 ::= NextDotCW(dot0,step);

vec0 ::= GetVec(dot0, dot1);

dot0 ::= dot1;

dot1 ::= NextDotCW(dot0, step);

vec1 ::= GetVec(dot0, dot1);

Если |vec1 – vec0| < alphaTest, то перейти к п. 11

Если найденная точка является слипанием, то разъединить линии

Если найденная точка является обрывом, то восстановить целостность линии

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

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

Конец

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

Входная информация. Входной информацией является битовый растр после предобработки. Растр имеет глубину 1бит на пиксель и разрешение 600dpi. Формат bmp (от слов BitMaP - битовая карта, или, говоря по-русски, битовый массив) представляет из себя несжатое (в основном), что позволяет не вносить погрешностей, изображение. Формат bmp довольно легко читается и выводится в ОС Windows, в которой есть специальные функции API.

Выходная информация. Выходной информацией является список параметров, где были обнаружены специфические точки (особенность, деталь), в абсолютных параметрах. Список, расположенный в памяти, на данном этапе содержит помимо нужных точек – ложные, которые образуются при некачественном входном образе. Каждый элемент массива (рисунок 3.6) содержит все необходимые параметры: координаты целого типа – 2х4 байта, угол направления 8 байт, тип точки 1 байт.

Рисунок 3.6 - Структура массива

где X_i, Y_i – Координаты минюции на растре;

a_i – Ориентация минюции;

T – Тип (окончание либо раздвоение);

k – Количество минюций.

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

На рисунке 3.6 показано «окончание», при этом выполняется условие (формула 3.2).

(3.2)

где A= {x,y};

B= {x,y};

D – эмпирическая величина.

На рисунке 3.7 показано «раздвоение», при этом выполняется условие (формула 3.2) для рисунка 3.7.

Рисунок 3.6 – Окончание

где A – сильное искривление контура линии папиллярного узора;

B – вероятная точка продолжения линии папиллярного узора;

C – искривление контура в вероятной точке продолжения;

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

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

Рисунок 3.7 – Раздвоение

где A – сильное искривление контура линии папиллярного узора;

B – вероятная точка продолжения линии папиллярного узора;

C – искривление контура в вероятной точке продолжения;

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

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

Локальные особенности: разрыв и слипание описаны в пункте 3.2.

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

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

− если обнаружена минюция, то запишем ее координаты в список.

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

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], получает список координат минюций

Начало

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

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

Вывод List

Конец

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

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

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

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

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

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

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

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

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

Начало

dot0 ::= начальное значение

dot1 ::= NextDotCW(dot0, step);

vec0 ::= GetVec(dot0, dot1);

dot0 ::= dot1;

dot1 ::= NextDotCW(dot0, step);

vec1 ::= GetVec(dot0, dot1);

Если |vec1 – vec0| < alphaTest, то перейти к п. 11

type ::= vec1 < vec0;
alpha ::= предположительное направление продолжения линии;

{dot0, alpha, type} Ì Return

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

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

Конец