Detección y evaluación de figuras manuscritas Alberto Alejandro Fiel Martínez, Miguel Galante, Alberto Laudadio, Nicolás Park, Gabriela Esperón
[email protected] Resumen— En el presente trabajo se exponen y describen diversas técnicas empleadas para el procesamiento y la evaluación de imágenes en el marco del Proyecto PROA que se lleva a cabo en el AIGroup1 de la Facultad de Ingeniería de la Universidad de Palermo. El objetivo del Proyecto PROA es diseñar un mecanismo de evaluación implementado en un sistema automático para la detección precoz de problemas en el aprendizaje. Dicho prototipo cuenta con un Sistema Experto que evalúa, con algorítmicas inteligentes, si un niño de entre 3 y 6 años tiene problemas potenciales de aprendizaje. A su vez, el Sistema Experto, tiene la capacidad de realizar sugerencias acerca de las áreas en las cuales se podrían presentar problemas. A tal fin se están desarrollando distintos módulos que forman parte del sistema: Procesamiento de Imágenes, Procesamiento de Sonido, Procesamiento Motor. Este trabajo se centra en descripción del módulo Procesamiento de Imágenes. Dicho módulo evalúa y analiza figuras geométricas dibujadas por niños de entre 3 y 6 años en condiciones de test. Se presentan los resultados obtenidos mediante la aplicación de algoritmos de clustering.
Keywords : Data Mining , Image processing 1. INTRODUCCIÓN A continuación se presentan algunos de los procedimientos automáticos implementados en el módulo de Procesamiento de imágenes para la identificación de figuras y generación de información numérica para el módulo de Análisis de Datos. Cabe aclarar que los algoritmos matemáticos fueron creados utilizando Matlab como herramienta de investigación. Aquí se describe el procedimiento para la identificación de figuras con vértices (triángulos) e identificación y análisis de círculos dibujados por niños entre 3 y 6 años bajo la consigna de copiar dichas figuras a partir de un modelo. 2. CAPTURA DE IMÁGENES Los dibujos son realizados por los niños en hojas A5 utilizando materiales estandarizados, con el fin de minimizar la influencia de factores externos a aquellos que se desea evaluar. Asimismo, las consignas son presentadas por las maestras, que son previamente capacitadas a los efectos de neutralizar alteraciones perturbadoras de las capturas. Para digitalizar los dibujos se utilizan scanners comunes, de los que se encuentran en el mercado. Luego de realizar numerosas pruebas con distintas configuraciones, se establecieron los siguientes valores como los óptimos respecto de la cantidad de información y tamaño de archivo de la imagen escaneada.[1]
1 El AIGroup es un laboratorio de investigaciones de transferencia especializado en Inteligencia Computacional. Fue fundado en el año 2005, como parte de la facultad de Ingeniería de la Universidad de Palermo.
Resolución: 50ppp (puntos por pulgada) Color: 256 bits en escala de grises. Profundidad: 8 bits Formato: PNG
Con los parámetros arriba definidos se obtuvieron imágenes con dimensiones de 413x292 pixeles (Ancho x Alto), dando una cantidad de 120596 puntos por imagen. 3. PROCESAMIENTO DE IMÁGENES El análisis al que se someten las imágenes consta de tres etapas: Pre-procesamiento: en esta instancia se busca eliminar toda la información no relevante de la imagen. Extracción de datos característicos de la imagen Análisis de las características extraídas 3.1 PRE-PROCESAMIENTO En esta etapa se busca minimizar la cantidad de información irrelevante presente en la imagen como sombras producidas por el escaneo o manchas presentes en el dibujo así como preparar la imagen para el procesamiento posterior. Para ser procesada, una figura debe estar limpia, cerrada (Fig.1) y no ser un garabato (Fig. 4).
Fig. 1 Círculo abierto y luego cerrado Este proceso se realiza con un script Matlab que se detalla a continuación: 1.- Se carga la imagen y se convierte a formato binario donde cada píxel estará representado por “1” o “0” 2.- Se realiza la limpieza de la imagen contando la cantidad de píxeles negros tanto en imagen inicial como en la imagen final. La limpieza de la imagen se compone de los siguientes pasos: Eliminación de parásitos: se eliminan conjuntos pequeños de píxeles. Obtención de bordes para el conteo de píxeles mediante la función “obtenerBordes”. Conteo de la cantidad inicial de píxeles negros. Cierre de figuras abiertas mediante la unión de extremos no cerrados de las mismas. Eliminación de líneas que no conforman figuras cerradas. Eliminación de grupos de píxeles sueltos. Eliminación de parásitos con menor tolerancia que en la primera aplicación. Obtención de bordes para el conteo de píxeles.
Conteo de la cantidad final de píxeles negros.
Fig. 3. Cálculo de distancia normalizada
En la Fig. 2 se puede apreciar el algoritmo implementado. 3.- Se calcula y estandariza la diferencia de píxeles negros entre la imagen inicial y la procesada, de esta manera se busca detectar si el dibujo es un garabato compuesto por líneas que no conforman figuras. Una diferencia superior al 25% del valor inicial, indicaría que en el proceso de limpieza se detectó que gran parte de la imagen inicial estaba compuesta por trazos que no definirían una figura de las esperadas para la evaluación. (Ver fig. 3)
En la Fig. 5 se puede observar la imagen antes de ser ingresada al script; allí se cuenta la cantidad de píxeles que la componen y, luego de realizada la limpieza y determinado el contorno exterior de la imagen (Fig. 6.) se realiza nuevamente el conteo de píxeles.
Fig. 4. Garabato
Fig. 5. Contorno del garabato La Fig. 6 muestra el valor de la diferencia de píxeles para dos figuras distintas. El cálculo se realiza sobre la consideración de que “0” significa que no hubo cambios en el proceso de limpieza y “1”, que la imagen resultante es totalmente diferente.
Fig. 2. Limpieza de la imagen
Diferencia: 0.0044 Diferencia: 0.5021 Fig. 6. Diferencia entre la imagen original y la pre-procesada Este script da como resultado una imagen limpia y preparada para ser procesada por los distintos algoritmos de detección de figuras. 3.2 EXTRACCIÓN DE CARACTERÍSTICAS 3.2.1 EXTRACCIÓN CÍRCULOS
DE
CARACTERÍSTICAS
DE
Para la detección de círculos, se aplica un script que automáticamente rotula cada unas de las figuras identificadas en una imagen y extrae ciertas propiedades de las mismas. La fig. 7 muestra el algoritmo Matlab correspondiente.
2
original. Dichos puntos, además se corresponderán con los cambios de dirección de las líneas que componen la imagen. Para la detección se llevan a cabo los siguientes pasos: 3.2.3 REDUCCIÓN DE LA CANTIDAD DE PÍXELES A ANALIZAR Fig. 7. Rotulación automática Con los datos (Mayor longitud presente en un eje, Menor longitud presente en un eje, área, perímetro, centroide, excentricidad) que devuelve la función “regionprops” se procede a la comparación entre el círculo dibujado y un circulo real que posea las mismas características.[2][3][4] En el proceso se emplean tres puntajes o scores que evalúan las diferencias o similitudes entre ambos. Como se aprecia en la Fig. 8. El primer score corresponde a la comparación de los diámetros más corto y largo de la figura, en el caso del círculo perfecto, dicho score es igual a 1. Por lo tanto, cuanto más cercano a 1 sea el valor calculado para la figura dibujada por el niño, más características de círculo tendrá la misma. El segundo score, compara el área de la figura dibujada, con el área de un círculo perfecto de radio igual al promedio entre el eje mayor y el menor de la misma. Para ello se emplea la formula A= π_r2 Cuanto más parecidas sean las áreas de la figura dibujada y del circulo perfecto, más cercana a 1 será dicha puntuación. El tercer score compara, el perímetro de la figura dibujada por el niño, con el perímetro del círculo perfecto calculado según la formula P= 2π_r
Se realiza un recorrido de la imagen pixel a pixel con el fin de reducir la cantidad de puntos a analizar, en pruebas se comprobó que la imagen puede ser redibujada correctamente tomando en cuenta 1 de cada 8 píxeles junto con la posición de los mismos. El no tomar píxeles consecutivos también resuelve el problema que se da por la irregularidad de los mismos en una imagen, lo que puede llevar a cálculos erróneos. Por caso, la Fig. 9 muestra una línea con puntos considerados consecutivos desde el punto de vista del algoritmo implementado.
Fig. 9 Amplificación de una recta En las Figuras 10 y 11 se muestran, respectivamente, una imagen inicial ya limpia y la misma imagen redibujada utilizando 1 píxel de cada 8 originales. Como puede apreciarse, no se pierden las características principales de la imagen original.
Fig. 8 Métricas de evaluación de círculos El script además genera un archivo con los datos numéricos que caracterizan, a partir de este punto, a la figura original, puesto que esta, ahora es descartada del procesamiento y reemplazada por estos datos. Para cada imagen se almacena: Nombre Puntajes de las pruebas matemáticas Coordenadas del centro Excentricidad Edad para ser analizadas en el módulo de Análisis de Estadísticas por medio de algoritmos de agrupamiento (clustering).
Fig. 10. Imagen original
3.2.2 IDENTIFICACIÓN DE FIGURAS CON VÉRTICES En el caso del triángulo, dado que se busca una imagen con vértices, se identifican los puntos relevantes puesto que éstos son los mínimos necesarios para generar una figura igual a la
3
-50
redibujada utilizando la mínima cantidad de puntos detectados como necesarios para su descripción.
-100 -50
-100
-150 -150
-200
-200 -250
-300 50
-250
100
150
200
250
300
350
-80
-300 50
100
150
200
250
300
-100
350
-120
Fig. 11. Imagen con 1/8 de píxeles
-140
-160
-180
3.2.4 COMPRESIÓN DE LA IMAGEN
-200
-220
-240
Se comprimen los datos obtenidos para descartar todos aquellos puntos no necesarios. El script de la Fig. 12 se utiliza para esta tarea.
-260
-280 150
200
250
300
350
400
Imagen limpia original Imagen redibujada Fig. 13 Imagen original y redibujada 4. ANÁLISIS DE LAS CARACTERÍSTICAS EXTRAIDAS DE LOS CÍRCULOS Para el análisis de los círculos se tomó un set de datos con 90 casos en los que se analizaron las variables: Score1, Score2, Score3, excentricidad y edad. Para dicho análisis se optó por el algoritmo de clustering TwoStep, dado que este provee buenos resultados al procesar variables continuas y determina automáticamente la cantidad de clusters. Otra de las razones para la elección de este algoritmo es que el mismo resulta robusto aun cuando no se cumpla alguna de las hipótesis [5][6][7]. Como se puede observar en la Fig.14 el algoritmo determinó la existencia de 2 conglomerados.
N Conglomerado
Casos excluidos Total
1 2 Combinados
85 4 89 1 90
% de combinados 95,5% 4,5% 100,0%
% del total 94,4% 4,4% 98,9% 1,1% 100,0%
Fig. 12. Simplificación y compresión de imágenes
Fig. 14 Distribución de los conglomerados
Para el procesamiento se proporcionan las coordenadas de cada uno de los puntos de la imagen y la tolerancia para la identificación de los puntos necesarios. Como parte del algoritmo, se calcula la pendiente para la recta formada por cada punto y el punto siguiente siendo este la posición del punto actual sumada a la variable que mide la separación elegida. Si la diferencia entre la pendiente de una recta con la pendiente de la posterior es mayor a la tolerancia, el punto inicial correspondiente a esa recta debe ser tenido en cuenta. En la Fig. 13 se observan los resultados del procesamiento de las figuras, donde se muestra la imagen original, junto con la
La Fig.15 muestra los centros para los conglomerados, en ella se puede observar la media y desviación por cada una de las variables. Las medias del conglomerado 2, ubican a las imágenes allí agrupadas como las que menos semejanza tienen a un círculo perfecto, presentando estas los valores más cercanos a 0 para los primeros 3 scores y con mayores desviaciones. Con respecto a la excentricidad, donde un círculo perfecto posee un valor de “0” y una línea recta un valor de “1”, se puede observar un valor medio menor en el cluster uno aunque elevado para lo que sería un círculo perfecto, esto se debe a que los niños, especialmente entre los 3 y 4 años tienden a dibujar elipses. También se puede observar que el
4
conglomerado 1 contiene a los niños de mayor edad lo que es coherente con la información de las variables para este conglomerado.
Conglomerado
1 2 Combinados
SCORE3 Media Desv. típica ,9230 ,06275 ,7068 ,21640 ,9133 ,08593
SCORE1 Media Desv. típica ,7510 ,12594 ,3202 ,17573 ,7317 ,15573
ECCENTRI Media Desv. típica ,6308 ,15019 ,9335 ,06308 ,6444 ,16014
SCORE2 Media Desv. típica ,9538 ,04298 ,4552 ,20835 ,9314 ,11847
[6] Brian S. Everitt, Graham Dunn. “Multivariate Applied Data analisys”. Wiley. 2001. ISBN 0340741228. [7] Witten, I. y Frank, E. Data Mining. “Practical Machine Learning Tools and Techniques”. San Francisco: Morgan Kaufmann Publishers. 2005. ISBN 0120884070
EDAD Media Desv. típica 3,96 ,851 3,50 ,577 3,94 ,844
Fig. 15 Perfiles de los conglomerados El análisis de los resultados arrojados por el algoritmo de clustering confirma que la selección de variables Score1, Score2 y excentricidad son adecuadas para evaluar las características que se desea estudiar. Sin embargo, el Score3 y la edad no se revelan como las variables de mayor importancia. Dado que la figura analizada es un círculo, figura que los niños pueden reproducir desde los 3 años, tiene sentido que la edad no sea una variable determinante. 5. CONCLUSIONES Y TRABAJO A FUTURO El proceso de clasificación demostró que los parámetros tenidos en cuenta para los cálculos resultan adecuados para evaluar las características de las imágenes analizadas y las variables escogidas son significativas. (Score1, Score2 y excentricidad) estos resultados están en concordancia con los que se conocen desde la psicología evolutiva. Para la futura evaluación de figuras con vértices se deben establecer los parámetros a evaluar, basándose en las características geométricas de las mismas. El procedimiento será similar al efectuado con los círculos, utilizando para ello las figuras obtenidas luego de la simplificación a sus coordenadas características. Queda pendiente, entre otras cosas, la adaptación de los métodos descriptos para el procesamiento de otras figuras, ya que constituyen algoritmos genéricos y parametrizables de manera bastante sencilla. 6. REFERENCIAS [1] Fiel Martínez A. A., Esperón G., Porreca C., Decunto M., López De Luise D., Laurito F., Scanavino L., Laudadio A., Burgos M. – “Sistema para la detección precoz de problemas en el aprendizaje”. X Workshop de Investigadores en Ciencias de la Computación 2008. [2] Mark Nixon, Alberto S Aguado “Feature Extraction and Image Processing”. Newnes. 2002. ISBN 0750650788 [3] Rafael C. Gonzalez, Richard E. Woods, Steven L. Eddins – “Digital Image Processing Using MATLAB” ISBN 0130085197. [4] Moore, Holly “Matlab para Ingenieros”. Editorial Pearson. ISBN: 970-26-1082-6. [5] Johann Bacher, Knut Wenzig, Melanie Vogler “SPSS Twostep Cluster – A First Evaluation". Sixth International Conference on Social Science Methodology. 2004.
5
