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.

No matter what good things I say about my job, something happens right after that tops it all. So after taking me to lunch for my birthday, today my boss and buddies Brian 'n Scott at work, decided to take me out to dinner. We went to this cute little restaurant in downtown St. Petes near the ocean-front. It was a British-India style restaurant with a wide variety of dishes on the menu. For me, it was Chana Masala. For them it was Chicken Tikka, Pasta, Salad, and Chicken Burger. We talked and chilled for about two hours and topped it off with yummy deserts - Chocolate Volcano for me :)

One of the reasons I love this job is not just the atmosphere but the real work itself. Right now I have to setup our inventory with barcodes. So here's the plan. We purchased Symbol PPT 8846 barcode scanner. It's runs WinCE 4.1 on Pocket PC x86 hardware. This tiny little device has a built in scanner, wireless ethernet card, and support for Microsoft .Net Compact Framework. It used to be that if anyone wanted to program devices like barcode scanners, remote controls etc., they would need to interface directly at the low hardware levels with the devices. Not so anymore. I can write full-fledged Visual Basic.Net or Visual C# applications that will run in the tiny 32mb ram scanner and perform all the required functions smoothly.

So basically I'm gonna have to program it in VB.Net to talk to our internal web server running WAMP (Windows, Apache, MySQL, PHP) over 802.11b network using XML. Here's what will happen: Anytime the scanner scans a barcode, it is sent to the web server that process the input and sends back an XML document which will be parsed by my VB.Net software and displayed to the user for further input. So basically, I can walk around with the device and scan random barcodes of all our inventory and simply enter the physical quantity of stock and all the computer systems will be automatically updated. This is by far one of the coolest things I've ever worked with. I can barely sleep at night because I'm thinking about what I want to program the next morning. Eight hours of coding a day is simply not enough. I want more!

Last night, for the first time in my life, I was stupid enough to catch a nasty virus, Parite.A. If I run into the guy who made it, trust me, I'll kill him with my bare hands. Within 2 hours it infected over 5000 executable files that I had on my computer. EVERY GODDAMNED .EXE file was infected! Since I had a full backup of my system, thankfully, I was able to restore every file. It took me about 10 hours to finish the restore. So that's how I spent my Sunday. And tomorrow everyone's gonna be like, so what did YOU do over the weekend, and I will punch them in the eye. That is how angry I am right now.

Yes, it was my mistake that I downloaded a file and ran it without checking with an anti-virus software. However, this doesn't mean I was totally negligent. Last night I was looking for a good FTP client and was randomly downloading 9-10 files at the same time. Usually I download all the files together and then run anti-virus scanner on them and then test them out. Once a month, there's a file with a virus in it, so of course, I am always careful enough. Last night however, 9 of the 10 files downloaded and I didn't realize the 10th was still downloading. I ran the anti-virus, it said every file was clean, just after the scanner ended, the 10th file finished downloading, I noticed that's a new file, so I thought lemme run the scanner on it again. And then instead of right-click, I used the left-mouse button and my system got nuked :( Yes, stuff like this happens even to the best of us. The solution is to have a virus scanner running in the background 24/7. I dunno, that's just too much pressure on my system (no matter HOW fast the system is).

Anyways, my pc is back to it's pristine perfect condition, thanks to a very recent FULL backup of EVERY FILE :) Restore process is slow though, because I need to tell it to restore only executable files and not all other files. Oh well, thus ends another barely productive weekend.

Ya so who said money can't buy happiness? I mean come on... This Lexmark X75 printer/scanner/copier combo, Creative Inspire 4.1 surround sound system with subwoofer and remote, and this cute little keyboard certainly make me happy from deep within! Yup, just went to WalMart with my buddy Arthur and bought these goodies for about $200 total. Ya ya... that's a lotta money, but hey, a geek needs his gadgets!

And before I go, look what I found: Windows 1.0! What a long history... Hehe. Ok time to go sleepy... G'nite world!