On the journey to find some working fingerprint matching code for use in dpfp and future projects, several people have pointed me towards NFIS2.

NFIS2 is a set of utilities for fingerprint analysis and matching. It has been developed by NIST for DHS and the FBI, so presumably it is of a decent quality. Additionally, Andrei Tchijov tells me that it does work.

This sounds great, and to get a copy all you have to do is ask for them to send you a CDROM. The CD includes source code and documentation. The code is mostly public domain, some with BSD-style “preserve this copyright notice” licensing terms.

There is only one possible problem, the NFIS website makes the following point rather clear:

Distribution of this software is subject to U.S. export control laws.

I’m not sure what this means, so I’ve done some research. The following may be incorrect – this is just my interpretation, which I’m seeking clarification on…

The most important point is that export control laws apply to almost everything that exits the United States – regardless of origin and regardless of transportation method (mail, internet, …). I was encouraged to read this, as surely the U.S. don’t place restrictions on source code — otherwise the whole open source thing would not be happening, however:

All exports should be classified with an ECCN number. If they can be classified, certain restrictions apply — mostly that you cannot export to certain countries.

Even if you can’t be classified with an ECCN, there are still restrictions. For example, you cannot export anything to any entities listed here, people listed here, etc. I find this immensely confusing considering that this effectively means a US-based open source software mirror site is violating export control laws if someone on one of those lists happens to download some software. How is open-source even possible in the US with these kinds of restrictions in place?

Anyway, going back to the NFIS2 thing. It seems fairly redundant for them to point out that NFIS2 is covered by export control laws, when software of any type automatically is. So I ventured further and looked into the ECCN classification lists. Unfortunately, some entries do explicitly cover fingerprint systems, although I’m having trouble determining if they are talking about hardware or software (would they apply to a software-only generic fingerprint matching library distribution?). These entries restrict distribution to a number of countries (for purposes of “crime control”, etc).

I’d be extremely grateful if anyone can confirm or deny any of the above. The question I’m looking to answer is: If I get my hands on NFIS2, can I include it in an open-source project and share it with the world?

Here are some sources which I used in the above research:

• Export Control Basics from the Bureau of Industry and Security
• Collection of technical documents detailing the export regulations
• ECCN categories relating to computers (plain text version here). Search for “finger-print” in these documents to see what I’m talking about – is NFIS2 covered by these? Would my own non-NFIS fingerprint matching library be subject to these requirements, bearing in mind that I am now US-based?
• ffpis is a sourceforge project which appears to include a partial copy of old NFIS2 code. There doesn’t seem to be any consideration for the export control issues here. Is this legal distribution?

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.

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!

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.