transfer/receive data to/from outside.

However, a novel system architecture is presented in this

work. The development of a small computational platform

is intended by fitting those resources specifically required

by the application. A novel topology is suggested by taking

profit of the advantages that application specific hardware

implementation offers in comparison with a purely software

implementation.

For this purpose, current work makes use of the

advantages of Field Programmable Gate Arrays technology.

FPGAs are configurable VLSI devices where it is possible

to synthesize application specific

logic functions by

hardware, and exploit the parallelism and pipelining

features available in these devices. The current FPGA

technology also includes the notion of reconfigurability

performance, based on the capability of modifying the

hardware content throughout the application execution time.

Image Acquisition

Image Processing

Feature Extraction

Input Feature

M

A

T

C

H

E

R

Matching Result

Feature Reading

Template Feature

Fig. 2. Tasks involved in the authentication process: fingerprint image acquisition, image processing and feature extraction stages for the query

fingerprint;

template and

query fingerprints.

fingerprint matching of both,

fingerprint; and

fingerprint

template

reading

feature

the

for

The suggested platform

is mainly based on a

microprocessor, its memory block and a dynamically

reconfigurable FPGA, as shown in Fig. 3.

Fingerprint

Sensor

CPU

I / O

RAM

ROM

EEPROM

Image processor

Minutiae extractor

Matcher

R-Hw FPGA

Cryptoprocessor

Arith. coprocessor

CORDIC controller

DMA controller

Fig. 3. Main physical blocks in the proposed fingerprint-based

authentication system.

There already exist some works in literature that make

use of FPGAs or embedded platforms to implement matcher

or complete authenticator systems [4], [5]. However,

innovative

fingerprint

research arises on automatic

authenticator systems making use of reconfigurable FPGAs.

The flexibility performance reached by the reconfigurable

FPGA allows using it as a multipurpose device where it is

possible to implement several computational functions

multiplexed in time. Specific mathematical, digital-image or

biometric coprocessors can be dynamically synthesized on

the FPGA to speed up the personal authentication process.

the system,

The reconfigurable hardware gives additional flexibility

to

the workload

increasing consistently

capability of the platform in comparison with a general-

purpose personal computer. Application-specific functions

are downloaded into the FPGA as they are needed along the

execution time, thus reducing drastically the area needs for

the device in comparison with the static implementation of

all functional modules in a non-reconfigurable FPGA.

In this new topology, the FPGA is used to implement

specific coprocessors multiplexed in time, whereas the

microprocessor is responsible for managing the biometric

authentication process, as well as taking care of the FPGA

reconfiguration.

FINGERPRINT

IMAGE

FEATURE

ACQUISITION

PROCESSOR

EXTRACTOR

UNIT

UNIT

UNIT

USER’S

TEMPLATE

SENSOR

FE ATURE MATCHING UNIT

EMBEDDED

SYSTEM

ENCRYPTION UNIT

INPUT:

User’s Finger

OUTPUT:

Authentication Result

Fig. 4. Main functional blocks in the proposed fingerprint-based

authentication system.

Although the main goal of this work is to check the

feasibility of

this new architecture proposal, special

attention has to be taken to the reconfiguration overhead.

The reconfiguration of the FPGA must not overload the

application execution time. The timing constraints imposed

by

the maximum overload

admissible for reconfigurability tasks. The microprocessor

becomes the master scheduler, and controls and monitors all

activities that take place during the recognition process.

the application will set

The complete block diagram suggested in this paper is

depicted on Fig. 4. An electronic fingerprint sensor is also

integrated into the system in order to allow the automatic

fingerprint acquisition stage.

III. FINGERPRINT MATCHING ALGORITHM

The fingerprint matching algorithm is responsible for

generating a similarity score for the input and template

prints. After similarity analysis, the comparison of the

resultant match score with a certain threshold will state

whether both original fingerprints are generated (or not)

from the same finger.

Many methods for matching two fingerprints have been

presented in literature [1]. Among them, minutia-based

(fingerprint ridge discontinuities: ridge endings and ridge

bifurcations) is the most widely used technique due to its

good performance with less computational costs (processing

time and memory needs) than other techniques. Matching

two fingerprints in minutia-based representations becomes a

point pattern-matching problem, and it consists of finding

the alignment and correspondences between pairs of

minutiae points in both sets.

The proposed algorithm is abstracted from [6] and [7].

They use both local and global structures of minutiae to

fingerprint alignment and matching. Some

perform

modifications have been

the original

introduced

algorithms in order to improve the matching performance

results. The matching process is split in several sequential

steps, as described in the following sections.

to

A. Minutia Description: Local Analysis

In order to determine the similarity of fingerprints, first

the local structure of every minutia point in both minutiae

sets is obtained. The local structure describes the spatial

characteristics of

its minutiae

neighbourhood into account. This local descriptor is a

rotation and translation invariant feature, inherent to a

minutia.

a minutia

taking

The relative Euclidean distances d (1) and angles φ (3)

between the specific minutia and its nearest N minutiae

neighbours, as well as the relative ridge directions γ (4) are

used in order to clearly define the local neighbourhood of a

minutia. Every minutia is then well defined by N relative

triplets (d,φ,γ), thus a minutiae set composed by W minutia

points is then characterized by W x N triplets (d,φ,γ).

Y

y1

y0

β1

γ

β0

m1

α

d

β0

φ

m0

x0

x1

X

Fig. 5. Fingerprint minutia descriptor (d, φ, γ), where m0 (x0, y0, β0) is a

ridge ending and m1 (x1, y1, β1) is a ridge bifurcation.

)

)2

(1)

(

(

−

=

+

−

d

y

x

x

y

2

1

0

1

0

−

−

y

0

x

0







(2)

(3)

y

1

x

1

1

−

=

α

tg







0βαφ

−

−

1 β

γ

β

=

=

0

(4)

Normally, a fingerprint impression contains W=30-50

minutia points, and authors have selected N=8 neighbours

as neighbourhood criterion.

B. Minutia Comparison: Similarity Matrix

Once template and input minutiae are properly defined,

next step consists of finding the correspondence between

minutia pairs in both sets. Given a template minutiae with T

minutia points and an input minutiae with I minutia points,

a T x I similarity matrix is built in order to analyze the

similarity score between any possible minutia pair

combination. To cope with

inevitable non-linear

distortions originated during the fingerprint acquisition

stage, when mapping a 3-dimensional and elastic fingertip

onto a 2-dimensional sensor plane, small local deformations

are allowed when determining the similarity level between

minutia pairs.

the

C. Central Feature Selection

The similarity scoring of local structures permits to

identify the best-matched minutia pair and take it as

reference to align both global structures (fingerprints).

D. Minutiae Description: Global Analysis

In the same way as a minutia is defined by its local

structure, a minutiae set is defined by its global structure.

The global structure describes the spatial characteristics of

the minutiae from a reference minutia point (central

feature). Given a minutiae set composed by W minutia

points, and once determined its central feature, the minutiae

is then characterized by (W-1) triplets (d,φ,γ) relative to the

central feature point.

E. Decision Making: Match Result

Once the global definition of both minutiae sets is done,

the global correspondence analysis guarantees that one

minutia of the template minutiae can be paired at most with

one minutia of the input minutiae. A set of global minutia

pairs is obtained, allowing certain elastic tolerances in them.

From the location of the corresponding minutia pairs it is

possible

interest on both

the regions of

fingerprints. These regions of interest can be interpreted as

the overlapped areas between both prints, and from them a

similarity score can be deduced.

to select

The resultant similarity score is then compared with a

certain threshold in order to decide the match result:

authentication OK (both prints come from the same finger)

or authentication NOK (both prints come from different

fingers).

IV. HARDWARE-SOFTWARE CO-DESIGN

Hardware-software co-design methodology for hardware-

software based systems is a well-known technique in the

current technological age. Biometrics field is not an

exception, a proof of this is the big amount of biometric

matcher or authenticator systems available nowadays in the

market [8]. However, the emphasis of this work is the

implementation of biometric systems by making use of

reconfigurable architectures. This novel approach benefits

the reuse of hardware sources in order to obtain embedded

systems with similar performance, but with higher

flexibility and at lower cost than current systems.

A. Physical Platform

System-on-chip

allows

technology

customized

implementations of complete hardware/software systems

within a single chip. A new trend in system-on-chip design

are the System Level Integrated Circuits, which consist of a

microprocessor, program and data memory, various

peripherals, and a programmable system logic, providing

thus a reduced but reconfigurable architecture to develop

any kind of application.

Many reconfigurable FPGAs already exist in the market

[9]. Among them, authors have selected the system-on-chip

FPSLIC from Atmel. The platform developed in this work

is based on FPSLIC device and a configuration EEPROM

memory:

one

incorporates

• The FPSLIC (Field Programmable System Level

Integrated Circuit)

8-bit

microprocessor, its memory block (36 kbytes of

program and data memory), some peripherals such as

three programmable timers, two serial UART, one

I2C controller, one 8-bit hardware multiplier

module, as well as two I/O ports, and a 40-kgates

FPGA with dynamic reconfigurability performance,

all embedded in a SRAM-based monolithic field

programmable device.

• The EEPROM memory is used for 2 main purposes:

a) as configuration memory, in order to store the

design that has to be downloaded into the FPSLIC

on power-up or at any moment during execution

time;

b) as non-volatile memory, used to store those

application specific data such as user’s fingerprint

templates or other configuration parameters needed.

The suggested embedded system allows the hardware-

software co-design of the application. The design is stored

in the form of bitstream, which includes the FPGA

hardware content, the microprocessor program code and the

application data. It is possible to partition the application in

hardware and software tasks, thus synthesizing in the FPGA

the

those computationally expensive

microprocessor is in charge of executing the rest of less

complex tasks and managing also the reconfiguration of the

system.

tasks, whereas

B. Hardware-Software Partitioning

It is assumed that template and input minutiae sets have

been already stored into the system, in enrolment and

authentication stages respectively, before starting the match

process.

In order to partition the matching algorithm in hardware

and software tasks, a first implementation of the complete

algorithm uniquely by software is done. From here, those

more expensive tasks are identified to be implemented as

hardware tasks. Thus the microprocessor is responsible for

managing the matching process whereas in the FPGA the

local and global analysis of both minutiae sets are

implemented. Several computational coprocessors have

been synthesized into the FPGA, all of them controlled by

means of a hardware FSM (finite state machine) core block,

responsible for managing the hardware tasks under pipeline

strategy:

• A CORDIC coprocessor [10] has been synthesized

in order to accelerate the computation of distances

(SQRT function) and angles (ATAN function)

between minutia points.

• A DMA controller has been implemented in order to

provide access to the memory in a fast way, without

the support of the microprocessor.

Some configuration registers have been synthesized

on the FPGA to allow the microprocessor to control

and monitor the hardware processing.

-

The application block diagram is shown in Fig. 6.

FPGA

SKELETON

INTERFACE

DMA

CORE

FSM

INS

OUTS

CORDIC

DFF

DUAL

PORT

SRAM

DATA

INT’S

M

I

C

R

O

C

O

N

T

R

O

L

L

E

R

SRAM

PROGRAM

MEMORY

EEPROM

MEMORY

Fig. 6. Fingerprint matching application block diagram.

C. Reconfigurable Hardware Stages

Owing to the limited hardware resources available in the

current FPGA, and the computational overhead present

during local and global minutiae analysis, FPGA run-time

reconfiguration has been needed in order to increase the

effective functional density of the current design. The

matching algorithm has been split in two stages: the first

one is based on the local analysis of both minutiae sets,

whereas in the second stage the global analysis is computed.

Several hardware blocks have been implemented in every

stage on the FPGA, and a complete reconfiguration of the

FPGA has been needed between both stages to fulfil the

matching process.

The application flow diagram is shown in Fig. 7.

Template Minutiae

Input Minutiae

Local Analysis

Local Analysis

Similarity Matrix

FPGA Context 1

C.F. Pair Selection

Global Analysis

Global Analysis

Minutia Pairing

Matching Score

Decision Making

FPGA Context 2

HW Tasks

SW Tasks

HW Tasks

Fig. 7. Fingerprint matching application flow diagram.

V. EXPERIMENTAL RESULTS

There exists a trade-off between cost and execution time

when performing the hardware-software partitioning of the

application. Hardware (FPGA-based) implementation tasks

mean more cost whereas software (microprocessor-based)

implementation

latency. The

tasks mean more

reconfigurability performance of the selected FPGA allows

to further reduce the cost of hardware implementation,

whereas it increases as penalty the extra load (time and/or

resources) required for reconfiguration purposes. Finally,

the application requirements are the basis to perform an

1

efficient

summarizes the experimental results reached in this work.

partitioning. Table

hardware-software

Although the overall application timing is not minimal –

due to several factors such as the working frequency

restrictions in current FPGA and CPU devices–, the results

shown on Table 1 points the feasibility of the novel

architecture presented in this work. In those applications

where the overhead due to the FPGA reconfiguration is not

critical (6.2% of the total time in our application), this

topology can be used in order to save FPGA resources, thus

REFERENCES

[1] D. Maltoni, D. Maio, A. K. Jain, S. Prabhakar, Handbook of

Fingerprint Recognition, Springer, 2003.

[2] A. K. Jain, L. Hong, S. Pankanti, R. Bolle, “An identity-

authentication system using fingerprints”, Proceedings of the IEEE,

vol. 85, no. 9, pp. 1365-1388, September 1997.

[3] D. Maio, D. Maltoni, R. Cappelli, J. L. Wayman, A. K. Jain,

FVC2004: Third Fingerprint Verification Competition, Proceedings

of ICBA 2004, LNCS 3072, pp. 1-7, 2004.

[4] C. López-Ongil, R. Sánchez-Reillo, J. Liu-Jiménez, F. Casado, L.

Sánchez, L. Entrena, “FPGA

implementation of biometric

authentication system based on hand geometry”, FPL 2004, LNCS

3203, pp. 43-53, 2004.

[5] Q. Su, J. Tian, X. Chen, X. Yang, “A fingerprint authentication

system based on mobile phone”, AVBPA 2005, LNCS 3546, pp. 151-

159, 2005.

[6] D.P. Mital, E. K. Teoh, “An automated matching technique for

fingerprint identification”, 22nd IEEE International Conference on

Industrial Electronics, Control and Instrumentation, vol. 2, pp. 806-

811, August 1996.

[7] X. Judong, W.-Y. Yau, “Fingerprint minutiae matching based on

local and global structures”, Proceedings of ICPR 2000, pp. 1038-

1041, 2000.

[8] The Biometric Consortium, www.biometrics.org

[9] S. Donthi, R.L. Haggard, “A survey of dynamically reconfigurable

the 35th Southeastern

FPGA devices”, IEEE Proceedings of

Symposium on System Theory, pp. 422-426, March 2003.

[10] F. Fons, M. Fons, E. Cantó, and M. López, “Dynamically

reconfigurable CORDIC coprocessor for trigonometric computing”,

19th International Conference on Architecture of Computing Systems,

Workshop Proceedings, vol. 1, pp. 254-263, March 2006.

Mariano Fons received his B.S.

degree in electrical engineering

from Rovira i Virgili University

in 1995, and his M.S. degree in

industrial

and

automation

electronics

from

Rovira i Virgili University in

2001. He is currently a Ph.D.

student in the Department of Electronic, Electrical and Automation

Engineering at the Rovira i Virgili University. His current research

interests include hardware-software co-design techniques and VLSI

implementations of embedded systems.

engineering

Francisco Fons received his B.S.

degree in electrical engineering

in

and

industrial

automation

electronics

from

Rovira

i Virgili University,

Tarragona (Spain) in 1995 and

2001, respectively. He is currently pursuing a Ph.D. degree from Rovira i

Virgili University in the field of VLSI design methodologies and

dynamically reconfigurable hardware techniques for embedded systems.

engineering

his M.S.

degree

and

Enrique Cantó works

as

assistant professor at the Rovira i

Virgili University, Tarragona

(Spain). He received his Ph.D.

degree in 2001, and he has been

collaborating

or managing

several European and Spanish

research projects about reconfigurable devices, smart card architectures,

and fingerprint coprocessors.

reducing cost without having a negative effect on final

application performance.

Resources usage

Memory

CPU

FPGA

TABLE I

SYSTEM PERFORMANCE

EEPROM memory (bytes)

Data memory (bytes)

Code memory (bytes)

fclk (MHz)

Percent load CPU (%)

fclk (MHz)

Percent load FPGA (%)

Gates context 1

Flip Flops context 1

Gates context 2

Flip Flops context 2

System timing

Task 1 (Sw)

Task 2 (Hw)

Task 3 (Hw)

Task 4 (Sw)

Task 5

Task 6 (Hw)

Task 7 (Hw)

Task 8 (Sw)

Total execution time (typical value):

Minutiae set up

Template local analysis

Input local analysis

Central feature selection

FPGA Reconfiguration

Template global analysis

Input global analysis

Matching result computation

134687

7412

8338

12.5

88.8

25

5.0

1344

365

1213

338

438 µs

6689 µs

6689 µs

183348 µs

17292 µs

334 µs

334 µs

62141 µs

277265 µs

VI. CONCLUSIONS AND FUTURE WORK

system architecture

Current personal biometrics-based recognition systems

deal with unlimited computational platforms based on high

performance microprocessors with big amounts of memory

resources and powerful DSP processors running parallel

tasks at high speed. Despite this, current performance of

software-based solutions is not enough to satisfy low-cost

requirements.

A novel

fingerprint

authentication system based on hardware-software co-

design has been proposed in this paper. In comparison with

conventional architectures, the suggested topology is based

on a general-purpose microcontroller and a small-size

reconfigurable FPGA used as hardware accelerator

integrated into the system. The FPGA gives additional

flexibility and increases the workload capability of the

platform by downloading functions to the FPGA as they are

needed, and reconfiguring it along the process.

for

a

The physical implementation of the fingerprint matching

stage has been discussed in this work. It has been proven

that it is possible to implement a fingerprint matching

system by using the proposed system architecture.

The aim of the authors in their future work is to take

profit of

the advantages of FPGA reconfigurability

performance in order to develop all the steps involved in the

recognition process: not only the fingerprint matching step,

but also the fingerprint acquisition process, the image

enhancement stage and the feature extraction phase.

View publication stats

View publication stats