Procesador de Alineamiento de Huellas Dactilares

Mariano Fons, Francisco Fons, Enrique Cant Dept. dEnginyeria Electrnica, Elctrica i Automtica

ETSE Tarragona Universitat Rovira i Virgili

43007 Tarragona {mariano.fons, francisco.fons}@estudiants.urv.cat, ecanto@etse.urv.cat

Mariano Lpez Dept. dEnginyeria Electrnica

EPSE Vilanova i la Geltr Universitat Politcnica de Catalunya

08800 Vilanova i la Geltr lopezg@eel.upc.edu

Resumen

Este artculo plantea el desarrollo, mediante tcnicas de codiseo hardware-software, de un procesador biomtrico de huellas dactilares. Ms concretamente, abarca el proceso de alineamiento de huellas a partir de la matriz de orientacin de campo generada por las crestas y los valles presentes en la imagen dactilar. Dadas dos imgenes de huellas dactilares, genuinas (obtenidas a partir del mismo dedo o huella) o no, y caracterizadas por sus respectivos campos de orientacin, el procesador biomtrico se encarga de realizar un anlisis de correlacin de los vectores de orientacin de ambas imgenes con el fin de identificar el mejor alineamiento entre stas.

La fase de alineamiento es un paso previo necesario en el proceso de comparacin o matching de huellas dactilares. A partir del proceso de matching se determina el nivel de semejanza entre ambas imgenes, y finalmente se decide si stas corresponden o no al mismo individuo.

Dada una aplicacin de reconocimiento personal basada en un sistema microprocesador donde sean requeridas prestaciones de tiempo real, la introduccin de coprocesadores hardware sobre dispositivos ASIC o FPGA permite acelerar el procesado. En este artculo se demuestra como el desarrollo mediante codiseo hardware-software del procesador de alineamiento permite dotar de caractersticas de tiempo real a la aplicacin, lo que no est garantizado cuando se implementa el mismo algoritmo de alineamiento de imgenes sobre una plataforma basada en un nico microprocesador.

1. Motivacin

Los sistemas automticos de reconocimiento personal basados en biometra de huella dactilar,

ms popularmente conocidos con las siglas AFAS (Automated Fingerprint Authentication Systems),tienen como objetivo la autentificacin de la identidad de un individuo como paso previo al acceso a una zona, objeto o recurso restringidos. Para ello, el sistema de autentificacin compara las caractersticas previamente obtenidas off-line de la huella dactilar del usuario (patrn o template) con las caractersticas recin adquiridas on-line del candidato (o query). Si el nivel de semejanza entre ambas caractersticas supera un cierto umbral predefinido, el sistema de autentificacin reconoce al usuario como genuino o autntico, y le permite el acceso. En caso contrario, se considera al usuario un impostor, negando por consiguiente la accesibilidad al medio o recurso solicitado (Fig. 1).

Figura 1. Sistema AFAS.

Template

Query

NivelSemejanza

ValorUmbral

ResultadoMatching

Template = Query ?

+

Base Datos Usuarios

Huella Dactilar

SIST

RECONOCI

MIENTO

Son muchos los algoritmos de identificacin personal basados en el estudio analtico de las huellas dactilares que han sido propuestos en la literatura especializada [2]. De forma general, es posible clasificar las diferentes tcnicas de autentificacin en 3 categoras:

Tcnicas basadas en correlacin de imgenes Tcnicas basadas en minucias (bifurcaciones y finales de cresta) Tcnicas basadas en otras caractersticas estructurales extradas a partir del mapa cresta-valle de la huella dactilar. Sin embargo, y a pesar de los distintos

avances realizados en los ltimos aos, donde la biometra se ha convertido en una tecnologa claramente emergente de aplicacin en muchos mbitos de la vida cotidiana (sistemas de control de acceso, identificacin biomtrica como alternativa al DNI, cajeros automticos, Internet), el matching de huellas dactilares constituye todava hoy un reto cientfico y tecnolgico importante. La principal dificultad radica en la tarea de extraccin, de forma eficiente y fiable, de los rasgos caractersticos de la huella en aquellas imgenes que presentan un bajo nivel de calidad por cualquiera de los siguientes motivos:

las deformaciones elsticas, intrnsecas a la piel del ser humano, otros efectos tales como la edad, o callosidades, cortes, heridas u otras imperfecciones derivadas del proceso de adquisicin (diferencias de brillo y contraste, zonas de la imagen con distinto nivel de presin).

El desarrollo de estos sistemas automticos de verificacin personal est normalmente orientado al uso de estaciones de trabajo, ordenadores personales o sistemas embebidos basados en procesador. Sin embargo, para hacer frente a las dificultades del procesado, y con el fin de aumentar la fiabilidad del sistema de reconocimiento, la tendencia a nivel de los algoritmos biomtricos consiste en fusionar las 3 tcnicas anteriormente citadas en sistemas hbridos, aprovechando de esta forma las ventajas de cada una de las tcnicas, y haciendo frente a sus limitaciones [3]. Por consiguiente, el incremento de cmputo exige el aumento de las prestaciones de las plataformas donde implementar dichos algoritmos, todo ello con el

fin de mantener las caractersticas de tiempo real, facilitando el uso y manejo de dichos sistemas de reconocimiento en multitud de tareas diarias (acceso a aeropuertos, bancos, parkings privados). En este sentido, el presente artculo trata la implementacin de un sistema embebido formado por un procesador de propsito general y un dispositivo lgico programable del tipo FPGA, donde sintetizar coprocesadores hardware de aplicacin especfica que permitan acelerar aquellas tareas de elevado coste computacional. Con ello se persigue dotar de caractersticas de tiempo real a la aplicacin de alineamiento de imgenes. Dadas 2 imgenes digitales de huellas dactilares, previamente al proceso de alineamiento es necesario extraer de stas los rasgos caractersticos. Son muchas las caractersticas que pueden ser extradas de la huella dactilar tales como las minucias, la orientacin del campo, la frecuencia de las crestas, el core y el deltaEntre todas ellas, el sistema de alineamiento propuesto en este artculo hace uso del mapa de orientacin de campo puesto que presenta un mayor nivel de fiabilidad y robustez que el resto de caractersticas en el caso de adquisiciones de huellas de baja calidad. Para ello, las imgenes se dividen en bloques de NxN pxeles (N=8 en este trabajo), y para cada bloque se computa el gradiente, en las direcciones x e y, de cada pxel. A partir de la informacin del gradiente de cada uno de los pxeles del bloque se estima la orientacin del bloque tal y como se sugiere en [1]. El valor de la orientacin de campo de cada uno de los bloques de la imagen constituye la matriz de orientacin con que es caracterizada la huella dactilar. En la Fig. 2 se muestra la matriz de orientacin de campo resultante (derecha) obtenida a partir de la imagen original (izquierda). La orientacin de campo de las huellas template y query son las entradas a considerar en el algoritmo de alineamiento. El sistema de alineamiento trata de encontrar la mejor alineacin entre ambas imgenes, dando como respuesta el grado de desplazamiento (X,Y) y rotacin ( ) que debe efectuarse sobre la imagen query con el fin de alinear sta con la imagen template. Una vez alineadas ambas imgenes, es fcil determinar la regin de solapamiento entre stas, que se convierte en la regin de inters (RoI: Region of Interest) a analizar en la siguiente etapa de matching.

Captulo 1: Sistemas de Visin

28

El resto del artculo presenta en detalle el diseo del procesador de alineamiento. En la seccin 2 se resume el algoritmo de alineamiento a implementar. La seccin 3 cubre la arquitectura del sistema embebido. En la seccin 4 se muestra el diseo hardware del coprocesador. Y finalmente, los resultados experimentales y las conclusiones del trabajo son abarcados en la seccin 5.

Figura 2. Extraccin matriz orientacin de campo.

2. Algoritmo de alineamiento

El algoritmo de alineamiento de imgenes implementado basa el anlisis en la matriz de orientacin de campo de la huella dactilar. Cada imagen es dividida en bloques de NxN pxeles, y para cada bloque se calcula la orientacin dominante marcada por el flujo de las crestas. El valor de la orientacin de campo se acota en el rango [0,+180). Dadas 2 imgenes template y query de (tx x ty) y (qx x qy) bloques respectivamente, el procesado de alineamiento trata de desplazar espacialmente la matriz template sobre la matriz query. Para cada posicin relativa template-query se identifica la zona solapada o regin de inters (RoI) entre ambas imgenes, y para cada par de bloques correspondientes en la RoI se calcula la diferencia entre las orientaciones de campo, tal y como muestran las ecuaciones (1)-(5).

(1)(2)(3)

(4)

(5)

Con el fin de hacer el algoritmo de alineamiento tolerante a las deformaciones no lineales existentes en las impresiones de las huellas dactilares, se dota al algoritmo de cierta elasticidad a la hora de calcular la diferencia de orientaciones entre 2 bloques correspondidos en la RoI. Cada bloque de la imagen template es comparado no solamente con su bloque homlogo o correspondiente de la imagen query, sino tambin con los bloques vecinos, considerando un nivel de vecindad K=2 centrado en el bloque correspondiente, tal y como queda reflejado en la ecuacin (6). De esta forma, el algoritmo de alineamiento permite compensar las deformaciones no lineales intrnsecas al proceso de adquisicin.

(6)

Para cada posicin relativa template-query objeto de estudio se calcula el valor medio de la diferencia de orientaciones de los bloques comprendidos en la RoI (7), as como su desviacin estndar (8). Ambos parmetros se suman con el fin de obtener la funcion objetivo f0(9), capaz de cuantificar el nivel de correlacin o alineamiento existente entre ambas imgenes en cada uno de los posibles alineamientos objeto de estudio.

(7)

(8)

(9)

El cmputo de la funcin objetivo se realiza sobre cada una de las posiciones relativas template-query, con el consiguiente coste computacional puesto que el proceso de alineamiento se convierte en un procesado de fuerza bruta donde todos los posibles ji,Qji,Tji,RoIamientorea solap

1...qv,1...quvu,Qbloques)qx(qQuery1...tv,1...tuvu,Tbloques)tx(tTemplate

yxyx

yxyx

RoI

ji,

RoI

ji,____

1

ji,

RoI

ji,ji,,180ji,ji,minji,

RoI,ji,

QTQT

RoI

ji,

RoI

ji,

2____

RoI

1

RoIji,

RoI

____

O RoIf

jiQTjiQTKK...0...KKK...0...K

Kj,Kiji,,180Kj,Kiji,min

ji,,RoIji,

ji

RoI

ji,1nRoIenbloquesN

VII Jornadas de Computacin Reconfigurable y Aplicaciones (JCRA 2007)

29

alineamientos son analizados y entre ellos el mejor alineamiento es seleccionado. Sin embargo, y con el fin de reducir el coste computacional del algoritmo, slo aquellas posiciones relativas en las que se obtenga un mnimo de bloques solapados, por encima de un cierto umbral UmbralRoI(UmbralRoI = 16x16 boques), son estudiadas (10).

(10)

Adicionalmente, y para dotar al algoritmo de cierto nivel de robustez frente a la posibilidad de obtener diferentes inclinaciones del dedo sobre el sensor durante el proceso de adquisicin, el algoritmo es capaz de rotar la matriz de orientacin de campo de la imagen query. Dada una matriz de orientacin, es posible calcular la nueva matriz resultante tras desplazar (X,Y) bloques y rotar la matriz original grados. Cada bloque (i,j) de la matriz original se convierte en un nuevo bloque (i,j) en la imagen rotada, tal y como muestra la ecuacin (11). El nuevo valor de la orientacin de campo en la imagen rotada se obtiene sumando el ngulo de rotacin a la orientacin del bloque original.

(11)

De esta forma, el sistema desarrollado permite alinear correctamente huellas que presentan solapamientos parciales e incluso inclinaciones distintas. Con todo ello, es fcil deducir que el tiempo de ejecucin del algoritmo depender notablemente del tamao de las matrices, as como del nmero de rotaciones distintas a probar en la fase de alineamiento. Al finalizar el proceso, el sistema obtiene como resultado el mejor alineamiento -aquel que minimiza la funcin objetivo cumpliendo con el requerimiento de presentar un rea solapada superior a un cierto umbral- o por el contrario indica la no alineacin si dichos requisitos no son satisfechos. En caso de alineamiento positivo se indican los parmetros espaciales (X,Y, ) a aplicar sobre la imagen query para alinear sta con el template.

3. Codiseo hardware-software

Para el diseo del sistema de alineamiento de huellas dactilares, y debido al elevado coste

computacional requerido por la aplicacin, se plantea una arquitectura basada en un sistema multiprocesador: por un lado un core software basado en un microprocesador de propsito general, y por otro lado un dispositivo lgico programable donde implementar aquellos coprocesadores hardware a medida de la aplicacin. Dichos procesadores hardware y software trabajarn de forma concurrente con el fin de acelerar el procesado y hacer frente a la carga computacional que requiere el algoritmo de alineamiento garantizando las prestaciones de tiempo real. Se plantea que sea el propio microprocesador el core master de la aplicacin, encargado de gestionar y controlar el flujo del programa, mientras que en la FPGA se sintetizan procesadores slave que ayudan a acelerar la ejecucin de aquellas tareas crticas. As pues, es necesario identificar cuales de las tareas necesitan ser ejecutadas por hardware y cuales por software. Para seleccionar el correcto particionamiento hardware-software de la aplicacin se estructura el algoritmo como la secuencia de un conjunto de tareas, y se ejecuta inicialmente el algoritmo completo por software sobre un sistema microprocesador basado en un ordenador personal.

La Fig. 3 muestra el diagrama de flujo de la aplicacin. Como puede observarse, las entradas de la aplicacin corresponden a las matrices de orientacin de las 2 huellas dactilares template y query. El anlisis de correlacin de la orientacin de campo se lleva a cabo para distintas orientaciones de la huella query. Para cada imagen query rotada, la matriz de orientacin de campo es contrastada con la orientacin de campo de la imagen template. Para ello, se traslada la matriz template sobre la matriz query, y en cada posicin relativa se identifica la RoI. Si el nmero de bloques de la RoI supera un cierto umbral UmbralRoI, se procede con el anlisis de alineamiento. En caso contrario, se descarta y contina el procesado con una nueva posicin relativa template-query. El anlisis de alineamiento consiste en el clculo de la funcin objetivo. El algoritmo memoriza los parmetros de traslacin y rotacin relativos X, Y, de aquellas posiciones que sucesivamente minimizan la funcin objetivo. Al final del proceso de alineamiento, dichos parmetros apuntan al mejor alineamiento template-query encontrado, o en caso de no haber encontrado ningn alineamiento

YX

jiji

jiji

),(1000cossin0sincos

)',''''

RoI

RoI

ji,Umbral1n

Captulo 1: Sistemas de Visin

30

que satisfaga las condiciones del tamao mnimo de la RoI, el sistema notifica el alineamiento nulo.

Figura 3. Diagrama de flujo.

En una primera fase se implementa el algoritmo sobre un ordenador personal basado en un procesador Intel Core2 Duo @ 1,83GHz. La Tabla 1 muestra el tiempo de ejecucin medio de cada una de las tareas cuando se analizan 2 imgenes de 32x45 bloques, considerando 5 ngulos de rotacin posibles en el anlisis de alineamiento para la imagen query. Tal y como puede observarse, la tarea de mayor coste computacional corresponde claramente al cmputo del solapamiento entre ambas matrices. sta ser pues la tarea crtica a implementar por hardware. Si se consideran 5 ngulos de rotacin de la imagen query, tales como (0, 10, 20), el tiempo de ejecucin de la aplicacin supera los 4 segundos, lo cual est lejos de las prestaciones de tiempo real requeridas para la aplicacin. El tiempo total de la aplicacin puede descomponerse en el diagrama temporal de la Fig. 4 a).

Una vez definido el particionamiento, el siguiente paso consiste en definir la plataforma de

trabajo sobre la cual implementar la aplicacin. Se ha escogido un sistema embebido basado en el dispositivo System-On-Chip Excalibur EPXA10F1020C1 de Altera, que incorpora un microprocesador ARM922T de 32 bits, un bloque de memoria SRAM (40Kbytes, incluyendo memoria de datos y cdigo de programa) y un dispositivo lgico programable de 1M puertas equivalentes de la familia APEX20KE en un solo chip.

Tarea tejecucin (ms) N ciclos 1) Inicializacin 0.016 1 2) Template-Query anlisis 809.928 5 3) Rotacin Query 0.310 4 4) Seleccin alineamiento 0.001 1 Tiempo ejecucin aplicacin (ms): (Se consideran 5 ngulos: 0, 10, 20) 4050.9

Tabla 1. Tiempos tpicos ejecucin tareas.

Es preciso implementar en la FPGA una memoria dual-port SRAM donde almacenar las matrices de orientacin a analizar. Se han implementado 2 memorias distintas para almacenar las matrices template y query respectivamente. El interfaz de comunicacin entre ambos cores se establece a travs de 2 buses AMBA existentes en el dispositivo. Se ha implementado un controlador slave para que el microprocesador pueda inicializar las matrices template y query en la memoria interna de la FPGA, as como dar la orden de inicio del anlisis al coprocesador. Adems, se ha implementado otro controlador master para que sea la FPGA quien pueda notificar mediante la activacin de un flag de los registros de interfaz MCU-FPGA el final del procesado hardware. Una vez notificado, ser el microprocesador el encargado de acceder a distintos registros especficos de interfaz para leer los resultados del alineamiento (X, Y, , tamao RoI, f0).

Con el fin de que ambos procesadores puedan trabajar en paralelo, se ha particionado el algoritmo para que mientras en la FPGA se lleva a cabo el anlisis de correlacin para un ngulo de rotacin del query dado, sea el MCU el encargado de rotar la matriz query un nuevo ngulo para la prxima iteracin. A fin de facilitar el pipeline de las tareas, en la FPGA se ha implementado una memoria dual-port de almacenamiento lo suficientemente grande como para albergar 2 matrices query. Esta memoria dual-port es tratada

Matriz O. Campo Template

No

Matriz O. Campo Query

Traslacin T ( X, Y ) Rotacin Q ( )

Anlisis Solapamiento Template-Query (RoI)

RoI > UmbralRoI ?

Actualizacin Resultado ( fobjectivo , RoI, X, Y, )

Inicializacin Alineamiento (UmbralRoI, fobjetivo , X0, Y0, 0 )

INICIO

FINAL

S

No

S

S

S

No

No

fobjectivo mnima ?

Actualiza ( X, Y ) Final (T) Traslacin ?

Final (Q) Rotacin ?

No

S

Alineamiento ?

Resultado Alineamiento: fobjectivo , RoI, X, Y,

TAREA 1

TAREAS 2 Y 3

TAREA 4

TAREA 2

Clculo fobjectivo

Inicializa ( X, Y ) Actualiza ( )

VII Jornadas de Computacin Reconfigurable y Aplicaciones (JCRA 2007)

31

por la FPGA como una memoria de 2 contextos. Mientras la FPGA accede al primer contexto, el MCU inicializa el segundo contexto con la nueva matriz rotada. De esta forma se consigue sacar partido de las prestaciones de paralelismo y acelerar el proceso. Tras finalizar el anlisis de un contexto, los contextos conmutan y mientras la FPGA procesa el segundo contexto, el MCU actualiza el contexto inicial con la nueva matriz de orientacin a analizar en el siguiente ciclo. As pues, el particionado temporal queda reflejado en al Fig. 4 b).

Al final del procesado de cada matriz query rotada, el MCU consulta el valor de la funcin objetivo, el nmero de bloques solapados y los parmetros de alineamiento correspondientes al mejor alineamiento encontrado. El MCU guarda cada uno de los resultados parciales obtenidos en cada iteracin, y tras procesar todas las posibles rotaciones, decide cual es el mejor alineamiento entre template y query. Dicho resultado ser usado en las siguientes etapas del proceso de matching biomtrico con el fin de determinar el nivel de semejanza entre ambas imgenes.

Figura 4. a) Procesamiento software. b) Codiseo hardware-software.

4. Coprocesador hardware

El coprocesador sintetizado en la FPGA es un procesador slave encargado de ejecutar los comandos indicados por el controlador master (MCU) de la aplicacin. El intercambio de informacin entre MCU y FPGA se lleva a cabo de 2 formas distintas:

Se han implementado diferentes registros de interfaz a partir de los cuales el microprocesador da las rdenes de inicio del procesado, e indica qu contextos de memoria deben ser usados por el controlador hardware en cada momento. Adems el controlador hardware indica al MCU cuando ste ha finalizado el clculo de alineamiento. Varios registros guardan el resultado. Paralelamente, en la FPGA se han sintetizado 2 memorias dual-port accesibles por el MCU (WR) para inicializar las matrices de orientacin de campo, y por el coprocesador hardware (RD) con el fin de llevar a cabo el procesado.Estas memorias en la FPGA son accedidas a

travs de 2 controladores AMBA master y slave, interfaz de comunicacin entre el bus AHB y la FPGA, tal y como muestra la Fig. 5.El bus de

escritura a memoria es de 32 bits, al igual que el bus del MCU, pero el bus de lectura es ampliado con el fin de acelerar el cmputo y poder procesar toda una fila del RoI en paralelo en la FPGA.

Existen 2 memorias de tamaos distintos. La memoria encargada de almacenar la matriz de orientacin de campo de la imagen template presenta un tamao de 64 filas x 32 columnas. Cada bloque presenta una capacidad de 1 byte, donde albergar el ngulo del bloque correspondiente codificado en el rango [0-180). Adems, y puesto que la imagen puede presentar bloques de reducida calidad, donde resulta difcil extraer la orientacin del campo de forma precisa, aquellos bloques no vlidos son codificados con el dato 255 a fin de ser usados como flag indicador y no ser tenidos en cuenta en el proceso de alineamiento.

Paralelamente, la memoria correspondiente al query es de mayor tamao puesto que en ella se almacenan las matrices rotadas. Un total de 128 filas x 60 columnas son usadas para almacenar la matriz query. Este tamao inicial es ampliado a 256 filas x 60 columnas con el fin de disponer de 2 contextos en la aplicacin. La seleccin del contexto a procesar por la FPGA en cada ocasin vendr marcada por 1 bit de control de los registros de interfaz controlados desde el MCU.

MCU

FPGA

Inicializacin Rotacin Q-10 Rotacin Q+10 Rotacin Q-20 Rotacin Q+20 Sel. Alineamiento

T-Q0 anlisis T-Q-10 anlisis T-Q+10 anlisis T-Q-20 anlisis T-Q+20 anlisis

Tiempo ejecucin

MCU

Tiempo ejecucin

T-Q-10 anlisisRotacin Q-10T-Q0 anlisisInicializacin T-Q10 anlisisRotacin Q+10 T-Q-20 anlisisRotacin Q-20 T-Q20 anlisis Rotacin Q+20 Sel. Alineamiento

a)

b)

Captulo 1: Sistemas de Visin

32

El anlisis de alineamiento se lleva a cabo fila a fila. Fijada una posicin relativa de las matrices template y query, toda una fila se procesa en paralelo. Para ello existen un total de 32 ALUs (mxima anchura de la RoI, puesto que la anchura mxima de la matriz template se limita a 32 bloques) encargadas de computar la diferencia de orientacin entre los bloques correspondidos. Estas 32 ALUs realizan el clculo de la diferencia de orientacin obteniendo como resultado 2 variables, ValidCell y , como indica el Algoritmo 1. if (( T 255) && ( Q 255)) {

= min ( T- Q ,180- T- Q ); ValidCell = 1; }else{

= 0; ValidCell = 0; }

Algoritmo 1. Tratamiento parmetros aplicacin.

Con el fin de tolerar las distorsiones o elasticidades frecuentes en la huella dactilar, para cada posicin relativa template-query el controlador hardware compara el resultado obtenido tras contrastar la orientacin de cada bloque template con el correspondiente kernel 5x5 de la matriz de orientacin de campo del query. Son por tanto necesarias 25 comparaciones para obtener el resultado de procesado de un bloque del template. Puesto que toda una fila es procesada en paralelo, al cabo de 25 comparaciones, que son ejecutadas con una latencia de un tic de la frecuencia de reloj del sistema, o lo que es lo mismo, al cabo de 25 clocks, se ha procesado una fila. Tras 25 tics un total de 32 datos parciales (ValidCell, ) son obtenidos. Se ha planteado una tarea pipeline encargada de computar los 32 datos parciales a fin de obtener los acumuladores parciales n= ValidCell, y 2. Para ello los 32 pares de datos son encadenados en 2 bloques de registros de desplazamiento. Se han dividido los 32 datos en 2 bloques de 16 registros de desplazamiento que permiten calcular n= ValidCell, y 2 en 16 clocks. As pues, esta tarea puede ser concatenada en forma de pipeline con el fin de obtener un tiempo de ciclo efectivo de 25 clocks. Son necesarios 25 clocks para procesar el solapamiento de una fila.

Tras procesar todas las filas, son necesarios 15 clocks adicionales para el clculo de la funcin objetivo f0 a partir de los resultados parciales RoI= n, y 2.

Figura 5. Sistema embebido desarrollado.

Si RoI= n supera un cierto umbral predefinido UmbralRoI = 16x16, se procede con el cmputo de la funcin objetivo f0. En caso contrario se devuelve como resultado RoI= n=0, como indicador de alinemiento nulo.

Finalmente la FPGA activa el flag indicador de final de proceso en el registro de control para que el MCU se percate de la finalizacin del anlisis y lea el resultado del alineamiento. Este proceso se repite para cada uno de las rotaciones de la imagen query a estudiar, y el mejor alineamiento de entre todos los anlisis se considera el resultado. La Fig. 5 muestra el diagrama de bloques del sistema desarrollado, junto con el detalle del coprocesador hardware. El coprocesador se rige bajo un fsm (finite state machine) encargado de leer los registros de control y actuar en consecuencia. Diversos multiplexores permiten seleccionar las filas y columnas deseadas en cada momento de las matrices de orientacin de campo template y query a fin de trasladar una imagen sobre la otra

ALIGNMENT CORE

Trows selector

AHB Slave

MATH PROCESSOR

RoI = n

n > UmbralRoI ?

f0 = + =

. . . . . .

. . .. . .

. . .. . .

Qrows & Context selector

Context 0

Context 1

255 255255255

T31 T0. . . Q31 Q0. . .T31 Q31

31ValidCell31

T30 Q30

30ValidCell30

T1 Q1

1ValidCell1

T0 Q0

0ValidCell0

. . .

Tcolumns selector

Qcolumns selector

ValidCell31

0

ValidCell29

ValidCell2 ValidCell0

ValidCell3 ValidCell1

ValidCell30

0

ValidCell28

ValidCell27

ValidCell26

ValidCell5

ValidCell4

. . .

. . .

31

0

29

2 0

3 1

30

0

28

27

26

5

4

. . .

. . .

30

31

28

29

26

27

4

5

2

3

0

1

30

31

28

29

26

27

4

5

2

3

0

1

n

2

INTERFACE REGISTERS

Tcolumns Qcolumns

Trows Qrows Context

select lines

1

2

22

nnn

EXCALIBUR EPXA10 SoC

APEX 20KE FPGA AHB Master

AHB2 FPGA Bridge FPGA AHB2 Bridge

ARM 922T Core Processor

SRAM Memory AHB1 AHB2 Bridge

AHB1

AHB2

SDRAM Controller

SDRAM

Memory

Template Matrix

Query Matrix

VII Jornadas de Computacin Reconfigurable y Aplicaciones (JCRA 2007)

33

de forma eficiente durante el proceso de anlisis de solapamiento de cada uno de los posibles alineamientos.

5. Resultados y conclusiones

En la Tabla 2 se resumen los diferentes tiempos de ejecucin del algoritmo de alineamiento cuando son procesadas las mismas matrices de orientacin de campo bajo 3 plataformas de desarrollo distintas. En el primer escenario (A) se ha implementado el algoritmo por software sobre un ordenador personal de ltima generacin (Intel Core2 Duo @ 1,83GHz). Los tiempos de ejecucin son del orden de segundos, lo cual puede llegar a ser excesivo en aquellas aplicaciones cotidianas que requieran una rpida respuesta. En el segundo escenario (B), se migra el algoritmo hacia un sistema embebido constituido por un MCU ARM922T @ 50MHz. Tal y como es de esperar, y debido a la reducida frecuencia de reloj del sistema en este caso, el tiempo de ejecucin incrementa notablemente. Sin embargo, si a esta plataforma se incorpora un acelerador hardware basado en una FPGA, el correcto particionado hardware-software de la aplicacin puede conllevar aceleraciones en el rango de 2 rdenes de magnitud si se compara con el mismo sistema ejecutado nicamente bajo el MCU ARM, o de 1 orden de magnitud si se compara con la ejecucin del algoritmo sobre un ordenador personal. As pues, la paralelizacin de las tareas y el factor de aceleracin del hardware permiten dotar a la aplicacin de prestaciones de tiempo real en el escenario C.

Tarea y tejecucin (s) A B C Inicializacin 16 1860 1860 Template-Query anlisis 810+5 4210+6 5410+3Rotacin Query 310 710+3 710+3Seleccin Alineamiento 1 84 84 tejecucin aplicacin (ms) 4050 2110+4 277

Tabla 2. Comparativa (timing promedio).

El sobrecoste necesario aadido en el tercer escenario a fin de lograr el objetivo marcado de alineamiento on-line es por tanto la inclusin de un dispositivo FPGA de tamao medio con los recursos mostrados en la Tabla 3. Del orden de 2K registros, 140K bits de memoria y 11K logic cells son suficientes para sintetizar el coprocesador hardware que usa la aplicacin.

Recursos HardwareMCU fclk (MHz) 50

fclk (MHz) 50 # logic cells 10601 # registros 1844

FPGA

# bits de memoria 139264

Tabla 3. Recursos hardware.

Este artculo constata como la implementacin de aceleradores hardware de aplicacin especfica sobre dispositivos lgicos programables es una alternativa vlida en aquellas aplicaciones de elevado coste computacional donde la ejecucin del algoritmo nicamente por software puede conllevar restricciones importantes en el tiempo de ejecucin [4], [5]. El desarrollo del sistema de alineamiento mediante tcnicas de codiseo hardware-software ha permitido dotar a la aplicacin de caractersticas de tiempo real, lo cual no resulta posible en el caso de basar la aplicacin en un nico sistema microprocesador.

Referencias

[1] Hong, L., Wan, Y., and Jain, A. Fingerprint image enhancement: algorithm and performance evaluation. IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 20, no. 8, pp. 777-789, 1998.

[2] Maltoni, D., Maio, D., Jain, A. K., and Prabhakar, S. Handbook of Fingerprint Recognition. Springer Verlag, 2003.

[3] Ross, A., Jain, A., and Reisman, J. A Hybrid Fingerprint Matcher. Pattern Recognition, vol. 36, no. 7, pp. 1661-1673, 2003.

[4] Tapiador Mateos, M., and Sigenza Pizarro, J. A. Tecnologas biomtricas aplicadas a la seguridad. Editorial RA-MA, ISBN 84-7897-636-1, 2005.

[5] Yang, S., Sakiyama, K., and Verbauwhede, I. Efficient and secure fingerprint verification for embedded devices. EURASIP Journal on Applied Signal Processing, vol. 2006, article ID 58263, pp. 1-11, 2006.

Agradecimientos

Este trabajo ha sido financiado por el proyecto CICYT TEC2006-12365-C02-02 del Ministerio de Educacin y Ciencia, Espaa.

Captulo 1: Sistemas de Visin

34

/ColorImageDict > /JPEG2000ColorACSImageDict > /JPEG2000ColorImageDict > /AntiAliasGrayImages false /DownsampleGrayImages true /GrayImageDownsampleType /Bicubic /GrayImageResolution 300 /GrayImageDepth -1 /GrayImageDownsampleThreshold 1.50000 /EncodeGrayImages true /GrayImageFilter /DCTEncode /AutoFilterGrayImages true /GrayImageAutoFilterStrategy /JPEG /GrayACSImageDict > /GrayImageDict > /JPEG2000GrayACSImageDict > /JPEG2000GrayImageDict > /AntiAliasMonoImages false /DownsampleMonoImages true /MonoImageDownsampleType /Bicubic /MonoImageResolution 1200 /MonoImageDepth -1 /MonoImageDownsampleThreshold 1.50000 /EncodeMonoImages true /MonoImageFilter /CCITTFaxEncode /MonoImageDict > /AllowPSXObjects false /PDFX1aCheck false /PDFX3Check false /PDFXCompliantPDFOnly false /PDFXNoTrimBoxError true /PDFXTrimBoxToMediaBoxOffset [ 0.00000 0.00000 0.00000 0.00000 ] /PDFXSetBleedBoxToMediaBox true /PDFXBleedBoxToTrimBoxOffset [ 0.00000 0.00000 0.00000 0.00000 ] /PDFXOutputIntentProfile () /PDFXOutputCondition () /PDFXRegistryName (http://www.color.org) /PDFXTrapped /Unknown

/Description >>> setdistillerparams> setpagedevice