Diseño de sistema de identificación de llaves de sierra

Proyecto Fin de Carrera Ingeniería de Telecomunicación Formato de Publicación de la Escuela Técnica Superior de Ingeniería Autor: F. Javier Payán Somet Tutor: Juan José Murillo Fuentes Dep. Teoría de la Señal y Comunicaciones Escuela Técnica Superior de Ingeniería Universidad de Sevilla Sevilla, 2013 Trabajo de Fin de Máster Ingeniería de Telecomunicación Diseño de sistema de identificación de llaves de sierra Autor: Ramón José Soldado Arroyo Tutor: José Ramón Cerquides Bueno Dpto. Teoría de la Señal y Comunicaciones Escuela Técnica Superior de Ingeniería Universidad de Sevilla Sevilla, 2021 Trabajo de Fin de Máster Ingeniería de Telecomunicación Diseño de sistema de identificación de llaves de sierra Autor: Ramón José Soldado Arroyo Tutor: José Ramón Cerquides Bueno Profesor Titular Dpto. Teoría de la Señal y Comunicaciones Escuela Técnica Superior de Ingeniería Universidad de Sevilla Sevilla, 2021 Trabajo de Fin de Máster: Diseño de sistema de identificación de llaves de sierra Autor: Ramón José Soldado Arroyo Tutor: José Ramón Cerquides Bueno El tribunal nombrado para juzgar el trabajo arriba indicado, compuesto por los siguientes profesores: Presidente: Vocal/es: Secretario: acuerdan otorgarle la calificación de: El Secretario del Tribunal Fecha: Agradecimientos La realización de este trabajo supone el último paso en mi carrera universitaria, cuyo inicio queda ya bastante lejano. Desconozco si en el futuro tendré la oportunidad o la voluntad de regresar a los estudios, pero puedo decir con toda seguridad que esta época ha sido determinante para convertirme en la persona que soy hoy en día. Quiero agradecer a todos los profesores y compañeros que he tenido el placer de conocer y aprender de ellos durante todos estos años, así como a mi familia y amigos por apoyarme en los momentos más difíciles. De la misma forma, el desarrollo de este proyecto ha sido un proceso largo, pandemia incluida, a veces muy complicado, que me ha llevado a muchos momentos de desesperación pero también a muchos momentos de alegría y satisfacción que guardo con mucho cariño y sin duda me han enseñado a organizarme y trabajar mejor. Quiero agradecer a Ramón y Eduardo por toda la ayuda y apoyo constante, así como la libertad ofrecida en todo momento. Ramón José Soldado Arroyo Córdoba, 2021 I Resumen En la actualidad, las llaves tradicionales tienen un papel fundamental en la vida diaria de la gente. Sin embargo, el proceso realizado cotidianamente para la copia de estas ha quedado algo desfasado, lo que conlleva gastos elevados que podrían evitarse. Este trabajo propone un sistema que automatice la tarea de identificación del perfil y la codificación de una llave, con el fin de generar una copia digital de esta, reproducible de manera sencilla. Tras varios estudios sobre las llaves de sierra y diferentes técnicas de procesamiento de imagen, se propone un diseño de sistema que engloba desde la toma de imágenes de la llave hasta el tratamiento y análisis de estas para obtener diversas características que puedan cotejarse con ficheros de especificaciones y obtener una identificación como salida. El proceso se divide en varias fases de diseño y se aborda con un sistema jerárquico para aumentar la simplicidad y eficiencia. Finalmente, varias pruebas de validación del sistema sirven para permitir analizar el funcionamiento de este. Pese a que los resultados obtenidos no son perfectos debido a diversos factores, los análisis realizados a partir de ellos permiten comprender de manera exhaustiva el comportamiento del sistema e identificar las fuentes de error. Este conocimiento permite desarrollar una estrategia para el perfeccionamiento del sistema en un futuro, así como ampliar su rango de funcionamiento. III 2 Objetivos y metodología Co mo primer paso, se trata de definir de manera clara cuales son los objetivos a cumplir con la realización del proyecto, así como su alcance y el marco en el cual se realiza. A continuación, se introducirán algunas consideraciones sobre la metodología a seguir en su realización, tales como una breve discusión sobre el enfoque y organización propuesta, así como una pequeña descripción de la estructura de esta memoria. 2.1 Objetivos El objetivo principal del proyecto es la realización de un sistema capaz de identificar y decodificar llaves proporcionadas. Es preciso mencionar que este trabajo se enmarca dentro de un proyecto de investigación y su objetivo no es realizar una aplicación que funcione perfectamente con carácter comercial, si no investigar los procedimientos, tecnologías y limitaciones que supone la realización de esta aplicación con las tecnologías utilizadas. El correcto funcionamiento del sistema es deseable sin duda, pero no se considera indispensable para considerar el trabajo satisfactorio, pudiendo ser considerado un objetivo secundario. De todos los tipos de llaves, este proyecto abarca unicamente las llaves conocidas como de sierra, ya son el modelo más utilizado y con mayor simplicidad. Siendo una primera aproximación al análisis e identificación de llaves, se considera más apropiado comenzar con el análisis de este tipo de llaves ya que la mayoría de sus características provienen del contorno de esta y no de su profundidad o relieve, como en otros tipos de llaves. Como sistema, consta de elementos físicos o hardware para capturar la llave de la manera necesaria y software para realizar el tratamiento de las imágenes tomadas. Por tanto, es objetivo del proyecto desarrollar un prototipo de ambas partes del sistema. La entrada del sistema es la propia llave física y la salida consiste en la identificación del tipo de llave y la codificación de cerradura que contiene. 2.2 Metodología Respecto a la metodología seguida, es posible organizar el proyecto en diferentes fases propuestas, con el fin de mantener una organización desde el primer momento y maximizar la eficiencia del desarrollo. Las fases propuestas son las siguientes: 1. Estudio de llaves de sierra. El primer paso consiste en un estudio de la morfología y características de las llaves de sierra, que van a ser el objeto de estudio del sistema. Es necesario conocer qué parámetros contienen información y son medibles de manera sencilla. Los resultados obtenidos formarán parte de una base de datos que servirá al sistema para identificar la llave. 2. Planificación y diseño del sistema. Con el fin de tener un desarrollo preciso y óptimo, es necesario realizar una planificación completa en diferentes niveles de profundidad del sistema. Es un sistema complejo, por lo que el diseño se realiza mediante diagramas de bloques de diferentes jerarquías según funcionalidad, permitiendo sucesivas correcciones si fuera necesario. 3. Desarrollo del sistema. Implementación del diseño realizado en el paso anterior, sea físico o a nivel de programación. Este desarrollo se realiza en bloques independientes para aislar posibles errores o 3 4Capítulo 2. Objetivos y metodología mal funcionamiento de alguno de ellos, permitiendo mayor eficiencia en modificaciones y detección de fallos más adelante. 4. Verificación del funcionamiento. Finalmente se prueba el sistema implementado a diferentes niveles, desde pequeños bloques a pruebas del sistema completo. Esto permite comprobar el funcionamiento de elementos básicos más sencillos antes de verificar sistemas más grandes y complejos, lo que acelera mucho la depuración de errores. Debido a la complejidad del proyecto, las fases 2-4 tendrán un carácter iterativo, sirviendo las diferentes pruebas realizadas para realizar cambios en el diseño y por lo tanto modificaciones en la implementación. Un diseño óptimo del sistema ayuda a reducir el número de iteraciones necesarias para conseguir que una parte del sistema funcione correctamente, aumentando la eficiencia. Sin embargo, uno de los objetivos es investigar las limitaciones y comportamiento de las diferentes tecnologías utilizadas, por lo que es conveniente realizar varios ciclos que permitan obtener un mayor conocimiento del funcionamiento práctico de estas. Por último, la estructura de esta memoria pretende respetar las fases de diseño propuestas anteriormente, de forma que describa el trabajo realizado de la forma más fiel y organizada. Inicialmente se presenta el estudio de las llaves realizado, seguido por un estudio del estado del arte que permite conocer mejor algunas de las técnicas de procesamiento de imagen más útiles para el desarrollo del proyecto. Las fases de planificación y desarrollo se engloban en un apartado dedicado al desarrollo del sistema, dónde se describen los pasos y planteamientos tomados para el diseño en los diferentes niveles de profundidad indicados anteriormente. Posteriormente, se muestran algunas de las verificaciones y pruebas realizadas al sistema, obteniendo así una serie de resultados, de los cuales se realizará un análisis sus fallos, limitaciones y complicaciones. Finalmente, se expondrán las conclusiones obtenidas a lo largo de todo el proceso y se expondrán algunas de las posibles futuras vías de desarrollo e investigación. 3 Descripción de llaves de sierra Pa ra poder desarrollar una aplicación de reconozca e identifique diferentes llaves de sierra, es necesario hacer un estudio de sus diferentes características, conocer sus posibles variaciones e identificar qué partes contienen información útil y cuales no. En este apartado se describe la morfología completa de las llaves de sierra y todas las características útiles para la identificación de las llaves en la aplicación. A nivel de terminología, cada tipo de llave es denominado perfil, siendo el nombre de cada uno de ellos establecido por cada fabricante. Esto significa, que un mismo perfil tendrá diferentes nombres según el fabricante pero idénticas propiedades. Por ejemplo, el perfil conocido como TE-8I por el fabricante JMA sería conocido como TE-2 por el fabricante Silca oTES-5 por Keyline. Figura 3.1 Diagrama de partes de llave de sierra. En la Figura 3.1 se muestra un diagrama con las principales partes de una llave de sierra. A grandes rasgos, la llave se divide en tres partes: cabeza, shoulder y hoja, aunque existen otras partes de especial relevancia en ellas, las cuales son descritas a continuación: •Cabeza. Es la parte de la llave que queda fuera de la cerradura al introducir la llave en ella. La información de esta parte de la llave es muy escasa, ya que como su función es solamente proporcionar apoyo a los dedos para girar la llave. Existen grandes variaciones en el diseño y forma de la cabeza entre los diferentes fabricantes, que no influyen en el uso de la llave. Por esto, no se valoran aspectos de ella en la identificación de las llaves. •Shoulder. Consiste en una pestaña entre la cabeza y la hoja que hace de tope con la cerradura al introducir la hoja, haciendo que los cortes de la llave entren al lugar correcto en la cerradura y permita desbloquearla. Su diseño o forma no contiene información por el mismo motivo que la cabeza, pero es posible discriminar entre perfiles según la llave tengo uno o dos shoulder (el segundo a la misma altura del primero, pero al otro lado de la llave). 5 6Capítulo 3. Descripción de llaves de sierra •Hoja. Se trata de la parte alargada de la llave que entra en la cerradura. Esta parte contiene prácticamente toda la información necesaria para identificar el perfil y obtener la codificación de la cerradura. Existen varias partes relevantes en ella que contienen mucha información, explicadas a continuación: – Cortes. Se tratan de las muescas de la hoja a cierta profundidad que permiten desbloquear la cerradura. Proporcionan a este tipo de llaves el nombre de llaves de sierra, debido a su similaridad. Los cortes contienen información de dos tipos: para identificar el tipo de perfil y para obtener la codificación de la misma llave, que hace que la cerradura abra. En la Figura 3.2 se muestran esquemáticamente las propiedades y medidas de los cortes de un perfil CVL-5I. Todos los cortes poseen la misma forma, delimitada por el ancho (llamado valle) y el ángulo del corte. Cada uno de los cortes, que son un número determinado en cada perfil, posee una localización determinada a lo largo de la hoja y una profundidad que determina su codificación, también llamada boundary. Figura 3.2 Detalle de las características de los cortes. – Boca. Consiste en la terminación de la hoja, siendo la parte que entra primero en la cerradura. Aunque cada perfil tiene una boca concreta, se pueden dividir en dos grandes grupos como se muestran en la Figura 3.3. El primero de los tipos consiste en una boca suavizada con una recta directa entre la parte recta de la hoja y la boca, por otro lado, el segundo tipo de boca muestra una caída abrupta desde la parte recta de la hoja, formando una especia de escalón. – Canales. Son las hendiduras que poseen las llaves en la superficie, paralelas a la longitud de la hoja. Es el único de los elementos mencionado que se basa en la profundidad en la llave, por lo que hasta ahora se ha realizado un tratamiento de la llave en dos dimensiones, sin contar con la profundidad de esta. Además, el patrón de canales de ambas caras de la llave generalmente difiere entre sí. (a) Tipo 1. (b) Tipo 2. Figura 3.3 Tipos de bocas de llaves de sierra. 3.1 Ficheros de especificación 7 3.1 Ficheros de especificación Una vez conocida la estructura y las diversas partes de las llaves de sierra, es posible abordar los ficheros de especificación que se van a utilizar para describir los diferentes perfiles. Estos ficheros contienen medidas e indicaciones de varias de las características de las llaves descritas anteriormente. De manera general, las medidas son proporcionadas por los fabricantes en ficheros de especificación, pero además ciertas indicaciones sobre forma o cantidad de elementos han sido introducidos en un estudio previo sobre las llaves, ya que existe información de utilidad para la identificación que no viene especificada por fabricantes. De esta forma, los ficheros de especificación utilizados, como el mostrado en Código 3.1, obtiene datos del fabricante y de estudios propios realizados. Código 3.1 Fichero de especificación de perfil CVL-5D. 1 { 2 "types":[ 3 { 4 "brandName":"JMA", 5 "typeName":"CVL", 6 "profileName":"CVL-5D" 7 }, 8 { 9 "brandName":"Silca", 10 "typeName":"CVL", 11 "profileName":"CVL3R" 12 }, 13 { 14 "brandName":"Keyline", 15 "typeName":"CVL", 16 "profileName":"CV3" 17 } 18 ], 19 "bladeWidth":840, 20 "bladeLength":2870, 21 "angle":100, 22 "valley":160, 23 "ncuts":5, 24 "nshoulder":2, 25 "nchannel1":2, 26 "nchannel2":1, 27 "group":0, 28 "bite":1, 29 "cuts":[ 30 470, 31 920, 32 1370, 33 1820, 34 2270 35 ], 36 "boundaries":[ 37 { 38 "text":"7", 39 "value":530 40 }, 41 { 42 "text":"6", 43 "value":580 44 }, 45 { 46 "text":"5", 8Capítulo 3. Descripción de llaves de sierra 47 "value":630 48 }, 49 { 50 "text":"4", 51 "value":680 52 }, 53 { 54 "text":"3", 55 "value":730 56 }, 57 { 58 "text":"2", 59 "value":780 60 }, 61 { 62 "text":"1", 63 "value":830 64 } 65 ] 66 } A continuación, se detallan los parámetros utilizados presentes en todos los ficheros de especificación. Todas las medidas longitudinales se expresan en centésimas de milímetro ( 10−5 metros) salvo que se indique lo contrario. •types: incluye una lista del nombre y tipo del perfil para los diferentes fabricantes. •bladeWidth: medida del ancho de la hoja. •bladeLength: medida del largo de la hoja. •angle: ángulo del corte en grados sexagesimales. •valley: medida de la distancia de valle. •ncuts: número de cortes en la hoja. •nshoulder: número de shoulder en la llave. •nchannel1: número de canales en la cara principal de la llave. •nchannel2: número de canales en la cara secundaria de la llave. •group: indica si la llave es posible de realizar mediante un perfil universal (1) o no (0). •bite: indica el tipo de boca de la llave. •cuts: listado con la localización del centro de los cortes de la hoja. •boundaries: listado con información sobre la profundidad de los cortes. Contiene un listado de las diferentes medidas de la profundidad y su código asociado. Una vez analizada la estructura de la llave y conocidas las características disponibles de los perfiles, es posible plantear una solución que permita medir cada una de ellas sobre una llave cualquiera y comparar los datos, obteniendo una identificación del perfil. 4 Estado del arte An tes de comenzar el desarrollo de la solución, este capitulo introduce teóricamente un repaso de las diferentes técnicas de procesamiento digital de imagen existentes, partiendo de un enfoque genérico e histórico que se concreta en un estudio de la segmentación, sus técnicas principales y bases, así como un estudio de algoritmos de segmentación actuales y aplicables al proyecto. 4.1 Introducción al procesamiento digital de imagen Para poder entender y estudiar las diversas técnicas de procesamiento digital de imagen, así como su evolución, es necesario comprender la historia de la imagen digital, cuya existencia abarca aproximadamente un siglo. A su vez, esto nos permitirá ir descubriendo los diferentes tipos de técnicas y soluciones surgidas desde un enfoque histórico. El primer uso importante de la imagen digital surge aproximadamente en 1920 a manos de Harry G. Bartholomew y Maynard D. McFarlane, trabajadores de un diario londinense que buscaba solucionar los largos tiempos de espera que existían para transportar imágenes de forma convencional de un lado a otro del océano Atlántico. Para solucionar este problema, se creo el sistema de transmisión de imágenes Bartlane [ 22 ] [ 4 ], que utilizaba un cable submarino entre Londres y Nueva York y permitía enviar imágenes en aproximadamente tres horas, frente al mes que se tardaba actualmente. Este sistema utilizaba unas cintas perforadas similares a las utilizadas en la época por los telégrafos. En principio, permitía codificar hasta cinco niveles de oscuridad que resultaban en imágenes de muy baja calidad. Con el tiempo, el sistema fue mejorando hasta ofrecer hasta quince niveles de oscuridad en 1929, mejorando considerablemente la calidad de la imagen. La Figura 4.1 muestra una de las imágenes digitales de quince tonos enviada mediante el sistema Bartlane. Figura 4.1 Imagen digital transmitida mediante el sistema Bartlane en 1929. 9 10 Capítulo 4. Estado del arte Sin embargo, aunque el sistema Bartlane digitalizaba imágenes para tu transmisión, no es correcto decir que se trate de procesamiento de imágenes ya que no era un proceso realizado con un ordenador digital. El desarrollo del procesamiento de imágenes depende estrechamente del desarrollo de la computación, ya que se requieren recursos de almacenamiento, procesado y transmisión para realizarse. Los primeros ordenadores con capacidad suficiente para realizar tareas de procesado de imagen fueron desarrollados en la década de 1960, en parte gracias al gran avance en computación que supuso la carrera espacial. En el Jet Propulsion Laboratory [ 26 ] de la NASA se crearon las primeras aplicaciones prácticas conocidas de procesamiento digital de imagen, donde se aplicaban técnicas para la mejora de la calidad de imágenes tomadas del espacio, concretamente de la superficie de la luna. Estas aplicaciones lograban corregir distorsiones y ruidos en las imágenes tomadas. La Figura 4.2 muestra una de las imágenes tomadas por la nave Ranger 7 en una misión. Figura 4.2 Imagen de la superficie de la luna tomada por la nave Ranger 7 de la NASA. La misión Ranger 7 fue considerada un gran éxito y permitió observar detalles de la superficie de la luna desconocidos hasta la fecha. En años sucesivos, el procesamiento de imagen fue una pieza clave para poder estudiar el satélite y realizar las misiones tripuladas a la superficie en 1969 [7]. Al mismo tiempo, el procesamiento digital de imagen fue de gran aplicación en el campo de la medicina, culminando con la invención de la tomografía axial computarizada (TAC), que llevó a sus inventores a ganar el Premio Nobel de Medicina en 1979. Esta técnica consiste en realizar varias proyecciones de rayos X sobre una parte del cuerpo en diferentes ángulos e inclinaciones. Aplicando procesamiento digital de imagen es posible combinar y promediar todas las proyecciones para obtener una imagen tridimensional completa que permita un estudio médico mucho más completo y riguroso [ 5 ]. Esta técnica, ampliamente utilizada hoy en día, es muy importante para detectar cánceres, fracturas, hemorragias internas y tratar otras muchas cuestiones médicas. El procesamiento digital de imagen alcanzó un momento de gran crecimiento con el abaratamiento de los ordenadores y el aumento de la capacidad de computación. Esto permitió que las aplicaciones se extendieran en la gran mayoría de campos y se lograran realizar aplicaciones más rápidas, incluso en algunos casos logrando procesamientos a tiempo real. Con el paso de los años, el procesamiento digital de imagen está presente en multitud de aplicaciones en una gran cantidad de ámbitos. La Figura 4.3 contiene varios ejemplos de aplicaciones actuales que se basan en técnicas de procesado de imagen digital. Los avances en el procesado digital de imagen siguen produciéndose a un gran ritmo conforme la tecnología avanza, surgiendo nuevas aplicaciones y técnicas constantemente. Es difícil establecer los límites entre procesado digital de imagen y algunas otras áreas similares como la visión artificial o el análisis de imagen [ 21 ]. En el futuro, algunos de las tecnologías que utilizan procesamiento de imagen como puede ser el 4.1 Introducción al procesamiento digital de imagen 11 reconocimiento facial, realidad aumentada o la conducción autónoma, tendrán gran relevancia, por lo que puede preverse un gran desarrollo futuro, mayor al actual. (a) TAC 3D de mandíbula. (b) Reconocimiento automático de matrículas. (c) Remasterización de películas antiguas. Figura 4.3 Ejemplos de aplicaciones actuales del procesamiento digital de imagen. A continuación se describe uno de los paradigmas de clasificación de técnicas más utilizado [ 21 ], que tiene tres clases según el tipo de transformación realizada: •Procesos de nivel bajo. Consisten en realizar operaciones primitivas, obteniendo a partir de una imagen de entrada otra imagen de salida. Algunas de las técnicas que encajan en este nivel son la eliminación de ruido, mejora de la nitidez o ajuste de contraste. •Procesos de nivel medio. En este caso, los procesos tienen como entrada una imagen, pero la salida consiste en atributos obtenidos a partir de ella. A este nivel pertenecen técnicas como la segmentación o la extracción de características, que obtienen elementos concretos a partir de una imagen. •Procesos de nivel alto. Este nivel consiste en dar sentido a una serie de atributos, es decir, obtener conocimiento a partir de ellos. En este nivel se encuentran procesos que emulan las capacidades cognitivas humanas, tales como el análisis de imágenes o la navegación autónoma. Como se ha expuesto en esta sección, el procesamiento digital de imagen es una herramienta muy importante y de gran utilidad a lo largo de su historia. Es aplicable a una gran cantidad de ámbitos, por lo que está en constante desarrollo. Debido a la imposibilidad de realizar un recorrido por todas las técnicas que lo componen, a continuación se abarca un desarrollo de la técnica de segmentación, que tiene gran relevancia en el proyecto. 18 Capítulo 4. Estado del arte 4.2.4 Métodos basados en grupos (Clustering) Este tipo de técnicas de segmentación se distingue por agrupar los píxeles de la imagen en conjuntos o grupos (clusters) con características similares. El análisis de grupos es una técnica común usada en el análisis de datos estadísticos, con muchas más aplicaciones que la segmentación de imágenes [18]. De forma general, existen dos métodos de agrupación: el agrupamiento jerárquico y el método de particiones. El método jerárquico se basa en el concepto de árboles, dónde la raíz representa la totalidad de los datos (o píxeles en este caso) y los diferentes nodos representan los grupos formados en diferentes niveles de jerarquía, según las características usadas para clasificar. Por otro lado, el método de particiones utiliza métodos de optimización iterativamente para minimizar una función objetivo. A continuación, se introducen dos de los algoritmos más populares de agrupación: •K-means. Consiste en agrupar los píxeles de la imagen en k grupos diferentes, siendo una agrupación dura, es decir, cada píxel pertenece unicamente a un grupo [ 18 ]. La asociación del píxel se realiza al grupo con la media más cercana, de ahí el nombre del algoritmo. Tras una elección inicial de k centroides o medias, el algoritmo consiste en la ejecución iterativa de dos pasos consecutivos: asignación de muestras (píxeles) al grupo más cercano y actualización del valor de los centroides del grupo, hasta converger. •Superpixel. La idea detrás de superpixel consiste en reemplazar la tradicional cuadrícula de píxeles que forma una foto en una serie de regiones llamadas superpíxeles que consisten en una agrupación de píxeles convencionales con características similares en color y propiedades de bajo nivel, es decir, píxeles perceptualmente similares a la vista [ 25 ]. El procedimiento seguido es similar al método anterior, realizando un procedimiento iterativo hasta converger. A continuación se muestran algunos ejemplos de ambas técnicas sobre la misma imagen para diferentes configuraciones. En la Figura 4.10 es posible observar como el algoritmo de k-means consigue separar la imagen en tantas regiones como valor se le asigne al parámetro k. Por otro lado, en la Figura 4.11, la resolución y precisión de los superpíxeles viene dado por un parámetro N que fija el número total de superpíxeles resultantes al final de la ejecución, por lo que cuanto mayor sea, más similar a la imagen original será y más precisión se obtendrá. (a) Imagen original. (b) K-means (k = 2). (c) K-means (k = 5). Figura 4.10 Ejemplo de aplicación de algoritmo k-means. 4.2.5 Métodos de transformación divisoria (Watershed) Por último, el método de transformación divisoria (watershed). El nombre en inglés viene tomado de las divisorias de agua, accidentes geográficos que marcan el límite entre dos cuencas hidrográficas contiguas. Esta técnica consiste en interpretar metafóricamente una imagen en escala de grises de dos dimensiones como un relieve topográfico de tres, siendo la intensidad de píxel interpretada como relieve. Si se vertiera una gota de agua en este mapa topográfico, esta iría a parar a una cuenca, que no es más que un punto de la imagen con un mínimo local de intensidad. Las divisorias en este caso serían los limites entre cuencas adyacentes. A partir de diferentes técnicas que siguen este proceso descrito mediante la metáfora topológica es posible obtener las divisorias o límites de la imagen, así como diferentes regiones dentro de las imágenes. 4.3 Superpixel-Based Fast Fuzzy C-Means Clustering for Color Image Segmentation 19 (a) Imagen original. (b) Superpixel (N = 200). (c) Superpixel (N = 600). Figura 4.11 Ejemplo de aplicación de algoritmo superpixel. (a) Imagen original. (b) Distancias entre objetos. (c) Resultado de aplicar watershed. Figura 4.12 Ejemplo de aplicación de watershed. La Figura 4.12 contiene un ejemplo muy simple de aplicación de un algoritmo de transformación divisoria. Partiendo de una imagen original compuesta por dos circulos superpuestos, es posible, calculando las distancias entre ellos, obtener una división de estos objetos de manera eficaz. 4.3 Superpixel-Based Fast Fuzzy C-Means Clustering for Color Image Segmentation Para finalizar el estudio del estado del arte, se ha elegido un algoritmo actual para su estudio e implementación en el proyecto. El objetivo es encontrar un algoritmo lo suficientemente avanzado y eficaz para obtener los mejores resultados posibles en segmentación. El algoritmo elegido para su aplicación en el proyecto se denomina Superpixel-Based Fast Fuzzy C- Means Clustering for Color Image Segmentation (2019) [ 17 ] y es una mezcla de varias técnicas ya vistas anteriormente como su propio nombre indica. Un detalle importante de este algoritmo es que la segmentación se realiza sobre una imagen a color, algo que en la mayoría de otros algoritmos se omite por su complejidad, pero que puede llegar a ofrecer un plus de información que permita mejorar sus resultados. Este algoritmo presenta una eficiencia computacional muy elevada en el uso de imágenes a color respecto a otros algoritmos similares, lo que lo hace muy apropiado para el proyecto. Entrando en detalles de su composición, el algoritmo principal está compuesto por dos algoritmos consecutivos de superpixel que funcionan de diferente manera. •Superpixel-based on MMGR-WT. Este primer algoritmo consiste en una sucesión de transformaciones basadas en superpixel que ofrecen una imagen segmentada parcialmente. Inicialmente, como suele ser común en muchos algoritmos de este tipo, se obtiene el gradiente de imagen, pero ya que vamos a tratar la imagen a color, se obtiene para cada una de las capas de color. En este caso, en lugar de trabajar sobre el espacio de color RGB, se trabaja sobre el espacio LAB, para poder acceder directamente a un canal con la información de luminosidad de la imagen. 20 Capítulo 4. Estado del arte A continuación, se aplica un algoritmo MMGR (Multiscale Morphological Gradient Reconstruction) que realiza un conjunto de operaciones morfológicas sobre el gradiente para obtener una sobresegmentación, eliminando ruido e imperfecciones y mejorando el contorno de los objetos. Este proceso está controlado por varios parámetros que fijan la precisión y que pueden ser modificados según la complejidad de los contornos de la aplicación para obtener un mejor funcionamiento. Por último, se realiza un algoritmo WT (Watershed transform) como el visto anteriormente. Siguiendo con la metáfora explicativa, el algoritmo busca las lineas divisorias entre las cuencas marcadas por los mínimos locales, ofreciendo una imagen compuesta por superpíxeles. En la Figura 4.13 puede observarse un ejemplo de los resultados obtenidos en cada uno de los pasos del algoritmo. (a) Imagen original. (b) Gradiente de imagen. (c) Resultado de MMGR. (d) Resultado de WT. Figura 4.13 Resultados de Superpixel-based on MMGR-WT. •Superpixel-based Fast FCM. La segunda y última parte realiza un enfoque similar a la primera basado en superpixel, pero en este caso realizando un procedimiento diferente. El algoritmo utilizado se denomina Fast Fuzzy C-means, y es una variación de segmentación por agrupación similar a k-means, descrita anteriormente. El algoritmo trata de minimizar una función objetivo sujeto a varios parámetros configurables como en el caso anterior, siendo en este caso muy relevante uno que indica el número de agrupaciones (clusters) que se desean finalmente, ya que el resultado variará según este valor. En la Figura 4.14 se muestran los resultados obtenidos con la imagen original del ejemplo anterior, mostrando el resultado para varios valores de número de agrupaciones. 4.3 Superpixel-Based Fast Fuzzy C-Means Clustering for Color Image Segmentation 21 (a) Imagen original. (b) N = 2. (c) N = 4. (d) N = 8. Figura 4.14 Resultados del algoritmo para diferentes números de agrupaciones. 5 Desarrollo del sistema Es tablecidos todos los elementos previos, es posible empezar con el desarrollo del sistema en sí. La Figura 5.1 muestra el diagrama general de bloques que sintetiza la organización de la solución propuesta. Debido a la complejidad se ha utilizado un modelo de bloques interconectados entre sí, mejorando la organización y eficiencia del trabajo, permitiendo abordar los problemas de forma más ordenada. En los sucesivos apartados de este capítulo se describen los diferentes bloques en profundidad. Figura 5.1 Diagrama general del sistema. 23 24 Capítulo 5. Desarrollo del sistema Es posible observar en el diagrama que existen dos diferentes entornos: uno para la toma de imágenes y otro para el procesamiento. Estos entornos son diferentes debido a las tecnologías usadas para implementarlos. En color rojo podemos encontrar los bloques encargados de la primera parte, la adquisición de imagen: su papel es tanto la toma como el tratamiento inicial de la imagen, de forma que esta se presente sin distorsiones y organizada convenientemente. Las imágenes tomadas de ambas caras de la llave pasan al bloque del análisis de llave, donde tras un proceso de tratamiento y análisis se obtienen una serie de características comunes de la llave de entrada. Estas características son puestas en común y valoradas en un clasificador de tipo bayesiano ingenuo, donde son comparados con los datos existentes de perfiles reales, obteniendo valores de probabilidad de coincidencia de los datos obtenidos con los perfiles reales. A partir de los resultados del clasificador en el primer descarte se produce una bifurcación en la ejecución: si encuentra más de un perfil de llave coincidente con las características obtenidas, es necesario un análisis más profundo. En este caso se realiza el análsis de cortes para extraer información de ellos que puedan determinar en una segunda ejecución del clasificador bayesiano cual es el perfil de la llave. En cualquier caso, el último paso común consiste en obtener la codificación de los cortes. Finalmente, el programa ofrece como salida el perfil de la llave identificado y la codificación de los cortes de la llave. Una vez explicadas las interacciones generales de los grandes bloques, es necesario revisar el funcionamiento interno de cada uno de estos bloques. 5.1 Adquisición y tratamiento inicial de imágenes El primer paso en la digitalización de llaves consiste en la toma de imágenes de estas, las cuales servirán de entrada principal para el resto del software de digitalización. La calidad y características de las fotografías utilizadas es muy importante ya que pueden limitar mucho la posibilidad de obtención de características o procesos de software posteriores, por lo que es necesario crear un entorno que permita tomar fotografías con suficiente calidad. Debido a la naturaleza de las operaciones necesarias, para la implementación de este bloque es necesario crear un entorno físico de adquisición, a diferencia del resto de los bloques de la aplicación que están basados unicamente en software. A continuación se describen tanto el entorno creado como las diferentes cuestiones de software tenidas en cuenta para la realización de este bloque. 5.1.1 Entorno de adquisición de imágenes Es necesario tener en cuenta muchos factores a la hora de crear un entorno físico para la toma de imágenes, de forma que una vez implementado estas dispongan de la mayor calidad posible, teniendo en cuenta diferentes factores adicionales como tamaño, coste o simplicidad. Figura 5.2 Esquema del entorno de adquisición de imágenes. 5.1 Adquisición y tratamiento inicial de imágenes 25 En la Figura 5.2 se representan esquemáticamente los elementos que conforman este entorno, que son los siguientes: •Cámara. Elemento principal del entorno de adquisición, es necesario que tenga una buena resolución para poder obtener imágenes con suficiente calidad y disponer de una conectividad sencilla para poder obtener y procesar las imágenes. Se coloca dentro de la caja, enfocando hacia la pantalla LCD, donde se coloca la llave. •Pantalla LCD. Se coloca al fondo de la caja con la función de aplicar una iluminación blanca uniforme detrás de la llave, de forma que sea mucho más sencillo controlar y equilibrar la iluminación recibida por la llave, que es colocada encima. •Caja. Espacio contenedor que contiene la cámara y pantalla y los aísla de la iluminación exterior, debe ser posible abrirlo para introducir y sacar las llaves que vayan a procesarse, y con tamaño para poder contener estos elementos. Es necesario que el interior de este sea uniforme y de color negro, para evitar la mayor cantidad de reflexiones posibles de la pantalla LCD. •CPU. Elemento procesador conectado a la cámara y pantalla LCD que gestiona su funcionamiento y ejecuta el software de adquisición de imágenes. En la Figura 5.3 se muestran algunas imágenes del prototipo del entorno de adquisición implementado. Figura 5.3 Fotografías del prototipo de entorno de adquisición de fotografías completo. 26 Capítulo 5. Desarrollo del sistema Se ha utilizado una caja de cartón reforzado ya que permite acceder al contenido de manera muy sencilla y es fácilmente modificable. Para el procesamiento se ha optado por utilizar una Raspberry Pi 4B [ 11 ], ya que tiene un precio muy asequible y es muy sencilla de utilizar, conectar y programar. Por simplicidad, se ha elegido un módulo de cámara de alta definición para la Raspberry Pi [ 12 ], con una lente adicional que permite tomar imágenes de más de 12 megapixeles de resolución. Estas elecciones garantizan la calidad necesaria para las fotografías y proporcionan una solución sencilla de conectividad entre los diferentes elementos. La pantalla LCD elegida también es un accesorio diseñado para Raspberry Pi por lo se mantiene la premisa de la sencilla conectividad y configuración. Para garantizar una mayor uniformidad en la iluminación de la pantalla y evitar el mallado visible de los píxeles, se ha colocado un forro de papel vegetal encima de la pantalla LCD que hace la función de pantalla. (a) Soporte de cámara. (b) Raspberry Pi. (c) Pantalla LCD. (d) Agujero de cámara. Figura 5.4 Detalles del prototipo de entorno de adquisición de fotografías. Otro elemento importante es garantizar que las fotografías se toman siempre en las mismas condiciones y posición, por lo que es necesario fijar los diversos elementos a la caja. Para la cámara, se ha diseñado un soporte e impreso en 3D tal y como se muestra en la Figura 5.4-a, colocado encima de la caja permite a la lente enfocar dentro de la caja mediante un agujero hecho encima de esta. En el fondo de la caja se ha fijado una base de corcho con perforaciones para que la pantalla LCD permanezca fija, mostrado en la Figura 5.4-c. Se han realizado algunas aberturas en la caja para pasar los cables de alimentación y se ha realizado un soporte con tornillos en la tapa de la caja para fijar la Raspberry Pi a esta. 5.1.2 Software de adquisición y calibrado de cámara Una vez realizado el prototipo del entorno de adquisición es necesario configurar sus elementos y desarrollar software para automatizar, simplificar y maximizar la calidad la toma de fotos. 5.1 Adquisición y tratamiento inicial de imágenes 27 Tanto la cámara como la pantalla son controlados mediante la Raspberry Pi, la cual puede ser controlada remotamente utilizando aplicaciones como SSH. A partir de un sencillo script bash se gestiona tanto el display de la pantalla LCD como la toma de imágenes, de forma que cada vez que se ejecute se toman dos fotografías del interior de la caja, pidiendo al usuario entre una y otra que de la vuelta a la llave, de forma que se tomen fotos de ambas. La imagen se toma con el menor tiempo de exposición posible para obtener una imagen oscura, en la cual sea posible distinguir de manera sencilla el fondo iluminado blanco de la pantalla LCD y el contorno negro sin iluminar de la llave. En la Figura 5.5 se puede apreciar las imágenes resultantes obtenidas mediante este script. Figura 5.5 Set de imágenes de entrada tomadas sobre una misma llave. Aunque la toma de fotografías está completa, es necesario solucionar un par de problemas relativos a la cámara. El primero y más evidente es la existencia de una elevada distorsión de ojo de pez en las imágenes obtenidas. Es posible comprobar como las esquinas de las imágenes no se muestran rectas, curvando las llaves, lo que con toda seguridad causará errores de medida y detección en bloques posteriores. Para solucionar este problema se debe realizar una calibración de la cámara, obteniendo así unos parámetros de distorsión que describen el comportamiento de la cámara y a partir de los cuales podemos revertir para conseguir eliminar este efecto de ojo de pez. Para realizar esto, se han utilizado una serie de herramientas de la librería Computer Vision de MATLAB. El procedimiento consiste en realizar una serie de fotografías con la cámara a calibrar sobre un tablero de ajedrez de ciertas características, en diferentes ángulos y posiciones. De esta forma, conociendo que el tablero está compuesto de lineas rectas y la medida del lado de los cuadros, esta herramienta consigue devolver un parámetro descriptivo de la cámara, mediante el cual es posible revertir la distorsión producida. La Figura 5.6 muestra algunos elementos y capturas del proceso de calibrado de la cámara. Figura 5.6 Imágenes tomadas sobre el patrón tablero de ajedrez para realizar la calibración. 34 Capítulo 5. Desarrollo del sistema (a) Derivada enventanada. (b) Shoulder detectado. Figura 5.14 Funciones de contorno y derivada en llave con doble shoulder. Detección de boca Respecto a la detección del tipo de boca de la llave, es preciso recordar que existen dos tipos de bocas, mostrados en la Figura 3.3 sobre imágenes de llaves reales y en la Figura 5.15 sobre funciones de contorno. El factor diferencial entre ambos reside en la forma que el contorno inferior de la llave pasa de la hoja a la boca, por lo que es lógico plantear la detección sobre la derivada de la función de contorno inferior, similar a lo realizado en la detección de shoulder. (a) Tipo 1. (b) Tipo 2. Figura 5.15 Función de contorno en boca de diferentes tipos. Las funciones derivadas de la función de contorno inferior se muestran en la Figura 5.16, pudiendo observar sus diferencias. Las bocas del primer tipo tienen una subida prácticamente constante que puede traducirse en un nivel de pendiente que crece en un determinado momento y se mantiene constante. Por el otro lado, las bocas del segundo tipo tienen una doble subida, existiendo un momento de pendiente nula entre ambas subidas. Es necesario buscar un método para conseguir distinguir automáticamente estos dos patrones. Como solución se plantea contar cuantas veces la derivada supera un cierto valor umbral, suponiendo de esta forma que en el tipo 1 solo se superará una vez y se mantendrá por encima de ese valor hasta el final y que en el tipo 2 se superará dos veces al volver el valor de derivada a un valor nulo. Este umbral es doble, ya que se considera apropiado que este detector tenga histéresis [ 19 ] para evitar que posibles oscilaciones generen errores de detección. Los umbrales se calculan a partir de un promediado de pendiente en el resto de la hoja. En la Figura 5.16 también se muestran los umbrales obtenidos y los cruces de ambos. Se puede 5.3 Análisis de cortes 35 comprobar como en ambos casos la detección es correcta, evitando en el segundo caso un posible error gracias a la histéresis del detector. (a) Tipo 1. (b) Tipo 2. Figura 5.16 Derivada de función de contorno de boca y umbral de detección. 5.3 Análisis de cortes El segundo bloque de análisis de características de la llave se centra en los cortes de la llave, los cuales contienen muchos parámetros de información adicionales que serán determinantes para identificar el perfil de la llave de entrada. Tal y como se puede observar en el diagrama general de la Figura 5.1, este bloque solo se ejecuta en caso de no obtener una coincidencia única en el primer descarte, ya que el proceso conlleva cierto riesgo de error que conviene evitar. En la Figura 5.17 se muestra un diagrama de bloques orientativo del proceso de análisis de cortes, el cual se explica a continuación. Figura 5.17 Diagrama de bloques del análisis de cortes. El análisis se realiza sobre la función de contorno de hoja obtenida en el bloque anterior, evitando tener que realizar nuevamente el procesado de imagen. Debido a que es un análisis complejo que puede no ofrecer los resultados esperados en la primera ejecución, se plantea una estructura iterativa que ejecuta el algoritmo 36 Capítulo 5. Desarrollo del sistema de análisis varias veces hasta encontrar una solución válida, maximizando de esta manera la probabilidad de acierto. Ya que el análisis se realiza sobre los máximos y mínimos de la función de contorno superior de la hoja, es de mucha utilidad suavizar las rugosidades del contorno realizando un promediado móvil de la función. Por lo tanto, la longitud del promediado será el parámetro sobre el que se iterará en las diferentes ejecuciones, pasando de un valor pequeño a uno cada vez mayor. En la Figura 5.18 se muestran las funciones de contorno de una hoja sin y con suavizado, mostrando a su vez los máximos y mínimos obtenidos. Es posible comprobar que sin modificar mucho la forma del contorno, el suavizado ofrece unos resultados más limpios y claros desde el primer momento ya que evita rugosidades que provocan valores extremos sin interés para el análisis. (a) Sin suavizado. (b) Suavizado de 0.3 mm. Figura 5.18 Funciones de hoja y valores extremos sin y con suavizado. Debido a que tanto el principio como el final de la hoja pueden presentar formas que pueden ser problemáticas para el algoritmo de reconocimiento, se crea una ventana de valores límites de cortes en base a los parámetros reales de las posibles llaves que pueden ser reconocidas. De esta manera eliminamos un riesgo con seguridad de no dejar fuera de la ventana ningún recorte posible. El núcleo del algoritmo de búsqueda de cortes se basa en la búsqueda de máximos y mínimos (valores extremos) en el contorno superior de la hoja. A partir de estos valores, es necesario hacer una limpieza para obtener en los mínimos los valores coincidentes con los cortes. Estas tareas de limpieza son dos principalmente: eliminación de próximos y centrado: •Eliminación de próximos: este proceso se encarga de reducir rachas de máximos y mínimos muy próximos a un único punto extremo. Esto es necesario ya que en la mayoría de los casos existe un gran número de extremos relativos debido a la irregularidad del contorno de la hoja, incluso después de realizar el suavizado de la función. El algoritmo obtiene rachas de valores extremos que tengan una distancia menor a medio milímetro, de forma que reduce la racha a un único valor extremo, dependiendo de las características de la racha y su entorno. •Centrado de puntos: a continuación es necesario centrar los valores extremos restantes para poder obtener un valor más fiel de la localización del corte, por ejemplo. Debido a las diversas formas de los cortes, el mínimo que lo describe puede encontrarse a un punto u otro del valle, algo que distorsiona la medida de la localización del corte. Para solucionar esto, se miden las paredes del corte y se mueve el valor extremo medido hacia un punto intermedio, donde es más lógico y probable que se encuentre el corte. Ambos procesos se realizan algunas veces hasta que dejan de producirse cambios en los valores extremos obtenidos, tal y como puede apreciarse en la Figura 5.19. Los valores iniciales en los cortes muestran varios máximos y mínimos consecutivos, eliminados en el segundo paso debido a que son próximos. Aunque el cambio es leve, el último paso centra los máximos y mínimos en el punto exacto, aumentando la precisión de las medidas. 5.3 Análisis de cortes 37 (a) Valores iniciales. (b) Eliminación de próximos. (c) Centrado de puntos. Figura 5.19 Pasos del proceso de limpieza de valores extremos. Posteriormente, se realizan una serie de verificaciones para comprobar que los mínimos tienen una separación mínima y son coherentes, asumiendo que estos puntos son los cortes encontrados. Adicionalmente se almacenan otros valores como los máximos, el número de cortes, la diferencia entre ellos y la profundidad a la que se encuentran los cortes. Una vez obtenidos los valores provisionales, se realiza una comparación del número de cortes obtenido con los posibles valores de número de cortes que existen en los diferentes perfiles, eligiendo el que coincida en caso de hacerlo. En caso de que el número de cortes sea menor del mínimo o mayor que el máximo se realizan dos procesos para completar la información de cortes a partir de los valores anteriormente calculados: •Cortes en defecto: en el caso de que hayamos obtenido menos cortes que los existentes en el contorno de la llave, el caso más probable que se valora es la posibilidad de haber ignorado un corte por estar en una posición alta. Esto significa que los algoritmos de limpieza explicados anteriormente probablemente lo hayan catalogado como un máximo, siendo algo usual en algunos tipos de perfiles. Para obtener el máximo correcto se realiza una valoración en torno a la diferencia de distancia entre los cortes existentes. Estos valores se comparan con un promediado de los valores de distancia entre cortes de los perfiles reales, obteniendo una aproximación de cual debería ser la distancia entre los cortes. Esta función tiene en cuenta diversos posibles casos como que hay varios cortes menos detectados de los necesarios o que el corte restante esté en un extremo. En la Figura 5.20-a puede comprobarse un caso de corte detectado como máximo, detectado mediante esta función. •Cortes en exceso: para el caso contrario, se valora el caso de que las funciones de limpieza no han funcionado correctamente y se han quedado más mínimos de los cortes posibles en una llave. En este caso se realiza un análisis similar de las diferencias entre las posiciones de los cortes, siendo posible detectar los cortes falsos como aquellos muy cercanos a dos cortes consecutivos, uno si son extremos. En la Figura 5.20-b se puede comprobar el funcionamiento de esta función. 38 Capítulo 5. Desarrollo del sistema (a) Defecto de cortes. (b) Exceso de cortes. Figura 5.20 Ejemplos de ajustes de número de cortes. Una vez determinado el número exacto y la localización de los cortes, es posible extraer el resto de características de utilidad como la profundidad del corte o la diferencia entre ellos y pasar a comparar los valores obtenidos con los de los perfiles reales. 5.4 Clasificador bayesiano El último de los bloques se trata del clasificador, cuya función es valorar las características frente a los perfiles reales y obtener cual es más coincidente. El tipo de clasificador utilizado es conocido como clasificador bayesiano ingenuo [ 28 ], cuya principal característica es la presunción de independencia en la probabilidad entre las características comparadas en él. Esto simplifica mucho el entrenamiento del clasificador, siendo únicamente necesarios parámetros reales de cada una de sus características y no sus dependencias entre ellos. Siguiendo el desarrollo teórico del teorema de Bayes, obtenemos la formulación mostrada en (5.1). p(C|F1,...,Fn) = p(C)p(F1,...,Fn|C) p(F1,...,Fn)=p(C,F1,...,Fn) p(F1,...,Fn)(5.1) La probabilidad a posteriori significa la probabilidad que tiene la llave analizada de ser cada uno de los diferentes perfiles analizados, por lo tanto es la probabilidad que queremos obtener. Esta se calcula a partir de una probabilidad a priori de cada perfil y una probabilidad condicionada, que pueden ser convertidas mediante la definición de probabilidad condicionada [ 27 ] en una probabilidad compuesta. Aplicando la condición de independencia mencionada anteriormente, se puede simplificar a la expresión de la (5.2). p(C,F1,...,Fn) = p(C) n ∏ i=1 p(Fi|C)(5.2) Como se puede observar, este valor consiste en la multiplicación de las probabilidades a priori y las probabilidades condicionadas con cada una de las características evaluadas. El denominador de (5.1) es conocido como evidencia, pero debido a que para todos los casos es el mismo valor, podemos evitar calcularlo de manera directa y solamente comparar los denominadores. Una vez conocido el razonamiento matemático detrás del clasificador, es necesario conocer las diferentes funciones de probabilidad condicionada que aplican según las características. En concreto, son dos tipos diferentes: •Función de probabilidad normal: es utilizada en las características medidas en unidades de longitud, por ejemplo el largo y ancho de la hoja o la localización de los cortes. La función de probabilidad normal requiere de dos parámetros: media y varianza. En este caso usamos como media el valor real especificado para cada perfil y como varianza un valor experimental aproximado obtenido a partir 5.4 Clasificador bayesiano 39 de los errores de varias medidas para cada llave. En la Figura 5.21 se observan las diferentes curvas normales generadas para cada tipo de perfil ante una misma característica. •Función de probabilidad binomial: es utilizada en características que precisan de valores precisos y enteros, como son el número de shoulder, cortes o tipo de boca. En este caso la distribución es muy sencilla: si el valor obtenido experimentalmente coincide con el valor de la especificación del perfil, la probabilidad condicionada es uno, si no, cero. Figura 5.21 Funciones de probabilidad condicionadas de cada perfil a la longitud de hoja. El procedimiento realizado en cada bloque de clasificador es estructuralmente similar, excepto alguna excepción. Inicialmente se crean las funciones de probabilidad condicionada para cada característica y perfil existentes, sean el tipo de función que sean. Posteriormente, se introduce el valor obtenido experimental en dichas funciones y se obtiene el valor de probabilidad condicional. Tal y como dice (5.2) , multiplicando la probabilidad a priori con las probabilidades condicionales es posible obtener el denominador de la función de probabilidad a posteriori de cada tipo de perfil. El valor de probabilidad concreto es posible obtenerlo escalando este valor para que la suma de las probabilidades sume siempre la unidad. La Figura 5.22 muestra de las probabilidades obtenidas en una ejecución del clasificador para el primer descarte. Figura 5.22 Probabilidades a posteriori obtenidas después del primer descarte. 40 Capítulo 5. Desarrollo del sistema Como se muestra en el diagrama de bloques de Figura 5.1, existen dos bloques de clasificador, realizando el mismo proceso para diferentes características. Como se ha mencionado, los procesos son estructuralmente iguales pero varían las características utilizadas y algunas particularidades. Respecto a las probabilidades a priori, en el caso del primer descarte se consideran todos los perfiles equiprobables ya que no tenemos información previa, mientras que en el segundo descarte las probabilidades a priori son las probabilidades a posteriori obtenidas en el primer descarte. Por otro lado, como salida del primer descarte se muestran todas las llaves con probabilidad superior a cierto umbral, de manera que se puedan seguir analizando características para las llaves restantes. En el segundo descarte se elige la llave con mayor probabilidad, ya que todas las características han sido tenidas en cuenta en el clasificador. 6 Validación y resultados Co mpleto el desarrollo de la aplicación y la creación del prototipo de captura de imagen, es posible realizar varias pruebas para validar el funcionamiento de diferentes partes del sistema. Este capítulo contiene una descripción y muestra de las diferentes pruebas realizadas, así como datos sobre los resultados obtenidos, tanto cuantitativos como cualitativos, según aplique. Para la realización de las pruebas es necesario disponer de un set de recursos de entrada. Todas las pruebas realizadas se enfocan a la aplicación, ya que el funcionamiento del entorno de captura de imágenes no tiene prácticamente capacidad de fallar una vez configurado y montado correctamente. Por este motivo, es más sencillo tomar como entradas de las pruebas las imágenes tomadas con el sistema de adquisición de imágenes, pero no emplearlo en dichas pruebas, siendo mucho más cómodo y rápido la ejecución de estas. Los ficheros de entrada utilizados en dichas pruebas consisten en 43 sets de imágenes tomadas sobre llaves diferentes, conteniendo cada uno dos imágenes (una por cada cara). Cada uno de estos sets contiene una identificación sobre el perfil del que se trata y su codificación. Por otro lado, las especificaciones utilizadas como entrada están formadas por 20 archivos, por lo que la aplicación debe identificar cada llave de las imágenes de entrada entre 20 tipos de perfiles diferentes. El set abarca 17 perfiles diferentes, por lo que prácticamente se abarcan la totalidad de las posibilidades de la aplicación. Figura 6.1 Ficheros de especificaciones utilizados. Debido a la complejidad de la aplicación se han propuesto varios conjuntos de pruebas, abarcando diferentes niveles de complejidad, abstracción y tipos de datos. Concretamente, se han realizado pruebas más concretas sobre el tratamiento de la imagen y la medida de cada una de las características. Una vez abordados los problemas y comportamientos obtenidos en ambos procedimientos se realiza una validación general sobre el comportamiento de la aplicación en cuanto a la identificación del perfil y el código de la llave. 41 42 Capítulo 6. Validación y resultados 6.1 Validación de tratamiento de imagen La primera de las pruebas de validación consiste en evaluar el funcionamiento de las primeras partes de la aplicación, concretamente el tratamiento de imagen, que comprende los procesos de segmentación y perfilado. Adicionalmente, se evalúa la detección de shoulder, ya que son los procesos consecutivos. Todos los bloques y procesos contienen en mayor o menor medida comprobaciones para evitar que se continúe la ejecución en caso de mal funcionamiento, aunque es posible que estos errores sean difíciles de detectar automáticamente, especialmente en procesos que involucren tratamiento de imagen. Por este motivo, la validación de estos procesos se realiza manualmente, mediante una inspección visual de los resultados. Es inmediato reconocer a simple vista si la segmentación se ha realizado correctamente o el perfil de la llave se ha generado recto y en la orientación esperada. Por lo tanto, la prueba realizada consiste en ejecutar estos tres procesos sobre las llaves de entrada de cada uno de los sets de imágenes, representando figuras como las mostradas en la Figura 6.2. Concretamente, se representan la imagen de entrada, la imagen binaria producto del proceso de segmentación y la función de contorno obtenida a partir del proceso de perfilado. Además, se indica sobre la función de contorno la localización del shoulder detectado. Figura 6.2 Figuras representadas del tratamiento de imagen para inspección visual. Los resultados de la prueba realizada se muestran en la Tabla 6.1. Debido a que la gran mayoría de las llaves se procesan satisfactoriamente es posible considerar la prueba un éxito, exceptuando fallos puntuales. Tabla 6.1 Resultados de validación de tratamiento de imagen. Segmentación Perfilado Det. Shoulder Total Aciertos 43 40 40 40 (93.02%) Fallos 0 3 0 3(6.98%) 6.2 Validación de las medidas de características 43 Entrando en detalle de cada parte, se ha comprobado que la segmentación funciona perfectamente, en ningún caso el contorno de la llave era diferente al esperado. Por otro lado, la parte de perfilado si contiene tres errores de ejecución. Dos de ellos han sido detectados por las comprobaciones realizadas en la aplicación, ya que no ha sido posible encontrar la recta de la hoja, un error algo común en imágenes tomadas incorrectamente, que convienen que sean descartadas. El otro caso, detectado mediante inspección visual, ocurre al confundir la recta de la hoja de la llave con una parte de la cabeza que es recta, produciendo un perfil incorrecto de la llave. En ninguno de los casos se presenta peligro para el funcionamiento ya que estos casos serían detectados en la misma aplicación y se solicitaría una nueva imagen que posiblemente funcionase. Por último, la detección de shoulder funciona correctamente en todos los casos restantes, como se indica en la tabla. Aunque la precisión varía dependiendo de los casos, debido a que existen una gran cantidad de tipos de shoulder, el error es mínimo y se considera un funcionamiento correcto siempre que el shoulder se localice a una distancia pequeña del shoulder real. 6.2 Validación de las medidas de características La segunda y última prueba específica realizada se centra en la calidad de las medidas obtenidas sobre las llaves. Es muy importante pues permite analizar el funcionamiento de estos bloques, que a diferencia de los anteriores no es posible analizar mediante inspección visual de manera cualitativa. Se ha creado un script de prueba en la que se ejecutan todos los pasos de análisis de llave y cortes sobre cada una de las imágenes, pudiendo obtener el error obtenido gracias a que cada archivo contiene el nombre del perfil real de la llave de la imagen y es posible obtener a partir de este las especificaciones del perfil. Como se indicó anteriormente, las características medidas se dividen en valores de longitud expresando medidas y distancias y valores enteros que indican cantidades, por lo tanto se dividen en varios grupos para el análisis. 6.2.1 Dimensiones de hoja Las primeras características analizadas son las medidas de las dimensiones de la hoja, que aunque son medidas relativamente sencillas de obtener, su precisión pueden determinar errores acumulados en procesos previos u otros problemas externos a la propia medida. Comenzando con la anchura, podemos observar en la Figura 6.3 la distribución estadística obtenida de los errores obtenidos, justo a una curva de una distribución normal sobre la que se ajustan los datos. Debido a que la cantidad de medidas es limitada la curva no se ajusta completamente, pero ofrece muchos datos de interés. El mismo procedimiento es realizado con la longitud de la hoja en la Figura 6.4. Figura 6.3 Distribución de los resultados de error de ancho de hoja obtenidos. 50 Capítulo 6. Validación y resultados Es interesante obtener el porcentaje de error en cada uno de los perfiles analizados, tal y como se muestra en la Figura 6.12. La conclusión más directa es que las llaves con características más peculiares tienen un porcentaje de error menor, incluso nulo. Ejemplos de esto son el perfil FAC-11D (gran longitud de hoja), DOM-1D, IS-1D (menor longitud), CVL-5 (doble shoulder y boca del tipo más inusual), etc. Es notorio que estas características de carácter binario discriminan mucho entre las llaves, por lo que son mucho más útiles. Figura 6.12 Porcentaje de error por perfil. Como ya se ha mencionado anteriormente, existen ciertos perfiles que pueden ser realizados mediante un perfil universal, algo común en la industria para ahorrar costes. Aunque tienen características diferenciadas como la localización de los cortes o ángulos y valle, esto hace que sean muy similares en general entre ellas. En concreto, de las llaves analizadas esto ocurre con las llaves AZ-1D, CAY-1D, CI-DL e IS-3D, las cuales tienen todas un elevado porcentaje de error, algo llamativo de cara al análisis. Comprobando con qué perfiles se han confundido las llaves del grupo de perfil universal que han sido identificadas incorrectamente, obtenemos que en todos los casos se corresponde con otra llave del mismo grupo. Esto es relevante pues indica que hay un paso intermedio de identificación correcto, pero es necesario ahondar en la extracción de características para determinar correctamente cual de los perfiles es, ya que son muy parecidos entre sí. 7 Conclusiones Am odo de broche final, se exponen las conclusiones obtenidas con la ejecución de cada una de las fases de diseño documentadas en este documento. Debido a que es un proyecto con una parte importante de investigación, es muy importante obtener unas conclusiones claras y organizadas del trabajo realizado, así como de los resultados obtenidos. Estas conclusiones son necesarias para continuar mejorando el diseño de la aplicación, por lo que se listan algunas de las ideas principales sobre las que se considera necesario trabajar en el futuro para lograr un mejor funcionamiento del sistema diseñado. A pesar de que el sistema ha sido desarrollado, los resultados indican que el objetivo de este no han sido cumplidos en su totalidad, ya que tanto el reconocimiento como la identificación funcionan en aproximadamente la mitad de los casos que se han probado. Por ello, es preciso realizar mejoras que permitan que el sistema proporcione un comportamiento aceptable para poder llegar a plantearse el sistema a nivel comercial. Por otro lado, ambos elementos del sistema han sido desarrollados con éxito, siendo resultado final un prototipo completamente funcional tanto en la parte hardware como software. Sin embargo, la aplicación necesita varias mejoras para poder proporcionar un comportamiento suficiente para que pueda plantearse el sistema a nivel comercial. Sin embargo, como ya se indicó en un principio, el objetivo principal consiste en la investigación de los procesos y limitaciones necesarios, algo que si se puede considerar cumplido con creces, ya que numerosas tecnologías y procedimientos han sido llevados a la práctica para conocer sus limitaciones y ventajas. El fruto de todos los análisis y desarrollos realizados es una recopilación de ideas y vías de desarrollo futuras con las que conseguir mejorar y ampliar el funcionamiento del sistema hasta poder completar con éxito el objetivo de la aplicación de proporcionar una identificación y decodificación exitosa. 7.1 Futuras vías de desarrollo A partir de estas conclusiones se propone una lista de vías de desarrollo a seguir para mejorar el funcionamiento del sistema creado, detalladas a continuación: •Detección de nuevas características de contorno. Se ha comprobado que en muchos casos las características obtenidas han sido insuficientes para determinar el perfil con precisión. Debido a los errores de medida, cuanto mayor sea el número de características medidas, menor será la probabilidad de que el perfil real sea confundido con otro. Algunas de estas características se incluyen en los ficheros de especificación actuales como los valores de ángulo y valle, los cuales son más complejos de obtener pero pueden proporcionar mucha información para la identificación. Por otro lado, también es posible pensar en nuevas características no presentes aun en los ficheros de especificación. Es posible realizar un estudio externo como se realizó para clasificar el tipo de bocas, característica que ha sido de mucha utilidad para identificar los perfiles y cuya detección ha sido relativamente simple y efectiva. •Añadir detección de características superficiales. Aunque este tipo de llaves contienen mucha información en sus elementos de contorno, existen características como los canales que solo son apreciables 51 52 Capítulo 7. Conclusiones realizando un análisis de la superficie de la llave. Esto supone un reto y un gran cambio en la estructura del sistema, pero puede ser de mucha utilidad. Únicamente obteniendo el número de canales en cada cara de la llave es posible discriminar entre un gran número de perfiles, así como distinguir entre los perfiles espejo, que son idénticos pero con número contrario de canales por cara. •Reducir el error en las medidas existentes. A partir de los resultados obtenidos es posible concluir que los errores de medida tienen un origen diverso, abarcan diferentes ámbitos y se acumulan hasta obtener en algunos casos errores muy elevados que impiden la correcta identificación de las llaves. Es necesario atacar las diversas fuentes de error y reducir estos niveles para aumentar la precisión. A lo largo del análisis de resultados se han descubierto algunas de las fuentes de error más evidentes, por ejemplo la precisión de la proporción milímetro por píxel de la cámara, que arrastra un error proporcional. Por otro lado, existen errores que se desconoce la fuente pero se conoce su naturaleza, como los aditivos que causan que la media de anchura esté muy desviada de valer cero, por lo que aunque no puedan solucionarse de manera sencilla, quizás es posible compensarlos de alguna forma. •Análisis de llaves universales independiente. Se ha comprobado que las llaves de perfiles que pueden realizarse con perfiles universales muestran un gran error de identificación, siendo en todos los casos confundidas entre ellas. Pese a que las soluciones propuestas anteriormente pueden ayudar a solucionar este problema, quizás sea conveniente proporcionar una herramienta de análisis exclusivo para estos tipos de llaves. Esto puede llevarse a otros ámbitos en caso de detectar que existen familias de llaves muy similares que son confundidas por la aplicación a menudo, consiguiendo simplificar el problema principal en problemas menores adaptados a cada circunstancia, lo que es mucho más efectivo que aplicar grandes procedimientos generales. •Mejora de la adquisición de imágenes. Una de las posibles fuentes de error es la calidad de imagen tomada en el entorno de adquisición, siendo además completamente determinante porque es el primer paso y los errores obtenidos se mantienen durante todo el resto del proceso. En este caso existen dos posibles maneras de realizar la mejora: modificando y mejorando los elementos del sistema de adquisición, como la cámara o el sistema de iluminación o modificando el software de captura de imágenes para obtener una configuración más óptima o unas imágenes de entrada diferentes. •Aumentar tipo de llaves analizadas. Esto queda fuera de los objetivos propuestos inicialmente, pero sería el siguiente paso natural para realizar tras completar el sistema para las llaves de sierra. Existen muchos tipos de llaves que comparten un considerable número de características con las llaves de sierra como son las llaves de seguridad. Sería posible aprovechar la gran mayoría de procedimientos para tratar estas llaves y aumentar de esta forma la compatibilidad del sistema. Índice de Figuras 3.1 Diagrama de partes de llave de sierra 5 3.2 Detalle de las características de los cortes 6 3.3 Tipos de bocas de llaves de sierra 6 4.1 Imagen digital transmitida mediante el sistema Bartlane en 1929 9 4.2 Imagen de la superficie de la luna tomada por la nave Ranger 7 de la NASA 10 4.3 Ejemplos de aplicaciones actuales del procesamiento digital de imagen 11 4.4 Ejemplos de aplicaciones de segmentación de imagen 12 4.5 Ejemplo de segmentación usando ambas propiedades 13 4.6 Aplicación de thresholding global sobre imagen 14 4.7 Diferencias entre thresholding global y variable 15 4.8 Resultados de aplicar el operador de Sobel a un imagen 16 4.9 Ejemplo de segmentación por crecimiento de región 17 4.10 Ejemplo de aplicación de algoritmo k-means 18 4.11 Ejemplo de aplicación de algoritmo superpixel 19 4.12 Ejemplo de aplicación de watershed 19 4.13 Resultados de Superpixel-based on MMGR-WT 20 4.14 Resultados del algoritmo para diferentes números de agrupaciones 21 5.1 Diagrama general del sistema 23 5.2 Esquema del entorno de adquisición de imágenes 24 5.3 Fotografías del prototipo de entorno de adquisición de fotografías completo 25 5.4 Detalles del prototipo de entorno de adquisición de fotografías 26 5.5 Set de imágenes de entrada tomadas sobre una misma llave 27 5.6 Imágenes tomadas sobre el patrón tablero de ajedrez para realizar la calibración 27 5.7 Imagen antes y después de corregir la distorsión ojo de pez 28 5.8 Diagrama de bloques del análisis de llaves 29 5.9 Pasos del proceso de segmentación 30 5.10 Rectas y partes de la llave detectadas 31 5.11 Pasos del proceso de perfilado 32 5.12 Funciones de contorno y derivada 33 5.13 Funciones de contorno y derivada en llave con único shoulder 33 5.14 Funciones de contorno y derivada en llave con doble shoulder 34 5.15 Función de contorno en boca de diferentes tipos 34 5.16 Derivada de función de contorno de boca y umbral de detección 35 5.17 Diagrama de bloques del análisis de cortes 35 5.18 Funciones de hoja y valores extremos sin y con suavizado 36 5.19 Pasos del proceso de limpieza de valores extremos 37 5.20 Ejemplos de ajustes de número de cortes 38 5.21 Funciones de probabilidad condicionadas de cada perfil a la longitud de hoja 39 5.22 Probabilidades a posteriori obtenidas después del primer descarte 39 53 54 Índice de Figuras 6.1 Ficheros de especificaciones utilizados 41 6.2 Figuras representadas del tratamiento de imagen para inspección visual 42 6.3 Distribución de los resultados de error de ancho de hoja obtenidos 43 6.4 Distribución de los resultados de error de largo de hoja obtenidos 44 6.5 Error medio relativo del ancho de hoja para cada perfil 45 6.6 Error medio relativo del largo de hoja para cada perfil 45 6.7 Distribución de los resultados de error de localización de cortes obtenidos 47 6.8 Distribución de los resultados de error de diferencia de cortes obtenidos 47 6.9 Error absoluto medio en cada número de corte 48 6.10 Error medio relativo en la localización de cortes por perfil 48 6.11 Error medio relativo en la diferencia de cortes por perfil 49 6.12 Porcentaje de error por perfil 50 Índice de Tablas 6.1 Resultados de validación de tratamiento de imagen 42 6.2 Valores de errores para dimensiones de hoja 44 6.3 Resultados de obtención de número de shoulder y tipo de boca 46 6.4 Resultados de inspección visual de detección de cortes 46 6.5 Valores de errores para dimensiones de hoja 46 6.6 Resultados de identificación y decodificación de la aplicación 49 55 Bibliografía [1] Mr Al-amri, Dr Kalyankar, and Dr S.D, Image segmentation by using edge detection, International Journal on Computer Science and Engineering 2(2010). [2] G. Roth Bradley, D., Adapting thresholding using the integral image, Journal of Graphics Tools 12 (2007), 13–21. [3] J. Canny, A computational approach to edge detection, IEEE Trans. Pattern Analysis and Machine Intelligence 8(1986), 679–698. [4] Rodger Carter, The bartlane transmission system (1920), 2001. [5] Mayo Clinic, Ct scan, 2020. [6] M.J. de Vries, N. Cross, and D.P. Grant, Design methodology and relationships with science, Nato Science Series D:, Springer Netherlands, 1993. [7] NASA History Division, Lunar impact: A history of project ranger, 2006. [8] Jose Dolz, Christian Desrosiers, Li Wang, Jing Yuan, Dinggang Shen, and Ismail Ben Ayed, Deep cnn ensembles and suggestive annotations for infant brain mri segmentation, Computerized Medical Imaging and Graphics 79 (2020), 101660. [9] R. Duda and P. Hart, Pattern classification and scene analysis, 1 ed., John Wiley and Sons, 1973. [10] R. O. Duda and P. E. Hart, Use of the hough transformation to detect lines and curves in pictures, Comm. ACM 15 (1972), 11–15. [11] The Raspberry Pi Foundation, Raspberry pi 4 model b. [12] , Raspberry pi high quality camera. [13] Gang Fu, Hongrui Zhao, Cong Li, and Limei Shi, Segmentation for high-resolution optical remote sensing imagery using improved quadtree and region adjacency graph technique, Remote Sensing 5 (2013), no. 7, 3259–3279. [14] P.V.C. Hough, Method and means for recognizing complex patterns. [15] Jun-Wei Hsieh, Chi-Hung Chuang, Sin-Yu Chen, Chih-Chiang Chen, and Kuo-Chin Fan, Segmentation of human body parts using deformable triangulation, IEEE Transactions on Systems, Man, and Cybernetics - Part A: Systems and Humans 40 (2010), no. 3, 596–610. [16] Dilpreet Kaur and Yadwinder Kaur, Various image segmentation techniques: A review, 2014. [17] Tao Lei, Xiaohong Jia, Yanning Zhang, Shigang Liu, Hongying Meng, and Asoke K. Nandi, Superpixelbased fast fuzzy c-means clustering for color image segmentation, IEEE Transactions on Fuzzy Systems 27 (2019), no. 9, 1753–1766. 57 58 Bibliografía [18] David J. C. MacKay, Information theory, inference and learning algorithms, Cambridge University Press, USA, 2002. [19] R Nave, The schmitt trigger. [20] Nobuyuki Otsu, A threshold selection method from gray-level histograms, IEEE Transactions on Systems, Man, and Cybernetics 9(1979), no. 1, 62–66. [21] Richard Woods Rafael Gonzalez, Digital image processing, 4 ed., Pearson, 2017. [22] Marius Rensen, The bartlane system (coded system), 1995. [23] Jadwiga Rogowska, Handbook of medical image processing and analysis, 2 ed., Academic Press, 2009. [24] Prasanna Sahoo, Sasan Soltani, and Andrew Wong, A survey of thresholding techniques, Computer Vision, Graphics, and Image Processing 41 (1988), 233–260. [25] David Stutz, Alexander Hermans, and Bastian Leibe, Superpixels: An evaluation of the state-of-the-art, Computer Vision and Image Understanding 166 (2018), 1–27. [26] NASA Veronica McGregor, History and archives. jet propulsion laboratory, 2020. [27] Wikipedia contributors, Conditional probability — Wikipedia, the free encyclopedia, 2021, [Online; accessed 19-November-2021]. [28] ,Naive bayes classifier — Wikipedia, the free encyclopedia, 2021, [Online; accessed 19- November-2021].