Estamos seguros de que hoy no hay un solo lector de Habr que no esté familiarizado con los códigos QR. Estos códigos de barras bidimensionales están en todas partes. Es lógico que en el mundo haya muchas herramientas que permitan agregar códigos QR a su proyecto con cierto grado de eficiencia. El punto es que esta eficiencia mencionada depende directamente de la calidad de la herramienta que se utiliza para reconocer los códigos QR. Y aquí viene el complemento clásico: puede resolver el problema (muy) bien y (muy) caro, o puede hacerlo de forma gratuita y de alguna manera. ¿Es posible modificar la versión gratuita para que, sin embargo, resuelva bien el problema? Si está interesado, mire debajo del gato.Reconocer un código QR en una fotografía es una tarea bien planteada de la visión artificial. En primer lugar, en la tarea, se investiga un objeto, que originalmente fue especialmente diseñado para el reconocimiento "conveniente". En segundo lugar, la tarea en sí se divide en varias subtareas entendibles independientes: localización del código QR, orientación del código QR y decodificación directa del código QR. Resultó que el dominio público ha tenido durante mucho tiempo buenas bibliotecas que pueden resolver los dos últimos problemas: orientación y decodificación de un código QR. Un problema: para la decodificación de alta calidad, tales bibliotecas esperan que se ingrese una buena imagen binaria directamente del código de barras. Por el contrario, se presta poca atención a la tarea de localización de códigos de barras en la imagen.En nuestra experiencia, cuanto más exactamente localice un objeto de reconocimiento, más fácil será elegir las herramientas de preprocesamiento adecuadas y, de hecho, reconocerlo. Por lo tanto, si desea mejorar la calidad del reconocimiento de los códigos QR en su proyecto, comience con la modernización de los métodos para localizar los códigos QR. De hecho, incluso si luego necesita binarizar una imagen, es mucho más eficiente (tanto desde el punto de vista computacional como cualitativo) binarizar una región con un código de barras que toda la imagen original.En este artículo, le diremos cómo mejorar fácilmente la calidad de localización de los códigos QR utilizando métodos clásicos de procesamiento de imágenes, así como proporcionar características numéricas de la efectividad del algoritmo propuesto.Hablaremos sobre la forma original de localizar códigos QR en imágenes, utilizando el método modificado de Viola y Jones como base.Nota informativa sobre el tema del artículo.
En esta sección, describimos las características clave del código QR que se utilizan para construir el método de localización, así como una breve descripción de la versión original del método Viola y Jones.Código QR
El código QR (abreviatura de Quick Response Code) es un código de barras bidimensional que se desarrolló en Japón a mediados de los 90 para la industria automotriz. Debido a la capacidad de leer rápidamente y a una mayor capacidad en comparación con los códigos de barras lineales, el sistema de códigos QR se ha vuelto popular en todo el mundo en diversas áreas de la vida.A diferencia de los códigos de barras lineales estándar, que generalmente son escaneados por hardware, una cámara escanea un código QR. La estructura del código QR se describe completamente en ISO / IEC 18004 (El estándar ISO / IEC 18004). Para construir un algoritmo de reconocimiento robusto para tales imágenes, el código QR tiene algunos puntos de referencia que forman un patrón de función: tres cuadrados en las esquinas de la imagen del código de barras (llamados patrones de búsqueda) y cuadrados de sincronización más pequeños en toda la imagen del código de barras (llamados patrones de alineación) . Dichos puntos le permiten normalizar el tamaño de la imagen y su orientación.
Higo. Estructura del código QR
Aunque visualmente todos los códigos QR son similares entre sí, las diferentes copias de los códigos QR, dependiendo de la cantidad de datos codificados, pueden tener un diseño diferente de elementos internos. Además, los llamados códigos QR de diseño son muy populares, en el que, en lugar de la parte de información adicional que garantiza el reconocimiento de alta calidad del código de barras, se utilizan elementos gráficos de terceros (logotipos, emblemas, inscripciones, etc.). Todas estas características de los códigos QR deben tenerse en cuenta al construir métodos para la localización y el reconocimiento de los códigos QR.
Higo. Diferentes opciones de códigos QR válidos
Método Viola y Jones
Solo los perezosos de Habré aún no escribieron sobre el método de Viola y Jones. Incluso nosotros en nuestro bloque hicimos esto varias veces (por ejemplo, aquí , aquí o aquí ). Y aún así, consideramos necesario decir muy brevemente, literalmente en dos párrafos, qué es.El método de detección de objetos Viola y Jones se desarrolló para buscar rostros en una imagen en tiempo real. Este método reduce el problema de detección al problema de clasificación binaria en cada punto de imagen, es decir, para cada región de imagen rectangular tomada con todo tipo de cambios y escalas, la hipótesis de la presencia del objeto deseado en la región se verifica utilizando un clasificador previamente entrenado.Como espacio de características, el método Viola y Jones utiliza características rectangulares de Haar, cuyo valor se calcula como la diferencia entre las sumas del brillo de los píxeles de las áreas de imagen dentro de los rectángulos adyacentes. Para calcular de manera efectiva el valor de las características de Haar, se utiliza una imagen integrada, que también se conoce en la literatura bajo el término tabla de área sumada. Un clasificador binario "débil" h ( x ): Χ → {-1, + 1}, generalmente presentado como un árbol de reconocimiento con una rama:
donde θ y p- el valor umbral del atributo y la paridad del clasificador, respectivamente. Luego, usando el método de aprendizaje automático AdaBoost, se construye un clasificador "fuerte" como una superposición lineal de los clasificadores "débiles" anteriores. La alta velocidad del método Viola y Jones se garantiza mediante el uso de una cascada de clasificadores "fuertes", que permite localizar regiones de imagen "vacías" (sin objetos) en un pequeño número de cálculos.Algoritmo de detección de código QR
Al construir un método para localizar un código QR, confiamos en las siguientes características de la tarea. Primero, el método desarrollado debe tener un alto rendimiento para su uso en sistemas de reconocimiento que operan en tiempo real. En segundo lugar, el método debe ser resistente a la distorsión permitida del código de barras en la imagen. En tercer lugar, el método debe tener en cuenta toda la variabilidad existente de los códigos QR.Como se mencionó anteriormente, hemos elegido el método de Viola y Jones como método fundamental. Este método ha demostrado su eficacia en diversas tareas de búsqueda de objetos rígidos, mientras que proporciona el rendimiento requerido. Pero en la versión original, el método Viola y Jones no se puede usar por las siguientes razones:- En el método clásico de Viola y Jones, se utiliza una familia de atributos de Haar que "enfatizan" las características de textura del objeto, y en nuestro caso, aunque el código QR consiste en barcels en blanco y negro, su distribución es muy diferente del código de barras al código de barras;
- El método clásico de Viola y Jones está diseñado para el mismo tipo de detección de objetos en una orientación dada, que tampoco se observa en nuestra tarea.
Para que el método Viola y Jones se pueda aplicar para resolver el problema, utilizamos la familia original de características de límite y un clasificador de alto nivel en forma de árbol de decisión. La primera modificación permitirá enfocarse en las características de contorno del objeto estudiado, y no en la textura. La segunda modificación le permitirá construir un único clasificador que puede detectar objetos variables. A continuación, le contaremos un poco más sobre cada modificación.Signos de gradiente de Haar.
Para construir un detector efectivo de códigos QR, utilizamos una familia especial de características de gradiente [1]. Estos signos son signos rectangulares de Haar, calculados en la parte superior del mapa de límites dirigidos, que pueden mejorar significativamente su poder generalizador.El mapa de límites direccionales es una imagen del módulo de gradiente, que además tiene en cuenta la dirección preferida del gradiente en el punto ( x , y ), definida como la discretización del ángulo del borde en direcciones horizontal, vertical, + 45 ° y –45 °. Para construir un detector de código QR, utilizamos dos tipos de mapa de límites direccionales: un mapa de límites rectos y un mapa de caras diagonales.Deje que la imagen original f ( x ,y ) Luego puede calcular el valor aproximado de la derivada a lo largo de las direcciones horizontal y vertical usando el operador Sobel:
Además, usando g x y g y , puede calcular la dirección del gradiente en cada punto de la imagen: El
mapa de bordes rectos contiene principalmente bordes horizontales y verticales y se calcula de la siguiente manera:
Mapa los bordes diagonales contienen principalmente bordes a lo largo de las diagonales y se calcula de la siguiente manera:
en la parte superior del mapa construido de bordes dirigidos (diagonales o rectos), se calculan los signos rectangulares de Haar. A diferencia de las características clásicas de Haar, tales características de límite generalizan objetos bien que contienen una gran cantidad de límites.
Higo. Ilustración de un mapa de bordes dirigidos: (a) la imagen original de un código QR, (b) un mapa de bordes rectos, (c) una imagen de un código QR girado (d) un mapa de los bordes diagonales de un código QR girado
El árbol decisivo de clasificadores fuertes
El árbol de clasificadores fuertes [2] es una especie de árbol de decisión binario: el nodo del árbol es un clasificador fuerte, en el borde derecho del cual hay subventanas que presumiblemente contienen el objeto, y a la izquierda, aquellos que no fueron reconocidos como un objeto, respectivamente. La respuesta final se da solo en hojas. El clasificador en cascada clásico descrito en el trabajo original de Viola y Jones es, de hecho, un clasificador de árbol que contiene solo una salida "positiva" (hoja) y muchas salidas "negativas".En [2], se muestra que cualquier ruta desde la raíz hasta el nodo más bajo del clasificador de árbol se puede representar como una cascada en la que los clasificadores fuertes individuales entran con una respuesta invertida. Gracias a esto, es posible construir un algoritmo de aprendizaje para el clasificador de árbol, que utiliza el procedimiento de entrenamiento del clasificador clásico en cascada para enseñar caminos individuales.El clasificador de árbol le permite entrenar clasificadores que son más efectivos en términos de completitud para objetos variables en comparación con los clasificadores en cascada clásicos.Resultados experimentales
Como parte de un experimento para evaluar la efectividad del método de localización de código de barras propuesto en este artículo, se preparó un conjunto de imágenes de código de barras que consta de 264 imágenes. El tamaño físico de las imágenes fue de aproximadamente 1 MPix. Cada imagen contiene solo un código QR en una orientación arbitraria, el área del código de barras era al menos el 10% del área total de la imagen. La figura siguiente muestra ejemplos de imágenes del conjunto ensamblado.
Higo. Ejemplos de imágenes del conjunto de imágenes de código de barras ensamblado
El conjunto de imágenes preparado se dividió en un conjunto de entrenamiento y un conjunto de prueba. El tamaño de la muestra de entrenamiento fue de 88 imágenes, el tamaño de la muestra de prueba fue de 176 imágenes.El conjunto de entrenamiento se usó tanto para preparar ejemplos positivos como para preparar ejemplos negativos. Dado que el número inicial de ejemplos positivos fue pequeño, utilizamos tecnología de aumento de datos [3]. En particular, aplicamos la rotación alrededor del centro del código de barras en incrementos de 15⁰. Después del aumento, el número de ejemplos positivos fue de 2088 ejemplos.Usando los mismos ejemplos positivos y negativos, capacitamos a tres detectores de código QR: un clasificador en cascada clásico con características estándar de Haar, un clasificador en cascada clásico con características de límite y un clasificador de árbol con características de límite. El primer clasificador en cascada constaba de 12 niveles y contenía un total de 58 atributos. El segundo clasificador en cascada constaba de 8 niveles y contenía un total de 39 atributos. El clasificador de árbol entrenado consistía en 39 vértices, contenía un total de 110 caracteres, y la ruta máxima desde la parte superior hasta la hoja era 9. A continuación se muestra un diagrama del clasificador de árbol entrenado.
Higo. Esquema de clasificador de árbol entrenado
Para evaluar la calidad de los detectores de códigos QR construidos, utilizamos el módulo de decodificación de código de barras de la biblioteca de visión por computadora de código abierto OpenCV. En el conjunto de imágenes de prueba preparado (que, como se mencionó anteriormente, consistía en 176 imágenes), lanzamos el módulo de decodificación sin ningún procesamiento previo especial, así como después de una búsqueda preliminar de códigos QR utilizando detectores capacitados. A continuación se muestran los resultados de la decodificación del código de barras:La tabla muestra que la localización preliminar del código QR utilizando el método descrito puede mejorar significativamente la calidad de la decodificación de códigos de barras (el número de errores de decodificación disminuyó en un 44%). Además, los resultados también demuestran que la aplicación del método original de Viola y Jones (con características clásicas de Haar y un clasificador en cascada) no es eficaz en la tarea de localizar códigos QR.Ahora veamos con qué precisión cada clasificador localiza el código de barras. La figura de izquierda a derecha muestra los resultados de detectar el mismo código de barras con un clasificador en cascada clásico con características estándar de Haar, un clasificador en cascada clásico con características de límite y un clasificador de árbol con características de límite. Se puede ver que el clasificador de árbol proporciona la mejor precisión de localización de código de barras teniendo en cuenta la variabilidad de los códigos QR.
Higo. Ilustración del trabajo de detectores capacitados en la misma imagen.
Conclusión
Hoy en día, los códigos QR se utilizan en diversas áreas de la vida: en la industria publicitaria para codificar URL, en el segmento estatal como parte de servicios electrónicos, etc. A pesar de la distribución extremadamente alta de dichos códigos de barras, las bibliotecas de código abierto existentes se centran en el proceso de decodificación, no en el problema de localización. Pero para ser honesto, el verdadero propósito de este artículo no fue tanto describir un método efectivo de localización de códigos QR, sino más bien un intento de decirle, querido lector, cómo, utilizando el pensamiento científico y el análisis de sistemas, entendiendo cómo usar las herramientas clásicas de procesamiento de imágenes digitales, puede liberar Las bibliotecas llevan al nivel industrial real. Gracias por la atención.Lista de fuentes utilizadas[1] A.A. Kotov, S.A. Usilin, S.A. Gladilin, and D.P. Nikolaev, “Construction of robust features for detection and classification of objects without characteristic brightness contrasts,” Journal of information technologies and computing systems, 1, 53-60, (2014).
[2] A. Minkina, D. Nikolaev, S. Usilin, and V. Kozyrev, “Generalization of the Viola-Jones method as a decision tree of strong classifiers for real-time object recognition in video stream,” in Seventh International Conference on Machine Vision (ICMV 2014), 9445, International Society for Optics and Photonics, (2015), doi:10.1117/12.2180941.
[3] D. P. Matalov, S. A. Usilin, and V. V. Arlazarov, “Modification of the viola-jones approach for the detection of the government seal stamp of the russian federation,” in Eleventh International Conference on Machine Vision (ICMV 2018), 11041, International Society for Optics and Photonics, (2019), doi:10.1117/12.2522793.