Nous sommes sûrs qu'aujourd'hui il n'y a pas un seul lecteur Habr qui ne connaîtrait pas les codes QR. Ces codes-barres bidimensionnels sont partout. Il est logique que dans le monde, il existe de nombreux outils qui permettent d'ajouter des codes QR à votre projet avec un certain degré d'efficacité. Le fait est que cette efficacité mentionnée dépend directement de la qualité de l'outil utilisé pour reconnaître les codes QR. Et voici la prise classique: vous pouvez résoudre le problème (très) bien et (très) cher, ou vous pouvez le faire gratuitement et en quelque sorte. Est-il possible de modifier le gratuit pour qu'il résout néanmoins bien le problème? Si vous êtes intéressé, regardez sous le chat.Reconnaître un code QR sur une photo est une tâche bien posée de la vision industrielle. Premièrement, dans la tâche, un objet est étudié, qui était à l'origine spécialement conçu pour une reconnaissance «pratique». Deuxièmement, la tâche elle-même est divisée en plusieurs sous-tâches compréhensibles indépendantes: localisation du code QR, orientation du code QR et décodage direct du code QR. Il s'est avéré que le domaine public dispose depuis longtemps de bonnes bibliothèques capables de résoudre les deux derniers problèmes: l'orientation et le décodage d'un code QR. Un problème: pour un décodage de haute qualité, ces bibliothèques s'attendent à ce qu'une bonne image binaire directement du code-barres soit entrée. Inversement, peu d'attention est accordée à la tâche de localisation des codes-barres dans l'image.D'après notre expérience, plus vous localisez avec précision un objet de reconnaissance, plus il est facile de choisir les bons outils de prétraitement et, en fait, de le reconnaître. Par conséquent, si vous souhaitez améliorer la qualité de reconnaissance des QR codes dans votre projet, alors commencez par la modernisation des méthodes de localisation des QR codes. En effet, même si vous devez ultérieurement binariser une image, il est beaucoup plus efficace (à la fois d'un point de vue informatique et qualitatif) de binariser une région avec un code-barres que la totalité de l'image d'origine.Dans cet article, nous vous expliquerons comment améliorer facilement la qualité de localisation des codes QR à l'aide des méthodes classiques de traitement d'image, ainsi que fournir des caractéristiques numériques de l'efficacité de l'algorithme proposé.Nous parlerons de la façon originale de localiser les codes QR sur les images en utilisant la méthode modifiée de Viola et Jones comme base.Note d'information sur le sujet de l'article
Dans cette section, nous décrivons les principales caractéristiques du code QR utilisées pour construire la méthode de localisation, ainsi qu'une brève description de la version originale de la méthode Viola et Jones.QR Code
Le QR code (abréviation de Quick Response Code) est un code-barres bidimensionnel qui a été développé au Japon au milieu des années 90 pour l'industrie automobile. En raison de sa capacité de lecture rapide et de sa capacité supérieure par rapport aux codes à barres linéaires, le système de code QR est devenu populaire dans le monde entier dans divers domaines de la vie.Contrairement aux codes-barres linéaires standard, qui sont généralement scannés par le matériel, un code QR est souvent scanné par une caméra. La structure du code QR est entièrement décrite dans ISO / IEC 18004 (La norme ISO / IEC 18004). Pour construire un algorithme de reconnaissance robuste pour de telles images, le code QR a des points de référence qui forment un modèle de fonction: trois carrés dans les coins de l'image du code à barres (appelés modèles de recherche) et des carrés de synchronisation plus petits dans toute l'image du code à barres (appelés modèles d'alignement) . Ces points vous permettent de normaliser la taille de l'image et son orientation.
Figure. Structure du code QR
Bien que visuellement tous les codes QR soient similaires les uns aux autres, différentes copies des codes QR, selon la quantité de données codées, peuvent avoir une disposition différente des éléments internes. En outre, les soi-disant codes QR de concepteur sont très populaires, dans lesquels au lieu de la partie d'informations supplémentaires qui garantit une reconnaissance de haute qualité du code à barres, des éléments graphiques tiers sont utilisés (logos, emblèmes, inscriptions, etc.). Toutes ces caractéristiques des codes QR doivent être prises en compte lors de la construction de méthodes de localisation et de reconnaissance de codes QR.
Figure. Différentes options de code QR valides
Méthode Viola et Jones
Seuls les paresseux sur Habré n'ont pas encore écrit sur la méthode de Viola et Jones. Même nous dans notre bloc l'avons fait plusieurs fois (par exemple, ici , ici ou ici ). Et pourtant, nous estimons nécessaire de dire très brièvement, littéralement en deux paragraphes, ce que c'est.La méthode de détection d'objets Viola et Jones a été développée pour rechercher des visages dans une image en temps réel. Cette méthode réduit le problème de détection au problème de classification binaire à chaque point d'image, c'est-à-dire que pour chaque région d'image rectangulaire prise avec toutes sortes de décalages et d'échelles, l'hypothèse de la présence de l'objet souhaité dans la région est vérifiée à l'aide d'un classificateur pré-formé.En tant qu'espace d'entité, la méthode Viola et Jones utilise des entités rectangulaires de Haar, dont la valeur est calculée comme la différence entre les sommes de luminosité des pixels des zones d'image à l'intérieur des rectangles adjacents. Pour calculer efficacement la valeur des caractéristiques de Haar, une image intégrée est utilisée, qui est également connue dans la littérature sous le terme table de surface sommée. Un classificateur binaire «faible» h ( x ): Χ → {-1, + 1}, généralement présenté comme un arbre de reconnaissance à une branche:
où θ et p- la valeur seuil de l'attribut et la parité du classificateur, respectivement. Ensuite, en utilisant la méthode d'apprentissage automatique AdaBoost, un classificateur «fort» est construit comme une superposition linéaire des classificateurs «faibles» ci-dessus. La vitesse élevée de la méthode Viola et Jones est assurée par l'utilisation d'une cascade de classificateurs «forts», qui permet de localiser des régions d'image «vides» (sans objet) dans un petit nombre de calculs.Algorithme de détection de code QR
Lors de la construction d'une méthode de localisation d'un code QR, nous nous sommes appuyés sur les fonctionnalités suivantes de la tâche. Premièrement, la méthode développée doit avoir des performances élevées pour une utilisation dans des systèmes de reconnaissance fonctionnant en temps réel. Deuxièmement, la méthode doit être résistante à la distorsion admissible du code-barres dans l'image. Troisièmement, la méthode devrait prendre en compte toute la variabilité existante des codes QR.Comme mentionné ci-dessus, nous avons choisi la méthode de Viola et Jones comme méthode fondamentale. Cette méthode a fait ses preuves dans diverses tâches de recherche d'objets rigides, tandis que la méthode fournit les performances requises. Mais dans la version originale, la méthode Viola et Jones ne peut pas être utilisée pour les raisons suivantes:- la méthode classique de Viola et Jones utilise une famille d'attributs Haar qui «soulignent» les caractéristiques de texture de l'objet, et dans notre cas, bien que le code QR soit composé de barcels noir et blanc, leur distribution est très différente du code-barres au code-barres;
- la méthode classique de Viola et Jones est conçue pour le même type de détection d'objets dans une orientation donnée, ce qui n'est pas non plus observé dans notre tâche.
Pour que la méthode de Viola et Jones puisse être appliquée pour résoudre le problème, nous utilisons la famille d'origine d'entités limites et un classificateur de haut niveau sous la forme d'un arbre de décision. La première modification permettra de se concentrer sur les traits limites de l'objet étudié, et non sur la texture. La deuxième modification vous permettra de construire un classificateur unique capable de détecter des objets variables. Ensuite, nous vous en dirons un peu plus sur chaque modification.Signes dégradés de Haar.
Pour construire un détecteur efficace de codes QR, nous avons utilisé une famille spéciale de caractéristiques de gradient [1]. Ces panneaux sont des panneaux rectangulaires de Haar, calculés en haut de la carte des limites dirigées, ce qui peut considérablement améliorer leur pouvoir de généralisation.La carte des limites directionnelles est une image du module de gradient, qui prend en outre en compte la direction préférée du gradient au point ( x , y ), définie comme la discrétisation de l'angle de la frontière dans les directions horizontale, verticale, + 45 ° et –45 °. Pour construire un détecteur de code QR, nous avons utilisé deux types de carte des limites directionnelles: une carte des limites droite et une carte des faces diagonales.Soit l'image d'origine f ( x ,y ). Ensuite, vous pouvez calculer la valeur approximative de la dérivée le long des directions horizontale et verticale à l'aide de l'opérateur Sobel:
De plus, en utilisant g x et g y , vous pouvez calculer la direction du dégradé à chaque point de l'image: La
carte des bordures droites contient principalement des bordures horizontales et verticales et est calculée comme suit:
Carte les bordures diagonales contiennent principalement des bordures le long des diagonales et sont calculées comme suit:
En plus de la carte construite des bordures dirigées (diagonales ou droites), des panneaux de Haar rectangulaires sont calculés. Contrairement aux entités Haar classiques, ces entités frontières généralisent bien les objets contenant un grand nombre de frontières.
Figure. Illustration d'une carte des frontières directionnelles: (a) l'image originale d'un code QR, (b) une carte des frontières droites, (c) une image d'un code QR tourné (d) une carte des frontières diagonales d'un code QR tourné
L'arbre décisif des classificateurs forts
L'arbre des classificateurs forts [2] est une sorte d'arbre de décision binaire: le nœud d'arbre est un classificateur fort, sur le bord droit duquel se trouvent des sous-fenêtres contenant vraisemblablement l'objet et sur la gauche - celles qui n'ont pas été reconnues comme un objet, respectivement. La réponse finale n'est donnée que dans les feuilles. Le classificateur classique en cascade décrit dans les travaux originaux de Viola et Jones est, en fait, un classificateur d'arbre contenant une seule sortie «positive» (feuille) et de nombreuses sorties «négatives».Dans [2], il est montré que tout chemin de la racine au nœud le plus bas du classificateur d'arbre peut être représenté comme une cascade dans laquelle les classificateurs forts individuels entrent avec une réponse inversée. Grâce à cela, il est possible de construire un algorithme d'apprentissage pour le classificateur d'arbre, qui utilise la procédure de formation du classificateur en cascade classique pour enseigner les chemins individuels.Le classificateur d'arborescence vous permet de former des classificateurs plus efficaces en termes d'exhaustivité pour les objets variables par rapport aux classificateurs en cascade classiques.Résultats expérimentaux
Dans le cadre d'une expérience visant à évaluer l'efficacité de la méthode de localisation de codes à barres proposée dans cet article, un ensemble d'images de codes à barres composé de 264 images a été préparé. La taille physique des images était d'environ 1 MPix. Chaque image contient un seul code QR dans une orientation arbitraire, la zone du code à barres représentait au moins 10% de la zone d'image totale. La figure ci-dessous montre des exemples d'images de l'ensemble assemblé.
Figure. Exemples d'images de l'ensemble d'images de codes à barres assemblé
L'ensemble d'images préparé a été divisé en un ensemble de formation et un ensemble de test. La taille de l'échantillon d'apprentissage était de 88 images, la taille de l'échantillon d'essai était de 176 images.L'ensemble de formation a été utilisé à la fois pour préparer des exemples positifs et pour préparer des exemples négatifs. Le nombre initial d'exemples positifs étant faible, nous avons utilisé la technologie d'augmentation des données [3]. En particulier, nous avons appliqué une rotation autour du centre du code-barres par incréments de 15⁰. Après augmentation, le nombre d'exemples positifs était de 2088 exemples.En utilisant les mêmes exemples positifs et négatifs, nous avons formé trois détecteurs de code QR: un classificateur en cascade classique avec des caractéristiques Haar standard, un classificateur en cascade classique avec des caractéristiques limites et un classificateur d'arbre avec des caractéristiques limites. Le premier classificateur en cascade comprenait 12 niveaux et contenait un total de 58 attributs. Le deuxième classificateur en cascade se composait de 8 niveaux et contenait un total de 39 attributs. Le classificateur d'arbre formé se composait de 39 sommets, contenait un total de 110 caractères, et le chemin maximal du haut vers la feuille était de 9. Ci-dessous est un diagramme du classificateur d'arbre formé.
Figure. Schéma du classificateur d'arbres formé
Pour évaluer la qualité des détecteurs de code QR construits, nous avons utilisé le module de décodage de codes à barres de la bibliothèque de vision par ordinateur open source OpenCV. Sur l'ensemble d'images de test préparé (qui, comme mentionné ci-dessus, comprenait 176 images), nous avons lancé le module de décodage sans prétraitement spécial, ainsi qu'après une recherche préliminaire de codes QR à l'aide de détecteurs formés. Voici les résultats du décodage des codes à barres:Le tableau montre que la localisation préliminaire du code QR à l'aide de la méthode décrite peut améliorer considérablement la qualité du décodage des codes à barres (le nombre d'erreurs de décodage a diminué de 44%). De plus, les résultats démontrent également que l'application de la méthode originale de Viola et Jones (avec les caractéristiques Haar classiques et un classificateur en cascade) n'est pas efficace dans la tâche de localisation des codes QR.Voyons maintenant avec quelle précision chaque classificateur localise le code-barres. La figure de gauche à droite montre les résultats de la détection du même code-barres avec un classificateur en cascade classique avec des caractéristiques Haar standard, un classificateur en cascade classique avec des caractéristiques de limite et un classificateur d'arbre avec des caractéristiques de limite. On peut voir que le classificateur d'arbre fournit la meilleure précision de localisation de code à barres en tenant compte de la variabilité des codes QR.
Figure. Illustration du travail de détecteurs formés sur la même image
Conclusion
Aujourd'hui, les codes QR sont utilisés dans divers domaines de la vie: dans le secteur de la publicité pour l'encodage d'URL, dans le segment de l'État dans le cadre des services électroniques, etc. Malgré la distribution extrêmement élevée de ces codes-barres, les bibliothèques open source existantes se concentrent sur le processus de décodage, pas sur le problème de localisation. Mais pour être honnête, le véritable objectif de cet article n'était pas tant de décrire une méthode efficace de localisation de codes QR, mais plutôt de vous dire, cher lecteur, comment, en utilisant la pensée scientifique et l'analyse du système, en comprenant comment utiliser les outils classiques de traitement d'image numérique, vous pouvez libérer les bibliothèques amènent au niveau industriel actuel. Merci pour l'attention.Liste des sources utilisées[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.