Matching Algorithm (possible reimplementation?)

[szbergeron]

Let me know if this isn't the proper place for this, I'm mostly putting it here because it doesn't make as much sense quite yet to try to bug the libfprint guys about it.

Since the sensor we're dealing with seems to work based on several low resolution, low quality images, what is the general consensus on how to implement a suitable matching algorithm?

Some thoughts on a few points:

The low quality images (high noise floor with some artifacting) shouldn't be too hard to eliminate. Since a bunch of captures can be done in a short amount of time, mean averaging of pixels over 3 or so captures should be enough to improve contrast fairly drastically.

The low resolution images could be a bit of an issue. One solution would be attempts at super-resolution by setting estimates for ridge width and then tracking movement over a few frames, this would require probably quite a bit of work to implement. Another possible solution is to attempt to grab different minutia over a few frames, and directly feed a collected set of them to a pre-existing matching algorithm. I suppose a third option would be to reduce matching accuracy, but this seems like it should be a last resort.

[hmaarrfk]

Honestly, I don't think we should reimplement the wheel.

My preferred approach would be to rip code from the android operating system regarding fingerprint detection. That way, we can track their progress and feature addition.

Currently, it seems that the authentication procedure in libfprint is:

1. Ask the user to put his finger on the sensor
2. Find more than a certain threshold of minutiae
3. Ask him to do this 5 times.
4. If the user isn't frustrated after the 5th time, you can kinda assume that the minutiae are reliable.

I didn't see any checking that the minutiae were consistent between images, nor did I see any averaging happening.

Personally, I would see a good algorithm as:

1. Use multiple small image to create a large mosaic of the user's finger.
   1. These images can be acquired one by one, or
   2. You can probably use the multiple images that are acquired while the user thinks he is "pressing once". The sensor actually runs in video mode.
2. Match the user's new finger to a small region of the registered mosaic.

All of this would be theoretically done by Android for us. This might be a good read

[szbergeron]

From what I'm seeing there, AOSP implements a HAL interface that lets vendor made drivers talk to the system properly and do the matching on their own. I'm probably missing something in that doc, but it would make sense if Android wouldn't have a matching algorithm of its own just to incentivize use of TPMs for all of that by vendors.

At this point how much of libfprint are we expecting to still integrate?

[hmaarrfk]

Really? android doesn't have a stock fingerprint matching algorithm.....
That is ALOT of work to get it working robustly.

I'm sure we can find a paper by somebody at MIT or Berkeley that has done this as part of their PhD.

Personally, I like python and would advocate for using it while working out the science of it.
Later, we can think if we want to integrate with libfprint. I did most of the integration already, but got stuck at their image matching algorithm which needs full prints.

An interesting aspect is that they binarize the images. You should have a look at how they do that. It seemed to work kinda well.

[szbergeron]

How much of a performance penalty would there be from implementing it with a machine learning framework? I feel as though that could lead too accuracy improvements over time, but it wouldn't be quite as efficient as a more "programmatic" solution.

I'll definitelly look into how libfprint handles things for their algorithm, we can probably at least use some of their work for minutia recognition, then play around with a middle layer for actual fp comparison. If nothing else, we can at least take advantage of what they already implemented to properly interface with the larger OS.

I should be able to keep up with python, I'm somewhat new to the language but it isn't that difficult to grasp what is going on here at the syntax level. The science of this would also probably be easier in python because there are so many open source image matching libraries right now in it, though for a final driver it might be valid to consider something else if only to make dependencies as minimal as possible.

[hmaarrfk]

Well, you can use whatever programming framework you want. I just think that all things considered, python is pretty powerful and easy to hack.

You can try to do it with a machine learning framework. I'm sure somebody has already done it.

I guess the possibilities are endless.

I did alot of work on the libfprint side. I didn't add your fix, but yea. It really wasn't a fun library to write. It was all asynchronous, probably running in a single thread with its own scheduler.