Wir sind sicher, dass es heute keinen einzigen Habr-Leser gibt, der mit QR-Codes nicht vertraut wĂ€re. Diese zweidimensionalen Barcodes sind ĂŒberall. Es ist logisch, dass es weltweit viele Tools gibt, mit denen Sie Ihrem Projekt QR-Codes mit einem gewissen Grad an Effizienz hinzufĂŒgen können. Der springende Punkt ist, dass diese erwĂ€hnte Effizienz direkt von der QualitĂ€t des Werkzeugs abhĂ€ngt, mit dem QR-Codes erkannt werden. Und hier kommt der klassische Stecker: Sie können das Problem (sehr) gut und (sehr) teuer lösen, oder Sie können es kostenlos und irgendwie. Ist es möglich, das freie so zu modifizieren, dass es das Problem trotzdem gut löst? Bei Interesse unter die Katze schauen.Das Erkennen eines QR-Codes auf einem Foto ist eine gut gestellte Aufgabe der Bildverarbeitung. ZunĂ€chst wird in der Aufgabe ein Objekt untersucht, das ursprĂŒnglich speziell fĂŒr die âbequemeâ Erkennung entwickelt wurde. Zweitens ist die Aufgabe selbst in mehrere unabhĂ€ngige verstĂ€ndliche Unteraufgaben unterteilt: Lokalisierung des QR-Codes, Ausrichtung des QR-Codes und direkte Dekodierung des QR-Codes. Es stellte sich heraus, dass die Public Domain seit langem gute Bibliotheken hat, die die letzten beiden Probleme lösen können: Orientierung und Dekodierung eines QR-Codes. Ein Problem: FĂŒr eine qualitativ hochwertige Decodierung erwarten solche Bibliotheken, dass ein gutes BinĂ€rbild direkt vom Barcode eingegeben wird. Umgekehrt wird der Aufgabe der Barcode-Lokalisierung im Bild wenig Aufmerksamkeit geschenkt.Nach unserer Erfahrung ist es umso einfacher, die richtigen Vorverarbeitungswerkzeuge auszuwĂ€hlen und tatsĂ€chlich zu erkennen, je genauer Sie ein Erkennungsobjekt lokalisieren. Wenn Sie daher die QualitĂ€t der Erkennung von QR-Codes in Ihrem Projekt verbessern möchten, beginnen Sie mit der Modernisierung der Methoden zur Lokalisierung von QR-Codes. Selbst wenn Sie spĂ€ter ein Bild binĂ€risieren mĂŒssen, ist es viel effizienter (sowohl aus rechnerischer als auch aus qualitativer Sicht), eine Region mit einem Barcode zu binarisieren als das gesamte Originalbild.In diesem Artikel erfahren Sie, wie Sie die QualitĂ€t der Lokalisierung von QR-Codes mithilfe klassischer Bildverarbeitungsmethoden auf einfache Weise verbessern und numerische Merkmale fĂŒr die Wirksamkeit des vorgeschlagenen Algorithmus bereitstellen können.Wir werden ĂŒber die ursprĂŒngliche Art der Lokalisierung von QR-Codes auf Bildern sprechen, wobei die modifizierte Viola- und Jones-Methode als Grundlage dient.Hinweis zum Thema des Artikels
In diesem Abschnitt beschreiben wir die Hauptmerkmale des QR-Codes, die zum Erstellen der Lokalisierungsmethode verwendet werden, sowie eine kurze Beschreibung der Originalversion der Viola- und Jones-Methode.QR-Code
Der QR-Code (kurz fĂŒr Quick Response Code) ist ein zweidimensionaler Barcode, der Mitte der 90er Jahre in Japan fĂŒr die Automobilindustrie entwickelt wurde. Aufgrund der FĂ€higkeit zum schnellen Lesen und der gröĂeren KapazitĂ€t im Vergleich zu linearen Barcodes ist das QR-Code-System in verschiedenen Lebensbereichen weltweit beliebt geworden.Im Gegensatz zu linearen Standard-Barcodes, die normalerweise von Hardware gescannt werden, wird ein QR-Code hĂ€ufig von einer Kamera gescannt. Die Struktur des QR-Codes ist vollstĂ€ndig in ISO / IEC 18004 (ISO / IEC-Norm 18004) beschrieben. Um einen robusten Erkennungsalgorithmus fĂŒr solche Bilder zu erstellen, verfĂŒgt der QR-Code ĂŒber einige Referenzpunkte, die ein Funktionsmuster bilden: drei Quadrate in den Ecken des Barcode-Bildes (als Finder-Muster bezeichnet) und kleinere Synchronisationsquadrate im gesamten Barcode-Bild (als Ausrichtungsmuster bezeichnet). . Mit solchen Punkten können Sie die BildgröĂe und ihre Ausrichtung normalisieren.
Feige. QR-Code-Struktur
Obwohl visuell alle QR-Codes einander Ă€hnlich sind, können unterschiedliche Kopien von QR-Codes abhĂ€ngig von der Menge der codierten Daten ein unterschiedliches Layout der internen Elemente aufweisen. DarĂŒber hinaus sind die sogenannten Designer-QR-Codes sehr beliebt, bei denen anstelle des Teils zusĂ€tzlicher Informationen, die eine qualitativ hochwertige Erkennung des Barcodes gewĂ€hrleisten, grafische Elemente von Drittanbietern (Logos, Embleme, Inschriften usw.) verwendet werden. Alle diese Merkmale von QR-Codes mĂŒssen bei der Erstellung von Methoden zur Lokalisierung und Erkennung von QR-Codes berĂŒcksichtigt werden.
Feige. Verschiedene gĂŒltige QR-Code-Optionen
Viola und Jones Methode
Nur die Faulen auf HabrĂ© haben noch nicht ĂŒber die Methode von Viola und Jones geschrieben. Sogar wir in unserem Block haben dies mehrmals getan (zum Beispiel hier , hier oder hier ). Und dennoch halten wir es fĂŒr notwendig, sehr kurz, buchstĂ€blich in zwei AbsĂ€tzen, zu sagen, was es ist.Die Objekterkennungsmethode von Viola und Jones wurde entwickelt, um in Echtzeit in einem Bild nach Gesichtern zu suchen. Dieses Verfahren reduziert das Erfassungsproblem auf das binĂ€re Klassifizierungsproblem an jedem Bildpunkt, d. H. FĂŒr jeden rechteckigen Bildbereich, der mit allen Arten von Verschiebungen und Skalen aufgenommen wurde, wird die Hypothese des Vorhandenseins des gewĂŒnschten Objekts in dem Bereich unter Verwendung eines vorab trainierten Klassifizierers ĂŒberprĂŒft.Als Merkmalsraum verwendet die Viola- und Jones-Methode rechteckige Haar-Merkmale, deren Wert als Differenz zwischen den Helligkeitssummen der Pixel der Bildbereiche innerhalb benachbarter Rechtecke berechnet wird. Um den Wert von Haar-Merkmalen effektiv zu berechnen, wird ein integriertes Bild verwendet, das in der Literatur auch unter dem Begriff Summenbereichstabelle bekannt ist. Ein binĂ€rer "schwacher" Klassifikator h ( x ): Χ â {-1, + 1}, normalerweise als Erkennungsbaum mit einem Zweig dargestellt:
wobei Ξ und p- der Schwellenwert des Attributs bzw. die ParitĂ€t des Klassifikators. Als nĂ€chstes wird unter Verwendung der AdaBoost-Methode fĂŒr maschinelles Lernen ein "starker" Klassifikator als lineare Ăberlagerung der obigen "schwachen" Klassifikatoren konstruiert. Die hohe Geschwindigkeit der Viola- und Jones-Methode wird durch die Verwendung einer Kaskade von âstarkenâ Klassifizierern sichergestellt, die es ermöglicht, âleereâ (objektfreie) Bildbereiche in einer kleinen Anzahl von Berechnungen zu lokalisieren.QR-Code-Erkennungsalgorithmus
Bei der Erstellung einer Methode zum Lokalisieren eines QR-Codes haben wir uns auf die folgenden Funktionen der Aufgabe verlassen. Erstens muss die entwickelte Methode eine hohe Leistung fĂŒr die Verwendung in Erkennungssystemen aufweisen, die in Echtzeit arbeiten. Zweitens muss das Verfahren gegen zulĂ€ssige Verzerrungen des Barcodes im Bild bestĂ€ndig sein. Drittens sollte die Methode die gesamte vorhandene VariabilitĂ€t der QR-Codes berĂŒcksichtigen.Wie oben erwĂ€hnt, haben wir die Methode von Viola und Jones als grundlegende Methode gewĂ€hlt. Diese Methode hat sich bei verschiedenen Aufgaben der Suche nach starren Objekten bewĂ€hrt, wĂ€hrend die Methode die erforderliche Leistung bietet. In der Originalversion kann die Viola- und Jones-Methode jedoch aus folgenden GrĂŒnden nicht verwendet werden:- Bei der klassischen Methode von Viola und Jones wird eine Familie von Haar-Attributen verwendet, die die Texturmerkmale des Objekts âhervorhebenâ. In unserem Fall unterscheidet sich ihre Verteilung vom Barcode zum Barcode stark, obwohl der QR-Code aus schwarzen und weiĂen Strichcodes besteht.
- Die klassische Viola- und Jones-Methode ist fĂŒr die gleiche Art der Erkennung von Objekten in einer bestimmten Ausrichtung ausgelegt, die auch in unserer Aufgabe nicht beobachtet wird.
Damit die Viola- und Jones-Methode zur Lösung des Problems angewendet werden kann, verwenden wir die ursprĂŒngliche Familie von Grenzmerkmalen und einen ĂŒbergeordneten Klassifikator in Form eines Entscheidungsbaums. Die erste Modifikation ermöglicht es, sich auf die Grenzmerkmale des untersuchten Objekts und nicht auf die Textur zu konzentrieren. Mit der zweiten Ănderung können Sie einen einzelnen Klassifizierer erstellen, der variable Objekte erkennen kann. Als nĂ€chstes werden wir Ihnen etwas mehr ĂŒber jede Ănderung erzĂ€hlen.Gradientenzeichen von Haar.
Um einen effektiven Detektor fĂŒr QR-Codes zu erstellen, haben wir eine spezielle Familie von Gradientenmerkmalen verwendet [1]. Diese Zeichen sind Haar-Rechteckzeichen, die ĂŒber der Karte der gerichteten Grenzen berechnet werden und deren Generalisierungskraft erheblich verbessern können.Die Karte der Richtungsgrenzen ist ein Bild des Gradientenmoduls, das zusĂ€tzlich die Vorzugsrichtung des Gradienten am Punkt ( x , y ) berĂŒcksichtigt , definiert als Diskretisierung des Randwinkels in horizontale, vertikale, + 45 ° - und â45 ° -Richtungen. Um einen QR-Code-Detektor zu erstellen, haben wir zwei Arten von Richtungsgrenzkarten verwendet: eine gerade Grenzkarte und eine diagonale FlĂ€chenkarte.Lassen Sie das Originalbild f ( x ,y ). AnschlieĂend können Sie den ungefĂ€hren Wert der Ableitung entlang der horizontalen und vertikalen Richtung mit dem Sobel-Operator berechnen :
ZusÀtzlich können Sie mit g x und g y die Richtung des Verlaufs an jedem Punkt des Bildes berechnen: Die
Karte der geraden RÀnder enthÀlt hauptsÀchlich horizontale und vertikale RÀnder und wird wie folgt berechnet:
Karte Diagonale RÀnder enthalten hauptsÀchlich RÀnder entlang der Diagonalen und werden wie folgt berechnet:
Auf der konstruierten Karte der gerichteten RĂ€nder (diagonal oder gerade) werden rechteckige Haarzeichen berechnet. Im Gegensatz zu den klassischen Haar-Merkmalen verallgemeinern solche Grenzmerkmale Brunnenobjekte, die eine groĂe Anzahl von Grenzen enthalten.
Feige. Darstellung einer Karte gerichteter RĂ€nder: (a) das Originalbild eines QR-Codes, (b) eine Karte gerader RĂ€nder, (c) ein Bild eines gedrehten QR-Codes (d) eine Karte der diagonalen RĂ€nder eines gedrehten QR-Codes
Der entscheidende Baum starker Klassifikatoren
Der Baum der starken Klassifizierer [2] ist eine Art binĂ€rer Entscheidungsbaum: Der Baumknoten ist ein starker Klassifizierer, an dessen rechtem Rand sich vermutlich Unterfenster befinden, die das Objekt enthalten, und am linken Rand diejenigen, die nicht als Objekt erkannt wurden. Die endgĂŒltige Antwort wird nur in BlĂ€ttern gegeben. Der klassische Kaskadenklassifikator, der in der Originalarbeit von Viola und Jones beschrieben wurde, ist in der Tat ein Baumklassifikator, der nur eine âpositiveâ Ausgabe (Blatt) und viele ânegativeâ Ausgaben enthĂ€lt.In [2] wird gezeigt, dass jeder Pfad von der Wurzel zum untersten Knoten des Baumklassifikators als eine Kaskade dargestellt werden kann, in die einzelne starke Klassifikatoren mit einer invertierten Antwort eintreten. Dank dessen ist es möglich, einen Lernalgorithmus fĂŒr den Baumklassifikator zu konstruieren, der das Trainingsverfahren des klassischen Kaskadenklassifikators verwendet, um einzelne Pfade zu lehren.Mit dem Baumklassifikator können Sie Klassifikatoren trainieren, die hinsichtlich der VollstĂ€ndigkeit fĂŒr variable Objekte im Vergleich zu klassischen Kaskadenklassifikatoren effektiver sind.Experimentelle Ergebnisse
Im Rahmen eines Experiments zur Bewertung der Wirksamkeit der in diesem Artikel vorgeschlagenen Barcode-Lokalisierungsmethode wurde ein Satz von Barcode-Bildern aus 264 Bildern erstellt. Die physikalische GröĂe der Bilder betrug etwa 1 MPix. Jedes Bild enthĂ€lt nur einen QR-Code in beliebiger Ausrichtung, der Barcode-Bereich betrug mindestens 10% des gesamten Bildbereichs. Die folgende Abbildung zeigt Beispiele fĂŒr Bilder aus dem zusammengesetzten Set.
Feige. Beispiele fĂŒr Bilder aus dem zusammengestellten Barcode-Bildsatz
Der vorbereitete Satz von Bildern wurde in einen Trainingssatz und einen Testsatz unterteilt. Die GröĂe der Trainingsprobe betrug 88 Bilder, die GröĂe der Testprobe betrug 176 Bilder.Das Trainingsset wurde sowohl zur Vorbereitung positiver als auch zur Vorbereitung negativer Beispiele verwendet. Da die anfĂ€ngliche Anzahl positiver Beispiele gering war, verwendeten wir die Datenerweiterungstechnologie [3]. Insbesondere haben wir die Drehung um die Mitte des Barcodes in Schritten von 15 ° angewendet. Nach der Augmentation betrug die Anzahl der positiven Beispiele 2088 Beispiele.Anhand der gleichen positiven und negativen Beispiele haben wir drei QR-Code-Detektoren trainiert: einen klassischen Kaskadenklassifikator mit Standard-Haar-Merkmalen, einen klassischen Kaskadenklassifikator mit Grenzmerkmalen und einen Baumklassifikator mit Grenzmerkmalen. Der erste Kaskadenklassifikator bestand aus 12 Ebenen und enthielt insgesamt 58 Attribute. Der zweite Kaskadenklassifikator bestand aus 8 Ebenen und enthielt insgesamt 39 Attribute. Der trainierte Baumklassifikator bestand aus 39 Eckpunkten, enthielt insgesamt 110 Zeichen und der maximale Pfad von oben zum Blatt betrug 9. Unten sehen Sie ein Diagramm des trainierten Baumklassifikators.
Feige. Schema des trainierten Baumklassifikators
Um die QualitĂ€t der konstruierten QR-Code-Detektoren zu beurteilen, verwendeten wir das Barcode-Decodierungsmodul aus der OpenCV-Open-Source-Computer-Vision-Bibliothek. Auf dem vorbereiteten Testsatz von Bildern (der, wie oben erwĂ€hnt, aus 176 Bildern bestand) haben wir das Decodierungsmodul ohne spezielle Vorverarbeitung sowie nach einer vorlĂ€ufigen Suche nach QR-Codes unter Verwendung geschulter Detektoren gestartet. Nachfolgend sind die Ergebnisse der Barcode-Dekodierung aufgefĂŒhrt:Die Tabelle zeigt, dass die vorlĂ€ufige Lokalisierung des QR-Codes unter Verwendung des beschriebenen Verfahrens die QualitĂ€t der Barcode-Decodierung erheblich verbessern kann (die Anzahl der Decodierungsfehler verringerte sich um 44%). DarĂŒber hinaus zeigen die Ergebnisse auch, dass die Anwendung der ursprĂŒnglichen Viola- und Jones-Methode (mit klassischen Haar-Merkmalen und einem kaskadierenden Klassifikator) bei der Lokalisierung von QR-Codes nicht effektiv ist.Nun wollen wir sehen, wie genau jeder Klassifikator den Barcode lokalisiert. Die Abbildung von links nach rechts zeigt die Ergebnisse der Erkennung desselben Barcodes mit einem klassischen Kaskadenklassifikator mit Standard-Haar-Merkmalen, einem klassischen Kaskadenklassifikator mit Grenzmerkmalen und einem Baumklassifikator mit Grenzmerkmalen. Es ist ersichtlich, dass der Baumklassifizierer die beste Genauigkeit der Barcode-Lokalisierung bietet, indem er die VariabilitĂ€t von QR-Codes berĂŒcksichtigt.
Feige. Illustration der Arbeit von geschulten Detektoren auf dem gleichen Bild
Fazit
Heutzutage werden QR-Codes in verschiedenen Lebensbereichen verwendet: in der Werbebranche zum Codieren von URLs, im staatlichen Segment als Teil elektronischer Dienste usw. Trotz der extrem hohen Verbreitung solcher Barcodes konzentrieren sich die vorhandenen Open Source-Bibliotheken auf den Decodierungsprozess und nicht auf das Lokalisierungsproblem. Um ehrlich zu sein, bestand der wahre Zweck dieses Artikels nicht darin, eine effektive Methode zur Lokalisierung von QR-Codes zu beschreiben, sondern vielmehr darin, Ihnen, lieber Leser, zu erklĂ€ren, wie Sie mithilfe von wissenschaftlichem Denken und Systemanalyse verstehen, wie Sie mit klassischen digitalen Bildverarbeitungswerkzeugen umgehen können Bibliotheken bringen auf das eigentliche industrielle Niveau. Vielen Dank fĂŒr Ihre Aufmerksamkeit.Liste der verwendeten Quellen[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.