DE69801161T2 - Verfahren zur Detektion von Coden in zweidimensionalen Bildern - Google Patents

Description

• Die Erfindung betrifft ein Verfahren zum Lokalisieren von Codes in zweidimensionalen Bildern.
• Codes sind bekannt zum Codieren von Information, z. B. zum optischen Identifizieren von Objekten. Insbesondere wird heute umfangreicher Gebrauch gemacht von Strichcodes, die in einer stets zunehmenden Vielzahl von Anwendungen eingesetzt werden, weil sie kompakt und robust in bezug auf Umgebungsbedingungen sind, was eine automatische Decodierung selbst in Anwesenheit eines hohen Rauschpegels und die Möglichkeit des automatischen Lesens und Interpretierens erlaubt. Sie erlauben jedoch nur die Speicherung einer relativ begrenzten Informationsmenge; um diese Begrenzung zu überwinden, wurden in jüngerer Vergangenheit zweidimensionale Codes vorgeschlagen, wie Datamatrix, Maxicode, QR-Code und Stapelcodes (z. B. PDF417), wobei Beispiele hierfür in den Fig. 1a, 1b, 1c und 1d gezeigt sind.
• Die zweidimensionalen Codes können auch gelesen werden, indem zweidimensionale Bilder in einem Bereich, in dem der Code erwartet wird, erfaßt werden, und der Code innerhalb des Bildes für die spätere Decodierung lokalisiert wird. Insbesondere muß das Lokalisieren des Codes eine Unterscheidung des Bereichs oder der Bereiche, der oder die ein oder mehrere Codes umfassen, von Bereichen, welche andere Objekte oder Zeichnungen enthalten, innerhalb des in einem Prozessorspeicher gespeicherten Bilds ermöglichen. In erster Instanz beabsichtigt die Lokalisierung das Finden bestimmter Erkennungsmuster, die für jeden Code typisch sind; die Kenntnis einer Musterposition und des Codetyps macht es möglich, den Code aus dem Bild zu extrahieren und dann zu decodieren.
• Die Aufgabe der Erfindung besteht darin, ein neues Verfahren für das Lokalisieren von Codes in zweidimensionalen Bildern anzugeben.
• Erfindungsgemäß wird ein Verfahren zum Lokalisieren von Codes in zweidimensionalen Bildern vorgesehen, das den Schritt der Erfassung eines zweidimensionalen Bildes umfaßt, das aus einer Vielzahl von durch einen Helligkeitswert charakterisierten Punkten gebildet ist, gekennzeichnet durch die folgenden Verfahrensschritten:
• - Aufteilen des zweidimensionalen Bildes in eine Vielzahl von Bildregionen, wobei jede Bildregion eine zugehörige erste Anzahl von Punkten umfaßt;
• - Bestimmen einer ersten Größe für jede der Bildregionen, die zu der Intensität der Helligkeitsänderung jeweiliger Punkte bezüglich benachbarter Punkte korreliert ist;
• - Bestimmen mindestens einer zweiten Größe für jede der Bildregionen, die mit der Richtung der Helligkeitsänderung der jeweiligen Punkte bezüglich benachbarter Punkte korreliert ist; und
• - Bestimmen jeglichen Vorhandenseins und Art eines Codes anhand der ersten und zweiten Größe in jeder der Bildregionen.
• Das Bild wird vorzugsweise in Blöcke mit solchen Abmessungen aufgeteilt, daß diese einen Teil eines Codes oder maximal einen gesamten Code, jedoch nicht mehr als einen Code enthalten, um die nachfolgende Bearbeitung zu vereinfachen; in jedem Block wird die Intensität der Helligkeitsänderung bewertet, um Blöcke mit geringem Kontrast, die eindeutig keine Codes enthalten, auszuschließen; für jeden Block mit ausreichendem Kontrast wird die Richtung der Helligkeitsänderung bewertet, die zu dem Typ eines vorhandenen Codes korreliert. Um die Intensität der Helligkeitsänderung abzuschätzen, wird vorzugsweise der Punktgradient verwendet, und die Intensitätswerte des Gradienten werden, berechnet für alle Punkte jedes Blocks, summiert; dann werden nur Blöcke betrachtet, die eine Summe haben, die über einen vorgegebenen Schwellwert liegt. Zusätzlich wird zum Abschätzen der Richtung der Helligkeitsänderung die Richtung des Gradienten der Punkthelligkeit verwendet, und für die betrachteten Blöcke wird oder werden die vorherrschende Gradientenrichtung oder - richtungen berechnet. Wenn es eine einzige vorherrschende Richtung gibt, wird für jeden betrachteten Block entschieden, daß dieser Block einen linearen Code (Strichcode oder Stapelcode) enthält; wenn es zwei vorherrschende Richtungen gibt, bedeutet dies, daß ein Datamatrix-Code oder ein QR-Code vorhanden ist.
• Die Lokalisierungsinformation (ein Block, der einen Code enthält) und der Codetyp werden dann dazu verwendet, eine Feinlokalisierung und Segmentierung durchzuführen, um den Umriß des Codes präzise zu ermitteln.
• Weitere Merkmale der Erfindung ergeben sich aus der Beschreibung einer bevorzugten Ausführungsform, die lediglich als Beispiel und nicht als Beschränkung dient und anhand der Zeichnungen illustriert ist. In den Figuren zeigen:
• Fig. 1a, 1b, 1c und 1d Beispiele von bekannten zweidimensionalen Code;
• Fig. 2 zeigt ein Flußdiagramm in bezug auf das Lesen eines optischen Codes aus einem zweidimensionalen Bild;
• Fig. 3 zeigt ein detailliertes Flußdiagramm eines Blocks der Fig. 2;
• Fig. 4a, 4b und 4c zeigen Histogramme in bezug auf die Kennlinienverteilung bekannter zweidimensionaler Codes;
• Fig. 5 zeigt ein detailliertes Flußdiagramm eines Blocks der Fig. 3;
• Fig. 6a zeigt ein Beispiel eines Bilds, das ein zweidimensionalen Code enthält, der lokalisiert werden soll; und
• Fig. 6b, 6c, 6d, 6e und 6f zeigen aufeinanderfolgende Verarbeitungsschritte des Bildes der Fig. 6a gemäß dem vorliegenden Lokalisierungsverfahren.
• Wie in Fig. 2 gezeigt, wird zum Suchen und Lesen eines Codes in einem zweidimensionalen Bild zunächst das Bild eines Raumabschnitts erfaßt und gespeichert, wobei wenigstens ein Informationscode (Block 10) gesucht wird. Insbesondere kann das Bild von jeder Art von Telekamera oder Aufzeichnungseinrichtung erfaßt werden, die an ihrem Ausgang ein digitalisiertes Bild in Graustufen vorsieht, das durch mehrere Pixel gebildet ist, die jeweils die Helligkeit des Bildes bei jedem Punkt darstellen, vorzugsweise mit wenigstens 8 Bit codiert (wenigstens 256 Graustufen). Das digitalisierte Bild wird dann in einem geeigneten Speicher (nicht gezeigt) für die spätere Verarbeitung gespeichert.
• Im einzelnen werden die sogenannten interessierenden Merkmale zunächst gesucht und aus dem digitalisierten Bild extrahiert, Block 11. Dieser Vorverarbeitungsschritt, der im folgenden mit Bezug auf Fig. 3 im einzelnen beschrieben ist, dient zum Zweck der Extraktion einiger Grundinformation für die nachfolgende Bestimmung der interessierenden Bereiche, d. h. der Bereiche, welche das Erkennungsmuster jedes Codetyps enthalten. Erfindungsgemäß sind diese interessierenden Merkmale zu lokalen Variationen der Helligkeit des digitalisierten Bildes korreliert. In den interessierenden Bereichen variieren tatsächlich die Helligkeitswerte benachbarter Pixel erheblich; die Codesuche kann somit auf Bereiche begrenzt werden, die hohe Helligkeitsvariationen aufweisen, weil die Suche nach einem Code in Bereichen des digitalisierten Bildes, welche praktisch konstante Helligkeit haben, sinnlos ist.
• Auf der Basis der extrahierten interessierenden Merkmale wird oder werden der interessierende Bereich bzw. die Bereiche, die einen einzelnen Code enthalten, innerhalb des gesamten digitalisierten Bildes ermittelt, und der Codetyp, der in jedem der ermittelten interessierenden Bereiche vorhanden ist, wird abgeschätzt, Block 12, wie in folgenden erläutert ist.
• Dann wird für jeden der interessierenden Bereiche der Code präzise lokalisiert, Block 13, und die geometrischen Grenzen des Codes werden präzise ermittelt, Block 14; schließlich werden die Decodiermerkmale extrahiert und der Code tatsächlich decodiert; Block 15.
• Der Schritt der Extraktion der interessierenden Merkmale 11 erlaubt die Ermittlung der Richtung der lokalen Helligkeitsänderung in beschränkten Bereichen um die einzelnen Pixel des digitalisierten Bildes. In dem betrachteten Beispiel werden insbesondere die Intensität (Größe) des Gradienten und die Richtung des Helligkeitsgradienten ermittelt; als eine Alternative zur Intensität des Gradienten ist es möglich, den Kontrast zu verwenden (durch Umwandeln des Helligkeitswertes des Pixels in binärer Form, um nur weiße oder schwarze Pixel zu erhalten, und Berechnen des Verhältnisses zwischen der Anzahl weißer und schwarzer Pixel in einem bestimmten Bereicht); zusätzlich ist es möglich, auch die Information in bezug auf die Richtung des Helligkeitsgradienten zu verwenden.
• Diese Größen können entweder für jedes Pixel des digitalisierten Bildes berechnet werden, wenn die Abmessungen des digitalisierten Bildes dies erlauben, oder für ausgewählte Pixel durch eine Unterabtastung des digitalisierten Bildes, wenn letzteres große Abmessungen hat. In beiden Fällen können die interessierenden Merkmale mit Hilfe eines der aus der Literatur bekannten Verfahrens berechnet werden, wie das in der EP-A-0 851 374 derselben Anmelderin beschriebene. Als eine Alternative ist es möglich, die Sobel-Faltung mit Kerneln zu verwenden (siehe z. B. R. Gonzalez, R. E. Woods: "Digital Image Processing", Addison Wesley, 1992), wobei für jedes betrachtete Pixel die Ableitung der Helligkeit entlang der x- und y- Achsen berechnet wird, wobei die acht Pixel verwendet werden, welche das betrachtete Pixel umgeben, um einen zweidimensionalen Vektor aus zwei Komponenten zu erhalten; die Intensität wird dann als die Quadratwurzel der Summe der Quadrate der zwei Komponenten berechnet, und die Richtung wird als der Arkustangenz des Verhältnisses zwischen den zwei Komponenten berechnet. Gemäß einer Alternative ist es auch möglich, den Kirch-Operator zu verwenden, der acht verschiedene Operatoren (3 · 3) an jedes betrachtete Pixel anlegt, indem die Ableitung entlang acht möglicher Richtungen um das Pixel herum berechnet und die Richtung unter den acht Richtungen ausgewählt wird, welche den höchsten Wert ergibt; in einer einzelnen Operation können dadurch die Intensität und die Richtung des Helligkeitsgradienten jedes betrachteten Pixels erhalten werden.
• Am Ende des Schrittes der Extraktion der interessierenden Merkmale 11 werden zwei Bilder oder Punktfelder erhalten, eins in bezug auf die Intensität des Gradienten (daß Gradientenintensitätsbild genannt wird) und das andere in bezug auf die Richtung des Gradienten (daß Gradientenrichtungsbild genannt wird), deren Punkte (welche um der Einheitlichkeit willen im folgenden Pixel genannt werden)- den Wert der eben ermittelten Größe haben. Das Gradientenintensitätsbild kann dann einem Schwellwertvergleich unterzogen werden, um Punkte mit niedriger Intensität des Gradienten zu eliminieren (d. h. auf Null zu setzen). Der Schwellwert kann mit einem statistischen Verfahren berechnet werden, das in der Literatur bekannt ist, z. B. ein Montecarlo-Verfahren, beschrieben in D. Montgomery, G. C. Runger: "Applied Statistics and Probability for Engineers", Wiley, 1994.
• Der Schritt des Ermittelns der interessierenden Bereiche 12 umfaßt eine Reihe von Unterschritten, die hier im einzelnen mit Bezug auf Fig. 3 beschrieben sind. Insbesondere wird das digitalisierte Bild zunächst in Blöcke aufgeteilt, d. h. in quadratische oder rechteckige Bereiche, die relativ große Abmessungen haben, so daß sie einen erheblichen Teil des zu dekodierenden Codes enthalten, Block 20. Für ein digitalisiertes Bild aus 512 · 512 Pixeln können z. B. quadratische Blöcke von 64 · 64 oder 48 · 48 Pixel gewählt werden. Die Blöcke können entweder benachbart oder teilweise überlappend sein; im zweiten Fall wird eine größere Genauigkeit erhalten, obwohl der Rechenaufwand erhöht wird.
• Danach wird der Kontrastpegel aller Blöcke aus dem Gradientenintensitätsbild abgeschätzt, das in dem Schritt der Extraktion der interessierenden Merkmale 11 erhalten wird, Block 21. Insbesondere kann der Kontrastpegel unter Verwendung der Pixel des Gradientenintensitätsbildes wirksam abgeschätzt werden, indem der Wert aller Pixel jedes Blocks summiert und dieser Wert in bezug auf die Anzahl der in jedem Block enthaltenen Pixel optional normalisiert wird. Auf diese Weise wird ein Blockkontrastbild erhalten.
• Anschließend wird die Direktionalität der Blöcke analysiert, um den Typ des Codes, der in einem oder mehreren der Blöcke vorhanden ist, zu identifizieren und zu ermitteln, Block 22. Dieser Schritt, der das Gradientenrichtungsbild verwendet und vorzugsweise nur die Blöcke verwendet, in denen der Kontrast einen vorgegebenen Schwellwert überschreitet, stützt sich auf die Tatsache, daß die verschiedenen Codetypen voneinander auf der Grundlage der Richtung des Gradienten der Pixel jedes Blocks unterschieden werden können, welche durch spezifische Histogramme identifiziert werden, die abhängig von dem Codetyp unterschiedliche Spitzenwerte haben, wie unten mit Bezug auf die Fig. 4a bis 4c und 5 erläutert ist.
• Bei allen Blöcken, die einen größeren Kontrast als der vorgegebene Schwellwert haben, ermöglicht dieser Schritt die Ermittlung der Blöcke, welche Codes enthalten, sowie jeder vorherrschenden Richtung, wie unten im einzelnen erklärt ist.
• Danach werden die Blöcke des digitalisierten Bildes, in denen ein Code erfaßt wurde, nach Typen klassifiziert und gemäß ihrer Signifikanz geordnet, Block 23. Insbesondere werden alle Blöcke desselben Typs und mit derselben vorherrschenden Richtung oder Richtungen von anderen getrennt und gemäß der Signifikanz geordnet, indem eine Kostenfunktion angewendet wird, z. B. die Gesamtgradientenintensität oder die Fläche, die dem dominanten Spitzenwert im Richtungsdiagramm gegenüberliegt, etc.
• Schließlich wird der Schritt der Identifikation des Bereichs oder der Bereiche des interessierenden Codes ausgeführt, Block 24; insbesondere wird eine in der Literatur bekannte Wachstumsprozedur (Bereichswachstum) angewendet (siehe der oben genannte Text von R. Gonzalez und R. E. Woods), wobei ähnliche Blöcke zusammengefaßt werden und der bedeutendste Block, der in dem vorhergehenden Schritt ermittelt wurde, als ein Anfangskeim verwendet wird.
• Der Schritt der Richtungsanalyse 22 ist im folgenden im einzelnen mit Bezug auf die Fig. 4a, 4b, 4c und 5 beschrieben. Wie bereits gesagt nutzt der Schritt 22 die Tatsache aus, daß Codes unterschiedlicher Typen Histogramme mit unterschiedlichen Formen haben; durch Untersuchen des Histogramms, das zu jedem Block gehört, ist es somit möglich, das Vorhandensein eines Codes und seinen Typ zu identifizieren. Im vorliegenden Kontext bezeichnet insbesondere der Begriff Histogramm einen Graphen, auf dessen x-Achse alle möglichen Richtungswerte (von 0º bis 180º in Schritten von 1º) aufgetragen sind und auf dessen y-Achse die Anzahl der Pixel des betrachteten Blocks, welche diesen Richtungswert haben, aufgetragen sind.
• Durch einen derartigen Aufbau von Richtungshistogrammen für die verschiedenen Codetypen kann tatsächlich verifiziert werden, daß:
• - die Stapelcodes (einschließlich der PDF417) und die Strichcodes gekennzeichnet sind durch eine starke Gradientendirektionalität, wie man in Fig. 4a sehen kann, die ein typisches Histogramm eines Stapelcodes zeigt;
• - der Maxicode gekennzeichnet ist durch das Fehlen von Direktionalität, wie in Fig. 4b gezeigt ist;
• - Datamatrix und der QR-Code gekennzeichnet sind durch eine doppelte Direktionalität im Quadrat, wie in Fig. 4c gezeigt ist.
• Auf dieser Basis wird der Schritt der Richtungsanalyse 22 wie in Fig. 5 gezeigt ausgeführt. Im einzelnen wird zunächst überprüft, ob der Kontrast des i-ten Blocks (der in Schritt 21 der Fig. 3 ermittelt wurde) größer ist als ein vorgegebener Schwellwert Th, Block 30. Wenn nein, Nein-Ausgang des Blocks 30, wird überprüft, ob alle Blöcke untersucht wurden, indem ein Zähler i (Block 31) erhöht wird und überprüft wird, ob der Zähler i gleich der gesamten Anzahl der Blöcke ist (Block 32). Wenn dies der Fall ist (Ja-Ausgang des Blocks 32), endet der Schritt der Richtungsanalyse 22, andernfalls (Nein-Ausgang) wird ein nachfolgender Block untersucht, und das Programm geht zum Block 30 zurück.
• Wenn jedoch der i-te Block größer ist als der vorgegebene Schwellwert, Ja-Ausgang des Blocks 30, wird die vorherrschende Richtung gesucht, die dem absoluten Maximum des Richtungshistogramms in dem betrachteten Blocks entspricht; insbesondere wird zunächst innerhalb des Gradientenrichtungsbildes und in bezug auf den betrachteten Block die Anzahl der Punkte N(DIRj) mit einer j-ten vorgegebenen Richtung bestimmt, wobei alle Richtungen zwischen 0º und 180º in Schritten von z. B. 1º betrachtet werden und die Anzahl der Punkte mit der Richtung 0º, die Anzahl der Punkte mit der Richtung 1º, die Anzahl der Punkte mit der Richtung 2º usw. gezählt werden, Block 33. Das Maximum der eben ermittelten Werte N(DIRj) wird dann gesucht, und die Richtung j, die zu diesem Maximalwert gehört, wird als die vorherrschende Richtung DMAX gespeichert, Block 34.
• Danach, Block 35, wird die Anzahl der Punkte NP1 mit einer Richtung, die in einem vorgegebenen Intervall liegt, das um die vorherrschende Richtung DMAX zentriert ist, berechnet (z. B. zwischen +/- 5º und +/- 15º), und die Energie um den Maximalwert wird innerhalb des gewählten Intervalls berechnet; das Verhältnis P 1 der Punkte NP 1 in bezug auf die Gesamtzahl T der Blockpunkte wird berechnet als P 1 = NP1/T·100, Block 36, und es wird überprüft, ob das so berechnete Verhältnis P1 wenigstens gleich einem vorgegebenen Schwellwert Ph ist, Block 37. Der Schwellwert Ph kann z. B. zwischen 5% und 40% variieren. Wenn das Ergebnis positiv ist (Ja-Ausgang), wird gespeichert, daß der i-te Block einen Strichcode oder einen Stapelcode enthält, und die vorherrschende Richtung DMAX wird gespeichert, Block 38. Andernfalls (Nein-Ausgang des Blocks 37) wird die Summe NP2 der Punkteanzahl in einer Richtung, die in einem vorgegebenen Intervall (variabel zwischen +/- 10º und +/-20º) der vorherrschenden Richtung DMAX liegt, sowie die Anzahl der Punkte in einer Richtung, die in einem vorgegebenen Intervall (variabel z. B. zwischen +/-10º und +/-20º) der Quadraturrichtung in bezug auf die vorherrschende Richtung (DMAX + 90º, Berechnung der Energie; die zu den zwei vorherrschenden Richtungen gehört, Block 40) liegt, berechnet; das Verhältnis P2 der Punkte NP2 in bezug auf die gesamte Anzahl T der Blockpunkte wird als P2 = NP2/T·100 berechnet, Block 41, und der Wert des Verhältnisses P2 wird überprüft, Block 42. Wenn das gerade berechnete Verhältnis P2 kleiner ist als ein erster Schwellwert Pm (variabel z. B. zwischen 5% und 35%), wird gespeichert, daß der i-te Block einen Maxicode enthält und eine vorherrschende Richtung hat, Block 43; wenn das gerade berechnete Verhältnis P2 wenigstens gleich einem zweiten Schwellwert Pn ist, der größer ist als der erste Schwellwert Pm (variabel z. B. zwischen 30% und 40%), wird gespeichert, daß der i-te Block einen Datamatrix-Code oder einen QR-Code enthält, und die vorherrschenden Richtungen DMAX und DMAX + 90º werden gespeichert, Block 44; in einem Zwischenfall Pm < P2 < Pn wird gespeichert, daß der Code ein Maxicode, ein Datamatrix-Code oder ein QR- Code sein kann, Block 45, und es wird später durch den nachfolgenden Decodieralgorithmus unterschieden oder durch Wiederholen des angegebenen Verfahrens anhand eines Blocks neben dem benachbarten Block.
• In allen Fällen folgt den Blöcken 43, 44 und 45 der Block 31 für die optionale Untersuchung eines nachfolgenden Blocks.
• Wieder in Fig. 2 kann der Schritt 13 der Feinlokalisierung auf bekannte Weise ausgeführt werden und ist daher nicht im einzelnen gezeigt. Es sei nur in Erinnerung gerufen, daß dieser Schritt abhängig von dem Codetyp unterschiedliche Verfahren erfordert. Für Datamatrix (Fig. 1a) ist es z. B. möglich, die Koordinaten der L-Form (welche die linke und untere Seite des Codes der Fig. 1a begrenzen) mit einem Kantenerfassungsalgorithmus zu ermitteln, der z. B. in dem zuvor genannten Text von D. Montgomery und G. C. Runger beschrieben ist, oder mit dem Standardverfahren, das in den AIM-Spezifikationen vorgeschlagen wird (AIM- Spezifikationen für Datamatrix), gestützt auf eine Suche nach zwei Segmenten mit einer minimalen Abmessung (eine Abmessung, die aus den Anwendungsspezifikationen bekannt ist), welche die zwei Seiten in der L-Form sind.
• Die Suche nach Abschnitten kann in dem digitalisierten Bild, das in binäre Form umgewandelt ist, auch mit einem Grau-Schwellwert ausgeführt werden (das Segment ist eine Folge von benachbarten schwarzen Pixeln) oder anhand des Gradientenintensitätsbildes pixelweise ausgeführt werden (Suche nach den Kanten der L-Form).
• Soweit Maxicode betroffen ist (Fig. 1b) umfaßt der Schritt 13 der Feinlokalisation die Ermittlung der Koordinaten des Codeszentrums oder Bull Eye (das Ziel, das durch eine Reihe von zu dem Codezentrum konzentrischen Kreisen gebildet wird) mittels Standardverfahren, die in der AIM-Spezifikationen beschrieben sind (AIM-Spezifikationen für Maxicode), gestützt auf die Suche nach der "Vorlage", die durch den Wechsel von weißen und schwarzen Pixeln gebildet ist und für das Ziel charakteristisch ist.
• Im Fall von linearen Codes (Strichcodes) oder Stapelcodes (PDF417) werden wenigstens drei Codesstriche mittels Algorithmen zum Erkennen bekannter Segmente ermittelt (siehe z. B. der zuvor genannte Text von D. Montgomery und G. C. Runger).
• Während des Schritts 13 der Feinlokalisierung ist es auch möglich, Informationen in bezug auf die geometrische Struktur und die Abmessungen des Codes zu extrahieren, die nachfolgend in dem Segmentierungsschritt 14 verwendet werden können. Im Falle von Maxicode werden z. B. die Abmessungen der Hexagone, welche den Code bilden, abgeschätzt.
• Der Segmentierungsschritt 14 trennt den Codebereich von dem restlichen Teil des digitalisierten Bildes. Der Zweck dieser Operation ist die Ermittlung der Koordinaten der vier Scheitelpunkte des Vierseits, das den Code bildet. Die Segmentierung kann durch ein progressives Pixeladditionsverfahren (Bereichswachstum) realisiert werden, das aus der Literatur bekannt ist (z. B. unter Verwendung von "konvexen Hüllen"-Algorithmen, die beschrieben sind in "Algorithmen" von R. Sedgewick, Herausgeber Addison Wesley), unter Verwendung der Feinlokalisierungsinformation. Für einen Maxicode ist es z. B. möglich, einen Bereichswachstum anzuwenden, indem bei dem äußeren Kreis des Bull Eye begonnen wird und eine Abschätzung der Abmessungen der einzelnen Hexagone und des von dem Code insgesamt belegten Bereichs vorgenommen wird. Das Bereichswachstum verwendet das Vorhandensein von Ruhebereichen um den Code.
• Im folgenden ist ein Beispiel in bezug auf die Anwendung der Schritte der Extraktion der interessierenden Merkmale 11 und der Ermittlung der interessierenden Bereiche 12 für ein digitalisiertes Bild beschrieben, das in Fig. 6a gezeigt ist. Das digitalisierte Bild, das 512 · 512 Pixel umfaßt, enthält zwei zu lokalisierende Maxicodes. Die Fig. 6b und 6c zeigen jeweils das Gradientenintensitätsbild und das Gradientenrichtungsbild, wie zuvor für den Schritt der Extraktion der interessierenden Merkmale 11 beschrieben. Die Fig. 6a und 6b zeigen auch die jeweiligen Maßstäbe, die in den zwei Bildern verwendet werden.
• Fig. 6d zeigt das Blockkontrastbild, das nach dem Aufteilen des Gradientenintensitätsbild der Fig. 6b in Blöcke und Berechnen des Kontrasts erhalten wird. In der Praxis stellt in Fig. 6d jedes kleine Quadrat ein Block dar, und das Bild insgesamt umfaßt 8 · 8 Blöcke. In Fig. 6d wird jedem Block ein Grauwert zugeordnet, der den Kontrastpegel des Block angibt. Je heller der Block ist, desto mehr Kontrast erhält er, wie auf der Skala rechts gezeigt. Die Figur zeigt bereits deutlich zwei Blöcke, die heller sind als andere.
• Fig. 6e zeigt das nach dem Schritt der Blockrichtungsanalyse erhaltene Bild (Block 22 der Fig. 5) und bezieht sich insbesondere nur auf Blöcke, die eine einzelne vorherrschende Richtung haben (Blöcke, welche die Bedingung P1 > Ph erfüllen, Block 37 in Fig. 5) und die daher Stapelcodes oder Strichcodes enthalten. In dem gezeigten Beispiel gibt es einen einzigen Block unter den Blöcken mit ausreichendem Kontrast, die in Fig. 6d gezeigt sind (bei der Position 2, 2), der eine starke Direktionalität hat.
• Fig. 6f zeigt ein Bild, das aus Fig. 6d abgeleitet ist und nur die Blöcke enthält, welche keine vorherrschende Richtungen aufweisen (Blöcke, welche die Bedingung P2 < Pm erfüllen, Block 43 der Fig. 5, und daher Maxicodes enthalten können) und die ein Kontrastpegel haben, der höher als ein vorgegebener Schwellwert ist. Das Bild der Fig. 6f wird dann einer weiteren Verarbeitung unterworfen, zum Gruppieren der Zellen beginnend bei der hellsten (mit dem größten Kontrast), Ermitteln der Koordinaten des Zentrums des Bull Eye, Feinlokalisieren des Codes, präzises Ermitteln der geometrischen Grenzen des Codes und Decodieren, wie mit Bezug auf die Blöcke 24 und 13 bis 15 beschrieben ist.
• Die Vorteile des beschriebenen Verfahrens sind wie folgt. Zunächst ist es in bezug auf geometrische Verformungen robuster und erlaubt eine Lokalisierung und Segmentierung von Codes, die mit erheblichen Verschiebungs- und/oder Steigungswinkeln erfaßt würden. Das beschriebene Verfahren arbeitet zuverlässig auch im Falle unregelmäßiger Helligkeit; tatsächlich arbeite es lokal und ist daher unempfindlich gegen Helligkeitsänderungen in dem digitalisierten Bild insgesamt. Das vorliegende Verfahren beschleunigt schließlich den gesamten Schritt der Decodierung bidimensionaler Codes; die Angabe des Codetyps in dem interessierenden Bereich erlaubt tatsächlich die direkte Suche nach dem spezifischen Code, der vorhanden ist, ohne zu versuchen, nach anderen zu suchen. Wenn das digitalisierte Bild mehrere Codes enthält, kann die Feinlokalisierung und Segmentierung ferner für jeden von diesen parallel ausgeführt werden.
• Es ist offensichtlich, daß zahlreiche Modifikationen und Abwandlungen an dem beschriebenen und gezeigten Verfahren vorgenommen werden können, die alle im Bereich der Erfindung gemäß den Ansprüchen liegen. Insbesondere wird die Tatsache betont, daß die Erfindung zum Lokalisieren und Erkennen eines bestimmten Codes eingesetzt werden kann, indem das Blockdiagramm der Fig. 5 auf den erforderlichen Codetyp begrenzt wird, obwohl ihre beabsichtigte Anwendung die Lokalisierung und Erkennung aller möglichen Arten von zweidimensionalen Codes (einschließlich Strichcodes) ist.
• Das Verfahren für die Blockaufteilung (Schritt 20 in Fig. 3) kann modifiziert werden. Wenn es eine große Vielzahl von Abmessungen der zu decodierenden Codes relativ zu den Abmessungen des digitalisierten Bildes gibt, ist es möglich, die interessierenden Bereiche mittels verschiedener Blockaufteilungsniveaus unter Verwendung verschiedener Maßstäbe, die gleichzeitig oder in Folge eingesetzt werden können, abzusuchen (zunächst die kleineren Blöcke, dann die größeren).
• Die Abmessungen des Blocks können sich von den angegebenen unterscheiden; insbesondere wird in bezug auf die optischen Parameter der Einrichtung und den maximalen Leseabstand eine Wahl getroffen, so daß die maximalen Blockabmessungen nicht die Abmessungen eines Codes überschreiten oder so daß die maximalen Blockabmessungen einen Codeteil oder maximal einen gesamten Code, jedoch nicht mehr als einen Code enthalten, so daß eine hohe Lokalisierungsgeschwindigkeit erreicht wird.
• Obwohl bei dem gegebenen Beispiel eine Berechnung des Gradientenrichtungsbildes vor der Aufteilung in Blöcke und für alle Pixel des digitalisierten Bildes ausgeführt wird, ist es zusätzlich auch möglich, diese Berechnung nach der Aufteilung nur für die Blöcke mit wenigstens einem minimalen Intensitätswert des Gradienten auszuführen.
• Anstelle der Berechnung der vorherrschenden Helligkeitsgradientenrichtung nur für die Blöcke, die ein Kontrastniveau haben, das höher als ein bestimmter Schwellwert ist, ist es schließlich auch möglich, diese vorherrschende Richtung für alle Blöcke des digitalisierten Bildes zu berechnen, wenn diese Informationen in der nachfolgenden Verarbeitung sinnvoll sein kann, obwohl man verstehen wird, daß die beschriebene Lösung es möglich macht, die Anzahl der notwendigen Rechenoperationen zu reduzieren.

Claims (21)

1. Verfahren zum Lokalisieren von Codes in zweidimensionalen Bildern, welche den Schritt der Erfassung (10) eines zweidimensionalen Bildes umfaßt, das aus einer Vielzahl von durch einen Helligkeitswert charakterisierten Punkten gebildet ist, gekennzeichnet durch die Schritte:

- Aufteilen (20) des zweidimensionalen Bildes in eine Vielzahl von Bildregionen, wobei jede Bildregion eine zugehörige erste Anzahl von Punkten (T) umfaßt;

- Bestimmen (21) einer ersten Größe für jede der Bildregionen, die mit der Intensität der Helligkeitsänderung jeweiliger Punkte bezüglich benachbarter Punkte korreliert ist;

- Bestimmen (22) mindestens einer zweiten Größe (P1, P2) für jede der Bildregionen, die mit der Richtung der Helligkeitsänderung der jeweiligen Punkte bezüglich benachbarter Punkte korreliert ist; und

- Bestimmen (35-44) jeglichen Vorhandenseins und Art eines Codes anhand der ersten und zweiten Größe in jeder der Bildregionen.

2. Verfahren nach Anspruch 1, dadurch gekennzeichnet, daß der Schritt des Bestimmens (21) einer ersten Größe den Schritt des Berechnens eines Kontrastwertes für jede der Bildregionen umfaßt.

3. Verfahren nach Anspruch 2, dadurch gekennzeichnet, daß der Schritt des Berechnens eines Kontrastwertes den Schritt des Berechnens eines Helligkeitsgradienten in jedem Punkt einer jeweiligen Bildregion bezüglich benachbarter Punkte und das Addieren des Helligkeitsgradienten für alle Punkte der jeweiligen Bildregion umfaßt.

4. Verfahren nach Anspruch 2, dadurch gekennzeichnet, daß der Schritt des Berechnens eines Kontrastwertes den Schritt des Berechnens des Verhältnisses zwischen einer zweiten Anzahl von Punkten der jeweiligen Bildregion mit einer Helligkeit größer als ein vorbestimmter Schwellwert und einer dritten Anzahl von Punkten der jeweiligen Bildregion mit einer Helligkeit kleiner als der vorbestimmte Schwellwert umfaßt.

5. Verfahren nach einem der Ansprüche 1 bis 4, dadurch gekennzeichnet, daß der Schritt des Bestimmens (22) mindestens einer zweiten Größe (P1, P2) den Schritt des Berechnens der Richtung des Helligkeitsgradienten in jedem Punkt einer jeweiligen Bildregion bezüglich benachbarter Punkte und das Aufsuchen einer vorherrschenden Richtung (DMAX) aus den berechneten Richtungen der Helligkeitsgradienten umfaßt.

6. Verfahren nach Anspruch 5, dadurch gekennzeichnet, daß der Schritt des Suchens die Schritte umfaßt:

- Berechnen (33) der Anzahl von Punkten der jeweiligen Bildregion mit vorbestimmter Richtung des Helligkeitsgradienten, wodurch eine Vielzahl von numerischen Werten erhalten wird, von denen jeder einer der vorbestimmten Richtungen des Helligkeitsgradienten zugeordnet ist; und

- Ermitteln (34) eines dem Maximum des numerischen Wertes zugeordneten Richtungswertes aus den Werten der vorbestimmten Richtungen des Helligkeitsgradienten.

7. Verfahren nach Anspruch 6, dadurch gekennzeichnet, daß der Schritt des Bestimmens (35-44) jeglichen Vorhandenseins und Typs eines Codes die Schritte umfaßt:

- Berechnen (35, 36) eines Richtungswertes (P1) für jede Bildregion, wobei der Richtungswert (P1), mit dem Verhältnis von den Punkten der Bildregion korreliert ist, die einen Helligkeitsgradienten-Richtungswert nahe der vorherrschenden Richtung (DMAX) haben;

- Nachprüfen (37), ob der Richtungswert (P1) einen ersten vorbestimmten Schwellwert überschreitet;

- wenn ja, Zuordnen (38) der jeweiligen Bildregion zu einem ersten Code-Typ.

8. Verfahren nach Anspruch 7, dadurch gekennzeichnet, daß der erste Code-Typ von Balkencodes und gestapelten Codes umfaßt.

9. Verfahren nach Anspruch 7 oder 8, dadurch gekennzeichnet, daß der Schritt des Berechnens eines Richtungswertes (35, 36) die Schritte des Berechnens (35) einer vierten Anzahl von Punkten (NP1) mit einem Helligkeitsgradienten-Richtungswert innerhalb eines ersten, die vorherrschende Richtung (DMAX) einschließenden Richtungsintervalles und das Berechnen (36) des Verhältnisses zwischen der vierten Anzahl von Punkten und der ersten Anzahl von Punkten (T) umfaßt.

10. Verfahren nach Anspruch 9, dadurch gekennzeichnet, daß das erste Intervall ±15º bezüglich der vorherrschenden Richtung umfaßt.

11. Verfahren nach Anspruch 9, dadurch gekennzeichnet, daß das erste Intervall ±5º bezüglich der vorherrschenden Richtung umfaßt.

12. Verfahren nach einem der Ansprüche 6 bis 11, dadurch gekennzeichnet, daß der Schritt des Bestimmens (35-44) jeglichen Code-Vorhandenseins und -Typs die Schritte umfaßt:

- Berechnen (40, 41) eines Bidirektionalitätswerts (P2) für jede Bildregion, der mit dem Verhältnis der Punkte der Bildregion mit Helligkeitsgradienten- Richtungswerten nahe der vorherrschenden Richtung (DMAX) und einer Querrichtung (DMAX + 90º) senkrecht zur vorherrschenden Richtung korreliert ist;

- Nachprüfen (42), ob der Bidirektionalitätswert einen zweiten vorbestimmten Schwellwert überschreitet;

- wenn ja, Verknüpfen (44) der jeweiligen Bildregion mit einem möglichen zweiten Code-Typ.

13. Verfahren nach Anspruch 12, dadurch gekennzeichnet, daß der zweite Code- Typ Datamatrix- oder QR-Codes umfaßt.

14. Verfahren nach Anspruch 13, dadurch gekennzeichnet, daß der Schritt des Berechnens (40, 41) eines Bidirektionalitätswertes die Schritte des Berechnens (40) einer fünften Anzahl von Punkten (NP2), deren Richtungswerte des Helligkeitsgradienten von einem zweiten und dritten Richtungsintervall, welche die vorherrschende Richtung, bzw. die Querrichtung in sich fassen, eingeschlossen sind, und dem Berechnen (41) des Verhältnisses zwischen der fünften Anzahl von Punkten und der ersten Anzahl von Punkten (T) umfaßt.

15. Verfahren nach Anspruch 14, dadurch gekennzeichnet, daß das zweite Intervall ±20º bezüglich der vorherrschenden Richtung (DMAX) und das dritte Intervall ±10º bezüglich der Querrichtung (DMAX + 90º) beträgt.

16. Verfahren nach Anspruch 14, dadurch gekennzeichnet, daß das zweite Intervall ±10º bezüglich der vorherrschenden Richtung (DMAX) und das dritte Intervall ±10º bezüglich der Querrichtung (DMAX + 90º) beträgt.

17. Verfahren nach einem der Ansprüche 11 bis 16, gekennzeichnet durch weitere Schritte:

- Prüfen (42), ob der Bidirektionalitätswert kleiner als ein dritter vorbestimmter Schwellenwert ist, der niedriger als der zweite vorbestimmte Schwellenwert ist;

- wenn ja, Zuordnen (43) der jeweiligen Bildregion zu einem möglichen dritten Code-Typ.

18. Verfahren nach Anspruch 17, dadurch gekennzeichnet, daß der dritte Code- Typ Maxicode-Codes umfaßt.

19. Verfahren nach einem der Ansprüche 7 bis 18, dadurch gekennzeichnet, daß nach dem Schritt des Bestimmens einer ersten Größe (21) der Schritt des Auswählens (30) von Regionen mit hohem Kontrast aus den Bildregionen ausgeführt wird, wobei die erste Größe größer als ein vorbestimmter Wert ist, und dadurch, daß der Schritt des Bestimmens (35-44) jeglichen Vorhandenseins oder Code-Typs nur für die Regionen mit hohem Kontrast ausgeführt wird.

20. Verfahren nach einem der vorangehenden Ansprüche, gekennzeichnet durch die nach dem Schritt des Bestimmens jeglichen Codes ausgeführten Schritte:

- Ordnen (23) der Bildregionen mit einem vorbestimmten Code-Typ basierend auf der Bedeutung; und

- Vereinigen (24) der geordneten Bildregionen durch einen Region-Growing- Schritt.

21. Verfahren nach Anspruch 20, dadurch gekennzeichnet, daß der Schritt des Ordnens (23) den Schritt des Ordnens der Bildregionen entsprechend der ersten Größe umfaßt.