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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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



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

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

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

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

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

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

Способ развития фрагмента можно усовершенствовать, используя известные функции Белмана в теории автоматического управления.

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

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

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

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

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