Berichte aus der PraxisFarbbarcode mit hoher Kapazität

Gavin Jancke

Wir alle sind mit Barcodes so vertraut, dass wir sie oft nicht einmal bemerken. Sie sind im Alltag allgegenwärtig – auf Lebensmittelverpackungen bis hin zu Adressetiketten. Die ursprünglichen 1D-Barcodes, die 1974 in der Einzelhandelsbranche auftauchten, bestanden aus senkrechten Strichen unterschiedlicher Breite und speicherten eine 12-stellige Zahl. Die Barcodes entwickelten sich mit zunehmender Rechenleistung, und gegen Ende der 80er Jahre wurden Schwarzweiß-2D-Barcodes (Matrixcodes) entwickelt, die die Datendichte von ein paar Zahlen auf einige hundert Bytes erhöhten.

2003 begann ich mit der Arbeit an einem fälschungssicheren, biometrischen Ausweis, wobei es sich um ein Projekt für Microsoft Research handelte. Ich musste nicht nur den kryptografischen Text wie Namen und Alter speichern, sondern auch Fingerabdruck- oder Netzhautscanvorlagen. Um alle notwendigen Daten speichern zu können, hätte der existierende Schwarzweißbarcode größer als der Ausweis selbst sein müssen, sodass ein neuer Ansatz erforderlich war.

Ich musste festlegen, wie mehr als ein Bit an Informationen pro Symbol gespeichert werden konnten, was der Standard für Schwarzweiß-2D-Barcodes gewesen war. Durch die Verwendung von Farben statt Schwarz und Weiß konnte ich dies mithilfe von vier bzw. acht Farben auf zwei bis drei Bit an Daten erhöhen.

Ich experimentierte auch mit den Symbolformen, um festzustellen, ob sie dichter zusammengepackt werden konnten, ohne dass ihre Erfassung beim Scannen beeinträchtigt wurde. Anfänglich schienen Sechsecke eine gute Möglichkeit, aber die Formen verschmolzen miteinander, und der Computer konnte sie nicht deutlich genug wahrnehmen.

Schließlich entschied ich mich für Dreiecke, da sie sich in einem komprimierten Raum ordentlich schneiden, aber gleichzeitig ihre Identität als eindeutige Formen bewahren. Durch die Verwendung von Zeilen von Dreiecken in mehreren Farben konnte ich die Dichtheitsfunktion auf 3D erweitern.

Es galt viele Variable zu beachten. Eine der größten Herausforderungen bei der Arbeit mit Farbe ist die Abweichung in Druckspezifikationen und bei unterschiedlichen Beleuchtungsbedingungen. Obwohl Farbe für das menschliche Auge leicht erkennbar ist (zumindest für diejenigen, die nicht farbenblind sind), ist sie für einen Computer nicht so deutlich erkennbar.

Ich verwendete mehrere verschiedene Ansätze, um sicherzustellen, dass die Software die Farbe genau lesen konnte. Ich erstellte eine sehr kleine, fast nicht wahrnehmbare Palette innerhalb des Badcodes, die die Referenzfarben für die im eigentlichen Barcode vorhandenen Farben enthielt. Auf diese Weise wurde eine Kalibrierungsmethode bereitgestellt, die genau angab, wie beispielsweise ein bestimmtes Rot aussieht. Ich probierte auch komplexere Verfahren wie beispielsweise angepasste, einfache Farbclusteringalgorithmen aus, die die Farbbereichstheorie nutzen, um Farben in Sätzen zu kategorisieren. Beide Ansätze funktionieren gleichermaßen gut und ergänzen einander.

Eines meiner Ziele bei diesem Projekt bestand im Schreiben eines Programms, das Handys das Lesen von Barcodes ermöglichen würde. Bei Handys müssen Dinge wie schlechte Beleuchtung und nicht fokussierte Objektive mit fester Brennweite in Betracht gezogen werden. Eine weitere Herausforderung bestand darin, das gesamte Computersehvermögen auf ganzzahlbasierten, relativ langsamen Handy-CPUs umzusetzen, sodass das Team eine Theorie entwickeln musste, mit der der Barcode im Bild erkannt werden kann, wobei möglichst wenige Pixel berührt werden. Der Scan musste innerhalb eines Bereichs von Lesebedingungen arbeiten, von hellen, scharf eingestellten LCD-Monitoren bis hin zu verschwommenen physischen Drucken bei geringerer Beleuchtung.

Der fertige Algorithmus decodiert Barcodebilder in Echtzeit-Kameravideoframes schneller als die eigentliche Framerate (ungefähr 10 Millisekunden bei einer 200-MHz-CPU). In einem Bild beträgt die kleinste Zahl von Pixeln, die ein Barcode für die kleinste Datennutzlast verwenden kann, die immer noch erkannt wird, etwa 45 Pixel im Quadrat.

Es waren mehr als zwei Jahre Entwicklungsarbeit erforderlich, damit dies unter verschiedenen Bedingungen funktionierte. Diese Technologie wurde Drittanbietern kürzlich unter Lizenz zur Verfügung gestellt, und später in diesem Jahr wird es einige interessante Anwendungen geben.

Gavin Jancke, Director of Engineering für Microsoft Research, leitet die Advanced Development Group- und Web Experience-Teams. Zuvor war er als Product Support Engineer und Software Engineer für SQL Server tätig und war Mitglied des technischen Beraterstabs von Bill Gates.