Патент на изобретение №2331108

(54) СПОСОБ СРАВНЕНИЯ ОТПЕЧАТКОВ ПАПИЛЛЯРНЫХ УЗОРОВ

(57) Реферат:

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

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

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

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

Известен способ сравнения отпечатков пальцев на основе сетевой модели особенностей, узлы которой описываются координатами и направлением. При сопоставлении двух сетевых моделей (запросного и архивного отпечатков пальцев) формируют список похожих пар узлов моделей, затем оптимизируют координатные системы и, сравнивая узлы двух моделей, определяют степень подобия моделей (патент США №4646352, МПК G06K 9/68, опубл. 1983).

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

Известен способ сравнения папиллярных узоров пальцев, при котором в области ясного отпечатка регистрируют особенности с определением их координат, направления, типа и гребневого счета до других особенностей, особенности разных отпечатков пальцев сравнивают и формируют матрицу совместности пар особенностей, из которой вычленяют наилучшую однозначную комбинацию идентичных особенностей запросного и архивного отпечатков пальцев (заявка РФ №94039018, МПК G06K 9/00, 9/68, опубл. 1996, бюл. №25).

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

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

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

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

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

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

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

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

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

на фиг.3 для особенности типа окончания показано гнездо, которое образовано сечением от окончания и особенностями 21-26;

на фиг.4 для особенности типа разветвления показано гнездо, которое образовано сечением от разветвления и особенностями 21-26;

на фиг.5 показаны пути параллельного развития фрагментов по гнездам из запросного и архивного отпечатков;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1100 – связь по линии замыкается.

С событием-числом, детектированным на связи, записывается номер особенности, породившей событие, а сами события-числа жестко привязываются к номеру связи (фиг.3, 4). Для каждой особенности перечень событий-чисел и соответствующих номеров особенностей сводится в гнездо (табл.1, 2). По событию-числу вычисляется состояние связи: ноль, если угол направления особенности ориентирован по ходу по связи; единица, если угол направления особенности ориентирован навстречу ходу по связи (табл.1, 2).

Таким образом, каждое гнездо описывается матрицей, в которой на основе i-й связи синтезируется i-я строка вида

где d_i – расстояние от центра сечения до особенности на i-й связи, _i – минимальный доворот угла направления особенности, образующей гнездо, до угла направления особенности по i-й связи, е_i – событие на i-й связи, _i – состояние i-й связи, _i{0,1}, n_i – номер особенности на i-й связи. Заметим, что параметры связи (строки матрицы) не зависят от ориентации и выбора центра координат.

Такие гнезда строятся для каждой особенности запросного и архивного отпечатков.

Сравнение гнезд особенностей запросного и архивного отпечатков производится в два этапа.

На первом этапе сравниваются состояния гнезда Г_k запросного отпечатка с состояниями гнезда Г_l архивного отпечатка (фиг.5) на одинаково нумерованных связях и определяется число несовпадающих состояний в гнездах Г_k и Г_l. Среди всех сравнений гнезд особенностей запросного и архивного отпечатков выделяются пары гнезд с минимальными (в смысле лучшими) оценками, количество которых обычно более одного. Такие оценки можно произвести машинной операцией исключающее или.

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

Далее выполняется развитие фрагментов. Для этого выбирается одна пара гнезд из выделенных на втором этапе пар гнезд: гнездо Г_k запросного отпечатка и соответствующий этому гнезду кандидат – гнездо Г_l архивного отпечатка. Для особенностей, номера которых указаны в гнездах Г_k и Г_l на одинаково нумерованных связях, оценивается степень похожести их гнезд по аналогии с оценками первого и второго этапов. Среди всех таких оценок на одинаково нумерованных связях выбирается лучшая оценка, которой соответствует пара особенностей с гнездами Г_k+1 и Г_l+1 (фиг.5). Особенность Г_k инцидентна особенности Г_k+1, а особенность Г_l инцидентна особенности Г_l+1. Оценка пар гнезд Г_k+1 и Г_l+1 соответствует оценке шага пути. Пару гнезд Г_k и Г_l вычеркнем из дальнейшего рассмотрения при развитии пути. Далее по аналогии оценим шаг пути из гнезд Г_k+1 и Г_l+1 в гнезда Г_k+2 и Г_l+2. Последовательно выполняя переходы от одной пары гнезд к другой, построим путь, число вершин которого не превышает минимального числа особенностей одного из отпечатков. Это и есть развитие фрагментов, начинающихся со стартовых выделенных гнезд Г_k и Г_l, а весь путь оценивается как сумма оценок шагов пути.

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

На этом сравнение отпечатков завершается.

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

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

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

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

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

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

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

РИСУНКИ