Archive for August, 2006

libdpfp 0.2.1 – basic image enhancement

Wednesday, August 30th, 2006

I have just released version 0.2.1 of libdpfp, a userspace library with example programs to interact with Microsoft and DigitalPersona fingerprint scanners on Linux.

This release contains code from eFinger and FVS to enhance the fingerprint images. The capture_finger_enhanced example program now produces images like the ones in this post, which is rather cool. Again, the enhancement takes a few seconds to complete, hopefully we can improve on this. Also, I think I saw an infinite loop in the thinning code, but have been unable to reproduce this.

Andrei Tchijov has done some work porting libdpfp to Mac OS X (Darwin). I say porting, only a few small changes were needed. It doesn’t work out-of-the-box on Darwin just yet due to a libusb bug, which Andrei is working on. Andrei also mumbled something about porting libdpfp to Windows, which would be rather interesting.

Download link. As usual, questions and bug reports belong on the mailing list, not in comments on my weblog.

No snakes on this plane

Sunday, August 27th, 2006

I’ve had an enjoyable first few days in the US (Boston, MA). My apartment is really nice (considerably nicer than the student places I’ve been in for the last 2 years!), plus Dave (flat mate) and Seemant + Aimee have been really helpful in terms of getting me settled in.

I’ve figured out the public transport system and ventured into the city a few times. As I don’t start working until September, I’m enjoying having the time just to wander around with a slightly alienated feeling (everyone talks funny, drives on the wrong side of the road, etc) and no real commitments as of yet.

A few things have struck me while trying to get on my feet:

  • The banking system is weird. The high street banks here seem to lack the efficiency which I’m used to back at home. And what’s this about paying monthly fees just to have a basic account? Savings accounts which offer only 0.40% interest? Having to pay to get a cheque checkbook?
  • Holes in the mobile cell phone network… Having a tri-band phone on a UK network allows me to connect to any GSM network out here, but reception of any network in my apartment is basically non-existent. Things don’t even get much better in the local town area, although it was OK in the city.
  • Lack of any decent pay-as-you-go cellphone plans — I don’t see myself using a cellphone too much if I can’t even get signal at home, but it looks like all “prepaid” phone plans really suck out here

It has also been an educational experience. I now know the value of a dime (why is a 10 cent coin smaller, thinner and lighter than a 5 cent coint!?), and discovered what a corn dog actually is (haven’t tried one yet, but this Americanism had been bugging me for a while).

On Friday (my 20th birthday) I met with Dave & Megan and friends, Seemant & Aimee, Mike Frysinger and Joshua Nichols. We ate at a nice bar in the city, which was fun. I hope we can meet up again soon, once I’ve adjusted to the timezone.

Moving soon!

Thursday, August 17th, 2006

Finally, I hold, within the grasp of my hands, a one-year US visa. It only took several months of paperwork and a 5 hour wait on the pavement outside the US embassy for a 30-second interview to get to this point.

I’m flying out on Tuesday, which is veeery soon. I’ll be living in Lexington, MA (just outside Boston).

It’s my 20th birthday on 25th August (next friday). As I won’t really know many people at that point, I’m hoping to get a few members of Gentoo’s boston conspiracy together for a meal or something, suggestions appreciated. Hopefully the worst of the jet lag will have worn off at that point.

Also hosting a joint leaving-and-nearly-birthday BBQ celebration at my house on Saturday. Hopefully it will have stopped raining by then.

libdpfp 0.2.0 released

Wednesday, August 16th, 2006

I released libdpfp 0.2.0 yesterday. This library allows you to capture images from Microsoft/DigitalPersona fingerprint scanners. Download link.

It does not yet include the more advanced image enhancement code which I wrote about recently, I will be adding that soon. The big change in this release is that it drops dependence on a kernel-side driver and having to upload firmware. libdpfp is now standalone.

Not requiring firmware avoids the potential distribution issues we had: we don’t have the rights to distribute their firmware. It is now not required because the device stores it, and even brand new devices seem to ship with the firmware already saved on the device. One reason we might need the firmware again is to disable encryption, but I’m reasonably confident we can do that without a firmware image — just waiting for someone who has a device which is encrypting images to come along so that I can test a theory.

The kernel-side driver is no longer required, all USB I/O is now done inside libdpfp itself, through libusb. This simplifies things for users quite substantially, and it’s much nicer writing drivers in userspace than in the kernel. It also means that ports to BSD and even Windows are now realistically possible (if someone contributes the code!), and means good things for users running old kernels on embedded devices.

Bug reports and questions belong on the mailing list, not in comments on this weblog entry. Thanks!

Fingerprint enhancement and recognition

Sunday, August 13th, 2006

A while ago, I posted some pretty pictures of my toe when I figured out the image format used by the Digital Persona and Microsoft fingerprint readers.

While it’s pretty cool to see your fingerprint on-screen, the real question is how do we make use of these prints? We need a way of storing fingerprints, and a way of saying “does this fingerprint equal the one we stored earlier?” From that point, we can implement fingerprint-based login and other things.

There are various open-source projects aiming to do this kind of thing, I made a list of them here. Unfortunately all of them appear to be dead projects and most of them aren’t useful at all, but I’ve made progress with one of them at least: FVS.

There are various different algorithms which can be used to compare fingerprints. I’ll try to describe the method used by FVS: minutiae detection.

A fingerprint is made up of ridges, basically just the curvy lines which you see. Ridges start and finish, and some of them split (bifurcate) into 2 other ridges. The points where ridge endings and bifurcations happen are known as minutiae. We can compare the positions and directions of the minutiae on two fingerprint images to decide whether they are equal. This is certainly throwing a lot of information away, but this method is very widely used in the fingerprint recognition world.

We start with the initial toe-print. I actually cheated by subtracting an image seen by the sensor before I scanned my toe from the toe-print, so what you can see below is slightly enhanced (clearer) than the original image.

The ridges of the fingerprint are visible above in white. The enhancement step involves finding the ridge direction and the ridge frequency. These details can then be used to apply a Gabor filter to the image, which produces a greatly enhanced version:

The above enhancement takes a few seconds on my system. This is OK for prototyping but is too slow for a real fingerprint login system, I hope we can find ways to optimise this. In addition to the Gabor filter, the image was further enhanced by binarization: all pixels are either black or white, no noise.

The ridges are now shown in black on a white background. The next step is to reduce each ridge line to a single pixel in width. This is known as thinning.

The advantage of thinning is that minutiae are now really easy to detect. We take every pixel on the image, and we ignore it if it is not a ridge (i.e. if it is white). For all the ridge pixels, we count the number of adjacent ridge pixels. If there is only one ridge pixel neighbour, we have found a ridge ending. If there are three ridge pixel neighbours, we have found a bifurcation.

Image borrowed from eFinger project report

FVS includes minutiae detection code based on the above algorithm:

The code isn’t perfect, as it detected many minutiae around the edge of the fingerprint image, where they do not exist. However it should be relatively simple to exclude those as FVS already knows about the edges of the print.

The next challenge is to compare two minutiae sets and decide how similar they are. FVS includes some code to do this, but it just crashes, and I haven’t spent much time debugging it yet. This is a difficult operation: prints of the same finger are never identical: sometimes some minutiae are not visible, they can be spaced slightly differently, and the finger might even be significantly rotated since the last print.

A project called eFinger has built a complete fingerprint recognition database. It uses FVS’s enhancement code, but ships it’s own code for thinning, minutiae detection, and minutiae set comparison. The code is not brilliant (does not consider rotation or anything like that) but should provide a good starting point.