fastest way to match fingerprints?

I am trying to check whether a fingerprint exists/matches in a huge collection of fingerprints (100,00开发者_高级运维0 fingerprints). It will take more time to search for matches sequentially. is there any better way to search for match? is it possible to organize the fingerprints in a binary tree structure so that the number of comparisons can be reduced? if yes how can we do it? it would be helpful if the answers are in Java perspective.

edit:

I have all the fingerprints as .gif images. how can i convert the finger print images into data?

Thanks.

1) You need to use Wavelet compression algorithm to encode the fingerprint in sequence of wavelet compression parameters:

0, -1, 2.4, 5.6.7.7, 32.-1.5, e.t.c.

2) You need to define match function, which will find some similarities, there are two options:

-the geometry approach (compare qudrants to qudrants, all field are spaced in continuous blocks by some space algorithm)

Pros:

hardware accelerated (SSE) pixel matching algorithm, normalization all fingerprints to a standart basis using affine transformation, f.e. to square 512x512 px

Cons:

Hight sensitivity in fingerprint quality (if a part of searched fingerprint is omittet totally)

-the topology approach (the connectivity of lines, arcs, the breakpoints, mutual positioning each other)

Pros:

Low sensibility to angle, position, and quality of fingerprint, can use the original image scale and direction;

Cons:

Low speed of analysis, highly dependent upon quality of an classification function,

3) You need to define some sort of a genetic algorithm to train the evaluate function on a known set of fingerprints

You knowledge system will be able to find fingerprints by the given sample, not known by the system, but trained to find some particular differences/matches, raises the probability of a successful search, lovering the probability of false matches upon the search.

This is not my field of expertise (I'm a web developer), but I think you should look into neural networks. I downloaded some demo code once and did some experimenting with character recognition. It was amazing to see how the neural network that I had setup could recognize characters that I drew on the screen. But before it could do this, it first had to learn (backpropagation learning).

Here's a slideshow that provides an outline: http://www.slideshare.net/alessandrobaffa/fingerprints-recognition-using-neural-networks

The last slide contains further references.

Good luck!

/Thomas Kahn

You can't just do some kind of image comparison - there are specific ways to analyze and store fingerprint information already established which, for example, take into account the quality of the lifted/scanned fingerprint and that of the stored fingerprint data.

I googled for fingerprint encoding standard and came up with several interesting results, including the Encyclopedia of Biometrics which mentions "quality in various fingerprint encoding standards", and an article talking about the FBI image coding standard (among other things)

I know that this question was asked 4 years ago, however many individuals are viewing it and for the viewers I think my response might be helpful.

There are a few questions posed:- 1)Is there any way to search for a fingerprint matching as fast as possible for large scale databases?

Ans: Yes - Before for a matching a fingerprint, there is an important step you are missing. This process is fingerprint classification, which is broken down into exclusive classification and continuous classification. Exclusive classification is easier to implement, since you identify a pattern of the fingerprint, known as a class and compare it to only the fingerprints in the database that are of the same class. This is what done to speed up fingerprint matching.

The link created by Peter kovesi below provides code for orientation field and minutia extraction for matching:- http://www.csse.uwa.edu.au/~pk/research/matlabfns/#fingerprints Singular point detection and orientation fields aids in identifying classes. It can be found on the link.

2)How can one convert the finger print images into data? Ans: Ok, it doesn't matter what format the image is, I use tiff. You need to know that fingerprints are made up of ridges and valleys. Ridges are represented by the darker line. You need to apply something called ridge segmentation to discard the background and extract only the ridges. This is stored in a mask.

3) "the existing image and the image that is scanned wont be exactly similar. that's my problem"

Ans: Is it affected by noise, rotation, translation etc. Reducing noise, use enhancement techniques. For rotation, use reference points and align fingerprints.

I know this is a brief overview, however I hope that it points your'll in the right direction. Good luck!

I can't comment on the fully-DIY best approach, but I do have a lot of field expertise in this area. All large (expensive!) commercial products have 2 or more algorithms to do fingerprint matching on larger datasets. There are some that use fingerprint classes (loop, whorl etc) to do some pre-filtering, but in general fingerprints do not index very well, you'll have to brute force it in an intelligent way. That is where the multiple algorithms come into play.

There are a few classes of algorithms that can do very fast fingerprint compares (ridge shape) but are highly susceptible to errors so are not by themselves accurate enough to do a sane identification on reasonably sized databases. So those algorithms are typically deployed as first stage. If the algorithm is in any doubt, it passes to the next stage. This could be some 'mid-class' algorithm, e.g. spectral minutiae or a 'slow&accurate' algorith, e.g. something that actually compares all minutiae. The net effect is that the secondary stages typically correct for most of the false-accepts of the first stage. The only unrecoverable loss is the false rejects in the first (and second) stage. Depending on the application domain, this can be negligible or pretty high. It's a trade-off between accuracy and performance. In our own test environment we have seen speeds over 100.000.000 fingerprints compares per second in this way on a single (beefy) desktop, solving the original problem in ~1ms. It is however a complex, expensive and very specialist piece of software.

Fingerprint matching, if you want accuracy is best done using the tried and true methods that just about all automated fingerprint matching algorithm use.

The extract minutia points and store their location and other data in a template and then use statistical analysis of relative positioning of the minutia data within two templates to calculate a score of how closely the two templates match.

Using this technique often requires taking into consideration things like differences in the rotation and area of the finger as they were placed on the fingerprint scanner for each impression.

Biometric algorithms are not perfect and there performance is measured by their False Accept Rate (FAR) and their False Reject Rate (FRR). These two measures are inversely related to each other, meaning that as you increase security (decrease FAR) you increase the FRR.