Finger Print

worked Biometric Authentication

er Greczner tthew Rosoff

RODUCTION DESIGN HARDWARE SOFTWARE RESULTS CONCLUSIONS APPENDIX

s project produces a system that captures a user’s fingerprint and then authenticates it ag mmunication; authentication results are displayed via two color LED's.

troduction:

e to the increasing need for securing data and places, the biometric authentication industry is seeing l d a scalable, small, and efficient device that can be used to secure doorways throughout a complex. acitance based fingerprint scanner as our capturing device. This data is captured through use of an A external SRAM while being sent through the microcontrollers USART serial port into a serial to Etherne s computer then performs the filtering and authentication and sends the result back over Ethernet to t

gh Level Design:

tionale:

urity is becoming increasingly important in many facets of society, ranging from military, corporate world, and personal lives. O of biometric authentication where a user is granted access to a piece of data, room, etc. via some form of biometric authenticatio $3.01B in 2007 and is projected to reach US $7.41B by 2012; fingerprint authentication is expected to reach US $400M by 2010 ctively, coupled with the project market growth of the biometric industry, led us into a project where we created a system that us to enter through a doorway.

ngerprint Capturing:

capture the fingerprint image we set the microcontroller to wait for an available character in USART. W eads it, and if it is equal to ‘G’ then it starts the image capturing. We then read in the stream from the ultaneously store the data point in SRAM and add it to the Ethernet packet for later transmission. The putted on the LED's. Once all 30400 bytes have been sent, the microcontroller returns to waiting for a strated below:

Figure – Logical Structure of Fingerprint Capturing Process

ngerprint Verification and Background Math:

ere are basically three steps to matching one fingerprint against a reference fingerprint in a database. ering on the input fingerprint in which the goal is to enhance all features and end up with a “skeleton” p two is to take this skeleton image and find as many legitimate minutiae (ridges and bifurcations) as legitimate minutiae that were just found against the reference minutiae in the database and output th mparison. ep One - Feature Enhancement:

Figure – Feature Enhancement steps of a Fingerprint malization: his step we take the input image and divide it up into N x N squares. In each square we find the mean image according to our preferred mean and variance (100 and 100 respectively). This equation is list

Figure - Normalization Formula

ere I(I,j) is the grayscale value of the image, M0 is the sample mean, VAR0 is the local variance, and M iance. G(i,j) is the output of this filtering for each pixel (i,j) in the input image I. bor Filtering: bor filters can best be thought of as a direction filter that when the orientation of the gabor filter is per entation the image is enhanced along that direction. For example, if we applied a gabor filter of orient entation, the result would resemble a smudge and have very low variance; but, if we filtered with a per ult would be a smoothed image eliminating most noise.

apply gabor filters in increments of 10 degress between 0 and 180 degrees on each N x N square in th volution is then placed back into our image for later work. The equation for a gabor filter is listed belo

Figure - Gabor Filter Formula

e important parameters for a gabor filter are its frequency, f, it’s standard deviations in both the x and ength, gamma (multiplied by the y’2 term). The frequency, f, represents the inverse of the average nu ters. For our purposes this was f = 1/6. The standard deviation is roughly a little less than one half of proximately 2.67 for both x and y. We set gamma to be equal to 1.0 (so the equation above is indicati ning the gabor filter to be extremely directional results in a loss of accuracy in the edges of the N x N eshold Binarization: each N x N window we take the average pixel value as the threshold and if a pixel in that windowed im ign it a value of 1 (indicating ridge) or 0 (indicating valley). The formula is listed below:

Figure - Threshold Binarization Formula

ere Nk is the number of pixels whose gray value is k, and M x N is equal to N x N. nning the Image: er we have binarized the image, we perform a thinning algorithm. The thinning algorithm takes in an i uces the collection of 1’s to a single pixel wide collection of 1’s by iterating through the entire N x N im cking to see if a point is a boundary point or not. If it is a boundary point, it marks it for removal. Onc rked points are marked as 0’s and the process is repeated until no more points can be marked becaus ep Two – Minutiae Extraction: his project we distinguish a minutiae as one of two types, a ridge ending or a bifurcation. We use a wi nned image to compute a crossing number. Depending on the value of the crossing number it identifie urcation, or as nothing. The crossing number calculation and identification is indicated below:

Figure – Crossing Number Formula and Identification of Minutiae er minutiae are identified as being possibly legitimate we attempt to delete all of the spurious minutiae t we eliminate are those on the border and those near regions of low variance in the initial fingerprint ause often the minutiae finding algorithm will mark them as ridge endings since they stop at the bord ond class of spurious minutiae are those that are very close to each other; either ridges very close to urcations. This is done because if minutiae are very close, then what most likely has happened is that ality and the enhancement techniques could not fully reconstruct. Determining of “too close” is done v eshold of about the ridge period. ep Three – Minutiae Comparison: utiae comparison is one of the most heavily researched areas of fingerprint matching. The primary co speed and accuracy. Speed is a tricky quantity to measure because it can be measured in so many w mplexity, or O(n), notation so that measurements are platform independent. Accuracy is measured in d false rejection ratio, or FRR. FAR= number of false accepts/ total number of comparisons made. FRR mber of comparisons made. A FAR of .1% and FRR=2% are common for high security applications.

goal in the Minutiae Comparison stage was to create the simplest algorithm, regardless of speed, tha nutiae set against a database of minutiae sets. The first step in the algorithm is to establish what infor d create a structure that stores all the relevant information. We need x,y coordinates , type of minutia gle is the angle the minutiae makes w.r.t to the ridge it lies on. A minutiae, as explained above, is eith

Figure - Minutiae Types e goal of the algorithm is to find out the Transformation T that maps the Query Set, Q, to the Template or. The transformation T can be generalized by a rotation and a x,y translation. Figure - Transformation Formula

e algorithm takes all minutiae points in the Query set, Q, and the template set T, and starts off by looki port pair is a point in Q and a point in T that could possibly be a matched point. Support points are fla curvature of the ridges of all similar minutiae types. This operation is O(M*N) where M is the size of t e of the template minutiae set.

rdware and Software Tradeoffs:

had two options for having a user log their name into a system for verification – we could perform a Hyperterm type of method o to the microcontroller, or we could use a peripheral, the keypad, and read in and debounce the data received on one of the ports. ch 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 reaso keypad to be sitting right next to the door, and thus opted to go with a more hardware approach with the keypad. ere was also the tradeoff of using a dedicated chip for processing and filtering the fingerprint images v cessing. The disadvantages to the dedicated chip were that it would be slower, possible add in an ext t to the unit. The benefit of a dedicated chip would be that all processing could be performed before s client side PC could possibly handle more simultaneous request. The benefit to using a PC was signifi using a PC for matching to the database, and also in a large scale application the PC’s performing the end we felt that the proper implementation would be to go the software route and perform the filterin eived data from the microcontroller. ndards: e WIZ110SR serial to Ethernet converted conforms to all IEEE 802.3 Ethernet standards. We also follow mmunication.

ardware Design:

hardware design for this project consisted of us interfacing the peripherals (sensors, memory, keypad, and LCD) with the ATMe actions we also needed to design a custom PCB board to handle this.

B Board Design:

en the amount of custom hardware and interconnects, neither a standard 476 proto- board nor a perf-board would suffice for our our only option in order to accommodate the LCD screen and the fingerprint sensor’s FPC connector. e circuit board was created first as a schematic in Eagle Cad, and was then routed in Eagle Cad’s board nstone Circuits printed the boards and granted us a generous sponsorship, allowing us four free PCB’s. ortunately, we could not afford a solder mask, which would have made soldering the LCD connector e ection ratio when soldering the LCD connector (0.5 mm pitch). Additionally, since the board was our fir design errors that had to be corrected by cutting 3 traces and soldering jumper wires on the undersid PCB’s are mounted on 0.25” Lexan (Polycarbonate) in order to avoid short circuits on the underside o thetic appeal of our project.

Figure - Custom PCB Board

Figure - Circuit Board Layout (click to enlarge)

rial Peripheral Interface (SPI):

e LCD display, keypad, and the fingerprint sensor were operated via serial peripheral interface (SPI). T ive low, so we therefore decided to use a 2 to 4 active low decoder. This meant that we would have tw

erface. This bits corresponding to PORTB.4 and PORTA.7.

e ATMega32 on the main board was set as a master because it needed to serve the LCD display (slave pad is not an SPI device, but we configured it to run on the auxiliary ATMega32 as a slave.

ngerprint Sensor:

fingerprint sensor that we used was the FPC1011C by Fingerprint Cards AB. This is a capacitance based fingerprint sensor with face. 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 onnected to the microcontroller via the SPI ports. e physical interconnect on the fingerprint sensor is a 10-wire FPC ribbon cable. This cable is impossible nector, manufactured by Molex, was used to mount the sensor.

AM:

project utilized parallel SRAM to store fingerprint images quickly. The SRAM is ~32KB, and can hold o AM, 15 address lines were needed to address each byte in memory (215 = 32KB). Additionally, 8 data ’), were needed. Since there were so many pins, and we were trying to keep hardware to a minimum, dress bits to PORTC and the most significant address bits to PORTA.0-6. CS’ connects to PORTD.2 and erates at 5V logic levels, compatible with the master MCU. The SRAM consumes most available pins on ipherals need to operate on the SPI port.

ypad:

C was used to handle our alpha-numeric keypad. The keypad had 9 pins, but only pins 1 – 8 were needed. The pinout was C.0 Keypad used the Auxillary ATMega32 SPI interface to send its data to the main ATMega32. This SPI was configured as a slav

Figure 1 – Keypad pins

D:

LCD screen was also interfaced with via SPI protocol. We used an EPSON S1D15G10 color LCD display. When using this di ng communication, with SS active low, MOSI, and SCK acting as outputs. We did not require MISO to be an input because no lay.

ltage Regulators

ice MEGA32 (master)

Operating Voltage 5.0V

Logic/ Communication Voltage 5.0V output, accepts 3.3 V in 3.3V I/O 3.3V I/O 5.0V I/O 3.3V I/O 3.3V I/O 5.0V

Voltage Translator Required Yes

gerprint Scanner 3.3V Yes D 3.3V, 6.0V Yes AM 5.0V No MEGA32 (slave) 3.3V Yes Decoder 3.3V Yes X3235 Serial Voltage 5.0V No nverter project needed three operating potentials: 3.3V, 5.0V, and 6.0V. The SPI bus and the CS’ decoder us X3235 use 5.0V, and the LCD uses 6.0V for its backlight. Therefore, three voltage regulators are need the components. Linear regulators, although inefficient, are used because they are inexpensive and p s. Clearly, this creates a problem where data is being sent and received at different voltages. A step V diodes in series) performs voltage down-conversions. Voltage up-conversions are not necessary bec uts.

rial and Ethernet Communication:

used the WIZ110SR serial to Ethernet converter to handle our Ethernet an serial communications. There was no hardware desig did need set the parameters for the ATMega32’s USART communication, as well as connect their pins appropriately to the serial B board, and the parameters were set via software. e full circuit schematic of our project is illustrated above. You will notice two different pictures. One pi ipheral connections in a schematic layout; the other is that of the PCB board that was designed and bu dware.

ocks:

4.7456 MHz crystal provides the master MCU with a clock. This XTAL is unique because it provides the USART with a clock t r. The clock on the auxillary board was 8 MHz.

mers and Interrupts:

also had to use timer2 on the ATMega32 as a timer for controlling the debouncing of our Keypad. We set timer2 to a prescaler o

TIM2_COMP interrupt. This interrupt would be executed a little under every millisecond (250 / (8 MHz / 32) = 0.001 seconds = 0 and executing it’s debouncing task every time the counter reaches 30 this allowed us to debounce once every 30.0 ms, or about an can punch in their keys.

oftware Design:

software was responsible for performing the following essential tasks – sending and receiving data th mmunication, saving data to SRAM, sending information to the LCD, receiving data from the fingerprint

decided to create a verification protocol that was sequential in the sense that we do not need to inter currently. For this implementation we made the assumptions that (1) we do not need to read a finger (2) we will only write to the LCD (later implemented two LED's) when alert information has changed, (3 e over serial and write to a byte over serial at the same time, and (4) writing to SRAM can be performe ernet since SRAM is not controlled via SPI. The diagram below illustrates the general program flow tha ks:

Figure – Program Flow involving various peripherals

ndling Keypad Input:

order for us to take in keypad input it required that we debounce the keypad. We used the following sc bouncing the keypad: used Bruce Land’s code for determining what button the user has pressed on the keypad. The code w row pins and column pins on the keypad as inputted to Port C. It then uses a lookup table to detect w ords that button number in a variable.

debouncing we also took Bruce Land’s state machine for debouncing. This state machine has four sta d MaybeNoPush. It sets a PushFlag to zero in every state except for the Pushed state in which PushFla ce timer2 runs about every 30 millisecond and it takes 3 state executions to enter the Pushed state, th chine setup a user would have to press a number 11 times per second which is simply too fast for a hu cute a conditional whenever PushFlag is set to one and based on the button number of the last press hing (a user is entering their numeric ID) or we capture their fingerprint and authenticate (they presse

set the auxiliary ATMega32 as a slave for SPI with MISO set as an output initially. A user would enter d hit asterisk when done. When asterisk was pressed it would set a sendable Boolean and we would th e communication was as followed. The master would continuously send a request ‘r’ and the slave wou o. Yes indicated that asterisk was pressed and we can send over SPI the 7 digits. A no indicated that t ntification number yet. On the master side, if it received a no, it would just ask again, otherwise it wou rt the fingerprint capturing process. When a yes was sent on the slave side, it would set MISO as an in en that master chip selects the auxiliary controller again and a user presses a button; this button is sti eded to do this change of MISO from output to input and back again, because before then the auxiliary when it was chip selecting the fingerprint scanner. This process would repeat itself after the fingerpri mplete.

iting to the LCD:

were never successfully able to write to the LCD. The hardware was implemented, but the SPI interface for the LCD proved dif ngs issued to the LCD, or the LCD could have been broken. We do not believe that it was an SPI issue because SPI successfully ner.

iting to SRAM:

chronous Random Accessed Memory, or SRAM, is a fast and simple way to expand a microcontroller's memory space. The SRA K board. It has 15 address lines, 8 data lines, OE' and WE' lines. To store data, data is placed on the data bus, the address is load , the address is loaded, the OE' line is strobed low, and data is sent back the MCU on the data bus. Because SRAM requires 25 d bit daunting at times. The address is stored in two sequential registers as an int using the pragma –regalloc. There are two poin ing these bytes onto the 15 address lines can be done in a single operation. The data is trickier because the low order nibble is p ed on D4-D7. To perform this operation, PORTD=(PORTD&0x0F)|(data&0xF0). This preserves the low order nibble on PORT ortunately, placing the data takes 8 cycles, placing the address takes 2 cycles, and strobing the appropriate control lines takes 2 c This is significantly slower than the approximate 100 ns read/write time for SRAM, so the code is well within the timing parame

rial to Ethernet Network Communication:

our serial to Ethernet network communication we used the serial to Ethernet converter chip WIZ110SR vice to act as a server which held packets of data for us. Since this acted as a server, on our PC side p t’s serving port. To send data to the WIZ110SR we use the ATMega32’s serial communication. Every R = (byte)someData for the USART communication. Once we have sent the number of bytes to the W e (153 in our case) the packet is sent to our PC client program. receive data on the ATMega32 we implement a wait loop to see when the UDR’s receive buffer is full. R (data = UDR). The receiving of data does not depend on packet size. Therefore we used a system o uld be sent from the client PC to the microcontroller. When the microcontroller is attempting to read in cesses a successful attempt. When it reads in a byte other than a ‘G’ it processes a failed attempt at mmunication was illustrated above.

Client Interface

e client interface on the PC side was written in Java. More information regarding this side of the project tion.

esults and Analysis:

following table is a list of parameters and corresponding results that are important to our authentication system.

Result ing Properties Image Capture Time 1.375 seconds Image Filter Time 4.500 seconds Compare Time 1.365 seconds Total Time 7.240 seconds a system like this the timing properties of are high importance, because when someone wants access t sonable time. A user will usually sacrifice the time it takes to type in the code for the authentication t code to the time a user is verified takes about 15 seconds. The image capture time, includes the sen ng captured by the authenticating computer; this time is reasonable. The image filter time is the time eived to the time it has been filtered. This will be the longest part of any authentication process as it r e time it takes for us to filter on an Intel Core2Duo E6600 overclocked to 3.4GHz 2GB RAM (a fast comp eria is the minutia comparison time, and we found this to be anywhere from about a second to five se ages in the database for a person. Performance Properties Result FAR (False Acceptance Ratio) 7.5% FRR (False Rejection Ratio) 7.5% Basis Images 5

Dots per Inch (dpi) 363 Tests Run 80 Acceptance Criteria 0.0800 an authentication system the two parameters FAR and FRR are probably the most important. These r hentication is. One would rather have FRR higher than FAR, since it is better to reject someone who b o shouldn’t be accessing the portal. Both of these are proportional to filtering time. The more exact y ering takes, but the lower the FAR and FRR. There needs to be some tradeoff. These two sets of data gerprints you match to for a user. Having a large set of reference prints will help reduce FRR because ept to. However, with more images induces higher chances for error, and thus could raise the FAR. O s than 10% is an acceptable result within the scope of our project. This means that only 3 in 40 users granted access, and at the same time only 3 in 40 users will encounter frustration with failing a test w again. Depending on the level of security of who is using this device the fact that our system lets 3 in acceptable. The security of this device could further be enhanced by certain operational proceduers. O users keep their 7 digit identification private. Our testing assumed that any other user could know any tem. But, if ID's were private, the error rates would go down due to the fact that it would be much mor e acceptance criteria number is the threshold on which we accept or reject a fingerprint. It is solely a re mputations. For our test runs the value of 0.0800 was used. This value can be either hard coded into th time. e filtering results of an input image are shown below. You can notice below that we were able to recon y accurate binary thinned reproduction. The only area of concern for this filtering is in the very center epting 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 (r

Figure – The gabor filtered binarized image (left) and the thinned image (

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

ability and Safety:

s project is able to be used by any company or industry that wants to implement a low-level security b ir networked building. The final size of the board is approximately 9” x 9”, is user friendly, and only co rks to work out before such a product would be put into final production, but the ground work is all the

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

s project is also very safe to the user. The only interaction the user has with the electronics is with the nner. These all protect the user from hazardous voltages or currents. They are all insolated from a to

onclusions:

believe that this project turned out to be a success of its original mission. We set out to develop a ne tem and this is exactly what we achieved. A user is able to be registered and stored into a database, ir fingerprint which is then authenticated and the result is sent back locally to the microcontroller.

FAR and FRR were both below our desired hopes of both being less than 10%, and this is a great acco en more time, research, and testing these results can be greatly improved upon. One reason for our re tems require that a user has 10 different basis images scanned at 500 dpi. Our system is able to inco for the purpose of our testing we included 5 per user and our fingerprint scanner was also only 363 dp hypothesis, we believe that these two factors hurt our FAR and FRR ratios.

e speed of our authentication is more than suitable. We believe that the duration of about 8 seconds fr hentication is within the realm of a proper user interface. It provides enough accuracy for the speed, a tware optimization on the PC side, we believe that its speed could be greatly increased in regards to a rease in speed could possibly also lead to more time for better filtering algorithms.

far as the reliability of our project goes, we feel that it is suitably reliable. All of the math, algorithms, me of the off the shelf products we bought had their issues, and made debugging very important. For al converter has the property of sometimes turning off unexpectedly. However, if this were corrected fectly reliable.

a team we feel that we worked very well together and have created a very impressive final project wh erent SPI devices together, two microcontrollers, external memory, and we developed a communicatio rocontrollers and a client PC for communication of data. This all required a lot of background research dy of datasheets for our peripheral components and the microcontrollers. elluctual Property Considerations e only imaginable intellectual property violation considered is that of the fingerprint matching algorithm tching algorithm was mentioned in various texts as a simple algorithm that had moderate success in m opinion, this algorithm is more public knowledge than intellectual property because the algorithm app bbyist projects. No single company has taken the rights or royalties on the algorithm. Some variations ve been posted in scientific journals, but we did not take a novel approach toward matching. The PCB ellectual property and could be protected under law. hics, Legality, and Standards Compliance ically, we could run into a conundrum where some guests don't want their fingerprint stored in a datab ticular secure area. Some users may not know that when they put their finger on our scanner, their fin abase, and could be subpoenaed in a court of law. Perhaps a sign is needed above the sensor, or perh ess privileges, the user enters a contractual agreement to provide fingerprints. Fortunately, our syste blic use, so any private applications or implementations should avert this ethical / legal debate. project complies with all SPI / RS 232 / and Ethernet standards, as posted by the IEEE because all com as, and all circuitry for these communication protocols is implemented by reputable designers, like Atm

ppendix:

de Listings: mory.c - The main ATMega32 source code

xboard.c - The auxilary ATMega32 source code stants_32.h - Header file containing ATMega32 bit definitions gerprintspi.h - Header file to initialize the fingerprint scanner a Program Listings ges:

Figure - Fingerprint GUI

Figure - Closeup of main ATMega32 board

Figure - Closeup of auxilary ATMega32 board

re - Fingerprint sensor and serial to Ethernet converter t Details: Manufactu Part Order rer Number number Name gerprint sor Fingerprints FPC1011C 538-52030x Connector Molex 5203008290829 V reg TI 78m33 reg TI 78m05 X233 Maxim max233cpp B SRAM Fujitsu pacitors D's ial to ernet Wiznet WIZ110SR WIZ110SR kia 6100Color Ebay

Ordered ?

Price

$32 yes $1.04 sampled sampled sampled sampled own own

no yes yes yes yes yes yes

$29 yes $0(notyes

D D Connector Sockets(4) 9 Connector Molex

B's

used) $1.00 yes $2.00 yes own yes sponsorshi p yes

Sunstone

AL

Fox

AL pad

Fox

14.7456M hz 8.0000 Mhz

SUM

own

yes

own

yes $6 yes $71

ecific Tasks: B Board Design - Matthew Rosoff cuit Layout - Matthew Rosoff gerprint Sensor SPI - Matthew Rosoff AM - Matthew Rosoff utiae Matching - Matthew Rosoff ypad SPI - Peter Greczner ering - Peter Greczner ent GUI - Peter Greczner ial and Ethernet Communication - Peter Greczner bsite - Peter Greczner D Attempted Interface - Peter Greczner erences: mputational Algorithms for Fingerprint Recognition, Bir Bhanu and Xuejun Tan. Kluwer Academic Publis

gerprint Image Enhancement and Minutiae Extraction, Nimitha Chama. Department of Electrical and C versity

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

gerprint Matching Using gabor Filters, Muhammad Umer Munir and Dr. Muhammad Younas Javed, Cole gienering. National University of Sciences and Technology

gerprint Image Enhancement and Minutiae Extraction, Raymond Thai.

aracteristic Preserving Binarization for Fingerprint Image, GUI Lei, CHEN Da-hai, Li Hai, CHANG Jiang. Fo age and Graphics

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

e international congress for global science and technology -GVIP special issue on fingerprent recognitio

Mega 32 Datasheet on S1D15G10 LCD Datasheet tsu MB84256A SRAM Datasheet gerprint Cards FPC1011C Fingerprint Scanner Datasheet

cknowledgements:

would like to sincerely thank Sunstone Circuits for their generous sponsorship of PCB boards so that we caould complete this pr tronic companies from whom we sampled components from.

eter Greczner, [email protected] atthew Rosoff, [email protected]

Peter and Matt