I spent yet another weekend pouring over computer algorithms. This time, it's fingerprint extraction and identification. The whole topic came up from my discussion at work. I foolishly boasted that I could design a system that will let any of the 10-15 people use any of the 10-15 computers to log on to their user account by pressing any of their 10 fingers against a little Fingerprint Scanner. So in theory, if my boss's computer was busy, he could walk up to my computer, press his finger against the fingerprint scanner and it will automatically log him into the new business software that I'm gonna make.

So of course, now that I've told everyone it's possible, it's time to figure out how. The lazy computer programmer in me wants to spend a little money, buy something like the VeriFinger Standard SDK, hook it up to one of the cheap fingerprint scanners, let it do the scanning and recognition, write a small application to manage it all, and call it a day. It won't be cheap but it'll work pretty realiably. A lot of companies around the world have done it. The mathematician in me wants to do it all myself. It's not just the thrill of writing it on my own, it's the additional features that I can add on to it. So, if you are given the task of writing a software to do all of this from scratch, how would you go about it?

It's a known fact that every individual has absolutely unique fingerprints on each of their ten (or so) digits. If you want to design something that can let anyone use any finger to log on from any computer, you need (1) software + scanner on every computer, (2) a server that has the database of every person's every finger, and (3) some way of reliably matching a finger with the correct person no matter what computer they are on. So now we can break this whole operation into two phases. The first phase is the setup phase when we add each users's fingerprint to the database. And the second phase is application phase in which we recognize the user when they press their finger against a scanner. In either phase, a fingerprint has to be read, converted to a form that can be understood by a computer, and transferred to the server. Only difference is that in the first phase it is stored on the server and in the second, it is matched against every existing fingerprint on the server.

What we have are two different operations: Extraction and Identification/Recognition/Matching. Extraction is the process by which a fingerprint is read from the scanner and specific unique qualities about the fingerprint are extracted from the image. Identification/Recognition/Matching is simply looking up the server for other fingerprints with similar unique qualities. So how and what do we extract from the scan of a fingerprint? Look at your own index finger right now or if you don't have any fingers or fingerprints, look at this image. The first thing we notice and actually don't even realize is that the lines are actually ridges and valleys. The ridges are the thick bright protruding highs and the valleys are the thin dark low-lying crevasses. It is this pattern of ridges/valleys that is different for each person's each finger.

The first thought that comes to mind is that, if this pattern is different for everyone, just store a picture of their fingerprint and match it up against the database. Storing a picture to a database is easy. But matching up a picture of a fingerprint against a database is not. How do you match? Based on what? One idea is to just overlay the scanned fingerprint on to each of the 1000 fingerprints in the database and compare each pixel - if 95% of the pixels match, we have a match. That is how the older fingerprint matching systems worked. It works decently in identifying criminals, especially if you can wait 2 hours for it to match with 1000 fingerprints. But it's not fast enough for instant identification and poses a lot of problems, like what happens if your finger is positioned slightly to the left and/or at a 5% degree angle. It wouldn't even match against your own finger with 5% margin of error. So people have moved from the picture (raster) matching techniques on to the marker (vector) matching.

Instead of matching the whole fingerprint against 1000 others, why not extract unique characteristics of each finger and store them. This is called Minutiae Matching. Look at your finger again. If you notice carefully, you can identify many types of markers where ridges end, ridges bifurcate into two ridges, three ridges form a delta etc. If we can somehow chart this information like a graph or a map, then we can store this in a database much more easily. The information stored in the database, if read in English would seem something like this - "At the center of the fingerprint is a 'delta' and 5mm away on the right is a 'bifurcation.' 7mm below the bifurcation is an 'island' and 3mm to left of the island is another bifurcation." If this information is stored in the database for my right index finger, then when I press my right index finger against a scanner, the software asks the server to match my finger against all others who have a delta near a bifurcation and must have an island. This instantly narrows down the search only to those fingers which have deltas, islands, and bifurcations. Then it looks to see if they are positioned similar to my finger.

So now the extraction problem is just to find where the ridges end, bifurcate, or form deltas and map them on a graph. It's like saying plot Singapore, Mexico City, and Cape Town on a map. Not very difficult when you look at the big picture. The algorithm to extract markers looks at every pixel and it's neighborhood pixels. If they satisfy some special characteristics then it assigns it a marker type (delta, island etc.) and stores it in the database, relative to the position of other markers on the same finger.

Now comes the hard part - matching a finger's markers against that of the 10,000 in the database. If you think about it, it's actually an age-old problem that the ancient Greeks like Ptolemy busied themselves with - finding constellations. You must've heard of the constellation Ursa Major (The Big Dipper) or my favorite Ursa Minor (The Little Dipper). Astronomers and astrologers for centuries have stood under the night sky and identified tons of constellations simply by looking up and observing. They didn't need no fancy computers or telescopes to find The Libra in the night sky. We humans have built-in pattern-matching and pattern-recognition abilities that seem so natural to us but it is near impossible to replicate these on a computer.

Given a night sky full of stars, how do you find a constellation you are looking for? You can start by looking for small groups within the constellation. Maybe two of the stars in the constellation you are looking for, are really close to each other. So scan the whole sky for two stars very close to each other. If you find such a pair of stars then look for further signs - like is there a third star directly above or below one of them but at twice the distance. Stuff like this is what we humans are really REALLY good at. You don't even realize that you are performing one of the most difficult patterm-recognition operations right now - reading text from a computer screen. After all, OCR is big business. So is recognizing sounds (especially voice), handwriting, images, and videos - things that we so easily discern and detect.

Anyways, back to recognizing fingerprints. After the extraction process, the software will have to form a constellation with all the markings on the fingerprint. In the setup phase, this is stored on the server and in the matching phase this is what is searched for in the server. Searching a constellation of markers within each of the 1000 fingerprints in the database can be done in the following way. One of the things we need to realize is that due to the randomness of the physical act of positioning a finger on a scanner, you will almost never get two exact readings. However, the marker data in the middle of the finger will be much more accurately readable than the markings on the fringes or towards the sides of the finger. So give more importance to a bifurcation in the middle of the finger than an island at the far left - after all, it could be just a normal fully-connected ridge but the person might not have pressed the finger fully on the scanner.

My extraction method would be to start towards the middle, spiral out in a clockwise direction and note the position of every marker. Note the distance between each marker and nearby ones and store it in a cyclic data format. Now search the database for only those fingers which have similar markings in the center as there is a very high probability that center readings are accurate. Then narrow down the list to only those with similar markings near the immediate area surrounding the center. Keep narrowing down the search till you have at most 5-10 fingerprints. Then just cycle through each of them and compare each of them to the reading. Leave some margin for error, take into account the rotation and position of the markers and we should have a pretty damn reliable match. If you don't account for rotation or slight movement in position, you will almost always get an incorrect reading.

Note that throughout this discussion, we have concentrated mostly on the 1:N and not the 1:1 matching. 1:N matching means that one fingerprint is compared against N (10 or 10,000 or 10 million) fingerprints to identify the person. This is mainly used for easy identification, say to let people into a Government building. 1:1 matching is used for secure authentication - that is to verify that a person really is who they say they are, say to allow you access to your own safety deposit box in your bank. The 1:N method is geared towards faster searching and the 1:1 method is geared towards more reliable matching. It is quite difficult to design an algorithm that performs equally well in both situations for you can either do it fast or do it accurately, rarely both.

Anyways, I'm still writing algorithm for the pre-extraction phase right now. Before you extract markers, you gotta convert the true-color ridges and valleys to two color lines and gaps. Using a very simple algorithm, this is what I've come up with so far. In the next few days, I should get my own fingerprint reader and then I'll improve upon this code and do more cool things with it :) If I'm successful, then maybe I'll open-source the code for scanner and recognition and make it easy for others to use it in their applications. While I'm almost positive I won't be able to make it as good as these guys, if I make it sufficiently workable, it'll certainly make them review their pricing. These people have been doing this for years and have received national awards so I don't think I'm gonna be much of a competition (neither do I care to be). After all, I've only known about fingerprint techniques for less than 24 hours now :) But it seems like the whole scientific world has been at it for ages.

I still dunno what/how I'm gonna be setting this up for my work but all I know is that I really want to. Good thing is that I can add this feature to my work software anytime so even if it takes me months that's perfectly fine. Let's see what happens first once I have a fingerprint scanner sitting on my desk.

Add a Comment