Neural Networks Project: Minutiae Classification

This page describes a collection of possible projects that qualify for the examination of the elective course Neural Networks. All projects deal with aspects of fingerprint verification.

Fingerprints and Minutiae

As fingerprints differ from person to person, they can be used for purposes of verification. Fingerprints are composed of line patterns called ridges and valleys. The picture at the right shows a small part of a fingerprint. In the picture, ridges are black (dark gray) and valleys are white (light gray). Note that pores appear as white dots on the ridges. Ridges and valleys run in parallel in most places. Sometimes a ridge ends or bifurcates (a valley bifurcates where a ridge ends and vice versa). These irregularities in the pattern are called minutiae. The locations of the minutiae are very valuable in fingerprint verification: they are the features that make it possible to distinguish one fingerprint from another. The picture below shows some minutiae in a fingerprint: bifurcations are enclosed in red squares and ridge endings in yellow ones.

Goal of This Project

The central question of this project is whether minutiae can be detected by simply inspecting small segments of a fingerprint image. The segments considered are squares of 20 by 20 pixels (an entire fingerprint image is about 300 by 300 pixels). These segments should be taken as inputs of a system to be built by you. The system's output should indicate whether or not the input segment contains a minutia. A more refined output will also tell whether a detected minutia is an ending or bifurcation.

As the projects proposed here are new and have not been carried out in the past, you should not worry too much about a successful termination. You can already obtain a good mark if you can convincingly report that you have spent 50 hours of practical work and followed a promising approach (you may conclude that it turned out not to be promising at the end).

The system to be constructed should make use of techniques that have been covered in the course. Here are some suggestions:

Make use of the multi-layer peceptron. It should take the image (or some preprocessed version of the image) as input and e.g. have two output neurons. The first becomes high when the input contains an ending, the second when it contains a bifurcation. When no minutiae are present, both outputs should be low. You are also free to choose another output encoding. You should train the network with backpropagation learning (or some other method that you take from literature).
Store the patterns in a Hopfield associative memory. Such a memory has stable states. After the storage of the training set, it can be expected that the stable states can be labeled with the type of pattern corresponding to the state. Try to investigate whether an initial pattern not stored in the memory converges to a stable state of the right type (ending, bifurcation, no minutiae).
Use a Kohonen neural network or another clustering technique. Are patterns of the same type grouped in one cluster? If so, how does the system behave for patterns not in the training set?
Use a genetic algorithm to build a classifier. One can think of a classifier as a large two-level Boolean expression, a sum of products. Assume that the expression has fixed dimensions: all product terms contain K variables, their negations or a don't care value (indicating that the variable is not part of the product), there are L product terms and the summation that generates the output performs the OR of M product terms (there is a separate summation for each output). The goal may be to maximize the number of don't cares in all products while, of course, performing the right type of classification. Try to experiment with different values for K, L and M.

The Databases

Test data with segments of different types can be downloaded through this page. The segments have been classified by visual inspection.

There are actually two sets of test data. The first set has been obtained from artificial fingerprints generated by the demo software available from the company OPTEL. These artificial fingerprints are binary valued (only black and white pixels). Segments extracted from them should be easier to classify.

The table below shows (magnified) example images of the three types of segments.

Ending	Bifurcation	Parallel lines

A data base of preclassified artificial fingerprint segments is available for downloading. Apart from the three classes mentioned, it contains a fourth class, the class of segments that contain multiple minutiae. The use of this class is optional. Note: Each segment is provided as a separate tiff file; the files have been packed by tar and gzip and can be both unpacked in a Unix/Linux environment as well as a Microsoft environment (use e.g. WinZip).

If you consider the artificial images too easy, a data base of preclassified natural fingerprint segments is available as well.

Please contact me if you think that you need a larger data base. I will try to construct a larger one.

General Remarks

Realize that the classifiers are not expected to be perfect and the errors made in classification are measure for the performance. Use half of the segments in the data base for training. How does the classifier perform for segments from the training set? How does it perform for the remaining segments, the segments of the test set?
You are allowed to reduce the problem size in order to reduce complexity. You can e.g. subsample the image in combination with averaging, fitering, etc. You can also perform any other type of preprocessing that you consider appropriate as long as the main effort of your work goes into computational intelligence techniques.
Before attempting to experiment with fingerprint fragments (whether preprocessed or not) it is wise to test your algorithms and data structures with artificial problems with much smaller input sizes.
If you use MATLAB, you can read the tiff files and obtain matrix of integers representing the image with the command imread. If you are interested, you can use a MATLAB script written by Asker Bazen to display the image (stored in a matrix) on screen. By the way, Asker is prepared to answer questions on this project in periods that I am absent.
Those that prefer other programming environments (you are free in your choice) should find their own ways to read tiff files (if you tell me, I can publish the methods here).

Last update on: Sat Feb 26 18:07:14 MET 2000 by Sabih Gerez.