Técnicas de aceleración para el reconocimiento de piezas de ajedrez

T´ecnicas de aceleraci´on para el reconocimiento de piezas de ajedrez Acceleration techniques for chess piece recognition TRABAJO DE FIN DE GRADO DEL GRADO EN INGENIER´ IA INFORM´ ATICA Curso 2019/2020 UNIVERSIDAD COMPLUTENSE DE MADRID FACULTAD DE INFORM´ ATICA Director: Alberto Antonio del Barrio Garc´ıa Codirector: Manuel Prieto Mat´ıas David Mallas´en Quintana Madrid, 20 de junio de 2020 Resumen La digitalizaci´on autom´atica de partidas de ajedrez mediante visi´on artificial es un reto tecnol´ogico significativo. Es imprescindible tanto para los organizadores de torneos como para jugadores amateurs o profesionales de cara a retransmitir en l´ınea o analizar las partidas mediante motores de ajedrez. En este trabajo primero hemos entrenado y comparado diversas redes neuronales convolucionales para la clasificaci´on de piezas de ajedrez. Posteriormente, hemos acelerado sobre una Nvidia Jetson Nano la detecci´on del tablero y la inferencia de estos modelos, necesarios para una completa digitalizaci´on. Conseguimos as´ı un framework funcional que digitaliza autom´aticamente la configuraci´on de un tablero de ajedrez sobre un sistema empotrado en menos de 5 segundos, con una precisi´on del 92 % al clasificar las piezas y un 95 % al detectar el tablero. Palabras clave Aceleraci´on de redes neuronales, Nvidia Jetson Nano, ONNX, TensorRT, Ajedrez, FEN, Visi´on artificial, Redes neuronales convolucionales, Deep learning, Python. Abstract Automatic digitization of chess games by means of computer vision is a significant technological challenge. It is essential both for tournament organizers and amateur or professional players in order to broadcast online or analyze games using chess engines. In this work, we have first trained and compared different convolutional neural networks for chess piece classification. Subsequently, we have accelerated on a Nvidia Jetson Nano the detection of the board and the inference of these models, required for a complete digitization. Thus achieving a functional framework that automatically digitizes the configuration of a chessboard on an embedded system in less than 5 seconds, with an accuracy of 92 % when classifying the pieces and 95 % when detecting the board. Keywords Neural network acceleration, Nvidia Jetson Nano, ONNX, TensorRT, Chess, FEN, Computer vision, Convolutional neural networks, Deep learning, Python. Agradecimientos En primer lugar, gracias a Alberto y Manuel por pensar en m´ı para este trabajo y por todo su inter´es e innumerables correcciones e ideas durante todo este tiempo. Desde las primeras reuniones con un tablero de ajedrez delante, hasta las sesiones virtuales de los ´ultimos meses. Gracias tambi´en a todos los dem´as profesores que durante estos a˜nos hab´eis hecho que descubra mi vocaci´on y que quiera convertir esta pasi´on en mi profesi´on. Quer´ıa agradecer tambi´en todo el apoyo desde siempre por parte de mi familia. En este caso especialmente el inconformismo de mi madre, que me empuj´o e hizo que no haya estudiado “solo” matem´aticas. No querr´ıa olvidarme de todos mis amigos, est´eis m´as cerca o m´as lejos, de todos aquellos con los que he compartido techo e inquietudes, compa˜neros de clase y personas en general con las que me he cruzado estos a˜nos. Sin vosotros no ser´ıa ni la mitad de feliz de lo que soy ahora. Este trabajo ha sido financiado por la Uni´on Europea (FEDER), el Gobierno de Espa˜na y la Comunidad de Madrid a trav´es de los proyectos RTI2018-093684-B-I00 y S2018/TCS-4423. ´ Indice general ´ Indice de figuras III ´ Indice de tablas IV ´ Indice de algoritmos V 1. Introducci´on 1 1.1. Antecedentes ............................... 1 1.2. Objetivos y plan de trabajo . . . . . . . . . . . . . . . . . . . . . . . 2 2. Detecci´on del tablero 5 2.1. Descripci´on de las iteraciones . . . . . . . . . . . . . . . . . . . . . . 5 2.1.1. Detecci´on de l´ıneas rectas . . . . . . . . . . . . . . . . . . . . 7 2.1.2. B´usqueda de puntos de la cuadr´ıcula . . . . . . . . . . . . . . 8 2.1.3. Identificaci´on de la posici´on del tablero . . . . . . . . . . . . . 10 2.1.4. Fin de la iteraci´on . . . . . . . . . . . . . . . . . . . . . . . . 12 2.2. Obtenci´on de las casillas individuales . . . . . . . . . . . . . . . . . . 13 2.2.1. Nuevom´etodo........................... 14 3. Clasificaci´on de las piezas 17 3.1. Notaci´onFEN............................... 17 3.2. Dataset etiquetado de piezas . . . . . . . . . . . . . . . . . . . . . . . 17 3.3. Entrenamiento de los modelos . . . . . . . . . . . . . . . . . . . . . . 18 3.4. Inferencia ................................. 20 3.4.1. Inferencia en tableros consecutivos . . . . . . . . . . . . . . . 21 4. Aceleraci´on 25 4.1. Plataformas de inferencia . . . . . . . . . . . . . . . . . . . . . . . . . 25 4.2. Optimizadores: ONNXRuntime y TensorRT . . . . . . . . . . . . . . 26 4.3. Detecci´on del tablero . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 4.3.1. Primer an´alisis: Optimizaci´on mediante ONNX . . . . . . . . 29 4.3.2. Segundo an´alisis: Reducci´on del sobrecoste de NumPy . . . . . 29 4.3.3. Tercer an´alisis: Reducci´on del sobrecoste de Bentley-Ottmann 30 4.4. Clasificaci´on de las piezas . . . . . . . . . . . . . . . . . . . . . . . . 31 4.4.1. Elecci´on del modelo . . . . . . . . . . . . . . . . . . . . . . . . 32 4.4.2. Optimizaci´on de la inferencia . . . . . . . . . . . . . . . . . . 34 i 5. Resultados 37 5.1. Detecci´on del tablero . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 5.2. Clasificaci´on de las piezas . . . . . . . . . . . . . . . . . . . . . . . . 38 5.3. Digitalizaci´on total . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 6. Conclusiones y trabajo futuro 44 7. Introduction (English) 46 7.1. Relatedwork ............................... 46 7.2. Objectives and work plan . . . . . . . . . . . . . . . . . . . . . . . . 47 8. Conclusions and future work 49 Referencias 51 ii ´ Indice de figuras Figura 1.1. Ejemplo de foto tomada por la c´amara. . . . . . . . . . . . . . 3 Figura 1.2. Esquema de la situaci´on de la c´amara y del hardware que realizar´a el c´omputo en el uso final. . . . . . . . . . . . . . . . . . . . 4 Figura 2.1. Ejemplo de las im´agenes obtenidas despu´es de cada iteraci´on. 6 Figura 2.2. Ejemplo de dos etapas en la primera fase de detecci´on de l´ıneas. 7 Figura 2.3. Ejemplo de las etapas finales de fase de detecci´on de l´ıneas. . . 8 Figura 2.4. Ejemplo de puntos que s´ı forman parte de la cuadr´ıcula. . . . 10 Figura 2.5. Ejemplo de las etapas de fase de identificaci´on del tablero. . . 12 Figura 2.6. Ejemplo del final de la primera iteraci´on. . . . . . . . . . . . . 13 Figura 2.7. Esquinas detectadas en la imagen original. . . . . . . . . . . . 14 Figura 2.8. Recorte de las casillas. . . . . . . . . . . . . . . . . . . . . . . 16 Figura3.1. Notaci´onFEN. .......................... 18 Figura 3.2. Ejemplo de vector de probabilidades para una casilla del tablero. 20 Figura 3.3. Esquema de los datos empleados en la inferencia de la configuraci´ondeltablero. ........................... 22 Figura 4.1. Ejecuci´on sobre un n´ucleo CUDA de 32 bits de dos operaciones delmismotipoenFP16.......................... 26 Figura 4.2. Flujo de trabajo para la aceleraci´on de la inferencia. . . . . . . 27 Figura 4.3. Imagen de prueba para la clasificaci´on de las piezas. . . . . . . 32 Figura 5.1. Precisi´on obtenida por cada modelo en funci´on del tiempo. . . 40 iii ´ Indice de tablas Tabla 4.1. Modelos iniciales ejecutando la inferencia mediante Keras. . . . 32 Tabla 4.2. Modelos m´as sencillos ejecutando la inferencia mediante Keras. 33 Tabla 4.3. Modelos ejecutando la inferencia mediante ONNXRuntime. . . 34 Tabla 4.4. Modelos ejecutando la inferencia mediante TensorRT. . . . . . 35 Tabla 4.5. Modelos ejecutando la inferencia mediante TensorRT en un batch de64im´agenes............................ 36 Tabla 5.1. Tiempo medio por imagen para cada una de las versiones de la detecci´ondeltablero............................ 37 Tabla 5.2. Valor Top-1 y precisi´on tras introducir conocimiento del dominio para cada uno de los modelos. . . . . . . . . . . . . . . . . . . . . 38 Tabla 5.3. Mejores tiempos por tablero y precisiones obtenidas para cada modelo sobre la Jetson Nano, junto con el optimizador utilizado. . . . 39 Tabla 5.4. Resumen de tiempos totales sobre la Jetson Nano por tablero de prueba para cada uno de los modelos que forman el frente de Pareto. 41 Tabla 5.5. Resumen de tiempos totales para cada uno de los modelos que forman el frente de Pareto sobre la Jetson Nano cuando la comprobaci´on de la posici´on del tablero devuelve cierto. . . . . . . . . . . . . 43 iv ´ Indice de algoritmos Algoritmo 2.1. Descripci´on de una iteraci´on. . . . . . . . . . . . . . . . . . 5 Algoritmo 2.2. Detecci´on de l´ıneas rectas (SLID)................ 7 Algoritmo 2.3. B´usqueda de puntos de la cuadr´ıcula (LAPS). ........ 9 Algoritmo 2.4. Identificaci´on de la posici´on del tablero (CPS)......... 11 Algoritmo 3.1. C´alculo de la configuraci´on del tablero a partir de los vectores de probabilidades de cada casilla. . . . . . . . . . . . . . . . . . . 23 Algoritmo 3.2. Inferencia del tipo de pieza a partir de su movimiento. . . . 24 Algoritmo 5.1. Comprobaci´on de la posici´on del tablero. . . . . . . . . . . . 42 v Cap´ıtulo 1 Introducci´on El reconocimiento de piezas y tableros de ajedrez es un problema de visi´on artificial que a´un no se ha resuelto de manera eficiente. Sin embargo, su soluci´on es crucial para muchos jugadores experimentados que desean competir contra motores de ajedrez y programas especializados, pero que tambi´en prefieren tomar decisiones usando un tablero de ajedrez f´ısico. Adem´as, es importante para los organizadores de torneos de ajedrez que desean digitalizar el juego para la retransmisi´on en l´ınea o para los jugadores aficionados que desean compartir sus partidas con amigos. Por lo general, estas tareas de digitalizaci´on son realizadas por humanos o con la ayuda de tableros de ajedrez y piezas especializadas. Para conseguir digitalizar una partida de forma autom´atica, es necesario ser capaz de reconocer tanto el tablero de ajedrez como posteriormente las posiciones de las piezas. En el escenario de las partidas en vivo, adem´as de la precisi´on es cr´ıtico minimizar el tiempo necesario para realizar dicho reconocimiento, ya que las jugadas pueden sucederse muy velozmente. Este es el caso de las modalidades de juego conocidas como “Blitz” y “Bullet”, en las que cada jugador tiene entre 1 y 5 minutos para jugar toda la partida. Tambi´en ocurre esto mismo en las partidas cl´asicas cuando queda poco tiempo. 1.1. Antecedentes Una soluci´on hardware para la digitalizaci´on autom´atica de las partidas son los tableros especializados que detectan las piezas f´ısicamente. Ejemplos recientes que se usan actualmente en grandes torneos los podemos encontrar en [Squ]o[DGTa]. Sin embargo, estos tableros son costosos y dif´ıcilmente desplegables en muchos ´ambitos. A modo de ejemplo, un set de tablero y piezas de DGT (marca usada en torneos oficiales) cuesta desde unos 500ehasta m´as de 1000e[DGTb]. Otras alternativas son las proporcionadas por robots que mueven las piezas de un tablero, como pueden ser [Mat+11] o m´as recientemente [CW19]. Estos robots se basan en posicionar una c´amara cenital sobre el tablero y detectar los diferenciales entre un movimiento y el siguiente. Un inconveniente de esto es que se necesita partir de un estado inicial conocido, no se podr´ıa digitalizar de esta forma un tablero con una configuraci´on de piezas gen´erica. Adem´as, habr´ıa que tener en cuenta los fallos, porque se podr´ıan encadenar en cada nueva jugada. Las soluciones que ofrece la visi´on artificial son una alternativa a tener en cuenta, ya que proporcionan sistemas m´as baratos y cada vez m´as precisos, adem´as de ser un reto tecnol´ogico importante. Como comparaci´on, la plataforma que utilizaremos 1 2.2b como varias de las l´ıneas de la cuadr´ıcula del tablero se detectan de forma discontinua como segmentos diferentes. La funci´on que decide si dos segmentos se deben unir o no est´a descrita en [CLW17]. A la hora de estudiar la colinealidad, tiene en cuenta tambi´en la longitud de los segmentos en comparaci´on con el tama˜no de la imagen. Esto se debe a que segmentos muy cortos cerca de un segmento muy largo en realidad pueden formar parte de la misma recta, aunque el ´angulo que formen entre ellos sea relativamente grande. Conforme crece la longitud, esta restricci´on sobre el ´angulo se vuelve m´as estricta. Finalmente, los conjuntos de segmentos colineales obtenidos se fusionan en una ´unica recta. Para ello, primero se convierten los segmentos en puntos, teniendo en cuenta que a mayor longitud m´as n´umero de puntos, y posteriormente se busca la recta que mejor se ajuste a ellos (Figura 2.3a). Esto ´ultimo se consigue a partir de un M-estimador para modelos aproximadamente lineales [Wie96] que encuentra dicha recta iterativamente mediante el algoritmo de m´ınimos cuadrados. Esta aproximaci´on busca solventar algunos de los problemas que presentan los algoritmos que se basan en el estudio de los centroides definidos por los segmentos. De esta forma, el m´etodo se ajusta a la intuici´on de que la recta de mejor ajuste se debe aproximar lo m´aximo posible a los segmentos m´as largos del conjunto. (a) L´ıneas obtenidas a partir de los puntos formados por los segmentos. (b) Resultado final de la fase de detecci´on de l´ıneas. Figura 2.3: Ejemplo de las etapas finales de fase de detecci´on de l´ıneas. 2.1.2. B´usqueda de puntos de la cuadr´ıcula A partir de las l´ıneas detectadas en el paso anterior, se obtienen todos los puntos de intersecci´on de las mismas. De estos, se selecciona el subconjunto de puntos que tenga una alta probabilidad de formar parte de la cuadr´ıcula formada por las casillas del tablero de ajedrez. Para conseguirlo hay dos v´ıas que se complementan: un primer detector geom´etrico que se encarga de filtrar positivamente los casos m´as sencillos y una red neuronal que termina de discriminar los puntos m´as complicados (Algoritmo 2.3). 8 Algoritmo 2.3: B´usqueda de puntos de la cuadr´ıcula (LAPS). Entrada: Imagen que contiene un tablero. L´ıneas detectadas por SLID. Salida: Conjunto de puntos que forman parte de la cuadr´ıcula del tablero. 1puntos cuadricula ←[ ]; 2para cada punto ∈intersecciones(lineas)hacer 3matriz ←preprocesar(vecindad(imagen,punto)); 4es punto cuadricula ←detector geometrico(matriz); 5si es punto cuadricula entonces 6puntos cuadricula.insertar(punto) 7en otro caso 8es punto cuadricula ←red neuronal(matriz); 9si es punto cuadricula entonces 10 puntos cuadricula.insertar(punto) 11 fin 12 // Si no pertenece a la cuadr´ıcula, pasamos al siguiente 13 fin 14 fin 15 devolver puntos cuadricula Para identificar todas las intersecciones de las l´ıneas obtenidas en el m´odulo anterior, se utiliza el algoritmo de barrido de Bentley-Ottmann [BO79]. Las vecindades de estos puntos en la imagen ser´an lo que se estudie para comprobar si efectivamente se tratan de puntos con una alta probabilidad de formar parte de las intersecciones del tablero. Partiendo de una peque˜na matriz de p´ıxeles centrada en cada uno de los puntos, se preprocesa para mantener solo la informaci´on relevante y, como hemos comentado anteriormente, primero se aplica un detector geom´etrico para marcar r´apidamente como positivos las situaciones m´as comunes. Este detector geom´etrico busca contornos y comprueba si el entorno del punto est´a formado por cuatro romboides. En caso afirmativo, estamos ante un punto que muy posiblemente forme parte de la cuadr´ıcula del tablero que buscamos. Esto se debe a que los cuatro romboides se corresponder´an con las cuatro casillas que forman parte de cada intersecci´on (Figura 2.4a). En caso de que no se detecte este patr´on en los alrededores del punto, el siguiente paso es intentar distinguir si esto se debe, por ejemplo, a que una de las piezas est´a ocultando parcialmente la intersecci´on (Figura 2.4b). Para ello se utiliza una red neuronal convolucional entrenada sobre un conjunto de casos muy diversos. As´ı se obtienen las probabilidades de que el punto pertenezca al conjunto con el que seguiremos trabajando en el siguiente m´odulo. Solo en caso de que el resultado sea positivo con una probabilidad muy alta, se da el punto como v´alido y se utilizar´a para identificar el tablero. 9 (a) Basta el detector geom´etrico. (b) Es necesaria la red neuronal. Figura 2.4: Ejemplo de puntos que s´ı forman parte de la cuadr´ıcula. 2.1.3. Identificaci´on de la posici´on del tablero El paso final de cada iteraci´on es identificar el tablero a partir de los puntos y las l´ıneas encontradas anteriormente. Para ello, el algoritmo analiza los conjuntos de cuatro rectas que formen un cuadril´atero para decidir cu´al de ellos es el que se corresponde con el tablero que estamos buscando (Algoritmo 2.4). N´otese que, como los puntos que hemos encontrado son los que forman las intersecciones de la cuadr´ıcula, en realidad no estamos encuadrando el tablero completo, sino el espacio 6×6 formado por las casillas centrales. Esto no ser´a un problema porque al final de la iteraci´on se toma un margen del ancho de una casilla, teniendo en cuenta la perspectiva, alrededor de este marco. De esta forma, en ´ultima instancia, ser´a este margen el que se corresponda con los bordes reales del tablero (ver Figura 2.6a). El algoritmo toma la decisi´on de qu´e cuadril´atero es mejor en base a una funci´on de coste que tiene su m´aximo cuando las cuatro l´ıneas forman perfectamente el marco de un tablero de ajedrez, con la limitaci´on al espacio 6 ×6 que hemos comentado anteriormente. Esta funci´on polyscore [CLW17] est´a definida como, dado un marco F: P(F) = L4 A2 F W3(k)W5(l). Donde Les el n´umero de puntos dentro del marco, AFes el ´area del marco F,kes la distancia media de los puntos dentro del marco a su borde m´as cercano, les la distancia del centroide del grupo de puntos dentro del marco al centroide del marco yWes la funci´on de peso siguiente 1: Wj(x) = 1 1 + j px L . Intuitivamente, para maximizar P(F) hay que maximizar Ly minimizar AF,kyl. Para evitar la comprobaci´on de las n 4posibles formas de elegir cuatro rectas, se optimiza el algoritmo para solo revisar algunas de las combinaciones. Esta optimizaci´on empieza encontrando el mayor cl´uster de puntos de la cuadr´ıcula mediante el algoritmo DBSCAN [Est+96] y descarta el resto, ya que este deber´ıa representar 1Existe una errata en [CLW17] confirmada por los autores. La f´ormula est´a corregida en la implementaci´on y el denominador es efectivamente Len lugar de AF. 10 Algoritmo 2.4: Identificaci´on de la posici´on del tablero (CPS). Entrada: L´ıneas detectadas por SLID. Puntos de la cuadr´ıcula devueltos por LAPS. Salida: Coordenadas en la imagen de las cuatro esquinas de la cuadr´ıcula. 1// Obtener las l´ıneas que bordean al mayor cl´uster de puntos de la cuadr´ıcula. 2clusters ←DBSCAN(puntos cuadricula); 3cluster tablero ←max(clusters); 4lineas candidatas ←esta cerca borde(lineas,cluster tablero); 5// Escoger el par de l´ıneas verticales y horizontales que se ajuste m´as al borde del tablero 6lineas verticales ←es vertical(lineas candidatas); 7lineas horizontales ←es horizontal(lineas candidatas); 8valor max ← −∞; 9para cada v1, v2∈lineas verticales,h1, h2∈lineas horizontales hacer 10 valor ←polyscore(v1, v2, h1, h2); 11 si valor >max valor entonces 12 max valor ←valor; 13 mejor marco ←[v1, v2, h1, h2]; 14 fin 15 fin 16 devolver intersecciones(mejor marco) 11 al tablero que buscamos. A continuaci´on, de todas las l´ıneas que se han obtenido en el primer paso, solo se tienen en cuenta las que est´en cerca de alguno de los puntos anteriores, que adem´as no pasen cerca del centroide del cl´uster y, ayud´andose de la funci´on de polyscore, comprueba que tambi´en est´en en las vecindades del borde del tablero. Finalmente, se dividen las rectas anteriores en horizontales y verticales, teniendo en cuenta la perspectiva. De esta manera, basta con tomar pares de estas rectas verticales y horizontales para elegir el marco que maximiza la funci´on de polyscore (Figura 2.5a). Las cuatro rectas obtenidas determinar´an el espacio central del tablero y, a partir de esto, se podr´a deducir su posici´on exacta (Figura 2.5b). (a) Pares de l´ıneas horizontales y verticales que se consideran. (b) Espacio central del tablero identificado junto con los puntos de la cuadr´ıcula detectados. Figura 2.5: Ejemplo de las etapas de fase de identificaci´on del tablero. 2.1.4. Fin de la iteraci´on Para pasar del cuadrado 6 ×6 al tablero completo, se forma un borde que, en ´ultima instancia, converger´a a sus l´ımites reales. Esto se consigue a˜nadiendo un margen a una distancia fija. Esta distancia ser´a la correspondiente a una casilla cuando el tablero ocupe la totalidad de la imagen en la ´ultima iteraci´on. Como en iteraciones intermedias el tablero ocupa solo un subconjunto del total, este borde siempre ser´a mayor o igual que el necesario, conteniendo al tablero real (Figura 2.6a). Veamos c´omo obtener esta imagen final de la iteraci´on. Esto servir´a tanto como inicio de la siguiente iteraci´on, si la hubiera, como imagen recortada del tablero despu´es de transformarlo teniendo en cuenta la perspectiva. La imagen final de cada iteraci´on ser´a un cuadrado de 1200 p´ıxeles de lado. As´ı, el objetivo es que los puntos detectados que contienen al tablero (los puntos verdes en la Figura 2.6a) sean los nuevos extremos de la imagen para la siguiente 12 iteraci´on. Para conseguir esto, se calcula la matriz de la proyecci´on perspectiva que lleva los cuatro puntos que hemos obtenido a los puntos (0,0), (1200,0), (0,1200) y (1200,1200). A partir de esta matriz, se transformar´a la imagen inicial, recortada por los cuatro puntos, en el cuadrado que buscamos (Figura 2.6b). (a) Cuadrado 6 ×6 central del tablero (rojo) y margen que tomamos (verde). (b) Imagen despu´es de aplicar la transformaci´on en perspectiva. Figura 2.6: Ejemplo del final de la primera iteraci´on. 2.2. Obtenci´on de las casillas individuales Una vez conocida la posici´on del tablero en la imagen original, tenemos que separarla en las casillas individuales de cara a clasificarlas para obtener el resultado final. La primera aproximaci´on consiste simplemente en dividir la imagen de la ´ultima iteraci´on de la detecci´on del tablero en un 8 ×8. Sin embargo, esto presenta un problema importante que trataremos de resolver mediante un nuevo m´etodo. Como se puede observar en la Figura 2.1, conforme las iteraciones se ajustan al tablero, las piezas que est´an en los bordes se ven recortadas parcialmente. Este problema es a´un m´as grave en el caso de la fila superior de la imagen, en la que solo se puede ver la base de las piezas seg´un el ´angulo con el que se haga la foto. Salvo que la imagen se tome desde un plano cenital lo suficientemente alejado del tablero, lo normal es que cada pieza invada el espacio ocupado por sus casillas vecinas. Adem´as, por esto ´ultimo, la parte inferior de cada casilla es la m´as propensa a contener informaci´on de casillas vecinas. Por este motivo, deber´ıamos fijarnos en m´as partes de la imagen adem´as de en los l´ımites formados por la propia casilla exclusivamente. 13 Figura 2.7: Esquinas detectadas en la imagen original. 2.2.1. Nuevo m´etodo Como nuestro objetivo es tomar una foto desde un lateral del tablero, ya que es mucho m´as sencillo que tener que posicionar una c´amara a cierta altura por encima, buscamos dise˜nar otro m´etodo que se adapte mejor a estas circunstancias. Para ello, nos basamos en la idea utilizada en [Din16] para tener en cuenta que las piezas vistas en perspectiva son m´as altas que el lateral de una casilla. El problema de este m´etodo es que para poder tener en cuenta la totalidad de las piezas, no nos basta con la imagen final del tablero recortado. Es decir, las casillas individuales hay que pasar a obtenerlas de la imagen original. El resultado de las iteraciones al detectar el tablero no nos proporciona las coordenadas de este en la foto inicial, as´ı que tenemos que invertir las transformaciones perspectivas que se realizan al pasar de una iteraci´on a la siguiente. Como ejemplo, en la Figura 2.1 tendr´ıamos que hacer la transformaci´on (d) →(c) →(b) →(a). Para conseguir esto, nos vamos guardando los cuatro puntos de las esquinas obtenidos al finalizar cada iteraci´on. De esta forma, podremos calcular las matrices de las transformaciones en el orden contrario y bastar´a con invertir cada una de las matrices obtenidas y multiplicarlas para obtener la funci´on que buscamos. A partir de esto ya tendremos la transformaci´on que nos permitir´a calcular las coordenadas en la foto inicial de un punto en la imagen final recortada. Dividiendo el resultado de la ´ultima iteraci´on en la cuadr´ıcula 8 ×8 del tablero, obtendremos las esquinas de cada una de las casillas (Figura 2.7). Una vez conocidas las coordenadas de las cuatro esquinas de una casilla, tenemos que calcular el rect´angulo por el que recortaremos. Primero calculamos la altura de la imagen como la diferencia entre una esquina superior y una inferior multiplicado por un factor de 1,75. El hecho de tomar una mayor altura m´as hace que podamos ver mejor la parte de arriba de las piezas, que al fin y al cabo es la que mejor las diferencia, sin llegar a introducir en el rect´angulo m´as que la base de la posible pieza de la casilla superior (Figuras 2.8b y2.8a). As´ı, ampliamos el conocimiento de la 14 zona de la pieza que mejor las diferencia e introducimos el menor ruido posible. En caso de salirnos de la imagen por arriba, ajustamos la altura al m´aximo. Como estamos asumiendo que las fotos se toman desde un lateral del tablero y no desde una esquina, podemos tomar la base del rect´angulo como el ancho de las dos esquinas inferiores (Figura 2.8). Como se puede observar en la Figura 2.8c, hay que ajustar el factor por el que multiplicamos la altura teniendo en cuenta tambi´en que los peones son m´as bajos y se podr´ıan solapar los unos con los otros. Otra opci´on ser´ıa ajustar la altura seg´un estemos en la parte inferior o superior de la imagen (Figuras 2.8d y2.8c). A´un as´ı, con la suficiente variedad de casos en el dataset, nuestra red neuronal convolucional que veremos en la secci´on 3.3 deber´ıa ser capaz de aprender en qu´e zona de la imagen fijarse para diferenciar las piezas m´as altas de las m´as bajas. Veamos una posible generalizaci´on de este m´etodo en caso de querer tambi´en admitir fotos hechas desde las esquinas (en las que el tablero se ver´ıa como un rombo). Podr´ıamos tomar una combinaci´on lineal de las alturas de las esquinas de cada casilla de forma que se mantuviese lo comentado en el p´arrafo anterior cuando el borde inferior de la imagen fuese paralelo al borde inferior del tablero. Una opci´on sencilla que cumplir´ıa esto es tomar la media de las alturas de las esquinas inferiores para situar la base del rect´angulo y ajustar el factor por el que multiplicamos la altura en funci´on de la diferencia entre el ancho y el alto de la casilla. Nuestra idea inicial era obtener una gran cantidad de fotos tomadas a partidas reales en un club de ajedrez, pero desgraciadamente por las circunstancias actuales no hemos podido construir un dataset de piezas obtenidas de esta forma. Por lo tanto, como veremos en la secci´on 3.2, nos quedaremos con la primera aproximaci´on que hemos visto al inicio de esta secci´on para recortar las casillas, ya que es la forma con la que se han obtenido los dataset que hemos podido utilizar. Planteamos en el cap´ıtulo 6, como trabajo futuro, seguir este estudio para incorporar el m´etodo que hemos propuesto. 15 (a) Dama negra. (b) Rey blanco. (c) Pe´on negro. (d) Torre blanca. Figura 2.8: Recorte de las casillas mediante la primera aproximaci´on (verde) y con el nuevo m´etodo (amarillo). En las dos primeras figuras, las m´as altas, vemos como con el rect´angulo amarillo se llega a poder diferenciar la parte superior de las piezas. En las dos figuras inferiores, las piezas m´as bajas, vemos la diferencia que puede haber entre que est´en situadas en la parte inferior o superior del tablero. 16 Cap´ıtulo 3 Clasificaci´on de las piezas Una vez detectada la posici´on del tablero en la imagen original, el siguiente paso es clasificar cada una de sus casillas. Cada casilla puede estar vac´ıa o puede estar ocupada por una pieza de uno de los jugadores, por lo que tendremos que decidir a cu´al de las 13 clases anteriores corresponde cada una de las 64 casillas del tablero. Actualmente, la manera m´as utilizada y los mejores algoritmos para realizar la clasificaci´on de una imagen en una serie de categor´ıas son mediante el uso de redes neuronales convolucionales [RW17]. Adem´as, estas redes se pueden acelerar enormemente como veremos en el cap´ıtulo 4. 3.1. Notaci´on FEN El resultado final de la clasificaci´on ser´a una cadena de caracteres que codificar´a las posiciones de las piezas en el tablero mediante la notaci´on de Forsyth-Edwards (FEN) [Edw94]. Como solo tendremos una instant´anea de la partida, ´unicamente podremos saber la posici´on de las piezas, no el jugador al que le toca mover o si hay posibilidad de enroque por ejemplo (factores que s´ı que se tienen en cuenta en la notaci´on FEN completa). As´ı, la cadena ser´a una serie de ocho bloques de caracteres alfanum´ericos representando cada fila del tablero separadas por el car´acter /. Las filas se escriben de izquierda a derecha y de arriba a abajo desde la perspectiva de las blancas. Los caracteres se corresponden con las iniciales de los nombres de las piezas en ingl´es (a excepci´on del caballo, que se representa con una n), en may´usculas si la pieza es blanca y en min´usculas si es negra. Las casillas en blanco se abrevian con un n´umero del 1 al 8 indicando el n´umero de casillas vac´ıas contiguas. La posici´on inicial de una partida se corresponde por tanto con la siguiente cadena: rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR. En la Figura 3.1 podemos ver un ejemplo de una posici´on m´as avanzada de la partida. 3.2. Dataset etiquetado de piezas Obtener un dataset etiquetado de im´agenes de tableros o de piezas de ajedrez no es tarea sencilla, ya que no existe ninguno disponible de forma p´ublica que sea completo o variado [Din16] [CLW17]. Usualmente, en estos casos, cada autor se crea su peque˜na muestra de piezas con las que poder poner a prueba su idea. Sin embargo, para entrenar un modelo de deep learning son necesarias una gran cantidad 17 Sabiendo esto, podemos deducir en funci´on de la casilla inicial y la final qu´e piezas son compatibles con el movimiento realizado. De esta manera podremos afinar m´as la pieza que se encuentre en la casilla final del movimiento (Algoritmo 3.2). En las pruebas y resultados que mostramos en los cap´ıtulos 4y5deshabilitamos este algoritmo, ya que requiere informaci´on que no tendremos al tomar una ´unica instant´anea de un tablero. Esto ser´a ´util y se podr´a ampliar como comentaremos en el cap´ıtulo 6de cara a digitalizar partidas completas. Algoritmo 3.2: Inferencia del tipo de pieza a partir de su movimiento. Entrada: Cadena FEN de la imagen anterior. Vectores de probabilidades de la imagen actual. Salida: Conjunto de piezas compatibles con el movimiento realizado. 1casillas ←casillas cambiadas(FEN anterior,vectores probs); 2(casilla ini,casilla fin,accion)←mov inferido(FEN anterior,vectores probs, 3casillas); 4piezas posibles ←piezas compatibles(casilla ini,casilla fin,accion); 5devolver piezas posibles 24 Cap´ıtulo 4 Aceleraci´on El paso final y la parte m´as importante de nuestro trabajo es la aceleraci´on de todo el framework que hemos construido. Desde la detecci´on inicial del tablero hasta la clasificaci´on de las piezas para obtener la digitalizaci´on completa. Existen multitud de t´ecnicas para hacer m´as eficiente la ejecuci´on de un programa, espec´ıficamente para la ejecuci´on eficiente de redes neuronales profundas [Sze+17] [Kim+19] [MDB20]. En este cap´ıtulo veremos las que hemos utilizado nosotros y c´omo las hemos adaptado a este caso concreto. 4.1. Plataformas de inferencia En base al uso final de nuestro programa, decidimos que lo m´as apropiado ser´ıa su ejecuci´on en local en un sistema empotrado con hardware espec´ıfico para la aceleraci´on. Existen diversos sistemas que cumplen estas caracter´ısticas y se adaptan al c´alculo de la inferencia de modelos de deep learning. Tres de ellos ser´ıan el Intel Neural Compute Stick 2 [Int], los sistemas Coral de Google [Goo] o la familia Jetson de Nvidia [Nvia]. Los Neural Compute Stick 2 de Intel permiten a˜nadir mediante una conexi´on USB una unidad de procesamiento de visi´on (Vision Processing Unit o VPU), esto es, un acelerador hardware de bajo consumo dedicado al c´alculo de algoritmos de visi´on artificial, como pueden ser las redes neuronales convolucionales. Los sistemas Coral de Google est´an compuestos o bien por una unidad USB o bien por una placa dedicada, permitiendo disponer en ambos casos de una unidad de procesamiento tensorial (Tensor Processing Unit o TPU) para la aceleraci´on de redes neuronales. La diferencia fundamental de una TPU con respecto a un GPU es el volumen de c´alculo que pueden alcanzar, estando las TPU optimizadas para tama˜nos de batch m´as grandes. Adem´as, est´an pensadas ´ıntegramente para el c´omputo utilizando precisi´on reducida, de forma similar a los n´ucleos tensoriales que proporcionan las GPU de Nvidia m´as recientes. En nuestro caso vamos a utilizar la Nvidia Jetson Nano [Nvib], el dispositivo m´as peque˜no de la familia Jetson. Est´a compuesto por una placa dedicada con dos modos de consumo, 5 o 10 W. Unos valores muy reducidos en comparaci´on con su potencia de c´omputo, ya que puede llegar a los 472 GFLOPs en FP16. Sus especificaciones t´ecnicas principales son las siguientes: Una GPU con arquitectura NVIDIA Maxwell de 128 n´ucleos CUDA. Una CPU ARM de cuatro n´ucleos Cortex-A57 a 1,43 GHz. 25 4 GB de memoria RAM LPDDR4 a 25,6 GB/s. Conectividad Gigabit Ethernet y conexi´on HDMI y DisplayPort. Estas caracter´ısticas nos ofrecen, adem´as de una GPU dedicada de Nvidia con el potencial de TensorRT para la inferencia (como veremos en la secci´on 4.2), una CPU capaz de realizar el c´omputo secuencial necesario para detectar los tableros. Del mismo modo, hemos optado por usar esta plataforma ya que, al incluir una GPU, permite acelerar tambi´en las fases de detecci´on del tablero. Este tipo de arquitectura se viene usando con ´exito desde hace m´as de una d´ecada en las tareas relacionadas con el procesamiento de im´agenes [Set+07] [Ten+08]. Este sistema forma parte de la familia Tegra X1 “Erista”, con una disminuci´on de la frecuencia de la CPU y disponiendo solamente de la mitad de n´ucleos CUDA que los modelos utilizados en la Nvidia Shield TV [Nvid] o la Nintendo Switch [Nin]. Esta familia fue la primera de Nvidia que se dise˜n´o pensando en dispositivos port´atiles, adem´as de ser la primera arquitectura que incluy´o cierto soporte para operaciones en punto flotante de 16 bits. En algunas situaciones, como en el caso de que se trate de la misma operaci´on, dos operaciones en FP16 se pueden empaquetar juntas a ejecuci´on sobre un ´unico n´ucleo CUDA de 32 bits (Figura 4.1) [HS]. Esto ´ultimo lo utilizaremos de cara a la aceleraci´on de la inferencia de nuestras redes neuronales. Figura 4.1: Ejecuci´on sobre un n´ucleo CUDA de 32 bits de dos operaciones del mismo tipo en FP16. 4.2. Optimizadores: ONNXRuntime y TensorRT Como hemos comentado en la secci´on 3.3, tanto la definici´on de nuestra red neuronal como su entrenamiento los hemos realizado utilizando la librer´ıa Keras sobre TensorFlow. Veremos ahora que la inferencia empleando estas librer´ıas se puede acelerar enormemente sobre otras plataformas. En esta secci´on estudiaremos las dos que hemos utilizado: el formato de representaci´on de modelos ONNX (Open Neural Network Exchange) [ONN] y su optimizador ONNXRuntime [Mic] y TensorRT [Nvie], la librer´ıa de Nvidia para la optimizaci´on de la inferencia sobre sus tarjetas gr´aficas (Figura 4.2). 26 Figura 4.2: Flujo de trabajo para la aceleraci´on de la inferencia. ONNX es un formato libre de representaci´on de modelos de aprendizaje autom´atico que define un conjunto de operadores y un formato de archivo normalizado. De esta forma se obtiene una representaci´on est´andar que permite la interconexi´on entre una gran variedad de librer´ıas de IA, herramientas, motores de ejecuci´on y compiladores. Posibilita el desarrollo de los modelos mediante librer´ıas como Keras, Caffe, MATLAB, PyTorch o TensorFlow y su posterior despliegue en entornos de ejecuci´on dise˜nados para acelerar la inferencia sobre un hardware espec´ıfico. ONNXRuntime es un motor de inferencia de alto rendimiento que permite optimizar la ejecuci´on de modelos de machine learning aprovechando de forma m´as eficiente las capacidades de cada hardware. El modelo ONNX lo convierte a una representaci´on interna en memoria principal y le aplica una serie transformaciones, como por ejemplo la divisi´on del modelo en una serie de partes para que cada una se ejecute sobre un entorno de ejecuci´on o acelerador diferente (CPU, nGraph, CUDA, TensorRT...). ONNX tambi´en nos sirve como representaci´on intermedia a partir de Keras para utilizar optimizadores sobre hardware m´as espec´ıficos, como puede ser TensorRT para las tarjetas gr´aficas de Nvidia. Utilizar TensorRT de forma directa en vez de indirectamente a partir de ONNXRuntime nos permite aplicar m´as y mejores optimizaciones adaptadas espec´ıficamente al hardware final. Esto se debe a que el paso del modelo en formato ONNX a TensorRT se realiza sobre este hardware, disponiendo de todos los par´ametros del sistema definitivo. Sin embargo, estas transformaciones ser´an a costa de una disminuci´on muy leve en la precisi´on obtenida. Las optimizaciones que realiza TensorRT de cara a reducir el tiempo necesario para la inferencia son las siguientes: Disminuir el tama˜no en memoria de los pesos para maximizar el ancho de banda, a expensas de reducir m´ınimamente la precisi´on del modelo. De esta 27 forma, se puede pasar de n´umeros en coma flotante de 32 bits a 16 bits o incluso a enteros de 8 bits mediante transformaciones y ajustes adicionales. Fusionar capas del modelo para optimizar el uso de la memoria de la GPU y el ancho de banda. Donde sea posible, transforma en un ´unico nodo una porci´on m´as compleja del modelo inicial. Adaptar los algoritmos y datos usados en la ejecuci´on de las capas del modelo a la GPU objetivo. Redistribuir los datos para minimizar la cantidad de huecos en memoria. Paralelizar la ejecuci´on de forma que se utilice de forma eficiente toda la GPU. 4.3. Detecci´on del tablero Como ya hemos visto en el cap´ıtulo 2, la fase de detecci´on del tablero se compone de distintos m´odulos que se ejecutan de forma iterativa hasta obtener la posici´on final. Para entender mejor el coste computacional de todo ese proceso, analizamos varias ejecuciones del c´odigo con la herramienta de an´alisis de rendimiento (profiler) que proporciona Python por defecto. Los primeros pasos tras decidirnos por basar la detecci´on del tablero en este m´etodo han sido: Adaptar el c´odigo a las versiones actuales del lenguaje y de las librer´ıas utilizadas, sobretodo el paso de Python 2 a Python 3, OpenCV 2 a 4 y TensorFlow 1 a 2. Refactorizar el proyecto para que tenga mayor claridad y poder incluirlo m´as facilmente en nuestro framework. Adecuar todo el c´odigo a la gu´ıa de estilo de Python PEP8 [RWC01]. Una vez obtenido un marco funcional, pasamos a hacer un primer an´alisis del rendimiento del c´odigo utilizando el profiler de Python. Esta herramienta nos proporciona una serie de estad´ısticas y nos describe cu´antas veces y durante cu´anto tiempo se ha ejecutado cada funci´on del c´odigo. En particular, por cada funci´on nos indica el n´umero veces que se ha llamado y el tiempo total y por llamada que ha tardado, distinguiendo entre incluir o no el tiempo que hayan empleado sus subfunciones en ejecutarse. Esto nos permitir´a dedicar esfuerzo a optimizar las zonas del c´odigo que nos vayan a proporcionar una mayor disminuci´on del tiempo. Las ejecuciones para analizar el rendimiento de la detecci´on de tablero las realizamos sobre nuestra plataforma final, la Nvidia Jetson Nano. Las im´agenes de prueba son el conjunto de 10 fotos que utilizan los autores de [CLW17] para obtener sus 28 resultados. Estas son im´agenes de situaciones muy variadas, que contienen otros objetos que forman l´ıneas rectas adicionales adem´as del tablero y que tienen sombras, distorsiones y ruido. Los tiempos mostrados aqu´ı son desde antes de leer las im´agenes de entrada hasta despu´es de escribir la imagen detectada de cada tablero (ver Figura 2.1). En particular, este no incluye la obtenci´on de las casillas individuales. Para un an´alisis completo de los tiempos finales ver el cap´ıtulo 5. 4.3.1. Primer an´alisis: Optimizaci´on mediante ONNX En la ejecuci´on del c´odigo en esta fase obtenemos que se tarda una media de 16,01 segundos en procesar cada uno de los 10 tableros de prueba. Este tiempo lo obtenemos utilizando la librer´ıa timeit y ejecutando 5 veces el conjunto completo de tableros. Los siguientes datos desgranados vienen dados por el profiler, que conlleva un ligero sobrecoste, por lo que los expresamos como porcentajes del tiempo total para abstraernos de esta diferencia. Inicialmente, el 38,1 % del tiempo se emplea en la fase de identificaci´on de la posici´on del tablero (CPS) 2.1.3, el 37,4 % en la fase de b´usqueda de puntos de la cuadr´ıcula (LAPS) 2.1.2 y el 18 % en la fase de detecci´on de l´ıneas rectas (SLID) 2.1.1. De aqu´ı, observamos que m´as de tres cuartas partes del tiempo de b´usqueda de puntos de la cuadr´ıcula se emplea en la inferencia de la red neuronal, desarrollada por [CLW17], utilizada para terminar de decidir los puntos que no filtra el detector geom´etrico (v´ease el Algoritmo 2.3). Por lo tanto, un buen punto de partida para optimizar el c´odigo ser´ıa acelerar esta red neuronal. Para ello, primero recuperamos del proyecto original la estructura del modelo y los pesos entrenados para detectar los puntos que forman parte de la cuadr´ıcula del tablero. Posteriormente, transformamos el modelo a formato ONNX para poder reducir el tiempo necesario para su ejecuci´on mediante ONNXRuntime, como hemos visto en la secci´on 4.2. De esta manera, haciendo unos cambios m´ınimos en el c´odigo, podremos aprovechar un modelo previamente entrenado optimiz´andolo de forma casi transparente. Tras optimizar esta parte del programa, hacemos una nueva prueba de rendimiento y comprobamos que ahora se tarda una media de 10,33 segundos en procesar cada uno de los 10 tableros de prueba. As´ı, centr´andonos en mejorar las funciones en las que se invierte una mayor cantidad de tiempo, conseguimos un speedup de 1,55. 4.3.2. Segundo an´alisis: Reducci´on del sobrecoste de NumPy Una vez optimizada la ejecuci´on de la red neuronal en la fase LAPS tras el primer an´alisis, volvemos a evaluar el rendimiento del c´odigo para ver por d´onde podemos seguir mejorando. En este segundo an´alisis, aproximadamente el 41,4 % del tiempo 29 se emplea en la identificaci´on de la posici´on del tablero, el 28,6 % en la detecci´on de l´ıneas rectas y el 21,8 % en la b´usqueda de puntos de la cuadr´ıcula (recordemos que esto antes ocupaba el 37,4 % del tiempo). Llegado a este punto, nos sorprende que casi la tercera parte del tiempo total se emplea en el c´alculo de un producto vectorial utilizando la librer´ıa NumPy [Oli06]. Esta operaci´on forma parte de una peque˜na funci´on utilizada tanto por la identificaci´on de la posici´on del tablero como por la detecci´on de l´ıneas rectas. El c´alculo es simplemente k(y−x)×(x−z)k, donde observamos que x, y yzson vectores de dos componentes. Sabiendo esto, podemos transformar el mismo c´alculo a otra forma equivalente y mucho m´as sencilla sin necesidad de hacer llamadas a la librer´ıa NumPy. Las llamadas a librer´ıas, al introducir peque˜nos sobrecostes por su amplio espectro de posibles usos, acaban siendo menos eficientes. El c´alculo anterior puede simplificarse como |(y1−x1)(x2−z2)−(y2−x2)(x1−z1)|, donde hemos denotado x= (x1, x2), y = (y1, y2) y z= (z1, z2). Esta operaci´on puede hacerse directamente sin necesidad de utilizar librer´ıas externas. Tambi´en hemos evitado el c´alculo de la norma del vector resultante del producto vectorial introduciendo simplemente un valor absoluto. Hay que notar que esta operaci´on acaba realiz´andose m´as de 25000 veces por tablero detectado. Por lo tanto, intentamos ver si se puede reducir su uso de alguna manera. Reordenando la forma de calcular si una l´ınea est´a cerca del borde de la cuadr´ıcula (v´ease el Algoritmo 2.4), evitamos llamadas a esta operaci´on cuyos resultados a veces no eran necesarios. As´ı, conseguimos reducir casi un 20 % el n´umero de invocaciones a esta funci´on. Tras estos cambios hacemos una nueva prueba de rendimiento y comprobamos que ahora se tarda una media de 5,55 segundos en procesar cada uno de los 10 tableros de prueba, consiguiendo un speedup de 1,86 sobre la optimizaci´on anterior. 4.3.3. Tercer an´alisis: Reducci´on del sobrecoste de BentleyOttmann Despu´es de observar c´omo las llamadas a librer´ıas pueden suponer un coste computacional mayor de lo necesario si no est´an justificadas, volvemos a analizar el c´odigo por si hubiese alguna otra situaci´on similar. En el tercer an´alisis, aproximadamente el 40,2 % del tiempo se emplea en la b´usqueda de puntos de la cuadr´ıcula, el 32,3 % en la identificaci´on de la posici´on del tablero y el 20,6 % en la detecci´on de l´ıneas rectas. Aqu´ı, destaca el hecho de que una funci´on dedicada al c´alculo de las intersecciones de un conjunto de l´ıneas mediante el algoritmo de Bentley-Ottmann ocupa 30 casi el 39 % del tiempo total. Vimos al principio del Algoritmo 2.3 que este m´etodo de barrido se emplea para obtener todos los puntos candidatos a formar parte de la cuadr´ıcula del tablero. Sin embargo, aqu´ı vemos que adem´as de para ese caso, tambi´en se est´a utilizando para calcular la intersecci´on de cada par de l´ıneas verticales y horizontales candidatas a ser el marco de la cuadr´ıcula 6 ×6 del tablero (funci´on polyscore del Algoritmo 2.4). Este segundo uso supone el 56,5 % del tiempo empleado en este c´alculo. El algoritmo de Bentley-Ottmann permite calcular las intersecciones de un conjunto de l´ıneas de forma m´as eficiente, O((n+k) log n), que la trivial, O(n2), donde nes el n´umero de l´ıneas y kel n´umero de intersecciones. Para conseguir esto se a˜nade un sobrecoste que no compensa para conjuntos peque˜nos de l´ıneas, en nuestro segundo caso son solo 4 l´ıneas. Solventamos esta situaci´on calculando directamente las 6 posibles intersecciones de 2 l´ıneas de entre el conjunto de 4. Esto consiste b´asicamente en el c´alculo de determinantes de orden 2 y operaciones elementales, que en nuestro caso, al ser un conjunto peque˜no, no supone ninguna ineficiencia pr´actica. De esta forma reducimos el tiempo en procesar cada uno de los 10 tableros de prueba a una media de 4,22 segundos por tablero, consiguiendo un speedup de 1,32 sobre la optimizaci´on anterior. 4.4. Clasificaci´on de las piezas En las secciones 3.3 y3.4 hemos detallado el proceso de clasificaci´on de las piezas del tablero utilizando una red neuronal profunda construida mediante Keras. Una vez establecido el proceso a trav´es del cual podemos completar la digitalizaci´on del tablero, estamos en situaci´on de escoger qu´e modelo utilizaremos para la inferencia y c´omo aceleraremos su ejecuci´on. Efectuaremos las pruebas sobre 5 im´agenes con tableros de ajedrez que contienen piezas de distinto tipo al utilizado en el conjunto de datos de entrenamiento. De esta forma, podremos comprobar lo robusto que es cada modelo ante cambios en el tipo de las piezas. Cada tablero tiene entre 21 y 32 piezas en posiciones diversas extra´ıdas de partidas reales. A diferencia del esquema que mostramos inicialmente en las Figuras 1.1 y1.2, las fotos para estas pruebas las hemos tomado desde un plano cenital. Adapt´andonos as´ı a las situaciones que hemos comentado en la secci´on 2.2 al obtener las casillas individuales del tablero (Figura 4.3). Como propondremos en el cap´ıtulo 6, en el caso de disponer de un dataset con el que recortar las casillas utilizando el m´etodo visto en el apartado 2.2.1, s´ı que pasar´ıamos a tomar las fotos desde un lateral. Los valores para la precisi´on los tomaremos como el porcentaje de casillas predichas correctamente por nuestro programa. Esto no coincide exactamente con lo que ser´ıa el valor Top-1 del modelo, ya que adem´as tenemos en cuenta el conocimiento sobre el dominio que hemos detallado en la secci´on 3.4. 31 Figura 4.3: Una de las im´agenes de prueba para la clasificaci´on de las piezas. Tomada en el XXXVII Torneo de Ajedrez Pueblo Nuevo 60’+30”. 4.4.1. Elecci´on del modelo Adelant´abamos en la secci´on 3.3 los modelos que hemos escogido para la clasificaci´on. Una vez entrenados sobre el dataset de piezas de ajedrez, tenemos que hacer una comparaci´on entre las precisiones obtenidas y el tiempo necesario para la inferencia. Para ello, en una primera aproximaci´on ejecutamos la inferencia sobre la Jetson Nano utilizando los modelos obtenidos directamente de Keras y obtenemos los resultados de la Tabla 4.1. Xception DenseNet201 NASNetMobile MobileNetV2 Test 1 95 % 18,73s 94 % 28,95s 94 % 11,81s 98 % 5,85s Test 2 94 % 18,73s 95 % 28,98s 92 % 12,01s 89 % 5,81s Test 3 95 % 18,73s 94 % 28,88s 91 % 11,73s 92 % 5,88s Test 4 91 % 18,72s 91 % 28,96s 91 % 11,68s 91 % 5,85s Test 5 97 % 18,72s 88 % 29,03s 98 % 11,89s 92 % 5,90s Media 94 % 18,73s 92 % 28,96s 93 % 11,82s 92 % 5,86s Tabla 4.1: Precisi´on y tiempo obtenido sobre la Jetson Nano para cada uno de los modelos iniciales ejecutando la inferencia mediante Keras. De estos primeros resultados podemos concluir que los cuatro modelos son lo suficientemente complejos como para aprender las caracter´ısticas que proporciona la imagen de una casilla, ya que proporcionan valores similares de precisi´on. De ellos, el m´as r´apido es el que tiene un menor n´umero de par´ametros, es decir, MobileNetV2. 32 Comparando, MobileNetV2 tiene unos 3,6 millones de par´ametros frente a los 5,4 millones de NasNetMobile, los 20,3 millones de DenseNet201 o los 23 millones de Xception. Viendo estos resultados nos preguntamos si con modelos m´as sencillos, cuya inferencia deber´ıa ser m´as r´apida, podr´ıamos obtener una precisi´on similar. As´ı, decidimos entrenar tambi´en una red AlexNet y otra SqueezeNet-v1.1. Adem´as de estas dos redes, la propia MobileNetV2 contiene un par´ametro αque controla el ancho de la red. Con α= 1, el n´umero de filtros en cada capa es el valor por defecto que proporcionan los autores del modelo. Con α > 1 se aumenta y con 0 < α < 1 se disminuye proporcionalmente el n´umero de filtros en cada capa. As´ı, incluimos en las pruebas la propia red MobileNetV2 con α= 0,5 y α= 0,35, valores para los cuales Keras proporciona pesos sobre ImageNet para inicializar el entrenamiento. MobileNetV2 MobileNetV2 AlexNet SqueezeNet-v1.1 α= 0,5α= 0,35 Test 1 95 % 3,10s 89 % 3,02s 81 % −97 % 1,27s Test 2 91 % 3,17s 75 % 3,05s 61 % −86 % 1,28s Test 3 94 % 3,09s 83 % 3,02s 81 % −92 % 1,28s Test 4 88 % 3,08s 83 % 3,02s 75 % −84 % 1,29s Test 5 91 % 3,12s 89 % 3,04s 73 % −94 % 1,28s Media 92 % 3,11s 84 % 3,03s 74 % −91 % 1,28s Tabla 4.2: Precisi´on y tiempo obtenido sobre la Jetson Nano para cada uno de los modelos m´as sencillos ejecutando la inferencia mediante Keras. En la Tabla 4.2 podemos observar los resultados de esta segunda bater´ıa de pruebas. Comprobamos que MobileNetV2 mantiene la precisi´on con α= 0,5, reduciendo el tiempo empleado en la inferencia a casi la mitad que con α= 1. El otro modelo que consigue una precisi´on superando el 90 % es SqueezeNet-v1.1, que adem´as es el m´as r´apido de todos los candidatos al ejecutarse directamente mediante Keras sobre la Jetson Nano. La precisi´on de MobileNetV2 con α= 0,35 es notablemente inferior a la variante con α= 0,5 sin conseguir apenas mejoras en el tiempo. El modelo que peores resultados obtiene es AlexNet. En este caso, al igual que con SqueezeNet-v1.1, hemos realizado la implementaci´on a partir de cada capa bas´andonos en otros modelos que no est´an incluidos oficialmente en la librer´ıa de Keras. Sin embargo, al contrario que con el resto de modelos, no hay disponibles pesos sobre ImageNet para la implementaci´on que hemos realizado de AlexNet. Estos han sido los mejores resultados que hemos obtenido tras varios entrenamientos. Este hecho ha podido ser un factor a la hora de explicar por qu´e la precisi´on es inferior al resto cuando en teor´ıa este modelo se comporta como SqueezeNet-v1.1 sobre ImageNet. Adem´as, ha sido demasiado pesado en memoria para ejecutarse de esta manera sobre la Jetson Nano (los resultados de la Tabla 4.2 son los obtenidos en nuestro PC, de ah´ı que no incluyamos valores para los tiempos). Podremos hacer un mejor an´alisis 33 tanto, reducimos el n´umero de modelos a considerar de 8 a 4 y, dependiendo de nuestras necesidades, podr´ıamos optar por una de las siguientes redes: SqueezeNetv1.1, MobileNetV2 (α= 0,5), NASNetMobile o Xception. N´otese que la ejecuci´on de NASNetMobile es sobre ONNXRuntime. Figura 5.1: Precisi´on obtenida por cada modelo en funci´on del tiempo necesario para la inferencia de un tablero sobre la Jetson Nano mediante TensorRT en un batch de 64 im´agenes, salvo NASNetMobile, cuyo mejor tiempo es sobre ONNXRuntime. Omitimos AlexNet por obtener una precisi´on mucho menor. 5.3. Digitalizaci´on total La completa digitalizaci´on de un tablero de ajedrez comprende desde que el sistema detecta que hay una nueva imagen a procesar hasta que termina de procesarla y produce una cadena en notaci´on FEN. En las secciones anteriores hemos estudiado en detalle los resultados que hemos obtenido para la detecci´on del tablero en la imagen inicial y la clasificaci´on de las piezas una vez separadas las casillas individuales. Adem´as de estas dos acciones, que suponen la practica totalidad del tiempo de ejecuci´on, existen otras tres operaciones que hay que completar para terminar todo el proceso. En primer lugar, una vez detectado el tablero de ajedrez debemos separar las casillas individuales (secci´on 2.2). Esto supone unos 80 milisegundos sobre la Jetson Nano. Adem´as, despu´es de obtener los vectores de probabilidades de la red que es40 temos utilizando, hay que inferir cu´al es la configuraci´on de piezas (secci´on 3.4) y finalmente transformar esta informaci´on a la notaci´on FEN (secci´on 3.1). La suma del tiempo necesario para ejecutar estas dos operaciones es inferior a los 10 milisegundos. Por tanto, adicionalmente a los tiempos de los procesos que hemos estudiado en profundidad, debemos a˜nadir algo menos de 100 milisegundos para completar la digitalizaci´on. Resumimos todos los tiempos que hemos obtenido en la Tabla 5.4. Aqu´ı podemos ver de forma m´as clara que existe una variable importante a la hora de desplegar el sistema, qu´e red utilizar para la clasificaci´on de las piezas. Esto depender´a del uso final del programa y, como veremos en el cap´ıtulo de conclusiones y trabajo futuro, de las necesidades y mejoras que se puedan implementar. Test 1 Test 2 Test 3 Test 4 Test 5 Detecci´on tablero 4,21s 3,30s 4,28s 3,69s 3,35s Separar casillas individuales 0,08s Obtener vectores de probabilidades SqueezeNet-v1.1 0,46s MobileNetV2 (α= 0,5) 0,60s NASNetMobile 3,42s Xception 5,61s Inferir piezas + Notaci´on FEN 0,01s Total SqueezeNet-v1.1 4,76s 3,85s 4,83s 4,24s 3,90s MobileNetV2 (α= 0,5) 4,90s 3,99s 4,97s 4,28s 4,04s NASNetMobile 7,72s 6,81s 7,79s 7,20s 6,86s Xception 9,91s 9,00s 9,98s 9,39s 9,05s Tabla 5.4: Resumen de tiempos totales sobre la Jetson Nano por tablero de prueba para cada uno de los modelos que forman el frente de Pareto. Al estudiar los tiempos que emplea nuestro programa en ejecutar cada una de estas fases observamos que, si optamos por las redes m´as peque˜nas para la clasificaci´on de las piezas, la inmensa mayor´ıa del tiempo transcurre en la fase de detecci´on del tablero. En situaciones en las que sepamos que el tablero y la c´amara van a estar inm´oviles, podemos aprovechar para no recalcular su posici´on cada vez. As´ı, simplemente tenemos que mantener las coordenadas de las esquinas que hemos calculado anteriormente, comprobar que el tablero sigue en el mismo sitio y pasar a separar las casillas directamente. Siguiendo la idea introducida en el apartado 2.1.2, hemos implementado un algoritmo que nos permite comprobar de una forma r´apida si el tablero sigue en la misma posici´on. Para ello, utilizamos el detector geom´etrico y la red neuronal vistos al buscar los puntos de la cuadr´ıcula. Si las 49 esquinas del cuadrado central 6 ×6 41 del tablero siguen en su sitio, podremos afirmar que la informaci´on que ten´ıamos sigue siendo correcta. Al contar las esquinas que s´ı forman parte de la cuadr´ıcula tendremos que tomar un margen de tolerancia, ya que hay puntos que pueden estar ocluidos por alguna pieza. De forma experimental hemos comprobado que acertando 20 de los 49 puntos que comprobamos es suficiente para afirmar que el tablero sigue en el mismo sitio (Algoritmo 5.1). Algoritmo 5.1: Comprobaci´on de la posici´on del tablero. Entrada: Imagen que contiene un tablero. Esquinas candidatas a seguir formando parte del cuadrado central 6 ×6 del tablero. Salida: Si el tablero sigue en la misma posici´on. 1esquinas correctas ←0; 2para cada punto ∈esquinas hacer 3matriz ←preprocesar(vecindad(imagen,punto)); 4es punto cuadricula ←detector geometrico(matriz); 5si es punto cuadricula entonces 6esquinas correctas ←esquinas correctas + 1; 7en otro caso 8es punto cuadricula ←red neuronal(matriz); 9si es punto cuadricula entonces 10 esquinas correctas ←esquinas correctas + 1; 11 fin 12 // Si no pertenece a la cuadr´ıcula, pasamos a la siguiente 13 fin 14 fin 15 devolver esquinas correctas ≥tolerancia (= 20) La ejecuci´on de este algoritmo sobre la Jetson Nano tarda unos 150 milisegundos por tablero. Luego en caso de devolver un resultado positivo conseguimos una reducci´on enorme en el tiempo total. En la Tabla 5.5 resumimos los tiempos cuando esta comprobaci´on devuelve cierto. Como podemos observar, esta predicci´on reducir´ıa el tiempo total necesario para digitalizar nuevas posiciones a menos de un segundo. Adem´as, con este tiempo se podr´ıa a˜nadir un muestreo peri´odico de im´agenes para capturar posibles jugadas intermedias. Se podr´ıan evitar de esta forma los casos en los que haya, por ejemplo, una mano tapando parte del tablero. Este peque˜no sobrecoste que habr´ıa que a˜nadir en caso de que la comprobaci´on devuelva falso se ve altamente compensado. En la Tabla 5.4 hemos visto que el tablero que se detecta m´as r´apido tarda 3,30 segundos, luego con que la comprobaci´on devolviera cierto en 1 de cada 14 ocasiones, se ver´ıan amortizadas estas llamadas. 42 Tablero inm´ovil Comprobaci´on tablero 0,15s Separar casillas individuales 0,08s Obtener vectores de probabilidades SqueezeNet-v1.1 0,46s MobileNetV2 (α= 0,5) 0,60s NASNetMobile 3,42s Xception 5,61s Inferir piezas + Notaci´on FEN 0,01s Total SqueezeNet-v1.1 0,70s MobileNetV2 (α= 0,5) 0,84s NASNetMobile 3,66s Xception 5,85s Tabla 5.5: Resumen de tiempos totales para cada uno de los modelos que forman el frente de Pareto sobre la Jetson Nano cuando la comprobaci´on de la posici´on del tablero devuelve cierto. 43 Cap´ıtulo 6 Conclusiones y trabajo futuro La visi´on artificial es un campo que est´a tomando una gran relevancia en muchas situaciones. El acceso de la sociedad a dispositivos capaces de interactuar con el mundo que les rodea ha supuesto la automatizaci´on de tareas muy diversas, bien sea mediante c´alculos en sistemas empotrados o utilizando el poder de c´omputo de potentes servidores alojados en la nube. En el ´ambito del ajedrez, uno de los primeros juegos para los que se desarroll´o un algoritmo de inteligencia artificial, tambi´en se puede aplicar este campo a la automatizaci´on de la digitalizaci´on de las partidas. En este trabajo hemos explorado una de las opciones que mejores resultados proporciona en la actualidad y hemos creado un programa que es capaz de seguir el ritmo de una partida de ajedrez sobre un sistema empotrado. Como hemos podido observar en los resultados finales (Tabla 5.4), el tiempo total utilizando tanto SqueezeNet-v1.1 como MobileNetV2(α= 0,5) se mantiene por debajo de los 5 segundos para todos los tableros de prueba sobre la Jetson Nano. Esto es alcanzando una precisi´on de 91 y 92 % respectivamente a la hora de clasificar las piezas. M´as a´un, si el tablero permanece inm´ovil, estos tiempos se reducen hasta los 0,70 y 0,84 segundos respectivamente. El tiempo que nos marcamos como objetivo inicialmente fueron 5 segundos por jugada. Por lo tanto, despu´es de partir de un tiempo total que rondaba entre los 25 y 45 segundos por tablero, duraci´on que no hac´ıa factible su uso pr´actico, hemos podido alcanzar una meta que permitir´ıa su despliegue en situaciones reales. Todo ello realizando los c´alculos ´ıntegramente en un sistema empotrado sin necesidad de conectividad con ninguna red. El c´odigo completo del programa que hemos desarrollado se encuentra de forma p´ublica en nuestro repositorio de GitHub: https://github.com/davidmallasen/LiveChess2FEN. Entrenando las distintas redes neuronales convolucionales para la clasificaci´on de las piezas nos hemos encontrado con una barrera a la hora de mejorar la precisi´on. Los modelos m´as sencillos han sido capaces de aprender pr´acticamente toda la informaci´on disponible en el dataset que hemos podido recopilar, y el hecho de tomar modelos m´as complejos no ha proporcionado casi beneficio (Tabla 4.1). Teniendo en cuenta esto, consideramos que parte de este problema se solucionar´ıa introduciendo m´as informaci´on en el dataset, por ejemplo mediante el nuevo m´etodo de separaci´on de casillas que hemos propuesto (apartado 2.2.1). As´ı evitar´ıamos los casos en los que solo se ve la base de la pieza, situaci´on en la que ni siquiera un humano es capaz de distinguirla. En el caso de que mejorando el dataset se obtuvieran resultados m´as precisos con un modelo que requiera un mayor esfuerzo de c´omputo, la disponibilidad de 44 n´ucleos tensoriales para el c´alculo de operaciones en FP16 ser´ıa una mejora cr´ıtica. Una evoluci´on de la Jetson Nano, que tiene el mismo factor de forma, es la Jetson Xavier NX [Nvic]. Actualmente, este m´odulo ronda los 400$, unas 4 veces m´as que la Jetson Nano, aunque previsiblemente con la reciente salida de la arquitectura Ampere habr´a una reducci´on de precios o nuevos modelos con precio inferior. La Jetson Xavier NX tiene una GPU con una arquitectura Volta que aporta 384 n´ucleos CUDA, 48 n´ucleos tensoriales y 2 n´ucleos NVDLA (NVidia Deep Learning Accelerator), frente a los 128 n´ucleos CUDA de la Jetson Nano que hemos empleado nosotros. Adem´as, dispone de una CPU hexa-core y 8 GB de RAM, ante los cuatro n´ucleos y 4 GB de nuestra plataforma. Todo ello hace que sea capaz de alcanzar 6 TFLOPS en FP16, unas 12 veces m´as de lo que disponemos actualmente. Adem´as, a diferencia de la Jetson Nano, permite la ejecuci´on de operaciones en enteros de 8 bits, a una raz´on de 21 TOPS. Esto ´ultimo se podr´ıa aprovechar transformando los modelos y calibrando los rangos de los pesos mediante las capacidades que proporciona TensorRT. El hecho de disponer de m´as n´ucleos de CPU har´ıa factible la paralelizaci´on de algunas secciones del c´odigo de la detecci´on del tablero. Por ejemplo, se podr´ıan calcular paralelamente en diferentes procesos las distintas m´ascaras CLAHE en los pasos hasta la obtenci´on de los segmentos, como hemos visto en el Algoritmo 2.2. Esto ha supuesto una mejora de un 10 % en el tiempo total sobre una CPU Intel Core i7-4770K con 4 n´ucleos con hyperthreading, utilizando la clase ProcessPoolExecutor de Python. Sin embargo, al hacer la prueba sobre la Jetson Nano los tiempos se han mantenido constantes. En el apartado 3.4.1 hemos introducido un algoritmo que permite inferir las piezas que se mueven en un tablero a partir de dos im´agenes consecutivas. En el caso de conocer con certeza la configuraci´on inicial de las piezas, por ejemplo digitalizando una partida desde el comienzo, podremos conocer de forma precisa el n´umero y tipo de piezas que hay en cada momento sobre el tablero. Esta informaci´on se podr´ıa incluir en el Algoritmo 3.1 para afinar m´as la funci´on alcanzado max. En ocasiones, sobre todo en partidas infantiles, alguno de los jugadores realiza un movimiento ilegal. Teniendo la certeza del tipo de pieza que realiza el movimiento, por ejemplo por im´agenes de las acciones anteriores, se podr´ıa advertir de estas situaciones. Esto servir´ıa tanto como informaci´on adicional para el usuario, como para corregir malas predicciones que podr´ıan darse a ra´ız de estas jugadas il´ıcitas. Adem´as, en todos los casos en los que sabemos que una pieza ha permanecido quieta, podemos utilizar los vectores de probabilidades que hemos obtenido en im´agenes anteriores para aumentar nuestro conocimiento. Por ejemplo, podr´ıamos tomar la media de estas probabilidades en las fotos en las que no se ha movido. De esta manera mejorar´ıamos la inferencia en situaciones en las que antes hab´ıa una pieza ocluyendo parte de la casilla que estamos considerando. 45 Cap´ıtulo 7 Introduction (English) The recognition of chess pieces and chessboards is a computer vision problem that has not yet been solved efficiently. However, its solution is crucial for many experienced players who want to compete against chess engines and specialized programs, but who also prefer to make decisions using a physical chessboard. It is also important for chess tournament organizers who want to broadcast the games online or for amateur players who want to share their games with friends. These digitizing tasks are usually performed by humans or with the help of specialized chessboards and pieces. In order to digitize a game automatically, it is necessary to be able to recognize both the chessboard and afterwards the layout of the pieces. In live games, in addition to precision, it is critical to minimize the time required to perform such recognition, since the moves can happen very quickly. This is the case of the game modes known as “Blitz” and “Bullet”, in which each player has between 1 and 5 minutes to play the entire game. This is also true in classic games when there is little time left. 7.1. Related work Specialized boards that physically detect the pieces are a hardware solution for automatic chess digitization. Recent examples currently used in major tournaments can be found in [Squ] or [DGTa]. However, these boards are expensive and difficult to deploy in many areas. As an example, a set of DGT chessboard and pieces (brand used in official tournaments) costs between e500 and e1000 [DGTb]. Other alternatives are those provided by robots that move the pieces on a board, such as [Mat+11] or more recently [CW19]. These robots are based on positioning a zenith camera over the board and detecting the differentials between one movement and the next. A drawback of this is that it is necessary to start from a known initial layout. A board with a generic layout could not be digitized this way. In addition, errors should be taken into account, because they could add up in each new play. The solutions offered by computer vision are an alternative to consider, since they provide cheaper and increasingly accurate systems, as well as being a major technological challenge. For comparison, the platform we will be using for inference, an Nvidia Jetson Nano, costs around e110 [Nvib] and does not just stick to one function, it could be reused for another task. These computer vision procedures are based on combining and adapting trans46 formations and detectors already known and used in other fields, such as the Harris corner detector and the Hough transform [EA10]. Many of the methods often assume big simplifications, such as determining the exact position of the camera, using boards specifically designed with markers to aid in corner detection, or directly through user interaction [Din16]. However, some generic solutions that overcome these restrictions already exist. For example, there are methods that allow us to classify occurrences of various objects in arbitrary places using convolutional neural networks (CNNs) [Gao+17], but they do not have the precision required to obtain their exact position. The authors of [Ben+16] describe a method for object detection that also uses CNNs trained through weak supervision. That is, it is enough to have labeled images of the objects in order to train the network, without the need to also provide the exact position of the object in each training image. The problem with this approach is that it takes many iterations to precisely locate an object, which does not make it very practical in situations that require real-time responses. The authors of [CLW17] propose a method for chessboard detection that is robust against light conditions and the angle from which the images are taken. In addition, it works with most styles of boards and it overcomes many of the weaknesses that we have been discussing. It is an iterative process in which the position of the board is refined in several phases. The authors get 99,5 % accuracy in detecting the intersections of the center board grid and find the full position of the chessboard accurately 95 % of the time. Regarding piece classification once the board has been located, in [Din16] a method is proposed that uses a support vector machine (SVM). This is trained on the features extracted by SIFT [Low04], thus achieving 85 % accuracy when classifying the pieces. In [CLW17] authors claim to achieve 95 % accuracy classifying chess pieces using a convolutional neural network (CNN), which they enhance by clustering similar pieces, taking into account their height and area, and using a game engine to obtain the probability of particular layouts. The code for these enhancements has not been released, so we were unable to analyze this particular approach. 7.2. Objectives and work plan The processing of each frame is still too slow in order to host live broadcasts. Therefore, accelerating this computation is a very important challenge. Our final objective is to build a functional framework that is capable of executing the entire process of digitizing a chess game photo in real-time, making all the necessary calculations on specialized hardware. To accomplish this, we have made a series of changes to a method already implemented that detects the chessboard. We have refactored the code and modified some modules to include new possibilities (see for example section 2.2.1 or board 47 position checking in section 5.3). In addition, we have optimized the code based on performance analysis tools and we have accelerated its execution on our hardware (section 4.3). To complete the framework, we have built a convolutional neural network to classify the obtained pieces and we have drastically reduced the necessary inference time in the final system (section 4.4). We have carried this out having in mind its use in amateur games or in tournaments, taking the photos from the side of the board each time a player presses the clock (Figure 1.1). However, sometimes players forget to press the clock. In these cases, periodic sampling based on the processing speed of an image would be necessary to try to capture all the moves. We show a schematic of the camera position in Figure 1.2. 48 Cap´ıtulo 8 Conclusions and future work Computer vision is a field that is acquiring great relevance in many situations. Universal access to devices capable of interacting with the world around them has meant the automation of very diverse tasks, either through embedded systems or using the computing power of servers hosted in the cloud. In chess, one of the first games for which an artificial intelligence algorithm was developed, computer vision can also be applied to automate the digitization of games. In this work we have explored one of the options that currently provide the best results and we have created a program that can keep up with a chess game on an embedded system. As we have seen in the final results (Table 5.4), the total time using both SqueezeNet-v1.1 and MobileNetV2(α= 0.5) remains below 5 seconds for all test boards on the Jetson Nano. Achieving an accuracy of 91 and 92 % respectively when classifying the chess pieces. Furthermore, if the board remains static, these times are reduced to 0.70 and 0.84 seconds respectively. Initially, the time we set as our goal was 5 seconds per board. Therefore, starting from a total time between 25 and 45 seconds, a cost that did not make its practical use feasible, we have been able to reach a target that would allow its deployment in practical scenarios. Moreover, the calculations are performed entirely on an embedded system without the need for connectivity to any network. The complete source code of the framework that we have developed is publicly available in our GitHub repository: https://github.com/davidmallasen/LiveChess2FEN. Whilst training the different convolutional neural networks, we have found a barrier when it comes to improving precision for piece classification. The simplest models have been able to learn practically all the information available in the dataset that we have been able to collect, and training more complex models has provided almost no benefit (Table 4.1). With this in mind, we believe that part of this problem would be solved by introducing more information into the dataset, for example by means of the new method for square separation that we have proposed (section 2.2.1). This way we would avoid the cases in which only the base of the piece is seen, a situation in which not even a human is able to distinguish it. If more accurate results were obtained by improving the dataset with a model that requires a greater computational effort, the availability of tensor cores for calculating operations in FP16 would be a critical improvement. An evolution of the Jetson Nano, which has the same form factor, is the Jetson Xavier NX [Nvic]. Currently, this module costs around $400, about 4 times more than the Jetson Nano, although with the recent release of the Ampere architecture, a reduction in prices or new models for a lower price are expected. 49