способ гребневого счета на основе топологии дактилоскопического узора

Формула изобретения

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

2. Способ кодирования дактилоскопического узора по п.1, отличающийся тем, что на узоре выделяют области информативные и неинформативные, а линии и особенности располагают в информативной области.

Описание изобретения к патенту

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

Известен способ кодирования папиллярных узоров, заключающийся в кручении условного вектора вокруг заданного центра и фиксации шестнадцатеричного кода при прохождении этого вектора через особенность (заявка PCT № 87/01224, МПК G06K 9/00, опубл. 1987).

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

Известен способ кодирования папиллярного узора, содержащего n особенностей, заключающийся в определении для каждой особенности вектора направления, координат, типа особенности, вектора и величины кривизны папиллярных линий в окрестности особенности, масштабной характеристики как среднего расстояния между папиллярными линиями в окрестности особенности, а также расстояния и гребневого счета от особенности до остальных n-1 особенностей, встречающихся в порядке вращения условного вектора вокруг особенности, начиная с вектора направления самой особенности, и углов, которые образуются между вектором направления особенности и условным вектором при встрече условного вектора с очередной из n-1 особенностей (патент РФ № 2054197, МПК G06K 9/46, опубл. 1992).

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

Наиболее близким к предлагаемому изобретению является способ кодирования отпечатка папиллярного узора, заключающийся в выделении на отпечатке линий и особенностей, нумерации особенностей, определении для каждой особенности вектора направления, координат, типа, вектора кривизны линий и масштабной характеристики в окрестности особенности, топологической характеристики, представленной нумерованным набором пар, образованных событием в виде числа и номером соответствующей особенности, причем топологическая характеристика детектируется при движении по связям от сечения, проходящего через особенность перпендикулярно линиям (патент РФ № 2185660, МПК7 G06K 9/52, опубл. 2002). Данный способ выбран в качестве прототипа.

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

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

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

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

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

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

Сущность предлагаемого способа иллюстрируется четырьмя фигурами и четырьмя таблицами:

на фиг.1 изображена особенность типа окончания с вектором направления и проекциями на соседние папиллярные линии 1 и 2;

на фиг.2 изображена особенность типа разветвления с вектором направления и проекциями на соседние папиллярные линии 1 и 2;

на фиг.3 от особенности типа окончания проведено сечение (длинный вертикальный пунктир) через другие линии, которые разрезаны сечением, пронумерованы и образуют связи 0-16, на которых располагаются особенности 20-27 с двумя проекциями от особенностей или одной проекцией от 20-й особенности из-за границы узора;

на фиг.4 от особенности типа разветвления проведено сечение (длинный вертикальный пунктир) через другие линии, которые разрезаны сечением, пронумерованы и образуют связи 0-18, на которых располагаются особенности 20-27 с двумя проекциями от каждой особенности или с одной проекцией от особенности 23-й из-за границы узора;

в табл.1 показана топологическая характеристика для особенности типа окончания, сечение через которую представлено на фиг.3, с указанием на нумерованных связях событий-чисел и номеров особенностей;

в табл.2 показана топологическая характеристика для особенности типа разветвления, сечение через которую представлено на фиг.4, с указанием на нумерованных связях событий-чисел и номеров особенностей;

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

в табл.4 показан гребневый счет для топологической характеристики разветвления из табл.2 с указанием номеров особенностей и величин гребневого счета.

Рассмотрим последовательность выполняемых действий в заявляемом изобретении.

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

Затем для каждой особенности дактилоскопического узора определяют топологическую характеристику.

Рассмотрим определение топологической характеристики для одной особенности. Для этого через особенность (базовая особенность) проводят сечение вправо и влево на глубину нескольких линий (обычно 1-8 линий вправо и столько же влево) перпендикулярно касательным к пересекаемым линиям. Если кривизна папиллярных линии меняется, сечение изгибается. Пересеченные линии нумеруют по часовой стрелке, при этом каждая пересеченная линия распадается на две связи, начинающиеся в точке пересечения линии с сечением. На фиг.3 пронумерованы связи 0-16, на фиг.4 - связи 0-18.

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

0000 - нет особенности или проекции от особенности на связи (линия прерывается на краю отпечатка);

1101 - на связи проекция от окончания, расположенного справа от связи по ходу прослеживания связи, вектор направления окончания ориентирован навстречу ходу по связи;

1001 - на связи проекция от окончания, расположенного справа от связи по ходу прослеживания связи, вектор направления окончания ориентирован по ходу по связи;

1110 - на связи проекция от окончания, расположенного слева от связи по ходу прослеживания связи, вектор направления окончания ориентирован навстречу ходу по связи;

1010 - на связи проекция от окончания, расположенного слева от связи по ходу прослеживания связи, вектор направления окончания ориентирован по ходу по связи;

0101 - на связи проекция от разветвления, расположенного справа от связи по ходу прослеживания связи, вектор направления разветвления ориентирован навстречу ходу по связи;

0001 - на связи проекция от разветвления, расположенного справа от связи по ходу прослеживания связи, вектор направления разветвления ориентирован по ходу по связи;

0110 - на связи проекция от разветвления, расположенного слева от связи по ходу прослеживания связи, вектор направления разветвления ориентирован навстречу ходу по связи;

0010 - на связи проекция от разветвления, расположенного слева от связи по ходу прослеживания связи, вектор направления разветвления ориентирован по ходу по связи;

1111 - окончание на связи, вектор направления окончания ориентирован навстречу ходу по связи;

0011 - разветвление на связи, вектор направления разветвления ориентирован по ходу по связи;

0111 - разветвление на связи, образованной линией, касательная к которой образует минимальный угол при повороте вектора направления разветвления на связи против часовой стрелки;

1011 - разветвление на связи, образованной линией, касательная к которой образует минимальный угол при повороте вектора направления разветвления на связи по часовой стрелке;

1100 - связь по линии замыкается, какая-либо особенность или проекция от особенности отсутствует.

С событием-числом, детектированным на связи, записывают номер особенности, породившей это событие, а сами события-числа жестко привязывают к номеру связи. Для событий 0000 и 1100 номера особенностей отсутствуют. Нумерованный набор связей с событиями-числами и соответствующими номерами особенностей есть топологическая характеристика, которая для особенности на фиг.3 представлена в табл.1, а для особенности на фиг.4 представлена в табл.2. Событие и соответствующий номер особенности образуют упорядоченную пару, а сами эти пары однозначно привязываются к номеру связи.

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

При расчете подсчитывают количество переходов с линии на линию в сечении. Переход с линии, на которой располагается базовая особенность, на смежную линию считается первым (линии 1 и 2 на фиг.1 и фиг.2). Если особенность непосредственно располагается на связи, то гребневый счет до этой особенности полагают равным количеству переходов. Например, для окончания на фиг.3 гребневый счет до особенности 23 равен 2, особенности 25-3, особенности 22-1. Если особенность располагается на связи, образованной линией с базовой особенностью, то гребневый счет равен нулю. Например, для разветвления на фиг.4 гребневый счет до особенности 21 равен 0, особенности 25 - 0.

Также при расчете учитывают событие, сохраняемое в топологической характеристике. Если особенность представлена в топологической характеристике только проекциями, то проекция, приближающая особенность к линии с базовой особенностью, добавляет к количеству переходов с линии на линию значение 1/2. Например, для окончания на фиг.3 гребневый счет до особенности 20 равен 3+1/2. Соответственно, проекция, удаляющая особенность от линии с базовой особенностью, вычитает из количества переходов с линии на линию значение 1/2. Например, для окончания на фиг.3 гребневый счет до особенности 24 по связи номер 3 равен 1+1/2, а по связи номер 7 равен 2-1/2. В целом по всем связям, для которых номер особенности одинаковый, вычисляется средняя величина гребневого счета, и для той же особенности номер 24 на фиг.3 эта величина равна ((1+1/2)+(2-1/2))/2=1,5. Приближает ли проекция особенность к линии с базовой особенностью или удаляет, зависит от числа-события и номера связи, но знак ±1/2 определяется, очевидно, однозначно.

Гребневый счет может определяться для части особенностей в топологической характеристике, например для одной особенности. Полный гребневый счет для топологической характеристики окончания (табл.1) показан в табл.3, а для разветвления (табл.2) показан в табл.4.

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

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

На этом кодирование дактилоскопического узора завершают.

Заметим, что линии, связи и особенности располагаются в информативных областях, заметно отличающихся от неинформативных областей, по которым проследить связи невозможно. В неинформативных областях особенности и линии не выделяются. Поэтому разделение площади узора на информативные и неинформативные области существенно. Это отражается в виде границы узора на фиг.3 и фиг.4. Если сечение от особенности выходит за границы узора, то для соответствующих связей, помеченных пунктиром, число события 0000, а гребневый счет не определяется.

Отметим преимущества предлагаемого способа кодирования.

В отличие от прототипа, здесь топологические характеристики дополняются значениями гребневого счета по меньшей мере до одной особенности в топологической характеристике. Гребневый счет строго определен структурой изображения, то есть составом топологической характеристики. Он определяется не до всех остальных особенностей, а для определенного их подмножества, и это подмножество структурировано лучше, чем в методе ограничения длины условного вектора вращения (подобно патенту РФ № 2054197). Действительно, особенности в топологическую характеристику набираются исходя не из геометрических характеристик особенностей, а из топологических свойств линий. Так, близкие к базовой особенности другие особенности могут не попасть в состав топологического вектора, а далекие особенности - могут (например, особенность 27 на фиг.3).

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

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

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

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

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

Гребневый счет повышает точность идентификации изображения, поскольку явно представляет информативную метрику, скрытую в исходной топологической характеристике, и представляет ее с точностью до долей числа переходов по сечению с линии на линию. Два мэтчера, работающие по топологии и гребневому счету независимо, позволяют организовать коллективные решающие правила, приводящие к уменьшению ошибок идентификации (хотя бы по правилу Байеса). Фактически топологическая характеристика и гребневый счет - это две различные метрики изображения (две модели), только структурированы эти метрики линиями изображения одинаково.

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

СПОСОБ ГРЕБНЕВОГО СЧЕТА НА ОСНОВЕ ТОПОЛОГИИ ДАКТИЛОСКОПИЧЕСКОГО УЗОРА
Таблица 1		Таблица 2
Номер связи	Событие	Номер особенности		Номер связи	Событие	Номер особенности
0	1110	22		0	1111	25
1	0001	21		1	1111	21
2	1110	23		2	1110	21
3	1001	24		3	0001	20
4	1111	22		4	1110	24
5	0011	21		5	1001	26
6	1111	23		6	1101	21
7	1010	24		7	0011	20
8	0010	25		8	1111	24
9	0010	21		9	1010	26
10	1010	20		10	0010	22
11	1010	26		11	0010	20
12	0011	25		12	1010	23
13	0000	-		13	1010	27
14	0000	-		14	0011	22
15	1111	27		15	0000	-
16	0001	25		16	0000	-
			17	1100	-
			18	1100	-

СПОСОБ ГРЕБНЕВОГО СЧЕТА НА ОСНОВЕ ТОПОЛОГИИ ДАКТИЛОСКОПИЧЕСКОГО УЗОРА
Таблица 3		Таблица 4
Гребневый счет	Номер особенности		Гребневый счет	Номер особенности
1	22		0	21
2	21		2	20
3,5	20		3,5	23
2	23		2	24
1,5	24		0	25
2,5	26		1,5	26
4	27		2,5	27
3	25		3	22