ABSTRACT

of the qualification master’s work

Algorithms and Tools
for Fingerprint Search in Informational Database

The relevance of development of a subsystem of search of dactyloscopic images consists in the following: a relevance of the development of the biometric systems caused by their wide usage; usage of new and effective aids for an information retrieval search in a database, and, therefore, rise of speed of operation of whole biometric system; usage of a free DBMS – cheapness of development.

The purpose of development of subsystem of search of dactyloscopic appearances is a rev-up search of finger-print in a database due to diminishing of size of selection of records, satisfying the terms of search.

It is assumed to carry out achievement of this purpose, due to the decision of the followings tasks:
–  analysis of methods of presentation of record about a fingerprint;
–  analysis of methods of codeindexing of record about a fingerprint;
–  programmatic realization of the found methods or their combinations;
–  exposure on the basis of test selection of the most effective methods or their combinations.

♦ Class of fingerprint

Class of finger-print – it one of many signs on which finger-prints can be divided into groups. There are the different systems of classification (groupings) of finger-prints. The so-called system of classification of Henry became traditional [1]. In obedience to it all finger-prints can be divided into 5 classes, (fig. 7.1): Whorl – W, Right Loop – R, Left Loop – L, Arch – A, Tented Arch – T.

Figure 7.1 – Classes of fingerprints: a) Left Loop, b) Right Loop, c) Whorl, d) Arch, e) Tented Arch

♦ Special points

The special points are unique for every fingerprint signs, determining the points of change of structure of papilliferous lines (completion, split, digging up e.c.), orientation of papilliferous lines and coordinates in these points. Every fingerprint contains about 70 details [2].

The special points are next kinds:
    – Ending point – point, where the line of ridge is closed;
    – Bifurcation – point of divergence of lines of ridge;
    – Core – point of most curvature of ridge;
    – Delta – area, where a ridge crutches on three lines, and then they meet in one point.

There is fingerprint and it's spacial points on fig. 7.2.

Figure 7.2 – Special points of fingerprint

♦ Vector of descriptions of the special points

There is a vector of descriptions of the special points: T = {m₁, m₂, ..., m_m} , where m_i triplet vector: m = {x, y, θ} , which specifies the coordinates of x and y of the location of detail and corner of detail θ [3]. These vectors were got before (in works [4] and [5] by the multichannel approach for fingerprint classification [6], combined classifier [7], fingerprint image enhancement: algorithm [8] and using gabor filters [9]) and brought in DB.

♦ Comparison of contours of formed by the special points

As talked before, a finger-print contains the special points. Thus extreme from them form the reserved polygon (or ground). The grounds of every finger-print are unique, but on the whole they can be divided into groups. It grouping in future will take part in the construction of index which will help to carry out more rapid search, due to decrease of size of selection for a final analysis.

In order that to build a polygon, containing all special points, it is possible to take advantage of algorithm of Quickhull [10]. This algorithm sets to work from creation of quadrangle, connecting extreme points. Only points, lyings out of this quadrangle, can lie on the searched polygon and will be examined in future. Every area, lying out of quadrangle, will be recursion treated an algorithm. Treatment of overhead right corner is represented on a fig. 7.3.

Figure 7.3 – Graphic chart of work of algorithm of Quickhull
(animation: volume – 25 097 byte; size – 400х400; consists of 28 frames;
a delay between last and the first frames – 2 000 msec;
a delay between frames – 1 000 msec; quantity of recycle – continuous)

On the first step A search a point с, which is most remote from a line (a;b). on second step B determine two sets of points: on the right or on a line (a;c) and on the right or on (c;b). For two found sets first step A repeats.

If on some sublevel of recursion a set consists only of two points, a recursion is stopped, returning these two points as side of the sought after polygon. Proceeds so, while all overhead right corner is not treated. The left top, left bottom and right bottom corners are processed with an analogical method, while will not get a complete convex shape.

Now that for every finger-print we built a polygon, limiting the special points, it is possible to make an effort find signs which these polygons can be grouped on.

Within the framework of the first method of comparison of two polygons (fingers built from two imprints) it is possible to find their crossing and association. Attitude of area of crossing toward the area of association will give some coefficient of difference of areas of polygons. And than stronger this coefficient aspires to the zero, the anymore these polygons are alike on each other. If a coefficient is not exceeded by some set threshold, it is possible to consider that these polygons behave to one group, and accordingly to take away a finger-print for a detailer analysis.

Other method can be a method of comparison of form of objects with the use of morphing contours of border [11]. In this method it is suggested to compare contours, using a next mechanical model. It is considered that contours are made from a wire. Deforming a wire by tension and bend, an initial contour will be transformed in eventual. This transformation is characterized mechanical work. It is suggested to use the minimum size of such work as a measure of distinction between contours.

For determination of size of work of transformation it is suggested to use a method, allowing to define the value of minimum work of transformation for two reserved poligonal contours [12].

We will define the reserved poligonal contour as well-organized cyclic chainlet of tops C = {c₀, c₁, …, c_N}. We will consider two contours P = {p₀, p₁, …, p_N} и Q = {q₀, q₁, …, q_N}. In each of contours will fix one of tops, which will name initial.

Thus: one top of initial contour can put in accordance a few tops of eventual contour and vice versa: to a few tops of initial contour – one top of eventual; the initial top of initial contour is translated in the initial top of eventual. The example of such accordance of tops for two contours is resulted on fig. 7.4.

Figure 7.4 – Accordance of tops for two poligonal contours

Work of transformation is determined two types of transformations – tension (by a compression) and bend. Work of tension (compression) is characterized the change of distance between two nearby tops of contour during transformation. Work of bend is characterized the change of corner which is formed by three nearby tops of contour.

By minimum work on transformation of contour of P with the initial top of p₀ in the contour of Q with the initial top of q₀ will name a size, calculated on a formula (1):

where W(S) – work, proper transformation S;
Ω( (P, p⁰), (Q, q⁰) ) – set of possible transformations of contour P with the initial top of p⁰ in the contour of Q with the initial top of q⁰.

All accordances between the tops of contours of P and Q it is possible to present dimensions by a matrix (m+2)*(n+2) (taking to account that p^m+1 = p⁰, qⁿ⁺¹ = q⁰) or graph (fig. 7.5). In this case the tops of contour of P correspond vertical lines P, and to the horizontal lines are tops of Q. A point on crossing of vertical line of i and horizontal line of j corresponds the pair of tops (pⁱ, q^j).

Figure 7.5 – All accordances between the tops of contours of P and Q

Transformation can be presented as a way on this graph, beginning in a point (0,0) and closed in a point (m+1, n+1). On a fig. 7.6 the example of such presentation is resulted for transformation, represented on a fig. 7.5.

Figure 7.6 – Transformation of contour of P in Q as a way on a graph

Thus, task about finding of minimum work on transformation of contour of P with the initial top of p⁰ in the contour of Q with the initial top of q⁰ taken to the task about the search of short cut on a graph.

Minimum work on transformation of contour of P to the contour of Q is a magnitude, calculated on a formula (2):

In order that the measure of distinction was unsensible to the linear sizes, it is necessary to ration before comparison of co-ordinate of tops of contour. Thus procedure of setting of norms must not depend on position of contour in space. It is suggested to use setting of norms on the radius of minimum circle, containing a contour, thus, a method becomes steady to the change of sizes of figures and their location.

♦ Comparison of dispersions of distributing of the special points

Another method of comparison of finger-prints on the special points is comparison of dispersions of distributing of the special points round their imaginary centre of gravity. For the calculation of co-ordinates of centre of gravity will take advantage of next method [13].

We will suppose that mass is only in tops, thus every top weighs identically. In this case the co-ordinates of centre of gravity are expressed on formulas (3) and (4):

where, (X_i, Y_i) – coordinates of i top of polygon;
M_i – mass i top;
M – mass of all tops (M = M₁ + ... + M_N).

Thus, for our special case of co-ordinate of center calculated on formulas (5) and (6):

We will find distance from the center of the masses to every point on a formula (7):

These distances are the values of casual size of S, for which it is possible to calculate the expectation value and dispersion on formulas (8) and (9) accordingly [14]:

Thus, for every finger-print on his special points it is possible to calculate dispersion and use its value for comparison, grouping and search.

Analysing the methods of comparison of finger-prints resulted higher, hardness to say what for them advantages and failings, as to practical realization of these methods in this area not produced. Their efficiency will be certain in future, and it is while possible to say that these methods differ simplicity of realization and sufficient exactness.

It is assumed that in future codeindexing on the basis of these methods or their combination will give an effective increase at a search.

1. Henry Classification System
    [Electronic Resource] – Mode of access: http://en.wikipedia.org/wiki/Henry_Classification_System

2. Minutiae points – Особые точки
    [Electronic Resource] – Mode of access: http://en.wikipedia.org/wiki/Minutiae

3. D. Maltoni, D. Maio, A. K. Jain, S. Prabhakar – Handbook of fingerprint recognition – New York – 2003 – 348

4. Петрова Т.В. – Методы и алгоритмы распознавания изображений отпечатков пальцев в биометрических системах
    контроля доступа – Магистерская работа – ДонНТУ – 2008
    [Electronic Resource] – Mode of access: http://masters.donntu.ru/2008/kita/petrova/index.htm

5. Евстюничева А.В. – Автоматизированная система контроля доступа на основании распознавания отпечатков пальцев
    Магистерская работа – ДонНТУ – 2006
    [Electronic Resource] – Mode of access: http://masters.donntu.ru/2006/kita/yevstyunicheva/index.htm

6. A. K. Jain, S. Prabhakar, L. Hong – A Multichannel Approach to Fingerprint Classification –
    (Многоканальный подход к классификации отпечатков пальцев) –
    IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 21, No. 4, April 1999
    [Electronic Resource] – Mode of access: http://ieeexplore.ieee.org/iel4/34/16468/00761265.pdf

7. A. Senior – A Combination Fingerprint Classifier –
    (Комбинированный классификатор отпечатков пальцев) –
    IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 23, No. 10, October 2001
    [Electronic Resource] – Mode of access: http://ieeexplore.ieee.org/iel5/34/20643/00954606.pdf?arnumber=954606

8. L. Hong, Y. Wan, A. Jain – Fingerprint Image Enhancement: Algorithm and Performance Evaluation –
    (Улучшение изображений отпечатков пальцев: алгоритм и оценка выполнения) –
    IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 20, No. 8, August 1998
    [Electronic Resource] – Mode of access: http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=709565

9. M. U. Munir, Dr. M. Y. Javed – Fingerprint Matching using Gabor Filters –
    (Сопоставление отпечатков пальцев, основанное на фильтрах Габора) –
    National Conference on Emerging Technologies – 2004
    [Electronic Resource] – Mode of access:
    http://www.szabist.edu.pk/ncet2004/docs/session%20vii%20paper%20no%203%20(p147-151).pdf

10. QuickHull – метод построения многоугольника вокруг множества точек
     [Electronic Resource] – Mode of access: http://algolist.manual.ru/maths/geom/convhull/quickhull.php

11. Рейер И.А. – Сравнения формы объектов с использованием морфинга контуров границы
     [Electronic Resource] – Mode of access: http://www.graphicon.ru/2000/2D%20GRAPHICS/Reyer.pdf

12. T.W.Sederberg, E. Greenwood – A physically based approach to 2-D shape blending –
     Computer Graphics, Vol. 26, No. 2, 25-34, 1992
     [Electronic Resource] – Mode of access: http://portal.acm.org/citation.cfm?id=134001

13. Егоров П. – Статья «Центр тяжести»
     [Electronic Resource] – Mode of access: http://algolist.manual.ru/maths/geom/polygon/center_mass.php

14. Гмурман В.Е. – Теория вероятностей и математическая статистика – 2003 – 480

While writing the given abstract the master's work has not been completed yet. The final date of the work completed is December, 1st, 2009. The text of master's work and materials on this topic can be received from the author or her research guide after the indicated date.