desarrollo de programas 1 authenticasoft. contenido definición del problema algoritmos de...
TRANSCRIPT
EXPERIMENTACIÓN NUMÉRICA
Desarrollo de Programas 1AuthenticaSoft
ContenidoDefinición del problemaAlgoritmos de comparación de firmasAlgoritmos de comparación de huellasPlaneación del experimentoEjecución y análisisResultadosConclusiones
Definición del problemaCASO: Validación de padrones electorales El proceso de comparación de firmas y
huellas en las actas se realizan de manera manual y utilizando muestras aleatorias.
Dificultades: Gran cantidad horas personas Alta posibilidad de cometer errores
Algoritmos de comparación de firmasAlgoritmo basado en esqueletización y
emparejamiento de distancias
1) Extracción de trazos con búsqueda completa2) Conformación de estructura3) Análisis bajo esquema de emparejamiento de
distancias4) Decisión
Algoritmos de comparación de firmasAlgoritmo para la verificación de firmas
mediante emparejamiento en un grafo1) Eliminación de ruido y
adelgazamiento de las líneas que conforman la firma
2) Determinación de puntos críticos de cada firma
3) Matriz de correspondencia de las distancias entre los puntos críticos, unificando los puntos críticos de las 2 firmas en esta matriz
Algoritmos de comparación de huellasAlgoritmo de verificación de huellas
usando el árbol de expansión mínimo1) Encontrar las minucias en
la imagen de la firma2) Crear un grafo con las
minucias encontradas3) Generar un árbol de
expansión mínima4) Basadas en las distancias
euclidianas de cada punto, comparar los costos de cada MST y decidir si es aceptable o no.
Algoritmos de comparación de huellasAlgoritmo de verificación de huellas
basado en la comparación de minucias1) Ubicar el centro
aproximado2) Extraer marcos de n x n
píxeles en forma paralela entre las dos imágenes
3) Compararlas simultáneamente usando un índice de similitud por marco de comparación del 70%
4) Determinar resultado de comparación
Planeación del experimentoModelo estadístico a utilizar : T-Student
( varianza conocida )
Planeación del experimentoExperimento Nro 1Datos de entrada
Planeación del experimentoExperimento Nro 2Datos de entrada
Ejecución y análisisExperimento 1 :
H0: El algoritmo para la verificación de firmas basado en esqueletización y emparejamiento de distancias obtiene un porcentaje de aciertos de comparación igual que el algoritmo mediante Emparejamiento en un Grafo.
H0: μ1 = μ2H1: El algoritmo para la verificación de firmas mediante
Emparejamiento en un Grafo obtiene un mejor porcentaje de aciertos de comparación que el algoritmo basado en esqueletización y emparejamiento de distancias.
H0: μ2 > μ1
Las variables a utilizar son: X1= porcentaje de aciertos de comparación del algoritmo basado en
esqueletización y emparejamiento de distancias.X2= porcentaje de aciertos de comparación del algoritmo para la
verificación de firmas mediante Emparejamiento en un Grafo. Considerando: μ1= porcentaje de aciertos de comparación promedio del algoritmo
basado en esqueletización y emparejamiento de distancias. μ2 = porcentaje de aciertos de comparación promedio del algoritmo
para la verificación de firmas mediante Emparejamiento en un Grafo.
Ejecución y análisisExperimento 2 :
Las hipótesis para este experimento son: H0: El algoritmo para la verificación de huellas que usa el árbol de
expansión obtiene un porcentaje de aciertos de comparación igual que el algoritmo basado en la comparación de minucias.
H0: μ1 = μ2
H1: El algoritmo para la verificación de huellas basado en la comparación de minucias, no obtiene un mejor porcentaje de aciertos de comparación que el algoritmo que usa el árbol de expansión
H0: μ2 > μ1
Ejecución y análisisLas variables a utilizar son: X1= porcentaje de aciertos de comparación del algoritmo para la
verificación de huellas usando el árbol de expansión mínimo. X2= porcentaje de aciertos de comparación del algoritmo para la
verificación de huellas basado en la comparación de minucias. Considerando: μ1 = porcentaje de aciertos de comparación promedio del algoritmo para
la verificación de huellas usando el árbol de expansión mínimo. μ2= porcentaje de aciertos de comparación promedio del algoritmo para la
verificación de huellas basado en la comparación de minucias.
ResultadosExperimento 1
FIRMA ACIERTOS
DESACIERTOS
PORCENTAJE DE ACIERTOS
Firma1 4 4 0.4
Firma2 3 6 0.3Firma3 5 5 0.5Firma4 4 4 0.4Firma5 4 4 0.4Firma6 5 4 0.5Firma7 6 5 0.6Firma8 3 6 0.3Firma9 4 5 0.4Firma10 3 5 0.3Firma11 4 5 0.4Firma12 4 5 0.4Firma13 5 4 0.5Firma14 3 5 0.3Firma15 3 3 0.3Firma16 5 5 0.5Firma17 3 6 0.3Firma18 2 6 0.2Firma19 4 6 0.4Firma20 4 6 0.4
Media (u2)0.3894736
8
Desviación estándar (S2)0.0994134
8
Algoritmo basado en esqueletización y emparejamiento de distancias
ResultadosExperimento 1
Media (u2) 0.505Desviación estándar (S2) 0.088704121
FIRMA ACIERTOS DESACIERTOS PORCENTAJE DE ACIERTOSFirma1 6 4 0.6Firma2 4 6 0.4Firma3 5 5 0.5Firma4 6 4 0.6Firma5 6 4 0.6Firma6 6 4 0.6Firma7 5 5 0.5Firma8 4 6 0.4Firma9 5 5 0.5
Firma10 5 5 0.5
Firma11 5 5 0.5
Firma12 5 5 0.5
Firma13 6 4 0.6
Firma14 5 5 0.5
Firma15 7 3 0.7
Firma16 5 5 0.5
Firma17 4 6 0.4
Firma18 4 6 0.4
Firma19 4 6 0.4
Firma20 4 6 0.4
Algoritmo para la verificación de firmas mediante emparejamiento en un grafo
El valor 1.691 se halla en la tabla t-Student con los grado de libertad n1+n2 -2 una probabilidad de 0.95 de acuerdo al definido= 5 % que es la probabilidad
de rechazar Ho siendo esta cierta."Como t = 1.691 > 0.867 se acepta Ho"
Calculamos el valor del estadístico t, en base a la media y desviación estándar:
ResultadosExperimento 2 Algoritmo de verificación de
huellas usando el árbol de expansión mínimoHUELLA ACIERTOS DESACIERTOS PORCENTAJE DE ACIERTOS
Huella1 4 2 0.4Huella2 5 5 0.5Huella3 4 2 0.4Huella4 4 3 0.4Huella5 6 1 0.6Huella6 5 3 0.5Huella7 7 1 0.7Huella8 3 2 0.3Huella9 5 7 0.5Huella10 4 2 0.4Huella11 6 6 0.6Huella12 6 2 0.6Huella13 4 4 0.4Huella14 3 1 0.3Huella15 5 5 0.5Huella16 6 2 0.6Huella17 3 1 0.3Huella18 4 4 0.4Huella19 4 2 0.4Huella20 5 4 0.5
Media (u2) 0.465
Desviación estándar (S2)0.1136708
1
t 3.877741531n1 20n2 20
ResultadosExperimento 2 Algoritmo de verificación de
huellas basado en la comparación de minucias
HUELLA ACIERTOS DESACIERTOS PORCENTAJE DE ACIERTOS
Huella1 8 2 0.8Huella2 5 5 0.5Huella3 8 2 0.8Huella4 7 3 0.7Huella5 9 1 0.9Huella6 7 3 0.7Huella7 9 1 0.9Huella8 8 2 0.8Huella9 3 7 0.3Huella10 8 2 0.8Huella11 4 6 0.4Huella12 8 2 0.8Huella13 6 4 0.6Huella14 9 1 0.9Huella15 5 5 0.5Huella16 8 2 0.8Huella17 9 1 0.9Huella18 6 4 0.6Huella19 8 2 0.8Huella20 6 4 0.6
Media (u2) 0.705
Desviación estándar (S2)0.1761428
8
t 5.11988024n1 20n2 20
El valor 1.691 se halla en la tabla t-Student con los grado de libertad n1+n2 -2 una probabilidad de 0.95 de acuerdo al definido= 5 % que es la probabilidad de rechazar Ho siendo esta cierta.
"Como t = 1.691 > 1.14484002 se acepta Ho"
ConclusionesExperimento 1
Dado que se pueden utilizar los dos algoritmos por su grado de confiabilidad, la característica que determinaría cual realmente usar, sería el que posea una complejidad en tiempo y en memoria menor, debido a esto, se utilizaría el segundo algoritmo, dada su confiabilidad y bajo tiempo en ejecución.
ConclusionesExperimento 2
Dado que se pueden utilizar los dos algoritmos por su grado de confiabilidad, la característica que determinaría cual realmente usar, sería el que posea una complejidad en tiempo y en memoria menor, debido a esto, se utilizaría el primer algoritmo, dada su confiabilidad y bajo tiempo en ejecución y la diferencia mencionada en la interpretación de los resultados.