Forum: Digitale Signalverarbeitung / DSP / Machine Learning Theorie: Welche Bildauflösung ist für Barcodeverarbeitung ausreichend?


von Sören K. (burnersk)


Lesenswert?

Ich habe einen eigenen Barcodescanner gebaut. Als Bildsensor habe ich 
einen alten Parallelinterface-Sensor aus einer kaputten 
billig-Digitalkamera verwendet. Soweit funktioniert es auch, ist aber 
praktisch nicht nutzbar. Aufgrund der unnötigen hohen Bildauflösung 
braucht der µC sehr lange bis die Rohdaten des Bildsensors soweit 
"komprimiert" (Farbe entfernen, Auflösung reduzieren) sind, dass der µC 
die Daten überhaupt verarbeiten kann. Durch die Bildbearbeitung habe ich 
auch erhebliche Qualitätsverluste (mehr als mit einem Sensor, welcher 
die "richtige" Auflösung bereitstellen würde). Soweit zum Projekt.

Ich versuche nun herauszufinden, welche (native) Auflösung der 
Bildsensor haben sollte, damit das Bild klein genug ist, um direkt 
verarbeitet werden zu können.

Für folgende Barcodes habe ich Decoder geschrieben. Die Auflösung müsste 
also so gewählt werden, dass zumindest diese Barcodes alle noch erkannt 
werden können (rein von der Rohdaten-Auflösung her):

* Code-128
* GTIN-8/13 (EAN-8/13)
* QR-Code
* PDF417 (mit meiner aktuellen "dreckigen" Lösung liegt die erfolgreiche 
Erkennungsrate allerdings bei unter 25%)

Ich denke die Anforderungen an die Auflösung werden wohl von PDF417 
getragen. Die Testbarcodes, welche ich nutzte, sind sehr klein und 
"Datenreich". Ein kleiner Datenpunkt ist nur 0,25 mm groß.

Edit: Mir ist gerade aufgefallen, dass der kleinste Barcode-Strich noch 
kleiner ist als 0,25 mm. Ich kann es nicht genau ausmessen, aber es 
sieht nach cirka 0,083 mm (1/3 von 0,25 mm) aus.

Folgende Anforderungen ergeben sich also:

* PDF147: Kleinster Datenpunkt ist 0,25 mm groß
* Code 128: Theoretisch "unendliche" Länge, daher muss die 
Ableseentfernung erhöht.
* Standardableseentfernung: 5 cm (EAN-8/13, QR-Code)
* Größte Ableseentfernung: 10 cm für 12 cm breite Code-128 Barcodes

Ich hätte am liebsten Graustufensensoren, so kann ich den Kontrast per 
Firmware selbst bestimmen (Barcode/Hintergrund-Schwelle).

Der Sensor sollte nach Möglichkeit quadratisch sein, dafür habe ich 
nämlich schon Entzerrroutinen geschrieben :)

Ich bin gerade ein bisschen überfordert, die Formel für die notwendige 
Auflösung zu entwerfen. Könnte mir jemand helfen?

: Bearbeitet durch User
von J. S. (engineer) Benutzerseite


Lesenswert?

Bei dem "Vermessen" solcher gerader Linien gibt es einige optische 
Tricks, die man veranstalten kann, um die Redundanz der Information, die 
sich durch mehrfaches Lesen der Strichbreiten durch die Sensorzeilen 
ergibt, zu nutzen.
Die Optik ist da mit das Wichtigste!

Wenn du einfach 1:1 über den gesamten Bereich abbildest, hast Du eine 
einfache Winkelbetrachtung, mit Unschärfe der Optik und der dynamischen 
Bewegung der Hand und dann nur noch die Entzerrung durch die 
Schräghaltung und Verbiegung des Barcodes auf der Verpackung.

Was genau meist Du mit "Graustufen"?

Beitrag #5269865 wurde vom Autor gelöscht.
von Sören K. (burnersk)


Lesenswert?

Jürgen S. schrieb:
> Was genau meist Du mit "Graustufen"?

Nur den Helligkeitswert eines Pixels (von 0 für Schwarz über 127 Grau 
bis 255 Weis). Ein Pixel verbraucht so nur 1 Byte (8 Bit) Speicher.

Bei Farb-/RGB-Sensoren wird ein Pixel als Rot-/Grün-/Blauwert übertragen 
und hat somit 3 Byte Speicherverbrauch pro Pixel.

Einen Farbsensor einzulesen braucht also:
1) 3x so lange, weil 3x so viele Daten übertragen werden (ungeachtet dem 
processing overhead)
2) 3x so viel Speicher (weil Rot/Gelb/Blau statt nur "Helligkeit" pro 
Pixel)
3) Processing overhead um aus den 3 Rot/Gelb/Blau-Werten einen 
"Helligkeitswert" zu machen.

Da der interne RAM und externe RAM begrenzt ist, würde ich den 
Speicherverbrauch gerne minimal halten.

von Strubi (Gast)


Lesenswert?

Moin,

mir ist nicht ganz klar, wo das Problem liegen sollte..
Linsenbrennweite und Bildgleichung (1/f = 1/b + 1/g) hast Du ja sicher 
im Griff.. Wenn du es gleich die Verzerrung in der Formel brauchst, 
geht's in die Matrizen, das ist komplexere Optik, da würde ich die 
Entzerrung einfach empirisch ermitteln.

Was den Sensor angeht: Mit dem Monochrom-WVGA MT9V032 und ähnlich (*024) 
habe ich betr. BV (insbesondere auch 2D-Barcode-Erfassung) gute 
Erfahrungen gemacht. Mit RGB oder YUV wird die Sache ziemlich hässlich, 
je nach Bayer-Pattern und Algo wird dir ganz unterschiedlich die 
Auflösung versaut.
Und dass bei deinem System Rot-Gelb-Blau rauskommt...also, da würde ich 
nochmal genau hinschauen :-) Billigcams haben normalerweise keine 
Farbensplitter sondern popliges Bayerpattern. Kameras mit dem Sensor und 
auf einem hackbaren DSP basierend finden sich zuhauf, das günstigste 
dürfte wohl aber ein px4flow-Brettchen sein.

So...und für den Rest musst du dir noch die passende Linse suchen, und 
die Entzerrung schlau machen. Typischerweise musst du nach Ermittelung 
der Lage des Barcode nur noch die Codes richtig tracen, eine 
Bild-Vorentzerrung ist rechnerisch viel zu teuer (BTDT). "Quadratisch" 
ist der Sensor dann, wenn du ein ROI einstellst...

von Dieter (Gast)


Lesenswert?

Rechne mal mindestens zwei Pixel für die schmalste Linie. Mein 
Beispiel-Strichcode (Code auf der Produktverpackung) hat 3cm Länge. 1,5 
mm benötigen 3 meiner kleinsten Striche. D.h. für schwarz je 2 und weiß 
je 2 Pixel macht, insgesamt 12 Pixel auf 1,5 mm. Also 12*30mm/1,5mm = 
240 Pixel. Wenn der Barcode nicht mindestens so groß auf dem Bild ist, 
dass er in der Länge 240 Pixel des Bildes beansprucht, bzw auf den 
Sensor fällt, kann es nicht gut funktionieren. Bei 320x240er Auflösung 
sollte der Barcode das Bild fast ausfüllen. Bei einer 640x480er Sollte 
es fast die Hälfte der Seitenlänge (bzw. ein viertel der Fläche) der 
Barcode abdecken.
Für andere Codes mußt Du Dir das entsprechend berechnen.

von J. S. (engineer) Benutzerseite


Lesenswert?

Sören K. schrieb:
> Bei Farb-/RGB-Sensoren wird ein Pixel als Rot-/Grün-/Blauwert übertragen
> und hat somit 3 Byte Speicherverbrauch pro Pixel.
>
> Einen Farbsensor einzulesen braucht also:
> 1) 3x so lange,

Nicht unbedingt. Bayersensoren sind Grausensoren mit Farbfilter. Es 
kommen also genau so viele Daten, nur eben mit reduzierter 
Farbinformation.

Meine eigentliche Frage ging aber auf das Thema "Stufen". Die wurde 
jetzt indirekt beantwortet, wobei 8 bit jetzt soviel nicht ist, je nach 
Lichtverhältnissen aber reichen kann.


Dieter schrieb:
> Rechne mal mindestens zwei Pixel für die schmalste Linie.
Auf das Thema habe Ich eigentlich gewartet: "Pseudonyquist" nenne Ich 
das immer. Nun, wenn die Linien ganzzahlige Vielfache der schmalsten 
Linie sind und man sehr einfach und grob verarbeiten möchte, dann ist 
das in der Tat eine valide Forderung. Die führt allerdings dazu, dass 
man sehr gut aufgelöste Sensoren braucht. Rechne Dir mal die Winkel aus.

Das geht besser: Mit etwas Schmalz reicht dann schon bei einem 
Zeilensensor mit nur einer Pixelgruppe ein Abstand in der 
Cosinus-Alpha-Achse mit etwa der 1,1 Pixel, sofern das Linienkriterium 
so einfach ist. Es gibt aber Bar-Codes wo das nicht der Fall ist, also 
die Linien z.B. 0,2 die nächste 0,3 und dann 0,45 breit ist. Für eine 
einfache Verarbeitung braucht man dann Linienauflösungen von 0,05 - mit 
etwas Schmalz und Vordiskriminierung 0,15.

Der entscheidende Clou ist aber die 2D-Charakteristik des Sensors zu 
benutzen und die Zeilen quasi per undersampling zu erwischen. Dann 
reicht auch ein n-tel der Sensorauflösung mit n = Wurzel (Pixelzahl). 
Mit einem Zeilensensor von 400 pixeln in X, der eine Auflösung von 0,1mm 
bietet, hätte man dann minimal 1/20 tel davon. Theoretisch und bei 
justierten Sensoren mit perfekten Pixeln mit kalibierter Optik 
2/400stel.  Mit einer Verzerroptik, die die Struktur entsprechend 
variabel abbildet, sind durchschnittlich 1/100 zu machen. Dann aber mit 
richtig ordentlich Auswertesoftware.

Hinzu kommt aber wie gesagt ein durch eine Verpackung 3D-verbogenes 
Label. Dessen Verzerrung limitiert die Erkennbarkeit wieder.

Wie liest du eigentlich aus und wie wird belichtet?

von Strubi (Gast)


Lesenswert?

Jürgen S. schrieb:
> Der entscheidende Clou ist aber die 2D-Charakteristik des Sensors zu
> benutzen und die Zeilen quasi per undersampling zu erwischen

Das ist zwar signalverarbeiterisch spannend, aber wenig praktikabel und 
dürfte die Rechenleistung eines STM32 ziemlich ausbooten..
Schon beim Entzerren und mit Bresenham-Tracer-Tricksereien (stückweise 
Linearisierung anstatt Linsenformel, usw.) geht einiges an Arithmetik 
drauf und liefert spätestens bei 2D-Barcode beliebig Artefakte. Warum 
immer verkomplizieren?
Schon mit einer Fischaugenlinse wird das gehörig mühsam (BTDT), gerade 
wenn Framerate gefordert wird. Aber gut, wenn's ein Lernprojekt ist...

Apropos: Eine olle LeanXcam mit MT9V032 hab ich hier noch rumliegen, die 
hat damals so an die 3-5 fps QR-Codes unter Linux geschafft, bare-metal 
geht fast das doppelte. Gebe das Ding gerne her (ohne Source).

von Possetitjel (Gast)


Lesenswert?

Strubi schrieb:

> Schon mit einer Fischaugenlinse wird das gehörig mühsam

Naja. Man kann sich das Leben natürlich beliebig schwer
machen... :)

Bei einem Selbstbau-Scanner würde ich schon eine vernünftige
winkeltreu abbildende Optik verwenden; im einfachsten Falle
eine altes Photo-Normaloptik.

von Abdul K. (ehydra) Benutzerseite


Lesenswert?

Schaut euch mal an wie schnell die Erfassung an einer Kasse ist. Da 
verwirbelt ein drehender Spiegel die Position der Ware auf dem Band. Das 
Ding dreht sich recht schnell. Vermutlich um den Barcode in eine 
passende Lage für den Sensor zu bringen.
Also würde ich mal sagen, das dauert nur Mikrosekunden.

von Strubi (Gast)


Angehängte Dateien:

Lesenswert?

Abdul K. schrieb:
> Also würde ich mal sagen, das dauert nur Mikrosekunden.

Wenn du's mit dem Laser abtastest, brauchst du auch kaum noch BV, die 
Kassendinger machen m.W. nur eine 1D-Abtastung. Der olle EAN ist ja 
schon mit einem Photosensor-Stift einfach zu implementieren.

Possetitjel schrieb:
> Naja. Man kann sich das Leben natürlich beliebig schwer
> machen... :)

Och..so schwer auch wieder nicht. Ich hab mal noch n ollen Snapshot 
(Datamatrix-'Briefmarke') ausgegraben, im Mittelfeld ist so'n Code gut 
linear zu erfassen. Gibt halt ein paar Bildbereiche am Rand, wo's eng 
wird..
Zugehörige Brennweite weiss ich allerdings nicht mehr genau, muss was 
zwischen 8 und 14 mm gewesen sein.

von Strubi (Gast)


Lesenswert?

Moin,

Abdul K. schrieb:
> Schaut euch mal an wie schnell die Erfassung an einer Kasse ist. Da
> verwirbelt ein drehender Spiegel die Position der Ware auf dem Band. Das

ich sag nur: morphogenetische Felder...
Heute im Supermarkt sehe ich, dass die Selbst-Bezahl-Kassen übers neue 
Jahr mit neuer HW des Typs Datalogic Magellan bestückt wurden. Anstatt 
rotierender Spiegel gibt's jetzt nur noch konstant rote LED-Panels und 
fixe Spiegel. Also auch wohl nur noch klassische CMOS-Kamerasensoren...

von J. S. (engineer) Benutzerseite


Angehängte Dateien:

Lesenswert?

Beitrag "Theorie: Welche Bildauflösung ist für Barcodeverarbeitung ausreichend?"

Strubi schrieb:
> Also auch wohl nur noch klassische CMOS-Kamerasensoren...
... mit eben entsprechender Signalverarbeitung! Wobei du richtig 
bemerktest, dass das mehr erfordert, als einen STM32.

>Fischauge
Eine Möglichkeit, ja. geht aber noch besser.

Anbei noch was aus der Mottenkiste: Echtzeit-Bildaufbereitung für eine 
Auswertesoftware. Bar-Codes sind aber nur der Trainer gewesen, die 
Kamera observierte was ganz anderes.

von Strubi (Gast)


Lesenswert?

Jürgen S. schrieb:
> Beitrag "Theorie: Welche Bildauflösung ist für Barcodeverarbeitung
> ausreichend?"
>
> Strubi schrieb:
>> Also auch wohl nur noch klassische CMOS-Kamerasensoren...
> ... mit eben entsprechender Signalverarbeitung! Wobei du richtig
> bemerktest, dass das mehr erfordert, als einen STM32.

DAS ginge jetzt schon mit nem STM32. Sobald die Beleuchtung gut ist und 
alles nur in 1D, ist das kein Thema. Trotzdem ist in den 
Magellan-Dingern ein Blackfin drin (zumindest gewesen), das aber 
vermutlich nicht aus Gründen der Rechenpower.


>>Fischauge
> Eine Möglichkeit, ja. geht aber noch besser.
>

M12 Fischaugen sind stinkebillig. Was will man da noch verbessern?

von Dieter (Gast)


Lesenswert?

>> Dieter schrieb:
>> Rechne mal mindestens zwei Pixel für die schmalste Linie.

>Auf das Thema habe Ich eigentlich gewartet: "Pseudonyquist" nenne Ich das immer. 
Nun, wenn die Linien ganzzahlige Vielfache der schmalsten Linie sind und man sehr 
einfach und grob verarbeiten möchte, dann ist das in der Tat eine valide 
Forderung. Die führt allerdings dazu, dass man sehr gut aufgelöste Sensoren 
braucht. Rechne Dir mal die Winkel aus.

Nyquist ist immer der erste Startpunkt und dann prüfe man, ob es 
geeignete Kniffe gibt mit weniger auszukommen. Der Wert mit mindestens 
zwei Pixeln stammt vom Liniensensor-Scanner mit 240-255 Pixeln. Die 
mußte man mit der Hand genau an den "Tag" auf der Packung halten.
Bei einer Kamera gibt es Tricks, die aber voraussetzen, dass der Sensor 
nie pixelgenau-lininen genau über dem gesamten Tag liegen. In dem Falle 
hätten alle Zeilen im Bild genau den identischen Inhalt, als wäre nur 
die Zeile des Liniensensors vervielfacht worden.

Ein normaler Kamerasensor mit 60° Öffnungswinkel bringt auf der Breite 
in 2m Entfernung gerade eine Schrankwand von 2m auf das Bild. Der "Tag" 
auf dem Produkt mit 2,8cm muss also bei diesem Sensor 640x480 mindestens 
2,8cm weit weg sein (sonst sieht die Kamera nur einen Ausschnitt des 
Tags) und darf höchstens 5,6 cm entfernt sein. Mit einer 2M-Kamera darf 
der Tag schon bis zu fast 15cm weit weg sein (1600x1200) mit einer 
8M-Kamera sind die 30cm zu erreichen.
Wenn nur 15cm bis 30cm als Entfernung (da die Tags gut ins Sichtfeld 
plaziert werden können) für die Funktion notwendig wären, würden es mit 
15° Öffnungswinkel und 640x480-Sensor schon funktionieren können.

von Tobias P. (hubertus)


Lesenswert?

Hi
habe ich das richtig gelesen, ihr könnt das mit einem STM32? also 
auslesen des Sensors und verarbeiten des Bildes?
das würde mich enorm interessieren, sowas wollte ich auch immer schon 
mal machen.
Bildverarbeitung habe ich bis jetzt aber immer in Matlab oder Octave 
implementiert.
Wie macht ihr das auf dem uC? wie wertet man einen Barcode auf einem 
Bild aus? und vor allem: wie findet man ihn?
Auf Strubis Bild weiter oben liegt der Code ja irgendwo schief in der 
Gegend.

von 235456456455623563235235635 (Gast)


Lesenswert?

klingt interessant

Wie wäre es mit einer USB Webcam?
Das funktioniert recht gut.
Zumal man bei webcams die Auflösung auf zuruf ändern kann.

Mich würde dabei interessieren wie man den BC erkennt und entsprechend 
so  hindreht das man etwas decodieren kann.

Mit geraden BC hab ich schon nen knoten im kopf ...


bildverarbeitung ist nicht so meins ^^

von 235456456455623563235235635 (Gast)


Lesenswert?

Tobias P. schrieb:
> habe ich das richtig gelesen, ihr könnt das mit einem STM32? also
> auslesen des Sensors und verarbeiten des Bildes?
> das würde mich enorm interessieren, sowas wollte ich auch immer schon
> mal machen.


die größeren STM  haben ein paralleles camera interface
Das witzige ist die riesigen Datenmengen zu verarbeiten.

von Strubi (Gast)


Lesenswert?

Tobias P. schrieb:
> Hi
> habe ich das richtig gelesen, ihr könnt das mit einem STM32? also
> auslesen des Sensors und verarbeiten des Bildes?

Die STM32 mit DCMI (nicht DCIM :-) ) können das. Nur beim DMA gibt es 
Stolperfallen, ich würde nach wie vor für robuste Lösungen einen 
Blackfin einsetzen.

> das würde mich enorm interessieren, sowas wollte ich auch immer schon
> mal machen.
> Bildverarbeitung habe ich bis jetzt aber immer in Matlab oder Octave
> implementiert.
> Wie macht ihr das auf dem uC? wie wertet man einen Barcode auf einem
> Bild aus? und vor allem: wie findet man ihn?

Kommt draufan, wie dein Bild/die Beleuchtung beschaffen ist. Wenn 
homogen ausgeleuchtet, wird's recht einfach, z.B.
- ein paar zufällig verwürfelte Scan-Linien übers Bild abtasten und auf 
charakteristische Profile triggern
- Ecken-Detection um die Marker zu lokalisieren

Die Marker geben die Orientierung und Synchronisationsinfo vor, im Bild 
oben ist das das durchgängige 'L' und die alternierenden Quadrate an den 
gegenüberliegenden Kanten. Hast du die Eckpunkte, kannst du die 
Rückprojektion mit einem schnellen Bresenham-'Walk' erledigen.

Die besten Ergebnisse hatte ich mit vorgängiger Blob-Detection, bei der 
gleich die Bounding-Box der Blobs bei rausfällt und die Beleuchtung 
nicht so ein Thema ist (dynamische Thresholds für Vorder/Hintergrund).

Ansonsten gibt's auch eine offene library namens libdtmx, die bringt 
zwar nicht viel Performance, aber ist eine brauchbare Referenz fürs 
Decoding.

Bitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.