Способ сравнения папиллярных узоров

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

 

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

Известна система для распознавания и поиска отпечатков пальцев, в которой папиллярный узор сканируется вращающейся линией вокруг центра узора и при встрече линии с особенностью фиксируется математический код, содержащий тип особенности, гребневый счет, угловую координату и расстояние (заявка РСТ №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 для особенности 1 типа окончания показано гнездо, которое образовано особенностями 2-5;

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

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

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

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

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

где d_ij - расстояние от i-й особенности до j-й особенности, α_ij - минимальный доворот вектора направления i-й особенности до вектора направления j-й особенности, ρ_ij - гребневый счет между i-й особенностью и j-й особенностью, e_ij - событие в гнезде i-й особенности для j-й особенности, n_j - номер j-й особенности. Состав гнезда можно расширить, хотя это для описания способа не принципиально. Совокупность параметров d_ij, α_ij, ρ_ij, e_ij, n_j назовем связью между i-й и j-й особенностями. Заметим, что параметры связи не зависят от ориентации и выбора центра координат.

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

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

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

Каждую свободную область описывают такими параметрами, как площадь, центр тяжести, степень вытянутости, величина изогнутости..., которые вычисляются из анализа пересекающихся окружностей (известные методы описаны в справочниках по математике, например вычисление центра тяжести). На фиг.4 центры тяжести свободных областей показаны жирными кружочками. Если для гнезда Г_k существует близлежащая свободная область с параметрами {р_i}, то для гнезда Г_l другого отпечатка следует ожидать нечто подобное (фиг.4). При отсутствии близлежащей к гнезду Г_l свободной области оценку сравнения двух гнезд занижают, умножая оценку на коэффициент меньше 1. При наличии подобной свободной области оценку сравнения двух гнезд умножают на коэффициент корреляции параметров {р_i} соответствующих свободных областей из разных узоров. При полном подобии свободных областей оценка сравнения двух гнезд не изменяется (коэффициент корреляции равен 1).

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

Выполним развитие фрагментов на сравниваемых узорах. Для этого выберем одну пару гнезд из списка пар гнезд: гнездо Г_k одного узора и соответствующий этому гнезду кандидат - гнездо Г_l другого узора. Выберем первую связь гнезда Г_k и запомним корреляцию с первой связью гнезда Г_l. На концах этих связей находятся другие гнезда, которые назовем инцидентными этим связям. Оценка инцидентной пары гнезд уже определена на предшествующем шаге. Умножим оценку инцидентной пары гнезд, скорректированную степенью подобия свободных областей сравниваемых узоров, на оценку соответствующей пары связей и получим оценку шага пути. Выполним подобные операции для всех связей гнезда Г_k, и всех связей гнезда Г_l методом перебора и выберем лучший шаг пути. Запомним оценку лучшего шага пути. Выполним переход, соответствующий лучшему шагу пути, в инцидентные гнезда: из гнезда Г_k в гнездо Г_k+1 одного отпечатка и из гнезда Г_l в гнездо Г_l+1 другого отпечатка (фиг.4), а пару гнезд Г_k и Г_l вычеркнем из дальнейшего рассмотрения.

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

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

На этом сравнение папиллярных узоров завершается.

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

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

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

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

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

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