Verificacion de Firmas Manuscritas
Ruben Dario Acosta Velasquez
Universidad Nacional de Colombia
Facultad de Ciencias, Departamento de Matematicas
Bogota D.C., Colombia
Ano 2013
Verificacion de Firmas Manuscritas
Ruben Dario Acosta Velasquez
Tesis o trabajo de grado presentada(o) como requisito parcial para optar al tıtulo de:
Magister en Ciencias Matematica Aplicada
Director(a):
Doctor, Jorge Mauricio Ruiz Vera
Lınea de Investigacion:
Procesamiento de imagenes y Simulacion numerica
Grupo de Investigacion:
Matematica Aplicada
Universidad Nacional de Colombia
Facultad de Ciencias, Departamento de Matematicas
Bogota D.C., Colombia
2013
A mi madre
En general, el exito de este trabajo esta dedicado
a todas aquellas personas que de alguna forma
me apoyaron en este proceso, que confıan en mi
y con los cuales espero compartir este logro.
Dedicado
A mis padres
No es el conocimiento, sino el acto de aprendi-
zaje; y no la posesion, sino el acto de llegar a
ella, lo que concede el mayor disfrute.
Carl Friedrich Gauss
Agradecimientos
Con la culminacion de este trabajo soy consciente de que es el inicio de nuevos procesos y
retos, en los cuales espero seguir contando con el apoyo de muchas de las personas que me han
acompanado a lo largo de mis estudios y que de alguna forma comparten mi gusto por ello. A
mis padres que fueron dotados de la paciencia para lidiar con mi educacion, a mis hermanas
porque son unas mujeres carinosas y comprensivas, a mi sobrino que me recuerda mi ninez,
a mi novia Margarita Robles y mis amigos, especialmente a Diana Ferrucho y Fabian Roldan
por acompanarme de cerca en todo el proceso y por el apoyo que me brindaron; ademas, un
agradecimiento especial a mis dos amigos y hermanos Leonardo Andres Espinosa y Fernando
Benavides y al profesor Jorge Mauricio Ruiz Vera por permitirme su paciencia y conocimiento
en el desarrollo y escritura de este trabajo y muchas otras personas a las cuales quisiera
dedicar un espacio de agradecimiento porque aunque ha sido poco el tiempo que al momento
he compartido con ellos ha sido motivador, entre ellos a Reinaldo Torres por brindarme su
amistad y preocupacion constante, a Edwin Munoz y Diego Fonseca, a la guıa prestada por
la Universidad Nacional de Colombia y en general a todos aquellos que me apoyan.
ix
Resumen
El desarrollo de la humanidad ha traıdo consigo la implementacion de sistemas que permiten
verificar la identidad de una persona analizando varios rasgos biometricos tales como las
retinas, huellas dactilares, rostro u otros. Para el uso de tales metodologıas se requiere de la
presencia fısica del firmante; a diferencia de los requeridos si la informacion a verificar es una
firma manuscrita sobre un documento; ejemplos de tales situaciones son los actuales casos
de falsificacion de firmas dados en Interbolsa en 2012 y la recoleccion de firmas manuscritas,
iniciada el 2 de enero de 2013 para la revocatoria del alcalde Petro.
En el presente trabajo se desarrolla un modelo matematico para la verificacion de firmas
basado en tecnicas de optimizacion dinamica y transformada de Radon. Basicamente se
presentan dos clases de analisis, con un pre-procesamiento previo basado en tratamiento
de imagenes digitales. El primer analisis consiste en comparar una firma registrada contra
una firmante entrante y esto con el algoritmo (DTW) Dynamic Time Wrapping que per-
mite encontrar similitudes entre series dependientes del tiempo. Para el segundo analisis se
calcula la Transformada de Radon de cada una de las firmas tal que el resultado son los
diferentes perfiles de la firma tomados a diferentes angulos, donde seguidamente se realiza
la comparacion entre perfiles de forma que permita establecer un criterio de discriminacion
de firmas.
Los resultados numericos se obtuvieron usando un conjunto de firmas, que entre otras, nos
permitira analisis posteriores.
Palabras clave: Firma Manuscrita, Sistema de Verificacion, Algoritmo, DTW, Trans-
formada, Radon, Biometrıa, Morfologıa de imagenes.
Abstract
Day by day the human beings have developed systems that allow verifying a person’s identity
just analyzing several biometric features such as retinas, fingertips, face and others. In order
to use these methodologies we require the physical presence of the individual; however,
there are problems related to identity verification when the only available information is a
handwritten signature on a document. Examples of such situations are the current signature
forgeries cases in Colombia like the Interbolsa brokerage, firm scandal and the request to
revoke Petro’s mandate to govern Bogota, by collecting signatures.
In the work presented here, we develop a mathematical model for signature verification
based on techniques of dynamic optimization and Radon Transform. Basically, we perform
two kinds of analysis after pre-processing a digital image of a signature. The first analysis
is ”to compare”the test signature against an incoming signature through Dynamic Time
Wrapping algorithm (DTW) to determine a similarity cost between them. For the second
x
analysis the Radon Transform of each signature is computed, the results are several signature
profiles from different angles; then, a comparison between profiles is performed that allow
us to establish a signature discrimination criteria. Numerical results are presented using a
database of signatures. The results of this study could be used as a questioned document
examination tool.
Keywords: Handwritten Signature, Verification System, Algorithm, DTW, Transform,
Radon, Biometrics, Morphology Images.
Contenido
Agradecimientos VII
Resumen IX
1. Introduccion 2
1.1. Antecedentes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2. Biometrıa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.3. Firmas Manuscritas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.4. Verificacion de Firmas On-line y Off-line . . . . . . . . . . . . . . . . . . . . 4
1.5. Tipos de Falsificaciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.6. Modelos Generativos y Discriminativos . . . . . . . . . . . . . . . . . . . . . 5
1.7. Objetivos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.7.1. Objetivo general . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.7.2. Objetivos especıficos . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2. Pre-procesamiento de la Firma 6
2.1. Introduccion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.2. Sistemas on-line . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.3. Sistemas off-line . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.4. Normalizacion de Firmas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.4.1. Binarizacion de la firma . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.4.2. Esqueletizacion de la firma . . . . . . . . . . . . . . . . . . . . . . . . 10
2.4.3. Obtencion de coordenadas . . . . . . . . . . . . . . . . . . . . . . . . 19
2.4.4. Normalizacion en tamano y posicion . . . . . . . . . . . . . . . . . . 21
3. Comparacion de Firmas 26
3.1. Introduccion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
3.2. DTW (Dynamic Time Warping) . . . . . . . . . . . . . . . . . . . . . . . . . 26
3.3. DTW en la Comparacion de Firmas . . . . . . . . . . . . . . . . . . . . . . . 28
4. Transformada de Radon 31
4.1. Introduccion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
4.2. Transformada en dos Dimensiones . . . . . . . . . . . . . . . . . . . . . . . . 32
Contenido 1
4.3. Transformada Discreta de Radon (DRT) . . . . . . . . . . . . . . . . . . . . 36
4.3.1. Transformada de Radon Clasica . . . . . . . . . . . . . . . . . . . . . 36
4.3.2. Definicion de la Transformada de Radon Discreta . . . . . . . . . . . 37
4.4. Transformada de Radon en el Procesamiento de Firmas . . . . . . . . . . . . 38
5. Sistemas de Verificacion 40
5.1. Introduccion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
5.2. Captura de Firmas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
5.3. Comparacion de Componentes . . . . . . . . . . . . . . . . . . . . . . . . . . 44
5.3.1. Experimentos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
5.4. Comparacion Basada en Transformada de Radon . . . . . . . . . . . . . . . 54
5.4.1. Experimentos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
6. Conclusiones y recomendaciones 58
6.1. Conclusiones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
6.2. Recomendaciones y Trabajos Futuros . . . . . . . . . . . . . . . . . . . . . . 59
Bibliografıa 60
1 Introduccion
1.1. Antecedentes
En diversas actividades que realizamos a diario se nos exige, por un lado, identificarnos (decir
quienes somos) y por otro lado verificar nuestra identidad, es decir, dar una prueba de que
en realidad somos quienes en determinado momento aseguramos ser, por lo que usualmente
se implementan una variedad de metodologıas de identificacion que van desde la retencion
de documentos de identificacion, la creacion de tarjetas de seguridad, firmas manuscritas
en libros de registro, pasando por registros fotograficos, hasta el uso de rasgos biometricos
entre los cuales cuentan el reconocimiento de huellas dactilares, retina del ojo, registro de
voz, reconocimiento de rostro a partir de imagenes, entre otros. Todo esto se hace en pro de
salvaguardar la identidad e intereses de los miembros de una determinada organizacion y de
esta forma evitar acciones fraudulentas, como la falsificacion, que en parte son la causa del
desarrollo de tales practicas y en general de delitos como la suplantacion.
Una practica comun, relacionada con lo anterior consiste en el registro de firmas manuscritas,
para la validacion de identidad en entidades como por ejemplo la registradurıa, en el caso de
entidades estatales y bancos, en el caso de entidades privadas; para la validacion de transac-
ciones, como retiros de dinero y cobranza de cheques, y es tambien en estas practicas donde
se ha hecho comun la falsificacion de firmas y donde surge la necesidad de crear sistemas de
verificacion que permitan validar la identidad de un usuario, partiendo del registro de una fir-
ma entrante, posterior comparacion contra una base de datos de firmas registradas y analisis.
Debido a que varias de las actividades de verificacion se deben hacer en intervalos de tiempo
relativamente cortos (0 a 5 min) es necesario que los sistemas de verificacion requieran de poco
tiempo para el procesamiento y analisis, ademas de facil interpretacion de resultados. Algunos
casos famosos recientemente son: la recoleccion de firmas para pedir la revocatoria del al-
calde de Bogota Gustavo Petro http : //www.elespectador.com/noticias/bogota/apelaran−certificacion−de−firmas−revocatoria−de−petro−articulo−445063 y las trampas jurıdi-
cas (entre ellas la falsificacion de firmas) que se han empleado en la apropiacion de baldıos
http : //www.eltiempo.com/justicia/ARTICULO −WEB − NEWNOTAINTERIOR −12720277.html.
1.2 Biometrıa 3
1.2. Biometrıa
En la implementacion de sistemas de verificacion de identidad es comun el uso de sistemas
biometricos, que como su nombre lo sugiere, hacen referencia a caracterısticas cuantificables
de los seres humanos que permiten diferenciar una persona de otra. Se distinguen dos tipos
de biometrıa, la estatica que alude a las caracterısticas fısicas y la dinamica que alude a
caracterısticas de conducta (ver [18]). Entre las caracterısticas estaticas mas comunes se en-
cuentran la huella dactilar, iris, geometrıa de la mano, retina, rostro, entre otras. Entre las
dinamicas las mas comunes son, la voz, los gestos, el caminar, la escritura manuscrita, entre
otras (ver [2]). A diferencia de otros sistemas de verificacion con los sistemas biometricos
no existe la posibilidad de robo u olvido de claves, partiendo del supuesto que las carac-
terısticas consideradas son unicas para cada persona y son universales en el sentido que es
independiente de la locacion del usuario.
En los procesos biometricos se reconocen dos estados, a saber, estado de registro y estado
de verificacion, que comprenden las siguientes actividades:
Estado de Registro
Adquisicion de datos referencia
Extraccion de rasgos
Almacenamiento de patrones referencia
Estado de Verificacion
Adquisicion de datos
Extraccion de rasgos
Comparacion con patrones de referencia
Aceptacion o rechazo
Cada una de estas actividades, requiere de un arduo trabajo y procesamiento especıfico, que
se iran describiendo con mas precision a lo largo del trabajo.
1.3. Firmas Manuscritas
Una firma manuscrita corresponde, en general, a un trazo o grafico que un individuo escribe
a mano sobre una documentacion con el fin de conferir validez o de expresar conformidad.
Usualmente cada firmante desarrolla patrones en los trazos, que lo identifican y que permiten
reconocer una firma original de una falsificacion (ver [19]).
4 1 Introduccion
En diversas actividades humanas se han implementado sistemas que permiten realizar vali-
daciones de identidad a partir de firmas manuscritas, que requieren de conocimiento previo
de muestras originales de la misma, ya sea sobre documentos o firmas registradas a partir
de dispositivos electronicos.
1.4. Verificacion de Firmas On-line y Off-line
Los sistemas de verificacion de firmas estan basicamente categorizados en sistemas off-line
y sistemas on-line. Por un lado, los sistemas off-line se caracterizan porque los rasgos de
la firma se extraen de una imagen estatica sobre un papel, que usualmente es obtenida a
partir del escaneo o fotografıa de la misma sobre un documento que contiene dicha firma. Por
otro lado, los sistemas on-line requieren que el usuario registre la firma sobre una tableta de
digitalizacion, donde claramente se requiere de la presencia fısica del mismo, (ver [12, 10]).
Mientras que los sistemas off-line proveen informacion estatica de la firma, como su geo-
metrıa, (ver [11]); los sistemas on-line proporcionan informacion dinamica como la presion,
velocidad y angulo de captura, que aunque tiene en cuenta mas caracterısticas, ademas de
la geometrıa, tiene el limitante, como ya se comento, de requerir necesariamente de la pre-
sencia fısica del usuario, por lo que puede resultar no tan practico en la autenticacion de
documentos [14].
1.5. Tipos de Falsificaciones
Dentro de los experimentos y analisis que se han efectuado a lo largo del trabajo, es impor-
tante aclarar el tipo de informacion que se considera a lo largo del mismo. Ası, se tiene varios
tipos de firmas; las que denominaremos firmas originales y que refieren a firmas registradas
por un usuario, y firmas falsas o falsificaciones que clasificaremos en tres tipologıas; la
primera, corresponde a las falsificaciones entrenadas que a su vez se subdivide en otras
dos tipologıas, falsificaciones entrenadas profesionales y falsificaciones entrenadas
amateur, las primeras refieren a falsificaciones hechas por personas con “experticia”, cono-
cimiento de la firma original y tiempo de entrenamiento de la misma; las segundas refieren a
falsificaciones hechas por personas que sin tener experticia, tienen conocimiento de la firma
original y la posibilidad de entrenamiento en la falsificacion. La segunda tipologıa alude a
falsificaciones casuales o falsificaciones sin entrenamiento, que como su nombre lo in-
dica reune falsificaciones efectuadas solo con conocimiento de la firma, pero sin la posibilidad
de algun tipo de entrenamiento previo y la tercera tipologıa corresponde a falsificaciones
inesperadas, es decir, en las cuales no se tiene conocimiento de la firma si no solamente del
nombre del usuario.
Las falsificaciones entrenadas profesionales usualmente son difıciles de reconocer tanto para
sistemas de verificacion como para peritos humanos, por lo que el sistema desarrollado esta
1.6 Modelos Generativos y Discriminativos 5
disenado para maximo detectar falsificaciones entrenadas amateur.
1.6. Modelos Generativos y Discriminativos
En la literatura se encuentra una diversidad de modelos de reconocimiento de firmas, que
podemos clasificar en dos tipos de modelos, conocidos como modelos generativos y modelos
discriminativos (ver [5, 23]). Los modelos generativos mas conocidos son Hidden Markov
Models (HMMs) (ver [9, 21]), Gaussian Mixture Models (GMMs) y Naive Bayesian Models, y
los modelos discrimimativos mas usuales son Support Vector Machines (SVMs), Conditional
Random Fields (CRFs) y Neural Networks (NNs) (ver [1, 8, 29]).
La diferencia entre modelos discriminativos y generativos radica basicamente en que, por
un lado, los primeros son completamente probabilısticos para todas sus variables, mientras
que por otro lado, los segundos, modelan la probabilidad condicional de la variable objeti-
vo dadas las variables observadas. El entrenamiento de un modelo discriminativo requiere,
por lo tanto, de dos clases a clasificar, una de muestras originales y otra de falsificaciones,
usando un criterio de clasificacion que permita detectar una falsificacion entrenada amateur.
Los modelos generativos solamente requieren de una muestra de firmas originales para ser
entrenados.
1.7. Objetivos
1.7.1. Objetivo general
Verificar si una firma manuscrita es falsa o no, a partir de una base de firmas registradas.
1.7.2. Objetivos especıficos
Proponer y analizar un modelo de verificacion de firmas basado en tecnicas de proyec-
cion y tomografıa axial computarizada.
Analisis de un metodo de optimizacion que permita determinar la distancia entre dos
firmas.
Establecer metodos matematicos para la captura y pre-procesamiento de firmas.
Implementar un algoritmo que verifique firmas manuscritas, basado en los analisis
anteriores.
Analisis de resultados del modelo propuesto a partir de firmas reales y establecer
criterios de rechazo o aceptacion de una firma como.
2 Pre-procesamiento de la Firma
2.1. Introduccion
En el pre-procesamiento de firmas se distinguen dos tipos de captura, el primero, conocido
como captura on-line o de sistemas on-line, y el segundo como captura off-line o de
sistemas off-line. Los primeros hacen referencia a una captura en la cual el firmante debe
estar presente y registrar su firma mediante una tableta de digitalizacion, mientras que en
los segundos no es necesaria la presencia fısica del firmante, por lo que usualmente se tiene
la firma, sobre algun tipo de documento, como una imagen. En los dos casos es necesario
efectuar una extraccion de rasgos que permita un analisis y posterior comparacion de las
firmas.
2.2. Sistemas on-line
Como ya se indico anteriormente, los sistemas on-line exigen la presencia fısica del firmante
y ademas un dispositivo que permita la captura y digitalizacion de la firma. Tales dispositivos
estan disenados como tableros, para registrar varios rasgos a medida que se escribe sobre
este. De las caracterısticas mas comunes a tener en cuenta son: las coordenadas x e y de
cada uno de los puntos que el dispositivo toma en un muestreo, la presion que ejerce el lapiz
sobre el tablero en cada uno de los puntos, el angulo de incliacion entre el esfero y el tablero,
tambien en cada punto, y por ultimo la rapidez que lleva en cada uno de los puntos. Dicha
informacion se puede representar en una matriz de la siguiente forma
x1 x2 x3 . . . xn
y1 y2 p3 . . . ynp1 p2 p3 . . . pnθ1 θ2 θ3 . . . θnv1 v2 v3 . . . vn
.
Donde xi, yi, pi, θi y vi representan las coordenadas x e y, la presion, el angulo de inclinacion
del esfero y la rapidez, en el punto i−esimo respectivamente, y n representa el numero de
puntos registrados durante el muestreo; ası, cada una de las firmas se registra como un
conjunto de puntos discretos que se pueden someter a analisis.
2.3 Sistemas off-line 7
Figura 2-1: Tablero de Digitalizacion.
2.3. Sistemas off-line
A diferencia de los sistemas on-line, los sistemas off-line no requieren de la presencia
fısica del firmante, ni de un tablero de digitalizacion que permitan la captura de la firma,
ademas, facilitan el analisis de firmas sobre documentos fısicos, a partir de una imagen,
claro esta, a diferencia de los sistemas on-line donde la firma se captura de manera “casi
automatica”, los sistemas off-line requieren de un pre-procesamiento extra en cuanto a su
digitalizacion se refiere. La firma es ingresada como una imagen, que sera interpretada como
una matriz, a la cual se le aplicaran procedimientos hasta obtener la firma como una matriz
de la siguiente forma
A =
[x1 x2 x3 · · · xn
y1 y2 y3 · · · yn
],
donde la primera y segunda fila contienen las abcisas y ordenadas del grafo de la firma,
respectivamente.
Dichos procedimientos obedecen a operaciones de morfologıa de imagenes y transformaciones
geometricas que permitiran una posterior comparacion de firmas.
8 2 Pre-procesamiento de la Firma
Figura 2-2: Documento Firmado.
2.4. Normalizacion de Firmas
Como un primer objetivo del pre-proceso reconoceremos que dado que la firma puede estar
en cualquier color o en escala de grises, se efectuara una binarizacion, que traduce la ma-
triz(firma) a una escala de pixeles “blancos”y “negros”. Para este fin se propone un valor
umbral que de acuerdo a una intensidad I determinada, clasifique en dos conjuntos. Si las
intensidades de los pixeles es mayor a I se consideraran blancos y menor a I se consideraran
negros. En el anterior proceso se eliminan algunos pixeles aislados de la firma, que pueden
aparecer en el proceso de escaneo, o manchas que pueden considerarse no tan relevantes, que
estan sobre la superficie en donde se encuentra la firma, que se supondra como un primer
filtrado de ruido de la firma digitalizada. Como un segundo objetivo del pre-procesamiento
se obtendra el “esqueleto”de la firma y para este fin, utilizaremos funciones de morfologıa de
imagenes, especıficamente una funcion de esqueletizacion y ası tener un trazo de un pixel de
grosor. Terminado dicho pre-proceso se obtendran las firmas como matrices de informacion
donde sus componentes son 1 y 0, las coordenadas de cada una de las componentes de la fir-
ma en la matriz seran analogas a coordenadas de puntos en el plano cartesiano. Por ultimo y
como un tercer objetivo se extraeran y obtendran dos vectores de informacion que contienen
las coordenadas de x y y de la firma; una interpolacion por splines cubicos de tales puntos
dara de nuevo como resultado el grafo de la firma.
2.4 Normalizacion de Firmas 9
Figura 2-3: Firma Original Escaneada
Consideremos dos firmas S y T , una firma del sistema que de antemano se tiene certeza que
es verdadera S y una firma “entrante” T , que se quiere verificar si es una falsificacion de
S o una firma original, es decir, si procede del firmante cuya firma esta registrada. Es de
considerar que la firma entrante T puede no ser del mismo tamano, ni estar en la misma
posicion, ni estar a la misma inclinacion de la firma registrada S; ası que esto implica otro pre-
proceso que permita trasladarla, rotarla y escalarla de tal forma que tales transformaciones
no marquen diferencias determinantes al comparar la nueva firma (trasladada, rotada y
escalada T ′) con la firma registrada S. Para efectos practicos consideraremos que T = T ′,
ası, con el pre-proceso expuesto anteriormente obtenemos Sx, Sy, Tx y Ty que corresponden
a las componentes en x y y de cada una de las firmas respectivamente.
Figura 2-4: Firma Entrante a Verificar
2.4.1. Binarizacion de la firma
La firma ingresa al sistema como una imagen que esta en color o en escala de grises, en
caso de estar a color se transforma a escala de grises, utilizando operaciones de morfologıa
10 2 Pre-procesamiento de la Firma
de imagenes como la erosion, dilatacion, apertura, cerradura, entre otras (ver [24]). Seguida-
mente utilizamos una funcion de binarizacion con un umbral de intensidad igual a 0,8 que
permite convertir pixeles con una intensidad superior al umbral establecido con el valor de
1 (blancos) e inferior al umbral establecido con el valor de 0 (negros). Luego la matriz final
que se obtiene, es una matriz cuyas componentes corresponden a 1 y 0 y de esta forma se
elimina parte del ruido de la imagen.
Figura 2-5: Firma Entrante Redimensionalizada
Figura 2-6: Firma Entrante Binarizada
2.4.2. Esqueletizacion de la firma
Para obtener la firma como un grafo de un “pixel”de grosor recurriremos a la morfologıa de
imagenes.
2.4 Normalizacion de Firmas 11
Figura 2-7: Firma Entrante Esqueletizada
Figura 2-8: Firma Entrante Esqueletizada 2
Especıficamente a una funcion de esqueletizacion de imagenes que se define por medio de
otras funciones mas basicas. En el estudio de la morfologıa de imagenes el lenguaje es la
teorıa de conjuntos y por tanto una imagen esta representada por un conjunto, por ejemplo,
en imagenes binarias los conjuntos en cuestion son subconjuntos del espacio Z2 donde cada
elemento del subconjunto es una dupla (x, y) cuyas coordenadas representan coordenadas
de pixeles en la imagen. Las operaciones que se presentaran son operaciones binarias donde
uno de los conjuntos lo denotaremos como B y se conoce como elemento estructural, este
conjunto no necesariamente es el mismo en todos los casos y depende mas de lo que se quiera
obtener.
12 2 Pre-procesamiento de la Firma
Figura 2-9: Operaciones Logicas Entre Imagenes Binarias
Figura 2-10: Ejemplo de un elemento estructural
A continuacion definiremos algunos conceptos previos y operaciones de morfologıa que uti-
lizaremos para efectos de nuestros intereses.
2.4 Normalizacion de Firmas 13
Definicion 1 La reflexion de un conjunto B se denota por B y se define como
B = {w/w = −b, para b ∈ B}.
Si B es el conjunto de pixeles que representan un objeto en una imagen, entonces B es el
conjunto de puntos cuyas coordenadas son reemplazadas por (−x,−y).
Figura 2-11: Reflexion del Conjunto B
Definicion 2 La traslacion de un conjunto B por un punto z = (z1, z2), se denota por (B)zy esta definido como
(B)z = {c/c = b+ z, para b ∈ B}.
Si B es el conjunto de pixeles que representan un objeto en una imagen, entonces (B)z es el
conjunto de puntos en B cuyas coordenadas (x, y) se reemplazan por (x+ z1, y + z2).
Figura 2-12: Traslacion del Conjunto A
14 2 Pre-procesamiento de la Firma
Definicion 3 Sean A y B conjuntos de Z2, la dilatacion de A por B se denota como A⊕B
y esta definida como:
A⊕B = {z/(B)z ∩ A = ∅}
o
A⊕B = {z/[(B)z ∩ A] ⊆ ∅}
Figura 2-13: Dilatacion
2.4 Normalizacion de Firmas 15
Figura 2-14: Dilatacion con dos elementos estructurales diferentes
Definicion 4 Sean A y B conjuntos de Z2, la erosion de A por B se denota por A ⊖ B y
esta definida como:
A⊖B = {z/(B)z ⊆ A}
o
A⊖B = {z/(B)z ∩ Ac = ∅}
16 2 Pre-procesamiento de la Firma
Figura 2-15: Erosion
Figura 2-16: Erosion con dos elementos estructurales diferentes
A partir de estas operaciones basicas, definimos otras dos, conocidas como apertura (opening)
y clausura (closing).
2.4 Normalizacion de Firmas 17
Definicion 5 (Apertura) La apertura de un conjunto A por un elemento estructural B,
se denota por A ◦B y esta definida como:
A ◦B = (A⊖B)⊕B
Figura 2-17: Apertura
Definicion 6 (Cerradura) La cerradura de un conjunto A por un elemento estructural B,
se denota por A •B y esta definida como:
A •B = (A⊕B)⊖B
Figura 2-18: Cerradura
18 2 Pre-procesamiento de la Firma
Por ultimo, mostraremos una definicion de esqueletizacion y su funcionalidad en el adelga-
zamiento de firmas.
Definicion 7 Sea A una imagen y B un elemento estructural, entonces, la esqueletizacion
de A puede ser expresada en terminos de las operaciones de erosion y apertura, ası:
S(A) =k∪
k=0
Sk(A),
donde
Sk(A) = (A⊖ kB)− (A⊖ kB) ◦B,
donde B es el elemento estructural, y (A⊖ kB) indica k erosiones sucesivas de A
(A⊖ kB) = ((. . . ((A⊖B)⊖B)⊖ . . .)⊖B),
k veces, con K el ultimo paso de iteracion antes de que A sea un conjunto vacio
K = max{k/(A⊖ kB) = ∅}.
Como resultado de la esqueletizacion la firma quedara representada graficamente como un
trazo de un pixel de grosor y en terminos de matrices, como una matriz que contiene 0
(“Pixeles negros”) y 1 (“Pixeles blancos”)
Figura 2-19: Esqueletizacion
2.4 Normalizacion de Firmas 19
Figura 2-20: Imagen en grises-Binarizacion-Esqueletizacion
2.4.3. Obtencion de coordenadas
Dado el resultado del proceso de esqueletizacion, es de nuestro interes hacer el reconocimiento
de las coordenadas, es decir, la posicion columna-fila para cada uno de los pixeles que hacen
parte del trazo de la firma y esto en pro de obtener una representacion de esta en el plano.
Ası, los valores de las columnas quedaran identificados con los valores de las abscisas en el eje
X y los valores de las filas se identificaran con las ordenadas en el eje Y . De esta forma, dada
la firma S, representada como una matriz, extraemos las respectivas coordenadas Sx, Sy, que
corresponden a la posicion i, j del pixel dentro de la matriz, por lo tanto, las j conforman
una sucesion que contiene las abscisas y las i una sucesion que contiene las ordenadas de
cada pixel. Como un ejercicio de verificacion se puede comprobar que al graficar los puntos
sobre un plano, se obtiene nuevamente el trazo de la firma en cuestion y por ultimo es de
resaltar que esta representacion es ventajosa en los procesos de escalamiento y comparacion
de las firmas.
20 2 Pre-procesamiento de la Firma
Figura 2-21: Coordenadas en X de la firma registrada
Figura 2-22: Coordenadas en Y de la firma registrada
2.4 Normalizacion de Firmas 21
2.4.4. Normalizacion en tamano y posicion
El supuesto inicial es que la firma que se considera como “original”, y la firma cuya veracidad
queremos comprobar, se encuentran en un mismo plano, pero no necesariamente estan sobre
los mismos ejes, o alineadas y tambien pueden no estar a la misma escala; lo que nos lleva a
tener que trasladarlas, rotarlas y dilatarlas o reducirlas, (ver [15, 26]).
Figura 2-23: Firmas en Diferentes Posiciones
Traslaciones
Consideremos la firma S y los vectores Sx, Sy, que representan las coordenadas en x y y
respectivamente y ademas supongamos que S no se encuentra centrada en el origen. Nuestro
objetivo consiste en mover la firma S al origen del plano reconociendo un vector de traslacion
que permita llevarla allı, esto se logra calculando el centro de masa de la firma y considerando
el vector cuyo punto inicial es el origen y punto final es el centro de masa, luego tenemos
que el centro de masa corresponde al punto
z =
(1
n
n∑i=1
xi,1
n
n∑i=1
yi
)= (xz, yz),
donde xz y yz representan los promedios de las componentes en x y y.
22 2 Pre-procesamiento de la Firma
Ahora definamos S ′ a la matriz cuyos elementos son (xi − xz, yi − yz) para todo i = 1, ..., n,
que representan a cada punto traslado, esto es
S ′ =
[x1 − xz x2 − xz x3 − xz · · · xn − xz
y1 − yz y2 − yz y3 − yz · · · yn − yz
].
Donde xi = xi − xz, yi = yi − yz para i = 1, ..., n y S ′ respresenta la firma centrada en el
origen del plano.
Figura 2-24: Firma Trasladada
Escalamiento
Para el escalamiento haremos uso del concepto de normalizacion de vectores, que aparece
naturalmente en el algebra lineal. Definiremos para ello el coeficiente
D′ =
√√√√ n∑i=1
xi2 + yi
2
que se puede interpretar como la norma de un vector y asumiendo que la firma es un vector,
entonces, 1D′S representa un vector paralelo y como el interes es obtener una respresentacion
a la misma escala de cada una de las firmas entrantes, ello esta dado por
1
D′
[x1 − xz x2 − xz x3 − xz · · · xn − xz
y1 − yz y2 − yz y3 − yz · · · yn − yz
].
2.4 Normalizacion de Firmas 23
Figura 2-25: Firma Escalada
Rotaciones
Consideremos la matriz de rotaciones dada por
R =
[cos θ − sin θ
sin θ cos θ
].
Dentro de la teorıa del algebra lineal, es sabido que dicha matriz permite la rotacion de un
vector de R2, θ radianes, manteniendo como invariante su longitud.
Conocido esto, consideremos una matriz de rotaciones que nos permite tener, a la misma
inclinacion, las dos firmas a comparar. La pregunta inmediata que surge es: ¿a que angulo θ
se debe rotar cada firma? Para ello calcularemos el angulo entre ellas considerando P , Q y
D coeficientes, que llamaremos coeficientes de normalizacion.
P =n∑
i=1
xiai + yibi
Q =n∑
i=1
xibi − yiai
D =
√√√√(P 2 +Q2)n∑
i=1
(x2i + y2i )
24 2 Pre-procesamiento de la Firma
Donde xi = xi − xz, yi = yi − yz, D =√P 2 +Q2D′ y ai, bi son las coordenadas en x e
y, respectivamente, de la firma registrada. Entonces las coordenadas para cada una de las
firmas trasladas, rotadas y escaladas, corresponde a
S ′ =
[Xi
Yi
]=
1
D
[P −Q
Q P
] [xi
yi
].
Nota: para tener claridad sobre los coeficientes P y Q tengamos en cuenta que cos θ = u·v∥u∥∥v∥
y ∥u× v∥ = ∥u∥∥v∥ sin θ respectivamente.
Figura 2-26: Firma Entrante
2.4 Normalizacion de Firmas 25
Figura 2-27: Firma Entrante Rotada
3 Comparacion de Firmas
3.1. Introduccion
Del pre-proceso anterior se obtiene como resultado que las firmas se encuentren centradas
en el punto (0, 0), escaladas y rotadas al mismo angulo, esto, tanto para la firma T cuya
originalidad se quiere comprobar como para la firma registrada S y cuya originalidad se
asume. Nuestro objetivo ahora es identificar si la firma T corresponde a una firma genuina o
a una falsificacion y para ello se propone examinar las firmas “punto a punto”, comparando
Sx con Tx y Sy con Ty. Para tal comparacion se supone cada vector de coordenadas como
una sucesion dependiente del tiempo, que en nuestro caso practico equivale a un subındice
tal que Sx = {Sx(i)\i = 1, ..., n} y Tx = {Tx(j)\j = 1, ...,m}, analogamente para Sy, Ty,
donde n y m son enteros positivos no necesariamente iguales. Por las caracterısticas ante-
riormente propuestas se sugiere la implementacion del algoritmo DTW que presentaremos a
continuacion.
3.2. DTW (Dynamic Time Warping)
DTW es una tecnica de Programacion Dinamica que permite encontrar una “alineacion
optima” entre dos sucesiones (dependientes del tiempo), bajo ciertas restricciones. Usual-
mente se utiliza en la comparacion de patrones de voz en discursos, en minerıa de datos, en
recuperacion de informacion y en general en la deteccion de formas similares de sucesiones
con diferentes fases (ver [7, 20, 25, 27]).
Dadas dos sucesiones X := (x1, x2, . . . , xN) con N ∈ N y Y = (y1, y2, . . . , yM) con M ∈ N,que pueden ser sucesiones de rasgos muestreadas en puntos equidistantes de tiempo. A
continuacion designamos un espacio de rasgos o caracterısticas denotado por F y entonces
xn, ym ∈ F, para n ∈ [1 : N ] y m ∈ [1 : M ]. Para comparar dos rasgos x, y ∈ F se requiere
de una medida de costo local, que en ocasiones tambien se conoce como medida de distancia
local y que se define como
c : F× F −→ R≥0.
Intuitivamente podrıamos decir que la distancia es pequena si x y y son “mas” parecidas y la
distancia sera mayor si son diferentes. Evaluando la medida de costo local para cada par de
elementos de las sucesiones X y Y se obtiene la matriz de costos C ∈ RN×M definida como
3.2 DTW (Dynamic Time Warping) 27
C(n,m) := c(xn, ym). Dicha funcion de distancia es comunmente conocida como funcion
de costo y el objetivo principal es encontrar una alineacion optima, esto es, minimizar el
costo, entre las sucesiones. El algoritmo inicia con la construccion de la matriz de costos
C ∈ RN×M , tal que, cada elemento de la matriz representa las distancias entre cada par de
elementos de X y Y , ası:
C ∈ RN×M : cij = d(xi, yj), i ∈ [1 : N ], j ∈ [1 : M ].
El camino optimo se obtendra a traves de la matriz de costos iniciando en el elemento que
se encuentra en la posicion (1, 1) y finalizando en la posicion (N,M). La siguiente definicion
formaliza la nocion de alineamiento.
Definicion 8 Un (N,M)-camino es una sucesion p = (p1, p2, ..., pL) con pl = (nl,ml) ∈ [1 :
N ]× [1 : M ] para l ∈ [1 : L] que satisface las siguientes tres condiciones:
Condicion de frontera: p1 = (1, 1) y pL = (N,M).
Condicion de monotonicidad: n1 ≤ n2 ≤ . . . ≤ nL y m1 ≤ m2 ≤ . . . ≤ mL.
Condicion de tamano de paso: pl+1 − pl ∈ {(1, 0), (0, 1), (1, 1)} para l ∈ [1 : L− 1].
Un (N,M) − camino p = (p1, p2, ..., pL) define un alineamiento entre dos sucesiones X =
(x1, x2, ..., xN) y Y = (y1, y2, ..., yM) asignando los elementos xnlde X a los elementos yml
de Y . La condicion de frontera reafirma que los primeros y ultimos elementos de X y Y se
corresponden respectivamente. La condicion de monotonicidad muestra que si un elemento
de X precede a un segundo elemento, entonces, sucedera lo mismo con sus correspondientes
en Y y finalmente el tamano de paso muestra que todos los pares contenidos en un camino,
son pares diferentes.
El costo total cp(X, Y ) de un camino p entre X y Y con respecto a la medida de costo local
c esta definida como:
cp(X,Y ) :=L∑l=1
c(xnl, yml
).
Ademas, un camino optimo entre X y Y , es un camino p∗ que tiene el costo mınimo de todos
los posibles caminos. Entonces la distancia DTW, DTW (X,Y ), entre X y Y esta definida
como el costo total de p∗:
DTW (X, Y ) := cp∗(X,Y ) = mın{cp(X,Y )/p es un (N,M)− camino}.
Para definir un camino optimo p∗ se podrıan explorar todos los posibles caminos entre X
y Y , pero tal procedimiento tendrıa una complejidad computacional exponencial. Ası que
usaremos un algoritmo de orden O(NM) basado en programacion dinamica y para este fin
28 3 Comparacion de Firmas
definimos la sucesiones de prefijos X(1 : n) := (x1, x2, ..., ) para n ∈ [1 : N ] y Y (1 : m) :=
(y1, y2, ..., ym) para m ∈ [1 : M ] y el conjunto
D(n,m) := DTW (X(1 : n), Y (1,m))
Los valores D(n,m) definen una matriz D de tamano N × M , que refiere la matriz de
costos acumulados y D(N,M) = DTW (X,Y ). En adelante, una dupla (n,m) representa
una entrada de la matriz de costos C o de la matriz de costos acumulados D. El siguiente
teorema muestra como D puede ser calculada eficientemente.
Teorema 1 La matriz de costos acumulados D satisface las siguientes identidades: D(n, 1) =∑nk=1 c(xk, y1) para n ∈ [1 : N ], D(1,m) =
∑mk=1 c(x1, yk) para m ∈ [1 : M ], y
D(n,m) = mın{D(n− 1,m− 1), D(n− 1,m), D(n,m− 1)}+ c(xn, ym)
para 1 < n ≤ N y 1 < m ≤ M . En particular, DTW (X,Y ) = D(N,M) puede ser calculada
con O(NM) operaciones.
Demostracion 1 Sea m = 1 y n ∈ [1 : N ]. Entonces existe solo un posible camino en-
tre Y (1, 1) y X(1, n) que tiene un costo total de∑n
k=1 c(xk, y1) que equivale a D(n, 1). De
manera similar se obtiene la ecuacion para D(1,m). Ahora, sea n > 1 y m > 1 y sea
q = (q1, q2, ..., qL−1, qL) un camino optimo para X(1 : n) y Y (1 : m), entonces, la condicion
de frontera implica que qL = (n,m). Suponiendo (a, b) = qL−1, la condicion de tamano de
paso implica que (a, b) ∈ {(n − 1,m − 1), (n − 1,m), (n,m − 1)}. Ademas de esto se sigue
que (q1, ..., qL−1) debe ser un camino optimo para X(1 : a) y Y (1 : b), de otra forma, q no
seria optimo para X(1 : n) y Y (1 : m). Dado que D(n,m) = c(q1, ..., qL−1)(X(1 : a), Y (1 :
b)) + c(xn, ym), la optimalidad de q implica que D(n,m) = mın{D(n − 1,m − 1), D(n −1,m), D(n,m− 1)}+ c(xn, ym).
Notese que D puede ser calculada en una unica columna, donde el calculo de la m− esima
columna solo requiere los valores de la (m−1)− esima columna y esto implica que si solo se
esta interesado en el valor DTW (X, Y ) = D(N,M), el almacenamiento requerido es O(N),
de manera similar si el calculo se hace sobre una unica fila, se obtiene O(M). Sin embargo
el tiempo requerido en nuestro caso es O(NM).
3.3. DTW en la Comparacion de Firmas
Dadas dos firmas S y T pre-procesadas, las comparaciones se efectuan entre Sx, Tx y Sy,
Ty respectivamente, donde cada una de estas es una sucesion dependiente de un ındice, por
ejemplo, Sx = Sx(1 : n) y Sy = Sy(1 : m). La caracterıstica especıfica a considerar es, las
coordenadas de los puntos de la muestra que conforman cada una de las firmas, seguidamente
3.3 DTW en la Comparacion de Firmas 29
se efectua la construccion de la matriz de costos C que requiere de la definicion de una
“funcion de distancia”que para nuestro caso es la funcion de distancia Euclıdea:
cij = d(xi, yj) = (xi − yj)2.
Ejemplo: Consideremos las sucesiones
Xtest = (2, 0, 3, 1, 1, 2, 1) y Xinp = (2, 1, 3, 0, 1, 1)
Figura 3-1: Series 1 y 2
La matriz de costos C correspondiente a la comparacion de las sucesiones es:
C =
0 1 1 4 1 1
4 1 9 0 1 1
1 4 0 9 4 4
1 0 4 1 0 0
1 0 4 1 0 0
0 1 1 4 1 1
1 0 4 1 0 0
.
La matriz de costos acumulados D corresponde a
D =
0 1 2 6 7 8
4 1 10 2 3 4
5 5 1 10 6 7
6 5 5 2 2 2
7 5 9 3 2 2
7 6 6 7 3 3
8 6 10 7 3 3
,
30 3 Comparacion de Firmas
donde el elemento D(7, 6) = 3 corresponde al costo mınimo entre las dos sucesiones y el
camino optimo es p = {(1, 1), (2, 2), (3, 3), (4, 4), (4, 5), (4, 6), (5, 6), (6, 6), (7, 6)}.
Figura 3-2: Comparacion entre series 1 y 2
Dada esta informacion, se obtiene la matriz de costos C, la matriz de costos acumulados D
y el costo mınimo entre cada par de sucesiones.
4 Transformada de Radon
4.1. Introduccion
Existe un problema comun a varias areas del conocimiento, conocido como el problema
de la reconstruccion, que consiste basicamente en como determinar la estructura interna
o alguna propiedad de la estructura interna de un objeto, sin comprometer su estructura
fısica, es decir, sin generar cortes, roturas o algun tipo de dano (ver [6, 28]). Varias de las
investigaciones que se han adelantado incluyen el uso de rayos X, rayos gamma, luz visible,
microondas, electrones, protones, neutrones y senales de resonancia magnetica nuclear, para
el estudio no solo de objetos de gran tamano si no tambien para el estudio de estructuras
moleculares, pasando por el estudio del cuerpo humano y esto por medio del desarrollo de
la tomografıa axial computarizada. Todas estas aplicaciones encuentran su fundamento en
el desarrollo de la Transformada de Radon, propuesta por el matematico hungaro Johann
Radon en 1917.
Con el desarrollo de la electronica son muchas las areas de la ciencia donde ha cobrado
importancia, entre las cuales se cuentan los avances en medicina con el desarrollo de la
tomografıa axial computarizada y los ultrasonidos entre otros; en la astronomıa, la optica,
analisis de stress, geofısica y otras areas, esto gracias a la implementacion tanto del concepto
como de la algoritmia que presupone el calculo de la transformada. Ası, intuitivamente,
podemos considerar alguna caracterıstica relacionada con la distribucion de masa interna de
un objeto, como por ejemplo la densidad y este en interaccion con algun tipo de onda permite
detectar una distribucion proyectada o un perfil de dicho objeto. En muchas ocasiones la
propiedad interna del objeto puede identificarse o ser aproximada por alguna funcion f y el
perfil puede ser identificado o aproximado por la Transformada de Radon de f , cada perfil
esta identificado con una muestra de la transformada y el conocimiento de todos los perfiles
constituye el conocimiento de toda la transformada.
De lo anterior suponemos que el objeto en estudio es cada una de las firmas y dado nuestro
interes en hacer un reconocimiento de la “configuracion” de la misma, abordamos dicho
problema haciendo uso de la transformada.
32 4 Transformada de Radon
4.2. Transformada en dos Dimensiones
Sea (x, y) un punto en el plano y f una funcion definida arbitrariamente sobre algun dominio
D de R2 y sea ademas L una lınea en el plano, entonces, definiremos la proyeccion o lınea
integral de f a lo largo de todas las posibles lıneas L como transformada de Radon, asumiendo
que la integral existe. Explıcitamente tenemos.
f = Rf =
∫L
f(x, y)ds.
Donde ds es un incremento de longitud a lo largo de L. El dominio D puede incluir todo el
plano o alguna region de este. Radon mostro que si f es continua y tiene soporte compacto,
entonces Rf esta unıvocamente determinada por la integral a lo largo de todas las lıneas L.
4.2 Transformada en dos Dimensiones 33
Figura 4-1: Dominio D
.
Donde la ecuacion de la lınea L esta dada en forma normal por
p = x cosϕ+ y sinϕ.
La lınea integral en la Figura 4-1 depende de los valores de p y ϕ lo cual se hace explıcito
escribiendo
f(p, ϕ) = Rf =
∫L
f(x, y)ds.
34 4 Transformada de Radon
Si f(p, ϕ) es conocido para todos los p y ϕ, entonces f(p, ϕ) es la transformada de Radon en
dos dimensiones de f(x, y); si f es conocida solo para ciertos valores de p y ϕ diremos que
se tiene una muestra de la transformada.
Introduciendo un nuevo sistema de coordenadas con ejes rotados un angulo ϕ. Si los nuevos
ejes estan marcados por p y s como en la Figura 4-2, entonces tenemos
x = p cosϕ− s sinϕ
y = p sinϕ+ s cosϕ.
Figura 4-2: Dominio D
Reemplazando
f(p, ϕ) =
∫ ∞
−∞f(p cosϕ− s sinϕ, p sinϕ+ s cosϕ)ds.
Por supuesto, los lımites son finitos, si f no esta definida fuera del dominio D.
Otra forma de obtener el mismo resultado, consiste en recurrir a la notacion vectorial
x = (x, y) para un vector con componentes x y y, entonces f(x) es equivalente a f(x, y)
e introduciendo los vectores unitarios,
4.2 Transformada en dos Dimensiones 35
ξ = (cosϕ, sinϕ)
y
ξ⊥ = (− sinϕ, cosϕ).
Figura 4-3: Dominio D
como indica la Figura 4-3
Ahora, podemos considerar un parametro t de tal forma que x = pξ + tξ⊥ y en terminos de
las nuevas variables la anterior formula se puede escribir como
f(p, ξ) =
∫ ∞
−∞f(pξ + tξ⊥)dt.
La notacion f(p, ξ) y f(p, ϕ) pueden ser usadas indistintamente dependiendo de lo que se
quiera enfatizar.
Finalmente se introducira otra forma que permite escribir la formula como una integral
doble. Observemos que
36 4 Transformada de Radon
p = ξ · x = x cosϕ+ y sinϕ.
Entonces la transformada puede ser escrita como una integral sobre R2 e introduciendo la
funcion Delta de Dirac se obtiene:
f(p, ξ) =
∫ ∫R2
f(x)δ(p− ξ · x)dxdy.
Aunque esta sea la forma deseada, con una modificacion mas de notacion, en lugar de dxdy
escribimos simplemente dx e indicamos la integral sobre todo el espacio por el sımbolo∫en
vez de∫ ∫
R2 y con dichas modificaciones obtenemos.
f(p, ξ) =
∫f(x)δ(p− ξ · x)dx
Es de notar que la direccion del vector unitario ξ se define en terminos del angulo ϕ. Dado que
ξ es un vector unitario caracterizado por ϕ, f esta definida sobre un cilindro semi-infinito,
esto debido a que los valores de f en (−p, ϕ) y (p, ϕ + π) son los mismos. Es importante
observar que en el espacio xy, para un angulo ϕ la variable p cambia a lo largo de una
direccion definida por ϕ. En el espacio de la transformada ϕ define la direccion asociada con
una posicion dada. Supongamos que se mantienen constante mientras p varia, entonces los
puntos (p, ϕ) definen una lınea sobre el cilindro. El numero real asociado con cada punto a
lo largo de la lınea y el conjunto de puntos definen un perfil fϕ(p).
4.3. Transformada Discreta de Radon (DRT)
Es necesario realizar un calculo discreto de la transformada, dada la naturaleza de la in-
formacion que se esta trabajando y la necesidad de una implementacion computacional,
para lo cual se considera la Transformada Discreta de Radon (DRT) por sus siglas en ingles
[15, 16, 17].
4.3.1. Transformada de Radon Clasica
Ya vimos previamente como se obtiene la transformada de Radon y una de sus representa-
ciones mas habituales. Ahora la Transformada de Radon de una funcion u de dos variables
es una funcion Ru definida sobre una familia de lıneas rectas [13], donde los valores de Ru es
la integral de linea de u a lo largo de cada una de las lıneas. Luego para representar cualquier
linea sobre un plano (t, q), tenemos
t = τ + pq,
donde τ y p son parametros y τ representa la interseccion de tiempo y p la pendiente, ası,
la funcion u(t, q) representa un objeto y la Transformada de Radon para este caso es
4.3 Transformada Discreta de Radon (DRT) 37
(Ru)(τ, p) =
∫ +∞
−∞u(τ + pq, q)dq.
La formula de inversion de Radon puede ser escrita en notacion de operadores como
R∗KR = I,
dondeK es una operador uni-dimensional(filtro) yR∗ es la transformada dual. Dado v(τ, p) =
(Ru)(τ, p) y por la ecuacion anterior tenemos que u = R∗Kv y el operador de convolucion
esta dado por
(Ku)(τ, p) =
∫ +∞
−∞|f |v(f, p)e−2πifτdf,
donde
v(f, p) =
∫ +∞
−∞v(τ, p)e2πifτdτ.
La transformada dual R∗ se define como:
(R∗v)(t, q) =
∫ +∞
−∞v(t− pq, p)dp
que tambien es conocido como el operador de retro-proyeccion.
Sea u(t, q) una funcion que contiene 2L + 1 lıneas y u(t, ql), donde l = 0,±1, ...,±L. Asu-
miendo que q−L < q−L+1 < ... < qL−1 < qL aproximamos la integral (Ru)(τ, p) por:
(Ru)(τ, p) =l=L∑l=−L
u(τ + pql, ql)∆ql,
donde ∆ql = (ql+1 − ql−1)/2 para l = 0,±1, ...,±(L − 1) y ∆qL = qL − qL−1,∆q−L =
q−L+1−q−L. Para obtener un valor de la funcion u(τ+pql, ql) se podrıa utilizar interpolacion
en la primera variable de ser necesario. La implementacion numerica del operador R∗ es
completamente analoga a la formula anterior.
4.3.2. Definicion de la Transformada de Radon Discreta
Sea xl(n) un arreglo dos-dimensional, donde −L ≤ l ≤ L para un indice fijo l, xl(n) repre-
senta una senal discreta a la cual nos referiremos como una serie de tiempo trazo sismico.
Elejimos un numero impar de trazos (2L + 1) por conveniencia. Para un punto de tiempo
fijo n, n = 0, ..., N − 1 denotamos por x(n) el siguiente vector:
38 4 Transformada de Radon
x(n) =
x−L(n)
...
x0(n)
...
xL(n)
.
Asumimos que x(n) esta definido para todos los enteros n y es una sucesion periodica con
periodo N ,
x(n+N) = x(n).
Suponiendo que todas las sucesiones consideradas son periodicas, tenemos la siguiente trans-
formada
y(n) =m=M∑m=−M
Rmx(n+m),
donde 2M + 1 ≤ N y Rm son matrices de tamano (2J + 1) × (2L + 1) que refieren a
transformadas, tal que y(n) denota una sucesion vector periodica, con periodo N
y(n) =
y−j(n)
...
y0(n)
...
yj(n)
,
donde yj(n) es una arreglo dos-dimensional con ındice j, −J ≤ j ≤ J , que representa
diferentes pendientes. El numero M es el numero de vectores vecinos a lado y lado del vector
entrante x(n) involucrado en el calculo del vector de salida y(n).
Definicion 9 Llamaremos Transformada de Radon Discreta a cualquier transformada de la
forma anteriormente nombrada.
La Definicion 9 es una definicion de una clase de transformadas mas que de una transformada.
4.4. Transformada de Radon en el Procesamiento de
Firmas
La transformada de Radon es obtenida cuando las proyecciones o perfiles de una imagen (o
matriz) son calculados para angulos igualmente distribuidos entreO◦ y 180◦. La transformada
es tambien una matriz, donde cada una de las columnas representa una proyeccion o perfil
de la imagen original en un determinado angulo (ver [3, 4, 22]).
4.4 Transformada de Radon en el Procesamiento de Firmas 39
Dada una imagen y suponiendo que consta de Ψ pixeles con intensidades Ii con i = 1, ...,Ψ
respectivamente, la Transformada de Radon se calcula usando Nφ rayos por angulo con NΘ
angulos en total. Las intensidades acumuladas de los pixeles por los que cruza el j − esimo
rayo es denotado por Rj con j = 1, ..., NφNΘ y es llamada la j − esima suma de rayos, ası,
en forma discreta la Transformada de Radon puede ser expresada como sigue
Rj =Ψ∑i=1
wijIi, j = 1, ..., NφNΘ.
Donde wij indica la contribucion del i − esimo pixel a la j − esima suma de rayos y son
encontrados calculando la distancia del segmento que cruza por el i− esimo pixel, donde la
diagonal principal del pixel equivale a uno.
Cada proyeccion por lo tanto contiene la suma de rayos que son calculados en un angulo
dado. La precision de la Transformada esta determinada por NΘ (numero de angulos), Nφ
(numero de rayos por angulo) y la precision en la medicion de cada wij.
Como ya es sabido, cada una de las firmas es ingresada al sistema como una imagen estatica
y comparada con firmas registradas que permiten establecer, con un cierto umbral, “que
tan parecidas son”, que se puede interpretar como que la firma entrante es original o no.
Basicamente, el sistema realiza una comparacion de firmas basado en la Transformada de
Radon de cada una de ellas, es decir, se calculan los perfiles de cada una de las firmas con
los mismos parametros NΘ y Nφ, para seguidamente efectuar la comparacion perfil a perfil
en cada uno de los angulos respectivos.
Cada perfil obtenido se puede considerar practicamente como una “senal”que guarda las
sumas de las intensidades por cada rayo en cada angulo, tal interpretacion permite comparar
cada senal angulo a angulo por medio del algoritmo DTW y de esta forma comparar cada
firma por medio del contraste entre proyecciones.
5 Sistemas de Verificacion
5.1. Introduccion
En el desarrollo teorico que hasta ahora se ha expuesto, se han presentado partes de lo que
comprende el proceso de verificacion, tanto lo que respecta al uso del algoritmo DTW [11]
para la comparacion de componentes en X y Y , como lo que respecta a la comparacion de
las proyecciones obtenidas a partir del calculo de la transformada de Radon de cada una de
las firmas. A continuacion se presenta un desarrollo mas exhaustivo de las dos metodologıas
propuestas para la verificacion de firmas y se pone a prueba haciendo uso de firmas obtenidas
de personas que dieron previa autorizacion para la manipulacion y falsificacion de su firma;
ver[14].
5.2. Captura de Firmas
Se pidio a cinco personas que practicaran su firma con el fin de obtener una muestra de cinco
firmas lo mas parecidas posible entre ellas y se registraron sobre papel de fondo blanco en
un espacio rectangular de 5cm× 11cm, con esfero negro, esto para completar 25 firmas que
denotaremos como originales; con las mismas caracterısticas de papel y esfero, se obtuvieron
falsificaciones divididas en tres grupos de la siguiente forma, cinco falsificaciones por cada
persona, donde el falsificador solo tenia conocimiento del nombre de dicha persona (falsifi-
caciones inesperadas); cinco falsificaciones por persona, donde el falsificador realizo la firma
a la primera vista de la firma original sin tener oportunidad de practica (falsificaciones sin
entrenamiento), y por ultimo, falsificaciones donde el falsificador tuvo previamente entre una
y dos semanas para practicar cada una de las firmas, para luego replicarlas y las denotaremos
como falsificaciones entrenadas amateur.
5.2 Captura de Firmas 41
Figura 5-1: Formato de Captura de Firmas
42 5 Sistemas de Verificacion
El anterior ejercicio permitio recopilar 100 firmas con las caracterısticas anteriormente ex-
puestas, que se resumen ası:
5 usuarios (5 firmantes)
5 firmas originales por usuario (25 firmas originales)
5 falsificaciones inesperadas por usuario (25 falsificaciones inesperadas)
5 falsificaciones sin entrenamiento por usuario (25 falsificaciones sin entrenamiento)
5 falsificaciones entrenadas amateur por usuario (25 falsificaciones entrenadas amateur)
Total de 100 firmas
Figura 5-2: Firma Original
Figura 5-3: Falsificacion Inesperada
5.2 Captura de Firmas 43
Figura 5-4: Falsificacion Sin Entrenamiento
Figura 5-5: Falsificacion Entrenada Amateur
Con las firmas obtenidas de usuarios y falsificadores, se procedio a digitalizar con impresora
multifuncional (funcion de escaner) Epson Stylus CX5600 y almacenar por usuario y tipo de
firma (original o clase de falsificacion). El resultado del procedimiento anterior son imagenes
digitales de las firmas con formato *.png sobre las cuales se inicia el pre-procesamiento.
En el pre-proceso se pueden reconocer dos fases, la primera enfocada al tratamiento de la
firma como una imagen y la segunda enfocada al tratamiento geometrico de la firma, es
decir, a su tamano, a su posicion respecto al origen y al angulo de giro respecto al eje X. Las
dos fases nombradas anteriormente hacen parte del sistema de verificacion, de comparacion
de componentes y del sistema de verificacion basado en Transformada de Radon.
Para los dos sistemas de verificacion se parte del pre-proceso de tratamiento de imagenes
con la firma como una imagen “redimensionalizada”y “esqueletizada”.
44 5 Sistemas de Verificacion
5.3. Comparacion de Componentes
Con la firma como un trazo de un pixel de grosor, lo que se obtiene en terminos de repre-
sentacion matricial, es una matriz de tamano 128× 128 tal que todas sus componentes son
1 o 0. El interes es identificar las posiciones, en la matriz, de cada pixel que conforman el
trazo, lo cual se hace en terminos de algoritmia extrayendo los valores de fila y columna para
cada pixel e ir registrando coordenadas de filas como coordenadas en Y y coordenadas de
columnas como coordenadas en X. Ası el arreglo
S =
[x1 x2 x3 · · · xn
y1 y2 y3 · · · yn
].
contiene coordenadas de pares de puntos de la firma. Seguidamente se aplica el pre-proceso
que consiste en escalar, trasladar y rotar para obtener firmas centradas en el origen, “de un
tamano estandar”y rotadas al mismo angulo. El mismo procedimiento es aplicado a la firma
que se quiere verificar con el fin, como ya se dijo, de tenerlas en las mismas condiciones para
la comparacion.
Dadas dos firmas S y T , pre-procesadas, donde S representa una firma registrada y T una
firma cuya originalidad se quiere verificar, de la extraccion de componentes de cada una de
ellas, se obtiene que:
SX =[a1 a2 a3 · · · an
], SY =
[b1 b2 b3 · · · bn
],
TX =[x1 x2 x3 · · · xm
], TY =
[y1 y2 y3 · · · ym
].
son los vectores de componentes en X y Y de cada una de las firmas a comparar. Como ya
se comento a lo largo del trabajo, el algoritmo de comparacion es el algoritmo DTW con la
distancia euclidiana; que se ejecuta sobre X y Y para obtener el costo respectivo en cada
componente y de esta forma obtener un criterio umbral de aceptacion de firmas originales.
5.3 Comparacion de Componentes 45
Figura 5-6: Coordenadas en X, SX de firma registrada (test) y Coordenadas en X, TX de
firma a verificar (inp)
Figura 5-7: Coordenadas en Y SY de firma registrada (test) y Coordenadas en Y TY de
firma a verificar (inp)
46 5 Sistemas de Verificacion
Figura 5-8: Comparacion de Coordenadas X
Figura 5-9: Comparacion de coordenadas en X
5.3 Comparacion de Componentes 47
Figura 5-10: Comparacion de Coordenadas en Y
Figura 5-11: Comparacion de Coordenadas en Y
48 5 Sistemas de Verificacion
5.3.1. Experimentos
Se realizo la comparacion de firmas originales con firmas originales y firmas originales con
las respectivas falsificaciones, esto para cada una de las componentes X y Y obteniendo
un total de 125 comparaciones por componente por tipo de firma y 500 comparaciones por
componente, ademas se registraron los promedios para cada usuario por cada componente y
tipo de firma, los cuales se presentan a continuacion:
GEN: Representa las firmas originales.
FOR: Representa falsificaciones entrenadas.
NT: Representa falsificaciones no entrenadas pero conociendo previamente la firma.
SV: Representa falsificaciones en las cuales no se tiene conocimiento de la firma original.
Usuario 1 Costos Promedio
GEN vs GEN GEN vs FOR GEN vs NT GEN vs SV
Componentes X 0,014876148 0,007131314 0,057321891 0,064781229
Componentes Y 0,099727114 0,143221474 0,154894988 0,289568438
Usuario 2 Costos Promedio
GEN vs GEN GEN vs FOR GEN vs NT GEN vs SV
Componentes X 0,007672171 0,015199488 0,012132172 0,071876862
Componentes Y 0,018251309 0,016141658 0,029041123 0,359872445
Usuario 3 Costos Promedio
GEN vs GEN GEN vs FOR GEN vs NT GEN vs SV
Componentes X 0,01206367 0,015534301 0,014988728 0,144326709
Componentes Y 0,153479328 0,190644972 0,156610858 0,735396205
Usuario 4 Costos Promedio
GEN vs GEN GEN vs FOR GEN vs NT GEN vs SV
Componentes X 0,010688585 0,021155402 0,014224347 0,023069608
Componentes Y 0,056273501 0,081786417 0,09353762 0,106241198
Usuario 5 Costos Promedio
GEN vs GEN GEN vs FOR GEN vs NT GEN vs SV
Componentes X 0,011313342 0,031507358 0,029397265 0,033621405
Componentes Y 0,088037762 0,188277891 0,180245133 0,288759435
5.3 Comparacion de Componentes 49
Para cada usuario y cada componente se registraron valores no necesariamente en los mismos
rangos, lo cual sugiere que el umbral de aceptacion debe ser diferente para cada uno y en este
caso el sistema requiere de un conjunto de firmas registradas, por persona, que le permita
entrenarse, ademas en los casos de los usuarios 1 y 2 una de las coordenadas presenta mas
“efectividad”que la otra, en el sentido que el costo promedio entre firmas originales es mayor
que el costo promedio entre originales y una tipologıa de falsa. Especıficamente, en el caso
del usuario 1 la comparacion en Y es mas efectiva, ya que el costo promedio en X entre
originales y falsas entrenadas es menor al costo promedio entre originales y en el caso del
usuario 2 la comparacion en X es mas efectiva, ya que el costo promedio en Y entre originales
y falsas entrenadas es menor al costo promedio entre originales.
Aunque uno de los promedios sea mayor que otro, no parece ser un argumento determinante
para afirmar que una de las componentes es mas efectiva que la otra y por lo tanto, pa-
ra obtener mas informacion se calcularon promedios por componente y tipo de firma, sin
discriminacion de usuario, de lo cual se obtuvo que:
Todos los Usuarios Costos Promedio
GEN vs GEN GEN vs FOR GEN vs NT GEN vs SV
Componentes X 0,011322783 0,018105573 0,025612881 0,067535162
Componentes Y 0,083153803 0,124014482 0,122865944 0,355967544
El costo promedio de la comparacion de componentes de firmas originales es menor que el
costo promedio de la comparacion entre componentes de firmas originales y alguna tipologıa
de firma falsa, lo cual permite intuir que los valores de costos de comparaciones entre firmas
originales, para las dos componentes, son menores que los costos de comparaciones entre
originales y falsas. Por esto, se propone revisar algunas medidas de localizacion como los
percentiles de los costos de comparacion entre firmas originales, estableciendo en cada caso,
cuantas firmas originales acepta, es decir, reconoce que son originales y que porcentaje de
firmas falsas acepta, es decir, no reconoce que son falsas y esto ultimo para cada una las
tipologıas de falsas.
50 5 Sistemas de Verificacion
Figura 5-12: Porcentaje de aceptacion por percentil para X
Figura 5-13: Porcentaje de aceptacion por percentil para Y
5.3 Comparacion de Componentes 51
Componente X
Percentil GEN Aceptadas FOR Aceptadas NT Aceptadas SV Aceptadas
5 0 0 0 0
10 0 0 0 0
15 0 0 0 0
20 25 1 0 0
25 31 3 2 0
30 38 4 6 1
35 44 10 7 3
40 50 29 24 11
45 56 34 36 16
50 62 48 42 21
55 69 50 46 23
60 75 52 46 26
65 81 63 54 33
70 87 66 60 41
75 93 71 63 46
80 100 81 73 56
85 106 89 79 59
90 112 106 89 68
95 118 110 100 73
99 124 123 113 91
52 5 Sistemas de Verificacion
Componente X
Percentil FOR Aceptadas NT Aceptadas SV Aceptadas
5 0% 0% 0%
10 0% 0% 0%
15 0% 0% 0%
20 0,8% 0% 0%
25 2,4% 1,6% 0%
30 3,2% 4,8% 0,8%
35 8% 5,6% 2,4%
40 23,2% 19,2% 8,8%
45 27,2% 28,8% 12,8%
50 38,4% 33,6% 16,8%
55 40% 36,8% 18,4%
60 41,6% 36,8% 20,8%
65 50,4% 43,2% 26,4%
70 52,8% 48% 32,8%
75 56,8% 50,4% 36,8%
80 64,8% 58,4% 44,8%
85 71,2% 63,2% 47,2%
90 84,8% 71,2% 54,4%
95 88% 80% 58,4%
99 98,4% 90,4% 72,8%
5.3 Comparacion de Componentes 53
Componente Y
Percentil GEN Aceptadas FOR Aceptadas NT Aceptadas SV Aceptadas
5 0 0 0 0
10 0 0 0 0
15 0 0 0 0
20 25 0 0 0
25 31 6 1 0
30 38 25 15 5
35 44 25 21 5
40 50 25 24 5
45 56 27 26 6
50 62 32 31 10
55 69 35 33 11
60 75 48 40 16
65 81 56 43 17
70 87 58 49 20
75 93 68 66 24
80 100 76 73 32
85 106 83 88 37
90 112 92 99 42
95 118 112 115 54
99 124 125 125 93
54 5 Sistemas de Verificacion
Componente Y
Percentil FOR Aceptadas NT Aceptadas SV Aceptadas
5 0% 0% 0%
10 0% 0% 0%
15 0% 0% 0%
20 0% 0% 0%
25 4,8% 0,8% 0%
30 20% 12% 4%
35 20% 16,8% 4%
40 20% 19,2% 4%
45 21,6% 20,8% 4,8%
50 25,6% 24,8% 8%
55 28% 26,4% 8,8%
60 38,4% 32% 12,8%
65 44,8% 34,4% 13,6%
70 46,4% 39,2% 16%
75 54,4% 52,8% 19,2%
80 60,8% 58,4% 25,6%
85 66,4% 70,4% 29,6%
90 73,6% 79,2% 33,6%
95 89,6% 92% 43,2%
99 100% 100% 74,4%
En el caso de las dos componentes es de notar que en el percentil 25 se obtiene la ultima
aceptacion nula de firmas falsas y estas corresponden a falsificaciones que no tenıan cono-
cimiento de la firma original, aunque para la componente X, en el percentil 30 e incluso
el 35 los porcentajes de aceptacion de falsificaciones siguen siendo relativamente bajos en
comparacion con los porcentajes de aceptacion de falsificaciones en los mismos percentiles
para la componente Y . De igual forma se debe considerar que si se asumen tales porcentajes
como los umbrales de aceptacion, se estan rechazando el 75%, 70% y 65% de las firmas
originales, lo que limita al usuario a hacer pocas variaciones en la firma a verificar, con
respecto al conjunto de firmas registradas, ademas en la medida que se aumente el umbral
de aceptacion, por ejemplo, al percentil 60, se acepta maximo el 41,6% de las falsificaciones
entrenadas por la componente X y maximo el 38,4% de las falsificaciones entrenadas en la
componente Y , que ya corresponde a valores grandes de error.
5.4. Comparacion Basada en Transformada de Radon
Para la comparacion con Transformada de Radon, se aplica el mismo procedimiento de
tratamiento de imagenes al punto de obtener la firma esqueletizada, seguido por el pre-
5.4 Comparacion Basada en Transformada de Radon 55
proceso de escalar, rotar y trasladar. Se definen los parametros NΘ = 19 (numero de angulos)
y Nφ = 185 (numero de rayos), con los cuales se hace el calculo de la Transformada Discreta
de Radon, para la firma registrada y la firma cuya originalidad se quiere verificar y se
registran en matrices R y P de tamano Nφ × NΘ, donde cada una de las columnas de la
matriz representa la transformada o perfil en un angulo especifico. Es de resaltar que cada
una de las firmas se puede considerar como una funcion f(x, y), que representa los valores de
intensidad de la firma en cada punto (x, y) y que cada perfil registra la suma de los aportes
de intensidad en cada pixel dependiendo del angulo en el cual se realice el calculo.
Para cada una de las firmas se calculo la misma cantidad de proyecciones, en los mismos
angulos y se procedio a efectuar la comparacion proyeccion a proyeccion, utilizando el al-
goritmo DTW y ası obtener el costo entre cada una, definido como suma de costos y que
corresponde a la suma de los costos de cada una de las proyecciones en cada angulo.
5.4.1. Experimentos
Debido a que los costos entre firmas varıan en rangos diferentes, no es conveniente proponer
un umbral general basado en los valores obtenidos para un usuario, esto se observa en los
resultados obtenidos donde los costos entre dos firmas originales del usuario 1 es 2006.653664
mientras que entre dos firmas originales del usuario 3 es de 4408.265677. Con el objetivo de
proponer un criterio de aceptacion-rechazo consideraremos lo siguiente: i) calcular los costos
entre firmas originales, ii) calcular el promedio entre costos de firmas originales, iii) calcular
las razones entre costos de firmas originales, iv) calcular el promedio entre tales razones y v)
calcular la razon entre el costo de una firma original y una falsa, y el promedio de los costos
de firmas originales.
Para determinar lo anterior se proponen porcentajes de falsas rechazadas, falsas aceptadas
como si fuesen originales, originales rechazadas como si fuesen falsas y originales verificadas
como verdaderas.
56 5 Sistemas de Verificacion
Usuario 1 Usuario 2 Usuario 3 Usuario 4 Usuario 5
Promedios
de costos
entre firmas
originales
3090,215582 5701,308481 7127,362424 1989,580711 2658,736370
Tabla 5-1: Costo Promedio Por Usuario
La Tabla 5-1 permite evidenciar que, como se dijo anteriormente, el promedio de los costos
entre firmas originales de un mismo usuario no permite establecer un criterio de comparacion
general para cualquier firma debido a que, por ejemplo, el promedio del Usuario 3 serıa alto
para el resto de usuarios y el promedio del Usuario 4 es bajo para los otros usuarios. Por lo
tanto, se sugieren criterios umbral para cada una de las firmas. En la tabla anteriormente
citada estan los pasos i) y ii) hasta obtener el promedio de costos entre firmas originales.
Usuario 1 Usuario 2 Usuario 3 Usuario 4 Usuario 5
Promedios de
razones entre
costos
1,05912156 1,90642998 1,03426763 1,01816508 1,04467234
Tabla 5-2: Razon Promedio Por Usuario
La Tabla 5-2 muestra los promedios de las razones entre costos de firmas originales para
cada usuario, exponiendo lo propuesto en los numerales iv) y v) y ademas sugiere valores
umbral para la aceptacion-rechazo de firmas.
A diferencia del Usuario 2, los valores promedio de las razones, son valores cercanos a 1, lo
cual se hace explıcito en el siguiente razonamiento. Los costos entre firmas originales de un
mismo usuario, intuitivamente, esperarıamos que fuesen cercanos a 0, lo cual se interpretarıa
como que efectivamente proceden de la misma persona y aunque esto no necesariamente
se da, los resultados obtenidos a partir de los costos entre firmas originales de un mismo
usuario, son valores “cercanos”entre si, y por tanto las razones entre dichos costos tienen
media cercana a uno con baja variabilidad, dados sus coeficientes de variacion (Tabla 5-3).
Usuario 1 Usuario 2 Usuario 3 Usuario 4 Usuario 5
Coeficientes
de Variacion
Entre Costos
de Razones
0,392637939 1,101958123 0,313244328 0,187832157 0,251971446
Tabla 5-3: Coeficientes de Variacion
5.4 Comparacion Basada en Transformada de Radon 57
Es en este orden, que el promedio de costos entre firmas originales CG es utilizado para el
calculo de razones entre costos de firmas originales/falsas y firmas originales, ası obtenemos
el cociente,
C
CG
donde C representa el costo entre un par de firmas (original-original u original-falsa) y CG
representa el promedio de costos entre firmas originales. Dado que los costos no son valores
negativos, la razon no puede ser un valor negativo y ademas si C < CG se tiene que CCG
< 1,
que indica que el costo C calculado entre firmas es mas pequeno que el promedio y por tanto
se puede considerar la firma analizada como original. Para obtener un valor umbral que
no exija que necesariamente los costos sean mas pequenos que el promedio, se calculan las
razones entre los costos de firmas originales con firmas originales, esto es, dado un conjunto
de firmas originales FG = {F1, F2, ..., FN} con los respectivos costos entre ellas C(Fi, Fj) para
todo i, j = 1, 2, ..., N con i = j, obtenemos el conjunto RG de las razones entre costos de
firmas originales; donde su respectiva media es RG ≈ 1, luego si tenemos,
C(Fi, FI)
CG
≤ RG
para una firma FI a verificar, esta sera aceptada como una firma original.
Los resultados obtenidos corresponden a los porcentajes de aceptacion para cada una de las
tipologıas de cada uno de los usuarios.
Transformada de Radon
Usuario
Valor Um-
bral (Razon
Promedio)
GEN Acep-
tadas
FOR Acep-
tadas
NT Acepta-
das
SV Acepta-
das
1 1,05912156955 68% 28% 0% 0%
2 1,90642998409 76% 84% 80% 72%
3 1,03426763425 60% 52% 24% 8%
4 1,01816508893 68% 0% 0% 0%
5 1,04467234766 60% 48% 32% 0%
6 Conclusiones y recomendaciones
6.1. Conclusiones
Como se dijo anteriormente, los sistemas off-line permiten realizar verificaciones de firmas
impresas sobre documentos, por lo cual, resulta practico debido a que puede prestar gran
variedad de servicios en instituciones con actividades de validacion de documentos. Esto
requiere de implementar un sistema compuesto, que contenga sistemas con los cuales se
realicen diferentes reconocimientos de patrones caracterısticos de la firma con el fin de tener
un amplio espectro de analisis.
La descomposicion, por componentes X y Y , de cada una de las firmas resulto como algo
ventajoso debido, precisamente, a que permite tener las dos series para comparar, por lo cual
las diferencias que no se puedan detectar con una de las componentes pueden resaltarse con
la otra, ası, el valor umbral de comparacion, es un factor compuesto de los valores umbral
para cada una de las componentes, de tal forma que una firma es aceptada como genuina si
es verificada en sus componentes de X y Y .
A diferencia de la comparacion de componentes con el algoritmo DTW, la transformada de
Radon proporciona los perfiles de distribuciones de intensidades de la firma, a la cantidad
de angulos que se considere conveniente, con el fin de tener mas informacion acerca de la
misma y aunque se propuso un ındice de comparacion, se pueden establecer otras formas de
establecer una medida.
Se evidencio que no necesariamente alguna de las dos metodologıas tiene mas efectividad que
la otra, dados los porcentajes de aceptacion por usuario. Aunque es pertinente obtener resul-
tados a partir de una muestra mas grande de firmas, considerando que mas que un desarrollo
estadıstico sobre determinacion de umbrales de aceptacion-rechazo, el interes central fue la
implementacion de las metodologıas. Por los porcentajes de aceptacion de falsificaciones que
se tuvo con las dos metodologıas, se induce que se puede establecer la susceptibilidad, de
una determinada firma, a ser falsificada.
Para la implementacion de un sistema de verificacion practico, este debe constar de por lo
menos dos metodologıas que en lo posible generen diferentes tipos de analisis sobre la firma,
es decir, si la metodologıa de comparacion basada en DTW permite analizar la geometrıa
de la firma, la comparacion basada en transformada de Radon permite comparar los perfiles
de distribucion de puntos de la firma.
6.2 Recomendaciones y Trabajos Futuros 59
6.2. Recomendaciones y Trabajos Futuros
Se proponen principalmente dos recomendaciones que pueden dar origen a otros posibles
desarrollos y complementos practicos.
En pro de determinar un valor umbral “mas” preciso se propone construir una base de firmas
mas extensa, con el fin de proponer un analisis estadıstico mas exhaustivo.
En la diferenciacion entre sistemas on-line y off-line se comento acerca de la facilidad con
que los sistemas on-line permiten analizar variables que son de dificultad para analizar en
los sistemas off-line. Una de ellas corresponde a la presion que ejerce la punta del lapiz, en
general, sobre la superficie sobre la cual se firma mientras que en los sistemas on-line es una
variable que se captura de forma inmediata, en los sistemas off-line es una variable que podrıa
ser analizada examinando las intensidades de cada uno de los pixeles que corresponden a la
firma.
El trabajo fue aceptado como una presentacion oral en el International Conference on Applied
Mathematics and Informatics ICAMI 2013 en las tematicas de investigacion de operaciones,
optimizacion y aplicaciones.
Bibliografıa
[1] H. Baltzakis and N. Papamarkos. A new signature verification technique based on a
two-stage neural network classifier. Engineering Applications of Artificial Intelligence,
14:95–103, 2001.
[2] Richard D. Sabourin R. Granger E. Batista, L. and P. Maupin. Pattern Recognition
Technologies and Applications: Recent Advances. IGI Global, 1st edition, 2007.
[3] G. Beylkin. Discrete radon transform. IEEE Transactions on Acoustics, Speech and
Signal Processing, 2, 1987.
[4] Herbst B. Coetzer, J. and J. du Preez. Off-line signature verification using the discrete
radon transform and hidden markov model. Journal on Applied Signal Processing,
4:559–571, 2004.
[5] J. Coetzer. Off-line Signature Verification. Phd thesis, University of Stellenbosch, 2005.
[6] Stanley R. Deans. The Radon Transform and Some of its Applications. John Wiley &
Sons, 1983.
[7] Proakis J.G. Deller, J.R. and J.H. Hansen. Discrete-time processing of speech signals.
IEEE, 1999.
[8] Jga Dolfing. Handwriting recognition and verification. A hidden Markov approach. Phd
thesis, Eindhoven University of Technology, 1998.
[9] Flavio Bortolozzi Robert Sabourin Edson J. R. Justino, Abdenaim El Yacoubi. An
off-line signature verification system using hidden markov model and cross-validation
computer graphics and image processing. Proceedings XIII Brazilian Symposium on.
[10] Leung C.H. Tang Y.Y. Tse K.W. Kwok P.C.K. Wong Y.K. Fang, B. Off-line signature
verification by the tracking of feature and stroke positions. The Journal on the Pattern
Recognition Society, 2003.
[11] Wang Y.Y. Leung C.H. Fang, B. and K.W. Tse. Off-line signature verification by the
analysis of cursive strokes. International Journal of Pattern Recognition and Artificial
Intelligence.
Bibliografıa 61
[12] Liwicki M. & Bunke H. Recognition of witheboard notes online, offline and combination.
series in machine perception and artificial intelligence, world scientific.
[13] William H. Discrete radon transform has an exact, fast inverse and generalizes to
operations other than sums along lines. Los Alamos National Laboratory, 2006.
[14] Coetzer H. Herbst B. On an off-line signature verification system. 2006.
[15] Kunze R. Hoffman K. Algebra Lineal. Prentice Hall, 1971.
[16] Mantilla I. Analisis Numerico. Universidad Nacional de Colombia, Bogota, 2004.
[17] Burden R. & Douglas J. Analisis Numerico. CENGAGE Learning.
[18] Campisi P. Maiorana, E. and A. Neri. Biometric signature authentication using Radon
transform-based watermarking tecniques. 2007.
[19] Bozza S. Schmittbuhl M. Taroni F. Marques, R. Handwriting evidence evaluation based
on the shape of characters: Application of multivariate likelihood ratios. Journal of
Forensic Sciences, 2006.
[20] M. Muller. Information Retrieval for Music and Motion. Springer, 2007.
[21] Du Preez J.A. Nel, E-M. and B.M. Herbst. Estimating the pen trajectories of static
signatures using hidden markov models. IEEE Transactions on Pattern Analysis and
Machine Intelligence.
[22] Coetzer H. Panton, M. Off-line signature verification using ensembles of local radon
transform-based hmms. 2010.
[23] M. Panton. Off-line signature verification using ensembles of local radon transform-
based hhms. Master’s thesis, University of Stellenbosch, 2010.
[24] Richard E. Woods Rafael C. Gonzalez. Digital Image Processing. Pearson. Prentice
Hall, third edition, 2008.
[25] P. Senin. Dynamic Time Warping Algorithm Review. University of Hawaii at Manoa,
2008.
[26] William F. Sinden. Method of normalizing handwritten symbols. European patent
application 0 581 529 A2, 2006.
[27] Hamdy A. Taha. Investigacion de operaciones, quinta edicion. Alfaomega, 5 edition,
1995.
[28] P. Toft. The Radon Transform - Theory and Implementation. Phd thesis, Technical
University of Denmark, 1996.
62 Bibliografıa
[29] Jozsef Valyon and Gabor Horvath. A hybrid intelligent system for image matching, used
as preprocessing for signature verification. In 5th International Conference on Artificial
Neural Networks and Genetic Algorithms, 2001.