RU2185661C2 - Method for comparing papillary patterns of fingers - Google Patents
Method for comparing papillary patterns of fingers Download PDFInfo
- Publication number
- RU2185661C2 RU2185661C2 RU2000121735A RU2000121735A RU2185661C2 RU 2185661 C2 RU2185661 C2 RU 2185661C2 RU 2000121735 A RU2000121735 A RU 2000121735A RU 2000121735 A RU2000121735 A RU 2000121735A RU 2185661 C2 RU2185661 C2 RU 2185661C2
- Authority
- RU
- Russia
- Prior art keywords
- nests
- archive
- prints
- nest
- fingerprint
- Prior art date
Links
- 238000000034 method Methods 0.000 title claims abstract description 19
- 239000012634 fragment Substances 0.000 claims abstract description 10
- 230000007704 transition Effects 0.000 claims description 3
- 230000000694 effects Effects 0.000 abstract description 2
- 239000000126 substance Substances 0.000 abstract 1
- 238000004891 communication Methods 0.000 description 3
- 230000005489 elastic deformation Effects 0.000 description 3
- 239000011159 matrix material Substances 0.000 description 2
- 238000007476 Maximum Likelihood Methods 0.000 description 1
- 230000008859 change Effects 0.000 description 1
- 230000008878 coupling Effects 0.000 description 1
- 238000010168 coupling process Methods 0.000 description 1
- 238000005859 coupling reaction Methods 0.000 description 1
- 238000006073 displacement reaction Methods 0.000 description 1
- 238000011156 evaluation Methods 0.000 description 1
Images
Landscapes
- Collating Specific Patterns (AREA)
Abstract
Description
Изобретение относится к области сравнения отпечатков пальцев по их математическому коду описания и может быть использовано для идентификации человека по отпечаткам пальцев и ладоней. The invention relates to the field of comparing fingerprints by their mathematical description code and can be used to identify a person by fingerprints and palms.
Известна система для распознавания и поиска отпечатков пальцев, в которой папиллярный узор сканируется вращающейся линией вокруг центра узора и при встрече линии с особенностью фиксируется математический код, содержащий тип особенности, гребневый счет, угловую координату и расстояние (заявка РСТ 87/01224, МПК G 06 K 9/00, опубл. 1987). A known system for recognizing and searching for fingerprints, in which a papillary pattern is scanned by a rotating line around the center of the pattern and when the line meets a feature, a mathematical code is recorded containing the feature type, crest count, angular coordinate and distance (PCT application 87/01224, IPC G 06 K 9/00, publ. 1987).
Недостатком является зависимость математического кода от порядка обхода особенностей, который нарушается при некорректном выборе системы координат или когда сканирующая линия образует малый угол с направлением папиллярных линий. Это приводит к снижению надежности идентификации отпечатков пальцев. The disadvantage is the dependence of the mathematical code on the traversal order of features, which is violated when the coordinate system is incorrectly selected or when the scanning line forms a small angle with the direction of the papillary lines. This leads to a decrease in the reliability of fingerprint identification.
Известен способ сравнения отпечатков пальцев, основанный на сетевой системе особенностей, которые описываются координатами и направлением особенностей. При сравнении двух отпечатков пальцев путем сопоставления координат и направлений особенностей формируют список пар особенностей (запросного и архивного отпечатков), затем оптимизируют координатные системы и, сравнивая узлы сетевой модели, определяют точное локальное подобие особенностей запросного и архивного отпечатков пальцев (патент США 4646352, МПК G 06 K 9/68, опубл. 1983). A known method of comparing fingerprints based on a network system of features that are described by the coordinates and direction of the features. When comparing two fingerprints by comparing the coordinates and directions of features, a list of feature pairs (request and archive fingerprints) is formed, then coordinate systems are optimized and, comparing the nodes of the network model, they determine the exact local similarity of features of the request and archive fingerprints (US patent 4646352, IPC G 06 K 9/68, publ. 1983).
Этот способ не позволяет однозначно восстановить структуру папиллярных линий по узлам сетевой модели, что показывает неполноту сетевой модели. Кроме того, результат сравнения зависит от наличия краевых особенностей, что увеличивает неопределенность сетевой модели. Неполнота и неопределенность сетевой модели снижает надежность идентификации отпечатков пальцев. This method does not allow to unambiguously restore the structure of papillary lines from the nodes of the network model, which shows the incompleteness of the network model. In addition, the comparison result depends on the presence of boundary features, which increases the uncertainty of the network model. The incompleteness and uncertainty of the network model reduces the reliability of fingerprint identification.
Наиболее близким к предлагаемому изобретению является способ сравнения папиллярных узоров пальцев, при котором в области ясного отпечатка регистрируют особенности с определением их координат, направления, типа и гребневого счета, особенности запросного и архивного отпечатков пальцев сравнивают и формируют матрицу совместности пар особенностей, из которой вычленяют наилучшую однозначную комбинацию идентичных особенностей запросного и архивного отпечатков пальцев (заявка РФ 94039018, МПК G 06 K 9/00, 9/68, опубл. 1996, БИ 25). Данный способ выбран в качестве прототипа. Closest to the proposed invention is a method of comparing papillary finger patterns, in which features are recorded in the area of a clear fingerprint with the determination of their coordinates, direction, type and comb count, features of the request and archive fingerprints are compared and a compatibility matrix of feature pairs is computed, from which the best an unambiguous combination of identical features of the request and archive fingerprints (RF application 94039018, IPC G 06 K 9/00, 9/68, publ. 1996, BI 25). This method is selected as a prototype.
При сравнении запросного и архивного отпечатков пальцев по прототипу строят дифференциальную плоскость, на которую наносят точки, координаты которых определяют как разность между характеристиками особенностей запросного и архивного отпечатков пальцев. Для идентичных отпечатков пальцев эти точки образуют компактное множество. При нарушении компактности производят первичную отбраковку архивных отпечатков и дальнейшее их детальное исследование исключают. Очевидно, что при эластичной деформации запросного отпечатка пальца компактность множества точек на дифференциальной плоскости нарушается. Кроме того, для построения дифференциальной плоскости необходимо определить центр координат запросного и архивного отпечатков пальцев. Центр координат определяет характеристики особенностей. При смещении одного из центров координат компактность множества точек на дифференциальной плоскости тоже нарушается. Таким образом деформации или смещение центров координат могут ложно забраковать идентичные отпечатки пальцев, что снижает надежность поиска. When comparing the request and archive fingerprints, a differential plane is built on the prototype, onto which points are applied, the coordinates of which are defined as the difference between the characteristics of the features of the request and archive fingerprints. For identical fingerprints, these points form a compact set. In case of violation of compactness, primary rejection of archival prints is performed and their further detailed study is excluded. Obviously, with elastic deformation of the request fingerprint, the compactness of the set of points on the differential plane is violated. In addition, to construct a differential plane, it is necessary to determine the center of coordinates of the request and archive fingerprints. The center of coordinates determines the characteristics of features. When one of the coordinate centers is shifted, the compactness of the set of points on the differential plane is also violated. Thus, deformations or a shift in the coordinate centers can falsely reject identical fingerprints, which reduces the reliability of the search.
Задачей, решаемой настоящим изобретением, является повышение надежности сравнения папиллярных узоров пальцев. The problem solved by the present invention is to increase the reliability of comparison of papillary finger patterns.
Достигается это тем, что для каждой особенности строят гнездо, сравнивают все гнезда запросного и архивного отпечатков пальцев и формируют не менее одной лучшей пары гнезд, от каждой выделенной пары гнезд развивают параллельно фрагменты запросного и архивного отпечатков пальцев методом перехода из гнезда в гнездо по пути наилучшего сравнения гнезд, накапливают оценки сравнения гнезд для каждого пути развития фрагментов и выбирают лучший путь. This is achieved by the fact that for each feature they build a nest, compare all the nests of the requested and archived fingerprints and form at least one of the best pair of nests, from each selected pair of nests, fragments of the requested and archived fingerprints are developed in parallel by the method of switching from socket to socket along the path of the best nest comparisons, accumulate nest comparison estimates for each fragment development path and choose the best path.
Рассмотрим последовательность выполняемых действий. Consider the sequence of actions performed.
Пусть каждая особенность в области ясного отпечатка нумеруется и описывается координатами, направлением в сторону увеличения числа папиллярных линий, типом и другими подобными характеристиками. Рассмотрим особенности двух типов: развлетвление и окончание (фиг.1, 2). Тогда гнездо Г1 для особенности 1 типа развлетвления, в которое входит несколько ближайших других особенностей, выбранных некоторым образом, например приоритетно вдоль линий (фиг. 3), описывается матрицей вида
где dij - расстояние от i-й особенности до j-й особенности, αij- минимальный доворот вектора направления i-й особенности до вектора направления j-й особенности, ρij- гребневый счет между i-й особенностью и j-й особенностью. Совокупность параметров dij, αij, ρij назовем связью между i-й особенностью и j-й особенностью. В общем случае количество параметров связи между двумя особенностями может быть расширено, например, топологией или другими геометрическими характеристиками. Заметим, что параметры связи не зависят от ориентации и выбора центра координат и эта независимость является основным условием включения параметра в связь. Последнее нетрудно выполнить, если параметр связи определять как разность между соответствующими характеристиками особенностей.Let each feature in the area of a clear imprint be numbered and described by coordinates, a direction in the direction of increasing the number of papillary lines, type and other similar characteristics. Consider the features of two types: fork and the end (figure 1, 2). Then the nest Г 1 for
where d ij is the distance from the i-th feature to the j-th feature, α ij is the minimum turn of the direction vector of the i-th feature to the direction vector of the j-th feature, ρ ij is the ridge count between the i-th feature and the j-th feature . The set of parameters d ij , α ij , ρ ij will be called the relationship between the i-th feature and the j-th feature. In the general case, the number of communication parameters between two features can be expanded, for example, by topology or other geometric characteristics. Note that the communication parameters do not depend on the orientation and choice of the coordinate center, and this independence is the main condition for the inclusion of the parameter in the communication. The latter is not difficult to fulfill if the coupling parameter is defined as the difference between the corresponding characteristics of the features.
Такие гнезда строят для каждой особенности запросного и архивного отпечатков пальцев. Such nests are built for each feature of the request and archive fingerprints.
Сравним гнездо Гk запросного отпечатка пальца с гнездом Гl архивного отпечатка пальца. Для этого выберем первую связь гнезда Гk и сравним со всеми связями гнезда Гl методом корреляции. Выберем наиболее похожую связь гнезда Гl, запомним результат сравнения со связью гнезда Гk, а полученную пару связей вычеркнем из дальнейшего рассмотрения. Подобные операции выполним последовательно для всех связей гнезда Гk. Суммируем эти результаты сравнения, количество которых не превышает минимального числа связей одного из гнезд. Усредненная суммарная корреляция вычлененных пар связей является оценкой сравнения двух гнезд. Способ сравнения двух гнезд можно усовершенствовать, используя метод максимального правдоподобия и метод перебора с возвратом.Compare the socket F k of the requested fingerprint with the socket F l of the archived fingerprint. To do this, we choose the first connection of the nest of G k and compare it with all the connections of the nest of G l by the correlation method. We choose the most similar connection of the socket Г l , remember the result of the comparison with the connection of the socket Г k , and delete the resulting pair of links from further consideration. We perform similar operations sequentially for all the connections of the jack Г k . We summarize these comparison results, the number of which does not exceed the minimum number of bonds of one of the nests. The averaged total correlation of isolated pairs of bonds is an estimate of the comparison of two nests. The method for comparing two nests can be improved using the maximum likelihood method and the return search method.
В результате каждое гнездо запросного отпечатка пальца имеет несколько отобранных лучших кандидатов - гнезд архивного отпечатка пальца. Эта процедура довольно медленна и ускорить ее можно с помощью петель, дельт и завитков. Так "родные" гнезда должны попадать в примерно одинаковые геометрические области на отпечатках, если гнезда привязывать к координатам и вектору направления петель, дельт и завитков. As a result, each fingerprint request nest has several selected best candidates - archival fingerprint nests. This procedure is rather slow and can be accelerated with the help of loops, deltas and curls. So "native" nests should fall into approximately the same geometric areas on the prints, if the nests are tied to the coordinates and direction vector of loops, deltas and curls.
Выполним развитие фрагмента запросного и архивного отпечатков пальцев. Для этого выберем одну пару гнезд, которой соответствует лучшая оценка гнезд: гнездо Гk запросного отпечатка пальца и соответствующий этому гнезду кандидат - гнездо Гl архивного отпечатка пальца. Выберем первую связь гнезда Гk и запомним корреляцию с первой связью гнезда Гl. На концах этих связей находятся другие гнезда, которые назовем инцидентными этим связям. Оценка инцидентной пары гнезд уже определена на предшествующем этапе. Умножим оценку инцидентной пары гнезд на оценку соответствующей пары связей и получим оценку шага пути. Выполним подобные операции для всех связей гнезда Гk и всех связей гнезда Гl методом перебора и выберем лучший шаг пути. Запомним оценку лучшего шага пути. Выполним переход, соответствующий лучшему шагу пути в инцидентные гнезда: из гнезда Гk в гнездо Гk+l запросного отпечатка пальца и из гнезда Гl в гнездо Гl+1 архивного отпечатка пальца (фиг.4), а пару гнезд Гk и Гl вычеркнем из дальнейшего рассмотрения. Последовательно выполняя переходы от одной пары гнезд к другой, построим путь, число вершин которого не превышает минимального числа особенностей запросного отпечатка пальца или архивного отпечатка пальца. Оценка этого пути есть усредненная оценка лучших шагов пути.Perform the development of a fragment of the request and archive fingerprints. To do this, we select one pair of nests that corresponds to the best rating of nests: socket G k of the requested fingerprint and the candidate corresponding to this socket - socket G l of the archive fingerprint. We choose the first connection of the nests of G k and remember the correlation with the first connection of the nests of l . At the ends of these connections are other nests, which we call incidental to these connections. The assessment of the incident pair of nests has already been determined at the previous stage. We multiply the estimate of the incident pair of nests by the estimate of the corresponding pair of links and obtain an estimate of the step of the path. We perform similar operations for all the connections of the nest Г k and all the connections of the nest Г l by brute force and choose the best step of the path. Remember the assessment of the best step of the path. Perform the transition corresponding to the best step of the path to the incident nests: from the slot Г k to the slot Г k + l of the request fingerprint and from the slot Г l to the slot Г l + 1 of the archive fingerprint (Fig. 4), and the pair of slots Г k and T l delete from further consideration. Consecutively making transitions from one pair of nests to another, we construct a path whose number of vertices does not exceed the minimum number of features of a request fingerprint or archived fingerprint. Evaluation of this path is an average assessment of the best steps of the path.
Выполним такие же операции для развития нескольких других фрагментов, начинающихся с других пар гнезд, которым соответствуют несколько лучших оценок сравнения гнезд. Из полученных нескольких путей выберем один, которому соответствует лучшая оценка пути. Это и есть результат сравнения запросного отпечатка пальца с архивным отпечатком пальца. We perform the same operations for the development of several other fragments starting with other pairs of nests, which correspond to several better estimates of nest comparison. From the obtained several paths, we choose one that corresponds to the best path estimate. This is the result of comparing the requested fingerprint with the archived fingerprint.
Способ развития фрагмента можно усовершенствовать, используя известные функции Белмана в теории автоматического управления. The fragment development method can be improved using the well-known Belman functions in the theory of automatic control.
Отметим достоинства способа сравнения папиллярных узоров пальцев. Note the advantages of the method of comparing papillary finger patterns.
Для построения связей фактически используется дифференциальная плоскость, как и в прототипе. Но в отличие от прототипа, где устанавливается единый центр координат, в предлагаемом способе центр координат каждый раз переносится в очередную особенность, встречающуюся на пути развития фрагмента. За счет того, что в гнезде особенности расположены геометрически компактнее, чем в целом на отпечатке пальца, параметры связей гнезда изменяются меньше при возникновении эластичной деформации. To build the bonds, the differential plane is actually used, as in the prototype. But unlike the prototype, where a single coordinate center is set, in the proposed method, the coordinate center is transferred each time to the next feature encountered in the development of the fragment. Due to the fact that the features in the nest are geometrically more compact than in general on the fingerprint, the parameters of the nest connections change less when elastic deformation occurs.
Далее, в предлагаемом способе используется не один, а множество центров координат, связанных с конкретными особенностями. Смещение одного из центров координат приведет к плохой корреляции всего в одной паре гнезд, что не сыграет существенной роли в общей усредненной оценке пути, если число особенностей достаточно велико (обычно более 10-14). Ясно, что влияние таких ошибок минимизируется. Further, the proposed method uses not one, but many centers of coordinates associated with specific features. The shift of one of the coordinate centers will lead to poor correlation in only one pair of nests, which will not play a significant role in the overall averaged estimate of the path if the number of features is large enough (usually more than 10-14). It is clear that the effect of such errors is minimized.
Таким образом за счет использования множества центров координат уменьшается влияние на результат сравнения запросного отпечатка пальца с архивным отпечатком пальца при эластичной деформации или смещении особенностей, что повышает надежность идентификации отпечатков пальцев. Thus, by using a plurality of coordinate centers, the influence on the result of comparing the requested fingerprint with the archived fingerprint during elastic deformation or displacement of features is reduced, which increases the reliability of fingerprint identification.
Настоящее изобретение может применяться в криминалистике, в системах предотвращения несанкционированного доступа в охраняемые помещения, при идентификации личности человека, пользующегося кредитной картой. The present invention can be used in forensics, in systems to prevent unauthorized access to secure premises, with the identification of the identity of a person using a credit card.
Claims (2)
Priority Applications (1)
Application Number | Priority Date | Filing Date | Title |
---|---|---|---|
RU2000121735A RU2185661C2 (en) | 2000-08-14 | 2000-08-14 | Method for comparing papillary patterns of fingers |
Applications Claiming Priority (1)
Application Number | Priority Date | Filing Date | Title |
---|---|---|---|
RU2000121735A RU2185661C2 (en) | 2000-08-14 | 2000-08-14 | Method for comparing papillary patterns of fingers |
Publications (2)
Publication Number | Publication Date |
---|---|
RU2185661C2 true RU2185661C2 (en) | 2002-07-20 |
RU2000121735A RU2000121735A (en) | 2002-08-10 |
Family
ID=20239228
Family Applications (1)
Application Number | Title | Priority Date | Filing Date |
---|---|---|---|
RU2000121735A RU2185661C2 (en) | 2000-08-14 | 2000-08-14 | Method for comparing papillary patterns of fingers |
Country Status (1)
Country | Link |
---|---|
RU (1) | RU2185661C2 (en) |
Cited By (4)
Publication number | Priority date | Publication date | Assignee | Title |
---|---|---|---|---|
RU2298828C1 (en) * | 2005-10-17 | 2007-05-10 | Закрытое акционерное общество "СОНДА Технолоджи" | Method for encoding imprint of papillary pattern |
RU2305317C2 (en) * | 2005-10-17 | 2007-08-27 | Закрытое акционерное общество "СОНДА Технолоджи" | Method of comparison of papillary patterns |
RU2306602C1 (en) * | 2006-02-20 | 2007-09-20 | Закрытое акционерное общество "СОНДА Технолоджи" | Device for recording papillary pattern |
RU2468429C2 (en) * | 2006-09-07 | 2012-11-27 | Стериа Биометрикс Аб | Method, device and computer software product for fingerprint matching |
Citations (5)
Publication number | Priority date | Publication date | Assignee | Title |
---|---|---|---|---|
FR2585152A1 (en) * | 1985-07-17 | 1987-01-23 | Desgorces Jean | Method of coding a fingerprint and its application to identity checking |
US4646352A (en) * | 1982-06-28 | 1987-02-24 | Nec Corporation | Method and device for matching fingerprints with precise minutia pairs selected from coarse pairs |
US4947443A (en) * | 1986-05-07 | 1990-08-07 | Costello Brendan D | Method and apparatus for verifying identity |
US5960101A (en) * | 1996-08-30 | 1999-09-28 | Printrak International, Inc. | Expert matcher fingerprint system |
US6052474A (en) * | 1995-08-30 | 2000-04-18 | Sony Corporation | Method and apparatus for collating images |
-
2000
- 2000-08-14 RU RU2000121735A patent/RU2185661C2/en active
Patent Citations (6)
Publication number | Priority date | Publication date | Assignee | Title |
---|---|---|---|---|
US4646352A (en) * | 1982-06-28 | 1987-02-24 | Nec Corporation | Method and device for matching fingerprints with precise minutia pairs selected from coarse pairs |
FR2585152A1 (en) * | 1985-07-17 | 1987-01-23 | Desgorces Jean | Method of coding a fingerprint and its application to identity checking |
US4947443A (en) * | 1986-05-07 | 1990-08-07 | Costello Brendan D | Method and apparatus for verifying identity |
US5321765A (en) * | 1986-05-07 | 1994-06-14 | Costello Brendan D | Method and apparatus for verifying identity |
US6052474A (en) * | 1995-08-30 | 2000-04-18 | Sony Corporation | Method and apparatus for collating images |
US5960101A (en) * | 1996-08-30 | 1999-09-28 | Printrak International, Inc. | Expert matcher fingerprint system |
Cited By (7)
Publication number | Priority date | Publication date | Assignee | Title |
---|---|---|---|---|
RU2298828C1 (en) * | 2005-10-17 | 2007-05-10 | Закрытое акционерное общество "СОНДА Технолоджи" | Method for encoding imprint of papillary pattern |
RU2305317C2 (en) * | 2005-10-17 | 2007-08-27 | Закрытое акционерное общество "СОНДА Технолоджи" | Method of comparison of papillary patterns |
RU2306602C1 (en) * | 2006-02-20 | 2007-09-20 | Закрытое акционерное общество "СОНДА Технолоджи" | Device for recording papillary pattern |
RU2468429C2 (en) * | 2006-09-07 | 2012-11-27 | Стериа Биометрикс Аб | Method, device and computer software product for fingerprint matching |
US8929617B2 (en) | 2006-09-07 | 2015-01-06 | Steria Biometrics Ab | Method for identifying an unknown fingerprint by generating a numeric representation through interleaving digits |
US8971595B2 (en) | 2006-09-07 | 2015-03-03 | Steria As | Method for generating interleaving digits to match fingerprints |
US8971596B2 (en) | 2006-09-07 | 2015-03-03 | Steria As | Method for identifying fingerprints through numeric representation |
Similar Documents
Publication | Publication Date | Title |
---|---|---|
EP0733240B1 (en) | Method for pairing fingerprint minutia using attributed relational graphs | |
US5974163A (en) | Fingerprint classification system | |
JP3053388B2 (en) | Fingerprint image special color correlator | |
EP1093079B1 (en) | Apparatus and method for matching fingerprint | |
US4944021A (en) | Identification system employing verification of fingerprints | |
US6961452B2 (en) | Fingerprint data synthesis method, fingerprint data synthesis apparatus and computer-readable recording medium on which fingerprint data synthesis program is recorded as well as biometric information synthesis method | |
EP1562134A2 (en) | Biometric information verifying apparatus | |
US6314197B1 (en) | Determining an alignment estimation between two (fingerprint) images | |
EP1420360B1 (en) | Apparatus, method and program for acquiring organism characteristic data, and corresponding authentication apparatus | |
US6487306B1 (en) | System and method for deriving a string-based representation of a fingerprint image | |
US5933516A (en) | Fingerprint matching by estimation of a maximum clique | |
US20070047777A1 (en) | Image collation method and apparatus and recording medium storing image collation program | |
US6091839A (en) | Fingerprint characteristic extraction apparatus as well as fingerprint classification apparatus and fingerprint verification apparatus for use with fingerprint characteristic extraction apparatus | |
JPH10177650A (en) | Device for extracting picture characteristic, device for analyzing picture characteristic, and system for collating picture | |
WO1995032482A1 (en) | Vector based topological fingerprint matching | |
EP0862131A2 (en) | A stripe pattern matching system | |
KR100291256B1 (en) | Fingerprint card preselection method and apparatus | |
RU2185661C2 (en) | Method for comparing papillary patterns of fingers | |
KR101774151B1 (en) | Method and apparatus of enhancing iris recognition security using distributed iris template storage and matching | |
JP2002163655A (en) | Personal authenticating device | |
JP2002024830A (en) | Image checking device, method and computer-readable storage medium | |
RU2054197C1 (en) | Method for encoding papillary pattern in finger- prints | |
CN116258842B (en) | Fingerprint template dynamic splicing optimization system and method | |
JP2005227933A (en) | Biometrics collation speed-increasing method | |
JP2002297549A (en) | Individual identification system and program |
Legal Events
Date | Code | Title | Description |
---|---|---|---|
PC4A | Invention patent assignment |
Effective date: 20080326 |