Hallo,

eine Frage an die Bildverarbeitungsprofi unter euch (*hust* delfiphan *hust* ): Wie kann ich auf einem per Webcam gemachten (und damit qualitativ eher schlechten) Bild einen Strichcode finden?

Da ich zurzeit für die Schule einen Roboter baue, der eine einfache Version des Brettspiels Dame spielen kann, habe ich schon eine Grundlage für dieses Problem: Ich nehme das Bild, wandle es in den HSV-Farbraum um und dann weiter in den - durch delfiphan bezeichnete - XYZ-Farbraum (siehe: Farben zusammenfassen). Dadurch kommt also ein sehr gut zu verarbeitendes Bild heraus, was dafür sorgt, dass mein Dame-Roboter inklusive Min-Max-Algo auch funktioniert.

Kommen wir aber wieder zum aktuellen Problem zurück. Ich brauche in diesem Fall nur Schwarz und Weiß und bekomme dann in etwa so ein Bild wie im Anhang heraus (ist eine Fotomanipulation, weil ich die Webcam gerade nicht da habe). Ich habe den zu suchenden Strichcode im Bild rot umrandet (der Rahmen ist also in Wirklichkeit nicht vorhanden). Wie kann ich diesen nun Finden, auch wenn er z.B. gedreht oder verzerrt ist?

Aufbau des Strichcodes (16-stellig):



Der Strichcode im Bild im Anhang bedeutet: 1132211333023302

Grüße
GTA-Place

öh.. bei der Bildgröße hast du dich ja nicht gerade überschlagen
Ich kann jedenfalls kaum was erkennen.

Das ist zwar nur ein Ausschnitt, der ist aber Originalgröße, also einfach zoomen

Habs mal 10fach vergrößert.

GTA-Place hat folgendes geschrieben:

Das ist zwar nur ein Ausschnitt, der ist aber Originalgröße, also einfach zoomen Habs mal 10fach vergrößert.

Also bei mir ist es ziemlich winzig und ich kann auch weder zoomen noch sonstwie vergrößern.

Ich sag ja: Ich habs vergrößert. Siehe Anhang oben.

Geh doch einfach Zeilenweise durch. Ein Strich bzw. Zwischenraum im Sinne des Strichcodes hat eine bestimmte Dicke +/- Toleranz. Du nimmst dir also jweils eine Zeile, suchst weisse(W) und schwarze Striche (S), die innerhalb der Toleranz sind, sowie Bereich (*), die außerhalb der Toleranz sind.

Dann bekommst Du z.B. '*WSSSWWWSSWSW*' oder auch einfach '****W', oder '*', irgendwie sowas jedenfalls.

Anhand deines Alphabetes kannst du dann sehr einfach dekodieren. Wenn mehrere Zeilen hintereinander die gleiche Dekodierung hervorbringen (Achtung!, vielleicht mit Levenshtein prüfen!), kannst du den Code als 'verifiziert und gelesen' ausgeben.

Da hast ja soetwas wie einen 2D-Barcode, da wird die Sache dann nicht ganz so trivial, aber im Grunde genommen immer noch simpel (rudimentäre Mustererkennung): Du scannst nicht eine Zeile, sondern z.B. 4:

Wichtig wäre erst einmal, dass Du dir eine Markierung suchst, die man im Bild recht einfach finden kannn. Und davon dann ausgehend weitersuchen ...

Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.

So machen es auch normale Barcodes. Hier dient SWS als Anfangs-, End- und Mittenzeichen.

Ich könnte eventuell noch, wie das bei Eye of Judgement gemacht wird, unter den Strichcode einen durchgehenden schwarzen Balken zeichnen. Dann müsste ich erstmal nur nach sowas suchen. Schwieriger wird das aber IMHO wenn der Strichcode gedreht ist.

Linien-Erkennung ist mit digitaler Bild-Verarbeitung relativ einfach. Und dann zu prüfen, ob oberhalb oder unterhalb vom Strichcode was geschrieben ist, sollte ja nicht das Thema sein

Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.

Ehm. Theoretisch könnte die Zahl ja auch 00000 sein, dann hast du ein weisses Bild... Wie soll da ein Algorithmus rausfinden, wo der Strichcode ist bzw. wo der Strichcode anfängt?

Ein Strichcode hat üblicherweise klare Start-Stop Sequenzen oder Orientierungsmuster und ist auf Maschinenlesbarkeit optimiert. Z.B. kann die "Taktfrequenz" in der Start/Stop-Sequenz festgehalten sein und die Zahl beinhaltet eine Prüfziffer und/oder ist redundant codiert. Ausserdem sollte ein Strichcode nicht über einen längeren Abschnitt ganz schwarz oder ganz weiss werden (zu mindest bei 1D). Es sollte da höchstens zwei oder drei vorgegebene Strichdicken/"Lückendicken".

Dein Strichcode geht schon fast Richtung 2D, was noch viel schwerer zu erkennen ist. Bei 1D kannst du den Code auch etwas schräg scannen, das spielt dann keine Rolle. Bei 2D muss die Ausrichtung ziemlich exakt bestimmbar sein. Bei deinem Strichcode dürfte das nicht ganz einfach sein.

delfiphan hat folgendes geschrieben:

Ehm. Theoretisch könnte die Zahl ja auch 00000 sein, dann hast du ein weisses Bild... Wie soll da ein Algorithmus rausfinden, wo der Strichcode ist bzw. wo der Strichcode anfängt?

Deshalb könnte ich ja eine durchgehende Markierung darunter setzen. Dann ist klar: der Strichcode ist da, wo der dicke Strich ist.


EDIT: Mit Sobel schein ich weiterzukommen. Die Kanten werden zumindest schonmal schön dargestellt und den Drehwinkel weiß ich dadurch ja automatisch auch.

Hängt davon ab, wie fest das Bild verzerrt sein kann, wie hoch die Auflösung des Bildes ist und in wiefern du selbst bestimmen kannst, wie der Barcode aussieht und ob mehrere Barcodes in einem Bild vorkommen können.

1. Umriss ermitteln
Der Freiheitsgrad ist 8 (Position/Grösse/Rotation/Verzerrung), was sehr viel ist. Du musst alle 4 Eckpunkte relativ sicher erkennen können. Es ist daher schlecht, wenn ein Eckpunkt einfach weiss sein kann und du durch Extrapolation den Eckpunkt errechnen musst. Der zusätzliche Balken reicht noch nicht. Auch wenn du oberhalb des Codes noch einen Balken hast, kannst du die Zahlen 11111, 00000 und 22222 nicht wirklich voneinander unterscheiden. Wenn du oben und unten einen Balken hast, dann sieht die Sache schon besser aus. Aber selbst dann ist es nicht immer einfach, denn zwei Striche bedeutet ja 00000, egal ob die Striche nun parallel sind oder nicht (Verzerrung!). Wenn mehrere Barcodes im Bild sind, wird die Sache noch viel komplizierter.

Fazit: Ohne klare Merkmale wird's nicht einfach. Bei Eye of Judgement sorgen 4 hellgrüne Pfeile für die Positionsbestimmung. Da ein solches hellgrün sonst nirgends auf den Bildchen oder auf der Karte vorkommt funktioniert die Erkennung sehr gut. Bei dir sind die Bilder extrem klein und schwarzweiss.

2. Bild entzerren/drehen
siehe Algorithmus zum Kamerabilder entzerren

3. Decodieren
Das sollte dann relativ einfach sein. Die Codierung sollte eine Prüfsumme beinhalten oder die Daten redundant speichern.

Eine ganz andere Möglichkeit wäre sowas wie Digimarc zu implementieren.

delfiphan hat folgendes geschrieben:

Hängt davon ab, wie fest das Bild verzerrt sein kann

Unverzerrt normalerweise. Direkte Draufsicht.

delfiphan hat folgendes geschrieben:

wie hoch die Auflösung des Bildes ist

Das müsste 640x480 sein. Der zu beachtende Bereich ist aber im Moment etwa 260x290.

delfiphan hat folgendes geschrieben:

und in wiefern du selbst bestimmen kannst, wie der Barcode aussieht

Den kann ich zu 100% selbt bestimmen, weil ich den auch erstelle

delfiphan hat folgendes geschrieben:

und ob mehrere Barcodes in einem Bild vorkommen können.

Jop.

delfiphan hat folgendes geschrieben:

Bei Eye of Judgement sorgen 4 hellgrüne Pfeile für die Positionsbestimmung. Da ein solches hellgrün sonst nirgends auf den Bildchen oder auf der Karte vorkommt funktioniert die Erkennung sehr gut. Bei dir sind die Bilder extrem klein und schwarzweiss.

Grün oder andere Farben da reinzubringen wäre natürlich auch möglich.


Soweit danke schonmal.

Grüße
GTA-Place