Download Grafística Forense

Tecnología Biométrica:
Escritura Manuscrita
“Writer ID”
Juan Alberto Sigüenza
[email protected]
Tabla de Contenidos
Áreas relacionadas
Grafística Forense
Características Computacionales
Otros trabajos relevantes
Ejemplo de Aplicación de Identificación
Áreas relacionadas
Tratamiento Digital de Imágenes (Digital Image Processing)
-Fundamentos de Imágenes Digitales
Elementos de la Percepción Visual, Muestreo y Captura de imágenes, Geometría de
Imágenes, etc.etc.
-Transformaciones de Imágenes
Transformada de Fourier, FFT, DFT, Trasformada Coseno, etc.etc.
-Mejora de Imágenes
Dominio espacial, dominio frecuencial, filtros, histogramas, máscaras, uso del color,
etc.etc.
-Restauración de Imágenes
Modelos de degradación, diagonalización de matrices, aprox. algebráicas, filtros
inversos, etc.etc.
Áreas relacionadas
Tratamiento Digital de Imágenes (Digital Image Processing)
-Compresión de Imágenes
Estándares, teoría de la información, compresión con/sin pérdida de información,
etc.etc.
-Segmentación de Imágenes
Detección de discontinuidades, enlace de bordes, detección de límites, umbrales,
regiones, etc.etc.
-Representación y Descripción
Esquemas de representación, descriptores de bordes, descriptores regionales, morfología,
etc.etc.
-Reconocimiento e Interpretación
Análisis de imágen, Reconocimiento de Patrones, Métodos estructurales, Redes Neuronales,
etc.etc.
Áreas relacionadas
Reconocimiento de Escritura (Handwriting Recognition)
-Tienen como objetivo transformar textos manuscritos o mecánicos desde su formato 2D
espacial en papel a una forma simbólica i.e. a un formato digital útil para el ordenador. Se
busca que el ordenador reconozca las palabras del texto, no identificar al autor.
-La principal aplicación de estas técnicas es el desarrollo de sistemas de Reconocimiento
Óptico de Caracteres (OCR, Optical Character Recognition) para convertir la escritura
manuscrita en texto digital.
-Módulos básicos de un OCR:
-Preprocesamiento.
-Segmentación de Caracteres.
-Reconstrucción de segmentaciones.
-Reconocimiento de caracteres.
-Construcción de palabras o frases.
Áreas relacionadas
Reconocimiento de Escritura (Handwriting Recognition)
-El National Institute of Standards and Technology (NIST) empezó a testear ‘large-scale’ OCRs en
1989, y los resultados de la primera conferencia de sistemas OCR mostró ya la aplicabilidad de un gran
número de técnicas de reconocimiento de patrones para solucionar el problema del reconocimiento de
caracteres. Algunas como las Redes Neuronales Artificiales son los sistemas más comunes y de mayor
precisión.
-Clases de sistemas de reconocimiento de escritura según el tipo de dispositivo de adquisición de
datos:
-Sistemas On-line  basados en tabletas digitalizadoras normalmente
-Sistemas Off-line basados en escáner normalmente
<<<<<<<<<<<< Writer ID (uso forense)
-Re-utilización con Writer ID:
-Técnicas de representación del conocimiento o características (features)
-Técnicas de preprocesamiento
-Técnicas de reconocimiento de patrones
Experiencia previa:
El proyecto RAMA
• Reconocimiento de caracteres manuscritos
españoles.
• Base de datos de mas de 300.000 caracteres.
• Palabras segmentadas mediante casillas.
• Redes neuronales para clasificación.
• Diccionarios asociados.
• Instalado en numerosas aplicaciones.
Grafística Forense
La grafística es la disciplina forense que tiene como objetivo la identificación o autenticación de los
autores de manuscritos. Se centra por tanto en el análisis de documentos escritos a mano por el
individuo utilizando algún tipo de utensilio de escritura (lápiz, bolígrafo, pluma, ...). La biometría de
la escritura o identificación de escritor tiene como objetivo el desarrollo de sistemas informáticos
que puedan desempeñar esta tarea de manera automática.
Nota: no confundir grafística con grafología que es la extracción de conclusiones sobre el perfil
psicológico del autor de la escritura.
La identificación grafística es un método comúnmente utilizado por los cuerpos policiales y fuerzas
del orden público a lo largo y ancho de todo el mundo, datándose las primeras utilizaciones de estas
técnicas desde el año 1600. Diferentes técnicas han sido desarrolladas por los científicos forenses con
el objetivo de verificar o identificar criminales y terroristas usando multitud de diferentes
características de la escritura reflejada en manuscritos. Los aspectos metodológicos de la
identificación grafística han sido ampliamente estudiados desde hace tiempo por los expertos forenses
(examinadores) como por ejemplo en los trabajos de:
1. H. Hardy and W. Fagel, “Methodological aspects of handwriting identification,”
Journal of Forensic Document Examination, Fall, 1995.
2. R. A. Huber and A. M. Headrick, Handwriting identification: facts and fundamentals.
Ed. CRC Press, 1999.
Grafística Forense
Interés policial y judicial desde dos enfoques: verificación e identificación.
La verificación se refiere a los casos en los que los científicos forenses tienen que trabajar con pruebas
en forma de documentos manuscritos que deben comparar uno frente a otro para contrastar su
autenticidad.
“1 doc. dubitado vs. 1 doc. indubitado”
Tipos de documentos dubitados:
- contratos,
- testamentos,
-firmas,
- anónimos,
- Etc. etc.
Se pretende averiguar si son auténticos comparándolos con una muestra validada del autor original del
que se supone que proceden i.e. un documento indubitado. Típicamente dicha muestra validada es
tomada por un agente de policía o judicial al sujeto en cuestión y se compone de diferentes elementos
de escritura: firma, nombre y apellidos, escritura natural en mayúsculas, en minúsculas y distintos
números.
Grafística Forense
Por otro lado, la identificación se refiere a
comparar un documento (dubitado) frente a N
documentos (indubitados, autenticados) i.e. N
será un número elevado, típicamente la población
total o grupo de individuos sobre el que queremos
identificar al individuo dubitado. Este podría ser
el caso de intentar identificar a un criminal o
terrorista entre un grupo de sospechosos,
suponiendo que disponemos de muestras
indubitadas de escritura de los mismos.
“1 doc. dubitado vs. N doc. indubitados”
Ejemplo de Doc. Indubitado
Grafística Forense
Características Forenses de los Documentos
Ejemplo, los “21 Elementos Discriminantes” de Huber & Headrick:
A.
Elementos de Estilo (características lúcidas o explícitas)
1.
Alineación. Márgenes, separación de líneas, paralelismo, indentaciones, etc.
2.
Clase de letra. Cursiva, manuscrito, impreso, composición, etc.
3.
Conexiones. Entre palabras, entre letras dentro de palabras.
4.
Diseño de alfabeto/letras & construcción. Sistema de escritura extranjero, local,
particular, tipo de numeración, naturaleza, posición, direcciones de trazos, ligaduras,
etc. Variaciones y desviaciones respecto del estándar, combinaciones, etc.
5.
Dimensiones (horizontal y vertical). Proporciones dentro del mismo carácter, tamaño
relativo entre diferentes caracteres, tamaño absoluto, etc.
6.
Inclinación. De toda la escritura, de letras o de partes de letras.
7.
Espaciado. Entre-palabras y dentro-de-palabras (entre letras).
Grafística Forense
Características Forenses de los Documentos
B.
Elementos de ejecución (características subyacentes, implícitas u ocultas)
8.
Abreviaturas. Eliminación de letras acortando palabras, combinaciones de letras, etc.
9.
Alineamiento base.
10. Trazos iniciales & finales.
11. Puntuación. Presencia, estilo, colocación.
12. Embellecimientos.
13. Legibilidad & calidad de la escritura.
14. Continuidad de líneas.
15. Calidad de líneas.
16. Control de la pluma/lápiz. Presión, sujección, decaida tinta.
17. Movimientos decorativos de la escritura. Dirección de reloj o inversa, arqueado,
angular, interminable.
Grafística Forense
Características Forenses de los Documentos
C.
Atributos de todos los tipos de hábitos de escritura
18. Variaciones naturales y Consistencia. Precisión con que los hábitos son
ejecutados y repetidos.
19. Persistencia. Frecuencia con que determinados hábitos se usan.
D.
Combinaciones de hábitos de escritura
20. Expansión lateral. Contracción/expansión de letras y espacios blancos.
21. Proporciones de las palabras. Relación alto por ancho de palabra.
Grafística Forense
Técnicas de Identificación por Formulación Grafonómica
Formas de Alógrafos (allographs) = diseño o forma de la letra
Características Computacionales
CEDAR
Center of Excellence for Document Analysis and Recognition
“Handwriting Identification: Research to Study Validity of
Individuality of Handwriting & Develop Computer-Assisted
Procedures for Comparing Handwriting”.
Sargur N. Srihari.
Technical Report CEDAR-TR-01-1. Center of Excellence on
Document Analysis and Recognition (CEDAR). State University of
New York at Buffalo. February 26, 2001.
Características Computacionales
Base de Datos: muestra representativa de la población de EE.UU.
constituida por 1.128 voluntarios, que hicieron 3 repeticiones sobre un
folio en blanco de un mismo texto fijo, la “CEDAR letter”.
Diferentes edades, grupos étnicos, sexo, nivel cultural y estudios.
La “CEDAR letter” tenía 156 palabras cubriendo los diferentes
caracteres del alfabeto latino, en minúsculas al inicio, fin o medio de
palabras y con mayúsculas de inicio de palabra.
Se basó en la “london letter” y la “dear sam letter”.
Ejemplo:
Proceso de Digitalización & Segmentación:
Proceso de Digitalización & Segmentación:
Diferentes Niveles de Características Estudiados
Diferentes Niveles de Características Estudiados
1. Nivel de Documento:
3. Nivel de palabra:
• Entropía de niveles de gris.
• Umbral de nivel de gris.
• Número de píxeles negros.
• Número de contornos interiores y
exteriores.
• Número de componentes de curvatura de 4
direcciones.
• Altura media.
• Inclinación media.
•Número de píxeles negros.
•Número de contornos interiores y exteriores.
•Número de componentes de curvatura de 4 direcciones.
•Altura media.
•Inclinación media.
•Longitud.
•Ratio entre la zona superior y la inferior
2. Nivel de Párrafo:
•Número de píxeles negros
•Ratio de aspecto
•Ratio de altura y anchura del centroide.
•Características espaciales.
•Características GSC (Gradient, Structural, Concavity)
• Número de pixeles negros.
• Número de contornos interiores y
exteriores.
• Número de componentes de curvatura de 4
direcciones.
• Altura media.
• Inclinación media.
• Ratio de aspecto.
• Ancho de margen.
4. Nivel de carácter:
Rendimiento de Diferentes Niveles de Características
Ejemplos: Binarización (Algoritmo de Otsu)
Ejemplos: Contornos
Contornos Exteriores (color rosa) e interiores (color negro):
Dos ejemplos distintos de letra ‘O’:
Ejemplos: Nivel de Párrafo
Proporciones del Párrafo de dirección: (‘address’, hay 2 por ‘letter’)
Ejemplos: Nivel de Palabra
Zonas y líneas clave de Palabra:
Ejemplos: Nivel de Caracter
Características GSC de Carácter: Gradient, Structural, Concavity
Otros Trabajos Relevantes
Tan, Baker et al (2000) : sistema independiente del
texto en concreto que se utilice. Trabajaban con textos
escritos sobre hojas en blanco por individuos, de manera
que las palabras habitualmente aparecían con distintas
inclinaciones y separaciones en el mismo texto (p.e.
líneas torcidas). Tomaron para ello una aproximación
basada en análisis de texturas.
El trabajo de Tan y Baker estuvo basado en los
experimentos de Kuckuck (1980) donde se utilizaba una
técnica de Fourier. Los autores utilizaron técnicas de
filtros multicanal espaciales para extraer las
características de la textura de las imágenes de escrituras.
En la investigación Tan y Baker usaron filtros de Gabor.
También utilizaron matrices de co-ocurrencia de escalas
de grises (Gray Scale Co-ocurrence Matrices, GSCM)
para la extracción de características y dos técnicas
diferentes de clasificación para identificar escritores:
distancias euclídeas ponderadas (Weighted Euclidean
Distances, WED) y el tradicional clasificador de “Kvecinos próximos” (K-Nearest Neighbor, K-NN).
Otros Trabajos Relevantes
Las normalizaciones fueron realizadas
utilizando los perfiles de proyección
horizontal y vertical, los cuales no son más
que histogramas del número de píxeles
negros que corresponden a un determinado
punto sobre la horizontal / vertical. Con los
máximos y picos de dichos histogramas de
proyección se puede estimar la ubicación e
inclinación de las líneas de palabras
(vertical). Dentro de una línea en concreto se
puede estimar la posición de las palabras
(horizontal) para aislarlas y procesarlas.
Los dos clasificadores considerados, WED y
K-NN, fueron ampliamente testados con
diferentes experimentos llevados a cabo para
10 escritores voluntarios. Se consiguió una
precisión de identificación del 96% con 150
documentos de test.
Ejemplo de Aplicación de Identificación
Objetivo: eliminar los problemas de la subjetividad de formulación
Ejemplo de Aplicación de Identificación
Digitalización & Segmentación
Componentes conexas
Ejemplo de Aplicación de Identificación
Explotación intensiva de Características de Nivel Caracter
G
GSC Features
SSu objetivo es detectar características “multi-resolución” i.e. se fijan en el pixel (x,y) y luego en relaciones de este con sus
vecinos de menor a mayor proximidad (de local a global, distancias). GSC features viene de Gradient (gradiente),
Structural (estructural) y Concavity (concavidad).
1.
2.
3.
Nivel local: Gradient features. Forma de los trazos, bajo tamaño.
Nivel intermedio: Structural features. Trayectoria de los trazos.
Nivel global: Concavity features. Relación entre trazos, cross-image. Detección de concavidades en la letra.
CComo unidad de área se utiliza una estrategia de malla i.e. la imágen de la letra (independientemente de su tamaño) se
divide en una malla de 4x4 celdas sobre las que computar o contabilizar las features.
Ejemplo de Aplicación de Identificación
Gradient Features
Las gradient features serán un vector de features cuyo cálculo se basa en calcular el gradiente (derivada)
en la imágen de la letra. Para cada punto (x,y) tendremos un valor de imágen f(x,y), el valor del vector
gradiente en ese punto será un vector cuyas componentes serán las derivadas parciales de f(x,y) respecto
de cada componente x e y..
Se utiliza una aproximación del cálculo del gradiente mediante operadores de Sobel.
Se convolucionarán dos operadores de Sobel de 3x3, los cuales aproximarán las derivadas parciales de x
& y en la posición del pixel en la imágen. Fijado un pixel se consideran sus vecinos de la siguiente
manera:
Ejemplo de Aplicación de Identificación
LLos operadores de Sobel se enmarcan dentro del campo de los filtros espaciales, que a diferencia de los filtros
espectrales basados en descomposición de frecuencias de Fourier, son filtros que se realizan aplicando máscaras
de coeficientes sobre pixels y sus vecinos. En concreto los operadores de Sobel se refieren a filtros lineales i.e.
que su resultado es una combinación lineal de los valores de los pixels y los coeficientes de la máscara espacial.
ww1 w2 w3
ww4 w5 w6
ww7 w8 w9
+
z1 z2 z3
z4 z5 z6
z7 z8 z9
dará como resultado R = Σ 9i=1 ( wi zi )
cCon wi los coeficientes de la máscara espacial a aplicar y zi los valores de los pixels.
OObservación: es un derivative filter. La idea es que:
1.
2.
promediar es una aproximación a integrar que equivale a “difuminar” la imágen.
diferenciar es una aproximación a derivar que equivale a “definir” la imágen.
Ejemplo de Aplicación de Identificación
Ejemplo de Aplicación de Identificación
Para la malla de 4x4 celdas en que se divide la imágen de la
letra, se calcula el gradiente en cada celda, haciéndose un
histograma de cuántas veces se da cada región de dirección
posible. Para cada celda se genera un vector de features
consistente en 12 bits asociados a las 12 direcciones posibles.
Sobre el histograma de direcciones de la celda se calcula un
umbral como se describió anteriormente para la binarización,
de manera que se decide si la dirección en la celda está (bit=1)
o no (bit=0).
El vector de gradient features total es de 12x4x4 = 192 bits.
Ejemplo de Aplicación de Identificación
Structural features
Estas features revelan patrones en el mapa de gradiente de la imágen bitmap (“mini-trazos”).
Se calculan aplicando a cada pixel un conjunto de 12 reglas que operan sobre los 8 pixels próximos
(vecinos). Cada regla busca un patrón determinado en los vecinos respecto a su gradiente.
Ejemplo de Aplicación de Identificación
Para que se cumpla la regla deben verificarse el rango del vecino 1 y el rango del vecino 2. Para que se verifique
un rango debe cumplirse que el gradiente del vecino indicado tenga una de las direcciones indicadas.
Ejemplo:
Nota: La tabla indica los vecinos de 0-7, y en este ejemplo igual pero de 1-8.
Así la regla 1, considera los vecinos 1 y 5 del pixel. La idea es que si por estos y el pixel pasa una línea horizontal,
los valores del gradiente en ellos serán perpendiculares y por tanto serán en dirección vertical (3), o casi (2,4).
Cada regla se cumplirá o no, y se indicará con un bit a 1 ó 0, de manera que se generará un vector de features de
12 bits que indica que reglas se cumplen en cada celda de la malla 4x4. De nuevo se calculará en todos los pixels y
se harán histogramas por celda de las reglas que se cumplen, generando el vector binarizado mediante un umbral
como se hizo anteriormente.
De esta manera se construirá un vector de structural features total de 12x4x4 = 192 bits.
Ejemplo de Aplicación de Identificación
Concavity Features
Se dividen en tres subclases:
• Coarse Pixel
• Large stroke
• U/D/L/R/H Concavities
Coarse pixel density features
Densidad de pixel ‘grueso’. Capturan las agrupaciones de pixels en la imágen i.e. se aplica la malla de 4x4 a la
imágen y se hace el histograma para cada celda del número de pixels negros. Se mide este número en las 16
celdas y se toma un umbral para hacer una binarización que indique en cada celda si predominan los puntos
negros o no.
Queda así un vector de features de 4x4 = 16 bits.
Ejemplo de Aplicación de Identificación
Large-stroke features
Características de ‘trazo-largo’. Detectan trazos largos en horizontal o en vertical en la imágen. Para esto se computan los
valores de pixels negros y blancos en run-length sobre filas –trazos horizontales- o columnas –trazos verticales-.
La idea es para cada fila y columna, formularla en términos de secuencias de pixels negros. Se hace así un histograma
sobre toda la imágen de los posibles valores de longitud de los trazos y se fija un umbral óptimo. En cada celda habrá
trazos horizontales, si hay alguno de longitud mayor que el umbral determinaremos que en la celda hay trazos largos
horizontales, y lo mismo en la celda para el caso vertical. Estos dos indicadores, sobre la malla total nos da un vector total
de features de 4x4x2 = 32 bits.
U/D/L/R/H concavity features
Se calculan convolucionando la imágen con un operador en estrella i.e. el operador ‘lanza rayos’ desde el pixel central
en 8 direcciones equidistantes en estrella y detecta con qué colisiona: borde de la imágen o con algún trazo de la letra.
Se hace una tabla con el estado de terminación del recorrido de cada rayo desde cada pixel. Se usa un algoritmo
eficiente similar run-length encoding. La clase de cada pixel se determina aplicando reglas a los patrones del estado de
terminación de los pixels.
Así se detectan concavidades arriba (U,up), abajo (D, down), izquierda (L, left), derecha (R, right) y agujeros (H,
holes). Las reglas se relajan lo suficiente como para que sean capaces de detectar como ‘H’ los “broken-holes” i.e.
óvalos no cerrados completamente en su trazado.
En un mismo pixel puede haber más de una de estas features, de manera que necesitamos 5 bits por pixel (U/D/L/R/H),
y considerando la malla de celdas queda así un vector de features total de 4x4x5 = 80 bits.
Ejemplo de Aplicación de Identificación
Geometric Features
Miden características geométricas de la letra. Su forma.
Son 5 features f1,f2,f3,f4, y f5. Denotamos cada pixel en el bitmap binarizado como B(i,j)


B(i,j) = 0 white pixel (fondo).
B(i,j) = 1 black pixel (trazo).
La primera de estas features es
f1 (#black pixels) = Σ i Σ j B(i,j)
Sean l (left), r (right), t (top) y b (bottom) los pixels negros extremos por las cuatro
direcciones que sus nombres indican tenemos
f2 (height-width ratio) = ( r – l + 1 ) / ( b – t + 1)
Ejemplo de Aplicación de Identificación
Se define la centroide como centroid(mi,mj) con componentes sobre las columnas y filas:
mi = Σ i Σ j [ i B(i,j) ] / Σ i Σ j B(i,j)
mj = Σ i Σ j [ j B(i,j) ] / Σ i Σ j B(i,j)
Así tenemos las features
f3 (centroid height ratio) = ( mi – l + 1 ) / ( b – t + 1 )
f4 (centroid width ratio) = ( mj – l + 1 ) / ( r – l + 1 )
Y finalmente se forma un 9-sensor espacial en la forma de una rejilla de 3x3 puntos equidistantes sobre el
carácter, y centrado en
center(ci,cj) = ( (b – t + 1) / 2 , (r – l + 1) / 2 )
La feature mide la distancia entre el pixel negro más cercano y los 9 puntos del sensor:
f5 (9 spatial sensor distance) = Σ S9S1 d( Sx , B(i,j) )
Ejemplo de Aplicación de Identificación
Identificación mediante k-Nearest Neighbour (k-NN)