OCR, Barcodes - Wie fängt man an?

[Prototypjack]

Moin,

Kurz zu meinem Vorhaben, damit mit mir nachher keiner nachsagt ich würde hier Captchas lesen wollen oder etwas ähnliches. Was ich vorhabe ist folgendes: Ich will mittels Photos Barcodes auf bestimmten Dingen (vorzugsweise CDs, DVDs, Bücher, etc.) erkennen und auslesen. Was die Interpretation der Codes anbelangt, werde ich vorerst nur EAN implementieren, aber darum geht es mir jetzt noch nicht.

Mein Problem ist folgendes: Ich habe keine Ahnung wie ich da anfangen soll. Gibt es irgendwelche Denkansätze / Techniken, die das Auslesen erleichtern bzw. ermöglichen?

Ich bin momentan so weit, dass ich das Bild (in Farbe) umrechne auf Schwarz & Weiß (keine Graustufen, also lediglich 255, 255, 255 bzw. 0, 0, 0!). Dadurch kann ich den Barcode gut von Störungen (durch das Scannen der Kamera bzw. des Scanners) befreien. Jetzt müsste ich irgendwie das Rechteck mit dem Barcode identifizieren können und dann muss ich den Code irgendwie lesen. Bei beidem kommt noch erschwerend hinzu, dass der Code sehr wohl gedreht sein kann.

Könnt ihr mir ein paar Ansätze geben?

Danke & Grüße,
Max

[sx2008]

Stell dir vor, du nimmst einen "Lesestrahl" (Bruder des Laserstrahls) und führst ihn quer über dein Bild.
Jedes Pixel wird ausgelesen, und die Information Hell oder Dunkel einem Helligkeitsarray abgelegt.
Dann wird diese Array analysiert und versucht, daraus die einzelnen Symbole eines Barcodes zu gewinnen.
Das war der grobe Ablauf.

Jetzt zum Auslesen der Pixel:
du brauchst dazu den Bresenham-Algorithmus.
Pro Bild würde ich mehrere Schnitte in Winkeln 0, 15, 30, 45, 60, 75, 90 machen.
Die Schnittlinien sollten nicht nur durch den Bildmittelpunkt gehen, sondern jeweils nochmal "links" und "rechts" deneben.
Am leichtesten findet man die geeingneten Schnittlinien mit Papier, Lineal und Bleistift.

Jeder Schnitt erzeugt ein Array mit Schwarz/weiss Werten.
Das Array wird nun verdichtet.
Man zählt die Anzahl der gleichen Bit und schreibt die Werte in ein neues Timing-Array.
Beispiel:

Code:

Helligkeitsarray:
111111000011111111100000000001101

6|4|9|10|2|1|1

Das untere Array is so zu verstehen 6 Mal Hell, 4 Mal dunkel,....
Es beginnt und endet immer mit Farbe Weiss.

Das Timing-Array wird sowohl vorwärts als auch rückwärts ausgewertet (Funktion ReverseArray() schreiben)
und versucht daraus einen Barcode zu extrahieren.

Du siehst, du hast einen ganz weiten Weg vor dir.
Das frühe Wandeln in ein Schwarz/Weiss Bild ist übrigens eher ungünstig -
besser man trifft die Entscheidung ob ein Punkt Schwarz oder Weiss ist entlang der Schnittlinie.
Dazu sollte man im Helligkeitsarray nicht Schwarz und Weiss, sondern den Graustufenwert ablegen.

[Prototypjack]

Moin,

Ok, es kann natürlich sein, dass ich dich falsch verstanden habe, aber ich denke deine Methode arbeitet eher dann günstig, wenn nur der Barcode auf dem Bild zu sehen ist, aber bei mir ist da ja noch wesentlich mehr (Teile des Covers, etc.) zu sehen. Dies erschwert aber dann im Timing-Array das finden des Barcodes.

Ich werde diese Methode auf jeden Fall implementieren und damit herumexperimentieren, aber wäre es nicht günstiger, wenn ich erst einmal das Rechteck, in welchem sich der Barcode befindet, finde?

Grüße,
Max

[BenjaminH]

Hallo,
ich hab da eine kleine Idee.
Vorraussetzung dafür ist, dass der Barcode das größte zusammenhängende Objekt, das zu sehen ist, ist.
Dann nehme ich das Bild und lasse es(in Schwarz-Weiß) immer unschärfer werden. Bis alles, was nahe beieinander gelegen ist(Barcodestriche) zusammen zu einem schwarzen Rechteck wird. Jetzt suchst du das größte schwarze Rechteck(darf ja auch gedreht sein) heraus und hast die Position des Barcodes. Das kopierst du dann aus dem Original Bild in ein neues und nimmst dabei die Drehung vor. Barcodes sind im Normalfall ja auch um 180° gedreht lesbar.

Einfacher wäre das ganze natürlich, wenn du statt zu fotographieren einen Barcodescanner nimmst. Sind bei Conrad auch recht billig.

Viele Grüße,
Benjamin

[Medium]

Die Hough Transformation könnte hier auch recht hilfreich werden.

[Prototypjack]

Zitat:

Zitat von BenjaminH

Hallo,
ich hab da eine kleine Idee.
Vorraussetzung dafür ist, dass der Barcode das größte zusammenhängende Objekt, das zu sehen ist, ist.
Dann nehme ich das Bild und lasse es(in Schwarz-Weiß) immer unschärfer werden. Bis alles, was nahe beieinander gelegen ist(Barcodestriche) zusammen zu einem schwarzen Rechteck wird. Jetzt suchst du das größte schwarze Rechteck(darf ja auch gedreht sein) heraus und hast die Position des Barcodes. Das kopierst du dann aus dem Original Bild in ein neues und nimmst dabei die Drehung vor. Barcodes sind im Normalfall ja auch um 180° gedreht lesbar.

Einfacher wäre das ganze natürlich, wenn du statt zu fotographieren einen Barcodescanner nimmst. Sind bei Conrad auch recht billig.

Viele Grüße,
Benjamin

Die Voraussetzungen sind aber leider fast nie gegeben. Alleine bei meinen zwei Beispielen, die ich hier habe (PC-Spiele), sehen die Kästen mit den Systemvoraussetzungen genauso aus, wie das vom Barcode, ganz zu schweigen von störenden Hintergrundbildern etc. In der Tat ist bei meinem Beispiel der Hintergrund bis auf die Kästen mit Voraussetzungen und Barcode und wenige andere Stelle komplett schwarz, was noch erschwerend hinzukommen dürfte.
Außerdem gibt es bei der Methode an sich bereits ein Problem: Das Verwischen tut nämlich genau das, was es tun soll: Verwischen. Ich bin mir fast zu 100% sicher, dass gerade durch dieses Verwischen der Grenzen eine genaue Feststellung der Position unmöglich wird, wodurch das Problem nur unzufriedenstellend gelöst werden kann.
Ach ja, schlussendlich stellt sich immer noch ein Problem: Angenommen das Verwischen funktioniert, wie stellst du dann die Position des größten schwarzen Rechtecks fest?

Bezüglich der Drehung gibt es auch noch etwas zu sagen: Natürlich sind Barcodes (bis auf die Start- und Stoppcodes, die länger sind, wenn ich nicht falsch liege) beidseitig lesbar, aber das ist ja auch nicht das Problem. Ich fürchte eher, dass mir gerade 10° Drehungen (und Ähnliche) ein Ei legen (und solche Winkel dürften bei Photos relativ häufig vorkommen).

Grüße,
Max

[BenjaminH]

Erscheinen die Barcodes auf allen Fotos gleich groß?
Wegen der Drehung:
Wenn du die Position einmal hast, dann findest du ja leicht heraus, welches die längere Seite ist und um wieviel sie von der horizontalen Abweicht. Dann sollte eine Drehung ja leicht möglich sein.(Soweit ich mich erinnere gibt es sowas auch in der CL).

[Prototypjack]

Zitat:

Zitat von BenjaminH

Erscheinen die Barcodes auf allen Fotos gleich groß?
Wegen der Drehung:
Wenn du die Position einmal hast, dann findest du ja leicht heraus, welches die längere Seite ist und um wieviel sie von der horizontalen Abweicht. Dann sollte eine Drehung ja leicht möglich sein.(Soweit ich mich erinnere gibt es sowas auch in der CL).

Wegen der Größe: Leider nein. Nicht einmal im Verhältnis, da es scheinbar auch dünnere (also kürzere) Version des Barcodes-Kästchens gibt. Konstant dieselbe Größe ist sowieso nicht möglich, da ich im Endeffekt ein Buch, dass vor eine Webcam gehalten wird, erkennen will und dieses wird mal näher und mal weniger nah sein.

Zu letzterem: Stimmt, so dürfte das gehen, danke für den Ansatz ;). Aber ich knabbere immer noch an dem Eingrenz bzw. Findungs-Problem.

Grüße,
Max

[Aphton]

Evt. hilft dir das hier weiter
Diplomarbeit von Tobias Hermann (OCR)

MfG

[sx2008]

Zitat:

Zitat von Prototypjack

aber wäre es nicht günstiger, wenn ich erst einmal das Rechteck, in welchem sich der Barcode befindet, finde?

Nein, ein Barcode hat gegenüber dem störenden Rest so eine eindeutige Signatur, dass sich dieser Aufwand meiner Meinung nach nicht lohnt.
Es gibt ja auch Laserscanner die ein Gitter aus schrägen Linien projezieren und nur mit dem empfangenen Helligkeitssignal arbeiten. (z.B. Scannerkassen im Supermarkt, Scanner im Paketverteilzentrum)
Die Erkennungsraten sind gut bis sehr gut, weil ein Barcode mehrmals gelesen wird und Fehler so minimiert werden.

[alzaimar]

Ein Barcode besteht aus einer bestimmten Kombination aus den Merkmalen
1. 'dünner Strich'
2. 'dicker Strich'
3. 'dünner Zwischenraum'
4. 'dicker Zwischenraum'

Manchmal gibt es nur eine Strichdicke, manchmal -glaube ich- auch drei. In jedem Fall sind die Toleranzen in den einzelnen Specs der Barcodes glasklar definiert.

Du benötigst also erstmal einen Bereich, der überhaupt eine Abfolge von dicken/dünnen Strichen/Zwischenräumen ist, die alle eben konstant (mehr oder weniger) dick bzw. dünn sind. Bei Code39 ist das Verhältnis z.B. 1:1,8 - 1:2,4. So, Du findest also etwas schwarzes der Länge 'X'. Dann muss darauf ein Zwischenraum der Länge 'X' oder 'X/2' folgen (immer mit einer Toleranz). Und danach muss wieder ein dunkler Bereich der Länge X bzw. X/2 folgen usw. Das ganze muss sich dann in der Vertikalen wiederholen, zur Not mit einem bestimmten Versatz (Barcode ist schräg). So ein Muster wäre ein Kandidat für einen Barcode. Natürlich ist die längsgestreifte Tapete dann auch ein Kandidat (oder ein Zaun), aber das sind ja nun mal senkrechte Striche...

Nimm Dir also eine Scanline und unterteile die Bitfolge in helle und dunkle Bereiche. Nehmen wir an, wir fangen immer mit einem hellen Bereich an (der kann ja ruhig 0 Pixel breit sein, wenn ganz links schon etwas schwarzes ist). Dann würde z.B. die Zahlen folge 0,10,5,20 bedeuten, das die Scanline erst 0 Pixel weiss, dann 10 Pixel schwarz, dann 5 Pixel weiss und zum Schluss wieder 20 Pixel weiss ist.

Ich kann mir gut vorstellen, das Du mit einer kleinen Heuristik durchaus relativ schnell brauchbare Resultate erzielen kannst.

[Medium]

Nur für den Fall dass der vergleichsweise kleine Beitrag übersehen wurde:

Zitat:

Zitat von Medium

Die Hough Transformation könnte hier auch recht hilfreich werden.

[alzaimar]

Hi Medium,
Du meinst, erst Geraden finden und die dann korrelieren/analysieren? Ein schöner analytischer Ansatz, der -ich denke mal- 100% in die richtige Richtung geht.

[Real-TTX]

Zitat:

Zitat von alzaimar

Ein Barcode besteht aus einer bestimmten Kombination aus den Merkmalen
1. 'dünner Strich'
2. 'dicker Strich'
3. 'dünner Zwischenraum'
4. 'dicker Zwischenraum'

.....

Muss man nur hoffen dass der Barcode kein HIBC oder ähnlicher ist... ;)

Gibt es bei Büchern oder CDs inzwischen schon HIBC Code? Wenn ja, würde ich am Kontrast nicht so viel drehen.... Nicht dass einer der "Pixel" durcheinander kommt von S auf W oder von W auf S ...

Gruß, Real-TTX

[alzaimar]

Zitat:

Zitat von Real-TTX

Zitat:

Zitat von alzaimar

Ein Barcode besteht aus einer bestimmten Kombination aus den Merkmalen
1. 'dünner Strich'
2. 'dicker Strich'
3. 'dünner Zwischenraum'
4. 'dicker Zwischenraum'

.....

Muss man nur hoffen dass der Barcode kein HIBC oder ähnlicher ist... ;)

Verstehe ich nicht. HIBC basiert auf Code39 und Code128 und die bestehen wiederum aus dicken und dünnen Strichen.

[Kalfany]

Du könntest auch versuchen mit Kantendetektion den Barcode zu finden.

[Alien_F]

nebenbei: HIBC ist keine Schriftart. Ich vermute mal, ihr meintet den CodablockCodablock.

Ist aber auch egal, da auf DVDs eh ausschließlich EAN13 zum Einsatz kommt. Die ISBN eines Buches kommt auch nur als EAN13 daher.

Ich hatte mal vor kurzem auf irgendeinem Luxus-Handy mit integrierter Kamera eine derartige Funktion ausprobiert. War letztlich nur eine nette Spielerei. Es war mir kaum möglich auch nur irgendeinen Code damit zu lesen.

Ein ehrgeiziges Projekt, wo viel Informatik bzgl. Bilderkennung reinfließen muss. Viel Erfolg :thumb:

[alzaimar]

Zitat:

Zitat von Alien_F

nebenbei: HIBC ist keine Schriftart. Ich vermute mal, ihr meintet den CodablockCodablock.

Wo steht das was von 'Schriftart'? HIBC ist -soweit ich das sehe- einfach eine Norm, um Informationen in direkt über/nebeneinanderliegenden Barcodes abzulegen.

EAN sollte aber machbar sein, auch ohne großartige Bilderkennung.

[Alien_F]

Joah, HIBC kann in verschiedenen Symbologien daher kommen, sei es Codablock, Code128, Datamatrix oder auch RFID. HIBC meint eher eine Datenstrukur.
(jetzt wird´s aber offtopic)

[Florian H]

Zitat:

Zitat von Alien_F

Ich hatte mal vor kurzem auf irgendeinem Luxus-Handy mit integrierter Kamera eine derartige Funktion ausprobiert. War letztlich nur eine nette Spielerei. Es war mir kaum möglich auch nur irgendeinen Code damit zu lesen.

Barcode-"Scanner" über die Handycam sind grad schwer in.
Nutze das bei meinem Handy sehr gern, weil es eben ungemein praktisch ist:
Im Laden scanne ich den Code von irgendeinem Produkt und sehe sofort alle relevanten Infos (oder Shops, wo's das günstiger gibt). Oder ich sehe hier am Rechner auf irgendeiner Webseite eine tolle App fürs Handy, fotografiere den dort abgebildeten (2D-) Barcode und hab die Download-URL auf dem Handy - ohne abtippen oder ähnliches.

Und das funktioniert bei mir auch sehr gut, weiß nicht, was du da für ein Modell hattest ...

[Spiderpig_GER_15]

Hi,

was hältst du von dieser Idee:

Du gehst das ganze Bild durch (das original Bild (=farbig)) und setzt in einem neuen Bild überall dort einen schwarzen Punkt wo ein besonders staker unterschied vom Nachbarpixel (schwarz weiß[evt. toleeranzgrenze?] zum nächsten ist.
Das bedeutet das neue Bild gibt nach dieser Bearbeitung alle Umrisse wider.
Jetzt teilst du das ganze Bild in Quadrate. Quadrate die Teile des Strichcodes enthalten, haben immer (wenn die Quadrate groß genug gewählt sind)schwarz-weiß übergänge. Also ist überall da wo in unserem neuen Bild kein Übergang (= keine schwarzen Punkte) ist kein Barcode.
So kann man vermutlich schon eine Menge stellen ausschließen.

Jetzt muss man sich Charackteristische Merkmale für Quadrate heraussuchen die Barcode enthalten. (Man könnte alle weißen Pixel und alle schwarzen Pixel in noch Möglichen quadraten addieren und den Mittelwert Bilden, vielleicht erkennt man durch ausprobieren das quadrate aus der Mitte des Codes meistens ein verhältnis von 2:100 oder so ist.

Bei Potentielen Quadraten kann man sich überlegen ob man irgendwie die schwarzen Pixel darauf überprüfen kann, dass sie in einer Reihe sind (wenn auch gedreht). So könnte man zurückrechnen wie weit man das Bild drehen muss um alles grade zu haben. Jetzt geht man von diesem Quadrat aus Nach rechts und links und findet leicht den rand des barcodes, nämlich dann wenn kein schwaz weiß unterschied bei gewissen Abständen vorhanden ist.

Das als Denkanstoß

MfG

Spiderpig

PS:

echt interessantes Thema :D

[Prototypjack]

Moin,

Der Ansatz mit der Timing-Tabelle scheint wirklich der Richtige zu sein, danke dafür! Aber ich habe jetzt ein grundsätzliches Problem mit dem EAN-13 Standard.

Wie finde ich die erste Zahl heraus? Steht die irgendwo kodiert (muss sie ja, denn es gibt ja auch Barcodes ohne Zahlen)? Denn laut Wikipedia (und der Standard ist in meinen Augen mehr als verwirrt :shock: ) ist diese Zahl maßgeblich für das Lesen des Strichcodes.

Grüße,
Max

[Alien_F]

Die eigentliche Nr. ist tatsächlich 13-stellig ( inkl. Prüfziffer ). Falls du C1,C2,C3 meinst - die Dinger stellen keine Ziffern dar, sondern lediglich Markierungen.

[Prototypjack]

Zitat:

Zitat von Alien_F

Die eigentliche Nr. ist tatsächlich 13-stellig ( inkl. Prüfziffer ). Falls du C1,C2,C3 meinst - die Dinger stellen keine Ziffern dar, sondern lediglich Markierungen.

Ja, schon klar. Aber sieh' dir mal die Prüfziffer bzw. deren Bedeutung an. Diese kann von 0-9 variieren und verändert, je nach Zahl, die gesamte Struktur des Codes (ist im englischen Wiki-Artikel als R/G/B gekennzeichnet).

Damit ich jetzt den Code überhaupt lesen kann, muss ich die erste Zahl wissen, nur, wie mach' ich das?

Grüße,
Max

[Alien_F]

Ach so. Du meinst was völlig anderes.
Die erste Ziffer wird gar nicht kodiert, sondern ergibt sich aus dem Pattern der Kodierung der 1 6er-Gruppe. ( Deswegen druckt man wahrscheinlich die erste Ziffer vor die erste Markierung C1 - rein optisch betrachtet).
Du musst einfach die ersten 6 Zahlen hinter dem ersten Marker entziffern. In dem Artikel ist ein Beispiel mit einer führenden 8. Hat man erkannt, dass für die erste 6er-Gruppe das zugrundeliegende Pattern LGLGGL war, kann man in der Tabelle entsprechend nachschauen.

( um Verwirrungen vorzubeugen: die Prüfziffer (also die Checksumme des Codes) ist die allerletzte Ziffer und wird explizit kodiert. Berechnugsformel zur Verifizierung ist ja weiter unten im Artikel angegeben. )

[Medium]

Meinst du die Entscheidung ob das Odd- oder Even-Alphabet vorkommt? Wenn ja, hat die Prüfziffer nichts damit zu tun. Die Unterscheidung Even/Odd fällt auch nicht zwangsweise an, da ein Even-Code nie auch als Odd auftaucht - auch nicht rückwärts, weil das wäre genau die selbe Zahl im jeweils anderen Alphabet. Jede Linienkombination ist eindeutig genau einer Ziffer zuzuordnen, egal ob sie Even oder Odd codiert ist.
Die Prüfziffer ist doch letztlich nur eine Sicherheitsmaßnahme, mit der man nach der Lesung prüfen kann ob man auch alles richitg gelesen hat. Sie ändert nichts an der Interpretation des Codes. Da würde sich ja die Katze in den Schwanz beißen.

[Alien_F]

Vielleicht auch etwas hilfreich. Guckst du hier EAN13 Barcode Control

[Prototypjack]

Moin,

Danke für den Hinweis. Ich dachte irrtümlicherweise, dass sich die Codes innerhalb der 3-Sparten (LGR) wiederholen. Wenn jeder Code dagegen einzigartig ist, ist das, was ich vorher über die erste Ziffer gesagt / gedacht habe natürlich sinnlos.

Grüße,
Max