THE IDEA OF DESCRIPTION (RECONSTRUCTION) OF FINGERPRINTS WITH MATHEMATICAL ALGORITHMS AND HISTORY OF THE DEVELOPMENT OF THIS IDEA AT OPTEL
Wiesław Bicz , written in May 2003
Before I start with the description of the idea, I must tell the story, that began about 10 years ago. This explains much. It is very difficult for me to tell, if 10 years ago, somebody else has already had the idea, that it would be possible to make a full mathematical description of fingerprints. In this time I have found no paper, describing such idea. During this time Optel worked mainly on the project, having the goal of creating a device, that would be able to recognize people measuring their fingers with the help of acoustical holography. We have already created first working prototypes of such devices and spend many days on discussions how to find a best way to compare the results and recognize fingerprints. We have studied papers, already published and discussed our ideas with a specialist, working since some years at the fingerprint recognition department of the local police, that was a member of our team during this time. We have also tried to create our own software for fingerprint recognition, that have mostly used classical approach (based on methods, proposed in this time). I suppose, that during this years many teams in the whole world have worked on such software. Our team was probably not much more skilled, than other teams, but there was one large difference: Nobody else in the world have tried to use acoustical holography for measurement of fingerprints. And although the picture of fingerprint obtained by this method is not significantly different, than picture, obtained by other methods (optical, capacitive chips, etc.), the first step - the information, that is directly seen by such device is significantly different. It is a hologram, that can be presented in the form of Fourier transform or pulse answer. And because we have used waves with the length, corresponding to the distance between the ridges of fingerprints, the structure of such pulse answer has some similarity to fingerprint itself. This is especially good to see on the following picture:
Our fingerprint technician (Adam Nowak) has even proposed to use direct comparison of such pulse answers and not to use reconstructed pictures. He has tried to find a method for this comparison, but was not able to find it. The work with such pictures has caused, that I have
had the idea, that fingerprint can be treated as a kind of structure, that may be considered as the result of interference of some waves. Team of Optel, I have tried to find a method of generation of such pattern using simulations with different wave
sources. We was able to produce very interesting patterns, some of them very similar to fingerprints. This was surely not a proper working idea, but probably not a bad way. From other point of view, it is obviously true, that fingerprint seems to be not far away
from wave pattern, that could be generated using different methods and for example found in pictures, published in books about physics.
Although I have had no evidence, that this can be possible, after such numerical experiments I was sure, that it must be possible to find an algorithm, that would allow to describe fingerprint using
small amount of parameters. This was the reason, why I have tried to convince all people working on this problem together with me. We have discussed many ideas together and with Mieczyslaw Pluta,
who began to work on finger recognition at Optel and also on reconstruction of pictures, that we have obtained from ultrasonic data. The work on this topic and our discussions have produced one
very significant result: algorithm, that allows mathematical description of minutia. He has assumed, that fingerprint can be seen as a wave pattern (periodical sinusoidal structure on the surface), that can be described using following function:
F(x,y)=cos(j(x,y))
(1)
Where j(x,y))
is a function, that describes the phase of the "wave
structure", that is "frozen" in the form of
fingerprint. This "phase describing" function has
normally two parts:
- Slowly changing part, that describe the shape of ridges,
- Quick changing part, that causes so called minutias.
This can be
mathematically formulated in following way:
j(x,y) = jg(x,y) + jo(x,y)
(2)
where the second
part describes quick changes.
Because fingerprint can be locally interpreted as a kind of a grid,
constructed from parallel lines (it is a very good known approach),
the first part of its function can be also interpreted as
information about the direction of this grid and its density.
It is probably a relatively simple job for a good mathematician to
construct a function, that describes a shape, that is similar to
the shapes found in fingerprints. This is the reason, why I will
not describe functions, that produce such shapes.
Much more interesting is the description of the second part of
fingerprint function. To do it, we will define special function Yqxz(x,y), giving each point (x,y) the
value of angle position in relation to a specially chosen middle
point (x,z). For each x and y, the function Yqxz(x,y) should be monotonically
changing from 0 to 2p around the point (x,z) and have a characteristic jump
from 0 to 2p for a chosen angle q. With certain assumptions, all
this is given for the following function:
Yqxz(x,y) = arctg ((x-x) / (y-z) )
(3)
If this function will be implemented in the finger describing
function, it will cause in the point (x,z) a phase jump, that will be
observed as minutia. Two kinds of minutias can be observed,
depending on the sign (subtraction or addition) of the second part
in the formula (2). Minutia is also defined using angle q (starting
point of the phase of formula (3)). In the following picture,
where the basic structure is build form concentric rings, the
minutia is caused by the setting (x,z)=(30,20)
If the simple function (3) will be replaced by a sum of such
functions:
N
jo(x,y) = S sk Yk (x,y) , where sk = signum (Yk ) (4)
k=1
it will be possible to describe a structure with many minutias. If
the basis function of the finger is good described, this formula
allows to implement all known minutias in any desired place. In
the following picture it can be seen, how many such points are
working on a simple arch structure:
If the simple function (3) will be replaced by a sum of such functions:
(4)
it will be possible to describe a structure with many minutias. If the basis function of the finger is good described, this formula allows to implement all known minutias in any desired place. In the following picture it can be seen, how many such points are working on a simple arch structure:
The idea described
before was also used for the software, that everybody can download
from our internet page, called "fingerprint creator". It
was also used as the basis for finger recognition software. This
software uses the idea of minutiae description in different
direction - from fingerprint data to the set of information,
describing fingerprint pattern. This software has some advantages
(it can for example work very good with relatively bad
fingerprints), but it would be surely necessary to continue the
work on this project to achieve very good performance. This was
not done, because the financing of this project was stopped.
Fingerprint creator should be treated as a demonstration, that the
idea of mathematical description can work at least in some cases.
And the limit of this idea is easily to see, too: To describe all
possible fingerprints it is necessary to find a mathematical
description of the basic structure of fingerprint, not only of
minutias. We have tried to find such description and this
considerations has caused, that I would assume, that the required
function should have probably the same structure, as the basic
function of the fingerprint: one function describing the basic
shape and the second one, describing such structures as delta end
points, centers of circular lines etc. The function of this kind
would have two stages, having similar structure. But this is only
my assumption.
Existing finger creator software can produce very large amount of
fingerprint pattern, using only a very small amount of data (exactly
10 bytes). If it would be possible (and this is what I believe,
but cannot exactly prove now), the realistic chance of storing
large amounts of fingerprints in a very small storage space (I
would assume, that not more, than 10 bytes will be necessary for
the full description of fingerprint) will occur. This is
especially interesting for people storing large amounts of such
data, but has a very important advantage for all other: it could
cause, that comparison of fingerprints will work much quicker,
that with existing algorithms, because such description allows the
creation of a kind of catalogue of fingerprint (each fingerprint
has a defined place in such catalogue, that has a number, but this
number is also a parameter for an algorithm, that allows to create
its pattern).
We was not able to continue the work on this project (I am
searching new partners for it, and it seems to be realistic, that
I will find them soon), but may be the publication of this paper
will cause, that more people will think about the possibility of
mathematical description of fingerprints and propose some new
ideas.
I assume, that mainly following work should be done if the project
of mathematical description of fingerprint should be continued:
1. Description of
the jg(x,y)
function from the formula
(2).
2. Finding a method of analysis of fingerprint pictures in the way,
that they can be described using mathematical algorithm.
3. Finding a method of sorting (finding a place in a catalogue) of
fingerprints in the way, that the comparison can be possible in
the simplest way.
I have decided to
publish this paper mainly because I think, that the idea of
mathematical description of fingerprints can be interesting for
many people working in this area and our achievements can be used
to achieve the goal of the description of all fingerprints and -
in this way - for the creation of a very concise catalog of all
existing fingerprints, that can take only a relatively small
amount of place (for example a collection of all fingerprints of
today living people together with their names could be placed on a
hard disk, that is easily available today - about 200 Gbytes).
I am sure, that the project, having the goal of creation of such
catalogue can be advantageous for all people, if they have no
reason for making their identification difficult. It can bring the
large advantage of secure identification with any kind of
automatic fingerprint reader.
I am interested in cooperation with people, interested in
developing such algorithm and hope to find in this way contact to
them.
