The idea of description (reconstruction) of fingerprints with mathematical algorithms and history of the development of this idea at Optel
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. Optel Team 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.
Wieslaw Bicz,
written in May 2003