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.
High Level Design:
Security is becoming increasingly important in many facets of society, ranging from military, corporate world, and personal lives. One area of technology that is seeing growth is that of biometric authentication where a user is granted access to a piece of data, room, etc. via some form of biometric authentication. This market saw revenues of approximately US $3.01B in 2007 and is projected to reach US $7.41B by 2012; fingerprint authentication is expected to reach US $400M by 2010. This need for securing data and places effectively, coupled with the project market growth of the biometric industry, led us into a project where we created a system that uses fingerprint biometric authentication for a user to enter through a doorway.
To capture the fingerprint image we set the microcontroller to wait for an available character in USART. When a character becomes available, it reads it, and if it is equal to ‘G’ then it starts the image capturing. We then read in the stream from the fingerprint reader and simultaneously store the data point in SRAM and add it to the Ethernet packet for later transmission. The result of the matching is then outputted on the LED’s. Once all 30400 bytes have been sent, the microcontroller returns to waiting for another read. The logical structure is illustrated below:
Fingerprint Verification and Background Math:
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.
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:
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 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 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).
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.
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.
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.
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.
Hardware and Software Tradeoffs:
We had two options for having a user log their name into a system for verification – we could perform a Hyperterm type of method of typing the name into a console and sending that to the microcontroller, or we could use a peripheral, the keypad, and read in and debounce the data received on one of the ports. Do to the original design of our project in which we wanted to create an authentication system that was small and could easily fit on a wall next to a door, it would not be reasonable to expect a full functioning computer and keypad to be sitting right next to the door, and thus opted to go with a more hardware approach with the keypad.
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.
The WIZ110SR serial to Ethernet converted conforms to all IEEE 802.3 Ethernet standards. We also followed RS232 standards for the serial communication.
The hardware design for this project consisted of us interfacing the peripherals (sensors, memory, keypad, and LCD) with the ATMega32. Due to the complexity of these interactions we also needed to design a custom PCB board to handle this.
PCB Board Design:
Given the amount of custom hardware and interconnects, neither a standard 476 proto- board nor a perf-board would suffice for our project. A custom-made printed circuit board was our only option in order to accommodate the LCD screen and the fingerprint sensor’s FPC connector.
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.
Serial Peripheral Interface (SPI):
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 fingerprint sensor that we used was the FPC1011C by Fingerprint Cards AB. This is a capacitance based fingerprint sensor with an internal A/D converter and provides an SPI interface. The operating voltage for this sensor is 3.3 volts. Since the voltage that we are providing to our board is 5 V this required us to use a 3.3 V voltage regulator. The sensor is connected to the microcontroller via the SPI ports.
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.
|Part Name||Manufacturer||Part Number||Order number||Price||Ordered?|
|5 V reg||TI||78m05||sampled||yes|
|Serial to Ethernet||Wiznet||WIZ110SR||WIZ110SR|
|Nokia 6100Color LCD||Ebay|
For more detail: Networked Biometric Authentication Using Atmega32