This project produces a system that captures a user’s fingerprint and then authenticates it against a database via Ethernet communication; authentication results are displayed via two color LED's.

Introduction:

Due to the increasing need for securing data and places, the biometric authentication industry is seeing large market growth.  We decided to build a scalable, small, and efficient device that can be used to secure doorways throughout a complex.  We use a FingerPrint Cards capacitance based fingerprint scanner as our capturing device.  This data is captured through use of an ATMega32 microcontroller and stored on external SRAM while being sent through the microcontrollers USART serial port into a serial to Ethernet converter to a server computer.  This computer then performs the filtering and authentication and sends the result back over Ethernet to the microcontroller. 

There are basically three steps to matching one fingerprint against a reference fingerprint in a database.  The first step is to perform the filtering on the input fingerprint in which the goal is to enhance all features and end up with a “skeleton” image of the original fingerprint.  Step two is to take this skeleton image and find as many legitimate minutiae (ridges and bifurcations) as possible.  The last step is to compare the legitimate minutiae that were just found against the reference minutiae in the database and output the result (true or false) of the comparison.

Step One - Feature Enhancement:

           
Figure – Feature Enhancement steps of a Fingerprint

Normalization:
In this step we take the input image and divide it up into N x N squares.  In each square we find the mean and variance.  We then normalize the image according to our preferred mean and variance (100 and 100 respectively).  This equation is listed below:

Figure - Normalization Formula

Where I(I,j) is the grayscale value of the image, M0 is the sample mean, VAR0 is the local variance, and M and VAR are the preferred mean and variance.  G(i,j) is the output of this filtering for each pixel (i,j) in the input image I.

Gabor Filtering:
Gabor filters can best be thought of as a direction filter that when the orientation of the gabor filter is perpendicular to that of the ridge orientation the image is enhanced along that direction.  For example, if we applied a gabor filter of orientation directly in line with ridge orientation, the result would resemble a smudge and have very low variance; but, if we filtered with a perfectly perpendicular gabor filter the result would be a smoothed image eliminating most noise.

We apply gabor filters in increments of 10 degress between 0 and 180 degrees on each N x N square in the image.  The result of this 2D convolution is then placed back into our image for later work.  The equation for a gabor filter is listed below:

Figure - Gabor Filter Formula

The important parameters for a gabor filter are its frequency, f, it’s standard deviations in both the x and y directions and its directional strength, gamma (multiplied by the y’2 term).  The frequency, f, represents the inverse of the average number of pixels between ridge centers.  For our purposes this was f = 1/6.  The standard deviation is roughly a little less than one half of the period.  In our case this is approximately 2.67 for both x and y.  We set gamma to be equal to 1.0 (so the equation above is indicative of our final result) because aligning the gabor filter to be extremely directional results in a loss of accuracy in the edges of the N x N window.

Threshold Binarization:
In each N x N window we take the average pixel value as the threshold and if a pixel in that windowed image is less than the threshold we assign it a value of 1 (indicating ridge) or 0 (indicating valley).  The formula is listed below:

Figure - Threshold Binarization Formula

Where Nk is the number of pixels whose gray value is k, and M x N is equal to N x N.

Thinning the Image:
After we have binarized the image, we perform a thinning algorithm.  The thinning algorithm takes in an image comprised of 1’s and 0’s and reduces the collection of 1’s to a single pixel wide collection of 1’s by iterating through the entire N x N image with a window of 3 x 3 and checking to see if a point is a boundary point or not.  If it is a boundary point, it marks it for removal.  Once all points have been marked, the marked points are marked as 0’s and the process is repeated until no more points can be marked because everything is a single pixel thick.

Step Two – Minutiae Extraction:
In this project we distinguish a minutiae as one of two types, a ridge ending or a bifurcation.  We use a window of 3 x 3 to scan across the thinned image to compute a crossing number.  Depending on the value of the crossing number it identifies a point as either a ridge ending, a bifurcation, or as nothing.  The crossing number calculation and identification is indicated below:

Figure – Crossing Number Formula and Identification of Minutiae

After minutiae are identified as being possibly legitimate we attempt to delete all of the spurious minutiae.  The first class of spurious minutiae that we eliminate are those on the border and those near regions of low variance in the initial fingerprint image.  These are eliminated because often the minutiae finding algorithm will mark them as ridge endings since they stop at the border of the windowed image.  The second class of spurious minutiae are those that are very close to each other; either ridges very close to ridges, or bifurcations very close to bifurcations.  This is done because if minutiae are very close, then what most likely has happened is that the original fingerprint is of poor quality and the enhancement techniques could not fully reconstruct.  Determining of “too close” is done via a simple distance formula and a threshold of about the ridge period.

Step Three – Minutiae Comparison:
Minutiae comparison is one of the most heavily researched areas of fingerprint matching.  The primary considerations for minutiae comparison are speed and accuracy.  Speed is a tricky quantity to measure because it can be measured in so many ways.  We prefer to measure speed in complexity, or O(n), notation so that measurements are platform independent.  Accuracy is measured in terms of a false accept ratio, or FAR, and false rejection ratio, or FRR. FAR= number of false accepts/ total number of comparisons made.  FRR= number of false rejections / total number of comparisons made.  A FAR of .1% and FRR=2% are common for high security applications.

Our goal in the Minutiae Comparison stage was to create the simplest algorithm, regardless of speed, that could accurately compare a minutiae set against a database of minutiae sets.  The first step in the algorithm is to establish what information we need about the minutiae and create a structure that stores all the relevant information.  We need x,y coordinates , type of minutiae, and minutiae angle.  The minutiae angle is the angle the minutiae makes w.r.t to the ridge it lies on.  A minutiae, as explained above, is either a bifurcation or a ridge ending.

Figure - Minutiae Types

The goal of the algorithm is to find out the Transformation T that maps the Query Set, Q, to the Template set, T, with the smallest amount of error.  The transformation T can be generalized by a rotation and a x,y translation.

 Figure - Transformation Formula

The algorithm takes all minutiae points in the Query set, Q, and the template set T, and starts off by looking for possible support pairs.  A support pair is a point in Q and a point in T that could possibly be a matched point.  Support points are flagged in a quick fashion by examining the curvature of the ridges of all similar minutiae types.  This operation is O(M*N) where M is the size of the query minutiae set and N is the size of the template minutiae set.

There was also the tradeoff of using a dedicated chip for processing and filtering the fingerprint images versus using a PC to do the processing.  The disadvantages to the dedicated chip were that it would be slower, possible add in an extra ATMega32, and would add extra cost to the unit.  The benefit of a dedicated chip would be that all processing could be performed before sending of minutiae data, and thus the client side PC could possibly handle more simultaneous request.  The benefit to using a PC was significant less cost since we would already be using a PC for matching to the database, and also in a large scale application the PC’s performing the calculations would be very quick.  In the end we felt that the proper implementation would be to go the software route and perform the filtering and matching on a PC which received data from the microcontroller.

Standards:
The WIZ110SR serial to Ethernet converted conforms to all IEEE 802.3 Ethernet standards.  We also followed RS232 standards for the serial communication.

The circuit board was created first as a schematic in Eagle Cad, and was then routed in Eagle Cad’s board layout mode as a double-sided PCB.  Sunstone Circuits printed the boards and granted us a generous sponsorship, allowing us four free PCB’s.

Unfortunately, we could not afford a solder mask, which would have made soldering the LCD connector easier.  Instead, we experienced a 50% rejection ratio when soldering the LCD connector (0.5 mm pitch).  Additionally, since the board was our first revision of the circuit, there were a few design errors that had to be corrected by cutting 3 traces and soldering jumper wires on the underside of the board.

Our PCB’s are mounted on 0.25” Lexan (Polycarbonate) in order to avoid short circuits on the underside of the board and to enhance the aesthetic appeal of our project.

Figure - Custom PCB Board

Figure - Circuit Board Layout (click to enlarge)

The LCD display, keypad, and the fingerprint sensor were operated via serial peripheral interface (SPI).  The chip select on both of these were active low, so we therefore decided to use a 2 to 4 active low decoder.  This meant that we would have two bits specifying the particular SPI interface.  This bits corresponding to PORTB.4 and PORTA.7.

The ATMega32 on the main board was set as a master because it needed to serve the LCD display (slave) and fingerprint sensor (slave).  Our keypad is not an SPI device, but we configured it to run on the auxiliary ATMega32 as a slave.

The physical interconnect on the fingerprint sensor is a 10-wire FPC ribbon cable.  This cable is impossible to solder directly, so a mating connector, manufactured by Molex, was used to mount the sensor.

Our project utilized parallel SRAM to store fingerprint images quickly.  The SRAM is ~32KB, and can hold one image.  Because of the size of the SRAM, 15 address lines were needed to address each byte in memory (215 = 32KB).  Additionally, 8 data lines, and 2 control lines (OE’ and WE’), were needed.  Since there were so many pins, and we were trying to keep hardware to a minimum, we connected the least significant address bits to PORTC and the most significant address bits to PORTA.0-6.  CS’ connects to PORTD.2 and OE’ connects to PORTD.3.  SRAM operates at 5V logic levels, compatible with the master MCU.  The SRAM consumes most available pins on the ATMEGA32, so all other peripherals need to operate on the SPI port.

Figure 1 – Keypad pins

Our project needed three operating potentials: 3.3V, 5.0V, and 6.0V.  The SPI bus and the CS’ decoder uses 3.3V, the MCU, SRAM, and MAX3235 use 5.0V, and the LCD uses 6.0V for its backlight.  Therefore, three voltage regulators are needed to supply the operating voltages for the components.  Linear regulators, although inefficient, are used because they are inexpensive and produce very little noise on the supply lines.  Clearly, this creates a problem where data is being sent and received at different voltages.  A step down circuit, outlined below (three 0.6V diodes in series) performs voltage down-conversions.  Voltage up-conversions are not necessary because the 5.0V devices accept 3.3V inputs.

The full circuit schematic of our project is illustrated above.  You will notice two different pictures.  One picture is that of the port and peripheral connections in a schematic layout; the other is that of the PCB board that was designed and built for implementation of the hardware.

Our software was responsible for performing the following essential tasks – sending and receiving data through serial to Ethernet communication, saving data to SRAM, sending information to the LCD, receiving data from the fingerprint scanner, and reading keypad input.

We decided to create a verification protocol that was sequential in the sense that we do not need to interface with all of the tasks concurrently.  For this implementation we made the assumptions that (1) we do not need to read a fingerprint until a user has typed in their ID, (2) we will only write to the LCD (later implemented two LED's) when alert information has changed, (3) we will never need to listen for a byte over serial and write to a byte over serial at the same time, and (4) writing to SRAM can be performed in line with sending data over Ethernet since SRAM is not controlled via SPI.  The diagram below illustrates the general program flow that was used for handling all essential tasks:

Figure – Program Flow involving various peripherals

In order for us to take in keypad input it required that we debounce the keypad.  We used the following schema for reading input and debouncing the keypad:
We used Bruce Land’s code for determining what button the user has pressed on the keypad.  The code works by scanning the cross section of the row pins and column pins on the keypad as inputted to Port C.  It then uses a lookup table to detect which button has been pressed and records that button number in a variable.

For debouncing we also took Bruce Land’s state machine for debouncing.  This state machine has four states, NoPush, MaybePush, Pushed, and MaybeNoPush.  It sets a PushFlag to zero in every state except for the Pushed state in which PushFlag is set to one.
Since timer2 runs about every 30 millisecond and it takes 3 state executions to enter the Pushed state, this means that to break our state machine setup a user would have to press a number 11 times per second which is simply too fast for a human.  In our main execution loop we execute a conditional whenever PushFlag is set to one and based on the button number of the last press we perform an operation of either nothing (a user is entering their numeric ID) or we capture their fingerprint and authenticate (they pressed #).

We set the auxiliary ATMega32 as a slave for SPI with MISO set as an output initially.  A user would enter in their identification 7 digit number and hit asterisk when done.  When asterisk was pressed it would set a sendable Boolean and we would then send the number bytes over SPI.  The communication was as followed.  The master would continuously send a request ‘r’ and the slave would respond with either a ‘y’es or ‘n’o.  Yes indicated that asterisk was pressed and we can send over SPI the 7 digits.  A no indicated that they did not want to send their identification number yet.  On the master side, if it received a no, it would just ask again, otherwise it would listen for the 7 numbers and then start the fingerprint capturing process.  When a yes was sent on the slave side, it would set MISO as an input.  MISO would return to output when that master chip selects the auxiliary controller again and a user presses a button; this button is still recorded.  We found that we needed to do this change of MISO from output to input and back again, because before then the auxiliary SPI was interfering with the master SPI when it was chip selecting the fingerprint scanner.  This process would repeat itself after the fingerprint verification process was complete.       

For our serial to Ethernet network communication we used the serial to Ethernet converter chip WIZ110SR by Wiznet.  We configured this device to act as a server which held packets of data for us.  Since this acted as a server, on our PC side program we create a socket to connect to it’s serving port.  To send data to the WIZ110SR we use the ATMega32’s serial communication.  Every time we want to send a byte we set UDR = (byte)someData for the USART communication.  Once we have sent the number of bytes to the WIZ110SR that is equal to it’s packet size (153 in our case) the packet is sent to our PC client program.

To receive data on the ATMega32 we implement a wait loop to see when the UDR’s receive buffer is full.  Once it is full we read the data from UDR (data = UDR).  The receiving of data does not depend on packet size.  Therefore we used a system of ‘G’ood and ‘F’ail for commands that would be sent from the client PC to the microcontroller.  When the microcontroller is attempting to read in a byte and it reads in a ‘G’ it processes a successful attempt.  When it reads in a byte other than a ‘G’ it processes a failed attempt at communication.  A diagram of this communication was illustrated above.

PC Client Interface

The client interface on the PC side was written in Java. More information regarding this side of the project can be found in the appendix section.

In a system like this the timing properties of are high importance, because when someone wants access through a portal they would like it in a reasonable time.  A user will usually sacrifice the time it takes to type in the code for the authentication time.  From the time a user types in our code to the time a user is verified takes about 15 seconds.  The image capture time, includes the sending of data through Ethernet and being captured by the authenticating computer; this time is reasonable.  The image filter time is the time is the time from when the image is received to the time it has been filtered.  This will be the longest part of any authentication process as it requires heavy filtering computation.  The time it takes for us to filter on an Intel Core2Duo E6600 overclocked to 3.4GHz 2GB RAM (a fast computer) is about 5 seconds.  The last criteria is the minutia comparison time, and we found this to be anywhere from about a second to five seconds depending on the number of images in the database for a person.

For an authentication system the two parameters FAR and FRR are probably the most important.  These represent how secure the authentication is.  One would rather have FRR higher than FAR, since it is better to reject someone who belongs, rather than accept someone who shouldn’t be accessing the portal.  Both of these are proportional to filtering time.  The more exact you filter and match, the longer the filtering takes, but the lower the FAR and FRR.  There needs to be some tradeoff.  These two sets of data also depend on how many fingerprints you match to for a user.  Having a large set of reference prints will help reduce FRR because we have many images for a user to accept to.  However, with more images induces higher chances for error, and thus could raise the FAR.  Our results of both FRR and FAR being less than 10% is an acceptable result within the scope of our project.  This means that only 3 in 40 users will be granted access who shouldn't be granted access, and at the same time only 3 in 40 users will encounter frustration with failing a test when they shouldn't, and then have to try again. Depending on the level of security of who is using this device the fact that our system lets 3 in 40 improper users in may or may not be acceptable. The security of this device could further be enhanced by certain operational proceduers. One such procedure would be to have all users keep their 7 digit identification private. Our testing assumed that any other user could know any other users ID and try and fraud the system. But, if ID's were private, the error rates would go down due to the fact that it would be much more difficult to fraud the device.

The acceptance criteria number is the threshold on which we accept or reject a fingerprint. It is solely a result of the matching algorithms computations. For our test runs the value of 0.0800 was used. This value can be either hard coded into the software or dynamically set at runtime.

The filtering results of an input image are shown below.  You can notice below that we were able to reconstruct a somewhat noisy image into a very accurate binary thinned reproduction.  The only area of concern for this filtering is in the very center swirl where the filtering has trouble accepting the small radius and rapidly changing angles of orientation.  This is a product of the gabor filter.

 
Figure - The original fingerprint image (left) and the normalized image (right).
 
Figure – The gabor filtered binarized image (left) and the thinned image (right)

 
Figure – All possible minutiae indicated (left) and spurious minutiae deleted (right)

This project is able to be used by any company or industry that wants to implement a low-level security biometric authentication system for their networked building.  The final size of the board is approximately 9” x 9”, is user friendly, and only cost us about $75.  There are still a few quirks to work out before such a product would be put into final production, but the ground work is all there for large scale integration.

As far as individual people working with this project, it is very suited to a majority of people.  People who would be excluded would be those without fingerprints, and those without fingers. 

This project is also very safe to the user.  The only interaction the user has with the electronics is with the LCD, the keypad, and the fingerprint scanner.  These all protect the user from hazardous voltages or currents.  They are all insolated from a touching surface by the user.

We believe that this project turned out to be a success of its original mission.  We set out to develop a networked biometric authentication system and this is exactly what we achieved.  A user is able to be registered and stored into a database, they can then enter their id and scan their fingerprint which is then authenticated and the result is sent back locally to the microcontroller.

Our FAR and FRR were both below our desired hopes of both being less than 10%, and this is a great accomplishment.  However, we feel that given more time, research, and testing these results can be greatly improved upon. One reason for our results is that many authentication systems require that a user has 10 different basis images scanned at 500 dpi.  Our system is able to incorporate any number of basis images, but for the purpose of our testing we included 5 per user and our fingerprint scanner was also only 363 dpi.  Although there is no way to test this hypothesis, we believe that these two factors hurt our FAR and FRR ratios.
           
The speed of our authentication is more than suitable.  We believe that the duration of about 8 seconds from entering code to recieving authentication is within the realm of a proper user interface. It provides enough accuracy for the speed, and because we did not focus on software optimization on the PC side, we believe that its speed could be greatly increased in regards to algorithms and data structures; this increase in speed could possibly also lead to more time for better filtering algorithms.
           
As far as the reliability of our project goes, we feel that it is suitably reliable.  All of the math, algorithms, and processing works every time, but some of the off the shelf products we bought had their issues, and made debugging very important.  For example, our WIS110SR Ethernet to serial converter has the property of sometimes turning off unexpectedly.  However, if this were corrected the product would be almost perfectly reliable.
           
As a team we feel that we worked very well together and have created a very impressive final project which required us to interface many different SPI devices together, two microcontrollers, external memory, and we developed a communication protocol between our microcontrollers and a client PC for communication of data.  This all required a lot of background research on biometrics as well as detailed study of datasheets for our peripheral components and the microcontrollers.

Intelluctual Property Considerations

The only imaginable intellectual property violation considered is that of the fingerprint matching algorithm.  The brute-force fingerprint matching algorithm was mentioned in various texts as a simple algorithm that had moderate success in matching fingerprints.  However, in our opinion, this algorithm is more public knowledge than intellectual property because the algorithm appears in many commercial and hobbyist projects.  No single company has taken the rights or royalties on the algorithm.  Some variations and improvements on the algorithm have been posted in scientific journals, but we did not take a novel approach toward matching.  The PCB design could be considered intellectual property and could be protected under law.

Ethics, Legality, and Standards Compliance

Ethically, we could run into a conundrum where some guests don't want their fingerprint stored in a database, but would like access to a particular secure area.  Some users may not know that when they put their finger on our scanner, their fingerprint may be stored in a database, and could be subpoenaed in a court of law.  Perhaps a sign is needed above the sensor, or perhaps it is assumed that upon gaining access privileges, the user enters a contractual agreement to provide fingerprints.  Fortunately, our system is not commissioned for general public use, so any private applications or implementations should avert this ethical / legal debate.

Our project complies with all SPI / RS 232 / and Ethernet standards, as posted by the IEEE because all components are certified for use in these areas, and all circuitry for these communication protocols is implemented by reputable designers, like Atmel, MAXIM, etc, for commercial use.

Code Listings:
memory.c - The main ATMega32 source code
auxboard.c - The auxilary ATMega32 source code
constants_32.h - Header file containing ATMega32 bit definitions
fingerprintspi.h - Header file to initialize the fingerprint scanner
Java Program Listings

Figure - Fingerprint GUI

Figure - Closeup of main ATMega32 board

Figure - Closeup of auxilary ATMega32 board

Figure - Fingerprint sensor and serial to Ethernet converter

Cost Details:

Specific Tasks:
PCB Board Design - Matthew Rosoff
Circuit Layout - Matthew Rosoff
Fingerprint Sensor SPI - Matthew Rosoff
SRAM - Matthew Rosoff
Minutiae Matching - Matthew Rosoff
Keypad SPI - Peter Greczner
Filtering - Peter Greczner
Client GUI - Peter Greczner
Serial and Ethernet Communication - Peter Greczner
Website - Peter Greczner
LCD Attempted Interface - Peter Greczner

References:
Computational Algorithms for Fingerprint Recognition, Bir Bhanu and Xuejun Tan. Kluwer Academic Publishers, 2004.

Fingerprint Image Enhancement and Minutiae Extraction, Nimitha Chama. Department of Electrical and Computer Engineering - Clemson University

Binary Vision Algorithms in Java, R. Mukundan. Faculty of Information Technology

Fingerprint Matching Using gabor Filters, Muhammad Umer Munir and Dr. Muhammad Younas Javed, Colege of Electrical and Mechanical Engienering. National University of Sciences and Technology

Fingerprint Image Enhancement and Minutiae Extraction, Raymond Thai.

Characteristic Preserving Binarization for Fingerprint Image, GUI Lei, CHEN Da-hai, Li Hai, CHANG Jiang. Fourth International Conference on Image and Graphics

Learning Fingerprint Minutiae Location and Type, Salil Prabhakar, Anil K. Jain, and Sharath Pankanti.

The international congress for global science and technology -GVIP special issue on fingerprent recognition, 2007

ATMega 32 Datasheet

Epson S1D15G10 LCD Datasheet

Fujitsu MB84256A SRAM Datasheet

Fingerprint Cards FPC1011C Fingerprint Scanner Datasheet

.

~Peter Greczner, pag42@cornell.edu
~Matthew Rosoff, msr53@cornell.edu